静态链表学习代码-不能用指针时在数组中的单链表实现

梦里梦外; 2022-05-20 08:12 97阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<stddef.h>
    #define ArrayMaxSize 1102//足够大的数组空间
    //线性表-静态链表
    //顺序存储的优点 （随机存取快O(1)）缺点（删除插入操作效率低时间复杂度为O(n) 大小无法随意更改）
    //非连续内存链式结构的优点（插入删除时间复杂度均为O(1) 大小随时改变） 缺点（无法随机存取，查找时间复杂度为O(n)）
    //静态链表用于不支持指针使用的编程环境，用结构体数组实现
    //静态链表的优点（用数据成员游标充当指针的角色，有链式结构的优点）缺点（依然无法解决数组大小固定的问题，查找效率不高）
    typedef struct StaticList{
        int data;
        int Cursor;//游标
    }S_List;
    unsigned SList_Length=0;//表长一开始为0
    S_List Base[ArrayMaxSize];
    unsigned exist = 0;//是否执行了第一次初始化
    void Initialize_StaticList(unsigned ElementNumber)
    {
        SList_Length=ElementNumber;//表长更新
        unsigned index;
        Base[ArrayMaxSize-1].Cursor=1;//更新第一个有数据结点的位置
        for(index=1;index<ElementNumber;index++)
        {
            Base[index].data=rand()%100 +1;//先生成n-1个有数据结点
            Base[index].Cursor=index+1;
        }
        Base[ElementNumber].data=index;
        Base[ElementNumber].Cursor=0;//最后一个结点游标为0以作识别
        Base[0].Cursor=ElementNumber+1;//Base[0]记录备用结点空间的第一个位置
        if(ElementNumber<ArrayMaxSize-100)for(index=ElementNumber+1;index<ArrayMaxSize-1;index++)Base[index].Cursor=index+1;
        //若表长没有接近数组空间限制，剩下的备用结点生成备用链表，数组最后一个元素用来记录有数据链表的第一个结点下标
    }
    void PrintAllElements_StaticList()
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}
        unsigned index=Base[ArrayMaxSize-1].Cursor;//index赋值为第一个有数据结点的位置
        while(index!=0)//当有数据表不为空表且未识别到表尾结点，输出下标index的结点数据
        {
            printf("%-4d",Base[index].data);
            index=Base[index].Cursor;
        }
    }
    void Insert_ElementInto_StaticList(unsigned Order_InsertBefore)
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}//当空表和即将满表，不能再新加入结点
        if(SList_Length>=ArrayMaxSize-100){
       printf("List is full.\n");return;}
        unsigned index=Base[ArrayMaxSize-1].Cursor,count;
        int value;
        for(count=2;count<Order_InsertBefore;count++)//count计数器使index移动到“将要插入到它后面的结点”的位置
        {
            index=Base[index].Cursor;
        }
        printf("Type in an Integer you want to Insert it Before Element%d: ",Order_InsertBefore);
        scanf("%d",&value);
        Base[Base[0].Cursor].data=value;//新结点赋数字值
        unsigned CursorToNextSpare=Base[Base[0].Cursor].Cursor;//记录下一个空闲结点位置
        Base[Base[0].Cursor].Cursor=Base[index].Cursor;//新结点的游标指向index位置结点的下一个结点
        Base[index].Cursor=Base[0].Cursor;//index位置结点的游标指向新结点
        Base[0].Cursor=CursorToNextSpare;//更新空闲链表的头结点位置
        SList_Length++;//更新表长
    }
    void Delete_ElementFrom_StaticList(unsigned Delete_Order)
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}
        char choice;
        printf("Delete Element%d? Y/N: ",Delete_Order);
        getchar();//吸收输入位置后敲回车
        scanf("%c",&choice);
        if(choice=='Y'||choice=='y')
        {
            int index=Base[ArrayMaxSize-1].Cursor,count;
            for(count=2;count<Delete_Order;count++)index=Base[index].Cursor;
            if(Delete_Order>1&&Delete_Order<SList_Length){Base[index].Cursor=Base[Base[index].Cursor].Cursor;SList_Length--;}//要删除的如果不是头尾结点，调整游标使遍历时跳过它
            else if(Delete_Order==1){Base[ArrayMaxSize-1].Cursor=Base[Base[ArrayMaxSize-1].Cursor].Cursor;SList_Length--;}//若为头结点，改变数组最后元素存储的“有数据链表头结点”的位置
            else if(Delete_Order==SList_Length)//若为尾结点，改变加0标记的结点
            {
                Base[index].Cursor=0;
                SList_Length--;
            }
            else {
       printf("The Order of the Number you have input is out of range\n");}//范围限定
    
        }
        else return;
    }
    void AddBack_StaticList()
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}
        if(SList_Length>=ArrayMaxSize-100){
       printf("List is full.\n");return;}
        unsigned index=Base[ArrayMaxSize-1].Cursor,count;
        int value;
        for(count=2;count<SList_Length+1;count++)
        {
            index=Base[index].Cursor;
        }
        printf("Type in an Integer which will be appended at the end: ");
        scanf("%d",&value);
        Base[Base[0].Cursor].data=value;
        unsigned CursorToNextSpare=Base[Base[0].Cursor].Cursor;
        Base[Base[0].Cursor].Cursor=0;//在尾部的标记
        Base[index].Cursor=Base[0].Cursor;
        Base[0].Cursor=CursorToNextSpare;
        SList_Length++;
    }
    void AddFront_StaticList()
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}
        if(SList_Length>=ArrayMaxSize-100){
       printf("List is full.\n");return;}
        int value;
        printf("Type in an Integer which will be appended at the front: ");
        scanf("%d",&value);
        Base[Base[0].Cursor].data=value;
        unsigned temp=Base[ArrayMaxSize-1].Cursor;//原本的有数据头结点位置
        Base[ArrayMaxSize-1].Cursor=Base[0].Cursor;//确定头结点位置
        Base[0].Cursor=Base[Base[0].Cursor].Cursor;
        Base[Base[ArrayMaxSize-1].Cursor].Cursor=temp;
        SList_Length++;
    }
    void ChangeNumber_StaticList(unsigned Order)
    {
        if(SList_Length<1){
       printf("List is empty.\n");return;}
        unsigned index = Base[ArrayMaxSize-1].Cursor,count;
        int value;
        for(count=1;count<Order;count++)index=Base[index].Cursor;
        printf("Type in a Integer as Element%d's New Number: ",Order);
        scanf("%d",&value);
        Base[index].data = value;
    }
    void Menu()
    {
        system("cls");
        int choice;
        printf("1.Create a Static ForwardList contains certain number of Integers\n");
        printf("2.Print All ElementValues in order\n");
        printf("3.Insert an Integer into Static ForwardList\n");
        printf("4.Append an Integer at the front of Static ForwardList\n");
        printf("5.Append an Integer at the end of Static ForwardList\n");
        printf("6.Change an Element's Number\n");
        printf("7.Remove an Element from Static ForwardList\n");
        printf("0.Exit\n");
        printf("Choose one Function by corresponding number: ");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
            {
    
                unsigned LengthParameter;
                printf("Set List's number of Elements: ");scanf("%d",&LengthParameter);//自定义表长
                Initialize_StaticList(LengthParameter);
                exist = 1;//静态链表状态改变
                system("pause");Menu();
                break;
            }
            case 2:if(!exist)break;PrintAllElements_StaticList();printf("\n");system("pause");Menu();break;
            case 3:
                {
                    if(!exist)break;//必须已经初始化
                    unsigned Location;
                    printf("Insert an Element before which Element? Type in its Order number: ");
                    scanf("%d",&Location);
                    if(Location>1&&Location<=SList_Length)Insert_ElementInto_StaticList(Location);//插入位置在头尾之间
                    else printf("Insert Failed\n");
                    system("pause");Menu();
                    break;
                }
            case 4:if(!exist)break;AddFront_StaticList();system("pause");Menu();break;
            case 5:if(!exist)break;AddBack_StaticList();system("pause");Menu();break;
            case 6:
                {
                    if(!exist)break;
                    unsigned Location;
                    printf("Change which Element's number ? Type in its Order number: ");
                    scanf("%d",&Location);
                    if(Location>=1&&Location<=SList_Length)ChangeNumber_StaticList(Location);//范围限定
                    else printf("Change Failed");
                    system("pause");Menu();
                    break;
                }
            case 7:
                {
                    if(!exist)break;
                    unsigned Location;
                    printf("Remove which Element? Type in its Order number: ");
                    scanf("%d",&Location);
                    Delete_ElementFrom_StaticList(Location);
                    system("pause");Menu();
                    break;
                }
            default:break;
        }
    }
    
    
    int main()
    {
        srand((unsigned)time(NULL));//随机数种子
        Base[0].Cursor=1;//空表时两个记录点的赋值
        Base[ArrayMaxSize-1].Cursor=0;
        //PrintAllElements_StaticList(WholeSpace);
        //printf("\n");
        //Insert_ElementInto_StaticList(WholeSpace,8);//Insert参数只接收>1且<=ListLength的整数
        //AddBack_StaticList(WholeSpace);
        //ChangeNumber_StaticList(WholeSpace,5);
        //AddFront_StaticList(WholeSpace);
        //Delete_ElementFrom_StaticList(WholeSpace,0);
        //PrintAllElements_StaticList(WholeSpace);
        //printf("\n");
        Menu();
        return 0;
    }