使用C语言实现动态顺序表

目录

1.顺序表的定义

2.申请空间

 （1）申请空间的方式一

（2）申请空间的方式二

3.动态顺序表的定义

4.动态顺序表的相关操作

（1）初始化

（2）申请空间

（3）顺序表的判空和判满

（4）顺序表的插入和定位插入元素

（5）定位删除元素和按值删除元素

（6）删除表和打印

（7）主函数

（8）测试

---

1.顺序表的定义

用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系又存储的邻接关系体现。

注：之所以要提出动态顺序表，是因为如果使用静态顺序表的话，空间上很容易就处于满的状态，但是如果一下子申请很大的空间的话，那么会造成空间上的浪费，所以根据需要申请空间的大小是必要的。

使用C语言实现静态顺序表

2.申请空间

 （1）申请空间的方式一

	ElemType *p=L.data;
	L.data=(ElemType*)malloc((L.MaxSize+len)*sizeof(ElemType));
	for(int i=0;i<L.length;i++){
		L.data[i]=p[i];
	} 
	L.MaxSize=L.MaxSize+len;
	free(p);

（2）申请空间的方式二

ElemType *newBase=(ElemType*)realloc(L.data,(L.MaxSize+len)*sizeof(ElemType));
L.data=newBase;
L.MaxSize+=len; 

3.动态顺序表的定义

#include<stdlib.h>
#include<stdio.h>
 
#define MAXSIZE 5
 
typedef int ElemType; 
 
typedef struct {
	ElemType*data;
	int length;
	int MaxSize;
}SqList;

4.动态顺序表的相关操作

（1）初始化

//顺序表的初始化
void InitSqList(SqList&L){
	L.data=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));
	L.MaxSize=MAXSIZE;
	L.length=0;
}

（2）申请空间

//增加顺序表的容量
void IncreaseSize(SqList&L,int len){
	//定义方式一
//	ElemType *p=L.data;
//	L.data=(ElemType*)malloc((L.MaxSize+len)*sizeof(ElemType));
//	for(int i=0;i<L.length;i++){
//		L.data[i]=p[i];
//	} 
//	L.MaxSize=L.MaxSize+len;
//	free(p);
	//方式二
	ElemType *newBase=(ElemType*)realloc(L.data,(L.MaxSize+len)*sizeof(ElemType));
	L.data=newBase;
	L.MaxSize+=len; 
} 

（3）顺序表的判空和判满

//操作清单
void MenuSqList(){
	printf("-------------1.插入操作-------------\n");
	printf("-------------2.定位插入操作---------\n");
	printf("-------------3.查找操作-------------\n");
	printf("-------------4.定位删除操作---------\n");
	printf("-------------5.按值删除元素---------\n");
	printf("-------------6.删除整个顺序表-------\n"); 
	printf("-------------7.打印操作-------------\n");
	printf("-------------8.结束操作-------------\n");
} 
 
//判断顺序表是否空 
bool IsEmpty (SqList L){
	if(L.length<=0){
		return true;
	}else {
		return false;
	}
}
//判断顺序表是否为满 
bool IsFull(SqList L){
	if(L.length>=L.MaxSize){
		return true;
	}else{
		return false;
	}
}

（4）顺序表的插入和定位插入元素

//顺序表的插入操作
void ListInsert(SqList&L,ElemType e) {
	if(IsFull(L)){
		printf("顺序表已满!\n");
		return ;
	}
	L.data[L.length]=e;
	L.length++;
} 
//定位向顺序表中插入数据 
void ListInsertLocate(SqList&L,int i,ElemType e){
	if(i<0||i>L.length+1){ 
		printf("输入的插入元素位置不合法\n");
		return ;
	}
	if(L.length>=L.MaxSize){
		printf("存储空间已满!\n");
		printf("请输入申请的空间大小: ");
		int len=0;
		scanf("%d",&len);
		IncreaseSize(L,len);
		printf("申请空间成功,目前空间大小: %d\n",L.MaxSize);
		return ;
	}
	for(int j=L.length;j>=i;j--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
}

（5）定位删除元素和按值删除元素

//定位删除操作
void DeleteElemType(SqList&L,int i,ElemType&e){
	if(i<0||i>L.length+1){ 
		printf("输入的插入元素位置不合法\n");
		return ;
	}
	e=L.data[i-1];
	for(int j=i-1;j<L.length;j++){
		L.data[j]=L.data[j+1];
	}
	L.length--;
} 
//顺序表按值删除（删除第一个元素为e的值） 
void DeleteElem(SqList&L,ElemType&e) {
	int index=0;
	for(int i=0;i<L.length;i++){
		if(L.data[i]==e){
			index=i;
			break;
		}
	}
	for(int j=index;j<L.length;j++){
		L.data[j]=L.data[j+1];
	}
	L.length--;
}

（6）删除表和打印

//删除顺序表
void DeleteSqList(SqList&L){
	for(int i=0;i<L.length;i++){
		L.data[i]=0;
	}
	L.length=0;
} 
 
//顺序表的打印操作
void PrintSqList(SqList L){
	for(int i=0;i<L.length;i++){
		printf("%d\t",L.data[i]);
	}
	printf("\n");
} 

（7）主函数

int main() {
	SqList L;
	//对顺序表进行初始化
	InitSqList(L);
	//对顺序表进行插入操作
	ElemType x;
	int flag=-1;
	//各种操作 
	while(1) {
		int i=0;
		ElemType e=0;
		MenuSqList();
		printf("请输入操作: ");
		scanf("%d",&flag);
		switch(flag){
			case 1:
				printf("请输入元素(-1_end): ");
				scanf("%d",&x);
				i=1;
				while(x!=-1) {
					ListInsert(L,x);
					printf("请输入元素(-1_end): ");
					scanf("%d",&x);
					i++;
					if(i>=L.MaxSize+1){
						printf("存储空间已满!\n");
						break;
					}
				} 
				break;
			case 2:
				printf("请输入元素插入位置: \n");
				scanf("%d",&i); 
				printf("请输入元素: ");
				scanf("%d",&x);
				ListInsertLocate(L,i,x);
				break;
			case 3:
				printf("请输入查找元素位置: ");
				scanf("%d",&i);
				if(i<0||i>=L.length+1){
					printf("输入的查找元素位置不合法!\n");
					break;
				}
				printf("Elem = %d\n",L.data[i-1]);
				printf("删除元素成功!\n");
				break;
			case 4:
				printf("请输入删除的定位位置: ");
				scanf("%d",&i);
				DeleteElemType(L,i,e);
				printf("删除成功元素=%d\n",e);
				break;
			case 5:
				printf("请输入要删除的元素: ");
				scanf("%d",&e);
				DeleteElem(L,e);
				break;
			case 6:
				DeleteSqList(L);
				printf("删除成功!\n");
				break;
			case 7:
				PrintSqList(L);
				break;
			default:
				printf("结束操作\n");
		}
		if(flag==8){
			break;
		}
	}
	return 0;
}

（8）测试