线性表的顺序存储结构

线性表的顺序存储结构有点类似于数组的样子，它在内存中的地址是连续的，也正是因为如此，它的插入，删除需要移动大量的元素，因为元素与元素之间是紧贴在一起的。

下面上一张图来表示它的样子
有点丑
它的基本操作包括创建，插入，删除，取元素（get），求长度，求容量（二者区别：容量即是实际申请的大小，长度是元素实际所占据的大小，比如我们申请容量是10，但只插入5个元素，那么他的容量是10，长度是5。），清空，销毁等基本操作。

下面我们逐一来看这些基本API：

创建
创建操作结合上图理解,首先申请一个红色方框（TSeqList），然后申请红框中的node域，用来指向capacit y大小的空间，用以存放数据，如此，创建操作完成。

 SeqList* SeqList_Creat(int capacity)
 {
     int ret = 0;
     TSeqList *tmp;

 tmp = (TSeqList *)malloc(sizeof(TSeqList));
 if(tmp == NULL)
 {
     ret = -2;
     printf("func SeqList_Creat err:%d",ret);
     return NULL;
 }
 memset(tmp,0,sizeof(TSeqList));

 //根据capacity的大小分配节点空间
 tmp->node = (unsigned int*)malloc(sizeof(unsigned int*)*capacity);
 if(tmp->node == NULL)
 {
     ret = -2;
     printf("func SeqList_Creat malloc err:%d",ret);
     return NULL;
 }

 tmp->capacity = capacity;
 tmp->length = 0;
 return tmp;

}

插入
插入操作：首先确定要插入的位置，然后将node所指向空间中要插入位置后的元素逐个后移，再将元素插入进去，length ++。

int Seqlist_Insert(SeqList* list,SeqListNode* node,int pos)
{
    int i = 0,ret = 0;
    TSeqList* tlist = NULL;
    
   if(list == NULL || node == NULL || pos < 0)
    {
        ret = -1;
        printf("func Seqlist_Insert err:%d",ret);
        return ret;
    }
    tlist = (TSeqList* )list;

   //判断是不是满了
    if(tlist->length >= tlist->capacity)
    {
        ret = -2;
        printf("func Seqlist_Insert err:%d",ret);
        return ret;
            }

   //容错修正
    if(pos>=tlist->length)
    {
        pos = tlist->length;
    }

   //1元素后移
    for(i = tlist->length;i>pos;i--)
    {
        tlist->node[i] = tlist->node[i-1];
        //a[7] = a[6]
    }

   //2插入元素
    tlist->node[i] = *(unsigned int*)node;
    tlist->length ++;
    return 0;
}

删除
删除操作与插入类似，1确定要删除位置，2要删除位置之后元素前移，3, length --。

	SeqListNode* Seqlist_Delete(SeqList* list,int pos)
{
    int i = 0;
    int ret = 0;
    SeqListNode* p = NULL;
    TSeqList* tlist = NULL;
    
    tlist = (TSeqList* )list;
    if(list == NULL ||  pos < 0)
    {
        ret = -1;
        printf("func Seqlist_Insert err:%d",ret);
        return NULL;
    }


    p = (SeqList*)&tlist->node[pos]; //缓存pos位置

    for(i = pos+1;i<tlist->length;i++)
    {
        tlist->node[i-1] = tlist->node[i];
    }
    tlist->length --;
    return p;
}

取元素
比较简单直接返回pos位置元素，注意这里返回的是一个地址，后面会强制类型转换，再取其中的数据。

SeqListNode* SeqList_Get(SeqList* list,int pos)
{
    int i = 0;
    int ret = 0;
    SeqListNode* p = NULL;
    TSeqList* tlist = NULL;
    
tlist = (TSeqList* )list;
if(list == NULL ||  pos < 0)
{
    ret = -1;
    printf("func Seqlist_Insert err:%d",ret);
    return NULL;
}


p =(void *) &tlist->node[pos];
return p;

}

求长度
由于之前的每次操作后长度及容量变化都记录在TSeqList中的length域和capacity域中，所以这里直接返回就可以。

int SeqList_Length(SeqList* list)
{
    TSeqList* tlist = NULL;
    tlist = (TSeqList*)list;
    if(tlist == NULL)
    {
        return -1;
    }



return tlist->length;
}

求容量
直接返回，无需多言。

int SeqList_Capacity(SeqList* list)
{
    TSeqList* tlist = NULL;
    
tlist = (TSeqList*)list;
if(tlist == NULL)
{
    return -1;
}



return tlist->capacity;
}

清空
使顺序表回到初始状态，所以直接将length变为0。需要注意，这里node所指向的数据并没有抹去，只是length = 0 后我们认为其中的数据都不存在了，后续可以覆盖，读取时也只会读取length以内的有效数据。

void SeqList_Clear(SeqList* list)
{
    TSeqList* tlist = NULL;
    tlist = (TSeqList*)list;
    
if(tlist == NULL)
{
    return ;
}


tlist->length = 0;
return ;
}

销毁
free掉list指针和TSeqList中的node指针即可。

void SeqList_Destory(SeqList* list)
{
    TSeqList* tlist = NULL;

tlist = (TSeqList*)list;
if(tlist == NULL)
{
    return ;
}

if(tlist->node != NULL)
{
    free(tlist->node);
}

free(tlist);
return ;

}

