链表作业

作业如下：（这是一个学生信息管理系统，主要考察对链表的相关操作，根据下面给出的代码将相应的函数补全）

题目：

//将下面程序书写完整。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N1 5
#define N2 3

struct student {
    int num;
    char name[10];
    float score;
};

int main() {
    //输入学生信息到数组，n为学生个数
    void input(struct student stu[], int n);

    //将数组中n个学生信息的建立一个单链表
    struct student* create(struct student stu[], int n);

    //将数组中n个学生按照成绩排序，期中by是'U'升序，是'D 降序
    void sort(struct student stu[], int n, char by);

    //按照by为'U'升序，'D降序，合并两个单链表成一个单链表，返回合并后链表的头指针
    struct student* combine(struct student* h1, struct student* h2, char by);

    //输出单链表中学生信息，要求每行一个学生信息:学号 姓名 成绩
    void print(struct student* h);

    //链表中删除stu结点
    void delete(struct student* h, struct student stu);

    struct student stul[N1];
    struct student stu2[N2];
    struct student *h,*h1,*h2;

    input(stu1,N1);
    input(stu2,N2);

    sort(stul, N1, 'U');
    sort(stu2, N2, 'D');

    h1 = create(stu1, N1);
    h2 = create(stu2, N2);
    h = combine(h1, h2, 'D');

    print(h);
    delete(h, stu1[1]);
    print(h);

    return 0;

}
//由此向下完成main函数中调用的函数

答案：

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h> // 输入输出函数
#include <stdlib.h> // 动态内存分配
#include <string.h> // 字符串处理函数

// 使用宏定义定义了两个常量N1和N2，分别表示两个学生数组的大小
#define N1 5
#define N2 3

// 函数声明
void input(struct student stu[], int n);
void sort(struct student stu[], int n, char by);
struct student* create(struct student stu[], int n);
struct student* combine(struct student* h1, struct student* h2, char by);
void print(struct student* h);
void delete(struct student* h, struct student stu);

// 定义学生结构体
struct student {
    int num;
    char name[10];
    float score;
    struct student* next;
    // 指向下一个学生结构体的指针next
};

int main() {
    struct student stu1[N1];
    struct student stu2[N2];
    struct student* h, * h1, * h2;
    // *h1 和 *h2 分别是两个数组构成单链表之后的头指针
    // *h 是两个单链表合并为一个单链表之后的头指针

    input(stu1, N1);
    printf("\n");
    input(stu2, N2);

    sort(stu1, N1, 'U');
    sort(stu2, N2, 'D');

    h1 = create(stu1, N1);
    h2 = create(stu2, N2);
    h = combine(h1, h2, 'D');

    printf("合并后的链表：\n");
    print(h);

    delete(h, stu1[1]);

    printf("删除节点后的链表：\n");
    print(h);

    return 0;
}

// 输入学生信息到数组，n为学生个数
void input(struct student stu[], int n) {
    printf("请输入学生信息：\n");
    for (int i = 0; i < n; i++) {
        printf("学号：");
        scanf("%d", &stu[i].num);
        printf("姓名：");
        scanf("%s", stu[i].name);
        printf("成绩：");
        scanf("%f", &stu[i].score);

        printf("\n");
    }
}

// 将数组中n个学生按照成绩排序，by是'U'升序，是'D'降序
void sort(struct student stu[], int n, char by) {
    // 使用冒泡排序，可以根据需要替换成其他排序算法
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if ((by == 'U' && stu[j].score > stu[j + 1].score) ||
                (by == 'D' && stu[j].score < stu[j + 1].score)) {
                // 交换学生信息
                struct student temp = stu[j];
                stu[j] = stu[j + 1];
                stu[j + 1] = temp;
            }
        }
    }
}

// 将数组中n个学生信息的建立一个单链表
// 接受一个包含学生结构体的数组 stu[] 和整数 n 作为输入
// 为每个学生动态分配内存，将数组中的信息复制到新的节点中，并通过指针连接这些节点以创建链表
// 返回链表的头指针
struct student* create(struct student stu[], int n) {
    struct student* head = NULL; // 头指针初始化为空
    struct student* tail = NULL; // 初始化尾指针为NULL
    // 这儿如果不将尾指针初始化为NULL，DevC++能直接编译，但是Visual Studio 2022会编译失败
    // 这儿的尾指针用于跟踪链表的尾部，而在链表开始时，尚未有任何节点，因此尾指针应该为NULL
    // 最好将指针在声明时初始化为NULL，特别是在它们用于跟踪链表等数据结构的情况下
    struct student* temp;

