C严蔚敏数据结构-顺序表

Myth丶恋晨 2022-01-06 06:49 289阅读 0赞

## **顺序表** ##

**C语言描述**

#define LIST_INIT_SIZE 80
    //线性表存储空间的初始分配量
    #define LISTINCREMENT 10
    //线性表存储空间的分配增量
    typedef int ElemType;    //为int设置别名
    typedef struct{
        ElemType *elem;  //存储空间基址
        int length; //当前长度
        int listsize; //当前分配的存储容量，以sizeof(ElemType)为单位
    }SqList;  //俗称顺序表

**1.顺序表的初始化**

>  *  **为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基址**
>  *  **将表的当前长度设为0**

Status InitList(SqList &L){
        L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); //为顺序表申请堆空间
        if(!L.elem) exit(OVERFLOW);  //存储分配失败退出
        L.length = 0;  //顺序表初始长度置空
        return OK;
    }

**2.顺序表的查找**

>  *  **从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem\[i\]，则查找成功，返回序号i+1**
>  *  **若查遍整个顺序表都没有找到，则查找失败，返回0**

int LocateElem(SqList L,ElemType e){
        //在顺序表中查找值为e的数据元素，返回其序号
        for(int i=0;i<L.length;i++){
            if(L.elem[i] == e) return i+1;  //查找成功，返回序号i+1
        }
        return 0;  //查找失败，返回0
    }

**时间复杂度：O(n)**

**3.顺序表的取值**

>  *  **判断指定的位置序号i值是否合理（1<=i<=L.length),若不合理，则返回ERROR**
>  *  **若i值合理，则将第i个数据元素L.elem\[i-1\]赋给参数e，通过e返回第i个数据元素的传值**

Status GetElem(SqList L,int i,ElemType &e){
        if(i<1 || i>L.length) return ERROR; //判断i值是否合理，若不合理，返回ERROR
        e = L.elem[i-1];    //将elem[i-1]单元存储第i个数据元素
        return OK;
    }

**时间复杂度：O(1)**

**4.顺序表的插入**

>  *  **判断插入位置i是否合法（i值的合法范围是1<=i<=n+1），若不合法则返回ERROR**
>  *  **判断顺序表的存储空间是否已满，若满则返回ERROR**
>  *  **将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时无需移动）**
>  *  **将要插入的新元素e放入第i个位置**
>  *  **表长+1**

Status ListInsert(SqList &L,int i,ElemType e){
        //在顺序表L中第i个位置插入新的元素e，i的合法范围是1<=i<=L.length+1
        if((i<1) || (i>L.length+1)) return ERROR;  //i值不合法
        if(L.length == MAXSIZE) return ERROR;  //存储空间已满
        for(j=L.length-1;j>=i-1;j--){
            L.elem[j+1] = L.elem[j];  //输入位置的元素后移
        }
        L.elem[i-1] = e;   //将新元素放入第i个位置
        ++L.length;    //表长+1
        return OK;
    }

**时间复杂度：O(n)**

**5.顺序表的删除**

>  *  **判断删除位置i是否合法（合法值为1<=i<=n),若不合法则返回ERROR**
>  *  **将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）**
>  *  **表长-1**

Status ListDelete(SqList &L,int i){
        //在顺序表L中删除第i个元素，i值得合法范围是1<=i<=L.length
        if((i<1) || (i>L.length)) return ERROR;  //i值不合法
        for(int j=i;j<=L.length-1;j++){
            L.elem[j-1] = L.elem[j];  //被删除元素之后得元素前移
            --L.length;
            return OK;
        } 
    }

**时间复杂度：O(n)**

## **代码实现** ##

