目录

前言

文章代码皆在Dev-C++ 5.11中测试，主要是总结一些方法，从而总结一些规律使自己进一步地深化学习内容，仅供参考，若有代码错误或表述不当之处，欢迎指正！

例题

例、设计一个删除算法，删除顺序表L中的第i个位置的元素，用引用变量返回。

思路：
由于这个函数删除后顺序表L有变，所以L前要有&，且我们要返回的变量也是变化的，一开始将其初始值设置为0，所以该变量前面也要加引用。

bool ListDelete(SqList &L,int i,int &e)//bool类型的函数，用于返回true和false

首先要判断删除的元素位置i是否有效，我们知道这里的i是位序（并不是数组，数组里面从0开始；而位序从1开始），所以当i小于1且i大于顺序表的长度时显示出错信息。

if (i<1||i>L.length)
	return false;

由于我们要删除某个元素，并通过引用变量返回，所以这里先获得位序为i的元素（i-1），并将这个位置的元素赋值给引用变量，然后这个位置就空了即被删除。

e=L.data[i-1];

删除该元素后，我们要将后面的元素都向前移动一格，这里注意，我们先移动删除元素右边的元素，而不从最后一个元素向前移，即我们可以设置一个for循环，将位序i这个量赋给j，作为j的初始值从而开始对位序为i后的元素进行向前移一格，按之前说的，所以要将数组下标大的赋值给下标小的，即

L.data[j-1]=L.data[j];

删除后顺序表要减1，并返回true表示删除成功。
核心代码如下：

/*顺序表的删除操作 （删除L中第i个位置的元素并引用变量e返回）*/
bool ListDelete(SqList &L,int i,int &e) {
	if (i<1||i>L.length)	//在[1,length+1]内有效
		return false; //删除失败返回true
	e=L.data[i-1];	//将要删除的元素赋值给e，由于是数组所以要i-1
	for(int j=i; j<L.length; j++)
		L.data[j-1]=L.data[j];	//将要删除的位置，第i个元素后的元素前移，先移动前面的元素，即下标大的赋值给下标小的
	L.length--;		//数组的长度减1
	return true; 	//删除成功后返回true
}

完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*顺序表的删除操作 （删除L中第i个位置的元素并引用变量e返回）*/
bool ListDelete(SqList &L,int i,int &e) {
	if (i<1||i>L.length)	//在[1,length+1]内有效
		return false; //删除失败返回true
	e=L.data[i-1];	//将要删除的元素赋值给e，由于是数组所以要i-1
	for(int j=i; j<L.length; j++)
		L.data[j-1]=L.data[j];	//将要删除的位置，第i个元素后的元素前移，先移动前面的元素，即下标大的赋值给下标小的
	L.length--;		//数组的长度减1
	return true; 	//删除成功后返回true
}

//主函数 
int main() {
	SqList L;
	int a;
	int e=0;	//初始化e的值 
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	DispList(L);
	printf("\n");
	printf("请输入想删除的元素位置：\n",a);
	scanf("%d",&a);
	if (ListDelete(L,a,e))
		printf("已删除顺序表中第%d个元素,其元素值为%d\n",a,e);
	else
		printf("输入的位序i不合法,删除操作失败！\n");
	printf("当前顺序表为：\n");
	DispList(L);
	return 0;
}

运行结果如下：
在这里插入图片描述

类似题目1

例、对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法实现删除线性表中所有值为x的数据元素。

思路：
通过定义一个函数来实现要求，其参数&L是因为执行删除操作后，顺序表中的元素个数会变化，另外参数x用于输入要删除的数据元素。

void del_x(SqList &L,int x)

我们通过一个for循环，还是循环遍历整个顺序表，设置两个变量i和k，其初始值都为0，目的是找到等于和不等于值为x的数据元素，k值用于记录顺序表中不等于x的数据元素次数（这个次数最后就可以作为顺序表的最终长度），i用于循环遍历顺序表，若当前的i值不等于x时，则将当前数组下标i赋给以k为数组下标的数据元素（当找到元素时，相当于将其后数据元素的数组下标i，赋给那个被找到的数据元素，即复制一个过去），且此时k++；而若等于x时，本次for循环不执行，即本次循环的k值为顺序表中不等于x的数据元素次数。

