Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Danh sách liên kết

Chương 4. Danh sách liên kếtTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn Cập nhật: ngày 10 tháng 04 năm 2016Mục tiêuNắm vững khái niệm về kiểu dữ liệu tĩnh và độngNắ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 đơnCài đặt minh họa được các thao tác của danh sách đơn bằng ngôn ngữ C2Vấn đề kiểu dữ liệu tĩnh3123456781057392151? Làm sao để chèn thêm số 6 vào vị trí 5 của mảng6Vấn đề kiểu dữ liệu tĩnh412345678910573921516Bổ sung thêm Giả sử cần thêm tiếp 1 phần tử?Bài tậpHãy cài đặt hàm (bằng ngôn ngữ 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); 5Vấn đề kiểu dữ liệu tĩnh? Làm sao để xóa phần tử 96123456781057392151Vấn đề kiểu dữ liệu tĩnh7123456781057392151Bài tậpHãy cài đặt hàm (bằng ngôn ngữ 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); 8Vấn đề kiểu dữ liệu tĩnh9Độ phức tạp của chèn/ xóa trên mảng 1 chiều là O(n)iVấn đề kiểu dữ liệu tĩnhGiả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?10DÙNG CẤU TRÚC DỮ LIỆU ĐỘNGBiến tĩnh và biến động trong CBiế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ệuKích thước cố định11Biến tĩnh và biến động trong CBiế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ìnhKích thước có thể thay đổi12Biến tĩnh và biến động trong CBiến độngCấp phát bộ nhớ: (kdl*)malloc(kích thước)Giải phóng bộ nhớ: free vùng nhớVí dụ: int *a;a=(int *)malloc(10); // Cấp phát //Các thao tác trên afree a; // Giải phóng13Danh sách liên kết (DSLK)1417263108594Các phần tử kết dính với nhau bằng “sợi dây liên kết”1517263108594Để đơn giản hơn trong việc minh họaĐặc điểm DSLKMột dãy tuần tự các nút (Node)Giữa hai nút có con trỏ liên kếtCá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 DSLKThao 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ếtQuản lý phần tử đầu tiên bằng con trỏ pHeadCó thể truy xuất đến các phần tử khác thông qua con trỏ liên kết17NodeCấu tạo của DSLK18pHeadpTailListCấu tạo của DSLKQuản lý toàn bộ danh sách liên kết thông qua con trỏ đầu pHeadpHead không phải là 1 nút, nó chỉ là “con trỏ chỉ đến nút” mà thôiTa 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ôi19Cấu tạo của nútTạo lập bằng cách cấp phát bộ nhớ độngMỗ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 = NULL20Thao 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ự21pHeadpTailListThao tác xóa node khỏi DSLK22Cần xóapHeadpTailListCác loại hình DSLKDSLK đơn: Các phần tử kết nối với nhau theo hướng “chiều đi tới”23Các loại hình DSLKDSLK đô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”24Các loại hình DSLKDanh 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ách25So sánh Mảng và DSLKMảngDanh sách liên kếtKích thước cố địnhSố 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óaChỉ cần thay đổi con trỏ liên kết khi Thêm/XóaTruy xuất ngẫu nhiênTruy xuất tuần tự26DSLK đơn27Cấu trúc 1 nodeDatapNextData : Dữ liệu của nodepNext : Con trỏ đến node kế tiếppHead: Con trỏ đến node đầupTail: Con trỏ đến node cuốipHeadpTailListKhai báo cấu trúc node28struct ttNODE{ Data; struct ttNODE *pNext;};DatapNexttypedef struct ttNODE NODE;Khai báo cấu trúc node lưu số nguyên29struct ttNODE{ int Data; struct ttNODE *pNext;};20pNexttypedef struct ttNODE NODE;Khai báo cấu trúc node lưu thông tin SV30struct ttNODE{ struct SINHVIEN Data; struct ttNODE *pNext;};struct SINHVIEN{ char ID[10], hoten[30]; float dtb;};ID, hoten, dtbpNextKhai báo cấu trúc DSLK đơn31struct ttLIST{ NODE *pHead, *pTail;};pHeadpTailListtypedef struct ttList LIST;Khai báo cấu trúc DSLK đơn32struct ttLIST{ NODE *pHead, *pTail;};struct ttNODE{ Data; struct ttNODE *pNext;};pHeadpTaillisttypedef struct ttNODE NODE;typedef struct ttLIST LIST;Các thao tác trên DSLK đơnTạo lập danh sách rỗngKiểm tra danh sách rỗngThêm 1 nút vào danh sáchDuyệt danh sáchXóa 1 nútTìm 1 phần tửSắp xếp danh sách33Cấu trúc tổng quát chương trình34Khai báo thư viện hàm1Khai báo cấu trúc danh sách liên kết2Khai 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 }4Cài đặt các hàm con5Tạo lập danh sách rỗngvoid CreateEmptyList(LIST &list){ list.pHead = list.pTail = NULL;}35Sau khi tạo lập?pHead?pTailListTrước khi tạo lậppHeadpTailListpHead và pTail chưa xác địnhpHead và pTail trỏ vào NULL (rỗng)Kiểm tra danh sách rỗngint IsEmptyList(LIST list){ if ((list.pHead==NULL) && (list.pTail==NULL)) return 1; return 0;}36Danh sách rỗngpHeadpTailListThêm một nút vào danh sáchTH danh sách rỗng37pHeadpTaillist30pNewlist.pHead = pNewlist.pTail = pNewif(IsEmptyList(list)){ list.pHead = list.pTail = pNew;}Thêm một nút vào danh sáchTH danh sách đã có phần tử38pHeadpTaillist3025pNewCó 2 trường hợp để thêm pNewThêm pNew vào đầu (AddHead)Thêm pNew vào cuối (AddTail)TH Thêm một nút vào đầu danh sách39pHeadpTaillist3025pNew12TH Thêm một nút vào đầu danh sách40pHeadpTaillist3025pHeadpTaillist2530Vẽ lạiTH Thêm một nút vào đầu danh sách41pHeadpTaillist253042pNew 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ách42pNew->pNext = list.pHeadlist.pHead = pNew12TH Thêm một nút vào đầu danh sách43 Hãy viết hàm thêm phần tử pNew vào đầu danh sách (bằng ngôn ngữ C), theo mẫu sau: void AddHead(LIST &list, NODE *pNew)?TH Thêm một nút vào cuối danh sách44pHeadpTaillist3025pNewlist.pTail->pNext = pNewlist.pTail = pNew1122TH Thêm một nút vào cuối danh sách45pHeadpTaillist3025 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?42pNewTH Thêm một nút vào cuối danh sách46 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), theo mẫu sau: void AddTail (LIST &list, NODE *pNew)?Nhập dữ liệu vào danh sách47Nhập dữ liệu cho nodeTạo con trỏ nodeThêm node vào danh sáchNhậ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 DataCon trỏ pNext trỏ đến NULL48DatapNewxpNew->Data = xpNew->pNext = NULLNhập dữ liệu vào danh sáchVD hàm tạo và trả về con trỏ node có chứa giá trị nguyên x bằng ngôn ngữ C++49NODE *CreateNode (int x){ NODE *p; p = (NODE*) malloc(sizeof(NODE)); if(p == NULL) { printf(“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áchVD hàm nhập dữ liệu cho danh sách số nguyên và đưa vào đầu danh sách50void Input(LIST &list){ int x; NODE *pNew; CreateEmptyList(list); do{ printf("Nhap gia tri (Nhap 0 ket thuc): “); scanf(“%d”, &x); if(x==0) break; pNew=CreateNode(x); AddHead(list, pNew); }while(1);}Xuất dslk51pHeadpTailListpViết hàm xuất dslk số nguyên52void Output(const LIST &list){NODE *p = list.pHead;while (p){printf("%d ->", p->data);p = p->pNext;}printf("[null]\n");}Bài tậpCài đặt các hàm sau trên dslk đơn số nguyên:1. Đếm số lượng node trong dslk int DemSL(const LIST &list);2. Tìm node có giá trị lớn nhất NODE* TimMax(const LIST &list); 3. Tìm node có giá trị x NODE* TimX(const LIST &list, int x);4. In những node có giá trị chẵn void InChan(const LIST &list);5. Tính giá trị trung bình cộng các node lẻ float TBLe(const LIST &list);53Các thao tác trên DSLK đơnTạo lập danh sách rỗngKiểm tra danh sách rỗngThêm 1 nút vào danh sáchDuyệt danh sáchXóa 1 nútTìm 1 phần tửSắp xếp danh sách54Chèn node vào DSLK đơnChèn vào sau node pChèn vào trước node p55pHeadpTaillist25pNewpChèn node vào sau node p56pHeadpTaillistpNewpChèn node vào trước node p – Cách 157pHeadpTaillistpNewppPrevChèn node vào trước node p – Cách 158 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), theo mẫu sau: NODE *PrevNode (LIST list, NODE *p)?Chèn node vào trước node p – Cách 159NODE *PrevNode (LIST list, NODE *p){ if(p == list.pHead) return NULL; NODE *pTruoc = list.pHead; while(pTruoc->pNext != p) pTruoc = pTruoc -> pNext; return pTruoc;}Chèn node vào trước node p – Cách 160void ChenTruocP1 (LIST &list, NODE *p, NODE *pNew){ pNew -> pNext = p; NODE *pTruoc = PrevNode(list, p); if(pTruoc == NULL) list.pHead = pNew; else pTruoc -> pNext = pNew;}Chèn node vào trước node p – Cách 261pHeadpTaillistpNewpBước 1. Chèn pNew vào sau pBước 2. Hoán vị giá trị pNew và pXóa một nút trong danh sáchXóa nút đầu của danh sách  Ảnh hưởng pHeadXóa nút cuối của danh sách  Ảnh hưởng pTailXóa nút giữa danh sách62Xóa một nút trong danh sáchXóa nút đầu của danh sách63pHeadpTaillist30254178Cần xóapDelNODE *pDel = list.pHeadlist.pHead = list.pHead->pNextfree(pDel)Xóa một nút trong danh sách64 Hãy viết hàm xóa nút đầu của danh sách (bằng ngôn ngữ 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ách65void DeleteHead (LIST &list){ NODE *pDel = list.pHead; if(list.pHead != list.pTail) list.pHead = pDel -> pNext; else list.pHead = list.pTail = NULL; free(pDel);}Xóa một nút trong danh sáchXóa nút cuối của danh sách66pHeadpTaillist30254178Cần xóapDelNODE *pDel = list.pTailNODE *pPrev = “Tìm node trước pTail”free(pDel)pPrevlist.pTail = pPrevpPrev->pNext = NULLXóa một nút trong danh sách67 Hãy viết hàm xóa nút cuối của danh sách (bằng ngôn ngữ C), theo mẫu sau: void DeleteTail (LIST &list) (lưu ý trường hợp xóa danh sách chỉ có 1 node)?Xóa một nút trong danh sách68void DeleteTail (LIST &list){ NODE *pDel = list.pTail; NODE *pTruoc = PrevNode(list, list.pTail); if(pTruoc != NULL) { pTruoc -> pNext = NULL; list.pTail = pTruoc; } else list.pHead = list.pTail = NULL; free(pDel);}Xóa một nút trong danh sáchXóa nút giữa của danh sách69pHeadpTaillist30254178Cần xóapDelNODE *pPrev = “Tìm node trước pDel”free(pDel)pPrevpPrev->pNext = pDel->pNext96Xóa một nút trong danh sách70 Hãy viết hàm xóa một node bất kỳ trong danh sách (bằng ngôn ngữ C), theo mẫu: void DeleteNode (LIST &list, NODE *pDel)?Xóa một nút trong danh sách71 Hãy viết hàm hủy toàn bộ danh sách (bằng ngôn ngữ C), theo mẫu sau: void DestroyList (LIST &list)?Bài tập6. Chèn node có giá trị x vào phía sau node có giá trị lớn nhất (giả sử danh sách không có giá trị trùng nhau) void ChenXSauMax(LIST &list, int x);7. Xóa node có giá trị x xuất hiện đầu tiên trong danh sách (nếu có xóa: trả về 1, ngược lại trả về 0) int XoaX(LIST &list, int x);8. Sắp tăng dslk void SapTang(LIST &list);72