学习记录：第二章 线性表的顺序存储-顺序表的插入删除查找三种基本 *** 作（代码、图示、C++）

文章目录

• 前言
• 一、顺序表的插入 *** 作
• 二、顺序表的删除 *** 作
• 三、顺序表的查找 *** 作
• • 1. 按位查找
  • 2. 按值查找
• 总结（需要注意）

---

前言

本文给出了顺序表的插入、删除、查找（按位、按值查找）三种基本 *** 作的代码及相应图示助于理解，代码实现使用的是C语言在线工具。无概念解释，初学者建议配合书本食用。
【如果图片看不清楚，网页版是很清晰的。😦】

---

一、顺序表的插入 *** 作

#include 
#define MaxSize 10
typedef struct{
	int data[MaxSize];  	//用静态的“数组”存放数据元素
	int length;  			//顺序表当前长度
}SqList;  					//顺序表类型定义

//基本 *** 作——初始化一个顺序表
void InitList(SqList &L){
	for(int i = 0; i<MaxSize; i++)
		L.data[i] = 0; 	 	//将所有数据元素设置为默认初始值
	L.length = 0;  			//顺序表初始长度为0 ！！！！这步很重要！！！！
}

//基本 *** 作——往顺序表中位序为i的位置插值
void ListInsert(SqList &L, int i, int e){
	for(int j=L.length;j>=i;j--)  	//将第i个元素及之后的元素后移
		L.data[j] = L.data[j-1]; 	//注意位序和数组下标的关系：i和j的关系
	L.data[i-1]=e;  				//在位置i处放入e：data数组的下标是位序i减1
	L.length++;  					//长度加1
}

int main(){
	SqList L;  					//声明一个顺序表
	InitList(L);  				//初始化顺序表
	for(int i = 0; i<5; i++){	//设置顺序表前5个元素的值
		L.data[i] = i;  
		L.length++;
	}
	ListInsert(L, 3, 999);		//往位序为3的位置插值
	for(int i = 0; i<L.length; i++)	//打印整个data数组
		printf("data[%d] = %d\n", i, L.data[i]);
	return 0;
}

在这里，定义的顺序表长度为10，设置前5个元素的值分别是0、1、2、3、4，往位序为3的位置插入值999，运行结果如下：

但是代码还有不完善的地方，好的代码应该具有健壮性。我们这里的顺序表最大长度为10，实际长度为5，往3的位置插值可以成功，那么往8的位置插值呢？最大长度为10，实际长度也为10的情况下再插值呢？当 i 超出顺序表长度的有效范围，或者存储空间已满，理论上这就不能继续插值了，但实际上结果如下：

因此需要修改代码，使得在 “ i 不在有效范围内” 或者 “当前存储空间已满” 的情况下不能继续插值。我们只需要修改ListInsert这段代码：

//基本 *** 作——往顺序表位序为i的位置插值
bool ListInsert(SqList &L, int i, int e){
	if(i<1 || i>L.length+1)  			//判断i的范围是否有效
		return false;
	if(L.length>=MaxSize)  				//当前存储空间已满，不能插入
		return false;
	for(int j=L.length;j>=i;j--)  		//将第i个元素及之后的元素后移
		L.data[j] = L.data[j-1]; 		//注意位序和数组下标的关系
	L.data[i-1]=e;  					//在位置i处放入e
	L.length++;  						//长度加1
	return true;
}

修改后再往8的位置插值结果如下：

二、顺序表的删除 *** 作

#include 
#define MaxSize 10
typedef struct{
	int data[MaxSize];    //用静态的“数组”存放数据元素
	int length;           //顺序表当前长度
}SqList;                  //顺序表类型定义

//基本 *** 作——初始化一个顺序表
void InitList(SqList &L){
	for(int i = 0; i<MaxSize; i++)
		L.data[i] = 0;    //将所有数据元素设置为默认初始值
	L.length = 0;         //顺序表初始长度为0 ！！！！这步很重要！！！！
}

//基本 *** 作——在顺序表中删除位序为i的值
bool ListDelete(SqList &L, int i, int &e){  //注意这里&e是引用类型，
	if(i<1 || i>L.length)         //判断i的范围是否有效
		return false;
	e = L.data[i-1];              //将被删除的元素赋值给e
	for(int j=i; j<L.length; j++) //将第i个元素及之后的元素前移
		L.data[j-1] = L.data[j];  //注意位序和数组下标的关系
	L.length--;                   //长度减1
	return true;
}

int main(){
	SqList L;           		//声明一个顺序表
	InitList(L);   				//初始化顺序表
	for(int i = 0; i<5; i++){	//设置顺序表前5个元素的值
		L.data[i] = i;  
		L.length++;
	}
	int i = 8;
	int e = -1;    			   	//用变量e把删除位置的元素“带回来”,e初始值为-1
	if(ListDelete(L, i, e))
		printf("已删除第%d个元素，删除元素的值为e=%d\n", i, e);
	else
		printf("位序%d不合法，删除失败\n", i);
	printf("\n打印整个顺序表\n");
	for(int i = 0; i<L.length; i++)	//打印整个data数组
		printf("data[%d] = %d\n", i, L.data[i]);
	return 0;
}

