C语言基础 —— 链表

今日一言：
You have to decide whether to trust your own eyes and ears, or what other people say.
你需要决定是相信自己的眼睛和耳朵，还是相信别人的话。

C语言基础 —— 链表

实验目的：

1. 理解单向链表的基本概念。
2. 掌握线性表的建立、访问、插入和删除基本操作。

实验内容

(1) 编写一个程序，采用标头插入或表尾插入的方法建立一个10个学生的链表。每个学生的信息包括：学号、姓名和多科成绩和总分。

C语言程序

#include <stdio.h>
#include <stdlib.h>

/************************************************
 * 链表需要
 ************************************************/

enum subjects
{
    CHINESE = 0,
    MATHEMASTICS,
    ENGLISH
};

typedef struct Elem {
    long stuId;
    char stuName[50];
    float scores[3];
    float scoSum;
    struct Elem* prev, * next;
}Elem;

struct {
    Elem elems[200];
    int size;
} Elems; // 全部的链表数据存储在这里 （ 不销毁, 但会覆盖 ） 

// 定义链表结构
typedef struct {
    struct Elem* first;
    struct Elem* last;
    int size;
} LinkList;

// 初始化链表
void initLinkList(LinkList* list) {
    list->size = 0;
}

// 获取表长 
int getSizeL(LinkList* list) {
    return list->size;
}

void addFirst(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->first = elem;
    }
    list->size++;
}

// 添加元素 
void addLast(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->last = elem;
    }
    list->size++;
}

Elem* getElem(LinkList* list, int index) {
    int i;
    Elem* elem;
    // 逐项访问 
    if (index > list->size / 2) {
        elem = list->last;
        for (i = list->size - 1; i >= index; i--) {
            if (i == index) {
                return elem;
            }
            elem = elem->prev;
        }
    }
    else {
        elem = list->first;
        for (i = 0; i <= index; i++) {
            if (i == index) {
                return elem;
            }
            elem = elem->next;
        }
    }
}

