欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-02-03 16:53:22
...

    今晚花了一晚上写了一个功能较完善的单链表操作模拟系统, 有助于帮助初学者初始单链表的各种操作. 虽然系统已经过本人简单的测试, 但可能还存在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;
    }
}