intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Ngọc Như Loan

Chia sẻ: Dien_vi10 Dien_vi10 | Ngày: | Loại File: PPTX | Số trang:84

52
lượt xem
3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách (List)" cung cấp cho người học các kiến thức: Danh sách liên kết đơn, các thao tác trên danh sách liên kết, listInsert, listwalk (duyệt ds),... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Ngọc Như Loan

  1. GV: Đỗ Ngọc Như Loan
  2. Danh sách liên kết đơn Danh sách liên kết kép Danh sách liên kết 
  3. Danh sách liên kết đơn  Danh sách liên kết đơn là một tập các nút  biểu diễn cấu trúc dữ liệu gồm các đối tượng  được sắp đặt theo một trật tự tuyến tính  Trật tự tuyến tính trong danh sách liên kết  được xác định bởi các pointer kết hợp với mỗi  đối tượng  Danh sách liên kết cung cấp một sự biểu  diễn mềm dẻo và đơn giản cho các tập động,  hỗ trợ các thao tác như tìm kiếm, chèn, xóa  v.v
  4. Ví dụ về một danh sách liên kết đơn  Mỗi nút x trong DS lưu trữ một đối tượng có  một khóa (có thể có thông tin khác) và một  pointer next chỉ đến nút (đối tượng) kế tiếp  Nếu next[x]= NULL, thì x là nút cuối cùng còn  gọi là đuôi của danh sách  Danh sách L là rỗng khi L = NULL
  5. Các thao tác trên danh sách  liên kết  ListInitialize (L)  ListSearch (L, k)  ListInsert (L, k)  ListDelete (L, k)  ListWalk (L)
  6. ĐỊNH NGHĨA DANH SÁCH  LIÊN KẾT ĐƠN TRONG C++  Danh sách các đối tượng có khóa là số  nguyên typedef struct CELL *LIST; struct CELL { int key; LIST next; }; LIST L;
  7. ListInitialize void ListInitialize(LIST &L) { L=NULL; }
  8. ListSearch  Thao tác ListSearch(L, k) tìm một đối tượng  có khóa k trong danh sách L  Nếu có đối tượng có khóa k, thủ tục sẽ trả về  một pointer chỉ đến đối tượng này  Nếu không có đối tượng nào có khóa bằng k  trong danh sách, thủ tục trả về NULL
  9. ListSearch LIST ListSearch(LIST L, int k) { LIST x; x=L; while(x!=NULL && x->key!=k) x=x->next; return x; }
  10. ListInsert  Thao tác ListInsert(L, k) thực hiện đơn giản  bằng cách chèn đối tượng x có khóa k vào  đầu của L
  11. ListInsert void ListInsert(LIST &L, int k) { LIST x; x=new(CELL); x->key=k; x->next=L; L=x; }
  12. ListDelete  Thao tác ListDelete(L, k) xóa đối tượng x có  khóa k khỏi L  Được thực hiện bằng cách tìm x và cập nhật  lại các con trỏ nút y đi trước x để loại x ra  khỏi danh sách
  13. ListDelete void ListDelete(LIST &L,int k) { LIST x, y; if(L!= NULL) { y= NULL; x =L; while(x!=NULL && x->key!=k) { y=x; x=x->next; } if(x!=NULL) //Tìm thấy {
  14. ListWalk (Duyệt DS) void ListWalk(LIST L) { if(L!=NULL) { cout
  15. ĐỘ PHỨC TẠP CÁC THAO  TÁC  ListSearch(L, k) có độ phức tạp trung bình  T(n) = O(n)  ListInsert(L, k) có độ phức tạp T(n)=O(1)  ListDelete(L, k) có độ phức tạp trung bình  T(n) = O(n)
  16. DANH SÁCH LIÊN KẾT KÉP  Danh sách liên kết kép là cấu trúc dữ liệu  trong đó các đối tượng được sắp đặt theo  một trật tự tuyến tính  Trật tự tuyến tính trong danh sách liên kết  kép được xác định bởi một cặp pointer trong  mỗi đối tượng
  17. ĐỊNH NGHĨA DANH SÁCH  LIÊN KẾT KÉP TRONG C++  Danh sách các đối tượng có khóa là số  nguyên typedef struct CELL *LIST; struct CELL { int key; LIST prev, next; }; LIST L;
  18. ListInitialize void ListInitialize(LIST &L) { L=NULL; }
  19. ListSearch  Thao tác ListSearch(L, k) tìm một phần tử có  khóa k trong danh sách L  Nếu có phần tử có khóa k, thủ tục sẽ trả về  một pointer chỉ đến phần tử này  Nếu không có đối tượng nào có khóa bằng k  trong danh sách, thủ tục trả về NULL
  20. ListSearch LIST ListSearch(LIST L, int k) { LIST x; x=L; while(x!=NULL && x->key!=k) x=x->next; return x; }
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2