数据结构之顺序表的实现

一、原理

1.定义

顺序表是在计算机中以数组形式保存的。

2.特点

• 在计算机中占用连续的一段内存

• 一旦声明，空间大小一般不变

二、初始化相关操作

包括：

1. 结构体的定义
2. 顺序表的创建
3. 顺序表清空
4. 判断顺序表是否为空

1.结构体定义

即定一个满足顺序表定义的结构体，其中包含 数组、存储长度、总长度。

typedef int elemtype; //将int抽象为elemtype，表明顺序表也可以存储其他类型（如将int改为char） struct list { 	elemtype *list;  	//声明数组用于给顺序表存储数据，等价于以下声明方式 	//elemtype[] list; 	int length; //用于记录顺序表存储的数据长度 	int maxsize; //用于记录顺序表最大长度（即最多存储数据） } 

2.初始化

对顺序表进行初始化，包括分配自定义长度的数组空间，设定存储长度为0，存储长度为规定值

//初始化，传入需要初始化的顺序表和初始化长度 void initlist(struct list *l,int maxsize){   //初始化长度合法性判断   if(maxsize<0){     printf("初始化长度非法!n");     exit(1); //退出程序   }   //对顺序表长度进行赋值   l->maxsize = maxsize;   //根据初始化长度和存储数据类型来动态分配数组   l->list = malloc(sizeof(maxsize*sizeof(elemtype)));   //分配成功判定   if(!l->list){     printf("动态分配存储失败n");     exit(1);   }   //初始化存储数据为0个   l->length = 0; } 

3.清空

将顺序表内容清空，用于某些题目要求或节省空间

//清空，传入需要清空的顺序表 void clearlist(struct list *l){   //判断顺序表是否已经为空   if(l->list!=null){     free(l->list); //释放顺序表中数组内存     l->list = 0;      l->length = 0;     l->maxsize = 0;   } } 

4. 判断是否为空

判断顺序表是否为空，在某些操作之前，先要判断顺序表是否为空，防止出错

