lOMoARcPSD|39108650 TRƯỜNG ĐẠI HỌC PHENIKAA KHOA KHOA HỌC CƠ BẢN ⸎⸎⸎⸎⸎ BÀI TẬP LỚN KẾT THÚC HỌC PHẦN Môn Cấu trúc dữ liệu và thuật toán Lớp Cấu trúc dữ liệu và thuật toán_1.2_LT Sinh viên : Đỗ Minh Quân Lớp : K14-CNTT3 Mã SV : 20010879 Downloaded by ANH LE (bachvan14@gmail. Các thao tác trên danh sách liên kết Danh sách liên kết là 1 cấu trúc dữ liệu có kiểu tuần tự, mỗi phần tử trong danh sách liên kết có chứa thông tin, qua đó ta có thể truy cập tới phần tử này. Danh sách liên kết có thể được xem như là 1 sự bố trí tuần tự các phần tử trong 1 tập. Bắt đầu từ 1 nút, ta coi đó là phần tử đầu tiên trong danh sách.
Từ nút này, theo liên kết mà nó trỏ tới, ta có nút thứ 2, được coi là phần tử thứ 2 trong danh sách, v. cứ tiếp tục như vậy cho đến hết danh sách. Nút cuối cùng có thể có liên kết là một liên kết null, tức là không trỏ tới nút nào, hoặc nó có thể trỏ về nút đầu tiên để tạo thành 1 vòng. • Các thao tác trên danh sách liên kết - Tạo, cấp phát, và giải phóng bộ nhớ cho 1 nút listnode p; // Khai báo biến p p = (listnode)malloc(sizeof(struct node));//cấp phát bộ nhớ cho p free(p); //giải phóng bộ nhớ đã cấp phát cho nút p; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 - Chèn một nút vào đầu danh sách B1 Tạo và cấp phát bộ nhớ cho một nút mới ,đc trỏ tới bởi q B2 Sau khi gán các giá trị thích hợp cho phần tử của nút mới, cho con trỏ tiếp của nút mới trỏ đến phần tử đầu tiên của nút.
B3 Để p trỏ đến đầu nút danh sách ,ta cần cho p trỏ đến nút mới tạo void Insert_Begin(listnode *p, int x){ listnode q; q = (listnode)malloc(sizeof(struct node)); q-> item = x; q-> next = *p; *p = q; } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 - Chèn một nút vào cuối danh sách B1 Dịch chuyển con trỏ tới nút cuối của danh sách. Để làm được việc này, ta phải khai báo một biến con trỏ mới r. Ban đầu, biến này, cùng với p, trỏ đến đầu danh sách. Lần lượt dịch chuyển r theo các nút kế tiếp cho tới khi đến cuối danh sách.
B2 Cho con trỏ tiếp của nút cuối (được trỏ tới bởi r) trỏ đến nút mới tạo là q, và con trỏ tiếp của q trỏ tới null void Insert_End(listnode *p, int x){ listnode q, r; q = (listnode)malloc(sizeof(struct node)); q-> item = x; q->next = NULL; if (*p==NULL) *p = q; else{ r = *p; while (r->next != NULL) r = r->next; r->next = q; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 } } - Chèn một nút vào trước nút r trong danh sách B1 Cho con trỏ tiếp của nút mới trỏ đến nút kế tiếp của nút r. B2 Cho con trỏ tiếp của nút r trỏ đến q void Insert_Middle(listnode *p, int position, int x){ int count=1, found=0; listnode q, r; r = *p; while ((r != NULL)&&(found==0)){ if (count == position){ q = (listnode)malloc(sizeof(struct node)); q-> item = x; q-> next = r-> next; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 r-> next = q; found = 1; } count ++; r = r-> next; } if (found==0) printf(“Khong tim thay vi tri can chen !”); } - Xóa một nút ở đầu danh sách B1 Dùng một con trỏ tạm q trỏ đến đầu danh sách B2 Dịch chuyển con trỏ p qua phần tử đầu tiên đến phần tử kế tiếp Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 B3 Ngắt liên kết của biến tạm q với nút tiếp theo, giải phóng bộ nhớ Cho q. void Remove_Begin(listnode *p){ listnode q; if (*p == NULL) return; q = *p; *p = (*p)-> next; q-> next = NULL; free(q); } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 - Xóa một nút ở cuối danh sách B1 Dịch chuyển con trỏ tới nút gần cuối của danh sách. Để làm được việc này, ta phải dùng 2 biến tạm là q và r.
Lần lượt dịch chuyển q và r từ đầu danh sách tới cuối danh sách, trong đó q luôn dịch chuyển sau r một nút. Khi r tới nút cuối cùng thì q là nút gần cuối cùng nhất B2 Cho con trỏ tiếp của nút gần cuối cùng nhất (đang được trỏ bởi q) trỏ tới null. Giải phóng bộ nhớ cho nút cuối cùng (đang được trỏ bởi r) void Remove_End(listnode *p){ listnode q, r; if (*p == NULL) return; if ((*p)-> next == NULL){ Remove_Begin(*p); return; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 } r = *p; while (r-> next != NULL){ q = r; r = r-> next; } q-> next = NULL; free(r); } - Xóa một nút trước nút r danh sách B1 Sử dụng một biến tạm q trỏ đến nút đứng trước nút r B2 Cho con trỏ của nút r trỏ tới nút đứng sau nút q. Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 B3 Ngắt liên kết của nút q và giải phóng bộ nhớ cho q void Remove_Middle(listnode *p, int position){ int count=1, found=0; listnode q, r; r = *p; while ((r != NULL)&&(found==0)){ if (count == position){ q = r-> next; r-> next = q-> next; q-> next = NULL; free (q); found = 1; } count ++; r = r-> next; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 } if (found==0) printf(“Khong tim thay vi tri can xoa !”); } - Duyệt toàn bộ danh sách Thao tác duyệt danh sách cho phép duyệt qua toàn bộ các phần tử của danh sách, từ phần tử đầu tiền cho tới phần tử cuối cùng.
Để thực hiện thao tác này, ta cần một biến tạm r trỏ tới đầu danh sách. Từ vị trí này, theo liên kết của các nút, thực hiện duyệt qua từng phần tử trong danh sách. Trong quá trình duyệt, tại mỗi nút ta có thể thực hiện các thao tác cần thiết như lấy thông tin phần tử, sửa thông tin, so sánh, v. r = p; while (r-> next != null){ //thực hiện các thao tác cần thiết r = r-> next; } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 Chương trình chạy: #include <stdio.h> struct node { int data; int key; struct node *next; }; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 struct node *head = NULL; struct node *current = NULL; //hien thi danh sach void printList() { struct node *ptr = head; printf("\n[ "); //bat dau tu phan dau danh sach while(ptr != NULL) { printf("(%d,%d) ",ptr->key,ptr->data); ptr = ptr->next; } printf(" ]"); Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 } //chen link tai vi tri dau tien void insertFirst(int key, int data) { //tao mot link struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; //tro link nay toi first node cu link->next = head; //tro first toi first node moi head = link; } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 //xoa phan tu dau tien struct node* deleteFirst() { //luu tham chieu toi first link struct node *tempLink = head; //danh dau next toi first link la first head = head->next; //tra ve link bi xoa return tempLink; } //kiem tra list co trong hay khong bool isEmpty() Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 { return head == NULL; } int length() { int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) { length++; } return length; } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 //tim mot link voi key da cho struct node* find(int key){ //bat dau tim tu first link struct node* current = head; //neu list la trong if(head == NULL) { return NULL; } //duyet qua list while(current->key != key){ //neu day la last node if(current->next == NULL){ Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 return NULL; }else { //di chuyen toi next link current = current->next; } } //neu tim thay du lieu, tra ve link hien tai return current; } //xoa mot link voi key da cho struct node* deleteKey(int key){ //bat dau tu first link struct node* current = head; struct node* previous = NULL; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 //neu list la trong if(head == NULL){ return NULL; } //duyet qua list while(current->key != key){ //neu day la last node if(current->next == NULL){ return NULL; }else { //luu tham chieu toi link hien tai previous = current; //di chuyen toi next link current = current->next; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 } } //cap nhat link if(current == head) { //thay doi first de tro toi next link head = head->next; }else { //bo qua link hien tai previous->next = current->next; } return current; } // ham sap xep Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 void sort(){ int i, j, k, tempKey, tempData ; struct node *current; struct node *next; int size = length(); k = size ; for ( i = 0 ; i < size - 1 ; i++, k-- ) { current = head ; next = head->next ; for ( j = 1 ; j < k ; j++ ) { if ( current->data > next->data ) { tempData = current->data ; current->data = next->data; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 next->data = tempData ; tempKey = current->key; current->key = next->key; next->key = tempKey; } current = current->next; next = next->next; } } } // ham dao nguoc list void reverse(struct node** head_ref) { struct node* prev = NULL; struct node* current = *head_ref; Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 struct node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } main() { insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("Danh sach ban dau: "); //in danh sach printList(); while(!isEmpty()){ struct node *temp = deleteFirst(); printf("\nGia tri bi xoa:"); printf("(%d,%d) ",temp->key,temp->data); } printf("\nDanh sach sau khi da xoa gia tri: "); printList(); Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 insertFirst(1,10); insertFirst(2,20); insertFirst(3,30); insertFirst(4,1); insertFirst(5,40); insertFirst(6,56); printf("\nPhuc hoi danh sach: "); printList(); printf("\n"); struct node *foundLink = find(4); if(foundLink != NULL){ printf("Tim thay phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf("\n"); }else { Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 printf("Khong tim thay phan tu."); } deleteKey(4); printf("Danh sach, sau khi xoa mot phan tu: "); printList(); printf("\n"); foundLink = find(4); if(foundLink != NULL){ printf("Tim thay phan tu: "); printf("(%d,%d) ",foundLink->key,foundLink->data); printf("\n"); }else { printf("Khong tim thay phan tu."); } Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 printf("\n"); sort(); printf("Danh sach sau khi duoc sap xep: "); printList(); reverse(&head); printf("\nDanh sach sau khi bi dao nguoc: "); printList(); } 1.
Các thao tác trên hàng đợi - Thao tác khởi tạo hàng đợi Thao tác này thực hiện việc gán giá trị 0 cho biến head, giá trị MAX -1 cho biến tail, và giá trị 0 cho biến count, cho biết hàng đợi đang ở trạng thái rỗng. void QueueInitialize(queue *q){ Downloaded by ANH LE (bachvan14@gmail.com) lOMoARcPSD|39108650 q-> head = 0; q-> tail = MAX-1; q-> count = 0; return; } - Thao tác kiểm tra hàng đợi rỗng Hàng đợi rỗng nếu có số phần tử nhỏ hơn hoặc bằng 0. int QueueEmpty(queue q){ return (q.count <= 0); } - Thao tác thêm 1 phần tử vào hàng đợi void Put(queue *q, int x){ if (q-> count == MAX) printf(“Hang doi day !”); else{ if (q->tail == MAX-1 ) q->tail=0; else (q->tail)++; q->node[q->tail]=x; q-> count++; Downloaded by ANH LE (bachvan14@gmail.