27.顺序表练习题目（1）（2023王道数据结构2.2.3前8题）

【这里所有解答都写的是全部代码，目的是让大家能够直接复制上手运行，感受代码的运行过程，而不单单只是写了一个函数】

试题1：（王道2023数据结构综合应用题1）

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

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}bool Del_Min(SqList &L){
//删除顺序表中的最小值元素结点if(L.length==0)return false;  //表空，中止操作返回ElemType value = L.data[0];int pos = 0;  //假定0号元素的值最小for(int i = 1; i < L.length; i++)  //循环，寻找具有最小值的元素 if(L.data[i] < value){value = L.data[i];  //让value始终记忆当前具有最小值的元素 pos = i;}L.data[pos] = L.data[L.length-1];  //空出的位置由最后一个元素填补 L.length--;return true;  //此时value即为最小值 
} int main(){int n,e;cout<<"请输入顺序表长度"<<endl;cin>>n;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n);	 //顺序表传值 Print(L);  //打印顺序表Del_Min(L);  //删除顺序表中的最小值Print(L);  //再次打印输出return 0;
}

输出：

请输入顺序表长度
5
顺序表初始化完成
请传入数值
3 7 5 2 4
目前顺序表为：
3       7       5       2       4
目前顺序表为：
3       7       5       4

试题2：（王道2023数据结构综合应用题2）

设计一个高效算法，将顺序表中的所有元素逆置，要求算法的空间复杂度是O（1）；

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}void Reverse(SqList &L){
//将顺序表所有元素逆置ElemType value;for(int i = 0; i < L.length/2; i++){value = L.data[i];L.data[i] = L.data[L.length - 1 - i];L.data[L.length - 1 - i] = value;}
} int main(){int n,e;cout<<"请输入顺序表长度"<<endl;cin>>n;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n);	 //顺序表传值 Print(L);  //打印顺序表Reverse(L);  //将顺序表逆置Print(L);  //再次打印输出return 0;
}

输出：

请输入顺序表长度
5
顺序表初始化完成
请传入数值
5 4 32 1 8
目前顺序表为：
5       4       32      1       8
目前顺序表为：
8       1       32      4       5

试题3：（王道2023数据结构综合应用题3）

对长度为n的顺序表L，设计一个时间复杂度为O（n），空间复杂度为O（1）的算法，删除线性表中所有值为x的元素。

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}void del_x(SqList &L,int x){
//删除所有值为x的元素int j = 0;  //j记录x元素的个数for(int i = 0; i < L.length; i++){if (L.data[i] == x)j = j + 1;L.data[i+1 - j] = L.data[i+1];  //前移元素}L.length = L.length - j;  //更新线性表长度
} int main(){int n,e,x;cout<<"请输入顺序表长度"<<endl;cin>>n;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n);	 //顺序表传值 Print(L);  //打印顺序表cout<<"请输入删除元素"<<endl;cin>>x;	 //输入删除的元素xdel_x(L,x);  //删除所有值为x的元素Print(L);  //再次打印输出return 0;
}

输出：

请输入顺序表长度
6
顺序表初始化完成
请传入数值
2 2 3 5 2 4
目前顺序表为：
2       2       3       5       2       4
请输入删除元素
2
目前顺序表为：
3       5       4

试题4/5：（王道2023数据结构综合应用题4/5）

从（有序）顺序表中删除值在s,t之间（要求s小于t），如果s和t的值不合理或顺序表为空，则显示出错信息并退出运行。

道理和题3差不多，只是要修改比较条件。这里假定顺序表不是有序的。

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}int del_x_st(SqList &L,int s,int t){
//删除所有值在s和t之间的元素if (s>t) cout<<"s和t的值非法"<<endl;if (L.length == 0) cout<<"顺序表为空"<<endl;int j = 0;  //j记录元素值在s与t之间的个数for(int i = 0; i < L.length; i++){if (L.data[i] >= s && L.data[i] <= t)j = j + 1;L.data[i+1 - j] = L.data[i+1];}L.length = L.length - j;return 0;
} int main(){int n,e,s,t;cout<<"请输入顺序表长度"<<endl;cin>>n;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n);	 //顺序表传值 Print(L);  //打印顺序表cout<<"请输入删除元素的下界"<<endl;cin>>s;	 //输入删除的元素下界scout<<"请输入删除元素的上界"<<endl;cin>>t;	 //输入删除的元素上界tdel_x_st(L,s,t);  //删除所有值在s和t之间的元素Print(L);  //再次打印输出return 0;
}

输出：

请输入顺序表长度
6
顺序表初始化完成
请传入数值
2 2 3 5 4 3
目前顺序表为：
2       2       3       5       4       3
请输入删除元素的下界
3
请输入删除元素的上界
4
目前顺序表为：
2       2       5

试题6（王道2023数据结构综合应用题6）：

删除顺序表中所有重复元素

这道题就不能按照前3，4，5题写：以下是错误示例：

int del(SqList &L){
//删除所有重复元素if (L.length == 0) cout<<"顺序表为空"<<endl;int j = 0;  //j记录重复次数for(int i = 1; i < L.length; i++){if (L.data[i-1] == L.data[i])j = j + 1;L.data[i+1 - j] = L.data[i+1];}L.length = L.length - j;return 0;
}

这段代码的输出结果是这样的：

目前顺序表为：
1       2       2       3       3       4
目前顺序表为：
1       2       4

