Trang 2
Bài giảng của PGS.TS. NGUYỄN ĐỨC NGHĨA Khoa học Máy tính Đại học Bách khoa Hà nội CTDL&TT – KHMT – ĐHBK Hà nội
Nội dung tài liệu
Trang 3
Nội dung 3.1. Các khái niệm 3.2. Mảng 3.3. Danh sách 3.4. Ngăn xếp 3.5. Hàng đợi CTDL & TT – KHMT – ĐHBK Hà nội Chap02-3
Trang 4
Chương 3. Các cấu trúc dữ liệu cơ bản 3.1. Các khái niệm 3.2. Mảng 3.3. Danh sách 3.4. Ngăn xếp 3.5. Hàng đợi CTDL & TT – KHMT – ĐHBK Hà nội Chap02-4
Trang 5
Kiểu dữ liệu (Data types) • Kiểu dữ liệu (data type) được đặc trưng bởi: 。tập các giá trị (a set of values) 。cách biểu diễn dữ liệu (data representation) được sử dụng chung cho tất cả các giá trị này và 。tập các phép toán (set of operations) có thể thực hiện trên tất cả các giá trị CTDL & TT – KHMT – ĐHBK Hà nội 5
Trang 6
Các kiểu dữ liệu dựng sẵn (Built-in data types) • Trong các ngôn ngữ lập trình thường có một số kiểu dữ liệu nguyên thuỷ đã được xây dựng sẵn. Ví dụ 。Kiểu số nguyên (Integer numeric types) • byte, char, short, int, long 。Kiểu số thực dấu phảy động (floating point numeric types) • float, double 。Các kiểu nguyên thuỷ khác (Other primitive types) • boolean 。Kiểu mảng (Array type) • mảng các phần tử cùng kiểu CTDL & TT – KHMT – ĐHBK Hà nội BGA
Trang 7
Dữ liệu đối với kiểu nguyên thuỷ Trong ngôn ngữ lập trình C Type Bits Minimum value Maximum value byte 8 -128 127 short 16 -32768 32767 char 16 0 65535 int 32 -2147483648 = -231 2147483647 = 231-1 long 64 -9223372036854775808 9223372036854775807 float 32 1.40 10-45 3.40 1038 double 64 4.9410-324 1.80 10308 Có thể có kiểu boolean với hai giá trị true hoặc false 7
Trang 8
Phép toán đối với kiểu dữ liệu nguyên thuỷ • Đối với kiểu: byte, char, short, int, long 。+, - , *, /, %, đổi thành xâu, ... • Đối với kiểu: float, double 。+, -, *, /, round, ceil, floor, ... • Đối với kiểu: boolean 。kiểm giá trị true, hay kiểm giá trị false • Nhận thấy rằng: Các ngôn ngữ lập trình khác nhau có thể sử dụng mô tả kiểu dữ liệu khác nhau. Chẳng hạn, PASCAL và C có những mô tả các dữ liệu số khác nhau. CTDL & TT – KHMT – ĐHBK Hà nội BGA
Trang 9
Kiểu dữ liệu trừu tường (Abstract Data Types) • Kiểu dữ liệu trừu tượng (Abstract Data Type -ADT) bao gồm: 。tập các giá trị (set of values) và 。tập các phép toán (set of operations) có thể thực hiện với tất cả các giá trị này • Phần nào của kiểu dữ liệu (Data Type) đã bị bỏ qua trong ADT ? 。cách biểu diễn dữ liệu (data representation) được sử dụng chung cho tất cả các giá trị này • Việc làm này có ý nghĩa làm trừu tượng hoá khái niệm kiểu dữ liệu. ADT không còn phụ thuộc vào cài đặt, không phụ thuộc ngôn ngữ lập trình. CTDL & TT – KHMT – ĐHBK Hà nội 9
Trang 10
Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) • Ví dụ: ADT Đối tượng Phép toán (Object) (Operations) Danh sách (List) các nút chèn, xoá, tìm,... Đồ thị (Graphs) đỉnh, cạnh duyệt, đường đi, ... Integer -∞...,-1, 0, 1,... +∞ +, -, *, v.v... Real -∞, ...., +∞ +, -, *, v.v... Ngăn xếp các phần tử pop, push, isEmpty,... Hàng đợi Các phần tử enqueue, dequeue,... Cây nhị phân các nút traversal, find,... CTDL & TT – KHMT – ĐHBK Hà nội Chap02-10
Trang 11
Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) • Điều dễ hiểu là các kiểu dữ liệu nguyên thuỷ mà các ngôn ngữ lập trình cài đặt sẵn cũng được coi là thuộc vào kiểu dữ liệu trừu tượng. Trên thực tế chúng là cài đặt của kiểu dữ liệu trừu tượng trên ngôn ngữ lập trình cụ thể. • Định nghĩa. Ta gọi việc cài đặt (implementation) một ADT là việc diễn tả bởi các câu lệnh của một ngôn ngữ lập trình để mô tả các biến trong ADT và các thủ tục trong ngôn ngữ lập trình để thực hiện các phép toán của ADT, hoặc trong các ngôn ngữ hướng đối tượng, là các lớp (class) bao gồm cả dữ liệu (data) và các phương thức xử lý (methods). CTDL & TT – KHMT – ĐHBK Hà nội Chap02-11
Trang 12
Kiểu dữ liệu - Kiểu dữ liệu trừu tượng và Cấu trúc dữ liệu (Data Types, Data Structures and Abstract Data Types) • Có thể nói những thuật ngữ: kiểu dữ liệu, kiểu dữ liệu trừu tượng và cấu trúc dữ liệu nghe rất giống nhau, nhưng thực ra chúng có ý nghĩa khác nhau. 。Trong ngôn ngữ lập trình, kiểu dữ liệu của biến là tập các giá trị mà biến này có thể nhận. Ví dụ, biến kiểu boolean chỉ có thể nhận giá trị đúng hoặc sai. Các kiểu dữ liệu cơ bản có thể thay đổi từ ngôn ngữ lập trình này sang NNLT khác. Ta có thể tạo những kiểu dữ liệu phức hợp từ những kiểu dữ liệu cơ bản. Cách tạo cũng phụ thuộc vào ngôn ngữ lập trình. 。Kiểu dữ liệu trừu tượng là mô hình toán học cùng với những phép toán xác định trên mô hình này. Nó là không phụ thuộc vào ngôn ngữ lập trình. 。Để biểu diễn mô hình toán học trong ADT ta sử dụng cấu trúc dữ liệu. CTDL & TT – KHMT – ĐHBK Hà nội Chap02-12
Trang 13
Cấu trúc dữ liệu (Data Structures) • Cấu trúc dữ liệu (Data Structures) là một họ các biến, có thể có kiểu dữ liệu khác nhau, được liên kết lại theo một cách thức nào đó. • Việc cài đặt ADT đòi hỏi lựa chọn cấu trúc dữ liệu để biểu diễn ADT. • Ta sẽ xét xem việc làm đó được tiến hành như thế nào? • Ô (cell) là đơn vị cơ sở cấu thành cấu trúc dữ liệu. Có thể hình dung ô như là cái hộp đựng giá trị phát sinh từ một kiểu dữ liệu cơ bản hay phức hợp. • Cấu trúc dữ liệu được tạo nhờ đặt tên cho một nhóm các ô và đặt giá trị cho một số ô để mô tả sự liên kết giữa các ô. • Ta xét một số cách tạo nhóm. CTDL & TT – KHMT – ĐHBK Hà nội Chap02-13
Trang 14
Cấu trúc dữ liệu (Data Structures) • Một trong những cách tạo nhóm đơn giản nhất trong các ngôn ngữ lập trình đó là mảng (array). Mảng là một dãy các ô có cùng kiểu xác định nào đó. • Ví dụ: Khai báo trong Csau đây C int name[10] khai báo biến name gồm 10 phần tử kiểu cơ sở nguyên (integer). • Có thể truy xuất đến phần tử của mảng nhờ chỉ ra tên mảng cùng với chỉ số của nó. • Ta sẽ xét kỹ hơn kiểu mảng trong mục tiếp theo. CTDL & TT – KHMT – ĐHBK Hà nội Chap02-14
Trang 15
Cấu trúc dữ liệu (Data Structures) • Một phương pháp chung nữa hay dùng để nhóm các ô là cấu trúc bản ghi (record structure). • Bản ghi (record) là ô được tạo bởi một họ các ô (gọi là các trường) có thể có kiểu rất khác nhau. • Các bản ghi lại thường được nhóm lại thành mảng; kiểu được xác định bởi việc nhóm các trường của bản ghi trở thành kiểu của phần tử của mảng. • Ví dụ: Trong C mô tả C struct record { float data; int next; } reclist[100]; khai báo reclist là mảng 100 phần tử, mỗi ô là một bản ghi gồm 2 trường: data và next. CTDL & TT – KHMT – ĐHBK Hà nội Chap02-15
Trang 16
Con trỏ (Pointer) • Một trong những ưu thế của phương pháp nhóm các ô trong các NNLT là ta có thể biểu diễn mối quan hệ giữa các ô nhờ sử dụng con trỏ. • Định nghĩa. Con trỏ (pointer) là ô mà giá trị của nó chỉ ra một ô khác. • Khi vẽ các cấu trúc dữ liệu, để thể hiện ô A là con trỏ đến ô B, ta sẽ sử dụng mũi tên hướng từ A đến B. A B • Ví dụ: Để tạo biến con trỏ ptr để trỏ đến ô có kiểu cho trước, chẳng hạn celltype, ta có thể khai báo: Trong C celltype *ptr CTDL & TT – KHMT – ĐHBK Hà nội Chap02-16
Trang 17
Phân loại các cấu trúc dữ liệu • Trong nhiều tài liệu về CTDL thường sử dụng phân loại cấu trúc dữ liệu sau đây: 。Cấu trúc dữ liệu cơ sở (Base data structures). Ví dụ: trong C: int, char, float, double,... 。Cấu trúc dữ liệu tuyến tính (Linear data structures). Ví dụ: Mảng (Array), Danh sách liên kết (Linked list), Ngăn xếp (Stack), Hàng đợi (Queue), 。Cấu trúc dữ liệu phi tuyến (Nonlinear data structures). Ví dụ: Cây (trees), đồ thị (graphs), bảng băm (hash tables),... CTDL & TT – KHMT – ĐHBK Hà nội Chap03-17
Trang 18
Chương 3. Các cấu trúc dữ liệu cơ bản 3.1. Các khái niệm 3.2. Mảng 3.3. Danh sách 3.4. Ngăn xếp 3.5. Hàng đợi CTDL & TT – KHMT – ĐHBK Hà nội Chap02-18
Trang 19
3.2. Mảng 3.2.1. Kiểu dữ liệu trừu tượng mảng 3.2.2. Phân bổ bộ nhớ cho mảng 3.2.3. Các thao tác với mảng CTDL & TT – KHMT – ĐHBK Hà nội Chap03-19
Trang 20
Kiểu dữ liệu trừu tượng mảng (ADT Array ) • Mảng được định nghĩa như kiểu dữ liệu trừu tượng như sau: • Đối tượng (object): tập các cặp <index, value> trong đó với mỗi giá trị của index có một giá trị từ tập item. Index là tập có thứ tự một chiều hay nhiều chiều, chẳng hạn, {0, … , n-1} đối với một chiều, {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)} đối với 2 chiều, v.v. • Các hàm (Functions): Với mọi A Array, i index, x item, j, size integer Khởi tạo mảng: Array Create(j, list) ::= trả lại mảng j chiều, trong đó list là bộ j thành phần với thành phần thứ i là kích thước của chiều thứ i. Item không được định nghĩa. CTDL & TT – KHMT – ĐHBK Hà nội
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!