Cơ sở dữ liệu - Chương 3: Danh sách liên kết

CHƯƠNG 3. DANH SÁCH LIÊN KẾT Võ Quang Hoàng Khang Email: vqhkhang@gmail.com Mục tiêu  Nắm vững khái niệm về kiểu dữ liệu tĩnh và động  Nắm vững cách tổ chức dữ liệu động bằng danh sách liên kết và minh họa được các thao tác xử lý trên danh sách liên kết đơn  Cài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C/ C++ 2 Vấn đề kiểu dữ liệu tĩnh 3 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 ? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng 6 Vấn đề kiểu dữ liệu tĩnh 4 1 2 3 4 5 6 7 8 9 10 5 7 3 9 2 15 1 6 Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử? Bài tập Hãy cài đặt hàm (bằng ngôn ngữ C/C++) chèn một phần tử có giá trị x vào vị trí vt trong mảng số nguyên a, kích thước n, theo mẫu hàm như sau: void ChenX(int a[], int &n, int x, int vt); 5 Vấn đề kiểu dữ liệu tĩnh ? Làm sao để xóa phần tử 9 6 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 Vấn đề kiểu dữ liệu tĩnh 7 1 2 3 4 5 6 7 8 10 5 7 3 9 2 15 1 Bài tập Hãy cài đặt hàm (bằng ngôn ngữ C/C++) xóa phần tử có giá trị x (nếu có) trong mảng số nguyên a, kích thước n (giả sử giá trị các phần tử trong mảng không trùng nhau), theo mẫu hàm như sau: void XoaX (int a[], int &n, int x); 8 Vấn đề kiểu dữ liệu tĩnh 9 Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n)i Vấn đề kiểu dữ liệu tĩnh  Giải quyết vấn đề phức tạp khi chèn/ xóa?  Giải quyết vấn đề giới hạn kích thước vùng nhớ tối đa?  Giải quyết vấn đề vùng nhớ không liên tục?  Giải quyết vấn đề giải phóng vùng nhớ khi không cần dùng đến? 10 DÙNG CẤU TRÚC DỮ LIỆU ĐỘNG Biến tĩnh và biến động trong C++  Biến tĩnh tên biến;  Vd: int a; float y; char s[20];  Tồn tại trong phạm vi khai báo  Được cấp phát vùng nhớ trong vùng dữ liệu  Kích thước cố định 11 Biến tĩnh và biến động trong C++  Biến động *tên biến;  Vd: int *a; float *y;  Chứa địa chỉ của một đối tượng dữ liệu  Được cấp phát hoặc giải phóng bộ nhớ tùy thuộc vào người lập trình  Kích thước có thể thay đổi 12 Biến tĩnh và biến động trong C++  Biến động  Cấp phát bộ nhớ: new int [kích thước]  Giải phóng bộ nhớ: delete vùng nhớ  Ví dụ: int *a; a=new int [10]; // Cấp phát //Các thao tác trên a delete a; // Giải phóng 13 Danh sách liên kết (DSLK) 14 1 7 2 6 3 10 8 5 9 4 Các phần tử kết dính với nhau bằng “sợi dây liên kết” 15 1 7 2 6 3 10 8 5 9 4 Để đơn giản hơn trong việc minh họa Đặc điểm DSLK Một dãy tuần tự các nút (Node) Giữa hai nút có con trỏ liên kết Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ) 16 Đặc điểm DSLK Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử mà chỉ cần thay đổi mối liên kết Quản lý phần tử đầu tiên bằng con trỏ pHead Có thể truy xuất đến các phần tử khác thông qua con trỏ liên kết 17 Node Cấu tạo của DSLK 18 pHead pTail List Cấu tạo của DSLK Quản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHead pHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi Ta cũng có thể quản lý danh sách bằng cách sử dụng thêm con trỏ cuối (pTail) pTail không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôi 19 Cấu tạo của nút Tạo lập bằng cách cấp phát bộ nhớ động Mỗi nút có 2 thông tin: Dữ liệu (data) Con trỏ liên kết đến phần tử kế tiếp trong danh sách (Next pointer link) Nếu không trỏ đến phần tử nào thì con trỏ Next = NULL 20 Thao tác chèn thêm node vào DSLK “Kết nối” lại sợi dây liên kết theo trình tự 21 pHead pTail List Thao tác xóa node khỏi DSLK 22 Cần xóa pHead pTail List Các loại DSLK DSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới” 23 A B X Z Y Các loại hình DSLK DSLK đôi: Các phần tử kết nối với nhau theo hướng “chiều đi tới và và đi lui” 24 A B C D Các loại hình DSLK Danh sách liên kết vòng: Các phần tử kết nối với nhau theo hướng “chiều đi tới” và phần tử cuối cùng có “đường đi vòng trở lại tới” phần tử đầu danh sách 25 A B X Z Y A B C D So sánh Mảng và DSLK Mảng Danh sách liên kết Kích thước cố định Số phần tử thay đổi tùy ý Các phần tử lưu trữ tuần tự (địa chỉ tăng dần) trong bộ nhớ Các phần tử liên kết với nhau bằng con trỏ Phải dịch chuyển các phần tử khi Thêm/Xóa Chỉ cần thay đổi con trỏ liên kết khi Thêm/Xóa Truy xuất ngẫu nhiên Truy xuất tuần tự 26 DSLK đơn 27 Cấu trúc 1 node Data pNext Data : Dữ liệu của node pNext : Con trỏ đến node kế tiếp pHead: Con trỏ đến node đầu pTail: Con trỏ đến node cuối pHead pTail List Khai báo cấu trúc node 28 struct tNODE { Data; struct tNODE *pNext; }; typedef struct tNODE NODE; Data pNext Khai báo cấu trúc node lưu số nguyên 29 struct tNODE { int Data; struct tNODE *pNext; }; typedef struct tNODE NODE; 20 pNext Khai báo cấu trúc node lưu thông tin SV 30 struct tNODE { SINHVIEN Data; struct tNODE *pNext; }; typedef struct tNODE NODE; struct tSinhVien { char ID[10], hoten[30]; float dtb; }; typedef struct tSinhVien SINHVIEN; ID, hoten, dtb pNext Khai báo cấu trúc DSLK đơn 31 struct tList { NODE *pHead, *pTail; }; typedef struct tList LIST; pHead pTail List Khai báo cấu trúc DSLK đơn 32 struct tList { NODE *pHead, *pTail; }; typedef struct tList LIST; struct tNODE { int Data; struct tNODE *pNext; }; typedef struct tNODE NODE; pHead pTail list Các thao tác trên DSLK đơn  Thêm 1 nút vào danh sách: đầu, cuối, sau ptử q  Duyệt danh sách  Xóa 1 nút: đầu, cuối, nút có giá trị x  Tìm 1 phần tử  Sắp xếp danh sách 33 C ấ u t rú c t ổ n g q u á t c h ư ơ n g t rì n h 34 Khai báo thư viện hàm1 Khai báo cấu trúc danh sách liên kết2 Khai báo các nguyên mẫu hàm3 void main() { Tạo lập danh sách rỗng Nhập dữ liệu vào danh sách Các thao tác xử lý trên danh sách Hủy danh sách } 4 Cài đặt các hàm con5 Tạo lập danh sách rỗng void CreateEmptyList(LIST &L) { L.pHead = L.pTail = NULL; } 35 Sau khi tạo lập ? pHead ? pTail List Trước khi tạo lập pHead pTail List pHead và pTail chưa xác định pHead và pTail trỏ vào NULL (rỗng) Kiểm tra danh sách rỗng bool IsEmptyList(LIST L) { return ((L.pHead==NULL) && (L.pTail==NULL)); } 36 Danh sách rỗng pHead pTail List Thêm một nút vào danh sách TH danh sách rỗng 37 pHead pTail list 30 pNew list.pHead = pNew list.pTail = pNew if(IsEmptyList(list)) { list.pHead = list.pTail = pNew; } Thêm một nút vào danh sách TH danh sách đã có phần tử 38 pHead pTail list 30 25 pNew Có 2 trường hợp để thêm pNew 1.Thêm pNew vào đầu (AddHead) 2.Thêm pNew vào cuối (AddTail) TH Thêm một nút vào đầu danh sách 39 pHead pTail list 30 25 pNew 1 2 TH Thêm một nút vào đầu danh sách 40 pHead pTail list 30 25 pHead pTail list 25 30 Vẽ lại TH Thêm một nút vào đầu danh sách 41 pHead pTail list 25 30 42 pNew Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào đầu danh sách ? TH Thêm một nút vào đầu danh sách 42 pNew->pNext = list.pHead list.pHead = pNew 1 2 TH Thêm một nút vào đầu danh sách 43 Hãy viết hàm thêm phần tử pNew vào đầu danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void AddHead(LIST &L, NODE *pNew) ? TH Thêm một nút vào cuối danh sách 44 pHead pTail list 30 25 pNew list.pTail->pNext = pNew list.pTail = pNew 1 1 2 2 TH Thêm một nút vào cuối danh sách 45 pHead pTail list 30 25 Hãy vẽ lại “đường kết nối” theo thứ tự thích hợp khi thêm pNew vào cuối danh sách ? 42 pNew TH Thêm một nút vào cuối danh sách 46 Hãy viết hàm thêm phần tử pNew vào cuối danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void AddTail (LIST &list, NODE *pNew) ? Nhập dữ liệu vào danh sách 47 Nhập dữ liệu cho node Tạo con trỏ node Thêm node vào danh sách Nhập dữ liệu vào danh sách Để tạo node mới từ dữ liệu x có sẵn Đưa dữ liệu có giá trị x vào phần Data Con trỏ pNext trỏ đến NULL 48 Data pNew x pNew->Data = x pNew->pNext = NULL Nhập dữ liệu vào danh sách VD hàm tạo và trả về con trỏ node có chứa giá trị nguyên x bằng ngôn ngữ C++ 49 NODE *CreateNode (int x) { NODE *p; p = new NODE; if(p == NULL) { cout<<“Loi cap phat duoc vung nho!"; exit(0); } p->Data = x; p->pNext=NULL; return p; } Nhập dữ liệu vào danh sách VD hàm nhập dữ liệu cho danh sách số nguyên và đưa vào đầu danh sách 50 void Input(LIST &list) { int x; NODE *pNew; CreateEmptyList(list); do{ cout<<"Nhap gia tri (Nhap 0 ket thuc): "; cin>>x; if(x==0) break; pNew=CreateNode(x); AddHead(list, pNew); }while(true); } Xuất dslk 51 pHead pTail List p Chèn node vào DSLK đơn Chèn vào sau node p Chèn vào trước node p 52pHead pTail list 25 pNewp Chèn node vào sau node p 53pHead pTail list pNewp Các thao tác trên DSLK (tt)   Xóa phần tử trong danh sách (đầu, cuối, giữa)  Sắp xếp danh sách Chèn node vào trước node p – Cách 1 55pHead pTail list pNewppPrev Chèn node vào trước node p – Cách 1 56 Hãy viết hàm tìm và trả về con trỏ node đứng trước con trỏ node p (bằng ngôn ngữ C/C++), theo mẫu sau: NODE *PrevNode (LIST list, NODE *p) ? Chèn node vào trước node p – Cách 2 57pHead pTail list pNewq Bước 1. Chèn pNew vào sau q Bước 2. Hoán vị giá trị pNew và q Xóa một nút trong danh sách Xóa nút đầu của danh sách  Ảnh hưởng pHead Xóa nút cuối của danh sách  Ảnh hưởng pTail Xóa nút giữa danh sách 58 Xóa một nút trong danh sách Xóa nút đầu của danh sách 59 pHead pTail list 30 25 41 78 Cần xóa pDel NODE *pDel = list.pHead list.pHead = list.pHead->pNext delete pDel Xóa một nút trong danh sách 60 Hãy viết hàm xóa nút đầu của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void DeleteHead (LIST &list) (lưu ý trường hợp danh sách chỉ còn 1 node trước khi xóa) ? Xóa một nút trong danh sách Xóa nút cuối của danh sách 61 pHead pTail list 30 25 41 78 Cần xóa pDel NODE *pDel = list.pTail NODE *pPrev = “Tìm node trước pTail” delete pDel pPrev list.pTail = pPrev pPrev->pNext = NULL Xóa một nút trong danh sách 62 Hãy viết hàm xóa nút cuối của danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void DeleteTail (LIST &list) (lưu ý trường hợp danh sách chỉ còn 1 node trước khi xóa) ? Xóa một nút trong danh sách Xóa nút giữa của danh sách 63 pHead pTail list 30 25 41 78 Cần xóa pDel NODE *pPrev = “Tìm node trước pDel” delete pDel pPrev pPrev->pNext = pDel->pNext 96 Xóa một nút trong danh sách 64 Hãy viết hàm xóa một node bất kỳ trong danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void DeleteNode (LIST &L, NODE *pDel) ? Xóa một nút trong danh sách 65 Hãy viết hàm hủy toàn bộ danh sách (bằng ngôn ngữ C/C++), theo mẫu sau: void DestroyList (LIST &list) ? Bài tập Cài đặt các hàm sau trên dslk đơn số nguyên: 1. Đếm số lượng node trong dslk int DemSL(LIST list); 2. Tìm node có giá trị lớn nhất NODE* TimMax(LIST list); 3. Tìm node có giá trị x NODE* TimX(LIST list, int x); 4. In những node có giá trị chẵn void InChan(LIST list); 5. Tính giá trị trung bình các node lẻ float TBLe(LIST list); 66 6. Chèn node có giá trị x vào phía sau node có giá trị lớn nhất void ChenXSauMax(LIST &list, int x); 7. Xóa node có giá trị x bool XoaX(LIST &list, int x); 8. Sắp tăng dslk void SapTang(LIST &list); 67 Sắp xếp void Doichotructiep ( LIST &L ) { Node *p,*q; for (p=L.DAU ; p!=L.CUOI ; p=p->tiep ) for (q=p->tiep; q!=NULL ; q=q->tiep) if ( p->dulieu > q->dulieu) Hoanvi( p->dulieu , q->dulieu ); } 68