int k=0;
for(int i=0; i<L.length; i++) {		//遍历顺序表
	if(L.data[i]!=x) {		//若不等于x，则将当前值赋给当前值；若不等于则不只需if内的语句，k值不变
		L.data[k]=L.data[i];
		k++;
	}
}

所以最后我们得到的k=总长度-不等于x的数据元素个数，然后将这个值赋给L.length从而修改顺序表的长度，后面的元素都被剪除，从而达到删除所有值为x的数据元素的操作。

L.length=k;	//最后将k值赋给顺序表的长度，此时长度为除掉所有为x的数据元素后的值

核心代码如下：

/*删除顺序表中所有值为x的数据元素*/
void del_x(SqList &L,int x) {
	int k=0;		//k用于记录顺序表中不等于x的数据元素
	for(int i=0; i<L.length; i++) {		//遍历顺序表
		if(L.data[i]!=x) {		//若不等于x，则将当前值赋给当前值；若不等于则不只需if内的语句，k值不变
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;	//最后将k值赋给顺序表的长度，此时长度为除掉所有为x的数据元素后的值 
}

这里讲得有点繁杂，所以对代码进行一些修改，……，从而可观察每次循环后的当前顺序表，根据结果可可以更好理解执行情况，如下：
在这里插入图片描述
第零次循环（i=0），第一次循环没有找到与x=1相同的元素，所以顺序表无变化，i和k的值正常递加；第二次循环（i=3）找到目标元素，本次if条件语句下的内容不执行，k2值不变，此时数组下标为i3（由于是数组所以实际上为i4，后面的i和k都是一样）的数据元素替换数组下标为k2的数据元素；第三次循环正常运行，i和k的值正常递加，k为k3，i为i4；第四次循环又找到目标元素，所以此时数组下标为i4的数据元素替换数组下标为k3的数据元素，由于本次循环正常进行所以k值加1，为k4；第五次循环i=6不满足i<L.Length退出for循环，将k4的值赋给顺序表长度，后面的元素被剪除。
在这里插入图片描述
完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*删除顺序表中所有值为x的数据元素*/
void del_x(SqList &L,int x) {
	int k=0;		//k用于记录顺序表中不等于x的数据元素
	for(int i=0; i<L.length; i++) {		//遍历顺序表
		if(L.data[i]!=x) {		//若不等于x，则将当前值赋给当前值；若不等于则不只需if内的语句，k值不变
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;	//最后将k值赋给顺序表的长度，此时长度为除掉所有为x的数据元素后的值 
}
//主函数
int main() {
	SqList L;
	int x;
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	DispList(L);
	printf("\n");
	printf("请输入要删除顺序表中所有为x的元素值：\n",x);
	scanf("%d",&x);
	del_x(L,x);
	printf("当前顺序表为：\n");
	DispList(L);
	return 0;
}

运行结果如下：
在这里插入图片描述
与例题2的相似对比总结：
在这里插入图片描述

类似题目2

例、删除有序顺序表中重复的数据元素，使表中所有元素的值均不同。

思路：
这道题要注意输入的顺序表是有序的，通过for循环遍历有序顺序表，分别设置参数i=0及j=1，从而查找下一个与上一个元素值不相同的元素，当不相同时，将元素向前移动，然后j++；若相同则退出本次循环，然后j++，最后得到的所有元素不重复的值统计个数，赋给L.length，此时i+1前都是不重复的元素，后面多余的元素即重复元素，即完成删除顺序表中重复的数据元素。
核心代码如下：

/*删除有序顺序表中重复的元素*/
bool Delete_same1(SqList &L) {
	if(L.length==0)
		return false;
	int i,j;
	for(i=0,j=1; j<L.length; j++){
		if(L.data[i]!=L.data[j])	 //查找下一个与上个元素值不同的元素 
			L.data[++i]=L.data[j];	//找到后将元素前移动 
	}	
	L.length=i+1; 	//所有不重复的值的个数赋给L.length 
	return true;
}

对代码进行一些修改，……，从而可观察每次循环后的当前顺序表，根据结果可以更好理解执行情况，如下：
在这里插入图片描述
完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*删除有序顺序表中重复的元素*/
bool Delete_same1(SqList &L) {
	if(L.length==0)
		return false;
	int i,j;
	for(i=0,j=1; j<L.length; j++){
		if(L.data[i]!=L.data[j])	 //查找下一个与上个元素值不同的元素 
			L.data[++i]=L.data[j];	//找到后将元素前移动 
	}	
	L.length=i+1; 	//所有不重复的值的个数赋给L.length 
	return true;
}

//主函数
int main() {
	SqList L;
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	Delete_same1(L);
	DispList(L);
	return 0;
}

运行结果如下：
在这里插入图片描述
与例题的类似对比：
在这里插入图片描述

类似题目3

例、删除顺序表中重复的数据元素，使表中所有元素的值均不同。

【本题代码参考文章：https://blog.csdn.net/qq_42285148/article/details/117393638】
思路：
这题与题目2相比也就是将有序顺序表改为顺序表，设置两个for循环，从内自外循环遍历顺序表，内层循环从顺序表的第二位元素开始，跟上一题类似，不过这里是要查找下一个与上个元素值相同的元素，这里再进行分支若当前查找的下一个元素至顺序表的末尾，则将下一个元素赋值为0，且顺序表的长度减一；若不是顺序表的末尾，则继续进行一个for循环，对其中将下标大的元素赋给下标小的元素，将元素全部左移，然后再将顺序表的长度减一，最后再j–，继续回到两层for循环，检查下一个与上个元素值相同的元素。
核心代码如下：

/*删除顺序表中重复的元素*/
bool Delete_same2(SqList &L) {
	if(L.length==0)
		return false;
	int i,j,k;
	for(i=0;i<L.length;i++){	//从顺序表的第一位数据元素遍历整个顺序表
		for(j=i+1;j<L.length;j++)	//从顺序表的第二位数据元素遍历整个顺序表
			if(L.data[j]==L.data[i]){	//查找下一个与上个元素值相同的元素
				if(j==L.length){	//若下一个查找的元素到顺序表的表尾
					L.data[j]=0;
					L.length--;
				}
				else{
					for(k=j;k<L.length;k++)	//若下一个查找的元素还没到表尾
						L.data[k]=L.data[k+1];	//将下标大的元素赋给下标小的元素
					L.length--; 	//顺序表的长度减1
				}
				j--;
			}
	}
	return true;
}

完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*删除顺序表中重复的元素*/
bool Delete_same2(SqList &L) {
	if(L.length==0)
		return false;
	int i,j,k;
	for(i=0;i<L.length;i++){	//从顺序表的第一位数据元素遍历整个顺序表
		for(j=i+1;j<L.length;j++)	//从顺序表的第二位数据元素遍历整个顺序表
			if(L.data[j]==L.data[i]){	//查找下一个与上个元素值相同的元素
				if(j==L.length){	//若下一个查找的元素到顺序表的表尾
					L.data[j]=0;
					L.length--;
				}
				else{
					for(k=j;k<L.length;k++)	//若下一个查找的元素还没到表尾
						L.data[k]=L.data[k+1];	//将下标大的元素赋给下标小的元素
					L.length--; 	//顺序表的长度减1
				}
				j--;
			}
	}
	return true;
}

//主函数
int main() {
	SqList L;
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	DispList(L);
	printf("\n"); 
	printf("删除重复值后的顺序表为：\n");
	Delete_same2(L);
	DispList(L);
	return 0;
}

运行结果如下：
在这里插入图片描述

类似题目4

例、从顺序表中删除其值在s与t之间的所有元素（包含s和t，且s<t），若s或t不合理或顺序表为空，则显示出错信息并退出运行。

思路：
首先判断s<t且顺序表不为空则继续执行操作。

if(s>=t||L.length==0)	//若不合理或顺序表为空，显示出错信息

然后遍历顺序表，在循环内，由于我们要删除值在s-t之间的元素且包括s、t，所以要通过一个if条件语句判断当前循环的data[i]的值在不在这个范围内，若在则将k++（k的初始值为0，该变量用于计数，计最后删除处于范围中的数量）；而若当前数据元素不在则将当前删除的位置的第i个数组下标的元素前移，这里先移下标大的元素，再移下标小的元素，依次全部向左移。

for(i=0; i<L.length; i++) {   //循环遍历顺序表 
	if(L.data[i]>=s&&L.data[i]<=t)//当数据元素值在s与t之间（包括s、t）的所有元素则k++ 
		k++;
	else
		L.data[i-k]=L.data[i]; //将要删除的位置，第i个元素后的元素前移，先移动前面的元素，即下标大的赋值给下标小的
}

遍历顺序表后，顺序表的长度减k，此时顺序表的长度为删除前的长度-要删除的元素长度（k）。

L.length=L.length-k;	//顺序表L的长度减k

核心代码如下：

/*删除其值在s与t之间的所有元素（包含s和t，且s<t），若不合理或顺序表为空，则显示出错信息并退出运行*/
bool Del_st(SqList &L,int s,int t) {
	int i,k=0;
	if(s>=t||L.length==0)	//若不合理或顺序表为空，显示出错信息
		return false;
	for(i=0; i<L.length; i++) {   //循环遍历顺序表 
		if(L.data[i]>=s&&L.data[i]<=t)//当数据元素值在s与t之间（包括s、t）的所有元素则k++ 
			k++;
		else
			L.data[i-k]=L.data[i]; //将要删除的位置，第i个元素后的元素前移，先移动前面的元素，即下标大的赋值给下标小的
	}
	L.length=L.length-k;	//顺序表L的长度减k
	return true;
}

完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*删除其值在s与t之间的所有元素（包含s和t，且s<t），若不合理或顺序表为空，
则显示出错信息并退出运行*/
bool Del_st(SqList &L,int s,int t) {
	int i,k=0;
	if(s>=t||L.length==0)	//若不合理或顺序表为空，显示出错信息
		return false;
	for(i=0; i<L.length; i++) {   //循环遍历顺序表
		if(L.data[i]>=s&&L.data[i]<=t)//当数据元素值在s与t之间（包括s、t）的所有元素则k++
			k++;
		else
			L.data[i-k]=L.data[i]; //将要删除的位置，第i个元素后的元素前移，先移动前面的元素，即下标大的赋值给下标小的
	}
	L.length=L.length-k;	//顺序表L的长度减k
	return true;
}

//主函数
int main() {
	SqList L;
	int s,t;
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	DispList(L);
	printf("\n");
	printf("请输入要删除的范围（s<t）：\n");
	scanf("%d %d",&s,&t);
	if (Del_st(L,s,t)) {
		printf("删除后的顺序表为：\n");
		DispList(L);
	} else
		printf("操作失败！\n");
	return 0;
}

运行结果如下：
在这里插入图片描述
与例题2的相似对比总结：
在这里插入图片描述

类似题目5

例、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素补齐，若顺序表为空，则显示出错信息并退出运行。

思路：
本题较于上面的例题，也是删除元素，但这是删除顺序表中最小值元素，由于不知道哪个元素最小，不像例题中直接通过位序进行删除元素，所以也是要遍历顺序表，首先假设数组的第一位元素是最小值元素，即L.data[0]，将其赋值给e变量储存，这样，在for循环中从数组的第一位元素开始搜索最小值，i的值每次递加每次搜索目标元素，当搜索到后，将另外假设的一个变量pos为最小元素的下标作为后面用，如下：

e=L.data[0];	//将数组的第一位元素赋值给e，从数组的第一位元素开始搜索最小值
int pos=0;		//假设pos元素最小，pos初始值为0

for循环中从第二位（i=1）开始遍历搜索顺序表中最小值的元素，然后通过引用变量，将其赋值给它进而删除，如下：

for(int i=1;i<L.length;i++)
	if(L.data[i]<e){		//找到顺序表中最小值的元素 
		e=L.data[i];	//使其赋值给e，从而删除这个值 
		pos=i;	//通过将i赋值给pos,来获取删除元素位序i对应的数组下标 
	}

另外由于题目还要求将删除的那个位置的元素用最后一个元素补齐，我们知道顺序表数组中最后一个元素为L.data[L.length-1]（数组下标从0开始），通过另外设置一个变量来对删除的最小值的元素的数组下标位置进行记录，然后与最后一个元素进行交换赋值，如下：

L.data[pos]=L.data[L.length-1];	//删除的空出位置由最后一个元素填补

核心代码如下：

/*从顺序表中删除最小值（假设唯一），并返回该值，且空的位置由
最后一个元素补齐，若顺序表为空，则显示出错信息并退出运行*/
bool Del_Min(SqList &L,int &e){
	if(L.length==0)	//顺序表为空，则显示出错信息并退出运行
		return false;
	e=L.data[0];	//将数组的第一位元素赋值给e，从数组的第一位元素开始搜索最小值
	int pos=0;	//假设pos元素最小，pos初始值为0 
	for(int i=1;i<L.length;i++)
		if(L.data[i]<e){		//找到顺序表中最小值的元素 
			e=L.data[i];	//使其赋值给e，从而删除这个值 
			pos=i;	//通过将i赋值给pos,来获取删除元素位序i对应的数组下标 
		} 
	L.data[pos]=L.data[L.length-1];	//删除的空出位置由最后一个元素填补
	L.length--;			//顺序表的长度减1
	return true; 
}

完整代码如下：

#include<stdio.h>
#define MaxSize 10
typedef struct {
	int data[MaxSize];
	int length;
} SqList;

/*初始化顺序表*/
void InitList(SqList L) {
	L.length=0;
}

/*顺序表的输出，从头到尾输出顺序表中各元素的值*/
void DispList(SqList L) {
	for(int i=0; i<L.length; i++)
		printf("%d ",L.data[i]);
}

/*从顺序表中删除最小值（假设唯一），并返回该值，且空的位置由
最后一个元素补齐，若顺序表为空，则显示出错信息并退出运行*/
bool Del_Min(SqList &L,int &e){
	if(L.length==0)	//顺序表为空，则显示出错信息并退出运行
		return false;
	e=L.data[0];	//将数组的第一位元素赋值给e，从数组的第一位元素开始搜索最小值
	int pos=0;		//假设pos元素最小，pos初始值为0 
	for(int i=1;i<L.length;i++)
		if(L.data[i]<e){		//找到顺序表中最小值的元素 
			e=L.data[i];	//使其赋值给e，从而删除这个值 
			pos=i;	//通过将i赋值给pos,来获取删除元素位序i对应的数组下标 
		} 
	L.data[pos]=L.data[L.length-1];	//删除的空出位置由最后一个元素填补
	L.length--;			//顺序表的长度减1
	return true; 
}

//主函数 
int main() {
	SqList L;
	int e=0;	//初始化e的值 
	InitList(L);
	printf("请输入建立顺序表的元素个数：\n");
	scanf("%d",&L.length);
	printf("请输入整数：\n");
	for(int i=0; i<L.length; i++)
		scanf("%d",&L.data[i]);
	printf("当前顺序表为：\n");
	DispList(L);
	printf("\n");
	if (Del_Min(L,e))
		printf("已删除顺序表中最小值元素,其元素值为%d,且已用最后一个元素填补！\n",e);
	else
		printf("顺序表为空，操作失败！\n");
	printf("当前顺序表为：\n");
	DispList(L);
	return 0;
}

运行结果如下：
在这里插入图片描述
与例题2的相似对比总结：
在这里插入图片描述

结语

参考书籍：《王道 数据结构 考研复习指导》

# 数据结构 # 算法
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

多模态大模型&科学计算双管齐下，百度飞桨两大赛项报名倒计时！

第二届开放原子大赛是由开放原子开源基金会组织举办的开源技术领域专业赛事，聚焦解决真问题，重点覆盖基础软件、工业软件、人工智能大模型等领域

avatar 开放原子开发者工作坊

以智能 致世界 | 操作系统大会2024议程全览

avatar 开放原子开发者工作坊

开放原子开源基金会新增捐赠人（2024年9月）

2024年9月，新增以下单位成为开放原子开源基金会及旗下项目捐赠人。

avatar 开放原子开发者工作坊