单链表简单操作

桃扇骨 2023-01-02 14:24 202阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    struct Node
    {
        int data;/* 数据域 */
        struct Node *next;
    };
    struct Node *head;/* 头指针 */
    struct Node *tail;/* 尾指针 */
    int node_Init()/* 初始化头结点 */
    {
        head=(struct Node*)malloc(sizeof(struct Node));
        if(head!=NULL)/* 头结点内存空间申请成功 */
        {
            head->next=NULL;
            tail=head;/* 初始化头结点后, 尾结点也指向头结点 */
            return 1;
        }
        else/* 头结点内存空间申请失败 */
        {
            return -1;
        }
    }
    int node_Creation_Rear()/* 创建一个新结点 */ /* 尾插法 */
    {
        struct Node *p=(struct Node*)malloc(sizeof(struct Node));/* 申请一个Node结点的存储空间 */
        if(p!=NULL)/* 存储空间分配成功 */
        {
            tail->next=p;/* 尾指针的下一结点为新创建的结点 */
            tail=p;/* 尾指针指向新创建结点 */
            p->next=NULL;/* 新创建结点的下一结点为空 */
            printf("请输入新建元素的数值: ");
            scanf("%d", &(tail->data));
            return 1;
        }
        else/* 存储空间分配失败 */
        {
            return -1;
        }
    }
    int node_Creation_Head()/* 创建一个新结点 */ /* 头插法 */
    {
        struct Node *p=(struct Node*)malloc(sizeof(struct Node));/* 申请一个Node结点的存储空间 */
        if(p!=NULL)/* 存储空间分配成功 */
        {
            p->next=head->next;/* 新结点的下一结点为表中第一个元素 */
            head->next=p;/* 表中第一个元素改为新结点 */
            printf("请输入新建元素的数值: ");
            scanf("%d", &(p->data));
        }
        else/* 存储空间分配失败 */
        {
            return -1;
        }
    }
    int get_Length()/* 获取当前表长 */
    {
        int length=0;
        struct Node *p=head->next;/* p指向表中第一个元素 */
        while(p!=NULL)
        {
            length++;
            p=p->next;
        }
        return length;
    }
    int is_Empty()/* 判断是否为空表 */
    {
        if(get_Length()==0)/* 表长为0 */
        {
            return 1;
        }
        else/* 表长不为0 */
        {
            return 0;
        }
    }
    int get_Element_Location(int value)/* 根据给定数值寻找表中元素, 并返回其坐标 */
    {
        int i=1;/* 表中第一个元素的坐标为1 */
        struct Node *p=head->next;/* p指向表中第一个元素 */
        while(p!=NULL)
        {
            if(p->data==value)/* 第一次找到与给定数值相匹配的结点 */
            {
                return i;/* 返回其坐标值 */
            }
            else
            {
                i++;
                p=p->next;
            }
        }
        return -1;/* 若程序运行至此, 说明未找到给定数值的结点 */
    }
    struct Node* get_Element_Address(int value)/* 根据给定数值寻找表中元素, 并返回其指针 */
    {
        struct Node *p=head->next;/* p指向表中第一个元素 */
        while(p!=NULL)
        {
            if(p->data==value)/* 第一次找到与给定数值相匹配的结点 */
            {
                return p;/* 返回其指针 */
            }
            else
            {
                p=p->next;
            }
        }
        return NULL;/* 若程序运行至此, 说明未找到给定数值的结点 */
    }
    int get_Location(int location)/* 根据坐标位置确定元素值 */
    {
        struct Node *p=head->next;/* p指向表中第一个元素 */
        int i=1;/* 表中第一个元素的坐标为1 */
        if(location>get_Length())/* 给定坐标超过表长 */
        {
            return -1;
        }
        else if(location<1)/* 给定坐标小于1 */
        {
            return -1;
        }
        else/* 给定坐标合法 */
        {
            while(p!=NULL)
            {
                if(i==location)
                {
                    return p->data;
                }
                else
                {
                    i++;
                    p=p->next;
                }
            }
        }
    }
    struct Node* get_Address(int location)/* 根据给定坐标确定结点指针 */
    {
        struct Node *p=head->next;/* p指向表中第一个元素 */
        int i=1;/* 表中第一个元素的坐标为1 */
        if(location>get_Length())/* 给定坐标超过表长 */
        {
            return NULL;
        }
        else if(location<1)/* 给定坐标小于1 */
        {
            return NULL;
        }
        else/* 给定坐标合法 */
        {
            while(p!=NULL)
            {
                if(i==location)
                {
                    return p;
                }
                else
                {
                    p=p->next;
                    i++;
                }
            }
        }
    }
    int delete_Element_Location(int location)/* 根据坐标位置删除结点 */
    {
        if(location<1)/* 给定坐标小于1 */
        {
            return -1;
        }
        else if(location>get_Length())/* 给定坐标大于表长 */
        {
            return -1;
        }
        else
        {
            struct Node *p=get_Address(location);
            struct Node *q;
            if(p==head->next)/* 待删除结点为表中首结点 */
            {
                head->next=p->next;
                free(p);
            }
            else/* 待删除结点不为表中首结点 */
            {
                q=get_Address(location-1);/* q指向待删除结点的直接前驱 */
                q->next=p->next;
                free(p);
            }
            return 1;
        }
    }
    int modify_Location(int location)/* 根据坐标位置修改元素值 */
    {
        struct Node *p=head->next;/* p指向表中第一个元素 */
        int i=1;/* 表中第一个元素的坐标为1 */
        if(location>get_Length())/* 给定坐标超过表长 */
        {
            return -1;
        }
        else if(location<1)/* 给定坐标小于1 */
        {
            return -1;
        }
        else/* 给定坐标合法 */
        {
            while(p!=NULL)
            {
                if(i==location)
                {
                    printf("请输入要修改的数值: ");
                    scanf("%d", &(p->data));
                    return 1;
                }
                else
                {
                    i++;
                    p=p->next;
                }
            }
        }
    }
    void Clear()/* 清空当前线性表 */
    {
        struct Node *p=head;/* p指向头结点 */
        struct Node *q=head->next;
        while(q!=NULL)
        {
            p->next=p->next->next;
            free(q);
            q=p->next;
        }
        printf("线性表已清空.\n");
    }
    void Traversal()/* 遍历单链表 */
    {
        struct Node *p=head->next;/* p指向表中第一个元素 */
        while(p!=NULL)
        {
            printf("%d  ", p->data);
            p=p->next;
        }
        printf("\n");
    }
    int main()
    {
        node_Init();/* 初始化头结点 */ /* 程序开始后必须先执行此步操作 */
        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("----------------------------注意:先尾插再头插不影响线性表的使用-----------------\n");
        printf("---------------------------------先头插再尾插会丢失前面头插的元素---------------\n");
        /* 先尾插再头插不影响线性表的使用 */
        /* 先头插再尾插会丢失前面头插元素 */
        int choice;
        int t;
        int location;
        int value;
        printf("请输入要执行的操作代码(1~10): ");
        scanf("%d", &choice);
        while(choice!=10)
        {
            if(choice==1)
            {
                t=node_Creation_Head();
                if(t==1)
                {
                    printf("插入成功.\n");
                }
                else if(t==-1)
                {
                    printf("插入失败.\n");
                }
            }
            else if(choice==2)
            {
                t=node_Creation_Rear();
                if(t==1)
                {
                    printf("插入成功.\n");
                }
                else if(t==-1)
                {
                    printf("插入失败.\n");
                }
            }
            else if(choice==3)
            {
                printf("请输入待删除结点的坐标: ");
                scanf("%d", &location);
                t=delete_Element_Location(location);
                if(t==1)
                {
                    printf("删除成功.\n");
                }
                else if(t==-1)
                {
                    printf("删除失败.\n");
                }
            }
            else if(choice==4)
            {
                printf("请输入待查找元素的坐标: ");
                scanf("%d", &location);
                t=get_Location(location);
                if(t==1)
                {
                    printf("坐标为%d的元素值为%d.\n", location, t);
                }
                else if(t==-1)
                {
                    printf("查找失败.\n");
                }
            }
            else if(choice==5)
            {
                printf("当前表长为%d.\n", get_Length());
            }
            else if(choice==6)
            {
                printf("请输入待确定坐标的元素值: ");
                scanf("%d", &value);
                t=get_Element_Location(value);
                if(t!=-1)
                {
                    printf("值为%d的元素的坐标为%d.\n", value, t);
                }
                else
                {
                    printf("未找到值为%d的元素.\n", value);
                }
            }
            else if(choice==7)
            {
                printf("当前表中元素为: ");
                Traversal();
            }
            else if(choice==8)
            {
                Clear();
            }
            else if(choice==9)
            {
                printf("请输入待修改元素的坐标: ");
                scanf("%d", &location);
                t=modify_Location(location);
                if(t==1)
                {
                    printf("修改成功.\n");
                }
                else if(t==-1)
                {
                    printf("修改失败.\n");
                }
            }
            printf("请输入要执行的操作代码(1~10): ");
            scanf("%d", &choice);
        }
        printf("感谢您的使用, 我们下次再见!\n");
        return 0;
    }