直接上完整源码，大家自己调试理解。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
typedef void SeqList;
typedef void SeqListNode;
typedef struct teacher
{
    int age;
    char name[64];
}Teacher;
typedef struct _tag_SeqList
{
    int length;
    int capacity;
    unsigned int *node;// int *node[] 此处是一个指针数组

}TSeqList;

SeqList* SeqList_Creat(int capacity)
{
    int ret = 0;
    TSeqList *tmp;

tmp = (TSeqList *)malloc(sizeof(TSeqList));
if(tmp == NULL)
{
    ret = -2;
    printf("func SeqList_Creat err:%d",ret);
    return NULL;
}
memset(tmp,0,sizeof(TSeqList));

//根据capacity的大小分配节点空间
tmp->node = (unsigned int*)malloc(sizeof(unsigned int*)*capacity);
if(tmp->node == NULL)
{
    ret = -2;
    printf("func SeqList_Creat malloc err:%d",ret);
    return NULL;
}

tmp->capacity = capacity;
tmp->length = 0;
return tmp;
}

void SeqList_Destory(SeqList* list)
{
    TSeqList* tlist = NULL;

tlist = (TSeqList*)list;
if(tlist == NULL)
{
    return ;
}

if(tlist->node != NULL)
{
    free(tlist->node);
}

free(tlist);
return ;
}

//清空顺序表回到初始状态
void SeqList_Clear(SeqList* list)
{
    TSeqList* tlist = NULL;
    tlist = (TSeqList*)list;

if(tlist == NULL)
{
    return ;
}


tlist->length = 0;
return ;
}

int SeqList_Length(SeqList* list)
{
    TSeqList* tlist = NULL;
    tlist = (TSeqList*)list;
    if(tlist == NULL)
    {
        return -1;
    }



return tlist->length;
}

int SeqList_Capacity(SeqList* list)
{
    TSeqList* tlist = NULL;
    
tlist = (TSeqList*)list;
if(tlist == NULL)
{
    return -1;
}



return tlist->capacity;
}

int Seqlist_Insert(SeqList* list,SeqListNode* node,int pos)
{
    int i = 0,ret = 0;
    TSeqList* tlist = NULL;

if(list == NULL || node == NULL || pos < 0)
{
    ret = -1;
    printf("func Seqlist_Insert err:%d",ret);
    return ret;
}
tlist = (TSeqList* )list;

//判断是不是满了
if(tlist->length >= tlist->capacity)
{
    ret = -2;
    printf("func Seqlist_Insert err:%d",ret);
    return ret;
    
}

//容错修正
if(pos>=tlist->length)
{
    pos = tlist->length;
}

//1元素后移
for(i = tlist->length;i>pos;i--)
{
    tlist->node[i] = tlist->node[i-1];
    //a[7] = a[6]
}

//2插入元素
tlist->node[i] = *(unsigned int*)node;
tlist->length ++;
return 0;
}

SeqListNode* SeqList_Get(SeqList* list,int pos)
{
    int i = 0;
    int ret = 0;
    SeqListNode* p = NULL;
    TSeqList* tlist = NULL;
    
tlist = (TSeqList* )list;
if(list == NULL ||  pos < 0)
{
    ret = -1;
    printf("func Seqlist_Insert err:%d",ret);
    return NULL;
}


p =(void *) &tlist->node[pos];
return p;

}

SeqListNode* Seqlist_Delete(SeqList* list,int pos)
{
    int i = 0;
    int ret = 0;
    SeqListNode* p = NULL;
    TSeqList* tlist = NULL;

tlist = (TSeqList* )list;
if(list == NULL ||  pos < 0)
{
    ret = -1;
    printf("func Seqlist_Insert err:%d",ret);
    return NULL;
}


p = (SeqList*)&tlist->node[pos]; //缓存pos位置

for(i = pos+1;i<tlist->length;i++)
{
    tlist->node[i-1] = tlist->node[i];
}
tlist->length --;
return p;
}
int main()
{
    int ret,i;
    Teacher t1,t2,t3,t4,t5;
    SeqList* list;
    t1.age = 31;
    t2.age = 32;
    t3.age = 33;
    t4.age = 35;
    t5.age = 36;

list = SeqList_Creat(10);
if(list == NULL)
{
    ret = -1;
    printf("func SeqList_Creat err:%d",ret);
    return 0;
}

Seqlist_Insert(list,(SeqListNode*)&t1,0); //头插法
Seqlist_Insert(list,(SeqListNode*)&t2,0); //头插法
Seqlist_Insert(list,(SeqListNode*)&t3,0); //头插法
Seqlist_Insert(list,(SeqListNode*)&t4,0); //头插法
Seqlist_Insert(list,(SeqListNode*)&t5,0); //头插法


//printf("length = %d",SeqList_Length(list));
//遍历
for(i = 0;i<SeqList_Length(list);i++)
{
    Teacher *tmp = (Teacher *)SeqList_Get(list,i);
    if(tmp == NULL)
    {
        return 0;
    }
    printf("tmp->age:%d\n",tmp->age);
}

//删除元素
while(SeqList_Length(list)>0)
{
    Seqlist_Delete(list,0);
}

printf("length = %d\n",SeqList_Length(list));

printf("capacity = %d\n",SeqList_Capacity(list));


return 0;
}