Cấu trúc dữ liệu - Chương 4: danh sách liên kết

Đại Học Sư Phạm Tp. Hồ Chí Minh Chương 4: DANH SÁCH LIÊN KẾT CẤU TRÚC DỮ LIỆU 1 2 Nội dung 1. Đặt vấn đề - ctdl động, tại sao? 2. Con trỏ và kiểu dữ liệu động 3. Cấu trúc và con trỏ 4. Định nghĩa danh sách liên kết 5. Các phép toán trên danh sách liên kết 6. Sắp thứ tự trên danh sách liên kết 7. Danh sách liên kết kiểu FIFO và LIFO 8. Một số ứng dụng của danh sách liên kết 3 1. Đặt vấn đề - ctdl động, tại sao? • Nhu cầu thực tế về kiểu dữ liệu: struct NGUOI { char hoten[30]; int soCMND; NGUOI cha,me; }; Khi khai báo một kiểu dữ liệu thì NNLT thường yêu cầu kiểu dữ liệu phải được xác định kích thước rõ ràng. Với nhu cầu trên  không thể tính kích thước rõ ràng cho kiểu dữ liệu người. CTDL động giải quyết được vấn đề này. Nó giải quyết như thế nào? 4 1. Đặt vấn đề - ctdl động, tại sao? Biến tĩnh trong NNLT • Vùng nhớ của kiểu dữ liệu tĩnh sẽ được sinh ra khi ta khai báo biến và mất đi khi ra khỏi phạm vi khai báo hoặc khi chương trình kết thúc đối với các biến toàn cục. • Biến tĩnh trong chương trình không thay đổi được cấu trúc hay độ lớn trong khi thực thi. Nhu cầu thực tế • Có nhiều biến tĩnh không cần sử dụng nữa nhưng nó vẫn tồn tại và chiếm bộ nhớ cho đến khi chương trình hủy nó đi theo đúng cơ chế của biến tỉnh  gây lãng phí bộ nhớ. • Trong chu kỳ sống của một số đối tượng dữ liệu có thể thay đổi về cấu trúc, độ lớn như: danh sách học viên có thể tăng lên hoặc giảm xuống  bất hợp lý. Vấn đề về hiệu quả sử dụng bộ nhớ CTDL động giải quyết được vấn đề này. Nó giải quyết như thế nào? 51. Đặt vấn đề - ctdl động, tại sao? • Tổng kích thước vùng nhớ dành cho tất cả các biến tĩnh chỉ là 64kb (1 segment bộ nhớ) • Nhu cầu thực tế: cần nhiều bộ nhớ hơn CTDL động giải quyết được vấn đề này. Nó giải quyết như thế nào? Hạn chế về kích thước bộ nhớ cho các biến tĩnh 6 2. Con trỏ và kiểu dữ liệu động • Biến không động • Kiểu con trỏ • Biến động 7 2. Con trỏ và kiểu dữ liệu động 8 2. Con trỏ và kiểu dữ liệu động a. Biến không động  Được khai báo tường minh.Tồn tại trong phạm vi khai báo.  Được cấp phát bộ nhớ trong vùng dữ liệu hoặc trong ngăn xếp.  Kích thước không đổi trong suốt quá trình sống  Biến sẽ có một định danh gắn với vùng nhớ đã được cấp phát, và được truy xuất trực tiếp thông qua định danh đó. Ví dụ: int x; char a[100]; 9b. Kiểu con trỏ Biến con trỏ là biến dùng để lưu địa chỉ của một đối tượng dữ liệu khác. Cho trước kiểu T=. Kiểu con trỏ Tp chỉ đến các phần tử có kiểu T được định nghĩa: Tp= Vp = {{Các địa chỉ có thể lưu trữ đối tượng kiểu T}, NULL} Op= {Các thao tác tác động lên biến con trỏ kiểu T} 10 Ví dụ: int *n; int *a = new int[4]; int data[4]; char *b; char c[10]; student *st; hay typedef student *pStudent; pStudent st; 11 Các thao tác cơ bản trên kiểu con trỏ Khi biến con trỏ p lưu địa chỉ của biến x, ta nói “p trỏ đến x” int *p; int x=5; p=&x; cout<<*p; //cout<<x; Truy xuất nội dung của một đối tượng do p trỏ đến. int *a = new int; *a = 5; cout<<*a; 12 Gán địa chỉ của một vùng nhớ vào con trỏ p. p = ; p = + ví dụ: int a[3] = {1,2,3} int *p,*q; p = &a[0]; //int *p = a; q = a + 1; *q = 5; cout<<*q; 13 c. Biến động  Biến không được khai báo tường minh  Có thể được cấp phát và giải phóng do người dùng yêu cầu.  Biến động không hoạt động theo nguyên tắc phạm vi  Vùng nhớ của biến được cấp phát trong Heap  Kích thước của vùng nhớ có thể thay đổi trong quá trình sống.  Do không có định danh khi khai báo nên ta sẽ dùng con trỏ để trỏ đến vùng nhớ được cấp phát.  Hai thao tác cơ bản của biến động là tạo và hủy một biến động do con trỏ p trỏ đến. 14 Thao tác tạo và hủy biến động Cấp phát bộ nhớ:  void* malloc(size) trả về con trỏ chỉ đến vùng nhớ với kích thước được cấp phát là size  void* calloc(n,size) trả về con trỏ chỉ đến vùng nhớ được cấp phát gồm n phần tử, mỗi phần tử kích thước là size  Dùng toán tử new Hủy biến động:  free(p); dùng để hủy vùng nhớ được cấp phát bởi malloc hoặc calloc do p trỏ tới.  delete p; dùng để hủy vùng nhớ được cấp phát bởi hàm new mà con trỏ p trỏ tới. 15 Ví dụ int* p1, p2; p1 = (int*)malloc(sizeof(int)); *p1 = 5; p2 = (int*)calloc(10,sizeof(int)); *(p2+3)=5; free(p1); free(p2); int *p3 = new int[4]; *p3 = 1; //p3[0]=1; p3[2]=5; delete p3; 16 2. Con trỏ và kiểu dữ liệu động 17 2. Con trỏ và kiểu dữ liệu động 18 2. Con trỏ và kiểu dữ liệu động 19 2. Con trỏ và kiểu dữ liệu động int x; int *p, *q; p=&x; q=&x; 20 2. Con trỏ và kiểu dữ liệu động 21 2. Con trỏ và kiểu dữ liệu động 22 2. Con trỏ và kiểu dữ liệu động 23 3. Cấu trúc và con trỏ #include struct PHANSO { int tu, mau; }; void main() { PHANSO *a; a = new PHANSO; a->tu = 5; // (*a).tu=5; a->mau = 7; // (*a).mau=7; couttu,”/”,a->mau); delete a; } 24 3. Cấu trúc và con trỏ #include struct PS { int tu,mau; PS *next; }; void main() { PS x,y,z; x.tu=7;x.mau=5; x.next=NULL; y.tu=4;y.mau=9; y.next=NULL; z.tu=2;z.mau=6; z.next=NULL; x.next=&y; y.next=&z; (x.next)->tu=12; (x.next)->mau=23; PS *p; p=&x; while(p!=NULL) { couttu<<",“ mau<<endl; p=p->next; } } 25 4. Danh sách liên kết • Mảng là một hình thức liên kết ngầm – Các phần tử trong mảng được cấp phát vùng nhớ một cách liên tiếp nhau – Với T là kiểu dữ liệu cho trước, xét mảng các phần tử kiểu T. Ta có: Address(i)=Address(0)+(i-1)*sizeof(T). 20459 43210 26 4. Danh sách liên kết • Có nhiều loại danh sách liên kiết như: – Danh sách liên kết đơn – Danh sách liên kết kép – Danh sách liên kết vòng – . • Trong môn này ta tìm hiểu kỹ về danh sách liên kết đơn 27 4. Danh sách liên kết 28 4. Danh sách liên kết 29 4. Danh sách liên kết 30 4. Danh sách liên kết 31 4. Danh sách liên kết 32 5. Danh sách liên kết đơn Mô tả:  Danh sách liên kết đơn là danh sách gồm nhiều nút mỗi nút có thông tin cần thiết và một liên kết đến nút khác.  Danh sách liên kết đơn cần có 1 head trỏ vào nút đầu tiên và con trỏ tail trỏ vào nút cuối cùng. A B C D head tail 33 5. Danh sách liên kết đơn • Tạo danh sách – Khai báo danh sách liên kết – Khởi tạo danh sách liên kết – Tạo mới một phần tử để thêm vào danh sách liên kết – Thêm vào đầu danh sách – Thêm vào cuối danh sách – Xuất dữ liệu của toàn bộ danh sách liên kết – Thêm vào sau một phần tử cho trước • Tìm kiếm – Tìm một phần tử có khóa cho trước – Tìm một phần tử đứng trước một phần tử cho trước • Hủy danh sách – Hủy một phần tử đầu danh sách – Hủy một phần tử cuối danh sách – Hủy một phần tử sau một phần tử cho trước – Hủy một phần tử có khóa cho trước – Hủy toàn bộ danh sách 34 5. Danh sách liên kết đơn struct NODE { int data; // 2 byte (dos) NODE* next; // 2 byte (dos) }; struct LIST { NODE* pHead; NODE* pTail; }; 35 5. Danh sách liên kết đơn void KhoiTao(LIST &l) { l.pHead =NULL; l.pTail =NULL; } Việc khởi tạo danh sách liên kết nhằm xác định danh sách ban đầu mới tạo ra là rỗng 36 5. Danh sách liên kết đơn NODE* GetNode(int x) { NODE* p; p=new NODE; p->next=NULL; p->data=x; return p; } Tạo mới một phần tử để thêm vào danh sách 37 5. Danh sách liên kết đơn Thêm một phần tử vào đầu danh sách liên kết 1. Danh sách rỗng 2. Danh sách đã có phần tử 38 5. Danh sách liên kết đơn void AddHead(LIST &l, NODE* add) { if(l.pHead==NULL) { l.pHead=l.pTail=add; } else { add->next=l.pHead; l.pHead=add; } } Thêm một phần tử vào đầu danh sách liên kết 39 5. Danh sách liên kết đơn Thêm một phần tử vào cuối danh sách liên kết 1. Danh sách rỗng 2. Danh sách đã có phần tử 40 5. Danh sách liên kết đơn void AddTail(LIST &l, NODE* add) { if(l.pHead==NULL) { l.pHead=l.pTail=add; } else { l.pTail->next=add; l.pTail=add; } } Thêm một phần tử vào cuối danh sách liên kết 41 5. Danh sách liên kết đơn void PrintfList(LIST l) { NODE* p; p=l.pHead; while(p!=NULL) { cout”data; p = p->next; } } Xuất dữ liệu của danh sách liên kết 42 5. Danh sách liên kết đơn Tìm một phần tử trong danh sách liên kết khi biết khóa (data) Sử dụng 1 con trỏ phụ p để duyệt tất cả các phần tử trong danh sách liên kết 43 5. Danh sách liên kết đơn NODE* Search(LIST l, int data) { NODE* p=l.pHead; while((p!=NULL) && (p->data !=data)) p=p->next; return p; } Tìm một phần tử trong danh sách liên kết khi biết khóa (data) Kết quả trả về là NULL tức là không tìm thấy phần tử có khóa data Ngược lại nếu tìm thấy thì nó sẽ trả về địa chỉ của phần tử đầu tiên có khóa data trong danh sách liên kết. 44 5. Danh sách liên kết đơn Thêm một phần tử vào sau một phần tử cho trước 1. Danh sách rỗng 2. Danh sách đã có phần tử q 45 5. Danh sách liên kết đơn void AddAfter(LIST &l, NODE* q, NODE* add) { if(q!=NULL) { add->next=q->next; q->next=add; if(q==l.pTail) l.pTail=add; } else { AddHead(l,add); } } Thêm một phần tử vào sau một phần tử cho trước 46 5. Danh sách liên kết đơn NODE* SearchPre(LIST l, NODE* s) { NODE* p=l.pHead; if(p==s) return NULL; while((p!=NULL) && (p->next!=s)) p=p->next; return p; } Tìm một phần tử đứng trước một phần tử cho trước 47 5. Danh sách liên kết đơn Hủy phần tử đầu trong danh sách liên kết 1. Tách phần tử đầu ra khỏi danh sách 2. Xóa phần tử này 48 5. Danh sách liên kết đơn void RemoveHead(LIST &l) { if(l.pHead!=NULL) { p=l.pHead; l.pHead=l.pHead->next; delete p; if(l.pHead==NULL) l.pTail=NULL; } } Hủy phần tử đầu trong danh sách liên kết 49 5. Danh sách liên kết đơn Hủy phần tử cuối trong danh sách liên kết 1. Tách phần tử cuối ra khỏi danh sách 2. Gán pTail = địa chỉ của phần tử kế cuối 3. Xóa phần tử này 50 5. Danh sách liên kết đơn void RemoveTail(LIST &l) { if(l.pHead==NULL) return; NODE *p=l.pTail; l.pTail=SearchPre(l,l.pTail); delete p; if(l.pTail!=NULL) l.pTail->next=NULL; else l.pHead=NULL; } Hủy phần tử cuối trong danh sách liên kết 51 5. Danh sách liên kết đơn Hủy phần tử sau phần tử q trong danh sách liên kết 1. Tách phần tử p ra khỏi danh sách liên kết 2. Xóa phần tử này q 52 5. Danh sách liên kết đơn void RemoveAfter(LIST &l, NODE* q) { NODE* p; if(q!=NULL) { p=q->next; if(p!=NULL) { if(p==l.pTail) l.pTail=q; q->next=p->next; delete p; } } else RemoveHead(l); } Hủy phần tử sau phần tử q trong danh sách liên kết Lưu ý: q là phần tử trong danh sách liên kết 53 5. Danh sách liên kết đơn Hủy phần tử có khóa k cho trước 1. Tìm phần tử p có khóa k và phần tử q trước nó 2. Tách phần tử p ra khỏi danh sách liên kết 3. Xóa nó q K=39 54 5. Danh sách liên kết đơn void Remove (LIST &l, int k) { NODE* p=l.pHead,*q=NULL; while((p!=NULL)&&(p->data!=k)) { q=p; p=p->next; } if(p==NULL) return; if(q!=NULL) { if(p==l.pTail) { l.pTail=q; l.pTail->next=NULL; } q->next=p->next; delete p; } else // p là phần tử đầu tiên (pHead) RemoveHead(l); } Hủy phần tử có khóa k cho trước 55 5. Danh sách liên kết đơn Cách 1: void RemoveList (LIST &l, int k) { while(l.pHead!=NULL) RemoveHead(l); } Cách 2: void RemoveList (LIST &l) { while(l.pHead!=NULL) { p=l.pHead; l.pHead=l.pHead->next; delete p; } l.pTail=NULL; } Hủy toàn bộ danh sách liên kết 56 6. Sắp xếp trên danh sách liên kết void ListSelectionSort (LIST &l) { NODE* min; //trỏ đến pt có data min NODE* i,*j; for(i = l.pHead;i->next!=NULL;i=i->next) { min=i; for(j=i->next;j!=NULL;j=j->next) if(j->datadata) min=j; HoanVi(min->data,i->data); } } Selection Sort – Hoán vị nội dung phần dữ liệu (data) 57 6. Sắp xếp trên danh sách liên kết void ListSelectionSort (LIST &l) { NODE *i,*j,*min, *minpre=NULL; LIST lresult;KhoiTao(lresult); while(l.pHead!=NULL) //danh dách chưa hết { min=l.pHead;minpre=NULL; for(j=min,i=min->next;i!=NULL;j=i,i=i->next) if(i->datadata) { min=i; minpre=j; } if(minpre==NULL) { l.pHead=l.pHead->next;if(min==l.pTail) l.pTail=NULL; } else { if(min==l.pTail) l.pTail=minpre;minpre->next=min->next; } min->next=NULL; AddTail(lresult,min); } l=lresult; } Selection Sort – Thay đổi mối liên kết 1. Tìm pt min có data nhỏ nhất 2. Tách min ra khỏi danh sách 3. Thêm min vào đầu ds mới 58 7. Các cấu trúc đặc biệt của dslk đơn • Stack – Là vật chứa (container) các đối tượng làm việc theo cơ chế LIFO (last in first out) – Các thao tác trên stack: • Push(o): thêm đối tượng vào đâu stack • Pop(): lấy đối tượng ở đầu stack ra khỏi stack và trả về đối tượng đó, nếu stack rỗng thì trả về NULL • isEmpty(): Kiểm tra stack có rỗng hay không • Top(): trả về phần tử nằm ở đầu stack mà không lấy phần tử này ra khỏi stack – Stack được sử dụng để: khử đệ quy, tổ chức lưu vết của quá trình tìm kiếm theo chiều sâu và quay lui, vét cạn, định trị biểu thức, SV tự cài đặt stack. 59 7. Các cấu trúc đặc biệt của dslk đơn • Hàng đợi – Là một vật chứa (container) các đối tượng làm việc theo cơ chế FIFO (first in first out) – Các thao tác trên hàng đợi • EnQueue(o): thêm đối tượng vào hàng đợi • DeQueue(): Lấy đối tượng ra khỏi hàng đợi và trả về đối tượng đó. • IsEmpty(): Kiểm tra hàng đợi có rỗng không • Front(): Trả về đối tượng nằm ở đầu hàng đợi mà không hủy nó. SV tự cài đặt hàng đợi 60 7. Các cấu trúc đặc biệt của dslk đơn • Hàng đợi 61 8. Chuyển từ trung tố sang hậu tố • Biểu thức trung tố: – Có phép toán ở giữa – Ví dụ: a+b • Biểu thức hậu tố: – Có phép toán để ở đằng sau – Ví dụ: a b + • Biểu thức tiền tố: – Có phép toán ở đằng trước – Ví dụ: + a b 62 8. Chuyển từ trung tố sang hậu tố • Duyệt từ trái sang phải – Gặp (: đưa vào stack – Gặp số: ghi ra – Gặp phép toán: • Lấy và ghi ra tất cả các phép toán tại đỉnh của stack mà có độ ưu tiên >= phép toán hiện tại. • Đưa phép toán hiện tại vào stack. – Gặp ): • Lấy và ghi ra tất cả các phép toán tại đỉnh cho đến khi gặp (. • Lấy ( ra khỏi stack – Sau khi duyệt hết dãy thì lấy và ghi ra những gì còn trong stack Độ ưu tiên Bậc 2: *,/ Bậc 1: +, - Bậc 0: (,) 63 8. Chuyển từ trung tố sang hậu tố A + B * C - D / E Infix Stack(bot->top)Postfix a) A + B * C - D / E b) + B * C - D / E A c) B * C - D / E + A d) * C - D / E + A B e) C - D / E + * A B f) - D / E + * A B C g) D / E - A B C *+ h) / E - A B C *+D i) E - / A B C *+D j) - / A B C *+D E k) A B C *+D E / - 64 8. Chuyển từ trung tố sang hậu tố A * B - ( C + D ) + E Infix Stack(bot->top) Postfix a) A * B - ( C - D ) + E empty empty b) * B - ( C + D ) + E empty A c) B - ( C + D ) + E * A d) - ( C + D ) + E * A B e) - ( C + D ) + E empty A B * f) ( C + D ) + E - A B * g) C + D ) + E - ( A B * h) + D ) + E - ( A B * C i) D ) + E - ( + A B * C j) ) + E - ( + A B * C D k) + E - A B * C D + l) + E empty A B * C D + - m) E + A B * C D + - n) + A B * C D + - E o) empty A B * C D + - E + 65 9. Định trị biểu thức hậu tố • Duyệt từ trái sang phải – Gặp số: đưa vào stack – Gặp phép toán: • Lấy ra 1 số và gán vào a • Lấy ra 1 số và gán vào b • Thực hiện c=b a; • Đưa c vào stack. – Sau khi duyệt hết thì lấy kết quả ra từ stack Lưu ý thứ tự của a, b, phép toán 66 9. Định trị biểu thức hậu tố 1*(2+3) 1 2 3 + * Postfix Stack( bot -> top ) a) 1 2 3 + * b) 2 3 + * 1 c) 3 + * 1 2 d) + * 1 2 3 e) * 1 5 // 5 from 2 + 3 f) 5 // 5 from 1 * 5 67 67 Câu hỏi và thảo luận