// 移除元素 
void removeIndexL(LinkList* list, int index) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i <= index; i++) {
        if (i == index) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

void removeElemL(LinkList* list, Elem* e) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i < list->size; i++) {
        if (elem == e) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

/************************************************
 * 链表需要
 ************************************************/

Elem * createElem() {
    Elem* p = &Elems.elems[Elems.size];
    Elems.size++;
    if (Elems.size >= 200) {
        printf("超出容量范围，即将退出程序.\n");
        exit(1);
    }
    return p;
}

void show() {
    int num = 10; // 学生人数

    int i,j;

    Elems.size = 0; // 初始化容器
    srand(time(NULL)); // 做种
    LinkList list; // 链表变量
    initLinkList(&list); // 初始化链表
    for (i = 0; i < 10; i++) {
        Elem* elem = createElem();
        // printf("请输入第%d位同学的学号：",i+1);
        // scanf_s("%ld", &elem->stuId);
        printf("生成第%d位同学的学号\n", i + 1);
        elem->stuId = rand() % 1000 + 30;
        printf("请输入第%d位同学的姓名：",i+1);
        scanf_s("%s", elem->stuName, 50);
        elem->scoSum = 0;
        for (j = 0; j < 3; j++) {
            switch (j) {
                case CHINESE:
                    printf("生成第%d位同学的语文成绩\n", i + 1);
                    // printf("请输入第%d位同学的语文成绩：", i + 1);
                    break;
                case ENGLISH:
                    printf("生成第%d位同学的英语成绩\n", i + 1);
                    // printf("请输入第%d位同学的英语成绩：", i + 1);
                    break;
                case MATHEMASTICS:
                    printf("生成第%d位同学的数学成绩\n", i + 1);
                    // printf("请输入第%d位同学的数学成绩：", i + 1);
                    break;
                default:
                    printf("超出成绩数组范围，即将退出程序.\n");
                    exit(1);
                    break;
            }
            // scanf_s("%f", &elem->scores[j]);
            elem->scores[j] = rand() % 120 + 30;
            elem->scoSum += elem->scores[j];
        }
        addLast(&list, elem);
    }
    printf("----------------------\n");
    printf("正在输出链表数据：\n");
    printf("\tid\t\tname\tChinese \tMathematics\tEnglish \tSumScore\t\n");
    Elem* p = list.first;
    for (i = 0; i < list.size; i++) {
        printf("%010ld\t%8s\t%7.1f\t%11.1f\t%7.1f\t\t%8.1f\t\n", p->stuId, p->stuName, p->scores[0], p->scores[1], p->scores[2], p->scoSum);
        p = p->next;
    }
}

void main() {
    int n;
    while (1) {
        show();
        printf("0. 退出程序\t1. 重新开始\n");
        printf("---------------------------\n");
        scanf_s("%d", &n);
        fflush(stdin);
        if (n) {
            system("cls");
        }
        else {
            exit(0);
        }
    }
}

运行结果

生成第3位同学的英语成绩
生成第4位同学的学号
请输入第4位同学的姓名：QQQ
生成第4位同学的语文成绩
生成第4位同学的数学成绩
生成第4位同学的英语成绩
生成第5位同学的学号
请输入第5位同学的姓名：III
生成第5位同学的语文成绩
生成第5位同学的数学成绩
生成第5位同学的英语成绩
生成第6位同学的学号
请输入第6位同学的姓名：OOO
生成第6位同学的语文成绩
生成第6位同学的数学成绩
生成第6位同学的英语成绩
生成第7位同学的学号
请输入第7位同学的姓名：MMM
生成第7位同学的语文成绩
生成第7位同学的数学成绩
生成第7位同学的英语成绩
生成第8位同学的学号
请输入第8位同学的姓名：SSS
生成第8位同学的语文成绩
生成第8位同学的数学成绩
生成第8位同学的英语成绩
生成第9位同学的学号
请输入第9位同学的姓名：DDD
生成第9位同学的语文成绩
生成第9位同学的数学成绩
生成第9位同学的英语成绩
生成第10位同学的学号
请输入第10位同学的姓名：FFF
生成第10位同学的语文成绩
生成第10位同学的数学成绩
生成第10位同学的英语成绩
----------------------
正在输出链表数据：
        id           name        Chinese     Mathematics  English         SumScore
0000000704           RCK          109.0        78.0        84.0            271.0
0000000056           LLL           60.0       113.0        82.0            255.0
0000000873           AAA          147.0       115.0       130.0            392.0
0000000867           QQQ           46.0        91.0       140.0            277.0
0000000629           III           67.0        61.0       111.0            239.0
0000000617           OOO           61.0       147.0       110.0            318.0
0000000308           MMM           47.0       144.0       115.0            306.0
0000000946           SSS          139.0        65.0        37.0            241.0
0000000154           DDD           43.0       133.0       102.0            278.0
0000000765           FFF           88.0        47.0        80.0            215.0
0. 退出程序     1. 重新开始
---------------------------

（2） 分别编写一个函数，建立n个整数节点的单向链表list，统计list表种的节点数、输出list表中的数据、在表中指定位置之后插入一个整数节点、在表中指定位置之前删除一个整数节点。编写一主函数调用上述函数测试其功能。

C语言程序

#include <stdio.h>
#include <stdlib.h>

/*********************************************************************************
 * 链表需要
 ********************************************************************************/

enum subjects
{
    CHINESE = 0,
    MATHEMASTICS,
    ENGLISH
};

typedef struct Elem {
    int num;
    struct Elem* prev, * next;
}Elem;

struct {
    Elem elems[200];
    int size;
} Elems; // 全部的链表数据存储在这里 （ 不销毁, 但会覆盖 ） 

// 定义链表结构
typedef struct {
    struct Elem* first;
    struct Elem* last;
    int size;
} LinkList;

// 初始化链表
void initLinkList(LinkList* list) {
    list->size = 0;
}

// 获取表长 
int getSizeL(LinkList* list) {
    return list->size;
}

Elem* getElem(LinkList* list, int index) {
    int i;
    Elem* elem;
    // 逐项访问 
    if (index > list->size / 2) {
        elem = list->last;
        for (i = list->size - 1; i >= index; i--) {
            if (i == index) {
                return elem;
            }
            elem = elem->prev;
        }
    }
    else {
        elem = list->first;
        for (i = 0; i <= index; i++) {
            if (i == index) {
                return elem;
            }
            elem = elem->next;
        }
    }
    return NULL;
}

void addFirst(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->first = elem;
    }
    list->size++;
}

// 添加元素 
void addLast(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->last = elem;
    }
    list->size++;
}

