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

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 02: Danh sách liên kết

1. DANH SÁCH LIÊN K ẾT MC TIÊU Hồn tất bài thực hành này, sinh viên cĩ th ể: Hiểu được các thành phần c ủa danh sách liên kết. Thành thạo các thao tác trên danh sách liên k ết: thêm phần tử, xĩa phần tử, duy ệt danh sách liên kết. Áp dụng cấu trúc dữ liệu danh sách liên k ết vào việc giải quyết một số bài tốn đơn giản. Thời gian thực hành: từ 120 phút đ ến 400 phút TĨM TT Danh sách liên kết là cấu trúc dữ li ệu dùng để lưu trữ một danh sách (tập hợp h ữu hạn) dữ liệu. Điểm đặc biệt của cấu trúc này là kh ả năng chứa của nĩ động (cĩ thể mở rộng và thu h ẹp dễ dàng). Cĩ các loại danh sách liên kế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 Mỗi danh sách liên kết là tập hợp các phần tử (node) chứa thơng tin lưu trữ của d ữ liệu. Giữa các phần tử cĩ một hoặc nhiều liên kết đ ể đảm bảo danh sách liên kết cĩ thể giữ các ph ần tử này một cách chặt chẽ. Ví dụ 1: Phần tử cĩ một liên kết Phần tử cĩ hai liên kết Phần t ử rỗng Ví dụ 2: 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 Trong mỗi phần tử của danh sách liên k ết, thơng tin liên kết là vơ cùng quan trọng. Ch ỉ cần một xử lý khơng cẩn thận cĩ thể làm mất ph ần liên kết này thì danh sách liên kết sẽ bị ‘gãy ’ từ phần tử đĩ (khơng thể truy xuất tiếp các phần t ử từ phần tử đĩ trở về trước hoặc trở về sau). Các thao tác cơ bản trên danh sách liên k ết: Thêm phần tử: vào đầu danh sách liên k ết, vào cuối danh sách liên kết, vào trư ớc/sau một phần tử trên danh sách liên k ết. Xĩa phần tử: ở đầu danh sách liên k ết, ở cuối danh sách liên kết, một phần t ử trên danh sách liên kết. 1 Duyệt danh sách liên kết: để cĩ thể đi được hết các phần tử trên danh sách liên k ết. Trang Tài li u hư ng d n th c hành mơn Cu trúc d li u và gi i thu t
2. NI DUNG THC HÀNH Cơ bản Sinh viên đọc kỹ phát biểu bài tập và thực hiện theo hướng dẫn: Tổ chức một danh sách liên kết đơn trong đĩ mỗi phần tử chứa thơng tin dữ liệu nguyên. Người dùng sẽ nhập các giá trị nguyên từ bàn phím. Với mỗi giá trị nguyên được nhập vào, giá trị đĩ được thêm vào phía đầu của danh sách liên kết. Nếu người dùng nhập vào giá trị 1, quá trình nhập dữ liệu sẽ kết thúc. Sau đĩ, in ra các phần tử đang cĩ trên danh sách liên kết. Khi chương trình kết thúc, tất cả các phần tử trên danh sách liên kết bị xĩa bỏ khỏi bộ nhớ. Phân tích Danh sách liên kết đơn gồm mỗi phần tử chứa dữ liệu nguyên. Thơng tin của mỗi phần tử được khai báo theo ngơn ngữ C/C++ như sau: struct NODE{ int Key; NODE *pNext; }; Danh sách liên kết được khai báo như sau: struct LIST{ NODE *pHead; NODE *pTail; }; Thao tác cần thực hiện: thêm phần tử nguyên vào đầu danh sách liên kết (AddHead ), in các phần tử của danh sách liên kết (PrintList ), loại bỏ tất cả các phần tử trên danh sách liên kết (RemoveAll ). Chương trình mẫu #include "stdafx.h" struct NODE{ int Key; NODE *pNext; }; struct LIST{ NODE *pHead; NODE *pTail; }; NODE* CreateNode( int Data) { NODE* pNode; pNode = new NODE; //Xin cp phát b nh đng đ to mt phn t (node) mi if (pNode == NULL) return NULL; pNode>Key = Data; pNode>pNext = NULL; return pNode; } 2 bool AddHead(LIST &L, int Data) { Trang Tài liu hưng dn thc hành mơn Cu trúc d liu và gii thut HCMUS 2010
3. NODE *pNode; pNode = CreateNode(Data); if (pNode == NULL) return false ; if (L.pHead == NULL) { L.pHead = pNode; L.pTail = pNode; } else { pNode>pNext = L.pHead; L.pHead = pNode; } return true ; } void PrintList(LIST L) { NODE *pNode; pNode = L.pHead; while (pNode != NULL) { printf( "%5d" , pNode>Key); pNode = pNode>pNext; //Ghi chu: thao tác này dùng đ làm gì? } } void RemoveAll(LIST &L) //Ghi chu: Ý nghĩa ca ký hiu & { NODE *pNode; while (L.pHead != NULL) { pNode = L.pHead; L.pHead = L.pHead>pNext; delete pNode; } L.pHead = NULL; //Ghi chu: Ti sao phi thc hin phép gán này? L.pTail = NULL; } int _tmain( int argc, _TCHAR* argv[]) { LIST L; //Ghi chu: Ti sao li phi thc hin phép gán phía dưi? L.pHead = NULL; L.pTail = NULL; int Data; do { printf( "Nhap vao du lieu, 1 de ket thuc: " ); scanf( "%d" , &Data); if (Data == 1) break ; AddHead(L, Data); }while (Data != 1); printf( "\nDu lieu da duoc nhap: \n" ); //Ghi chu: Chc năng ca dịng lnh phía dưi PrintList(L); 3 //Ghi chu : Chc năng ca dịng lnh phía dưi RemoveAll(L); Trang Tài liu hưng dn thc hành mơn Cu trúc d liu và gii thut HCMUS 2010
4. return 0; } Yêu cầu 1. Biên dịch đoạn chương trình nêu trên. 2. Cho biết kết quả in ra màn hình khi người dùng nhập vào các dữ liệu sau: 1 5 1 7 10 23 25 4 1 1 1 2 3 4 1 3. Nêu nhận xét ngắn gọn mối liên hệ giữa thứ tự nhập dữ liệu vào với thứ tự in dữ liệu ra màn hình. 4. Vẽ hình danh sách liên kết theo dữ liệu được nhập ở câu 2. 5. Nếu trong hàm main (_tmain ) thứ tự hai dịng lệnh sau đây bị hốn đổi cho nhau thì kết quả kết xuất ra màn hình sẽ như thế nào đối với dữ liệu câu 2? Giải thích lý do? PrintList(L); RemoveAll(L); 6. Nếu trong hàm main (_tmain ) vịng lặp do while được thay đổi như dưới đây thì kết quả kết xuất ra màn hình sẽ như thế nào đối với dữ liệu câu 2? Giải thích lý do? do { printf( "Nhap vao du lieu, 1 de ket thuc: " ); scanf( "%d" , &Data); AddHead(L, Data); if (Data == 1) break ; }while (Data != 1); 7. Với các hàm CreateNode , AddHead được cung cấp sẵn, hãy cho biết ý nghĩa của các giá trị trả về của hàm. 8. Hãy ghi chú các thơng tin bằng cách trả lời các câu hỏi ứng với các dịng lệnh cĩ yêu cầu ghi chú (//Ghi chú ) trong các hàm RemoveAll, PrintList, _tmain . 9. Kết quả sẽ như thế nào nếu hàm RemoveAll được thay đổi như dưới đây? Giải thích lý do void RemoveAll(LIST &L) { while (L.pHead != NULL) { L.pHead = L.pHead>pNext; delete L.pHead; } L.pHead = NULL; } 10. Giá trị cuối cùng của biến pRoot trong đoạn chương trình mẫu là gì? Giải thích lý do. Áp dụng – Nâng cao 1. Bổ sung chương trình mẫu cho phép tính tổng giá trị các phần tử trên danh sách liên kết đơn gồm các giá trị nguyên. 4 Gợi ý: tham khảo hàm PrintList để viết hàm SumList . Trang Tài liu hưng dn thc hành mơn Cu trúc d liu và gii thut HCMUS 2010
5. 2. Bổ sung chương trình mẫu cho phép tìm giá trị nguyên lớn nhất trong số các phần tử nguyên trên danh sách liên kết đơn gồm các giá trị nguyên. Gợi ý: tham khảo hàm PrintList để viết hàm MaxList . 3. Bổ sung chương trình mẫu cho phép tính số lượng các phần tử của danh sách liên kết đơn gồm các giá trị nguyên. Gợi ý: tham khảo hàm PrintList để viết hàm CountList . 4. Bổ sung chương trình mẫu cho phép thêm vào cuối danh sách liên kết đơn một giá trị nguyên. Gợi ý: tham khảo hàm AddHead để viết hàm AddTail . 5. Bổ sung chương trình mẫu cho phép xĩa phần tử đầu danh sách liên kết đơn. 6. Bổ sung chương trình mẫu cho phép xĩa phần tử cuối danh sách liên kết đơn. 7. Bổ sung chương trình mẫu cho biết số lượng các phần tử trên danh sách liên kết đơn cĩ giá trị trùng với giá trị x được cho trước. Gợi ý: tham khảo thao tác duyệt danh sách liên kết trong hàm PrintList . 8. Bổ sung chương trình mẫu cho phép tạo một danh sách liên kết đơn gồm các phần tử mang giá trị nguyên trong đĩ khơng cĩ cặp phần tử nào mang giá trị giống nhau. Gợi ý: sử dụng hàm AddHead hoặc AddTail cĩ bổ sung thao tác kiểm tra phần tử giống nhau. 9. Cho sẵn một danh sách liên kết đơn gồm các phần tử mang giá trị nguyên và một giá trị nguyên x. Hãy tách danh sách liên kết đã cho thành 2 danh sách liên kết: một danh sách gồm các phần tử cĩ giá trị nhỏ hơn giá trị x và một danh sách gồm các phần tử cĩ giá trị lớn hơn giá trị x. Giải quyết trong 2 trường hợp: a. Danh sách liên kết ban đầu khơng cần tồn tại. b. Danh sách liên kết ban đầu bắt buộc phải tồn tại. BÀI TP THÊM n n1 1. Đề xuất cấu trúc dữ liệu thích hợp để biểu diễn đa thức (a nx + a n1x + + a 1x + a 0) bằng danh sách liên kết (đơn hoặc kép). Cài đặt các thao tác trên danh sách liên kết đơn biểu diễn đa thức: a. In đa thức b. Rút gọn đa thức c. Cộng hai đa thức d. Nhân hai đa thức 2. Thơng tin của một quyển sách trong thư việc gồm các thơng tin: • Tên sách (chuỗi) • Tác giả (chuỗi, tối đa 5 tác giả) • Nhà xuất bản (chuỗi) • Năm xuất bản (số nguyên) a. Hãy tạo danh sách liên kết (đơn hoặc kép) chứa thơng tin các quyển sách cĩ trong thư viện (được nhập từ bàn phím). b. Cho biết số lượng các quyển sách của một tác giả bất kỳ (nhập từ bàn phím). c. Trong năm YYYY (nhập từ bàn phím), nhà xuất bản ABC (nhập từ bàn phím) đã phát hành 5 những quyển sách nào. Trang Tài liu hưng dn thc hành mơn Cu trúc d liu và gii thut HCMUS 2010