单链表-实验报告二¶

功能：¶

C
void Menu() {
    printf("\n***********************************************\n");
    printf("************** 学生成绩管理系统 ***************\n");
    printf("**                                           **\n");
    printf("**       1: SListPushBack  尾插数据          **\n");
    printf("**       2: SListPushFront 头插数据          **\n");
    printf("**       3: SListPopBack   尾删数据          **\n");
    printf("**       4: SListPopFront  头删数据          **\n");
    printf("**       5: SListPrint     打印单链表        **\n");
    printf("**       6: ListInsert     插入数据          **\n");
    printf("**       7: FindFromElem   由数据查找        **\n");
    printf("**       8: FindFromIndex  由索引值查找      **\n");
    printf("**       9: SListErase     删除节点          **\n");
    printf("**      10: Combine        合并两个单链表    **\n");
    printf("**      11: ClearSList     清空单链表        **\n");
    printf("**      12: destroyList    销毁单链表(退出)  **\n");
    printf("**                                           **\n");
    printf("***********************************************\n\n");
}

代码：¶

C
/*
Name:   LinkList.cpp
Author: 侯霖钰
data: 24/03/24 15:23
Description: 单链组的一系列操作
*/


#define _CRT_SECURE_NO_WARNINGS 1

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

typedef int ElemType;
int count = 0; // 计数

// 定义单链表结点结构体
typedef struct SListNode {
    ElemType data;
    struct SListNode* next;
} LNode, * LinkList;


// 初始化单链表
void InitList(LinkList* List) {
    *List = NULL;  // 初始时链表为空，头指针为NULL
}


// 尾插法插入结点
void SListPushBack(LinkList* pphead, ElemType x) {
    LinkList newnode = (LinkList)malloc(sizeof(LNode));
    newnode->data = x;
    newnode->next = NULL;

    if (*pphead == NULL) {
        *pphead = newnode;
    }
    else {
        LinkList tail = *pphead;
        while (tail->next != NULL) {
            tail = tail->next;
        }
        tail->next = newnode;
    }

    count++;
}


// 头插法插入结点
void SListPushFront(LinkList* pphead, ElemType x) {
    LinkList newnode = (LinkList)malloc(sizeof(LNode));
    newnode->data = x;
    newnode->next = *pphead;
    *pphead = newnode;

    count++;
}


// 头删操作
void SListPopFront(LinkList* pphead) {
    if (*pphead == NULL) {
        printf("当前为空链表！\a\n");
        return;
    }
    LinkList next = (*pphead)->next;
    free(*pphead);
    *pphead = next;

    printf("删除成功！\n");
    count--;
}


// 尾删操作
void SListPopBack(LinkList* pphead) {
    if (*pphead == NULL) {
        printf("当前为空链表！\a\n");
        return;
    }
    else if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    }
    else {
        LinkList prev = NULL;
        LinkList tail = *pphead;
        while (tail->next != NULL) {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }

    printf("删除成功！\n");
    count--;
}


// 打印单链表
void SListPrint(LinkList phead) {
    LinkList cur = phead;
    int index = 1;
    while (cur != NULL) {
        printf("(第%d位):%d -->", index, cur->data);
        cur = cur->next;
        index++;
    }
    printf("NULL\n");
}


// 在index的前面插入x
void SListInsert(LinkList* phead, int index, ElemType x) {
    if (*phead == NULL) {
        printf("\n当前链表为空，默认插入首位！\n");
        SListPushFront(phead, x);
        return;
    }

    index--; // 因为链表的首元素的索引值设置为‘1’

    LinkList cur = *phead;
    int num = 1;
    while (cur != NULL && num < index) {
        cur = cur->next;
        num++;
    }

    if (cur == NULL) {
        printf("未找到指定位置\n");
        return;
    }

    LinkList newnode = (LinkList)malloc(sizeof(LNode));
    if (newnode == NULL) {
        printf("内存分配失败\a\n");
        return;
    }

    newnode->data = x;
    newnode->next = cur->next;
    cur->next = newnode;

    count++;
}


