C语言数据结构实现-顺序表基本操作

顺序表，全名顺序存储结构，是线性表的一种。通过《什么是线性表》一节的学习我们知道，线性表用于存储逻辑关系为“一对一”的数据，顺序表自然也不例外。

不仅如此，顺序表对数据的物理存储结构也有要求。顺序表存储数据时，会提前申请一整块足够大小的物理空间，然后将数据依次存储起来，存储时做到数据元素之间不留一丝缝隙。

例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如图 1 所示：

由此我们可以得出，将“具有 '一对一' 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。

通过观察图 1 中数据的存储状态，我们可以发现，顺序表存储数据同数组非常接近。其实，顺序表存储数据使用的就是数组。
顺序表的初始化
使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：
顺序表申请的存储容量；
顺序表的长度，也就是表中存储数据元素的个数；
提示：正常状态下，顺序表申请的存储容量要大于顺序表的长度。
因此，我们需要自定义顺序表，C 语言实现代码如下：

typedef struct Table{
    int * head;//存放一块连续空间的内存地址
    int length;//目前已经存放数据长度
    int size;//空间大小
} table;

注意，head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。

接下来开始学习顺序表的初始化，也就是初步建立一个顺序表。建立顺序表需要做如下工作：
给 head 动态数据申请足够大小的物理空间；
给 size 和 length 赋初值；

table initTable(){
    table t;
    t.head = (int *)malloc(LengthSize * sizeof(int));//申请内存
    t.size = LengthSize;
    return t;
}

完整代码如下

#include<stdio.h>
#include<stdlib.h>
#define LengthSize 5
//顺序表操作-其实就是数组操作-数据结果比较简单只是小小是实现下
typedef struct Table{
    int * head;
    int length;
    int size;
} table;
table initTable(){
    table t;
    t.head = (int *)malloc(LengthSize * sizeof(int));//申请内存
    t.size = LengthSize;
    return t;
}
int main(){
    table tt = initTable();
    tt.length=0;
    for(int i=0;i<LengthSize;i++){
        tt.head[i] = i+1;
        tt.length++;
    }
   //addTable(&tt,100,3);
    for(int j=0;j<tt.length;j++){
        printf("%d\n",tt.head[j]);
    }
    return 0;
}

顺序表对应的操作有添加数据、删除数据、查找数据、更改对应位置数据。所有功能代码如下

#include<stdio.h>
#include<stdlib.h>
#define LengthSize 5
//顺序表操作-其实就是数组操作-数据结果比较简单只是小小是实现下
typedef struct Table{
    int * head;
    int length;
    int size;
} table;
table initTable(){
    table t;
    t.head = (int *)malloc(LengthSize * sizeof(int));//申请内存
    t.size = LengthSize;
    return t;
}
//添加
table addTable(table * t , int elem,int addIndex){
    if(addIndex > t->length+1 || addIndex <1){
        printf("is errors");
        exit(0);
    }
    if(t->length == t->size){
        t->head=(int *)realloc(t->head,(t->size+1) * sizeof(int));
        t->size +=1;
        t->length++;
    }
    for(int i = t->length-1;i>=addIndex-1;i--){
        t->head[i+1] = t->head[i];
    }
    t->head[addIndex-1] = elem;
}
//删除
void delTable(table * t, int post){
    for(int i = post -1; i<t->length;i++){
        t->head[i] = t->head[i+1];
    }
    t->length--;
}
//查找
int searchTable(table * t, int elem){
    int pos=-1;
    for(int i = 0;i<t->length;i++){
        if(t->head[i] == elem){
            pos = i+1;
        }
    }
    return pos;    
}
//更改
void changeTable(table * t , int elem, int pos){
    t->head[pos-1]=elem;
}
int main(){
    table tt = initTable();
    tt.length=0;
    for(int i=0;i<LengthSize;i++){
        tt.head[i] = i+1;
        tt.length++;
    }
   //addTable(&tt,100,3);//添加
   //delTable(&tt,3);//删除
    //int s = searchTable(&tt,100);//查找
    //changeTable(&tt,90,3);//修改对应位置

    for(int j=0;j<tt.length;j++){
        printf("%d\n",tt.head[j]);
    }

    return 0;
}