Bài tập danh sách liên kết đôi sử dụng C/C++ | Lập Trình Từ Đầu

Posted on by mtoplistChuyên mục:Top List

Để thực hành được bài tập này, bạn đọc hãy chắc chắc rằng đã đọc hết 5 bài trước trong seri “Danh sách liên kết đôi”. Trong bài này tập chung chủ yếu vào việc ôn tập lại các cách cài đặt danh sách liên kết đôi và các hàm thao tác với danh sách liên kết đôi.

1.Yêu cầu đề bài quản lý học viên bằng danh sách liên kết đôi

Trên ngôn ngữ C/C++, viết chương trình thực hiện yêu cầu sau:

  • 1 : Định nghĩa một cấu trúc Học viên bao gồm các trường thông tin như sau: Mã học viên (kiểu số nguyên), tên học viên (kiểu chuỗi ký tự), lớp (kiểu chuỗi ký tự), chuyên ngành (Khoa học máy tính, Thương mại điện tử, Quản trị an ninh mạng), điểm tổng kết (kiểu số thực).
  • 2 : Cài đặt một cấu trúc danh sách liên kết đôi cho kiểu dữ liệu Học viên, với các thao tác: 1) Khởi tạo danh sách; 2) Tạo mới một nút chứa dữ liệu; 3) Chèn nút vào đầu danh sách; 4) Duyệt danh sách.
  • 3 : Chương trình chính: Sử dụng cấu trúc danh sách liên kết đơn và các thao tác đã tạo để:

– Nhập và 1 danh sách gồm n Học viên (n bất kỳ).

– Hiển thị danh sách đã nhập ra màn hình.

– Liệt kê ra màn hình danh sách tất cả những Học viên thuộc chuyên ngành “Thương mại điện tử” và có điểm tổng kết ≥ 8.0

-Nhập vào mã học viên và xóa học viên đó khỏi danh sách

-Hiển thị lại danh sách sau khi xóa học viên

2.Xây dựng chương trình cài đặt danh sách liên kết đôi và thực hiện yêu cầu đề bài

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct hocvien{
    int mhv;
    char tenHV[25];
    char lop[25];
    char chuyenNganh[30];
    float diemTK;
};
typedef struct hocvien HV;

struct Node
{
    //khai bao thanh phan du lieu co kieu int
    HV data;
    //khai bao con tro next co kieu Node de chua dia chi phan tu sau
    Node *next;
    //khai bao con tro prev co kieu Node de chua dia chi phan tu truoc
    Node *prev;
};
typedef struct Node NODE;

struct doulist{
    //thanh phan dau danh sach
    NODE *pHead;
    //thanh phan cuoi danh sach
    NODE *pTail;
};
typedef struct doulist DLIST;

void KhoiTao(DLIST &ds){
    //dat dia chi dau danh sach bang NULL
    ds.pHead = NULL;
    //dat dia chi cuoi danh sach bang NULL
    ds.pTail = NULL;
}

NODE* TaoNode(HV x) {
    //tao mot node p moi
    NODE *p;
    p = new NODE;
    //neu p==NULL thi khong du bo nho va ket thuc viec tao node
    if (p==NULL) {
        printf ("KHONG DU BO NHO");
        return NULL;
    }
    //gan thanh phan data = x
    p->data=x;
    //gan con tro next = NULL
    p->next=NULL;
    //gan con tro prev = NULL
    p->prev = NULL;
    //tra ve node p da tao
    return p;
}

void ThemCuoi(DLIST &ds, NODE*p){
    //kiem tra danh sach rong neu rong thi them vao dau va cuoi
    if (ds.pHead == NULL){
        ds.pHead = ds.pTail = p;
    }else{
        //dat con tro next cua pTail hien tai vao p la node can them cuoi
        ds.pTail->next = p;
        //dat con tro prev cua node p ve phan tu cuoi danh sach
        p->prev = ds.pTail;
        //thay doi lai phan tu cuoi danh sach
        ds.pTail = p;
    }
}
void Nhap(DLIST &ds, int n){
    printf("NHAP VAO THONG TIN HOC VIEN\n");
    //duyet N lan
    for(int i = 0; i < n; i++){
        //nhap du lieu la cho hoc vien thu i
        HV x;
        printf("Nhap MaHV: ");
        scanf("%d",&x.mhv);
        printf("Nhap TenHV: ");
        fflush(stdin);
        gets(x.tenHV);
        printf("Nhap lop: ");
        fflush(stdin);
        gets(x.lop);
        printf("Chuyen nganh: ");
        fflush(stdin);
        gets(x.chuyenNganh);
        printf("Diem TK: ");
        scanf("%f",&x.diemTK);
        printf("\n\n");
        //tao node p
        NODE *p = new NODE;
        //dua du lieu vua nhap vao node p
        p = TaoNode(x);
        //dua node p vao ham them cuoi va truyen vao node p vua tao
        ThemCuoi(ds,p);
    }
}
void Xuat(DLIST ds){
    //khoi tao mot node
    NODE *p = new NODE;
    //duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
    for(p = ds.pHead; p!= NULL; p=p->next){
        //hien thi du lieu cua tung hoc vien
        printf("%d\t %s\t %s\t %s\t %f\t \n", p->data.mhv, p->data.tenHV, p->data.lop, p->data.chuyenNganh, p->data.diemTK);
    }
}
void LietKe(DLIST ds){
    //khoi tao mot node
    NODE *p = new NODE;
    //duyet tu dau danh sach den cuoi danh sach voi dieu kien p!=NULL
    for(p = ds.pHead; p!= NULL; p=p->next){
        //so sanh hoc vien thuoc nganh Thuong Mai Dien Tu
        if(strcmp(p->data.chuyenNganh,"Thuong Mai Dien Tu") == 0){
            //neu diem tong ket cua hoc vien >= 8
            if(p->data.diemTK >= 8){
                //hien thi du lieu cua tung hoc vien
                printf("%d\t %s\t %s\t %s\t %f\t \n", p->data.mhv, p->data.tenHV, p->data.lop, p->data.chuyenNganh, p->data.diemTK);
            }
        }
        
    }
}
NODE* TimKiem(DLIST ds, int mhv){
    //tao node p
    NODE *p;
    //gan p bang phan tu dau danh sach
    p = ds.pHead;
    //su dung vong lap
    while ((p!=NULL) && (p->data.mhv!=mhv)){
        p=p->next;
    }
    //tra ve ket qua, neu NULL thi khong tim thay
    return p;
}
void XoaDau(DLIST &ds){
    //gan p bang phan tu dau danh sach
    NODE *p = ds.pHead;
    //thuc hien gan lai phan tu dau danh sach
    ds.pHead = ds.pHead->next;
    ds.pHead->prev = NULL;
    //neu khong ton tai phan tu dau danh sach
    if (ds.pHead==NULL){
        ds.pTail = NULL;
    }
    //thay doi con tro next ve NULL
    p->next = NULL;
    //xoa node p duoc gan bang phan tu dau danh sach
    delete p;
}
void XoaCuoi (DLIST &ds){
    //tao node p va gan bang phan tu cuoi danh sach
    NODE *p = ds.pTail;
    //thuc hien gan lai phan tu cuoi danh sach
    ds.pTail = ds.pTail->prev;
    ds.pTail->next = NULL;
    //kiem tra phan tu cuoi neu rong
    if (ds.pTail==NULL){
        ds.pHead = NULL;
    }
    //thay doi con tro prev cua node p ve NULL
    p->prev = NULL;
    //xoa p duoc gan bang phan tu cuoi danh sach
    delete p;
}
void XoaTheoKhoaK(DLIST &ds, int mhv){
    //tim kiem theo du lieu x va gan vao node p
    NODE *p = TimKiem(ds, mhv);
    //neu tim thay ket qua
    if(p != NULL){
        //neu p->prev == NULL thuc hien xoa dau
        if (p->prev==NULL){
            XoaDau(ds);
            return;
        }
        //neu p->next == NULL thuc hien xoa cuoi
        if (p->next==NULL){
            XoaCuoi(ds);
            return;
        }
        //thay doi lai lien ket cua phan tu co khoa K can xoa
        p->prev->next = p->next;
        p->next->prev = p->prev;
        //gan con tro prev va next cua phan tu co khoa K can xoa ve null
        p->prev = NULL; 
        p->next = NULL;
        //xoa node p co phan tu la khoa k
        delete p;
    }
}
int main(){
    //khai bao mot danh sach lien ket doi
    DLIST ds;
    //nhap n phan tu 
    int n;
    printf("NHAP N: ");
    scanf("%d",&n);
    //khoi tao danh sach
    KhoiTao(ds);
    //goi ham nhap tryuyen vao danh sach va N phan tu
    Nhap(ds,n);
    //goi ham xuat cac du lieu co trong danh sach
    printf("DANH SACH HOC VIEN VUA NHAP\n");
    Xuat(ds);
    printf("\nDANH SACH HOC VIEN NGANH THUONG MAI DIEN TU VA DIEM TONG KET >= 8\n");
    LietKe(ds);
    //Xoa theo ma hoc vien
    int mhv;
    printf("\nNHAP MA HOC VIEN: "); 
    scanf("%d",&mhv);
    //goi ham xoa theo khoa k voi k = mhv
    XoaTheoKhoaK(ds,mhv);
    printf("\nDANH SACH SAU KHI XOA THEO MA HOC VIEN %d\n",mhv);
    Xuat(ds);
}

mtoplist