void addAfter(LinkList* list, Elem* elem, int index) {
    if (index < 0 || index >= list->size) return;
    if (index == list->size - 1 || !getSizeL(list) ) {
        addLast(list, elem);
        return;
    }
    Elem* p = getElem(list, index);
    printf("%d\n", p->num);
    if (p == NULL) exit(1);
    elem->next = p->next;
    elem->prev = p;
    p->next->prev = elem;
    p->next = elem;
    list->size++;
}

void addBefore(LinkList* list, Elem* elem, int index) {
    if (index < 0 || index >= list->size) return;
    if (index == 0 || !getSizeL(list)) {
        addFirst(list, elem);
        return;
    }
    Elem* p = getElem(list, index);
    printf("%d\n", p->num);
    elem->next = p;
    p->prev->next = elem;
    elem->prev = p->prev;
    p->prev = elem;
    list->size++;
}

// 移除元素 
void removeIndexL(LinkList* list, int index) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i <= index; i++) {
        if (i == index) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

void removeElemL(LinkList* list, Elem* e) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i < list->size; i++) {
        if (elem == e) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

/*********************************************************************************
 * 链表需要
 ********************************************************************************/

Elem * createElem() {
    Elem* p = &Elems.elems[Elems.size];
    Elems.size++;
    if (Elems.size >= 200) {
        printf("超出容量范围，即将退出程序.\n");
        exit(1);
    }
    return p;
}

void main() {
    Elem* p = NULL;
    int i, n, f;
    int size = 10;
    srand(time(NULL));// 随机种
    LinkList list;
    initLinkList(&list); // 初始化链表
    Elems.size = 0; // 初始化容器
    printf("链表数据：\n---------------------\n");
    for (i = 0; i < size; i++) {
        p = createElem();
        p->num = rand() % 100;
        addLast(&list, p);
        printf("第%d个 --> num: %d\n",i,p->num);
    }
    printf("---------------------\n");
    printf("链表节点数：%d\n", list.size);
    printf("请输入要插入的整数：");
    scanf_s("%d", &n);
    printf("请输入要插入的坐标：");
    scanf_s("%d", &i);
    printf("在%d处之后插入...\n",i);
    p = createElem();
    p->num = n;
    addAfter(&list, p, i);
    printf("链表数据：\n---------------------\n");
    p = list.first;
    for (i = 0; i < list.size; i++) {
        printf("第%d个 --> num: %d\n", i, p->num);
        p = p->next;
    }
    printf("请输入要插入的整数：");
    scanf_s("%d", &n);
    printf("请输入要插入的坐标：");
    scanf_s("%d", &i);
    printf("在%d处之前插入...\n",i);
    p = createElem();
    p->num = n;
    addBefore(&list, p, i);
    printf("链表数据：\n---------------------\n");
    p = list.first;
    for (i = 0; i < list.size; i++) {
        printf("第%d个 --> num: %d\n", i, p->num);
        p = p->next;
    }
}

运行结果

链表数据：
---------------------
第0个 --> num: 91
第1个 --> num: 63
第2个 --> num: 58
第3个 --> num: 63
第4个 --> num: 99
第5个 --> num: 32
第6个 --> num: 2
第7个 --> num: 73
第8个 --> num: 99
第9个 --> num: 15
---------------------
链表节点数：10
请输入要插入的整数：6
请输入要插入的坐标：2
在2处之后插入...
58
链表数据：
---------------------
第0个 --> num: 91
第1个 --> num: 63
第2个 --> num: 58
第3个 --> num: 6
第4个 --> num: 63
第5个 --> num: 99
第6个 --> num: 32
第7个 --> num: 2
第8个 --> num: 73
第9个 --> num: 99
第10个 --> num: 15
请输入要插入的整数：55
请输入要插入的坐标：7
在7处之前插入...
2
链表数据：
---------------------
第0个 --> num: 91
第1个 --> num: 63
第2个 --> num: 58
第3个 --> num: 6
第4个 --> num: 63
第5个 --> num: 99
第6个 --> num: 32
第7个 --> num: 55
第8个 --> num: 2
第9个 --> num: 73
第10个 --> num: 99
第11个 --> num: 15

(3) 用数组构造一个线性链表，事得数据的第一个元素的指针指向数组的第2个元素，… ，第i个元素的指针指向第i+1个元素，二数组的最后一个元素的指针为空。这样就使得数组元素变成了线性链表的结点，从而构造了一个线性链表。请输入一批整数，构造一个线性表，并访问该链表，输出链表中每个元素的值。

C语言程序

#include <stdio.h>
#include <stdlib.h>

/*********************************************************************************
 * 链表需要
 ********************************************************************************/

enum subjects
{
    CHINESE = 0,
    MATHEMASTICS,
    ENGLISH
};

typedef struct Elem {
    int num;
    struct Elem* prev, * next;
}Elem;

struct {
    Elem elems[200];
    int size;
} Elems; // 全部的链表数据存储在这里 （ 不销毁, 但会覆盖 ） 

// 定义链表结构
typedef struct {
    struct Elem* first;
    struct Elem* last;
    int size;
} LinkList;

// 初始化链表
void initLinkList(LinkList* list) {
    list->size = 0;
}

// 获取表长 
int getSizeL(LinkList* list) {
    return list->size;
}

Elem* getElem(LinkList* list, int index) {
    int i;
    Elem* elem;
    // 逐项访问 
    if (index > list->size / 2) {
        elem = list->last;
        for (i = list->size - 1; i >= index; i--) {
            if (i == index) {
                return elem;
            }
            elem = elem->prev;
        }
    }
    else {
        elem = list->first;
        for (i = 0; i <= index; i++) {
            if (i == index) {
                return elem;
            }
            elem = elem->next;
        }
    }
    return NULL;
}

void addFirst(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->first = elem;
    }
    list->size++;
}