// 删除索引位置的结点
void SListErase(LinkList* phead, int index) {
    if (*phead == NULL) {
        return;
    }

    index--; // 因为设置单链表首元素的索引值为‘1’

    if (index == 0) { // 删除的元素为首元素，其实直接调用头删就行
        LinkList temp = *phead;
        *phead = (*phead)->next;
        free(temp);
        count--;
        return;
    }

    LinkList prev = *phead;
    int currIndex = 1;
    while (prev != NULL && currIndex < index) {
        prev = prev->next;
        currIndex++;
    }

    if (prev == NULL || prev->next == NULL) {
        printf("未找到指定结点\n");
        return;
    }

    LinkList pos = prev->next;
    prev->next = pos->next;
    free(pos);
    count--;
}


// 在链表中查找值为x的结点
int SListFind(LinkList phead, ElemType x) {
    LinkList cur = phead;
    int index = 0;
    while (cur != NULL) {
        if (cur->data == x) {
            return index;
        }
        cur = cur->next;
        index++;
    }

    return -1;
}


// 由索引值查找元素
void FindFromIndex(LinkList L, int index) {
    if (L == NULL || index <= 0) {
        printf("不存在第 %d 位元素\n", index);
        return;
    }

    LinkList p = L;
    int i = 0;
    index--; // 因为第一个元素的索引值设置为了‘1’

    while (p && i < index) {
        p = p->next;
        i++;
    }

    if (i == index && p) {
        //printf("第%d位元素是：%d\n", index, p->data);
        std::cout << "第" << index + 1 << "位元素是：" << p->data << std::endl;
    }
    else {
        printf("未查询到第%d位元素\n", index);
    }
}


// 检查是否为“非降序”,
bool isNotDecreasing(LinkList list) {
    if (list == NULL || list->next == NULL) {
        return true;  // 空链表或只有一个节点的链表视为非降序
    }

    LinkList cur = list;
    while (cur->next != NULL) {
        if (cur->data > cur->next->data) {
            return false;  // 出现降序，返回false
        }
        cur = cur->next;
    }

    return true;  // 遍历完链表没有出现降序，返回true
}


// 合并两个链表
LinkList Combine(LinkList La, LinkList Lb) {
    if (La == NULL) {
        return Lb;
    }
    if (Lb == NULL) {
        return La;
    }

    LinkList head = NULL;
    LinkList tail = NULL;

    LinkList curA = La;
    LinkList curB = Lb;

    if (curA->data <= curB->data) {
        head = tail = curA;
        curA = curA->next;
    }
    else {
        head = tail = curB;
        curB = curB->next;
    }

    while (curA != NULL && curB != NULL) {
        if (curA->data <= curB->data) {
            tail->next = curA;
            curA = curA->next;
        }
        else {
            tail->next = curB;
            curB = curB->next;
        }
        tail = tail->next;
    }

    // 将剩余未遍历完的链表连接到结果链表的末尾
    if (curA != NULL) {
        tail->next = curA;
    }
    else if (curB != NULL) {
        tail->next = curB;
    }

    return head;
}


// 清空单链表
void ClearSList(LinkList* phead) {
    *phead = NULL;
    count = 0;
}


// 销毁单链表
void DestroyList(LinkList* phead) {
    LinkList cur = *phead;
    while (cur != NULL) {
        LinkList next = cur->next;
        free(cur);
        cur = next;
    }
    *phead = NULL;
}


void Menu() {
    printf("\n***********************************************\n");
    printf("************** 学生成绩管理系统 ***************\n");
    printf("**                                           **\n");
    printf("**         \033[1;36;41m当前系统中有 %d 份数据！\033[m           **\n", count);
    printf("**                                           **\n");
    printf("**       1: SListPushBack  尾插数据          **\n");
    printf("**       2: SListPushFront 头插数据          **\n");
    printf("**       3: SListPopBack   尾删数据          **\n");
    printf("**       4: SListPopFront  头删数据          **\n");
    printf("**       5: SListPrint     打印单链表        **\n");
    printf("**       6: ListInsert     插入数据          **\n");
    printf("**       7: FindFromElem   由数据查找        **\n");
    printf("**       8: FindFromIndex  由索引值查找      **\n");
    printf("**       9: SListErase     删除节点          **\n");
    printf("**      10: Combine        合并两个单链表    **\n");
    printf("**      11: ClearSList     清空单链表        **\n");
    printf("**      12: destroyList    销毁单链表(退出)  **\n");
    printf("**                                           **\n");
    printf("***********************************************\n\n");
}


