Bài giảng Cấu trúc dữ liệu 1: Chương 4 - Lương Trần Hy Hiến

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

95
lượt xem 5
download

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

Chương 4 trình bày về danh sách liên kết thông qua các nội dung cụ thể như sau: Đặt vấn đề - cấu trúc dữ liệu động, con trỏ và kiểu dữ liệu động, cấu trúc và con trỏ, định nghĩa danh sách liên kết, các phép toán trên danh sách liên kết, sắp thứ tự trên danh sách liên kết, danh sách liên kết kiểu FIFO và LIFO, một số ứng dụng của danh sách liên kết. Mời tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu 1: Chương 4 - Lương Trần Hy Hiến

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