Bài giảng bài 3; Danh sách liên kết đơn (Linked list)

Câu hỏi kiểm tra Trình bày cách khai báo hàng đợi (queue)? Trả lời typedef struct { int front,rear; int nodes[MAXSIZE]; } queue; Bài 3. DANH SÁCH LIÊN KẾT ĐƠN (LINKED LIST) CBGD: Trần Việt Khánh MỤC TIÊU Sau bài học này, sinh viên có khả năng: Trình bày được định nghĩa danh sách liên kết đơn  Cài đặt được danh sách liên kết đơn  Vận dụng danh sách liên kết đơn vào công tác quản lý (quản lý sinh viên, quản lý tuyến xe lửa,...) NỘI DUNG I/ Định nghĩa II/ Cài đặt danh sách liên kết đơn Khai báo cấu trúc của một nút trong danh sách liên kết đơn Các tác vụ trên danh sách liên kết đơn I/ Định nghĩa Danh sách liên kết đơn là một danh sách bao gồm nhiều nút liên kết với nhau, mỗi nút là một cấu trúc có hai trường: - Trường info chứa nội dung thật sự của nút. - Trường next là con trỏ cấu trúc chỉ nút kế tiếp trong danh sách. l  Hình vẽ minh họa danh sách liên kết đơn NULL Khai báo mỗi nút là một mẫu tin có hai trường là info và next. - Trường info: chứa nội dung của nút. - Trường next: là con trỏ chỉ nút kế tiếp trong danh sách II/ Cài đặt danh sách liên kết đơn 1. Khai báo cấu trúc một nút // Khai báo cấu trúc của một nút typedef struct node { node *next; int info; } node; // Khai báo kiểu con trỏ chỉ đến nút typedef struct node *list; Khởi tạo danh sách rỗng void CreateList(list &l) { l=NULL; } 2. Các tác vụ trên danh sách liên kết đơn l  NULL Kiểm tra danh sách có bị rỗng không bool EmptyList(list l) { return ( l == NULL); } Minh họa đoạn code trên: l  NULL 1 2 3 4 giả sử nút cần tìm là x =3 Tìm kiếm phần tử x trong danh sách list SearchList(list l, int x) { list p; p=l; while (p!=NULL && p->info!=x) p=p->next; return p; } Tìm vị trí của nút trước nút cần xóa hoặc thêm trong danh sách list SearchPrevousNode(list l, int x) { list p,c; bool stop=false; p=NULL; c=l; while( c!=NULL && !stop) { if(c->info != x) { p=c; c= c->next; } else stop=true; } return p; } l  1 2 3 4 NULL Minh họa đoạn code trên: giả sử nút cần xóa x = 4 X Thêm một nút vào danh sách ( có 3 trường hợp) + Trường hợp 1: thêm một nút vào đầu danh sách (p==NULL) NULL l  Nút newp newp->next = l; l = newp; Đây là đoạn code của trường hợp trên if(p==NULL)// chèn nút newp ở đầu danh sách { newp->next=l; l = newp; } + Trường hợp 2: thêm một nút vào giữa danh sách (thêm sau phần tử p) NULL l  Nút newp newp->next = p->next; p->next = newp; + Trường hợp 3: thêm một nút vào cuối danh sách (thêm sau phần tử p) NULL l  Nút newp newp->next = p->next; p->next = newp; // chèn giữa và chèn cuối(chèn nút newp sau phần tử p) if ( p != NULL) { newp->next = p->next; p->next = newp; } Đây là đoạn code của trường hợp 2 và trường hợp 3 void InsertList(list &l, list p, int x) { list newp; newp = (list) malloc(sizeof(node));//hoặc newp = new node; newp->info =x; if(p==NULL)// chèn nút newp ở đầu danh sách { newp->next=l; l = newp; } else //chèn giữa và chèn cuối,chèn nút newp sau phần tử p { newp->next = p->next; p->next = newp; } } // Cài đặt phương thức thêm một nút vào danh sách Xóa một nút ra khỏi danh sách (có 3 trường hợp) + Trường hợp 1: xóa nút ở đầu danh sách (p==NULL) NULL l  temp l = temp->next; delete temp; temp=l; Đây là đoạn code của trường hợp 1: If (p==NULL) // xóa nút ở đầu danh sách { temp=l; l = temp->next; } + Trường hợp 2: xóa nút ở giữa danh sách (xóa sau phần tử p) NULL l  temp p->next = temp->next; delete temp; temp=p->next; + Trường hợp 3: xóa nút ở cuối danh sách (xóa sau phần tử p) NULL l  temp p->next = temp->next; delete temp; temp=p->next; // Xóa giữa và xóa cuối ( xóa sau phần tử p ) if ( p != NULL) { temp = p->next; p->next = temp->next; } Đây là đoạn code của trường hợp 2 và trường hợp 3 void DeleteList(list &l, list p) { list temp; if(p==NULL) // xóa nút temp ở đầu danh sách { temp = l; l = temp->next; } else // Xóa sau nút p (xóa giữa và cuối) { temp = p->next; p->next = temp->next; } delete temp; } // Định nghĩa phương thức xóa một nút ra khỏi danh sách Đảo ngược danh sách liên kết 1 2 3 4 NULL void DaoNguoc(list &l) { list p,q; p = NULL; while(!EmptyList(l)) { q = l; l = l->next; q->next = p; p=q; } l = p; } Hình vẽ minh họa đoạn code trên NULL Tách 1 danh sách ra thành 2 danh sách void SplitList( list &l, list &l1, list &l2 ) { list p1,p2; l1 = (list) malloc(sizeof(node)); //hoặc l1 = new node; l2 = (list) malloc(sizeof(node)); //hoặc l2 = new node; p1 = l1; p2 = l2; while(!EmptyList(l)) { if( l->info % 2 != 0) { p1->next = l; p1 = l; } else { p2->next = l; p2 =l; } l = l->next; } p1->next = NULL; p2->next = NULL; p1=l1;l1 = p1->next; p2=l2;l2 = p2->next; delete p1; delete p2; } Hình ảnh mô tả cho đoạn code trên: l  NULL 1 2 3 4 6 5 l1  l2  NULL NULL l1  l2  Gộp 2 danh sách thành 1 danh sách void MergeList( list &l, list &l1, list &l2 ) { list p; l = (list) malloc(sizeof(node)); //hoặc l = new node; p = l; while(!EmptyList(l1)&&!EmptyList(l2)) { if( l1->info info) { p->next = l1; l1 = l1->next ; } else { p->next = l2; l2 =l2 ->next; } p = p->next; } if(l1!=NULL) p->next = l1; if(l2!=NULL) p->next = l2; p=l; l = p->next; delete p; } Hình ảnh mô tả cho đoạn code trên: l  NULL 1 2 3 4 6 5 l1  l2  delete p; NULL 1. Viết chương trình áp dụng danh sách liên kết đơn vào quản lý sinh viên. Chương trình bao gồm: + Nhập một thông tin sinh viên vào danh sách + Xuất danh sách sinh viên trong danh sách + Cho biết danh sách sinh viên thi đậu môn Kỹ Thuật Lập Trình + Sắp xếp danh sách sinh viên tăng dần theo điểm trung bình 2. Có thể áp dụng danh sách liên kết đơn vào thực tế như quản lý tuyến xe lửa ( cho biết ngày đến, ngày đi, số toa,...) được không? BÀI TẬP