    for (int i = 0; i < n; i++) {
        temp = (struct student*)malloc(sizeof(struct student)); // 为新节点分配内存
        if (temp == NULL) {
            printf("内存分配失败\n");
            exit(1);
            //这里的exit()操作可以删除，它更像是一种应急操作
            //不止这里，代码中所有的exif都可以删除
        }

        // 将数组中的学生信息复制到新节点
        temp->num = stu[i].num;
        strcpy(temp->name, stu[i].name);
        temp->score = stu[i].score;
        temp->next = NULL;

        if (head == NULL) {
            head = temp; // 如果是第一个节点，直接作为头节点
        }
        else {
            tail->next = temp; // 否则加入到链表的尾部
        }

        tail = temp; // 更新尾指针

        tail->next = NULL; //将最后一个指针中的next指向为空
        //一般来说最好有这么一个步骤，但是这里其实已经不需要了
        //因为上边已经 temp->next = NULL;然后 tail = temp;了
    }

    return head; // 返回头指针
}

// 合并两个单链表成一个单链表，返回合并后链表的头指针
// 接受两个链表的头指针head1和head2作为参数
// 首先判断head1和head2是否为空，如果其中一个为空，直接返回另一个链表的头指针
// 然后，根据学生成绩的大小，将head1和head2中的节点逐个连接起来，形成一个新的链表
// 最后，返回新链表的头指针
struct student* combine(struct student* h1, struct student* h2, char by) {
    struct student* merged_head = h1;
    struct student* tail = NULL; // 初始化尾指针为NULL
    struct student* temp_1 = (struct student*)malloc(sizeof(struct student));
    struct student* head_temp1;
    struct student* head_temp2;


    for (int i = 0; i < N1-1; i++) {
        h1 = h1->next;
    }
    h1 -> next = h2;

    //如果链表为空直接返回
    if (merged_head == NULL) {
        return merged_head;
    }

    for (int i = 0; i < N1 + N2 - 1; i++) {

        //线性表的排序,采用冒泡排序,直接遍历链表
        //用于变量链表
        head_temp1 = merged_head;
        head_temp2 = head_temp1->next;

        for (int j = 0; j < N1 + N2 - i - 1; j++) {

            if (head_temp2 != NULL) {
                //如果前面那个的score比后面那个的score大，就交换它们之间的数据域
                if ((by == 'D' && head_temp1->score >= head_temp2->score) 
                    || (by == 'U' && head_temp1->score <= head_temp2->score)) {

                    temp_1->num = head_temp1->num;
                    strcpy(temp_1->name, head_temp1->name);
                    temp_1->score = head_temp1->score;

                    head_temp1->num = head_temp2->num;
                    strcpy(head_temp1->name, head_temp2->name);
                    head_temp1->score = head_temp2->score;

                    head_temp2->num = temp_1->num;
                    strcpy(head_temp2->name, temp_1->name);
                    head_temp2->score = temp_1->score;
                }
                head_temp1 = head_temp1->next;
                head_temp2 = head_temp1->next;
            }
        }

        head_temp1 = NULL;
        head_temp2 = NULL;
    }

    free(head_temp1);
    free(head_temp2);

    return merged_head;
}

// 输出单链表中学生信息，每行一个学生信息:学号 姓名 成绩
void print(struct student* h) {
    printf("学号\t姓名\t成绩\n");
    while (h != NULL) {
        printf("%d\t%s\t%.2f\n", h->num, h->name, h->score);
        h = h->next;
    }
    printf("\n");
}

// 链表中删除stu结点
// 接受一个链表的头指针head和一个学号num作为参数
// 通过遍历链表找到要删除的节点，并更新链表的指针连接
// 最后，释放被删除节点的内存，并返回链表的头指针
void delete(struct student* h, struct student stu) {
    struct student* prev = NULL;
    struct student* current = h;

    // 寻找待删除节点的位置
    while (current != NULL && current->num != stu.num) {
        prev = current;
        current = current->next;
    }

    // 删除节点
    if (current != NULL) {
        if (prev == NULL) {
            // 如果是头节点
            h = current->next;
        }
        else {
            prev->next = current->next;
        }
        free(current); // 释放内存
        //不释放内存会导致内存泄漏，特别是在使用动态内存分配的情况下
        //内存泄漏是指程序在运行过程中分配了一些内存空间
        //但在不再需要使用这些空间时未将其释放，导致系统无法回收这些内存
    }
    else {
        printf("未找到要删除的节点\n");
    }
}