> **注意事项：**
> 
> 1.  **文件要命名为.cpp也就是C++文件，因为.c(C语言）不支持引用，会报错**
> 2.  **初始化顺序表时，要使用new来申请堆空间，如果直接定义一个数组，再让指针指向数组的话，因为数组是保存在栈上，随着函数调用的结束，栈会被释放，数组也会随之释放。而堆空间只能由程序员手动释放，或者程序运行结束后自动释放；或者使用malloc函数在堆中申请内存空间**
> 3.  **插入和删除顺序表元素，应注意表长的相应变化**
> 4.  **如果还有不理解的地方，可以直接评论问我！！**

#include <stdio.h>
    #include <stdlib.h>
    #define ERROR 0
    #define OK 1
    #define OVERFLOW 0
    #define SIZE 20
    typedef int Status;
    typedef int ElemType;
    typedef struct List SqList;
    struct List
    {
        ElemType *elem;
        int length;
    };
    void ListPrintf(SqList L);
    Status InitList(SqList &L);
    Status ListInsert(SqList &L,int i,ElemType e);
    Status ListDelete(SqList &L,int i);
    Status Getelem(SqList L,int i,ElemType &e) ;
    int main()
    {
        int n,s,a,b;
        char c;
        SqList L;
        if(InitList(L))
        {
            printf("------顺序表初始化成功------\n");
            printf("请输入顺序表的长度:\n");
            scanf("%d",&n);
            if(n>SIZE)
            {
                printf("超出顺序表分配空间!\n");
                exit(0);
            }
            printf("请输入顺序表元素:\n");
            for(int i=0; i<n; i++)
            {
                scanf("%d",&L.elem[i]);
                L.length++;
            }
            ListPrintf(L);
        }
        else
        {
            printf("------顺序表初始化失败------\n");
            exit(0);
        }
    
        while(true)
        {
            printf("请选择你想要执行的操作:\n1.打印顺序表\n2.插入元素\n3.删除元素\n4.取值\n5.退出\n");
            scanf(" %c",&c);
            if(c=='1')
            {
                ListPrintf(L);
            }
            else if(c=='2')
            {
                printf("请输入插入的位置和元素:\n");
                scanf("%d %d",&a,&b);
                ListInsert(L,a,b);
                ListPrintf(L);
            }
            else if(c=='3')
            {
                printf("请输入删除的位置:\n");
                scanf("%d",&a);
                ListDelete(L,a);
                ListPrintf(L);
            }
            else if(c=='4')
            {
                printf("请输入查询的位置:\n");
                scanf("%d",&a);
                if(Getelem(L,a,b))
                {
                    printf("位置%d的元素为%d\n",a,b);
                }
    
            }
            else
            {
                exit(0);
            }
        }
    
    }
    Status InitList(SqList &L)
    {
        //L.elem = new ElemType[SIZE]; //使用new在堆中申请内存
        L.elem = (ElemType*)malloc(SIZE*sizeof(ElemType));  //使用malloc函数在堆中开辟内存空间
        if(!L.elem)
        {
            return ERROR;
        }
        L.length = 0;
        return OK;
    }
    Status ListInsert(SqList &L,int i,ElemType e) //合法性判断，表长+1
    {
        int j;
        if(i<1||i>L.length+1)
        {
            printf("查询位置无效!\n");
            return ERROR;
        }
        if(L.length == SIZE)
        {
            printf("存储空间已满,无法插入!\n");
            return ERROR;
        }
        for(j=L.length-1; j>=i-1; j--)
        {
            L.elem[j+1] = L.elem[j];  //从后开始，每个元素后移一位
        }
        L.elem[i-1] = e;
        L.length++;  //表长+1
        return OK;
    }
    
    Status ListDelete(SqList &L,int i) //合法性判断，表长-1
    {
        if(i<1||i>L.length)
        {
            printf("删除位置无效!\n");
            return ERROR;
        }
        for(int j=i;j<=L.length-1;j++)   //使j定位在指定删除位置，后面的元素依次覆盖前一元素
        {
            L.elem[j-1] = L.elem[j];
        }
        L.length--; //表长-1
        return OK;
    }
    /*
    Status ListDelete(SqList &L,int i,ElemType &e)
    {
        if(i<1||i>L.length)
        {
            printf("删除位置无效!\n");
            return ERROR;
        }
        int* p = &(L.elem[i-1]);    //p指向待删除节点的位置
        //e = *p;                   //将待删除节点的值赋给e
        int* q = L.elem+L.length-1; //q为表尾元素的位置
        for(++p; p<=q; ++p)
        {
            *(p-1) = *p;
        }
        L.length--;
        return OK;
    }
    */
    Status Getelem(SqList L,int i,ElemType &e) //合法性判断
    {
        if(i<1||i>L.length)
        {
            printf("输入位置无效!\n");
            return ERROR;
        }
        e = L.elem[i-1];
        return OK;
    }
    void ListPrintf(SqList L)
    {
        for(int i=0; i<L.length; i++)
        {
            printf("%d\t",L.elem[i]);
        }
    
        printf("\n当前顺序表的表长为:%d\n",L.length);
    }