顺序存储结构

在C语言中可以用一维数组来实现顺序存储结构

获取元素操作

　　 判断线性表是否合法

　　 判断位置是否合法

　　 直接通过数组下标的方式获取元素

插入元素算法

　　 判断线性表是否合法

　　 判断插入位置是否合法

　　 把最后一个元素到插入位置的元素后移一个位置

　　 将新元素插入

　　 线性表长度加1

删除元素算法

　　 判断线性表是否合法

　　 判断删除位置是否合法

　　 将元素取出

　　 将删除位置后的元素分别向前移动一个位置

　　 线性表长度减1

代码练习场：

 

先看list.c文件的类型声明：

#include 
     
      #include 
      
       #include "SequenceList.h"typedef struct TSeqList{    Tsize capcity;    Tleng length;    TSeqListNode * node;}TSeqList;
      
     

list.h中的类型声明：

typedef void SeqList;typedef void SeqListNode;

typedef unsigned int TSeqListNode;//很重要，慢慢看下去typedef unsigned int Tsize;typedef unsigned int Tleng;

创建线性表：

/*创建线性表，创建失败返回NULL*/SeqList * SequenceList_Create(Tsize capacity){    TSeqList *ret=NULL;    if (capacity>=0)        {            ret=(SeqList *)malloc(sizeof(TSeqList)+sizeof(TSeqListNode)*capacity);//TSeqListNode类型乘以容量（类型*个数）为需要开辟的大小        }    if(ret!=NULL)        {            ret->capcity=capacity;            ret->length=0;            ret->node=(TSeqListNode *)(ret+1);        }    return ret;}

注意红色部分，ret是指向整个线性表的指针，ret指向一片malloc开辟的内存（如果你对malloc开辟的内存是否是连续的有疑问），ret+1刚好指向node后面紧挨的内存，内存示意图如下：

虽然返回值类型貌似和我们定义ret的类型不一致，但是由于返回的是个void * 类型的指针，所以不管定义ret为何种类型的指针，都可以赋值给void *类型。

销毁线性表：

/*销毁线性表*/void SequenceList_Destroy(SeqList *list){    free(list);}

获取线性表长度：

int SequenceList_Length(SeqList* list) {    TSeqList* sList = (TSeqList*)list;    int ret = -1;        if( sList != NULL )    {        ret = sList->length;    }        return ret;}

获取线性表容量：

 

int SequenceList_Capacity(SeqList* list) {    TSeqList* sList = (TSeqList*)list;    int ret = -1;        if( sList != NULL )    {        ret = sList->capcity;    }        return ret;}

线性表的插入：

 

int SequenceList_Insert(SeqList* list, SeqListNode* node, int pos)  {    TSeqList* sList = (TSeqList*)list;//void *强制转化成线性表指针    int ret = (sList != NULL);    int i = 0;        ret = ret && (sList->length + 1 <= sList->capcity);//要插入，线性表的长度应该小于等于线性表的容量    ret = ret && (0 <= pos);//插入的位置至少是大于等于零的        if( ret )    {        if( pos >= sList->length )//如果插入的位置大于等于线性表的长度，就插入到最后长度处        {            pos = sList->length;        }                for(i=sList->length; i>pos; i--)//线性表从自身长度处一次后移，给pos位置腾出插入空间        {            sList->node[i] = sList->node[i-1];        }                sList->node[i] = (TSeqListNode)node;//形参node指针接收要插入的元素的地址，并将其保存在线性表node指针中。                sList->length++;//插入一个，长度加1    }        return ret;}

获得线性表内容的地址：

 

SeqListNode* SequenceList_Get(SeqList* list, int pos) {    TSeqList* sList = (TSeqList*)list;    SeqListNode* ret = NULL;        if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )    {        ret = (SeqListNode*)(sList->node[pos]);    }        return ret;}

删除元素：

 

SeqListNode* SequenceList_Delete(SeqList* list, int pos) {    TSeqList* sList = (TSeqList*)list;    SeqListNode* ret = SequenceList_Get(list, pos);//得到要删除位置的元素的地址    int i = 0;        if( ret != NULL )    {        for(i=pos+1; i
     
      length; i++)//从删除位置后面开始，一次前移一位        {            sList->node[i-1] = sList->node[i];        }                sList->length--;//删除一个，长度递减    }        return ret;//返回当前删除位置元素的地址}
     

 

main.c:

#include 
     
      #include 
      
       #include "SequenceList.h"int main(int argc, char *argv[]) {    SeqList* list = SequenceList_Create(5);//创建容量为5的线性表        int i = -100;    int j = 99;    int k = 98;    int x = 97;    int y = 96;    int z = 95;    int index = 0;    SequenceList_Insert(list, &i, 0);//插入元素，每次都是插入在0的位置，那么最后的排列顺序和插入顺序刚好相反    SequenceList_Insert(list, &j, 0);    SequenceList_Insert(list, &k, 0);    SequenceList_Insert(list, &x, 0);    SequenceList_Insert(list, &y, 0);        SequenceList_Insert(list, &z, 1000);//只有5个单位的容量，多余的插入不起作用        for(index=0; index
       
         0 )    {        int* p = (int*)SequenceList_Delete(list, 0);//delete的返回值是删除的元素的地址                printf("%d\n", *p);    }        SequenceList_Destroy(list);//释放堆空间        return 0;}
       
      
     

SequenceList.h:

#ifndef _SEQENCELIST_H_#define _SEQENCELIST_H_typedef unsigned int TSeqListNode;//为了存放一个指针强制类型转化后的值typedef unsigned int Tsize;typedef unsigned int Tleng;typedef void SeqList;typedef void SeqListNode;SeqList * SequenceList_Create(Tsize capacity);SeqList  SequenceList_Destroy(SeqList *list);SeqList  SequenceList_Clear(SeqList* list);int  SequenceList_Length(SeqList* list);int  SequenceList_Capacity(SeqList* list);int SequenceList_Insert(SeqList* list, SeqListNode* node, int pos) ;SeqListNode* SequenceList_Get(SeqList* list, int pos);SeqListNode* SequenceList_Delete(SeqList* list, int pos);#endif

运行效果：

 当然也是可以支持输入浮点数的，把插入元素类型换成浮点数，更改如下：

#include 
     
      #include 
      
       #include "SequenceList.h"int main(int argc, char *argv[]) {    SeqList* list = SequenceList_Create(5);//创建容量为5的线性表        double i = -100.100;    double j = 99.99;    double k = 98.98;    double x = 97.97;    double y = 96.96;    double z = 95;    double index = 0;    SequenceList_Insert(list, &i, 0);//插入元素，每次都是插入在0的位置，那么最后的排列顺序和插入顺序刚好相反    SequenceList_Insert(list, &j, 0);    SequenceList_Insert(list, &k, 0);    SequenceList_Insert(list, &x, 0);    SequenceList_Insert(list, &y, 0);        SequenceList_Insert(list, &z, 1000);//只有5个单位的容量，多余的插入不起作用        for(index=0; index
       
         0 )    {        double* p = (double*)SequenceList_Delete(list, 0);//delete的返回值是删除的元素的地址                printf("%f\n", *p);    }        SequenceList_Destroy(list);//释放堆空间        return 0;}
       
      
     

我们插入浮点数就OK，我们的代码是和类型无关的，甚至，你还可以插入结构体。它运行如下：

但是我们切不可犯了低级错误，插入不同类型的元素，比如，你要么插入int类型的，要么插入浮点类型的，不能第一个插入folat，第二个又插入int，这是犯了概念错误，线性表元素类型必须相同。

 

WARNING:

还有，在运行这个代码的时候你的编译器或许会给出警告：

从指针转换为不同大小的整数。我们的编译器是64位的，指针是8个字节，但是我们使用的是typedef unsigned int TSeqListNode;这样一个四个字节的容器来存放8个字节的数据，显然是会出问题的（运行将导致段错误）。但要是你的编译器是32位的则不会出现问题，这也就是为什么我说可能你运行会出现这样的警告。知道了问题所在，那么我们就要改进代码，更改头文件增加如下内容：

 

#define Compiler_64Bit#ifdef  Compiler_32Bit    typedef unsigned int TSeqListNode;//为了存放一个指针强制类型转化后的值#endif#ifdef  Compiler_64Bit    typedef long long TSeqListNode;//为了存放一个指针强制类型转化后的值#endif

 

通过条件编译，选择不同大小的容器存放指针。这样之后（在freertos中经常看到这种用法），使用多少位的编译器对应开启多少位的宏，可移植性得到大大的增强。