顺序表的建立，初始化，插入，删除模板

线性结构：在非空有限集合中，存在唯一“第一个”数据元素，存在唯一“最后一个”数据元素；

                    除此之外的数据元素都存在唯一的前驱，唯一的后继。

线性表：n个元素的有限序列

顺序表：用一组地址连续的存储单元依次存储线性表的数据元素。

 

动态分配存储结构

*elem:表示基地址。

length:顺序表的当前长度。

lisesize:顺序表当前分配的存储空间。

LIST_INIT_SIZE:顺序表存储空间的初始分配量

LISTINCREMENT:当因插入而空间不足时，增加的数据元素空间

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType* elem; int length; int listsize; }SqList;

 

bool InitList_Sq(SqList *L)

C99还提供了一个头文件 <stdbool.h> 定义了bool代表_Bool，true代表1，false代表0。

只要导入 stdbool.h ，就能非常方便的操作布尔类型了。

/*初始化顺序表*/ bool InitList_Sq(SqList *L)//stdbool.h放到头文件目录就可以了。(在新的c语言中) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) { printf("Failed to allocate memory"); exit(0); } L->length=0; L->listsize=LIST_INIT_SIZE; return true; }

 

bool ListInit_Sq(SqList *L,int pos,ElemType e)

//在第i个位置，插入元素e

/*链表的插入*/ bool ListInit_Sq(SqList *L,int pos,ElemType e)//在第i个位置，插入元素e { ElemType *p,*q; //i的合法位置为1~length if(pos<1||pos>L->length+1)//插入位置不合法 { printf("Improper insertion position"); return false; } if(L->length>=L->listsize)//当前空间已满，增加分配 { //这里有个非常好的问题：L->length>=L->listsize，而不是L->length==L->listsize //看到下面主函数的初始赋值，便知道了，它增加容错性 ElemType* newbase;//C语言的标准中变量必须在函数或者块的开始部分进行 声明/定义。 newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) { printf("Failed to allocate memory"); exit(0); } L->elem=newbase; L->listsize+=LISTINCREMENT; } p=&(L->elem[pos-1]); for(q=&(L->elem[L->length-1]);q>=p;q--) *(q+1)=*q; *p=e; L->length++; return true; }

上面，有个很好的东西。

if(L->length>=L->listsize)//当前空间已满，增加分配

这条，判断是否空间已满的判断语句是很好的。

如果，我写成if(L->length==L->listsize)，这样行不。因为每次只能插入一个元素，也行。

但if(L->length>=L->listsize)的容错性更好些。如果程序不注意，是会出现L->length>L->listsize的情况出现的。

比如：

for(i=0;i<15;i++)//这样写，不用插入，可能会导致内存爆掉       {         p=&L.elem[i];         *p=i;         L.length++;     }     if(L.listsize<L.length)//给L.listsize刷新，就不会爆掉了         L.listsize= L.length;

假如，我给链表初始化赋值的时候，忘了刷新 L.listsize，那么可能导致 L.listsize<L.length的情况出现。

而如果紧在后面的是链表的插入，这个问题可以弥补的。

另外看到有的文章，在赋初始值的时候，用插入函数。

不建议这么用，因为在赋初始值的时候，用插入函数，会导致许多无用的移动。

用c语言，不是图个高效嘛。

 

ElemType ListDelete_Sq(SqList *L,int pos,ElemType e)

/*顺序表位置元素的删除*/