int isempty(struct list *l){   return l->length==0?1:0; //顺序表最大长度为0则为空返回1，否则返回0 } 

三、增加相关操作

包括：

1. 向表头插入元素x
2. 向表尾插入元素x
3. 向第n个位置插入元素x
4. 向递增的线性表中插入元素x，之后仍然保持有序

进行操作之前，还需要一个方法，当插入元素超过数组长度时，将数组容量扩大，即重新申请空间

tip:将顺序表扩大一倍空间

void remalloc(struct list *l){ 	elemtype *p = realloc(l->list,2*l->maxsize*sizeof(elemtype));   if(!p){     printf("空间分配失败n");     exit(1);   }   l->list = p; //使list重新指向新生成的空间   l->maxsize = 2*l->maxsize;   printf("存储空间已经扩大为2倍n"); }	 

1.向表头插入元素x

void insertelemtohead(struct list *l,elemtype x){   int i;   //判断存储空间是否已满 	if(l->length==l->maxsize){     printf("存储空间已满，重新分配中...");     remalloc(l);   }   //所有元素后移   for(i=l->length;i>0;i--){     l->list[i+1]=l->list[i];   }   l->list[i]=x;   l->length++; } 

2.向表尾插入元素x

void insertelemtotail(struct list *l,elemtype x){ 	 //判断存储空间是否已满 	if(l->length==l->maxsize){     printf("存储空间已满，重新分配中...");     remalloc(l);   }   l->list[l->length++]=x; } 

3.向线性表l的第n个位置插入元素x

void insertelemsomewhere(struct list *l,elemtype x,int n){    //判断存储空间是否已满    if(l->length==l->maxsize){    printf("存储空间已满，重新分配中...");    remalloc(l);  }  int i;  for(i=l->length;i>=n;i--){  	l->list[i] = l->list[i-1];  }  l->list[i] = x;  l->length--; } 

四、删除相关操作

包括：

1. 删除表头元素并返回被删除的值

2. 删除第n个元素并返回被删除元素

3. 从线性表l中删除值为x的第一个元素

1.删除表头元素并返回被删除的值

删除表头第一个元素，长度减少1，返回被删除的值

elemtype delheadelem(struct list *l){ 	elemtype x = l->list[0]; 	//合法性判断 	if(l->length==0){ 		 printf("线性表为空，不能删除n");      exit(1); 	} 	for(int i=0;i<l->length;i++){ 		l->list[i] = l->list[i+1]; 	} 	l->length--; 	return x; } 

2.删除第n个元素并返回被删除元素

elemtype delsomeelem(struct list *l,int n){   if(n<l->length){     printf("n位置越界，不能删除");     exit(1);   }   elemtype x = l->list[n-1];   for(int i=n;i<l->length;i++){     l->list[i]=l->list[i+1];   }   l->length--;   retur x; } 

3.从线性表l中删除值为x的第一个元素

从线性表l中删除值为x的第一个元素，若删除成功则返回1，否则返回0

int delelemknown(struct list *l,elemtype x){ 	int i,j;   //先找出值为x的下标   for(i=0;i<l->length;i++){     if(l->list[i]==x){       break;     }   }   for(j=i;i<l->length;j++){     l->list[j]=l->list[j+1];   }   l->length--;   return 1; } 

五、修改相关操作

包括：

1. 把线性表中第n个元素修改为x

1.把线性表中第n个元素修改为x

把线性表中第n个元素修改为x，若成功则返回1，失败返回0 

int updateelemknown(struct list *l,elemtype x,int n){ 	if(n>l->length||n<1){     return 0;   }   l->list[n]=x;   return 1; } 

六、查找相关操作

包括：

1. 查找第n个位置的值

2. 顺序遍历输出所有值

3. 返回值等于x的下标

1.查找第n个位置的值

输入要查找的坐标，若合法则范围对应的值，若非法则提示并推出

int getelem(struct list *l,int n){   if(n<0||n>l->maxsize){     printf("查找位置超出长度!n");     exit(1);   }   return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数，而数组是从0开始计数 } 

2.顺序遍历输出所有值

输出顺序表中的所有值

void getall(struct list *l){ 	int i = 0; 	while(i<l->length){ 		printf(l->list[i]+"t"); 		i++; 	} 	printf("n"); } 

3.查找值为x的节点并返回其坐标

输入要查找的值x，若存在则范围首次出现的下标，否则返回0

void findelem(struct list *l,elemtype x){ 	int i; 	for(i=0;i<l->length;i++){ 		if(l->list[i]==x){ 			return i; 		} 	} } 

七、总结

1.优点

• 查找方便
• 空间利用率高

2.缺点

• 删除和增加操作效率低
• 空间固定，不易扩展

八、完整代码

#include "stdio.h" #include <stdlib.h> /**  * =======顺序表的定义=========  */ typedef int elemtype; //结构体定义 struct list{     elemtype *list;//存储数据     int length;//存储长度     int maxsize;//最大长度 };  //初始化 void initlist(struct list *l,int maxsize){     //初始化长度合法性判断     if(maxsize<0){         printf("初始化长度非法!n");         exit(1); //退出程序     }     l->maxsize = maxsize;     l->list = malloc(sizeof(maxsize* sizeof(elemtype)));     //判断分配空间是否成功     if(!l->list){         printf("空间分配失败");         exit(1);     }     l->length=0; }  //清空 void clearlist(struct list *l){     if(l->list!=null){         free(l->list);         l->list=0;         l->maxsize=0;         l->length=0;     } }  //判空 int isempty(struct list *l){     return l->length==0?1:0; }  /**  * =======增加操作=========  */  //空间再分配 void remalloc(struct list *l){     elemtype *p = realloc(l->list,2*l->maxsize* sizeof(elemtype));     if(!p){         printf("空间分配失败");         exit(1);     }     l->list = p;     l->maxsize = 2*l->maxsize;     printf("空间已扩大两倍"); }  //向表头插入元素 void insertelemtohead(struct list *l,elemtype x){     if(l->length==l->maxsize){         remalloc(l);         printf("空间已满，重新分配中");     }     for(int i=l->length;i>0;i++){         l->list[i-1] = l->list[i];     }     l->list[0] = x;     l->length++; }  //向表尾插入元素 void insertelemtotail(struct list *l,elemtype x){     if(l->length==l->maxsize){         remalloc(l);         printf("空间已满，重新分配中");     }     l->list[l->length++] = x; }  //向线性表l的第n个位置插入元素x void insertelemsomewhere(struct list *l,elemtype x,int n){     int i;     if(l->length==l->maxsize){         remalloc(l);         printf("空间已满，重新分配中");     }     for(i=l->length;i>=n;i--){         l->list[i]=l->list[i-1];     }     l->list[i]=x;     l->length++; }  /**  * =======删除操作=========  */  //删除表头元素并返回被删除的值 void delheadelem(struct list *l){     elemtype x = l->list[0];     if(l->length==0){         printf("顺序表为空，删除失败!");         exit(1);     }     for(int i=1;i<l->length;i++){         l->list[i-1] = l->list[i];     }     l->length--; }  //删除第n个元素并返回被删除元素 elemtype delsomeelem(struct list *l,int n){     elemtype x = l->list[n-1];     if(n>l->length){         printf("n位置越界，不能删除");         exit(1);     }     for(int i=n;i<l->length;i++){         l->list[i-1] = l->list[i];     }     l->length--;     return x; }  //从线性表l中删除值为x的第一个元素 int delelemknown(struct list *l,elemtype x){     int i,j;     for(i=0;i<l->length;i++){         if(l->list[i]==x){             break;         }     }     for(j=i;j<l->length;j++){         l->list[j]=l->list[j+1];     }     l->length--;     return 1; }  /**  * =======修改操作=========  */ //把线性表中第n个元素修改为x int updateelemknown(struct list *l,elemtype x,int n){     if(n>l->length||n<1){         return 0;     }     l->list[n]=x;     return 1; }  /**  * =======查找操作=========  */  //查找第n个位置的值  int getelem(struct list *l,int n){      if(n<0||n>l->maxsize){          printf("查找位置超出长度!n");          exit(1);      }      return l->list[n-1]; //n-1的原因是查找的第n个是从1开始计数，而数组是从0开始计数  }   //顺序遍历输出所有值  void getall(struct list *l){      int i = 0;      while(i<l->length){          printf("%dt",l->list[i]);          i++;      }      printf("n");  } //查找值为x的节点并返回其坐标 int findelem(struct list *l,elemtype x){     int i;     for(i=0;i<l->length;i++){         if(l->list[i]==x){             return i;         }     } }  //主函数 int main() {      //初始化操作测试     struct list l;     initlist(&l,20);     //插入操作测试     insertelemtohead(&l,2);     insertelemsomewhere(&l,4,2);     insertelemtotail(&l,5);     printf("%dn",l.list[0]);     printf("%dn",l.list[1]);     //删除操作测试     delelemknown(&l,2);     printf("%dn",l.list[0]);     //修改操作测试     updateelemknown(&l,8,1);     //查找操作测试     printf("%dn",getelem(&l,2));     printf("%dn",findelem(&l,8));     printf("%dn",l.list[0]);     getall(&l); }