单链表操作模拟系统(12种功能)

骑猪看日落 2023-01-22 07:51 8阅读 0赞

今晚花了一晚上写了一个功能较完善的单链表操作模拟系统, 有助于帮助初学者初始单链表的各种操作. 虽然系统已经过本人简单的测试, 但可能还存在bug, 还请各位朋友帮我一起测试这个系统, 如有问题直接在评论区留言即可, 谢谢大家!

#include<stdio.h>
    #include<stdlib.h>
    short InitLinkList(struct Node* &, struct Node* &);
    short RearInsert(struct Node* &, short);
    short IsEmpty(struct Node* &);
    void Traversal(struct Node* &);
    short GetListLength(struct Node* &);
    short GetListLength2(struct Node* &);
    short HeadInsert(struct Node* &, struct Node* &, short);
    short GetElemPosition(struct Node* &, short);
    short DeleteNodeByValue(struct Node* &, struct Node* &, short);
    short DeleteNodeByPos(struct Node* &, struct Node* & ,short);
    /* 单链表结点的定义 */
    struct Node
    {
        short data;
        struct Node* next;
    };
    int main()
    {
        /* 单链表的头指针 */
        struct Node *head;
        /* 单链表的尾指针 */
        struct Node *rear;
        /* 操作代码 */
        short choice;
        short temp;
        short pos;
        short length;
        /* 头结点初始化标志 */
        short headInit = 0;
        printf("-------------------------单链表操作模拟系统---------------------------\n");
        printf("--------------------------1. 初始化头结点-----------------------------\n");
        printf("--------------------------2. 插入新结点(头插法)-----------------------\n");
        printf("--------------------------3. 插入新结点(尾插法)-----------------------\n");
        printf("--------------------------4. 按位置删除结点---------------------------\n");
        printf("--------------------------5. 按数值删除结点---------------------------\n");
        printf("--------------------------6. 获取当前表长-----------------------------\n");
        printf("--------------------------7. 遍历单链表-------------------------------\n");
        printf("--------------------------8. 判断是否为空表---------------------------\n");
        printf("--------------------------9. 根据数值查找结点位置---------------------\n");
        printf("-------------------------10. 退出系统---------------------------------\n");
        printf("-------------------------11. 清空单链表-------------------------------\n");
        printf("-------------------------12. 销毁单链表-------------------------------\n");
        /* */
        while(1)
        {
            printf("请输入操作码(1~12): ");
            while(scanf("%hd", &choice) != 1 || choice < 1 || choice > 12)
            {
                printf("请输入合法操作码.\n");
                while(getchar() != '\n') ;
                printf("请输入操作码(1~12): ");
            }
            if(choice == 10)
            {
                printf("欢迎再次使用, 再见!\n");
                break;
            }
            if(headInit == 1 && choice == 1)
            {
                /* 企图重复初始化头结点 */
                /* 拦截该行为 */
                printf("请不要重复初始化头结点.\n");
                continue;
            }
            else if(headInit == 0 && choice == 12)
            {
                /* 企图重复销毁链表 */
                /* 拦截该行为 */
                printf("请先初始化头结点再尝试销毁单链表.\n");
                continue;
            }
            else if(headInit == 0 && choice != 1)
            {
                /* 企图不初始化头结点就开始访问链表 */
                /* 拦截该行为 */
                printf("请先初始化头结点再对单链表进行操作.\n");
                continue;
            }
            switch(choice)
            {
                case 1:
                    if(InitLinkList(head, rear) == -1)
                    {
                        /* 头结点申请失败 */
                        printf("头结点申请失败, 程序结束.\n");
                        exit(0);
                    }
                    printf("头结点初始化成功.\n");
                    headInit = 1;
                    break;
                case 2:
                    printf("请输入要插入结点的数据域: ");
                    while(scanf("%hd", &temp) != 1)
                    {
                        while(getchar() != '\n') ;
                        printf("请输入合法数据.\n");
                        printf("请输入要插入结点的数据域: ");
                    }
                    if(HeadInsert(head, rear, temp) == -1)
                    {
                        /* 新结点申请失败 */
                        printf("结点申请失败.\n");
                    }
                    else
                    {
                        /* 结点插入成功 */
                        printf("数据域为%3hd的结点插入成功.\n", temp);
                    }
                    break;
                case 3:
                    printf("请输入要插入结点的数据域: ");
                    while(scanf("%hd", &temp) != 1)
                    {
                        while(getchar() != '\n') ;
                        printf("请输入合法数据.\n");
                        printf("请输入要插入结点的数据域: ");
                    }
                    if(RearInsert(rear, temp) == -1)
                    {
                        /* 新结点申请失败 */
                        printf("结点申请失败.\n");
                    }
                    else
                    {
                        /* 结点插入成功 */
                        printf("数据域为%3hd的结点插入成功.\n", temp);
                    }
                    break;
                case 4:
                    printf("请输入要删除结点的下标: ");
                    while(scanf("%hd", &temp) != 1 || temp < 1)
                    {
                        while(getchar() != '\n') ;
                        printf("请输入合法数据.\n");
                        printf("请输入要删除结点的下标: ");
                    }
                    if(DeleteNodeByPos(head, rear, temp) == -1)
                    {
                        /* 给定位置超出表长范围 */
                        printf("给定位置超出表长范围.\n");
                        printf("删除失败.\n");
                    }
                    else
                    {
                        /* 结点删除成功 */
                        printf("数据域为%3hd的结点删除成功.\n", temp);
                    }
                    break;
                case 5:
                    printf("请输入要删除结点数据域的值: ");
                    while(scanf("%hd", &temp) != 1)
                    {
                        while(getchar() != '\n') ;
                        printf("请输入合法数据.\n");
                        printf("请输入要删除结点数据域的值: ");
                    }
                    if(DeleteNodeByValue(head, rear, temp) == -1)
                    {
                        /* 未找到相应结点 */
                        printf("未找到数据域为%3hd的结点.\n", temp);
                        printf("删除失败.\n");
                    }
                    else
                    {
                        /* 结点删除成功 */
                        printf("数据域为%3hd的结点已删除.\n", temp);
                    }
                    break;
                case 6:
                    printf("当前表长为%3hd.\n", GetListLength(head));
                    break;
                case 7:
                    printf("当前表中元素为: ");
                    Traversal(head);
                    break;
                case 8:
                    if(IsEmpty(head) == 1)
                    {
                        printf("当前单链表为空表.\n");
                    }
                    else
                    {
                        printf("当前单链表为非空表.\n");
                    }
                    break;
                case 9:
                    printf("请输入要查找结点的数据域: ");
                    while(scanf("%hd", &temp) != 1)
                    {
                        while(getchar() != '\n') ;
                        printf("请输入合法数据.\n");
                        printf("请输入要查找结点的数据域: ");
                    }
                    pos = GetElemPosition(head, temp);
                    if(pos == -1)
                    {
                        /* 未找到该结点 */
                        printf("数据域为%3hd的结点不在表中.\n", temp);
                    }
                    else
                    {
                        printf("数据域为%3hd的结点在表中的下标为%3hd.\n", temp, pos);
                    }
                    break;
                case 11:
                    if(IsEmpty(head) == 1)
                    {
                        /* 表空 */
                        printf("表已空, 不必重复清空.\n");
                    }
                    else
                    {
                        /* 表不空 */
                        /* 获取表长 */
                        length = GetListLength(head);
                        short i = 0;
                        /* 执行length次循环, 每次都将下标为1的结点删除, length次后表空 */
                        while(i < length)
                        {
                            DeleteNodeByPos(head, rear, 1);
                            i ++;
                        }
                        printf("已清空单链表.\n");
                    }
                    break;
                case 12:
                    /* 进入循环后的判断语句确保当前链表未被销毁, 即头结点存在 */
                    /* 先清空链表数据结点 */
                    if(IsEmpty(head) == 1)
                    {
                        /* 已是空表, 只需要销毁头结点即可 */
                        free(head);
                        headInit = 0;
                    }
                    else
                    {
                        /* 表中还有数据结点, 应先销毁数据结点 */
                        length = GetListLength(head);
                        short j = 0;
                        while(j < length)
                        {
                            DeleteNodeByPos(head, rear, 1);
                            j ++;
                        }
                        /* 接着销毁头结点 */
                        free(head);
                        headInit = 0;
                    }
                    printf("单链表已销毁.\n");
                    break;
            }
        }
    }
    /* 根据给定位置删除表中元素 */
    short DeleteNodeByPos(struct Node* &head, struct Node* &rear, short pos)
    {
        short length = GetListLength(head);
        if(pos > length || pos < 1)
        {
            /* 给定位置已超出表长范围 */
            return -1;
        }
        short i = 1;
        struct Node *p = head -> next;
        struct Node *q = head;
        while(p != NULL)
        {
            if(i == pos)
            {
                /* 定位到删除位置 */
                if(p -> next == NULL)
                {
                    /* 待删除结点为表尾结点 */
                    /* 需要修改尾指针rear */
                    rear = q;
                }
                q -> next = p -> next;
                free(p);
                return 1;
            }
            i ++;
            p = p -> next;
            q = q -> next;
        }
    }
    /* 删除表中第一个值为value的元素 */
    short DeleteNodeByValue(struct Node* &head, struct Node* &rear, short value)
    {
        struct Node *p = head -> next;
        struct Node *q = head;
        while(p != NULL)
        {
            if(p -> data == value)
            {
                /* 找到待删除结点 */
                if(p -> next == NULL)
                {
                    /* 待删除结点为表尾结点 */
                    /* 此时需要修改尾指针rear */
                    rear = q;
                }
                q -> next = p -> next;
                free(p);
                return 1;
            }
            p = p -> next;
            q = q -> next;
        }
        /* 未找到值为value的元素 */
        return -1;
    }
    /* 查找数据元素value是否在表中, 如果在, 返回该结点在表中的位置 */
    short GetElemPosition(struct Node* &head, short value)
    {
        short i = 1;
        struct Node *p = head -> next;
        while(p != NULL)
        {
            if(p -> data == value)
            {
                return i;
            }
            p = p -> next;
            i ++;
        }
        /* 未找到数据元素value */
        return -1;
    }
    /* 单链表的头插法 */
    short HeadInsert(struct Node* &head, struct Node* &rear, short value)
    {
        struct Node *p = head -> next;
        struct Node *N = (struct Node*)malloc(sizeof(struct Node));
        if(N != NULL)
        {
            /* 结点申请成功 */
            if(IsEmpty(head) == 1)
            {
                /* 表空, 此时需要修改尾指针 */
                rear = N;
            }
            N -> next = p;
            head -> next = N;
            N -> data = value;
            return 1;
        }
        else
        {
            /* 结点申请失败 */
            return -1;
        }
    }
    /* 获取当前表长 */
    short GetListLength2(struct Node* &head)
    {
        short length = 0;
        struct Node *p = head -> next;
        while(p != NULL)
        {
            length ++;
            p = p -> next;
        }
        return length;
    }
    /* 获取当前表长 */
    short GetListLength(struct Node* &head)
    {
        short length = 0;
        struct Node *p = head;
        while(p -> next != NULL)
        {
            length ++;
            p = p -> next;
        }
        return length;
    }
    /* 遍历单链表并输出 */
    void Traversal(struct Node* &head)
    {
        if(IsEmpty(head) == 0)
        {
            /* 表非空 */
            struct Node *p = head -> next;
            while(p != NULL)
            {
                printf("%3hd", p -> data);
                p = p -> next;
            }
        }
        putchar('\n');
    }
    /* 判断单链表是否为空表 */
    short IsEmpty(struct Node* &head)
    {
        if(head -> next == NULL)
        {
            /* 表空 */
            return 1;
        }
        else
        {
            /* 表非空 */
            return 0;
        }
    }
    /* 单链表的尾插法 */
    short RearInsert(struct Node* &rear, short value)
    {
        struct Node *p = (struct Node*)malloc(sizeof(struct Node));
        if(p != NULL)
        {
            /* 结点空间申请成功 */
            p -> data = value;
            rear -> next = p;
            p -> next = NULL;
            rear = p;
            return 1;
        }
        else
        {
            /* 结点空间申请失败 */
            return -1;
        }
    }
    /* 创建头结点 */
    short InitLinkList(struct Node* &head, struct Node* &rear)
    {
        head = (struct Node*)malloc(sizeof(struct Node));
        if(head != NULL)
        {
            /* 头结点申请成功 */
            printf("头结点申请成功.\n");
            head -> data = 0;
            head -> next = NULL;
            rear = head;
            return 1;
        }
        else
        {
            printf("头结点申请失败.\n");
            return -1;
        }
    }