Lý thuyết và bài tập Bài 05: Danh sách liên kết môn Máy tính - Hệ thống nhúng | Đại học Đồng Tháp

Bộ môn Máy tính và Hệ thống nhúng Bài 05 DANH SÁCH LIÊN KẾT I. Mục tiêu
Hoàn tất bài thực hành này, sinh viên có thể:
▪ Cài đặt được danh sách liên kết bằng ngôn ngữ C/C++.
▪ Triển khai và quản lý dữ liệu bằng danh sách liên kết. II. Lý thuyết 1. Định nghĩa:
Danh sách là tập hợp gồm một số hữu hạn các phần tử có cùng kiểu dữ liệu.
❖ Có 2 cách cài đặt danh sách:
• Cài đặt theo kiểu kế tiếp
• Cài đặt theo kiểu liên kết
❖ Các dạng 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
❖ Các thao tác cơ bản trên danh sách liên kết • Tạo danh sách rỗng
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1
Bộ môn Máy tính và Hệ thống nhúng
• Thêm một phần tử vào danh sách Thêm vào đầu danh sách
input: danh sách (first, last), phần tử mới new_ele
output: danh sách (first, last) với new_ele ở đầu DS
* Nếu Danh sách rỗng Thì ▪ first = new_ele; ▪ last = first; * Ngược lại
▪ new_ele ->link = first; ▪ first = new_ele ; Thêm vào cuối danh sách
input: danh sách (first, last), phần tử mới new_ele
output: danh sách (first, last) với new_ele ở cuối DS
* Nếu Danh sách rỗng Thì ▪ first = new_ele; ▪ last = first; * Ngược lại ▪ last->link = new_ele ; ▪ last = new_ele ;
Thêm vào sau phần tử “q”
input: danh sách (first, last), q, phần tử mới new_ele
output: danh sách (first, last) với new_ele ở sau q * Nếu ( q != NULL) thì
▪ new_ele -> link = q -> link; ▪ q -> link = new_ele ; Nếu ( q == last) thì ▪ last = new_ele; * Ngược lại
▪ Thêm new_ele vào đầu danh sách
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2
Bộ môn Máy tính và Hệ thống nhúng
• Xóa một phần tử ra khỏi danh sách Xóa đầu danh sách
▪ Bước 1: Gọi p là node đầu của danh sách (là l.first)
▪ Bước 2: Cho l.first trỏ vào node sau node p (là p->link)
▪ Bước 3: Nếu danh sách trở thành rỗng thì l.last=NULL
▪ Bước 4: Giải phóng vùng nhớ mà p trỏ tới Xóa sau phần tử “q”
✓ Điều kiện để có thể xóa được node sau q là : + q phải khác NULL
+ Node sau q phải khác NULL ➢ Có 3 thao tác
▪ Bước 1: Gọi p là node sau q
▪ Bướ 2: Cho vùng link của q trỏ vào node đứng sau p (là l.link)
▪ Bước 3: Nếu p là phần tử cuối thì l.last trỏ vào q
▪ Bước 4: Giải phóng vùng nhớ mà p trỏ tới • Duyệt danh sách ▪
Bước 1: p = first; //Cho p trỏ đến phần tử đầu danh sách ▪
Bước 2: Trong khi (Danh sách chưa hết) thực hiện
▪ B21 : Xử lý phần tử p; ▪ B22 : p:=p->link;
// Cho p trỏ tới phần tử kế
• Hủy toàn bộ danh sách ▪
Bước 1: Trong khi (Danh sách chưa hết) thực hiện ▪ B11: ▪ p = first; ▪
first =first->link; // Cho p trỏ tới phần tử kế ▪ B12: ▪ Hủy p; ▪ Bước 2: ▪
last = NULL;//Bảo đảm tính nhất quán khi xâu rỗng III. Thực hành
❖ Bài tập bắt buộc:
1. Hoàn thành các yêu cầu bên dưới: Cho các tên hàm: struct birth { unsigned char day; unsigned char month; unsigned int year; }; struct Student { char name[50];
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 3
Bộ môn Máy tính và Hệ thống nhúng struct birth;
char studentID[8]; float GPA; }; struct NODE {
// thêm định nghĩa node vào đây }; struct LIST{
// thêm định ngĩa list vào đây };
void GetNode (Student X); // hàm tạo node mới
void AddFirst(LIST &l, NODE* new_ele); // Thêm node mới vào đầu danh // sách
void AddLast(LIST &l, NODE *new_ele) ; // Thêm node mới vào cuối danh // sách
NODE * SearchNode (LIST l, Student x); // Tìm node với khoa xalloc
void AddAfter (LIST &l, NODE * new_ele, NODE * q); // Thêm vào sau // node qsort
void PrintList(LIST l); // In danh sách
void RemoveFirst (LIST &l); // Xóa phần tử ở đầu sách
void RemoveLast (LIST &l); // Xóa phần tử ở cuối danh sách
1.1.Viết lại nội dung cho các hàm trên.
1.2.Viết hàm main để gọi các hàm trên để tạo một chương trình hoàn chỉnh. ❖ Bài tập nâng cao:
1. Sửa lại các hàm ở phần trên để tạo sử dụng danh sách liên kết kép.
2. Thêm hàm đọc và ghi file để đọc/ghi dữ liệu giữa file data.txt và danh sách liên kết kép.
3. Viết thêm hàm tìm tất cả sinh viên có điểm trung bình dưới năm và xóa khỏi danh sách
ban đầu và thêm vào danh sách thứ hai.
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 4