Bài giảng Cấu trúc dữ liệu: Chương 2 - TS. Trần Cao Đệ

Bài giảng Cấu trúc dữ liệu: Chương 2 trình bày các kiểu dữ liệu trừu tượng cơ bản như kiểu dữ liệu trừu tượng danh sách, các phép toán trên danh sách, cài đặt danh sách bằng mảng,... Tham khảo nội dung bài giảng để hiểu rõ hơn về các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 2 - TS. Trần Cao Đệ CÁC KIỂU DỮ LIỆUTRỪU TƯỢNG CƠ BẢN BASIC ABSTRACT DATA TYPES TS. Trần Cao Đệ Năm 2010 1 KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST)„ Danh sách: một tập hợp hữu hạn các phần tử có cùng một kiểu (ElementType).„ Ta biểu diễn danh sách như là một chuỗi các phần tử của nó: a1, a2, . . ., an với n ≥ 0. „ Nếu n=0 ta nói danh sách rỗng (empty list). „ Nếu n > 0: „ a1 là phần tử đầu tiên „ an là phần tử cuối cùng của danh sách. „ Số phần tử của danh sách ta gọi là độ dài của danh sách. 2„ Các phần tử của danh sách có thứ tự tuyến tính theo vị trí (position) xuất hiện của các phần tử. „ Ta nói ai đứng trước ai+1, với i từ 1 đến n-1; „ ai là phần tử đứng sau ai-1, với i từ 2 đến n. „ ai là phần tử tại vị trí thứ i, hay phần tử thứ i của danh sách.„ Ví dụ: Tập hợp họ tên các sinh viên của lớp TINHOC 28 được liệt kê trên giấy như sau: 1. Nguyễn Trung Cang 2. Nguyễn Ngọc Chương 3. Lê Thị Lệ Sương 4. Trịnh Vũ Thành 5. Nguyễn Phú Vĩnh là một danh sách. Danh sách này gồm có 5 phần tử, mỗi phần tử có một vị trí trong danh sách theo thứ tự xuất hiện của nó. 3 Các phép toán trên danh sáchx: phần tử kiểu ElementType „ NEXT(p,L) cho kết quả là vị tríp: vị trí (position) của phần tử (kiểu position) đi sauL: LIST phần tử p.„ INSERT_LIST(x,p,L): xen phần „ PREVIOUS(p,L) cho kết quả là tử x, tại vị trí p trong danh sách L. vị trí của phần tử đứng trước phần tử p trong danh sách.„ LOCATE(x,L) tìm kiếm và định vị phần tử có nội dung x đầu tiên „ FIRST(L) cho kết quả là vị trí trong danh sách L. của phần tử đầu tiên trong danh sách. „ Nếu x không có trong danh sách thì vị trí sau phần tử cuối „ EMPTY_LIST(L) cho kết quả cùng của danh sách được trả TRUE nếu danh sách có rỗng, về, tức là ENDLIST(L). ngược lại nó cho giá trị FALSE.„ RETRIEVE(p,L) lấy giá trị của „ MAKENULL_LIST(L) khởi tạo phần tử ở vị trí p (kiểu position) một danh sách L rỗng. của danh sách L;„ DELETE_LIST(p,L) xoá phần Các phép toán trừu tượng đã được tử ở vị trí p của danh sách. định nghĩa ở đây như là các phép toán nguyên sơ. 4Ví dụ: Dùng các phép toán trừu tượng trên danh sách, viết một chương trình con nhận một tham số là danh sách rồi sắp xếp danh sách theo thứ tự tăng dần. Giả sử SWAP(p,q) thực hiện việc đổi chỗ hai phần tử tại vị trí p và q trong danh sách.void SORT(LIST& L){ Position p= FIRST(L); //vị trí phần tử đầu tiên trong danh sách while (p!=ENDLIST(L)){ Position q=NEXT(p,L); //vị trí phần tử đứng ngay sau phần tử p while (q!=ENDLIST(L)){ if (RETRIEVE(p,L) > RETRIEVE(q,L)) swap(p,q); // hoán chuyển nội dung phần tử q=NEXT(q,L); } p=NEXT(p,L); }} 5 Cài đặt danh sách bằng mảng (danh sách đặc)„ Dùng một mảng để lưu giữ liên tiếp các phần tử của danh sách từ vị trí đầu tiên của mảng.„ Ta định nghĩa vị trí của một phần tử trong danh sách là số thứ tự của phần tử trong danh sách Chỉ số 0 1 … Last-1 … Maxlength-1 Vị trí 1 2 Last MaxlengthNội dung Phần tử thứ 1 Phần tử thứ 2 … Phần tử cuối cùng … phần trong danh sách tử 6„ các khai báo cần thiết là#define MaxLength ...//Số nguyên thích hợp để chỉ độ dài của mảngtypedef ... ElementType;//kiểu của phần tử trong danh sáchtypedef int Position; //kiểu vị trí cuả các phần tửtypedef struct { ElementType Elements[MaxLength]; //mảng chứa các phần tử của danh sách Position Last; //giữ độ dài danh sách} List; 7 Chỉ số Phần tử Last=0„ Khởi tạo danh sách rỗngvoid MAKENULL_L ...