Chuong2_cautrucdulieudanhsach

  • Số trang: 80 |
  • Loại file: PDF |
  • Lượt xem: 27 |
  • Lượt tải: 0
tranphuong5053

Đã đăng 6896 tài liệu

Mô tả:

KHOA KHOA HỌC MÁY TÍNH – BỘ MÔN LẬP TRÌNH BÀI GIẢNG CẤU TRÚC DỮ LIỆU (BẬC CAO ĐẲNG) Chương2: CẤU TRÚC DỮ LIỆU DANH SÁCH Nguyễn Thanh Cẩm NỘI DUNG TRÌNH BÀY 1. Danh sách 2. Danh sách đặc 3. Danh sách liên kết 4. Ngăn xếp 5. Hàng đợi 1 1. Danh sách a. Định nghĩa b. Các phép toán trên danh sách 1. Danh sách a. Định nghĩa Danh sách là tập hợp hữu hạn các phần tử cùng kiểu (Elementtype) : a1, a2, …, an (n>=1) với tính chất: nếu biết được ai sẽ biết ai+1 (0<= i <= n-1 ) Danh sách được sắp xếp tuyến tính theo vị trí của chúng (position) Số các phần tử (n) của danh sách gọi là độ dài của danh sách. Nếu n=0 thì ta có danh sách rỗng. Ví dụ: 1. Danh sách b. Các phép toán trên danh sách Phép duyệt danh sách: là phép thăm tất cả các phần tử của danh sách thỏa mãn <điều kiện> nào đó để thực hiện công việc Ví dụ: Phép tìm kiếm: là thao tác tìm phần tử trong danh sách thỏa mãn điều kiện nào đó Ví dụ: 1. Danh sách b. Các phép toán trên danh sách Thêm phần tử vào danh sách: là thao tác thêm phần tử mới Vào danh sách. Phần tử có thể được thêm vào cuối, đầu hoặc giữa danh sách. Chú ý danh sách đầy Ví dụ: 1. Danh sách b. Các phép toán trên danh sách Loại bỏ phần tử khỏi danh sách: là thao tác loại bỏ phần tử khỏi danh sách. Trước khi loại bỏ phải xác định phần tử cần loại bỏ (tìm kiếm). Chú ý: sau khi loại bỏ, số phần tử của danh sách giảm đi 1 đơn vị Ví dụ: 1. Danh sách b. Các phép toán trên danh sách Sửa đổi phần tử trong danh sách: là thao tác hiệu chỉnh phần tử trong danh sách. Trước khi hiệu chỉnh cần phải xác định phần tử cần hiệu chỉnh (tìm kiếm) Ví dụ: Sắp xếp thứ tự danh sách: là thao tác sắp lại thứ tự các phần tử trong danh sách theo một quy tắc nào đó Ví dụ: 1. Danh sách b. Các phép toán trên danh sách Tách một danh sách thành nhiều danh sách: là thao tác tách một phần hoặc tất cả các phần tử trong DS đưa sang các danh sách khác Vd: Ghép nhiều danh sách thành danh sách mới: là thao tác ngược lại của quá trình tách. Trộn nhiều danh sách thành danh sách mới 2. Danh sách đặc a. Định nghĩa b. Khai báo c. Các phép toán d. Đặc điểm của danh sách đặc 2. Danh sách đặc a. Định nghĩa Danh sách đặc là danh sách mà các phần tử được sắp xếp kế tiếp nhau trong bộ nhớ, phần tử ai+1 đứng sau phần tử ai. a0 add[1] a1 … ai add[i] ai+1 … an-2 an-1 d add[i] = add[1] + (i-1)*d add[n] 2. Danh sách đặc b. Khai báo #define MaxLength ... //Số nguyên thích hợp để chỉ độ dài của danh sách typedef ... ElementType; //kiểu của phần tử trong danh sách typedef 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 DS Position Last; //giữ độ dài danh sách } List; Vd: 2. Danh sách đặc c. Các phép toán i. Khởi tạo danh sách rỗng ii. Kiểm tra danh sách rỗng iii. Tìm kiếm phần tử trong danh sách iv. Chèn phần tử vào danh sách v. Loại bỏ phần tử khỏi danh sách 2. Danh sách đặc c. Các phép toán i. Khởi tạo danh sách rỗng void Make_List(List *L) { L->Last = 0; } Trong đó Last chỉ vị trí của phần tử cuối cùng trong danh sách và đó cũng là độ dài hiện tại của danh sách 2. Danh sách đặc c. Các phép toán ii. Kiểm tra danh sách rỗng Danh sách rỗng là một danh sách mà độ dài của nó bằng 0. int Empty_List(List L) { return L.Last == 0; } 2. Danh sách đặc c. Các phép toán iii. Chèn phần tử vào danh sách Giả sử ta chèn phần tử có nội dung x vào danh sách ở vị trí p. Khi đó các phần tử từ vị trí thứ p đến vị trí thứ last được di chuyển ra sau 1 đơn vị và độ dài danh sách tăng lên 1 đơn vị. 2. Danh sách đặc c. Các phép toán Giải thuật Chèn phần tử vào danh sách void Insert_List(ElementType X, Position P, List *L){ if (L->Last==MaxLength) printf("Danh sach day"); else if ((P<0) || (P>L->Last)) printf("Vi tri khong hop le"); else{ Position i; for(i=L.Last; i>=p; i--) L->element[i+1]= L->element[i]; L->Elements[p]=X; L->Last++; } } 2. Danh sách đặc c. Các phép toán iv. Loại bỏ phần tử khỏi danh sách Để loại bỏ phần tử vị trí p ra khỏi danh sách L ta dời các phần tử từ vị trí p+1 đến cuối danh sách sang trái 1 vị trí. Lưu ý: độ dài của danh sách giảm đi 1 đơn vị 2. Danh sách đặc c. Các phép toán iv. Loại bỏ phần tử khỏi danh sách Giải thuật loại bỏ void Delete_List(Position P,List *L){ if ((P<0) || (P>L->Last)) printf("Vi tri khong hop le"); else if (Empty_List(*L)) printf("Danh sach rong!"); else{ Position i; for(i=P;iLast;i++) L->Elements[i] = L->Elements[i+1]; L->Last--; } } 2. Danh sách đặc c. Các phép toán v. Tìm kiếm phần tử trong danh sách Trường hợp danh sách không thứ tự Position Search_List(ElementType X,List L){ Position found=0, i=0; if (Empty_List(L)) printf("Danh sach rong!"); else{ while (i - Xem thêm -