Bài tập và ví dụ về danh sách nối đơn năm 2024
BÀI 5: DANH SÁCH NỐI ĐƠN(Singlely Linked List)Bộ môn CNPM- Khoa CNTTTrường Đại học SPKT Hưng YênMục tiêuSau khi học xong bài học người học có khả năng:- Trình bày được khái niệm về danh sách nối đơn- Trình bày được cấu trúc dữ liệu của 1 node trong danhsách nối đơn- Giải thích được nguyên tắc lưu trữ của danh sách nốiđơn- Viết được các giải thuật thêm, xóa, tìm kiếm, duyệtsanh sách nối đơn- Hình thành kỹ năng lập trìnhNội dung Danh sách liên kết Danh sách liên kết đơn Khái niệm Khai báo Truy xuất Một số thao tác trên danh sách liên kếtDanh sách liên kết Danh sách liên kết là tập hợp các phần tử được liên kết nhau bởicác mối liên kết; Mỗi phần tử của danh sách được gọi là 1 node; Mỗi node gồm có thành phần dữ liệu để chứa thông tin của phầntử, và một hoặc nhiều mối liên kết để liên kết với node trước [vànode sau nó]Danh sách & danh sách liên kếtDanh sách Danh sách liên kếtDanh sách là một mô hình dữliệu, nó có thể được cài đặt bởicác cấu trúc dữ liệu khác nhau.DSLK là một cấu trúc dữ liệu,nó được sử dụng để biểu diễndanh sách.Phân loại danh sách liên kết Tùy thuộc vào số liên kết trên mỗi phần tử và cách thức kết nốigiữa các nút trong DSLK mà có thể chia DSLK thành nhiềuloại: Danh sách liên kết đơn Danh sách liên kết đôi/ kép Danh sách liên kết vòng đơn Danh sách liên kết vòng képPhân loại danh sách liên kết Danh sách liên kết vòng: phần tử cuối danh sáchliên kết với phần tử đầu danh sách:A B X Z YA B C DNội dung Danh sách liên kết Danh sách liên kết đơn Khái niệm Khai báo Truy xuất Một số thao tác trên danh sách liên kếtKhái niệm danh sách nối đơn Mỗi phần tử (nút) gồm 2 thành phần: Thành phần dữ liệu: chứa giá trị lưu trong nút đó. Thành phần mối liên kết: chứa con trỏ (địa chỉ) tới nút kế tiếptrong danh sách, hoặc lưu trữ một giá trị đặc biệt (gọi là contrỏ rỗng null) nếu là nút cuối cùng của danh sách.Nội dung Danh sách liên kết Danh sách liên kết đơn Khái niệm Định nghĩa cấu trúc của một phần tử trong danh sách Truy xuất Một số thao tác trên danh sách liên kếtĐịnh nghĩa cấu trúc của một phần tửtrong danh sáchclass Node{public DataType info; //Data là kiểu dữ liệu định nghĩa trướcpublic Node link; // con trỏ chỉ đến cấu trúc Node}Trong đó:Node: là tên CTDL của 1 phần tử trong danh sáchDataType: là cấu trúc dữ liệu để biểu diễn cho 1 phần tử củadanh sáchlink: Tên của mối liên kết (do người dùng đặt)Ví dụ Khai báo 1 node dữ liệulưu số nguyên:class Node{public int info;public Node link;} Khai báo 1 node dữ liệu lưu đốitượng sinh viên:class[struct] SinhVien{public string Ten;public int MaSV;}class SVNode{public SinhVien info;public SVNode link;} 18Ví dụ 2:Định nghĩa CTDL của 1 node của DSLK đơn chứa 1 danhsách tên của các đường phốclass Node{public string info;public Node link;}Ví dụ 3:Định nghĩa CTDL của 1 node của DSLK đơn chứa 1 danhsách sinh viên, biết rằng mỗi sinh viên gồm có các thôngtin: Mã sinh viên, Họ tên, Lớp, Năm sinhCấu trúc dữ liệu của 1 phần tử của danh sách có dạng:class Node{public DataType info;public Node link;}Vậy cấu trúc dữ liệu nào có thể biểu diễn được đầy đủcủa 1 sinh viên?Đề bài: Xây dựng chương trình quản lý sinh viên bằng danh sách liên kết đơn, bao gồm các thông tin: Mã số sinh viên (MSSV), Họ và tên (HoTen), Điểm trung bình (DTB). Show
Yêu cầu:
Khai báo kiểu cấu trúc SinhVien typedef struct SinhVien { int MSSV; char HoTen[30]; float DTB; } SV; Tạo cấu trúc danh sách liên kết đơn struct node { SV info; node* next; }; typedef struct node NODE; struct list { node* pHead; node* pTail; }; typedef struct list LIST; 1. Các thao tác cơ bản trên danh sách liên kết đơn Khởi tạo danh sách liên kết đơn void init(list& l) { l.pHead = NULL; l.pTail = NULL; } Tạo node mới node* makenode(SV s) { node* p = new node; if (p == NULL) { cout << “\nKhong du bo nho.”; return NULL; } p->info.MSSV = s.MSSV; strcpy_s(p->info.HoTen, s.HoTen); p->info.DTB = s.DTB; p->next = NULL; return p; } Thêm node vào đầu danh sách void AddFirst(list& l, node* p) { if (l.pHead == NULL) l.pHead = l.pTail = p; else { p->next = l.pHead; l.pHead = p; } } Thêm node vào cuối danh sách void AddLast(list& l, node* p) { if (l.pHead == NULL) l.pHead = l.pTail = p; else { l.pTail->next = p; l.pTail = p; } } Xóa node đầu danh sách void RemoveFirst(list& l) { node* p = l.pHead; if (l.pHead == NULL) cout << “\nDanh sach rong.”; else { l.pHead = p->next; delete p; } } Xóa node cuối danh sách void RemoveLast(list& l) { node* p = l.pHead; node* r = new node; if (l.pHead == NULL) cout << “\nDanh sach rong”; else { while (p != l.pTail) { r = p; p = p->next; } l.pTail = r; r->next = NULL; delete p; } } 2. Nhập, xuất danh sách sinh viên Hàm nhập thông tin của một sinh viên void Nhap(SV& s) { cout << “Ma so sinh vien: “; cin >> s.MSSV; while (getchar() != ‘\n’); cout << “Ho va ten: “; gets_s(s.HoTen); cout << “Diem trung binh: “; cin >> s.DTB; } Hàm nhập danh sách sinh viên void InputList(list& l) { int n; SV s; do { cout << “\nNhap so luong sinh vien: “; cin >> n; if (n <= 0) cout << “So luong sinh vien phai lon hon 0. Vui long nhap lai.”; } while (n <= 0); for (int i = 1; i <= n; i++) { node* p; cout << “\nNhap thong tin sinh vien thu ” << i << endl; Nhap(s); p = makenode(s); AddLast(l, p); } } Hàm xuất thông tin của một sinh viên void Xuat(SV s) { cout << s.MSSV << “\t” << s.HoTen << “\t\t” << s.DTB << endl; } Hàm xuất danh sách sinh viên void OutputList(list l) { cout << endl << “MSSV\tHo va ten\tDiem trung binh” << endl; for (node* i = l.pHead; i != NULL; i = i->next) Xuat(i->info); } 3. Tìm kiếm sinh viên theo MSSV void TimKiem(list l) { int x; cout << “\nNhap MSSV can tim: “; cin >> x; for (node* i = l.pHead; i != NULL; i = i->next) { if (i->info.MSSV == x) { cout << endl << “MSSV\tHo va ten\t\tDiem trung binh” << endl; Xuat(i->info); return; } } cout << “Khong ton tai sinh vien co MSSV ” << x << endl; } 4. Thêm sinh viên vào danh sách đã sắp xếp void Them(list& l) { node* p, * r, * q; SV x; cout << “Nhap thong tin sinh vien can them:\n”; Nhap(x); cout << “\nThem thanh cong.\n”; p = makenode(x); if (l.pHead->info.MSSV > x.MSSV) { AddFirst(l, p); OutputList(l); return; } if (l.pTail->info.MSSV < x.MSSV) { AddLast(l, p); OutputList(l); return; } r = l.pHead; q = l.pHead->next; while (q != NULL) { if (q->info.MSSV < x.MSSV) { r = q; q = q->next; } else { r->next = p; p->next = q; OutputList(l); return; } } } 5. Xóa sinh viên khỏi danh sách theo MSSV void Xoa(list& l) { int x; cout << “\nNhap MSSV can xoa: “; cin >> x; if (l.pHead == NULL) { cout << “\nDanh sach rong.”; return; } if (l.pHead->info.MSSV == x) { cout << “Xoa thanh cong.\n”; RemoveFirst(l); OutputList(l); return; } if (l.pTail->info.MSSV == x) { cout << “Xoa thanh cong.\n”; RemoveLast(l); OutputList(l); return; } node* q = l.pHead->next; node* r = l.pHead; while (q != NULL) { if (q->info.MSSV == x) { r->next = q->next; delete q; cout << “Xoa thanh cong.\n”; OutputList(l); return; } r = q; q = q->next; } cout << “Khong ton tai MSSV can xoa.\n”; } 6. Sắp xếp danh sách sinh viên
void SolectionSort(list l) { node* min; for (node* i = l.pHead; i != l.pTail; i = i->next) { min = i; for (node* j = i->next; j != NULL; j = j->next) if (j->info.MSSV < min->info.MSSV) min = j; swap(i->info, min->info); } }
void InterchangeSort(list l) { for (node* i = l.pHead; i != l.pTail; i = i->next) for (node* j = i->next; j != NULL; j = j->next) if (i->info.MSSV > j->info.MSSV) swap(i->info, j->info); }
void Bubble(list l) { node* pTail2 = l.pTail, * r = l.pHead; for (node* i = l.pHead; i != pTail2; pTail2 = r) for (node* j = l.pHead; j != pTail2; j = j->next) { if (j->info.MSSV > j->next->info.MSSV) swap(j->info, j->next->info); r = j; } } Tác giả: Lê Thị Mỹ Hậu (sinh viên lớp 21DHT02, khoa Công Nghệ Thông Tin) Blog chia sẻ kiến thức dành cho sinh viên UFM |
