Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản

Bài giảng Cấu trúc dữ liệu và giải thuật - Các cấu trúc dữ liệu cơ bản trình bày những nội dung chính sau: Các khái niệm cơ bản, mảng và mảng động, con trỏ và cấu trúc liên kết, danh sách tuyến tính. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu cơ bản REVIEW• Dùng định lý thợ để đưa ra các tiệm cận chặt cho các công thức đệ quy sau ?a) ? ? = 3? 2 +? ?b) ? ? = 5? + ?2 2Chapter 2Các cấu trúc dữ liệucơ bảnNội dung• Các khái niệm cơ bản• Mảng và mảng động• Con trỏ và cấu trúc liên kết• Danh sách tuyến tính2.1 CÁC KHÁI NIỆM CƠ BẢN 2.1 Khái niệm cơ bản• Xử lý dữ liệu trên máy tính xét cho cùng là xử lý với các bit• Một kiểu dữ liệu (data type): là một tập các giá trị và nhóm các phép toán được thực hiện trên các giá trị đó. • Chỉ ra cách sử dụng các nhóm bit và các phép toán thực hiện trên các nhóm bit• VD. Kiểu số nguyên char số bit : 8 bit các phép toán +, -, *, /, % Khái niệm cơ bản • Các kiểu dữ liệu dựng sẵn (Built-in data types): được xây dựng sẵn trong ngôn ngữ lập trình Macintosh IBM PC Metrowerks CW Windows XP ANSI CType (Default) Linux on a PC Windows NT Minimumchar 8 8 8 8int 32 32 32 16short 16 16 16 16long 32 32 32 32long long 64 64 64 64 Ngôn ngữ lập trình CKhái niệm cơ bản • Chuẩn IEEE754/85: Tổng Dấu Mũ Độ lệch mũ Giá trị Type cộng (sign) (Exponent) (Exponent Bias) (fraction) (bit)Half (IEEE 1 5 15 10 16754-2008)Single 1 8 127 23 32Double 1 11 1023 52 64Quad 1 15 16383 112 128 exponent  exponent bias v  (1) sign 2  (1  fraction)Khái niệm cơ bản• Kiểu dữ liệu trừu tượng (Abstract DataType - ADT) gồm: • Tập các giá trị • Tập các phép toán có thể thực hiện trên các giá trị này• Cách biểu diễn cụ thể bị bỏ qua khi xét đến ADT. • Làm trừu tượng hóa kiểu dữ liệu, không phụ thuộc ngôn ngữ lập trình cụ thể.• Cài đặt ADT là biểu diễn ADT bởi một ngôn ngữ lập trình cụ thể • Xét đến một biểu diễn cụ thể cho ADT• Các kiểu dữ liệu dựng sẵn chính là cài đặt của các ADT tương ứng bằng ngôn ngữ lập trình cụ thể.Khái niệm cơ bản• Cấu trúc dữ liệu (data structure): Gồm các kiểu dữ liệu và cách liên kết giữa chúng.• Cấu trúc dữ liệu mô tả cách tổ chức và lưu trữ dữ liệu trên máy tính để sử dụng một cách hiệu quả nhất.• Hai vấn đề của một cấu trúc dữ liệu: • Các thao tác mà nó hỗ trợ, và • Cách cài đặt các thao tác nàyKhái niệm cơ bản• Thay đổi cấu trúc dữ liệu không làm thay đổi tính chính xác của chương trình. Tuy nhiên nó sẽ làm thay đổi hiệu quả của chương trình.• Tốt nhất nên chọn cấu trúc dữ liệu cho hiệu quả cao nhất ngay từ khi thiết kế chương trình! Cấu trúc liên tục VS liên kết• Các cấu trúc dữ liệu có thể được chia thành liên tục (contiguous) hoặc liên kết(linked), tùy vào việc nó được cài đặt dựa trên mảng hay con trỏ. Cấu trúc được cấp phát liên tục: được cấp phát thành vùng bộ nhớ liên tục. VD mảng, ma trận, đống (heap), và bảng băm Cấu trúc dữ liệu liên kết: gồm các đoạn(chunk) trong bộ nhớ (không nằm liên tục) và được liên kết với nhau thông qua con trỏ. VD, danh sách, cây, và đồ thị danh sách kề.2.2 ARRAY – MẢNGMảng• Mảng : gồm các bản ghi có kiểu giống nhau, có kích thước cố định. Mỗi phần tử được xác định bởi chỉ số (địa chỉ)• Mảng là cấu trúc dữ liệu được cấp phát liên tục cơ bản.Mảng• Ưu điểm của mảng: • Truy cập phần tử với thời gian hằng số ?(?): vì thông qua chỉ số của phần tử ta có thể truy cập trực tiếp vào ô nhớ chứa phần tử. • Sử dụng bộ nhớ hiệu quả: chỉ dùng bộ nhớ để chứa dữ liệu nguyên bản, không lãng phí bộ nhớ để lưu thêm các thông tin khác. • Tính cục bộ về bộ nhớ: các phần tử nằm liên tục trong 1 vùng bộ nhớ, duyệt qua các phần tử trong mảng rất dễ dàng và nhanh chóng.• Nhược điểm: không thể thay đổi kích thước của mảng khi chương trình đang thực hiện.Mảng• Mảng động (dynamic array): cấp phát bộ nhớ cho mảng một cách động trong quá trình chạy chương trình. Trong C là malloc và cal ...