C语言数据结构--顺序表

痛定思痛。 2024-03-23 13:43 28阅读 0赞

这一期用顺序表实现插入、查找、删除这几个基本操作。（一共两题）

**1****、利用顺序表的几个基础操作算法完成以下功能：**

(1)顺序表L定义

(2)给顺序表赋初值：包含12, 10, 60, 30, 11, 17, 80等元素

(3)打印出顺序表L

12 10 60 30 11 17 80

(4)打印出线性表第3个元素60

(5)打印出11的位置:1

(6)在第4个元素位置上插入元素999

(7)打印出线性表：

12 10 60 999 30 11 17 80

(8)删除L的第3个元素

(9)打印出线性表L

12 10 999 30 11 17 80

**2****、从顺序表Ｌ中删除从第ｉ个元素开始的ｋ个元素（ｉ，ｋ均为序号）。**

①创建顺序表

void CreateSeqList(SeqList *L)
    {
        int len;
        printf("请输入数据的总个数：");
        scanf("%d",&len);
        L->last = len - 1;                    //得到最后一个数组的下标
        for(int i=0;i <= L->last;i++)        //依次往后赋值
        {
            printf("请输入数据：");
            scanf("%d",&L->elem[i]);
        }
    }

②插入操作

int InsList(SeqList *L,int i,int e)
    {
        if((i<1)||(i>L->last+2))     //（1）//判断插入位置是否合法，如果小于1或者大于表长加1，则返回错误
        {
            printf("\n插入位置 %d 不合法！",i);
            return ERROR;
        }
        if(L->last >= MAXSIZE-1)     //（2）
        {
            printf("\n表已满！");
            return ERROR;
        }
        for (int k=L->last;k>=i-1;k--)//（3）//从表尾开始，将第i个位置及之后的元素依次后移一位，为插入元素腾出空间
        {
            L->elem[k+1] = L->elem[k];   //依次后移
        }
        L->elem[i-1]=e;       //将元素e放入第i个位置
        L->last++;             //更新表长
        return OK;
    }

③查找操作

按值查找

int Locate(SeqList L, int e)
    {
        int i=0;        /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
        while ((i<=L.last) && (L.elem[i]!=e))/*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
            i++;
        if  (i <= L.last)
            return i+1;  /*若找到值为e的元素，则返回其序号*/
        else
            return ERROR;  /*若没找到，则返回0序号*/
    }

按位置查找

int Get(SeqList L,int i)
    {
        return L.elem[i-1];
    }

④删除操作

第一题的删除函数

int DelList(SeqList *L,int i,int *e)
    {
        if((i<1) || (i > L->last+1))     //（1）判断删除位置是否合法，如果小于1或者大于表长，则返回错
        {
            printf("\n删除 %d 位置不合法！",i);
            return ERROR;
        }
        *e = L->elem[i-1];                //（2）将第i个位置的元素的值赋给e
        for(int k=i;k<=L->last;k++)          //（3）从第i+1个位置开始，将之后的元素依次前移一位，覆盖被删除的元素
        {
            L->elem[k-1] = L->elem[k];     //将元素依次往前移
        }
        L->last--;                     //更新表长
        return OK;
    }

第二题的删除函数

int MyDel(SeqList *L,int i,int k)
    {
        if((i<1)||(i>L->last+1) ||k<1)
        {
            printf("\n删除 %d 位置不合法！",i);
            return ERROR;
        }
        if((i+k-1)>L->last)   //i+k-1：新的表尾的位置，这一句的意思是如果超出原表尾，则直接截断
        {
            L->last=i-2;
            return OK;
        }
        for(int m=i+k-1;m<=L->last;m++)
        {
            L->elem[m-k]=L->elem[m];
        }                                            /*将后面的元素依次前移*/
        L->last-=k;
        return OK;
    }

⑤输出顺序表

void SeqList_display(SeqList L)
    {
        printf("\n打印顺序表如下：\n");
        for(int i=0; i<=L.last; i++)
            printf("  %d",L.elem[i]);
    }

完整代码：