/*顺序表元素的删除*/ ElemType ListDelete_Sq(SqList *L,int pos,ElemType e) { //删除顺序表的pos位置（第pos个）的元素，并用e返回其值 ElemType *p,*q; //i的合法位置为1~length if(pos<1||pos>L->length+1)//插入位置不合法 { printf("Improper delete position"); exit(0); } p=&(L->elem[pos-1]); q=&(L->elem[L->length-1]);//q=l->elem+l->length-1; e=*p; for(++p;p<=q;p++) *(p-1)=*p; L->length--; return e; }

 

int LocateElem_Sq(SqList *L,ElemType e)

/*顺序表元素的查找：查找第一个值与e满足的位序*/

/*顺序表元素的查找：查找第一个值与e满足的位序*/ int LocateElem_Sq(SqList *L,ElemType e) { int i=1; ElemType* p=L->elem; for(i,p;i<=L->length&&(*p!=e);p++,i++); if(i<=L->length) return i; else return 0; }

 

void FreeList(SqList *L)

void FreeList(SqList *L) { free(L->elem); }

 

整体的代码：

//顺序表的动态存储模板 //dacao //2018/10/28 #include<stdio.h> #include<stdlib.h>//exit #include<stdbool.h> #define ElemType int #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType* elem; int length; int listsize; }SqList; /*初始化顺序表*/ bool InitList_Sq(SqList *L)//stdbool.h放到头文件目录就可以了。(在新的c语言中) { L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) { printf("Failed to allocate memory"); exit(0); } L->length=0; L->listsize=LIST_INIT_SIZE; return true; } /*链表的插入*/ bool ListInit_Sq(SqList *L,int pos,ElemType e)//在第i个位置，插入元素e { ElemType *p,*q; //i的合法位置为1~length if(pos<1||pos>L->length+1)//插入位置不合法 { printf("Improper insertion position"); return false; } if(L->length>=L->listsize)//当前空间已满，增加分配 { //这里有个非常好的问题：L->length>=L->listsize，而不是L->length==L->listsize //看到下面主函数的初始赋值，便知道了，它增加容错性 ElemType* newbase;//C语言的标准中变量必须在函数或者块的开始部分进行 声明/定义。 newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) { printf("Failed to allocate memory"); exit(0); } L->elem=newbase; L->listsize+=LISTINCREMENT; } p=&(L->elem[pos-1]); for(q=&(L->elem[L->length-1]);q>=p;q--) *(q+1)=*q; *p=e; L->length++; return true; } /*顺序表元素的删除*/ ElemType ListDelete_Sq(SqList *L,int pos,ElemType e) { //删除顺序表的pos位置（第pos个）的元素，并用e返回其值 ElemType *p,*q; //i的合法位置为1~length if(pos<1||pos>L->length+1)//插入位置不合法 { printf("Improper delete position"); exit(0); } p=&(L->elem[pos-1]); q=&(L->elem[L->length-1]);//q=l->elem+l->length-1; e=*p; for(++p;p<=q;p++) *(p-1)=*p; L->length--; return e; } /*顺序表元素的查找：查找第一个值与e满足的位序*/ int LocateElem_Sq(SqList *L,ElemType e) { int i=1; ElemType* p=L->elem; for(i,p;i<=L->length&&(*p!=e);p++,i++); if(i<=L->length) return i; else return 0; } void FreeList(SqList *L) { free(L->elem); } int main() { int i,pos=1; int *p; SqList L; InitList_Sq(&L); for(i=0;i<15;i++)//这样写，不用插入，可能会导致内存爆掉 { p=&L.elem[i]; *p=i; L.length++; } if(L.listsize<L.length)//给L.listsize刷新，就不会爆掉了 L.listsize= L.length; //但是如果用插入来写，在未插入数据地方内存的移动是毫无意义的 //那现在的问题是：如何进行初始化 pos=LocateElem_Sq(&L,13); printf("%d",pos); FreeList(&L); return 0; }

 

顺序表还有很多功能：比如说删除某种元素，具体的可以使用C++中list容器。

为了使得通用性好些：#define   ElemType    int

C语言中，变量必须在函数或者块的开始部分进行 声明/定义。

在C语言标准(C89)没有定义布尔类型，所以C语言判断真假时以0为假，非0为真。

C99还提供了一个头文件 <stdbool.h> 定义了bool代表_Bool，true代表1，false代表0。

只要导入 stdbool.h ，就能非常方便的操作布尔类型了。

 

参考文章：

数据结构——顺序表的基本操作

C语言中实现模板函数小结

C语言中变量定义的位置

C语言的布尔类型