[CẤU TRÚC DỮ LIỆU & GIẢI THUẬT] – BÀI TẬP DANH SÁCH LIÊ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).

Yêu cầu:

• Nhập, xuất danh sách sinh viên.
• Tìm kiếm sinh viên theo MSSV.
• Thêm sinh viên vào danh sách đã sắp xếp.
• Xóa sinh viên khỏi danh sách theo MSSV.
• Sắp xếp danh sách sinh viên (Solection Sort, Interchange Sort, Bubble)

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

• Sắp xếp Solection Sort

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);

}

}

• Sắp xếp Interchange Sort

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);

}

• Sắp xếp Bubble

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)

Chia sẻ:

• Bấm để chia sẻ trên Twitter (Mở trong cửa sổ mới)
• Nhấn vào chia sẻ trên Facebook (Mở trong cửa sổ mới)

Thích Đang tải...

Có liên quan