// 添加元素 
void addLast(LinkList* list, Elem* elem) {
    if (!getSizeL(list)) {
        list->first = elem;
        list->last = elem;
    }
    else {
        elem->prev = list->last;
        elem->next = list->first;
        list->last->next = elem;
        list->first->prev = elem;
        list->last = elem;
    }
    list->size++;
}

void addAfter(LinkList* list, Elem* elem, int index) {
    if (index < 0 || index >= list->size) return;
    if (index == list->size - 1 || !getSizeL(list) ) {
        addLast(list, elem);
        return;
    }
    Elem* p = getElem(list, index);
    printf("%d\n", p->num);
    if (p == NULL) exit(1);
    elem->next = p->next;
    elem->prev = p;
    p->next->prev = elem;
    p->next = elem;
    list->size++;
}

void addBefore(LinkList* list, Elem* elem, int index) {
    if (index < 0 || index >= list->size) return;
    if (index == 0 || !getSizeL(list)) {
        addFirst(list, elem);
        return;
    }
    Elem* p = getElem(list, index);
    printf("%d\n", p->num);
    elem->next = p;
    p->prev->next = elem;
    elem->prev = p->prev;
    p->prev = elem;
    list->size++;
}

// 移除元素 
void removeIndexL(LinkList* list, int index) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i <= index; i++) {
        if (i == index) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

void removeElemL(LinkList* list, Elem* e) {
    int i;
    Elem* elem = list->first;
    int flag = 0;
    for (i = 0; i < list->size; i++) {
        if (elem == e) {
            elem->prev->next = elem->next;
            elem->next->prev = elem->prev;
            if (list->first == elem) {
                list->first = elem->next;
            }
            if (list->last == elem) {
                list->last = elem->prev;
            }
            flag = 1;
        }
        elem = elem->next;
    }
    if (!flag) printf("没能完成任务！！！\n");
    list->size--;
}

/*********************************************************************************
 * 链表需要
 ********************************************************************************/

Elem * createElem() {
    Elem* p = &Elems.elems[Elems.size];
    Elems.size++;
    if (Elems.size >= 200) {
        printf("超出容量范围，即将退出程序.\n");
        exit(1);
    }
    return p;
}

void main() {
    Elem* p = NULL;
    int i, n;
    int size = 10;
    LinkList list;
    initLinkList(&list);
    printf("请输入整数的数量：");
    scanf_s("%d", &n);
    for (i = 0; i < n; i++) {
        printf("第%d个整数：", i + 1);
        p = createElem();
        scanf_s("%d", &p->num);
        addLast(&list, p);
    }
    p = list.first;
    for (i = 0; i < list.size; i++) {
        printf("第%2d个数据 --> num : %d\n", i, p->num);
        p = p->next;
    }
}

运行结果

请输入整数的数量：5
第1个整数：2
第2个整数：3
第3个整数：55
第4个整数：666
第5个整数：11
第 0个数据 --> num : 2
第 1个数据 --> num : 3
第 2个数据 --> num : 55
第 3个数据 --> num : 666
第 4个数据 --> num : 11