数据结构学习笔记——线性表的概念及顺序表示（超详细最终版+++）建议反复看看ヾ(≧▽≦*)o_顺序表的输出
赞
踩
前言
以下所有代码都经过测试，编译运行软件：Dev-C++ 5.11，若有表述和代码错误感谢指出！！！
一、线性表的定义
线性表是具有相同数据类型的n个数据元素的有限序列，其中n≥0，即线性表可以为空【有限序列，可以为空】，当n=0时，称线性表是一个空表。线性表是一种逻辑结构，且为线性结构，即数据元素之间是一对一关系，另外，线性表中除了第一个元素外每个元素都只有一个前驱，除了最后一个元素外每个元素都只有一个后继。【表头元素无前驱，表尾元素无后继】
通过不同的存储结构，可以将线性表分为由顺序存储结构的顺序表和由链式存储结构的链表（链表包括单链表、双链表、循环链表等），其中链表还可以细分，例如静态链表中指针是通过结点的数组下标表示，它是借助数组来描述链式结构：
二、顺序表的相关知识点
（一）顺序存储和链式存储的对比
通过顺序存储的线性表称为顺序表，它是将线性表中所有元素按照其逻辑顺序，依次存储到指定存储位置开始的一块连续的存储空间里；而通过链式存储的链表中，每个结点不仅包含该元素的信息，还包含元素之间的逻辑关系的信息。
顺序表和链表的优缺点如下：
- 顺序表实现简单，
可以随机存取，其存储密度大，但是执行插入、删除操作需要移动大量元素，效率低，另外其存储空间需事先分配，容易造成空间浪费或溢出。 - 链表不支持随机存取，
只能顺序存取，通过指针来体现元素之间的逻辑关系，存储密度比顺序表小，其执行插入、删除操作不需要移动元素，只需修改指针，效率高，另外它还支持动态分配存储空间，不会造成空间浪费或溢出。
（二）顺序表的插入操作
1、最好情况
若在顺序表的表尾插入元素，则不需要执行元素后移操作，即最好情况，所以最好时间复杂度为O(1)。
2、最坏情况
若在顺序表的表头插入元素，需要执行n次元素后移操作，即最坏情况，所以最坏时间复杂度为O(n)。
3、平均情况
设在顺序表第i个位置插入元素的概率为pi=1/(n+1)【设插入概率相同】，即在长度为n的线性表中插入一个结点，所需移动元素的平均次数为：
1
n
+
1
∑
i
=
1
n
+
1
(
n
−
i
+
1
)
=
1
n
+
1
n
(
n
+
1
)
2
=
n
2
\frac{1}{n+1} \sum_{i=1}^{n+1} (n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac{n}{2}
n+11i=1∑n+1(n−i+1)=n+112n(n+1)=2n
平均情况下，所需移动元素的平均次数为n/2，故顺序表插入操作的平均时间复杂度为O(n)。
（三）顺序表的删除操作
1、最好情况
若删除顺序表的表尾元素，则不需要执行元素后移操作，即最好情况，所以最好时间复杂度为O(1)，与顺序表的插入操作的最好情况一样。
2、最坏情况
若删除顺序表的表头元素，则执行n次移动操作，即最坏情况，所以最坏时间复杂度为O(n)，与顺序表的插入操作的最坏情况一样。
3、平均情况
设删除顺序表第i个位置上元素的概率为pi=1/n【设删除概率相同】，即在长度为n的线性表中删除一个结点，若删除第一个结点需移动n-1次，……，删除第n个结点移动0次：
1
n
∑
i
=
1
n
(
n
−
i
)
=
1
n
n
(
n
−
1
)
2
=
n
−
1
2
\frac{1}{n} \sum_{i=1}^{n} (n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2}
n1i=1∑n(n−i)=n12n(n−1)=2n−1
平均情况下，所需移动元素的平均次数为(n-1)/2，故顺序表的删除操作的平均时间复杂度为O(n)。
在长度为n的顺序表中删除第i个结点（1≤i≤n）时，需要移动n-1个结点，而在第i个结点（1≤i≤n）前插入一个结点时，需要移动n-i+1个结点。
（四）顺序表的按位查找
由于顺序表中每个数据元素是通过一组连续的存储单元依次存储，从而逻辑上相邻的元素物理位置上也相邻【逻辑顺序与物理顺序相同】。若要在顺序表中进行按位查找，即通过所给数据元素位置，即下标来访问，而不需要遍历整个顺序表来查找，故顺序表按位查找的时间复杂度为O(1)。
# 创建一个顺序表
List = [1, 2, 3, 4, 5，6]
# 访问第3个元素
element = List[2]
print(element)
- 1
- 2
- 3
- 4
- 5
输出结果为：3
上述代码，可以体现顺序表在O(1)时间访问线性表中第i个数据元素。
（五）顺序表的按值查找
1、最好情况
若查找元素在顺序表的表头，则在常数级即可查找到该元素，即最好情况，最好时间复杂度为O(1)。
2、最坏情况
若查找元素在顺序表的表尾或不存在时，需要遍历整个顺序表，即最坏情况，最坏时间复杂度为O(n)。
3、平均情况
设删除顺序表第i个位置上元素的概率为pi=1/n【设删除概率相同】，即在长度为n的线性表中删除一个结点，若删除第一个结点需移动n-1次，……，删除第n个结点移动0次：
∑
i
=
1
n
(
1
n
×
i
)
=
1
n
n
(
n
+
1
)
2
=
n
+
1
2
\sum_{i=1}^{n} (\frac{1}{n} ×i)=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}
i=1∑n(n1×i)=n12n(n+1)=2n+1
平均情况下，按值查找一个元素的平均次数为(n+1)/2，故顺序表的按值查找的平均时间复杂度为O(n)。
（六）各种操作的对比
平均情况下，顺序表的各种操作数据元素的平均比较次数和平均时间复杂度如下表【插入n/2，删除减一，查找加一】：
| 名称 | 插入 | 删除 | 查找 |
|---|---|---|---|
| 平均比较次数 | n/2 | (n-1)/2 | (n+1)/2 |
| 平均时间复杂度 | O(n) | O(n) | O(n) |
三、顺序表的代码实现
（一）顺序表的定义
以下操作均为顺序表的静态分配，所以其大小和空间是固定的，可通过MaxSize设置顺序表的最大长度。
#include<stdio.h>
#define MaxSize 10 //可自行更改最大长度
typedef struct {
int data[MaxSize]; //元素
int length; //顺序表的当前长度
} SqList; //顺序表的类型定义
- 1
- 2
- 3
- 4
- 5
- 6
（二）顺序表的初始化
设置顺序表的初始长度为0，即L.length=0。
/*初始化顺序表*/
void InitList(SqList L) {
L.length=0;
}
- 1
- 2
- 3
- 4
（三）顺序表的建立
/*顺序表的建立*/
void CreatList(SqList &L) {
printf("请输入建立顺序表的元素个数：\n");
scanf("%d",&L.length);
for(int i=0; i<L.length; i++) {
int number=i+1;
printf("请输入第%d个整数：\n",number);
scanf("%d",&L.data[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
（四）顺序表的输出
顺序表的输出，依次遍历从头到尾输出顺序表中各元素的值，即通过一个for循环，条件<L.length（顺序表的总长度），每次输出元素。
/*顺序表的输出（从头到尾输出顺序表中各元素的值）*/
void DispList(SqList L) {
for(int i=0; i<L.length; i++)
printf("%d ",L.data[i]);
}
- 1
- 2
- 3
- 4
- 5
结合以上功能函数，如下，创建一个顺序表，长度为6，其功能是创建一个顺序表并输入元素，再通过函数调用依次输出各元素，数据元素依次为2，6，0，-1，4，8，如下完整代码：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } //主函数 int main() { SqList L; InitList(L); CreatList(L); printf("顺序表为：\n"); DispList(L); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
首先输入要创建顺序表中的元素个数，然后依次输入各数据元素，最后输出该顺序表，运行结果如下：
（五）顺序表的逆序输出
顺序表的逆序输出也就是交换通过折半法，交换数据元素，然后也是通过调用DispList()函数依次遍历顺序表输出。
/*将顺序表中的所有元素逆置并输出*/
void ReverseList(SqList L) {
int temp;
for(int i=0; i<L.length/2; i++) {
temp=L.data[i];
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
DispList(L); //调用输出函数
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
例如，接上一个例子，不过这次是逆序输出顺序表，如下完整代码：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、将顺序表中的所有元素逆置并输出*/ void ReverseList(SqList L) { int temp; for(int i=0; i<L.length/2; i++) { temp=L.data[i]; L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=temp; } DispList(L); } //主函数 int main() { SqList L; InitList(L); CreatList(L); printf("逆序输出顺序表：\n"); ReverseList(L); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
运行结果如下：
（六）顺序表的插入操作
顺序表的插入操作以位序进行插入元素，这里要注意位序是从1开始的，而c语言中的数组下标是从0开始的，这一点在插入操作中要明白，这里加了一个if语句判断输入的插入位置是否合法，若不合法则会返回false，插入后，要将其后的元素后移，最后数组长度加1。
/*顺序表的插入操作 （在L的位序i处插入元素e）*/
bool ListInsert(SqList &L,int i, int e) {
if (i<1||i>L.length||L.length>=MaxSize) //在[1,length+1]内有效且未存满或等于最大长度
return false; //插入失败返回 false
for(int j=L.length; j>=i; j--) //j变量等于顺序表的长度
L.data[j]=L.data[j-1]; //将要插入的位置，第i个元素及以后的元素后移，先移动后面的元素，即数组下标小的赋给下标大的
L.data[i-1]=e; //由于数组的下标是从0开始的，所以位序要减一，即将要插入的元素e赋值给L.data[i-1]
L.length++; //数组长度加1
return true; //插入成功返回 true
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
例如，向之前所创建好的顺序表的位序为3（数组下标为2）处插入数据元素“7”，如下完整代码：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、顺序表的插入操作 （在L的位序i处插入元素e）*/ bool ListInsert(SqList &L,int i, int e) { if (i<1||i>L.length||L.length>=MaxSize) //在[1,length+1]内有效且未存满或等于最大长度 return false; //插入失败返回 false for(int j=L.length; j>=i; j--) //j变量等于顺序表的长度 L.data[j]=L.data[j-1]; //将要插入的位置，第i个元素及以后的元素后移，先移动后面的元素，即数组下标小的赋给下标大的 L.data[i-1]=e; //由于数组的下标是从0开始的，所以位序要减一，即将要插入的元素e赋值给L.data[i-1] L.length++; //数组长度加1 return true; //插入成功返回 true } //主函数 int main() { SqList L; InitList(L); CreatList(L); printf("当前顺序表为：\n"); DispList(L); ListInsert(L,3,7); //在顺序表L的位序为3处插入数据元素7 printf("\n"); printf("插入后的顺序表为：\n"); DispList(L); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
运行结果如下：
（七）顺序表的删除操作
顺序表的删除操作同插入操作一样，也是通过位序插入/删除，删除目标元素后，其后的元素要向前移动一格，最后数组长度要减1。
/*顺序表的删除操作 （删除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
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
例如对创建的顺序表，删除第4个元素（位序为4），然后输出顺序表，完整代码如下：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、顺序表的删除操作 （删除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); CreatList(L); 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
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
运行结果如下：
（八）顺序表的按位和按值查找
顺序表的按位查找是以数组下标进行查找的，所以位序要减1，即L.data[i-1]。
/*顺序表的按位查找 （获取L中第i个位置元素的值）*/
int GetElem(SqList L,int i) {
return L.data[i-1]; //立即找到第i个元素
}
- 1
- 2
- 3
- 4
顺序表的按值查找是，查找L中第一个元素值等于e的元素，它会依次沿着顺序表向后查找，找到后返回其位序。
/*顺序表的按值查找 （查找L中第一个元素值等于e的元素并返回其次序）*/
int LocateElem(SqList L,int e) {
for(int i=0; i<L.length; i++) //依次从前往后查找
if(L.data[i]==e)
return i+1; //数组下标为i的元素值为e，返回其位序i+1（数组从0开始）
return 0; //未找到元素，退出循环查找失败
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
例如对创建的顺序表，查询顺序表中第3个位置的数据元素，另外查询顺序表中第一个元素值等于“4”的数据元素，其完整代码如下：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、顺序表的按位查找 （获取L中第i个位置元素的值）*/ int GetElem(SqList L,int i) { return L.data[i-1]; //立即找到第i个元素 } /*5、顺序表的按值查找 （查找L中第一个元素值等于e的元素并返回其次序）*/ int LocateElem(SqList L,int e) { for(int i=0; i<L.length; i++) //依次从前往后查找 if(L.data[i]==e) return i+1; //数组下标为i的元素值为e，返回其位序i+1（数组从0开始） return 0; //未找到元素，退出循环查找失败 } //主函数 int main() { SqList L; int a,b; InitList(L); CreatList(L); printf("顺序表为：\n"); DispList(L); printf("\n"); printf("按位查找第3个元素的值：\n"); a=GetElem(L,3); printf("%d \n",a); printf("按值查找值为4的元素：\n"); b=LocateElem(L,4); printf("%d \n",b); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
运行结果如下：
基本操作的完整代码
以上顺序表基本操作的完整代码如下：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、将顺序表中的所有元素逆置并输出*/ void ReverseList(SqList L) { int temp; for(int i=0; i<L.length/2; i++) { temp=L.data[i]; L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=temp; } DispList(L); //调用输出函数 } /*5、顺序表的插入操作 （在L的位序i处插入元素e）*/ bool ListInsert(SqList &L,int i, int e) { if (i<1||i>L.length||L.length>=MaxSize) //在[1,length+1]内有效且未存满或等于最大长度 return false; //插入失败返回 false for(int j=L.length; j>=i; j--) //j变量等于顺序表的长度 L.data[j]=L.data[j-1]; //将要插入的位置，第i个元素及以后的元素后移，先移动后面的元素，即数组下标小的赋给下标大的 L.data[i-1]=e; //由于数组的下标是从0开始的，所以位序要减一，即将要插入的元素e赋值给L.data[i-1] L.length++; //数组长度加1 return true; //插入成功返回 true } /*6、顺序表的删除操作 （删除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 } /*7、顺序表的按位查找 （获取L中第i个位置元素的值）*/ int GetElem(SqList L,int i) { return L.data[i-1]; //立即找到第i个元素 } /*8、顺序表的按值查找 （查找L中第一个元素值等于e的元素并返回其次序）*/ int LocateElem(SqList L,int e) { for(int i=0; i<L.length; i++) //依次从前往后查找 if(L.data[i]==e) return i+1; //数组下标为i的元素值为e，返回其位序i+1（数组从0开始） return 0; //未找到元素，退出循环查找失败 }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
*顺序表删除的常用操作
- 删除顺序表中的最小值
- 删除顺序表中的所有特定值的元素
- 删除顺序表值在特定区间的元素
- 删除顺序表中重复元素
- 删除有序表中重复元素
具体的实现步骤感兴趣的小伙伴可以看之前这篇文章：
数据结构学习笔记：顺序表的删除操作及其演化题目总结
*顺序表的常用合并操作
- 顺序表的合并操作
若要将两个顺序表的数据元素合并，通过创建一个CombineList1()函数，将顺序表L1和顺序表L2分别添加至顺序表L3中，该函数中包含三个参数，分别是SqList L1,SqList L2,SqList &L3（顺序表L3由于被更改，所以要用引用符号），如下：
bool CombineList1(SqList L1,SqList L2,SqList &L3) {
...
}
- 1
- 2
- 3
只需设置一个while()循环，条件是该顺序表的长度，每次将该顺序表的值赋给最终顺序表，且每次循环变量都加1，如下：
while(i<L1.length)
L3.data[k++]=L1.data[i++];
while(j<L2.length)
L3.data[k++]=L2.data[j++];
- 1
- 2
- 3
- 4
该算法的完整代码：
/*合并两个顺序表*/
bool CombineList1(SqList L1,SqList L2,SqList &L3) {
InitList(L3);
int i=0,j=0;
int k = 0;
while(i<L1.length)
L3.data[k++]=L1.data[i++];
while(j<L2.length)
L3.data[k++]=L2.data[j++];
L3.length=k;
return true;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
例如，创建两个顺序表L1、L2，顺序表L1的数据元素依次为4、5、0、2、-1；顺序表L2的数据元素依次为8、1、4、7、2，将这两个顺序表合并为顺序表L3，并最后输出顺序表L3：
代码如下：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、合并两个顺序表*/ bool CombineList1(SqList L1,SqList L2,SqList &L3) { InitList(L3); int i=0,j=0; int k = 0; while(i<L1.length) L3.data[k++]=L1.data[i++]; while(j<L2.length) L3.data[k++]=L2.data[j++]; L3.length=k; return true; } //主函数 int main() { SqList L1,L2,L3; int a,b; InitList(L1); InitList(L2); InitList(L3); printf("建立第一个顺序表！\n"); CreatList(L1); DispList(L1); printf("\n"); printf("建立第二个顺序表！\n"); CreatList(L2); DispList(L2); printf("\n"); printf("合并后的顺序表如下：\n"); CombineList1(L1,L2,L3); DispList(L3); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
运行结果如下：
- 有序顺序表的合并操作
若要将两个有序顺序表的数据元素合并，我们则要对上述代码进行修改，即按顺序依次取两个顺序表较小的数据元素存入新的顺序表中，然后对剩余的数据元素再添加至新的顺序表的后面，创建一个函数CombineList2()：
bool CombineList2(SqList L1,SqList L2,SqList &L3) {
...
}
- 1
- 2
- 3
该算法的完整代码如下：
/*5、合并有序顺序表*/ bool CombineList2(SqList L1,SqList L2,SqList &L3) { if(L1.length+L2.length>MaxSize) return false; int i=0,j=0; int k = 0; InitList(L3); while(i<L1.length&&j<L2.length) { //对两个顺序表中的元素两两比较，将小者存入结果表 if(L1.data[i]<=L2.data[j]) L3.data[k++]=L1.data[i++]; else L3.data[k++]=L2.data[j++]; } while(i<L1.length) L3.data[k++]=L1.data[i++]; while(j<L2.length) L3.data[k++]=L2.data[j++]; L3.length=k; return true; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
注：该代码参考《王道 数据结构 考研复习指导》
例如，创建两个有序顺序表L1、L2，有序顺序表L1的数据元素依次为-5、0、3、7；有序顺序表L2的数据元素依次为1、7、10，将这两个有序顺序表合并为有序顺序表L3，并最后输出有序顺序表L3：
代码如下：
#include<stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; } SqList; /*1、初始化顺序表*/ void InitList(SqList L) { L.length=0; } /*2、顺序表的建立*/ void CreatList(SqList &L) { printf("请输入建立顺序表的元素个数：\n"); scanf("%d",&L.length); for(int i=0; i<L.length; i++) { int number=i+1; printf("请输入第%d个整数：\n",number); scanf("%d",&L.data[i]); } } /*3、顺序表的输出（从头到尾输出顺序表中各元素的值）*/ void DispList(SqList L) { for(int i=0; i<L.length; i++) printf("%d ",L.data[i]); } /*4、合并有序顺序表*/ bool CombineList2(SqList L1,SqList L2,SqList &L3) { if(L1.length+L2.length>MaxSize) return false; int i=0,j=0; int k = 0; InitList(L3); while(i<L1.length&&j<L2.length) { //对两个顺序表中的元素两两比较，将小者存入结果表 if(L1.data[i]<=L2.data[j]) L3.data[k++]=L1.data[i++]; else L3.data[k++]=L2.data[j++]; } while(i<L1.length) L3.data[k++]=L1.data[i++]; while(j<L2.length) L3.data[k++]=L2.data[j++]; L3.length=k; return true; } //主函数 int main() { SqList L1,L2,L3; int a,b; InitList(L1); InitList(L2); InitList(L3); printf("建立第一个有序顺序表！\n"); CreatList(L1); DispList(L1); printf("\n"); printf("建立第二个有序顺序表！\n"); CreatList(L2); DispList(L2); printf("\n"); printf("合并后的有序顺序表如下：\n"); CombineList2(L1,L2,L3); DispList(L3); }
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
运行结果如下：