int main() {

    LinkList list = NULL;
    int function = 0;

    Menu();
    while (1) {
        printf("请选择你的操作：");
        scanf("%d", &function);

        switch (function) {
        case 1: {
            ElemType i = 0;
            printf("请出入要插入的数据：");
            //scanf("%d", &i);
            std::cin >> i;

            SListPushBack(&list, i);
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 2: {
            ElemType i = 0;
            printf("请出入要插入的数据：");
            //scanf("%d", &i);
            std::cin >> i;

            SListPushFront(&list, i);
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 3: {
            SListPopBack(&list);
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 4: {
            SListPopFront(&list);
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 5: {
            printf("单链表如下：\n");
            SListPrint(list);
            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 6: {
            ElemType num;
            int index;
            printf("请输入要插入的索引值 (数据将插入到索引值的前一位！！)：");
            scanf("%d", &index);

            printf("请输入要插入的数据：");
            //scanf("%d", &i);
            std::cin >> num;

            SListInsert(&list, index, num);
            printf("插入成功！\n");
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 7: {
            if (count) {
                int index;

                ElemType num;
                printf("请输入要查找的数据：");
                //scanf("%d", &num);
                std::cin >> num;

                index = SListFind(list, num);

                if (index > 0) {
                    printf("所查找的数据对应的对应索引值为：%d\n", index + 1);
                }
                else {
                    printf("当前链表中无此数据！\n");
                }
            }
            else {
                printf("当前链表无数据，请先插入数据！\n");
            }

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 8: {
            if (count) {
                int index;
                printf("请输入要查找的索引值：");
                scanf("%d", &index);
                FindFromIndex(list, index);
            }
            else {
                printf("当前链表无数据，请先插入数据！\n");
            }

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 9: {
            if (count) {
                int index = NULL;
                printf("请输入你要删除元素的索引值:");
                scanf("%d", &index);
                SListErase(&list, index);
                printf("删除成功！\n");
                SListPrint(list);
            }
            else {
                printf("当前链表无数据，请先插入数据！\n");
            }

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 10: {
            /* 
            两个线性表合并算法的实现。
            已知顺序表LA和LB中的数据元素按值非递减有序排列
            现要将LA和LB归并为一个新的顺序表LC
            且LC中的数据元素仍按值非递减有序排序。
            例如：LA＝（3,5,8,11）  LB＝（2,6,9,15,20）。
            */

            LinkList La = list;

            LinkList Lb = NULL;  // 初始化为空链表
            LinkList pB = NULL;  

            // 检查A是否合法
            if (!isNotDecreasing(La)) {
                printf("\n当前链表并非\"非递减有序排列\"！\n\n");
                break;
            }

            // 初始化单链表 Lb
            printf("请输入链表 B 的元素（输入 -1 结束）:\n");
            ElemType temp;
            std::cin >> temp;

            int countTemp = 0;

            while (temp != -1) {
                LinkList newnode = (LNode*)malloc(sizeof(LNode));
                newnode->data = temp;
                newnode->next = NULL;

                if (Lb == NULL) {
                    Lb = newnode;
                    pB = Lb; // 指向链表 Lb 的尾节点
                }
                else {
                    pB->next = newnode;
                    pB = pB->next;
                }

                std::cin >> temp;
                countTemp++;
            }

            printf("B中元素为：");
            SListPrint(Lb);
            printf("\n");

            // 检查B是否合法
            if (!isNotDecreasing(Lb)) {
                printf("\nLb 并非\"非递减有序排列\"！\n\n");
                break;
            }

            // 合并单链表 La 和 Lb 至 Lc
            LinkList Lc = Combine(La, Lb);

            count += countTemp;

            // 打印合并后的链表 Lc
            printf("合并后的链表为: \n");
            SListPrint(Lc);

            printf("-------------------------------------------\n\n\n");
            Menu();

            break;
        }

        case 11: {
            ClearSList(&list);
            printf("清空成功！\n");
            SListPrint(list);

            printf("-------------------------------------------\n\n\n");
            Menu();
            break;
        }

        case 12: {
            DestroyList(&list);
            exit(0);
        }

        default:
            printf("输入有误，请重新输入\a\n");
            break;
        }
    }

    return 0;
}