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

Chương 3.1. Danh sách liên kết đơnTrần Minh TháiEmail: minhthai@itc.edu.vnWebsite: www.minhthai.edu.vn Cập nhật: ngày 20 tháng 10 năm 2012Mụ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ữ C/ C++2Vấ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/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/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 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ệuKích thước cố định11Biế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ìnhKích thước có thể thay đổi12Biến tĩnh và biến động trong C++Biến độngCấ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 adelete 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 tNODE{ Data; struct tNODE *pNext;};typedef struct tNODE NODE;DatapNextKhai báo cấu trúc node lưu số nguyên29struct tNODE{ int Data; struct tNODE *pNext;};typedef struct tNODE NODE;20pNextKhai báo cấu trúc node lưu thông tin SV30struct 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, dtbpNextKhai báo cấu trúc DSLK đơn31struct tList{ NODE *pHead, *pTail;};typedef struct tList LIST;pHeadpTailListKhai báo cấu trúc DSLK đơn32struct tList{ NODE *pHead, *pTail;};typedef struct tList LIST;struct tNODE{ Data; struct tNODE *pNext;};typedef struct tNODE NODE;pHeadpTaillistCá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ỗngbool IsEmptyList(LIST list){ return ((list.pHead==NULL) && (list.pTail==NULL));}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/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/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 = new NODE; if(p == NULL) { coutData = 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{ cout>x; if(x==0) break; pNew=CreateNode(x); AddHead(list, pNew); }while(true);}Xuất dslk51pHeadpTailListpBà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(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ộng các node lẻ float TBLe(LIST list);52Chèn node vào DSLK đơnChèn vào sau node pChèn vào trước node p53pHeadpTaillist25pNewpChèn node vào sau node p54pHeadpTaillistpNewpChèn node vào trước node p – Cách 155pHeadpTaillistpNewppPrevChèn node vào trước node p – Cách 156 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 257pHeadpTaillistpNewpBướ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ách58Xóa một nút trong danh sáchXóa nút đầu của danh sách59pHeadpTaillist30254178Cần xóapDelNODE *pDel = list.pHeadlist.pHead = list.pHead->pNextdelete pDelXóa một nút trong danh sách60 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áchXóa nút cuối của danh sách61pHeadpTaillist30254178Cần xóapDelNODE *pDel = list.pTailNODE *pPrev = “Tìm node trước pTail”delete pDelpPrevlist.pTail = pPrevpPrev->pNext = NULLXóa một nút trong danh sách62 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 xóa danh sách chỉ có 1 node)?Xóa một nút trong danh sáchXóa nút giữa của danh sách63pHeadpTaillist30254178Cần xóapDelNODE *pPrev = “Tìm node trước pDel”delete pDelpPrevpPrev->pNext = pDel->pNext96Xóa một nút trong danh sách64 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 &list, NODE *pDel)?Xóa một nút trong danh sách65 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)?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);66