#include "stdio.h"
    #define MAXSIZE 100
    #define OK 1
    #define ERROR 0
    
    typedef struct
    {
        int elem[MAXSIZE];
        int last;
    }SeqList;
    
    //创建顺序表
    void CreateSeqList(SeqList *L)
    {
        int len;
        printf("请输入数据的总个数：");
        scanf("%d",&len);
        L->last = len - 1;                    //得到最后一个数组的下标
        for(int i=0;i <= L->last;i++)        //依次往后赋值
        {
            printf("请输入数据：");
            scanf("%d",&L->elem[i]);
        }
    }
    //插入操作
    int InsList(SeqList *L,int i,int e)
    {
        if((i<1)||(i>L->last+2))     //（1）//判断插入位置是否合法，如果小于1或者大于表长加1，则返回错误
        {
            printf("\n插入位置 %d 不合法！",i);
            return ERROR;
        }
        if(L->last >= MAXSIZE-1)     //（2）
        {
            printf("\n表已满！");
            return ERROR;
        }
        for (int k=L->last;k>=i-1;k--)//（3）//从表尾开始，将第i个位置及之后的元素依次后移一位，为插入元素腾出空间
        {
            L->elem[k+1] = L->elem[k];   //依次后移
        }
        L->elem[i-1]=e;       //将元素e放入第i个位置
        L->last++;             //更新表长
        return OK;
    }
    
    //查找操作
    //按值查找
    int Locate(SeqList L, int e)
    {
        int i=0;        /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
        while ((i<=L.last) && (L.elem[i]!=e))/*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
            i++;
        if  (i <= L.last)
            return i+1;  /*若找到值为e的元素，则返回其序号*/
        else
            return ERROR;  /*若没找到，则返回0序号*/
    }
    
    //按位置查找
    int Get(SeqList L,int i)
    {
        return L.elem[i-1];
    }
    
    //删除操作
    int DelList(SeqList *L,int i,int *e)
    {
        if((i<1) || (i > L->last+1))     //（1）判断删除位置是否合法，如果小于1或者大于表长，则返回错
        {
            printf("\n删除 %d 位置不合法！",i);
            return ERROR;
        }
        *e = L->elem[i-1];                //（2）将第i个位置的元素的值赋给e
        for(int k=i;k<=L->last;k++)          //（3）从第i+1个位置开始，将之后的元素依次前移一位，覆盖被删除的元素
        {
            L->elem[k-1] = L->elem[k];     //将元素依次往前移
        }
        L->last--;                     //更新表长
        return OK;
    }
    
    //第二题的删除函数
    int MyDel(SeqList *L,int i,int k)
    {
        if((i<1)||(i>L->last+1) ||k<1)
        {
            printf("\n删除 %d 位置不合法！",i);
            return ERROR;
        }
        if((i+k-1)>L->last)   //i+k-1：新的表尾的位置，这一句的意思是如果超出原表尾，则直接截断
        {
            L->last=i-2;
            return OK;
        }
        for(int m=i+k-1;m<=L->last;m++)
        {
            L->elem[m-k]=L->elem[m];
        }                                            /*将后面的元素依次前移*/
        L->last-=k;
        return OK;
    }
    
    //输出顺序表
    void SeqList_display(SeqList L)
    {
        printf("\n打印顺序表如下：\n");
        for(int i=0; i<=L.last; i++)
            printf("  %d",L.elem[i]);
    }
    
    int main()
    {
        SeqList L;
        int loc = 3;                   //按位置查找，可以修改成其它位置，这里表示第 3个元素
        int ele = 11;                  //按值查找，可以修改成其它值，这里表示为元素值为11
        int ins = 4,e = 999;          //插入操作，ins表示插入的位置，e表示插入元素的值，可以修改你想要的
        int del=3,se;                 //删除操作，del表示删除的位置，se保存了要删除元素的值，可以修改你想要的
        int i = 3,k = 2;              //第二题,i表示要从序号为 i的元素开始删除，k表示从i开始要删除多少个元素
        CreateSeqList(&L);
        SeqList_display(L);
        int get_elem = Get(L,loc);
        printf("\n顺序表第 %d 个元素：%d",loc,get_elem);
        int get_loc = Locate(L, ele);
        printf("\n顺序表 %d 元素的位置：%d",ele,get_loc);    //如果没有找到则得到0
        if( InsList(&L,ins,e))
        {
            printf("\n在第 %d 元素位置上插入元素 %d  ",ins,e);
            SeqList_display(L);
        }
        if(DelList(&L,del,&se))
        {
            printf("\n删除顺序表的第 %d 个元素  ",del);
            SeqList_display(L);
        }
        if( MyDel(&L,i,k))
        {
            printf("\n删除从第 %d 个元素开始的 %d 个元素  ",i,k);
            SeqList_display(L);
        }
        return 0;
    }

结果：

![b6baf439dd78441e9f2e0ac1c599fda1.png][]

总结：

这里我只演示了查找操作、插入操作和删除操作成功时的结果，大家也可以试一下当查找操作、插入操作和删除操作失败时会得到什么结果。

[b6baf439dd78441e9f2e0ac1c599fda1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/20377316fa5f452d9003198094d5999a.png