顺序表及C实现

逻辑结构上呈线性分布的数据元素在实际的物理存储结构中也同样相互之间紧挨着，这种存储结构称为线性表的顺序存储结构

逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中，之间不存在空隙，这样的存储结构称为顺序存储结构。
使用顺序存储结构存储的数据，第一个元素所在的地址就是这块存储空间的首地址。通过首地址，可以轻松访问到存储的所有的数据，只要首地址不丢，数据永远都能找着（一根绳上的蚂蚱，要有就都有）。

1.定义顺序表的结构

    typedef struct Table{
        int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
        int length;//记录当前顺序表的长度
        int size;//记录顺序表分配的存储容量
    }table;

2.创建顺序表

    table initTable(){
        table t;
        t.head=(int*)malloc(Size*sizeof(int));//构造一个空的顺序表，动态申请存储空间
        if (!t.head) //如果申请失败，作出提示并直接退出程序
        {
            printf("初始化失败");
            exit(0);
        }
        t.length=0;//空表的长度初始化为0
        t.size=Size;//空表的初始存储空间为Size
        return t;
    }

3.顺序表查找元素

普通遍历

    //查找函数，其中，elem表示要查找的数据元素的值
    int selectTable(table t,int elem){
        for (int i=0; i<t.length; i++) {
            if (t.head[i]==elem) {
                return i+1;
            }
        }
        return -1;//如果查找失败，返回-1
    }

4.顺序表中更改元素

调用查找算法找到该数据元素的位置，直接在该位置上更改。

    //更改函数，其中，elem为要更改的元素，newElem为新的数据元素
    table amendTable(table t,int elem,int newElem){
        int add=selectTable(t, elem);
        t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
        return t;
    }

5.顺序表插入元素

插入数据元素有三种情况：

1).在表头插入
2).在表的中间某个位置插入
3).直接尾随顺序表，作为表的最后一个元素

无论在顺序表的什么位置插入数据元素，解决办法都是：找到要插入的位置，将后续数据元素整体向后移动一个位置，最后直接在腾出来的位置上插入数据元素。

    //插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
    table addTable(table t,int elem,int add)
    {
        //判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），
        //或者插入的位置本身不存在，程序作为提示并自动退出）
        if (add>t.length+1||add<1) {
            printf("插入位置有问题");
            return t;
        }
        //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
        if (t.length==t.size) {
            t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
            if (!t.head) {
                printf("存储分配失败");
                return t;
            }
            t.size+=1;
        }  
        //插入操作，需要将从插入位置开始的后续元素，逐个后移
        for (int i=t.length-1; i>=add-1; i--) {
            t.head[i+1]=t.head[i];
        }
        //后移完成后，直接将所需插入元素，添加到顺序表的相应位置
        t.head[add-1]=elem;
        //由于添加了元素，所以长度+1
        t.length++;
        return t;
    }

6.顺序表删除元素

在数组中删除元素时，只需将该元素所在位置后的所有数据元素整体前移 1 个位置.

前移的过程中被删除元素被后一个元素覆盖掉，间接实现了删除操作。

    table delTable(table t,int add){
        if (add>t.length || add<1) {
            printf("被删除元素的位置有误");
            exit(0);
        }
        //删除操作
        for (int i=add; i<t.length; i++) {
            t.head[i-1]=t.head[i];
        }
        t.length--;
        return t;
    }

完整代码实例

    #include <stdio.h>
    #include <stdlib.h>
    #define Size 6
    typedef struct Table{
        int * head;
        int length;
        int size;
    }table;
    table initTable(){
        table t;
        t.head=(int*)malloc(Size*sizeof(int));
        if (!t.head)
        {
            printf("初始化失败");
            exit(0);
        }
        t.length=0;
        t.size=Size;
        return t;
    }
    table addTable(table t,int elem,int add)
    {
        if (add>t.length+1||add<1) {
            printf("插入位置有问题");
            return t;
        }
        if (t.length>=t.size) {
            t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
            if (!t.head) {
                printf("存储分配失败");
            }
            t.size+=1;
        }
        for (int i=t.length-1; i>=add-1; i--) {
            t.head[i+1]=t.head[i];
        }
        t.head[add-1]=elem;
        t.length++;
        return t;
    }
    table delTable(table t,int add){
        if (add>t.length || add<1) {
            printf("被删除元素的位置有误");
            exit(0);
        }
        for (int i=add; i<t.length; i++) {
            t.head[i-1]=t.head[i];
        }
        t.length--;
        return t;
    }
    int selectTable(table t,int elem){
        for (int i=0; i<t.length; i++) {
            if (t.head[i]==elem) {
                return i+1;
            }
        }
        return -1;
    }
    table amendTable(table t,int elem,int newElem){
        int add=selectTable(t, elem);
        t.head[add-1]=newElem;
        return t;
    }
    void displayTable(table t){
        for (int i=0;i<t.length;i++) {
            printf("%d",t.head[i]);
        }
        printf("\n");
    }
    void main(){
        table t1=initTable();
        for (int i=1; i<=Size; i++) {
            t1.head[i-1]=i;
            t1.length++;
        }
        printf("原顺序表:");
    displayTable(t1);

    printf("\n删除元素:");
    t1=delTable(t1,1);
    displayTable(t1);

    printf("\n在第2位置插入元素5:");
    t1 = addTable(t1,5,2);
    displayTable(t1);

    printf("\n查找元素3的位置:");
    int add=selectTable(t1,3);
    printf("%d",add);

    printf("\n将元素3改为6:");
    t1=amendTabke(t1,3,6);
    displayTable(t1);
    }

注意for(int i;)

输出：

原顺序表:123456
删除元素:23456
在第2位置插入元素5:253456
查找元素3的位置:3
将元素3改为6:256456