顺序表相关习题(C语言实现)

顺序表的定义

线性表的顺序存储又称为顺序表。它是一组地址连续的存储单元,依次存储线性表中的数据元素,从而使得逻辑上相邻的元素在物理上也相邻。

假定线性表的元素类型是ElemType,线性表的顺序存储类型描述为

1
2
3
4
5
6
#define MaxSize 100 	//表长初始值
typedef int ElemType; //顺序表元素类型
typedef struct{
ElemType data[MaxSize]; //表中数据元素
int Length; //顺序表的当前长度
}SqList;

相关习题

1、删除具有最小值的元素

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

思路:遍历顺序表找到最小元素,记录其位置,然后将其替换为最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool deleteMin(SqList &L, ElemType &left){
if (L.Length == 0)
return false;
left = L.data[0];
int pos = 0; //最小值位置记录
for (int i = 0; i < L.Length; i++){
if (L.data[i] < left){
left = L.data[i];
pos = i;
}
}
L.data[pos] = L.data[L.Length-1];
L.Length--;
}

2、元素逆置

设计一个高效的算法,将顺序表的所有元素逆置,要求算法的空间复杂度为O(1)。

思路:将第i个元素和第n-i个元素互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool reverseList(SqList &L){
if (L.Length == 0)
return false;
int n = L.Length/2;
int tmp;
for (int i = 0;i <n; i++){
int j = L.Length-1-i;
tmp = L.data[i];
L.data[i] = L.data[j];
L.data[j] = tmp;
}
return true;
}

3、删除所有值为X的数据元素

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

思路:遍历顺序表时记录值不为x的个数j,并将第i个元素移动至第j个。

1
2
3
4
5
6
7
8
9
10
11
bool deleteValue(SqList &L,ElemType value){
int j = 0;
for (int i = 0; i < L.Length; i++){
if (L.data[i] != value){
L.data[j] = L.data[i];
j++;
}
}
L.Length = j;
return true;
}

4、有序表中删除值在给定区间的数据元素

从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素,如果s或t不合理或者顺序表为空则显示出错信息并退出。

解法1:遍历顺序表,元素值小于等于s时无操作;元素值在s与t之间时计数n加一,元素值大于等于t时元素前移n位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool deleteValueBetweenST(SqList &L, ElemType s, ElemType t){
int n = 0;
if(s >= t || L.Length == 0)
return false;
for (int i = 0; i < L.Length; i++){
if (L.data[i] > s && L.data[i] < t ){
n++;
}else if (L.data[i] >= t){
L.data[i-n] = L.data[i];
}
}
L.Length -= n;
return true;
}

解法2:与题目3类似,判断条件变为元素值不在s与t之间。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool deleteValueBetweenST(SqList &L, ElemType s, ElemType t){
int j = 0;
if(s >= t || L.Length == 0)
return false;
for (int i = 0; i < L.Length; i++){
if (L.data[i] <= s || L.data[i]>= t ){
L.data[j] = L.data[i];
j++;
}
}
L.Length = j;
return true;
}

5、无序表中删除值在给定区间的数据元素

从顺序表中删除其值在给定值s与t之间(包含s和t,要求s<t)的所有元素,如果s或t不合理或者顺序表为空则显示出错信息并退出。

思路:与题目3类似,判断条件变为元素值小于s或者大于t。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool deleteValueBetweenST2(SqList &L, ElemType s, ElemType t){
int j = 0;
if(s >= t || L.Length == 0)
return false;
for (int i = 0; i < L.Length; i++){
if (L.data[i] < s || L.data[i]> t ){
L.data[j] = L.data[i];
j++;
}
}
L.Length = j;
return true;
}

6、删除重复的的数据元素

从有序顺序表中删除所有其值重复的元素。使表中所有元素值均不同。

思路:遍历顺序表,依次判断当前元素与下一元素是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool deleteSameValue(SqList &L){
int j = 0;
if(L.Length == 0)
return false;
for (int i = 1; i < L.Length; i++){
if (L.data[j] != L.data[i]){
L.data[j+1] = L.data[i];
j++;
}
}
L.Length = j + 1;
return true;
}

7、合并顺序表

将两个有序顺序表合并成一个新的有序顺序表,并由函数返回结果顺序表

思路:比较两个有序顺序表A与B的最小的元素,将最小元素放入顺序表L中。重复此操作。最后将A或者B中剩余未比较部分加入到表L。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool merge(SqList &L, SqList A, SqList B){
int i = 0, j = 0,k = 0; //分别标记三个数组下标
for (; i < A.Length || j < B.Length; ){ //比较大小,将较小的值放入顺序表L
if(A.data[i] >= B.data[j]){
L.data[k++] = B.data[j++];
}else if(A.data[i] < B.data[j]){
L.data[k++] = A.data[i++];
}
}
while( i < A.Length){ //将比较完毕后剩余的元素加入表L
L.data[k++] = A.data[i++];
}
while( j < B.Length){
L.data[k++] = B.data[j++];
}
L.Length = k;
return true;
}

8、顺序表位置互换

已知在一维数组A[m+n]中依次存放着两个线性表($a_1,a_2,…,a_m$)与($b_1,b_2,…,b_n$)。试编写一个函数,将数组中两个顺序表的位置互换。

思路:先整体逆置,再分别逆置0到n-1和n到n+m-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool reverse(SqList &L,int left, int right){	//将顺序表的left到right逆置
if (L.Length == 0 || left > right || right >= L.Length)
return false;
int n = (right + left)/2;
int tmp;
for (int i = 0; i < n-left; i++){
tmp = L.data[left+i];
L.data[left+i] = L.data[right-i];
L.data[right-i] = tmp;
}
return true;
}

void reverseList(SqList &L, int m, int n){
reverse(L, 0, m + n-1);
reverse(L, 0, n-1);
reverse(L, n, m + n-1);
}

9、查找值为x的元素并与后继元素交换位置

线性表($a_1,a_2,…,a_m$)中元素递增有序且按照顺序存储于计算机中。要求设计一算法完成用最少时间在表中查找数值为x的元素,若找到将其与后继元素位置相交换,若找不到将其插入表中并使表中元素仍然有序。

思路:查找时间最少,使用折半查找法。有值为x的函数则与下一元素交换位置,没有则将值大于x的元素后移一位,插入x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void searchValue(SqList &L,int x){
int low, mid ,high; //折半查找
low = 0;
high = L.Length-1;
while(low <= high){
mid = (low + high)/2;
if(L.data[mid] > x){
high = mid-1;
}else if(L.data[mid] < x){
low = mid+1;
}else{
break;
}
}
if(low > high){ //无该元素则插入
int i;
for (i = L.Length-1;L.data[i] > x; i--){ //大于x的元素后移一位
L.data[i+1] = L.data[i];
}
L.data[i+1] = x;//插入x
L.Length++;
}else { //有该元素则与下一元素交换
int tmp = L.data[mid];
L.data[mid] = L.data[mid+1];
L.data[mid+1] = tmp;
}
}