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

阳光穿透心脏的1/2处 2022-05-14 15:22 200阅读 0赞

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

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

线性表：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 ，就能非常方便的操作布尔类型了。

参考文章：

[数据结构——顺序表的基本操作][Link 1]

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

[C语言中变量定义的位置][C 1]

[C语言的布尔类型][C 2]

[Link 1]: https://blog.csdn.net/ada_73/article/details/77855646
[C]: https://blog.csdn.net/immcss/article/details/6408851
[C 1]: https://blog.csdn.net/zhanghuaichao/article/details/48207201?locationNum=1&fps=1
[C 2]: https://www.cnblogs.com/pharen/archive/2012/02/06/2340257.html