在这里，定义的顺序表长度为10，设置前5个元素的值分别是0、1、2、3、4，删除3的位置的值，运行结果如下：

这个代码已经加强过健壮性了，因此在 i 不在有效范围内的情况下，比如删除位序为8的元素的值，运行结果如下：

三、顺序表的查找 *** 作 1. 按位查找

按位查找：获取表L中第i个位置的元素的值，并返回这个值。
由于顺序表的各个元素在内存中连续存放，因此可以根据 [起始地址] 和 [数据元素大小] 立即找到第 i 个元素，这也是顺序表的 “随机存取” 的特性。

顺序表按位查找（动态分配）的代码为：

#include 
#include 
#define InitSize 10				//顺序表的初始长度

typedef struct{
	int *data;					//指示动态分配数组的指针，data指向分配空间的首地址
	int MaxSize;				//顺序表的最大容量
	int length;					//顺序表的当前长度
}SeqList;						//顺序表的类型定义【动态分配方式】

//基本 *** 作——按位查找，获取表L中第i个位置的元素的值
int GetElem(SeqList L, int i){
	return L.data[i-1];			//返回查找位置的元素的值		
}

//基本 *** 作——初始化一个顺序表
void InitList(SeqList &L){
	L.data = (int *)malloc(InitSize*sizeof(int));	//用malloc函数申请一片连续的内存空间
	L.length = 0;  									//顺序表初始长度为0
	L.MaxSize = InitSize;
}

int main(){
	SeqList L;           		//声明一个顺序表
	InitList(L);   				//初始化顺序表
	for(int i = 0; i<5; i++){	//设置顺序表前5个元素的值
		L.data[i] = i;  
		L.length++;
	}
	int i = 3;
	for(int i = 0; i<L.length; i++)	//打印整个顺序表
		printf("data[%d] = %d\n", i, L.data[i]);
	printf("表L的第%d个位置的元素值为%d\n", i, GetElem(L, i));
	return 0;
}

在这里，定义的顺序表初始长度为10，设置前5个元素的值分别是0、1、2、3、4，查找位序为3的元素的值，运行结果如下：

2. 按值查找

按值查找：获取表L中第一个元素值等于e的元素，并返回其位序。
顺序表按值查找（动态分配）的代码为：

#include 
#include 
#define InitSize 10				//顺序表的初始长度

typedef struct{
	int *data;					//指示动态分配数组的指针，data指向分配空间的首地址
	int MaxSize;				//顺序表的最大容量
	int length;					//顺序表的当前长度
}SeqList;						//顺序表的类型定义【动态分配方式】

//基本 *** 作——按值查找，获取表L中第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, int e){
	for(int i=0; i<L.length; i++)
		if(L.data[i] == e)  
			return i+1;
	return 0;
}

//基本 *** 作——初始化一个顺序表
void InitList(SeqList &L){
	L.data = (int *)malloc(InitSize*sizeof(int));	//用malloc函数申请一片连续的内存空间
	L.length = 0;  									//顺序表初始长度为0
	L.MaxSize = InitSize;
}

int main(){
	SeqList L;           		//声明一个顺序表
	InitList(L);   				//初始化顺序表
	for(int i = 0; i<5; i++){	//设置顺序表前5个元素的值
		L.data[i] = i;  
		L.length++;
	}
	int e = 3;
	for(int i = 0; i<L.length; i++)	//打印整个顺序表
		printf("data[%d] = %d\n", i, L.data[i]);
	printf("表L的第一个元素值为%d的元素位序为%d\n", e, LocateElem(L, e));
	return 0;
}

在这里，定义的顺序表初始长度为10，设置前5个元素的值分别是0、1、2、3、4，查找值为3的元素的位序，运行结果如下：

---

总结（需要注意）

• 数组下标从0开始，顺序表位序从1开始
• 往顺序表位序为 i 的位置插值时，i 之后的元素要后移
• 在顺序表位序为 i 的位置删值时，i 之后的元素要前移
• 插值时 i 的有效范围是[1, length+1]
• 删值时 i 的有效范围是[1, length]
• 插值函数bool ListInsert(SqList &L, int i, int e)是把e插到 i 这个位置，e是从main函数传入ListInsert函数的参数
• 删值函数bool ListDelete(SqList &L, int i, int &e)是把要删除的 i 这个位置的值赋给e，再由e “带回” 给main函数，&e是引用类型
• C语言中，结构体的比较不能直接用 “==”，需要依次对比各个分量来判断两个结构体是否相等，而基本数据类型：int、char、double、float等的比较可以直接用