分析：当i=2的时候，data[1]和data[2]相等。j变为1，于是data[2]就改为3，此时顺序表变为1，2，3，3，3，4。相当于多引入了一次重复。这样本来原顺序表只有两次重复，现在变成了3次。

正确解法：

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}int del(SqList &L){
//删除所有重复元素if (L.length == 0) cout<<"顺序表为空"<<endl;int j = 1;  //j记录不重复的元素个数for(int i = 1; i < L.length; i++){if (L.data[i-1] != L.data[i])  //此时第i个元素不和前面元素重复j = j + 1;L.data[j-1] = L.data[i];  //把不重复的元素加到后面}L.length = j;return 0;
} int main(){int n,e,s,t;cout<<"请输入顺序表长度"<<endl;cin>>n;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n);	 //顺序表传值 Print(L);  //打印顺序表del(L);  //删除所有重复元素Print(L);  //再次打印输出return 0;
}

输出：

请输入顺序表长度
6
顺序表初始化完成
请传入数值
1 2 2 3 3 4
目前顺序表为：
1       2       2       3       3       4
目前顺序表为：
1       2       3       4

试题7（王道2023数据结构综合应用题7）：

将两个有序顺序表合并成一个有序顺序表

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}SqList Merge(SqList L1,SqList L2){
//将两个有序表合并成一个有序表if (L1.length == 0 ||L2.length == 0) cout<<"顺序表为空"<<endl;int i = 0, j = 0, k = 0;SqList L;L.length = L1.length + L2.length;while (i<=L1.length && j<=L2.length){if (L1.data[i]<=L2.data[j]){L.data[k] = L1.data[i];i = i + 1;k = k + 1;}else{L.data[k] = L2.data[j];j = j + 1;k = k + 1;}}if (i=L1.length) {  //L1已比较完毕，把L2剩下的元素依次复制到L中for (; j < L2.length; j++){L.data[k] = L2.data[j];k = k + 1;}}if (j=L2.length) {  //L2已比较完毕，把L1剩下的元素依次复制到L中for (; i < L1.length; i++){	L.data[k] = L1.data[i];k = k + 1;}}return L;
} int main(){int n1, n2;cout<<"请输入顺序表L1长度"<<endl;cin>>n1;	 //输入数组的长度nSqList L1;InitList(L1);  //顺序表的初始化CreatList(L1,n1);	 //顺序表传值 Print(L1);  //打印顺序表cout<<"请输入顺序表L2长度"<<endl;cin>>n2;	 //输入数组的长度nSqList L2;InitList(L2);  //顺序表的初始化CreatList(L2,n2);	 //顺序表传值 Print(L2);  //打印顺序表Print(Merge(L1,L2));  //打印输出合并之后的顺序表return 0;
}

输出：

请输入顺序表L1长度
4
顺序表初始化完成
请传入数值
1 2 3 5
目前顺序表为：
1       2       3       5
请输入顺序表L2长度
4
顺序表初始化完成
请传入数值
2 3 6 8
目前顺序表为：
2       3       6       8
目前顺序表为：
1       2       2       3       3       5       6       8

试题8（王道2023数据结构综合应用题8）：

已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, a3...am)和(b1, b2, b3...bn)，将数组中两个顺序表的位置互换。也就是把(b1, b2, b3...bn)放在(a1, a2, a3...am)的前面。

直接暴力求解：

#include<iostream>
#include<algorithm>using namespace std;
#define MaxSize 10
#define ElemType int//顺序表的建立 
typedef struct{int data[MaxSize];  //存储空间的基地址int length;  //当前长度 
}SqList;//顺序表的初始化
void InitList(SqList &L){L.length = 0;cout<<"顺序表初始化完成"<<endl; 
} //顺序表传值 
void CreatList(SqList &L,int n){cout<<"请传入数值"<<endl; for(int i=0;i<n;i++){cin>>L.data[i];L.length++;}
}//打印顺序表 
int Print(SqList L){cout<<"目前顺序表为："<<endl;if (L.length == 0){return 0;}for (int k = 0; k < L.length; k++){  //输出顺序表 cout<<L.data[k]<<"\t";	}cout<<endl;
}SqList Merge(SqList &L,int m,int n){
//把两个顺序表交换顺序SqList L0;L0.length = m;for (int i = 0; i < m; i++)  //把第一个顺序表复制一份{L0.data[i] = L.data[i];}for (int i = 0; i < n; i++)  //把后面的复制到前面去{L.data[i] = L.data[m + i];}for (int i = 0; i < m; i++)  //然后把第一个顺序表再复制到后面{L.data[i+n] = L0.data[i];}return L;
} int main(){int n1, n2;cout<<"请输入顺序表L1长度"<<endl;cin>>n1;	 //输入数组的长度ncout<<"请输入顺序表L2长度"<<endl;cin>>n2;	 //输入数组的长度nSqList L;InitList(L);  //顺序表的初始化CreatList(L,n1+n2);	 //顺序表传值 Print(L);  //打印顺序表Print(Merge(L,n1,n2));  //打印输出交换之后的顺序表return 0;
}

输出：

请输入顺序表L1长度
3
请输入顺序表L2长度
4
顺序表初始化完成
请传入数值
1 2 3 4 5 6 7
目前顺序表为：
1       2       3       4       5       6       7
目前顺序表为：
4       5       6       7       1       2       3