Lập trình C - Sự tự tham chiếu của cấu trúc trong C

Nội dung text: Lập trình C - Sự tự tham chiếu của cấu trúc trong C

1. Chủ đề ⚫ Sự tự tham chiếu của cấu trúc trong C ⚫ Cấu trúc dữ liệu danh sách liên kết đơn (single linked list), danh sách liên kết đôi (double linked list): -Khởi tạo, thi hành. -Thuật toán quét dữ liệu -Thuật toán chèn, xoá.
2. Sự tự tham chiếu của cấu trúc ⚫ 1 hoặc nhiều thành phần của nó là con trỏ tới chính nó. struct list { char data; struct list *link; }; list item1, item2, item3; a b c item1.data=‘a’; item2.data=‘b’; item3.data=‘c’; item1.link=item2.link=item3.lik=NULL;
3. Thi hành list trong C ⚫ List là 1 cấu trúc dữ liệu mà nó lưu giữ thông tin tổng quát về vị trí của phần tử tiếp theo. ⚫ Các phần tử của “single linked list ” chỉ có vị trí tiếp theo ⚫ Trong C con trỏ được sử dụng để trỏ tới phần tử tiếp theo. ⚫ Array(mảng): ta có thể truy nhập ở bất kì vị trí nào trong mảng ngay lập tức. ⚫ Linked list: ta có thể thay đổi số phần tử dữ liệu của nó.
4. Khai báo linked list typedef elementtype;//kiểu dữ liệu phần tử typedef struct node{ elementtype element; node* next; }; node* root; node* cur; Hoặc: typedef elementtype; struct node{ elementtype element; struct node* next; }; struct node* root; struct node* cur;
5. Cấp phát bộ nhớ cho 1 phần tử ⚫ Ta cần cấp phát 1 khối bộ nhớ cho mỗi node(phần tử) qua 1 con trỏ. struct node * new; new = (struct node*) malloc(sizeof(structnode)); new->element = new->next = null; • new->addr có nghĩa là (*new).addr. • “con trỏ biến cho bản ghi cấu trúc” ->”tên trường (field)”
6. Exercise 3.1 ⚫Ta thiết kế “address list”(danh sách địa chỉ) cho các số điện thoại di động . ⚫Phải tạo 1 bản ghi cấu trúc gồm có name, phone number và email address. ⚫Phải tạo 1 chương trình có thể giải quyết với số lượng dữ liệu tuỳ ý.
7. Exercise 3.1 (tiếp) ⚫Tạo 1 danh sách liên kết đơn chứa danh sách phone address. ⚫Viết 1 hàm insert 1 phần tử vào list ngay sau phần tử hiện thời, sử dụng nó để thêm node vào list ⚫Viết 1 hàm duyệt toàn bộ list và in ra thông tin chứa trong nó. ⚫Viết hàm xoá 1 node khỏi list.
8. Gợi ý ⚫Bạn có thể tổ chức các phần tử và cấu trúc dữ liệu theo bản ghi cấu trúc AddressList sau.Bạn tự định nghĩa 1 cấu trúc (Address) để chứ thông tin về địa chỉ. struct AddressList { struct AddressList *next; struct Address addr; };
9. Khai báo bản ghi cấu trúc struct AddressList { struct AddressList *next; struct Address addr; }; ⚫“next”: biến con trỏ trỏ tới phần tử tiếp theo cũng có cùng cấu trúc AddressList. ⚫“addr”: là 1 địa chỉ
10. 3 thừa số quan trọng của 1 list ⚫ Root: đầu của list ⚫ NULL:giá trị của con trỏ.nó báo hiệu kết thúc của list. ⚫ Cur: biến con trỏ lưu giữ phần tử hiện tại. Cur Root (head) NULL
11. Link list : Insertion (chèn) ⚫ Chèn ngay sau vị trí hiện tại: create new_item //phần tử mới cur->next = new; cur = cur->next; Cur root New_item
12. Link list : Insertion ⚫ Chèn ngay sau vị trí hiện tại new = ( struct AddressList * ) malloc( sizeof(struct AddressList ) ); new->addr = addr; new->next = NULL; if ( root == NULL ) { /* nếu không có phần tử nào */ root = new; cur = root; } else { cur->next = new; cur = cur->next; } }
13. Link list : Insertion ⚫ Chèn vào trước vị trí hiện tại: cur prev root New_item
14. Duyệt 1 list ⚫for ( cur = root; cur != NULL; cur = cur- >next ) { showAddress( cur->addr, stdout ); } //showAddress là hàm in ra dữ liệu (tự viết)
15. Duyệt 1 list ⚫Thay đổi giá trị của biến con trỏ cur trong dãy ⚫Các biến này được gọi là “biến lặp” ⚫Hoàn thành duyệt khi giá trị cur = NULL
16. Deletion (xoá) ⚫Khi xoá phần tử đầu tiên: del=root; root = del->next; free(del); ⚫Khi xoá phần tử đầu tiên, ta chuyển con trỏ root tới vị trí next được chỉ ra bởi del.
17. Xoá phần tử ở giữa ⚫Xoá node đang được trỏ bởi cur. ⚫Xác định prev là con trỏ tới node ngay trước node cần xoá. ⚫Sau đó thực hiện: prev->next = cur->next; free(cur);
18. Exercise 3.2 ⚫ Tạo hàm insert, delete với tham số n (nguyên) chỉ ra vị trí của node bị tác động đến. - Vị trí đầu tiên là 0 - n = 1: thêm phần tử vào sau phần tử đầu tiên. - n = 2: thêm phần tử vào sau phần tử thứ 2. struct AddressList *insert (struct AddressList *root, struct Address ad, int n); struct AddressList *delete(struct AddressList *root, int n);
19. Giải phóng list to_free = root ;//to_free là biến lặp lưu vị trí node ta giải phóng while (to_free != NULL) { root = root->next; free(to_free); to_free = root; }
20. Exercise 3.3 ⚫ Xây dựng 1 chương trình quản lí sinh viên đơn giản sử dụng linked list gồm node có cấu trúc như sau: typedef struct Student_t { char id[ID_LENGTH]; char name[NAME_LENGTH]; int grade; struct Student_t *next; } Student;
21. Exercise 3.3 Yêu cầu: ⚫ List được sắp xếp theo thứ tự giảm dần của điểm sinh viên. ⚫ Chương trình cung cấp các chức năng sau: - Chèn new student (khi chèn thì trước hết fải tìm ra vị trí đúng của student đó đã rồi mới chèn). - Tìm 1 student qua ID: trả về con trỏ. - Xoá 1 student ( xác định qua ID ) khỏi list.
22. Thêm 1 student – vào đầu list if (root == NULL) return to_add; //to_add là 1 node đã được tạo ra từ trước chứa dữ liệu về sinh viên cần thêm. if (to_add->grade > root->grade) { to_add->next = root; return to_add; }
23. Thêm 1 sinh viên – vào giữa/cuối list curr_std = root; while (curr_std != NULL && to_add->grade grade) //vòng lặp tìm vị trí đúng để add vào { prev_std = curr_std; curr_std = curr_std->next; } prev_std->next = to_add; to_add->next = curr_std; return root;
24. Exercise 3.4 ⚫ Sử dụng Student_Package2.c (các bt trước) và tạo hàm find_student() nhận vào 1 list và 1 số ID, trả về con trỏ tới student có số ID trùng khớp ở trong list đó, hoặc trả về 0 nếu không tìm thấy. Student *find_student(Student *root, char* id); - Gợi ý: sử dụng hàm strcmp(s1,s2) để so sánh ID,hàm này trả về 0 nếu s1 trùng khớp s2.
25. Solution /*tim student có ID khớp với ID được đưa ra*/ Student *find_student(Student *root, char* id) { Student *to_search = root;/* bắt đầu từ root của list */ while (to_search != NULL) /* đi khắp list */ { if (strcmp(to_search->id, id) == 0) /* id giống */ return to_search; to_search = to_search->next; } /* Nếu đến đây tức là đã không tìm được ID khớp */ return NULL; }
26. Loại bỏ 1 student ⚫Ta muốn có thể loại bỏ student qua ID. ⚫Hàm thực hiện: remove_student() ⚫Xem Student_Package3.c
27. Loại bỏ 1 student - ở đầu list if (root == NULL) return root; cur = root; if (strcmp(cur->id, id) == 0) { root = root->next; free(cur); return root; }
28. Loại bỏ 1 student - ở giữa list while (cur != NULL && strcmp(cur->id, id) != 0) { prev = cur; cur = cur->next; } if (cur != NULL) { prev->next = cur->next; free(cur); } return root;
29. Exercise 3.5 ⚫Sử dụng Student_Package3.c và thêm hàm change_grade(thay đổi điểm). Hàm này nên lấy tham số là root của list, ID của người có điểm (grade) ta muốn thay đổi và điểm mới. ⚫Gợi ý: tạo ra 1 new student với cùng tên, ID như cũ nhưng có điểm mới.Sau đó loại bỏ student cũ đi và thêm student mới này vào sử dụng các hàm đã có từ trước.
30. Solution Student *find_student(Student* root, char* id) { Student* curr = root; while (curr != NULL && strcmp(curr->id, id) != 0) { curr = curr->next; } return curr; } Student *change_grade(Student *root, char* id, int new_grade) { Student* std = find_student(root, id); /*tạo new student*/ std = create_student(std->name, id, new_grade); root = remove_student(root, id); return add_student(root, std); }