Phân tích và thiết kế giải thuật - Chương 3: Cấu trúc dữ liệu động

13.1. Kiểu dữ liệu con trỏ 3.2. Danh sách liên kết (link list) 3.3. Danh sách liên kết ñơn 3.4. Sắp xếp danh sách 3.5. Các cấu trúc ñặc biệt của danh sách liên kết ñơn 3.5.1. Stack 3.5.2. Hàng ñợi (Queue) 3.6. Bài tập Chương 3: CẤU TRÚC DỮ LIỆU ðỘNG Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 23.1. Kiểu Dữ Liệu Con Trỏ © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.1.1. Biến không ñộng 3.1.2. Kiểu con trỏ 3.1.3. Biến ñộng 3 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Dùng ñề lưu trữ những ñối tượng dữ liệu ñược sử dụng không có nhu cầu thay ñổi và kích thước, số lượng . . . • ðược khai báo tường minh • Tồn tại trong phạm vi khái báo • Kích thước không thay ñổi trong suốt quá trình sống Ví dụ: int a; char b[10]; 3.1.1. Biến không ñộng 4 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Kiểu con trỏ là kiểu cơ sở dùng lưu ñịa chỉ của một ñối tượng dữ liệu khác.
Biến thuộc kiểu con trỏ là biến mà giá trị của nó là ñịa chỉ một vùng nhớ của một biến hoặc là giá trị Null. Tùy vào loại con trỏ gần (near pointer) hay con trỏ xa (far pointer) mà kiểu dữ liệu con trỏ có các kích thước khác nhau: + Con trỏ gần: 2 bytes + Con trỏ xa: 4 bytes 3.1.2. Kiểu con trỏ 5 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Cú pháp ñịnh nghĩa một kiểu con trỏ typedef *; Ví dụ: typedef int *intpointer; inpointer p; Hay int *p; Các thao tác: - Khi 1 biến con trỏ p lưu ñịa chỉ của ñối tượng x, ta nói “p trỏ x” - Gán ñịa chỉ của biến cho con trỏ p: p=& -Truy xuất nội dung của ñối tượng do p trỏ ñến *p 6 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM c. Ví dụ: void main() { int a,b,*pa,*pb; a=2; b=3; cout<<"\nGia tri cua bien a="<<a; cout<<"\nGia tri cua bien b="<<b; pa=&a; pb=&b; cout<<"\nDia chi cua o nho con tro pa tro toi="<<pa; cout<<"\nDia chi cua o nho con tro pb tro toi="<<pb; cout<<"\nNoi dung cua o nho con tro pa tro toi="<<*pa; cout<<"\nNoi dung cua o nho con tro pb tro toi="<<*pb; *pa=20; /* Thay doi giá tr cua *pa*/ *pb=20; /* Thay doi giá tri cua *pb*/ cout<<"\nGia tri moi cua bien a="<<a; cout<<"\nGia tri moi cua bien b="<<b; } 7 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Trong trường hợp, tại thời ñiểm biên dịch không thể xác ñịnh trước kích thước chính xác của ñối tượng dữ liệu (do chúng phụ thuộc vào ngữ cảnh). Các ñối tượng dữ liệu này ñược khai báo như biến ñộng. Biến ñộng là những biến thỏa: 3.1.3. Biến ñộng
Không ñược khai báo tường minh.
ðược cấp phát/giải phóng bộ nhớ khi yêu cầu.
Các biến này không theo qui tắc phạm vi.
Vùng nhớ của biến ñược cấp phát trong Heap.
Kích thước thay ñổi trong quá trình sống. 8 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Các thao tác trên biến ñộng: Tạo biến ñộng và cho con trỏ p trỏ ñến: Các hàm cấp phát bộ nhớ: void* malloc(size); // trả về con trỏ chỉ ñến một vùng // nhớ size byte vừa ñược cấp phát. void* calloc(n,size);// trả về con trỏ chỉ ñến một vùng // nhớ vừa ñược cấp phát gồm n //phần tử,mỗi phần tử có kích //thước size byte new // hàm cấp phát bộ nhớ trong C++ 9 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Hủy một biến ñộng do p chỉ ñến: Hàm free(p): Huỷ vùng nhớ cấp phát bởi hàm malloc do p trỏ tới Hàm delete p: huỷ vùng nhớ cấp phát bởi hàm new do p trỏ tới 10 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Ví dụ: int* p1, p2; //Cấp phát vùng nhớ cho 1 biến ñộng kiểu int p1 = (int*)malloc(sizeof(int)); //ðặt giá trị 5 cho biến ñộng p1 p1* = 5; //Cấp phát biến ñộng kiểu mảng 10 p.tử kiểu int p2 = (int*)calloc(10, sizeof(int)); //ðặt giá trị 0 cho phần tử thứ 4 của mảng p2 (p2+3)* = 0; free(p1); free(p2); 11 3.2. Danh Sách Liên Kết © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.2.1. Ðịnh nghĩa 3.2.2. Các hình thức tổ chức danh sách 12 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.2.1. Ðịnh nghĩa Kiểu danh sách Tx gồm các phần tử thuộc kiểu T ñược ñịnh nghĩa là: Tx = trong ñó:
Vx = {tập hợp có thứ tự các phần tử kiểu T ñược móc nối với nhau theo trình tự tuyến tính};
Ox = {Tạo danh sách; Tìm 1 phần tử trong danh sách; Chèn một phần tử vào danh sách; Huỷ một phần tử khỏi danh sách ; Liệt kê danh sách, Sắp xếp danh sách ...} 13 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Ví du: Hồ sơ các học sinh của một trường ñược tổ chức thành danh sách gồm nhiều hồ sơ của từng học sinh; số lượng học sinh trong trường có thể thay ñổi do vậy cần có các thao tác thêm, hủy một hồ sơ; ñể phục vụ công tác giáo vụ cần thực hiện các thao tác tìm hồ sơ của một học sinh, in danh sách hồ sơ ... 14 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.2.2. Các hình thức tổ chức danh sách  Mối liên hệ giữa các phần tử ñược thể hiện ngầm:
Mỗi phần tử trong danh sách ñược ñặc trưng bằng chỉ số.
Cặp phần tử xi, xi+1 ñược xác ñịnh là kế cận
Với hình thức tổ chức này, các phần tử của danh sách phải lưu trữ liên tiếp trong bộ nhớ, công thức xác ñịnh ñịa chỉ phần tử thứ I là. Cách biểu diễn này cho phép truy xuất ngẫu nhiên, ñơn giản và nhanh chóng ñến một phần tử bất kỳ trong danh sách, nhưng lại hạn chế về mặt sử dụng bộ nhớ bị lãng phí. 15 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Mối liên hệ giữa các phần tử thể hiện tường minh:
Mỗi phần tử ngoài các thông tin còn chứa một liên kết (ñịa chỉ) ñến phần tử kế trong danh sách nên còn ñược gọi là danh sách móc nối.
Với hình thức này các phần tử trong danh sách không cần phải lưu trữ kế cận trong bộ nhớ nên khắc phục ñược các khuyết ñiểm của hình thức tổ chức mảng, nhưng việc truy xuất ñến một phần tử ñòi hỏi phải thực hiện truy xuất qua một số phần tử khác. 16 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Có các kiểu tổ chức liên kết giữa các phần tử.
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 17 3.3. Danh Sách Liên Kết ðơn © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết 3.3.2. Các thao tác cơ bản trên danh sách ñơn 18 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.3.1. Tổ chức danh sách ñơn theo cách cấp phát liên kết Mỗi phần tử là một cấu trúc chứa 2 thông tin : - Thành phần dữ liệu: Lưu trữ các thông tin về bản thân phần tử . - Thành phần mối liên kết: lưu trữ ñịa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu là phần tử cuối danh s ách. Ta có ñịnh nghĩa tổng quát typedef struct tagNode { Data Info; // Data là kiểu ñã ñịnh nghĩa trước struct tagNode* pNext;//con trỏ trỏ ñến cấu trúc node }NODE; 19 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Ví dụ: Ðịnh nghĩa danh sách ñơn lưu trữ hồ sơ SV typedef struct SinhVien { char Ten[30]; int MaSV; }SV; typedef struct SinhvienNode { SV Info; struct SinhvienNode* pNext; }SVNode; 20 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Nếu biết ñược ñịa chỉ của phần tử ñầu tiên trong danh sách ñơn thì có thể dựa vào thông tin pNext của nó ñể truy xuất ñến phần tử thứ 2, thứ 3... ðể quản lý một xâu ñơn chỉ cần biết ñịa chỉ phần tử ñầu xâu. Con trỏ Head dùng ñể lưu trữ ñịa chỉ phần tử ñầu xâu Khai báo: NODE *pHead; Ðể tiện lợi, có thể sử dụng thêm một con trỏ pTail giữ ñịa chỉ phần tử cuối xâu. Khai báo: NODE *pTail; 21 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.3.2. Các thao tác cơ bản trên danh sách ñơn Giả sử có các ñịnh nghĩa: typedef struct tagNode { Data Info; struct tagNode* pNext; }NODE; typedef struct tagList { NODE* pHead; NODE* pTail; }LIST; NODE *new_ele; // giữ ñịa chỉ của một phần tử mới ñược tạo Data x; // lưu thông tin về một phần tử sẽ ñược tạo 22 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Chèn một phần tử vào ñầu danh sách Thu t toán : Bắt ñầu: Nếu Danh sách rỗng Thì B11 : Head = new_elelment; B12 : Tail = Head; Ngược lại B21 : new_ele ->pNext = Head; B22 : Head = new_ele ; 23 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM void AddFirst(LIST &l, NODE* new_ele) { if (l.pHead==NULL) //Xâu rỗng { l.pHead = new_ele; l.pTail = l.pHead; } else { new_ele->pNext = l.pHead; l.pHead = new_ele; } } NODE* InsertHead(LIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { new_ele->pNext = l.pHead; .pHead = new_ele; } return new_ele; } 24 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Chèn một phần tử vào cuối danh sách Thu t toán : Bắt ñầu : Nếu Danh sách rỗng Thì B11 : Head = new_elelment; B12 : Tail = Head; Ngược lại B21 : Tail ->pNext = new_ele; B22 : Tail = new_ele ; 25 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM void AddTail(LIST &l, NODE *new_ele) { if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->Next = new_ele; l.pTail = new_ele; } } NODE* InsertTail(LIST &l, Data x) { NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if (l.pHead==NULL) { l.pHead = new_ele; l.pTail = l.pHead; } else { l.pTail->Next = new_ele; l.pTail = new_ele; } return new_ele; } 26 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Chèn một phần tử vào sau phần tử q Thu t toán : Bắt ñầu : Nếu ( q != NULL) thì B1: new_ele -> pNext = q->pNext; B2: q->pNext = new_ele 27 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM void AddAfter(LIST &l,NODE *q, NODE* new_ele) { if ( q!=NULL) { new_ele->pNext = q->pNext; q->pNext = new_ele; if(q == l.pTail) l.pTail = new_ele; }else //chèn vào ñầu danh sách AddFirst(l, new_ele); } void InsertAfter(LIST &l,NODE *q, Data x){ NODE* new_ele = GetNode(x); if (new_ele ==NULL) return NULL; if ( q!=NULL) { new_ele->pNext = q->pNext; q->pNext = new_ele; if(q == l.pTail) l.pTail = new_ele; }else //chèn vào ñầu danh sách AddFirst(l, new_ele); } 28 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Tìm một phần tử trong danh sách ñơn Thu t toán : Xâu ñơn ñòi hỏi truy xuất tuần tự, áp dụng thuật toán tìm tuyến tính ñể xác ñịnh phần tử trong xâu có khoá k. Thuật toán ñược thể hiện như sau : Bước 1: p = Head; //Cho p trỏ ñến phần tử ñầu danh sách Bước 2: Trong khi (p != NULL) và (p->pNext != k ) thực hiện: B21 : p:=p->Next;// Cho p trỏ tới phần tử kế Bước 3: Nếu p != NULL thì p trỏ tới phần tử cần tìm Ngược lại: không có phần tử cần tìm. 29 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM NODE *Search(LIST l, Data k) { NODE *p; p = l.pHead; while((p!= NULL)&&(p->Info != x)) p = p->pNext; return p; } 30 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Hủy một phần tử ñầu danh sách ñơn Thu t toán : Bắt ñầu: Nếu (Head != NULL) thì B1: p = Head; B2: B21 : Head = Head->pNext; // tách p ra khỏi xâu B22 : free(p); // Hủy biến ñộng do p trỏ ñến B3: Nếu Head=NULL thì Tail = NULL; //Xâu rỗng. 31 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Data RemoveHead(LIST &l) { NODE *p; Data x = NULLDATA; if ( l.pHead != NULL) { p = l.pHead; x = p->Info; l.pHead = l.pHead->pNext; delete p; if(l.pHead == NULL) l.pTail = NULL; } return x; } 32 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Hủy một phần tử ñứng sau phần tử q Thu t toán : Bắt ñầu: Nếu (q!= NULL) thì B1: p = q->Next; // p là phần tử cần hủy B2: Nếu (p != NULL) thì // q không phải là cuối xâu B21 : q->Next = p->Next; // tách p ra khỏi xâu B22 : free(p); // Hủy biến ñộng do p trỏ ñến 33 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM void RemoveAfter (LIST &l, NODE *q) { NODE *p; if ( q != NULL) { p = q ->pNext ; if ( p != NULL) { if(p == l.pTail) l.pTail = q; q->pNext = p->pNext; delete p; } } else RemoveHead(l); } 34 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Hủy một phần tử có khóa k Thu t toán : Bước 1: Tìm phần tử p có khóa k và phần tử q ñứng trước nó Bước 2: Nếu (p!= NULL) thì // tìm thấy k Hủy p ra khỏi xâu tương tự hủy phần tử sau q; Ngược lại Báo không có k; 35 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM int RemoveNode(LIST &l, Data k) { NODE *p = l.pHead; NODE *q = NULL; while( p != NULL) { if(p->Info == k) break; q = p; p = p->pNext; } if(p == NULL) return 0; //Không tìm thấy k if(q != NULL) { if(p == l.pTail) l.pTail = q; q->pNext = p->pNext; delete p; }else{ l.pHead = p->pNext; if(l.pHead == NULL) l.pTail = NULL; } return 1; } 36 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  Duyệt danh sách Duyệt danh sách là thao tác thường ñược thực hiện khi có nhu cầu xử lý các phần tử của danh sách như: - Ðếm các phần tử của danh sách, - Tìm tất cả các phần tử thoả ñiều kiện, - Huỷ toàn bộ danh sách (và giải phóng bộ nhớ) Thu t toán : Bước 1: p = Head; //Cho p trỏ ñến phần tử ñầu DS Bước 2: Trong khi (Danh sách chưa hết) thực hiện B21 : Xử lý phần tử p; B22 : p:=p->pNext; // Cho p trỏ tới phần tử kế 37 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM void ProcessList (LIST &l) { NODE *p; p = l.pHead; while (p!= NULL) { ProcessNode(p); // xử lý cụ thể tùy ứng dụng p = p->pNext; } } 38 3.4. Sắp Xếp Danh Sách © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.4.1. Các cách tiếp cận 3.4.2. Một số phương pháp sắp xếp trên danh sách 39 3.5. Các Cấu Trúc ðặc Biệt Của Danh Sách Liên Kết ðơn © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 3.5.1. Stack 3.5.2. Hàng ñợi (Queue) 40 3.6. Bài Tập © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM