[Danh sách liên kết đôi] - Nhập, xóa, sắp xếp nhân viên trong C/C++

Thuật toán nhập, xóa, sắp xếp trong danh sách liên kêt đôi C/C++

Thông tin về nhân viên gồm: mã số nhân viên (MaNV - kiểu nguyên), họ tên (HoTen - kiểu xâu kí tự), ngày sinh (NS - kiểu xâu kí tự), tổng lương (TL - kiểu thực).
Thực hiện các yêu cầu sau (bằng ngôn ngữ lập trình C):
Khai báo cấu trúc dữ liệu (dạng con trỏ) của danh sách liên kết đôi để quản lý danh sách nhân viên (Kiểu danh sách là ListNV lưu các nhân viên có kiểu là NV).
  • Viết hàm thêm một nhân viên vào đầu danh sách liên kết đôi trên.
  • Viết hàm tính tổng lương của tất cả các nhân viên trong danh sách. 
  • Viết hàm hủy nhân viên cuối cùng ra khỏi danh sách
  • Viết hàm tìm nhân viên có mức lương cao nhất
  • Viết hàm in ra danh sách Nhân viên có mức lương trên 2000000
  • Sắp xếp danh sách theo thứ tự tăng dần của MaNV
Với liên kết đôi thì cũng khá giống với liên kết đơn, khác nhau là ở chỗ nó có thêm node trở về (prev).
Với những yêu cầu của bài toán, mình sẽ trình bày chi tiết các yêu cầu:

Nhập một nhân viên vào đầu danh sách

  • Bước 1: Tạo một struct để lưu trữ thông tin của nhân viên, sau đó tạo hàm init và khai báo node có giá trị rỗng(NULL)
typedef struct nhanVien
{
int maNV;
char hoTen[30], ngaySinh[15];
float tongLuong;
} NV;
typedef struct NODE {
NV x;
NODE *next ;
NODE *prev ;
} node, *head, *tail;
void init(node *&head, node *&tail)
{
head = NULL;
tail = NULL;
}
  • Bước 2: Tạo ra một node mới, cấp phát bộ nhớ cho node bằng hàm malloc(ngoài ra có thể sử dụng new new_node() thay cho malloc).
node *createNode()
{
node *new_node = (node*)malloc(sizeof(node));
printf("\nNhap vao ten: ");
fflush(stdin);
scanf("%[^\n]s", &new_node->x.hoTen);
printf("Nhap ma nhan vien: ");
scanf("%d", &new_node->x.maNV);
printf("Nhap ngay sinh: ");
scanf("%s", &new_node->x.ngaySinh);
printf("Nhap tong luong nhan vien: ");
scanf("%f", &new_node->x.tongLuong);
new_node->prev = NULL;
new_node->next = NULL;
return new_node;
}
  • Bước 3: Tạo ra hàm nhập vào đầu danh sách nhân viên:
void addHead(node *&head, node *&tail)
{
node *add_node = createNode();
if(head == NULL)
{
head = add_node;
tail = head;
}
else
{
add_node->next = head;
head->prev = add_node;
head = add_node;
}
}
  • Bước 4: Nhập n nhân viên từ bàn phím vào danh sách liên kết đôi
void nhapNV(node *&head, node *&tail)
{
int n;
init(head, tail);
do
{
printf("\nNhap vao so luong nhan vien: ");
scanf("%d", &n);
}
while(n<=0);
for(int i=0; i<n; i++)
{
printf("Nhap vao nhan vien thu: %d",i+1);
addHead(head, tail);
}
}

Xuất danh sách đã nhập

Ta in từ node head trở đi về sau, kiểm tra điều kiện node đó không == NULL là được. Mình dùng cú pháp printf của C để in ra.
  • Chú ý: Bạn cũng có thể in từ node tail, và dùng node *prev đề in ngược về
void xuatDS(node *head, node *tail)
{
node *p = head;
printf("%20s%15s%15s%18s\n", "Ho ten", "Ma NV", "ngay sinh", "Tong luong");
// den cuoi danh sach thi p->next ==NULL, do do check p!=NULL la duoc
while (p != NULL)
{
printf("%20s%15d%15s%18.2f\n", p->x.hoTen, p->x.maNV, p->x.ngaySinh, p->x.tongLuong);
p = p->next;
}
}

 Tổng lương của tất cả nhân viên

Tổng lương của các nhân viên là tổng từ tổng lương của các nhân viên :))
float tongLuong(node *head, node *tail)
{
node *p = head;
float S;
S=0;
while(p!=NULL)
{
S+= p->x.tongLuong;
p=p->next;
}
return S; // dung return de tra tri cho ham
}

Nhân viên có lương cao nhất?

So sánh lương của từng nhân viên với nhau để tìm ra nhân viên có lương cao nhất
float luongNV(node *head, node *tail)
{
float max;
max = head->x.tongLuong;
node *p = head;
while(p!=NULL)
{
if(max<p->x.tongLuong)
{
max = p->x.tongLuong;
}
p=p->next;
}
return max;
}

Nhân viên có lương trên 2000000

Kiểm tra nhân viên có lương trên 2000000 và in ngay trong hàm luôn, hoặc bạn có thể tạo ra node trung gian để lưu danh sách rồi dùng hàm xuatDS(head, tail)
void luong20(node *head, node *tail)
{
node *p, *q;
p = head;
q= head;
q=NULL;
printf("\nDanh sach nhan vien luong tren 2000000\n");
printf("%20s%15s%15s%18s\n", "Ho ten", "Ma NV", "ngay sinh", "Tong luong");
while(p!=NULL)
{
if(p->x.tongLuong >2000000)
{
printf("%20s%15d%15s%18.2f\n", p->x.hoTen, p->v.maNV, p->x.ngaySinh, p->x.tongLuong);
}
p=p->next;
}
}

Xóa Node cuối cùng của danh sách liên kết đôi

Đơn giản là xóa đi tail và cập nhật lại tail về vị trí node trước đó
void delTail(node *&head, node *&tail)
{
if(tail !=NULL)
{
node *p;
p = tail;
tail =tail->prev;
tail->next = NULL;
free(p);
if(head == NULL)
tail = NULL;
}
}

Sắp xếp lại DS nhân viên theo mã nhân viên

Sử dụng thuật toán bubbeSort để sắp xếp lại danh sách. Bạn cũng có thể sử dụng quickSort, MegaSort để sắp xếp.
void sapXep(node *&head, node *&tail)
{
node *p, *q;
p = head;
while(p!=NULL)
{
q = p->next;
while(q!=NULL)
{
if(p->x.maNV>q->x.maNV)
{
NV tg =p->x;
p->x=q->x;
q->x = tg;
}
q=q->next;
}
p= p->next;
}

Cuối cùng, đưa tất cả vào hàm main() và chạy.

Code đầy đủ

#include <cstdio>
#include <cstdlib>
#include <algorithm>
typedef struct nhanVien
{
    int maNV;
    char hoTen[30], ngaySinh[15];
    float tongLuong;
} NV;
typedef struct NODE {
    NV x;
    NODE *next ;
    NODE *prev  ;
} node, *head, *tail;
void init(node *&head, node *&tail)
{
    head = NULL;
    tail = NULL;
}
node *createNode()
{
    node *new_node = (node*)malloc(sizeof(node));
    printf("\nNhap vao ten: ");
    fflush(stdin);
    scanf("%[^\n]s", &new_node->x.hoTen);
    printf("Nhap ma nhan vien: ");
    scanf("%d", &new_node->x.maNV);
    printf("Nhap ngay sinh: ");
    scanf("%s", &new_node->x.ngaySinh);
    printf("Nhap tong luong nhan vien: ");
    scanf("%f", &new_node->x.tongLuong);
    new_node->prev =  NULL;
    new_node->next = NULL;
    return new_node;
}
void addHead(node *&head, node *&tail)
{
    node *add_node = createNode();
    if(head == NULL)
    {
        head = add_node;
        tail = head;
    }
    else
    {
        add_node->next = head;
        head->prev = add_node;
        head = add_node;
    }
}
void nhapNV(node *&head, node *&tail)
{
    int n;
    init(head, tail);
    do
    {
        printf("\nNhap vao so luong nhan vien: ");
        scanf("%d", &n);
    }
    while(n<=0);
    for(int i=0; i<n; i++)
    {
        printf("Nhap vao nhan vien thu: %d",i+1);
        addHead(head, tail);
    }
}
void xuatDS(node *head, node *tail)
{
    node *p = head;
    printf("%20s%15s%15s%18s\n", "Ho ten", "Ma NV", "ngay sinh", "Tong luong");
    while (p != NULL)
    {
        printf("%20s%15d%15s%18.2f\n", p->x.hoTen, p->x.maNV, p->x.ngaySinh, p->x.tongLuong);
        p = p->next;
    }
}
float tongLuong(node *head, node *tail)
{
    node *p = head;
    float S;
    S=0;
    while(p!=NULL)
    {
        S+= p->x.tongLuong;
        p=p->next;
    }
    return S;
}
float luongNV(node *head, node *tail)
{
    float max;
    max = head->x.tongLuong;
    node *p = head;
    while(p!=NULL)
    {
        if(max<p->x.tongLuong)
        {
            max = p->x.tongLuong;
        }
        p=p->next;
    }
    return max;
}
void luong20(node *head, node *tail)
{
    node *p, *q;
    p = head;
    q= head;
    q=NULL;
    printf("\nDanh sach nhan vien luong tren 2000000\n");
    printf("%20s%15s%15s%18s\n", "Ho ten", "Ma NV", "ngay sinh", "Tong luong");
    while(p!=NULL)
    {
        if(p->x.tongLuong >2000000)
        {
            printf("%20s%15d%15s%18.2f\n", p->x.hoTen, p->x.maNV, p->x.ngaySinh, p->x.tongLuong);
        }
        p=p->next;
    }
}
void delTail(node *&head, node *&tail)
{
    if(tail !=NULL)
    {
        node *p;
        p = tail;
        tail =tail->prev;
        tail->next = NULL;
        free(p);
        if(head == NULL)
            tail = NULL;
    }
}
void sapXep(node *&head, node *&tail)
{
    node *p, *q;
    p = head;
    while(p!=NULL)
    {
        q = p->next;
        while(q!=NULL)
        {
            if(p->x.maNV>q->x.maNV)
            {
                NV tg =p->x;
                p->x=q->x;
                q->x = tg;
            }
            q=q->next;
        }
        p= p->next;
    }
}
int main()
{
    node *head, *tail;
    nhapNV(head, tail);
    printf("\nDanh sach thong tin nhan vien\n");
    xuatDS(head, tail);
    float S= tongLuong(head, tail);
    printf("\nTong luong cua tat ca nhan vien la: %f", S);
    float max= luongNV(head, tail);
    printf("\nLuong nhan vien cao nhat la: %f\n",max);
    luong20(head, tail);
    sapXep(head, tail);
    printf("\nDanh sach nhan vien sap xep\n");
    xuatDS(head, tail);
    delTail(head, tail);
    printf("\nDanh sach nhan vien sau khi xoa phan tu cuoi\n");
    xuatDS(head, tail);

    return 0;
}
Để lại bình luận nếu có thắc mắc, mình sẽ trả lời bạn ngay khi mình online.
Kết quả test


COMMENTS

BLOGGER
Tên

bài viết hay,4,Bài viết khác,1,cấu trúc dữ liệu và giải thuật,3,fithou,36,ghim,4,giải tích 2,1,Hướng dẫn,5,Lập trình C,1,lập trình hướng đối tượng,3,Lập trình java,1,phần mềm,2,phần mềm lập trình,2,sách,1,tác phẩm đồ họa,3,tản mạn,4,Thiết kế web,3,thực hành lập trình cơ sở,18,thực hành lập trình hướng đối tượng,16,
ltr
item
Blog NDanh: [Danh sách liên kết đôi] - Nhập, xóa, sắp xếp nhân viên trong C/C++
[Danh sách liên kết đôi] - Nhập, xóa, sắp xếp nhân viên trong C/C++
Thuật toán nhập, xóa, sắp xếp trong danh sách liên kêt đôi C/C++
https://1.bp.blogspot.com/-ais_XXUSXnk/Xm4IyL8mh3I/AAAAAAAAdpo/t069gkFFoEE_ItTVB30gTiRpwYtAFTRkgCLcBGAsYHQ/s640/danh%2Bsach%2Blien%2Bket%2Bdoi.jpg
https://1.bp.blogspot.com/-ais_XXUSXnk/Xm4IyL8mh3I/AAAAAAAAdpo/t069gkFFoEE_ItTVB30gTiRpwYtAFTRkgCLcBGAsYHQ/s72-c/danh%2Bsach%2Blien%2Bket%2Bdoi.jpg
Blog NDanh
https://blog.ndanh.com/2020/03/danh-sach-lien-ket-doi-nhap-xoa-sap-xep.html
https://blog.ndanh.com/
https://blog.ndanh.com/
https://blog.ndanh.com/2020/03/danh-sach-lien-ket-doi-nhap-xoa-sap-xep.html
true
1596452775547375681
UTF-8
Tải tất cả bài viết Không tìm thấy bài viết nào XEM TẤT CẢ Đọc thêm Trả lời Hủy trả lời Xóa Bởi Trang chủ PAGES POSTS Xem tất cả Bài viết đề xuất CHỦ ĐỀ LƯU TRỮ SEARCH TẤT CẢ BÀI VIẾT Không tìm thấy nội dung của bạn Quay về trang chủ Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow CHIA SẺ ĐỂ XEM NỘI DUNG Bước 1: Chia sẻ lên facebook chế độ công khai Bước 2: Vào facebook, ấn vào bài đã chia sẻ công khai để hiện nội dung! Click Copy All Code Select All Code Code của bạn đã được copy Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content