Bài giảng Danh sách liên kết

Bài 4: Danh sách liên kết 1. Khái nịêm Cách biểu diễn khác của danh sách. danh sách liên kết được tạo nên từ các tế bào (nút-node) mỗi tế bào là một bản ghi gồm hai trường, trường infor "chứa" phần tử của danh sách, trường next là con trỏ trỏ đến phần tử đi sau trong danh sách. sử dụng con trỏ head trỏ tới đầu danh sách. danh sách (a1, a2, ...an) có thể biểu diễn bởi cấu trúc dữ liệu danh sách liên kết: 1. Khái nịêm … a1 Chú ý : Không nên nhầm lẫn danh sách và danh sách liên kết. Danh sách và danh sách liên kết là hai khái niệm hoàn toàn khác nhau a2 an HEAD 2. Các phép toán trên danh sách liên kết Điều kiện để một danh sách liên kết rỗng là head = null Danh sách liên kết chỉ đầy khi không còn không gian nhớ để cấp phát cho các thành phần mới của danh sách. giả thiết điều này không xảy ra -> insert luôn luôn thực hiện được struct list { char ch; struct list *next; }; typedef struct list LIST; typedef LIST *LISTLINK; 2.1 Thêm mới một phần tử Void InsertAfter (Item x, LISTLINK Q, LISTLINK head) { LISTLINK P; P = (LISTLINK) malloc( sizeof(LIST) ); P->infor = x ; if head == null { P->next = null ; head = P ; } else { P -> next = Q -> next ; Q-> next = P ; } } 2.1 Thêm mới… 2.1 Thêm mới… void InsertBefore (Item x, LISTLINK Q, LISTLINK head) { LISTLINK P; P = (LISTLINK) malloc( sizeof(LIST) ); if Q == head { P->infor = x ; P-> next = Q ; head = P } else { P->next = Q ->next ; Q->next = P ; P->infor = Q->infor ; Q->infor = x ; } } 2.2 Phép toán loại bỏ Giả sử có 1 danh sách liên kết không rỗng (head  nil), Q là một con trỏ trỏ vào một thành phần trong danh sách -> cần loại bỏ thành phần Q khỏi danh sách. ~ muốn thêm một thành phần mới vào trước thành phần Q. ->đưa vào một con trỏ R trỏ tới trước Q một bước, tức là nếu Q không phải là thành phần đầu tiên, thì Q = R -> next. -> rất dễ dàng 2.2 Phép toán loại bỏ… void Delete (LISTLINK Q,R, LISTLINK head, Item *x) { x = Q->Infor ; if Q == head head = Q->next; else R->next = Q->next ; } 2.2 Phép toán loại bỏ… 2.3 Phép toán tìm kiếm với danh sách liên kết: áp dụng phương pháp tìm kiếm tuần tự kể cả danh sách đã được sắp xếp theo thứ tự ? cần tìm trong danh sách thành phần với infor là x cho trước. con trỏ P chạy từ đầu danh sách, lần lượt qua các thành phần của danh sách và dừng lại ở thành phần với infor = x. Biến found ghi lại sự tìm kiếm thành công hay không. 2.3 Phép toán tìm kiếm… void Search (Item x, LISTLINK *P, LISTLINK head, bool *found) ; { P = head ; found = false ; while ((P null ) && (not found)) if P->infor == x found = true; else P = P->next } 2.3 Phép toán tìm kiếm… void Search (Item x, LISTLINK *Q, *R, LIST head, bool *found) { R = null ; Q = head ; found : = false : while ((Q nil) && (not found)) do if Q->infor == x found = true else { R=Q ; Q = Q-> next ; } } 2.4 Phép toán đi qua danh sách void traverse (LIST head) { LISTLINK P ; { P = head ; while (P nil) { Visit (P->) ; P = P -> next; } } 3. So sánh hai phương pháp Khi biểu diễn danh sách bởi mảng, phải ước lượng độ dài tối đa của danh sách để khai báo cỡ của mảng -> lãng phí bộ nhớ khi danh sách còn nhỏ. Khi chạy chương trình, nếu phép toán xen vào được thực hiện thường xuyên, sẽ có khả năng dẫn đến danh sách đầy. biểu diễn danh sách bới mảng, các phép toán truy cập đến mỗi phần tử của danh sách, xác định độ dài của danh sách... được thực hiện trong thời gian hằng, phép toán xen vào và loại bỏ đòi hỏi thời gian tỉ lệ với độ dài của danh sách. với danh sách liên kết, các phép toán xen vào và loại bỏ lại được thực hiện trong thời gian hằng, còn các phép toán khác lại cần thời gian tuyến tính -> cần xét xem phép toán nào trên danh sách được sử dụng nhiều nhất, để lựa chọn phương pháp biểu diễn cho thích hợp. 4. Các dạng danh sách liên kết khác 4.1 Danh sách vòng tròn Danh sách liên kết vòng tròn (danh sách vòng tròn): con trỏ của thành phần cuối cùng của danh sách không bằng null mà trỏ đến thành phần đầu tiên của danh sách, tạo thành một vòng tròn. Đặc điểm: thành phần trong danh sách đều bình đẳng, mỗi thành phần đều có thành phần đi sau. Xuất phát từ một thành phần bất kỳ ta có thể truy cập đến thành phần bất kỳ khác trong danh sách. Danh sách rỗng head->next=head -> Kô bao giờ rỗng 4.2 Danh sách hai liên kết có những xử lý trên mỗi thành phần của danh sách lại liên quan đến cả thành phần đi trước và thành phần đi sau. ->nextleft trỏ đến thành phần bên trái và nextright trỏ đến thành phần bên phải -> ta có một danh sách hai liên kết. Ds này cần đến hai con trỏ : left trỏ đến thành phần ngoài cùng bên trái và righ trỏ đến thành phần ngoài cùng bên bên phải danh sách 4.2 Danh sách hai… Nhuợc điểm: cài đặt danh sách tiêu tốn nhiều bộ nhớ hơn danh sách một liên kết, ưu điểm: khi xem xét một danh sách hai liên kết ta có thể tiến lên trước hoặc lùi lại sau. Các phép toán trên danh sách hai liên kết được thực hiện dễ dàng hơn danh sách một liên kết. 4.2 Danh sách hai… Phép toán xoá một phần tử Q = P-> nextleft ; Q->nextright = P-> nextright ; Q = P-> nextright ; Q-> nextleft = P-> nextleft ; free(P) ; 5. Ứng dụng danh sách Bài toán: Các phép tính số học trên đa thức xét các phép tính số học (cộng, trừ, nhân, chia) đa thức một biến 3x5 - x3 + 5x2 + 6 (1) Mỗi số hạng của đa thức được đặc trưng bởi hệ số (coef) và số mũ của x (exp). Nếu các số hạng trong đa thức được sắp xếp theo thứ tự giảm dần của số mũ, như (1) -> Xem đa thức như một danh sách tuyến tính các số hạng -> phương pháp tốt nhất là biểu diễn đa thức dưới dạng danh sách liên kết. Mỗi thành phần của danh sách này là bản ghi gồm ba trường : coef - hệ số, exp - số mũ của x và con trỏ để trỏ tới thành phần đi sau. struct term { float coef; int exp; struct term *next; }; typedef struct term LIST; typedef LIST *POINTER; 5. Ứng dụng… Cài đặt bằng ds nối vòng 3 5 -1 3 5 2 6 0 0 -1 5. Ứng dụng… xét phép cộng đa thức P với đa thức Q. Con trỏ P(Q) trỏ đến đầu danh sách nối vòng biểu diễn đa thức P(Q) dstổng: thay đổi danh sách Q (xen vào, loại bỏ hay thay đổi trường coef). Một con trỏ P1 chạy trên danh sách P, hai con trỏ Q1, Q2 chạy cách nhau một bước (Q2 = Q1->Next) trên danh sách Q. So sánh số mũ của P1 với số mũ của Q2. Có ba khả năng 1. Nếu P1 -> exp > Q2 -> exp thì ta xen thành phần P1 vào danh sách Q trước thành phần Q2. Cho P1 chạy tới thành phần sau trong danh sách. 2. Nếu P1-> exp = Q2-> exp thì ta thêm P1^. coef vào Q2^. coef. nếu Q2^. coef = 0 thì ta loại bỏ thành phần Q2 khỏi danh sách Q. cho P1 và Q1, Q2 chạy tới các thành phần tiếp theo trong danh sách P và Q. 3. Nếu P1-> exp exp thì ta cho Q1, Q2 chạy lên một bước. lặp lại cho tới khi P1 hoặc Q2 đi hết danh sách. Trong trường hợp Q2 đi hết danh sách Q còn P1 còn ở giữa danh sách P thì chuyển các thành phần còn lại của danh sách P vào danh sách Q. Void Read Poly (POINTER P) ; // Tạo ra danh sách vòng tròn biểu diễn đa thức { POINTER P1, P2; Char Traloi; P = (POINTER)malloc(sizeof(LIST)); P1-> coef = 0 ; P1-> exp = -1; //Tạo ra đầu danh sách P1 = P ; gets(Traloi) ; while Traloi == “C“ { P2 = (POINTER)malloc(sizeof(LIST)); gets(P2->coef, P2-> exp) ; P1-> next = P2 ; P1 = P2 ; gets(traloi) } P1-> next = P ; } void Insert(POINTER P1, Q1, Q2) // Xen thành phần P1 vào giữa hai thành phần Q1, Q2 trong danh sách Q { P1->next= Q2 ; Q1->next = P1; Q1= P1 } void Delete (POINTER Q1, Q2) // Xoá thành phần Q2 khỏi danh sách Q, Q2 = Q1-> next { Q1->next = Q2->next ; Q2 = Q1->next } void WritePoly (POINTER Q1) ; { Q = Q1-> next ; if Q-> exp == -1 printf(“Q = 0” ); else while Q-> exp > -1 do { Write (Q->coef, X' ', Q->exp); Q = Q-> next ; if Q->exp > -1 printf('+'); } } Void main(){ Read Poly (P) ; Read Poly (Q) ; P = P->next ; Q1 = Q ; Q2 = Q1-> next ; while (P-> exp > -1) && ( Q2->exp > -1){ if P->exp > Q2-> exp { P1 = P ; P = P-> next ; Insert (P1, Q1, Q2); } else if P-> exp == Q2-> exp { Q2->coef = Q2->coef + P->coef ; if Q2^. coef = 0 Delete (Q1, Q2) else { Q1 = Q2 ; Q2 = Q1-> next ; } P = P->next } else { Q1 = Q2 ; Q2 = Q1->next; } } //hết vòng lặp while. Nếu Q2^. exp = -1 còn P^. exp > -1 thì chuyển các hạng thức còn lại của đa thức P vào cuối đa thức Q while (P->exp > -1) { P1 = P ; P = P-> next ; Insert (P1, Q1, Q2) } WritePoly (Q) ; } Bài tập 1) Một ma trận chỉ chứa rất ít phần tử với giá trị có nghĩa (ví dụ: phần tử ≠ 0) được gọi là ma trận thưa. Ví dụ : 1 0 0 0 2 3 2 6 0 0 0 0 3 0 0 6 5 0 Dùng cấu trúc liên kết để tổ chức biễu diễn một ma trận thưa sao cho tiết kiệm nhất (chỉ lưu trữ các phần tử có nghĩa). a) Viết chương trình cho phép nhập, xuất ma trận. b) Viết chương trình con cho phép cộng hai ma trận Bài tập 2) Bài toán Josephus : có N người đã quyết định tự sát tập thể bằng cách đứng trong vòng tròn và giết người thứ M quanh vòng tròn, thu hẹp hàng ngũ lại khi từng người lần lượt ngã khỏi vòng tròn. Vấn đề là tìm ra thứ tự từng người bị giết. Ví dụ : N = 9, M = 5 thì thứ tự là 5, 1, 7, 4, 3, 6, 9, 2, 8. Hãy viết chương trình giải quyết bài toán Josephus, sử dụng cấu trúc liên kết. Bài tập 3) Cài đặt dsách hđộng LIFO, FIFO int main( void ) { LISTPTR rec_addr; int i=0; first = rec_addr; /* Start of our printf(“Before insertion\n”); A=1; b=1; For (i=1; i<20; i++) { c=a+b; add_to_list( c, HEAD, d); } }