408考研数据结构复习（线性表）
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。线性表一般表示为La1a2a3anLa1a2a3……an其中，a1为表头元素，an为表尾元素，除了表头元素，每个元素有且仅有一个直接前驱，除了表尾元素，每个元素有且仅有一个直接后继。以下为线性表的某些特点：★表是有限的，即n不能是无限大。★表中的元素是有逻辑上的顺序性。（记得上一章提到过链表的话是不遵循物理地址存储空间上的顺序性的
文章目录
复习重点
线性表在算法题中经常出现，因为实现起来容易而且代码量并没有很多，注意在实现的时候考虑算法的时间复杂度和空间复杂度。
一、线性表的定义和基本操作
1.线性表的定义
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。线性表一般表示为
L
=
(
a
1
,
a
2
,
a
3
,
…
…
,
a
n
)
L=(a_1,a_2,a_3,……,a_n)
L=(a1,a2,a3,……,an)，
其中，a1为表头元素，an为表尾元素，除了表头元素，每个元素有且仅有一个直接前驱，除了表尾元素，每个元素有且仅有一个直接后继。
以下为线性表的某些特点：
★表是有限的，即n不能是无限大。
★表中的元素是有逻辑上的顺序性。（记得上一章提到过链表的话是不遵循物理地址存储空间上的顺序性的，所以对于线性表只能有逻辑上的顺序性）
★表中的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
1.线性表的基本操作
InitList(&L):初始化线性表。
Length(L):求表长。
LocateElem(L,e):查找表中等于e的元素。
GetElem(L,i):查找表中第i个元素的值并返回。
ListInsert(&L,i,e):在表中第i个位置插入元素e，并返回新表。
ListDelete(&L,i,&e):在表中删除第i个元素，并用e来返回删除的元素，同时返回新表。
PrintList(L):打印线性表L。
IsEmpty(L):线性表是否为空，是则返回true，否则返回false。
DestroyList(&L):销毁线性表，释放L所占用的空间。
附：个人觉得对于线性表的这些操作记得有就行，基本不会考这些基本操作的具体实现，一般都是可以直接使用的，在不给你这些基本操作名的时候，可以自己申明但是尽量写的和上述差不多。比如IsEmpty可以写成Empty，ListDelete可以写Del_List,都是没什么太大问题的。
二、线性表的顺序表示
1.什么是顺序表
简单来说，顺序表就是线性表(逻辑结构)的顺序存储(存储结构)，也就是说顺序表就是一个数据结构了，还记得上一篇提到的顺序存储的特点吗，逻辑上相邻的元素存储的物理地址空间上也相邻，所以顺序表是用一组地址连续的存储单元来依次存放线性表中的数据元素。
注意线性表中元素的位序从1开始，数组下标从0开始。
顺序表的存储类型可以定义为如下：
#define MaxSize 20 //定义线性表的最大长度
typedef struct
{
ElemType data[MaxSize]; //元素
int length; //顺序表当前长度
}SqList; //顺序表类型
当然也可以定义如下：
#define InitSize 100 //初始表大小
typedef struct
{
ElemType *data; //动态分配数组的指针
int MaxSize,length; //最大长度和当前长度
}SeqList; //动态分配数组的顺序表的类型定义
对于C语言，初始的动态分配语句为：
SeqList L;
L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
对于C++，初始的动态分配语句为:
SeqList L;
L.data=new ElemType[InitSize]
！！！注意：动态分配虽然有指针但不是链式存储，同样属于顺序存储结构，只是分配的空间大小可以在运行时动态决定。
2.顺序表上基本操作的实现
（1）插入操作代码如下,(1<=i<=L.length+1)：
bool ListInsert(SqList &L,int i,ElemType e){
if(i<1|| i>L.length+1) return false; //插入元素位置不合法
if(L.length>=MaxSize) return false; //当前表已满，无法继续插入
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1]; //第i个元素之后所有元素右移
L.data[i-1]=e; //将第i个元素赋值为e
L.length++; //插入后表长+1
return true; //插入成功！
}
注意：在判断插入位置合法时为length+1是因为在表的末尾插入就是length+1
最好情况：表尾插入元素，不需要右移元素，直接赋值即可，时间复杂度为O(1);
最差情况：表头插入元素，全部元素右移，时间复杂度为O(n);
平均情况：时间复杂度为O(n/2)。
（2）删除操作代码如下，(1<=i<=L.length)：
bool ListDelete(SqList &L,int i,ElemType &e){
if(i<1||i>L.length) return false; //删除位置不合法
e.data=L.data[i]; //返回值
for(int j=i;j<L.length;j++)
L.data[j-1]=L.data[j]; //i位置之后的所有元素左移
L.length--;
return true;
}
最好情况：表尾删除元素，不需要左移元素，直接删除即可，时间复杂度为O(1);
最差情况：表头删除元素，全部元素左移，时间复杂度为O(n);
平均情况：时间复杂度为O(n)。
个人错题&统考真题：
01.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用(D)的存储方式。
A.单链表 B.双向链表 C.单循环链表 D.顺序表
解答：一开始选择了B项，因为双向链表找前驱和后继元素的时间复杂度都是O(1)但是没考虑到找到第i个元素需要从头开始，即时间复杂度为O(n)，所以本题ABC选项的时间复杂度都为O(n)，D项中顺序表可以随机存取，所以时间复杂度为O(1)，此时效率最高。
02.【2010统考】设将n(n>1)个整数存放到一维数组R中试设计一个时向和空间两方面尽可能高效的算法将R中整数序列循环左移p(0<p<n)个位置，即将R中的数据由(X0,X1,……,Xn-1)变换为(Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1)
(1)给出算法去的基本设计思想。
(2)根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
解答：
（1）
由图可以看出，我们需要将0-(p-1)位置的数组A部分逆置，再将p~(n-1)位置的数组B部分逆置，最后将整个数组逆置就可以得到我们想要的数组了。
(2)
void Reverse(int R[],int i,int j,int length){ //将数组中下标为i元素到下标为j的元素逆置,i<=j,length为当前数组长度
if(i<0||j>length-1) printf("不合法"); //位置不合法
if(i>j) printf("不合法"); //i,j不合法
if(length<=0) printf("不合法"); //数组为空
for(int k=i;k<=(i+j)/2;k++)
swap(R[k],R[j-(k-i)]);
}
void func(int R[],int p,int length){ //这里写成R[]或者是*R都可以
Reverse(R,0,p-1);
Reverse(R,p,n-1);
Reverse(R,0,n-1);
}
（3）算法的时间复杂度为O(n)，空间复杂度为O（1）。
个人觉得这应该算是这题的最优解了。
03.【2011统考】一个长度为L(L≥1)的升序序列S,处在第L/2个位置的数称为S的中位数。例如,若序列
S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是包含其所有元素的升序序列
的中位数。例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11。现在有两个等长升序序列
A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C、C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
解答：
(1)
我的思考：我最初是想到合并之后排序成一个长的有序序列找中位数，但是会消耗空间和时间，显得算法不够优。看了答案之后恍然大悟豁然开朗TAT。
因为是俩个等长的升序序列，所以中位数一定是中间的数，若俩个数列的中位数相等，那么合并之后肯定也是原来的中位数。假设S1的中位数为A，S2的中位数为B。
①A=B，俩个序列的中位数就是A或者B。
②A>B，说明中位数在A的左边，B的右边，所以舍弃A的右半部分和B的左半部分，继续令A等于剩下S1数列的中位数，令B等于剩下S2数列的中位数，一直比对到只剩一个数，若还不相等则取较小的数为中位数。
③A<B，说明中位数在A的右边，B的左边，所以舍弃A的左半部分和B的右半部分，继续令A等于剩下S1数列的中位数，令B等于剩下S2数列的中位数，一直比对到只剩一个数，若还不相等则取较小的数为中位数。
(2)
int Mid_Search(int S1[],int S2[],int n){
int A,B; //S1,S2的中位数
int s1_low=0,s1_mid,s1_high=n-1,s2_low=0,s2_mid,s2_high=n-1; //辅助下标
while(s1_low!=s1_high||s2_low!=s2_high){
s1_mid=(s1_low+s1_high)/2;
s2_mid=(s2_low+s2_high)/2;
A=S1[s1_mid];
B=S2[s2_mid];
if(A==B) return A;
if(A>B){
if((s1_high-s1_mid+1)%2!=0){ //有奇数个元素
s1_high=s1_mid;
s2_low=s2_mid;
}
else{
s1_high=s1_mid;
s2_low=s2_mid+1;
}
}
else{
if((s1_high-s1_mid+1)%2!=0){ //有奇数个元素
s2_high=s2_mid;
s1_low=s1_mid;
}
else{
s2_high=s2_mid;
s1_low=s1_mid+1;
}
}
}
return A<B?A:B;
}
(3)算法的时间复杂度为log2n，算法的空间复杂度为O(1)。
04.【2013统考】已知一个整数序列A=(a0,a1,…,an-1)，其中0<=ai<n(0<=i<n)。若存在ap1=ap2=ap3=apm=x其m>n/2(0<=pk<n,1<=k<=m)，则称x为A的主元素。例如有A=(0,5,5,3,5,7,5,5)，
则5位主元素；又如A=(0,5,5,3,5,1,5,7)，A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计尽可能高效的算法，找出A的主元素。若存在主元素，
则输出主元素；否则输出-1。要求：
(1)给出算法的基本设计思想
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计的算法的时间复杂度和空间复杂度
解答：(最简单的方法就是先排序再统计，可能时间复杂度会高一点，但是不妨碍拿分，丢一俩分和消耗时间去想最优解来对比，可能得不偿失，以下为最优解，讲究的就是一个贪心的贪字)
(1)由题意可以知道主元素的个数一定大于这个序列一半个数的数，那我们就可以跟玩消消乐一样，用一个主元素去消除一个非主元素，最后多出来的就是序列中最多的数。我们将第一个元素设为主元素，另计数器初始为1，然后如果下一个元素和它不相等，则计数器减一，若计数器减为0，则下一个数便是新的主元素，并重置计数器为1，一直循环到数列结束。判断c是否是真正的主元素，因为此时得到的元素为序列中最多的元素并不是一定是主元素。
(2)
int func(int A[],int n){ //找出序列中最多的数
int m=A[0],c=1; //初始化主元素为A[0],计数器为1
for(int i=1;i<n;i++){
if(m==A[i]) c++;
else{
if(c>0) c--;
else{
m=A[i];
c=1;
}
}
}
//以下开始验证是否是主元素
if(c>0){
c=0;
for(int i=0;i<n;i++){
if(A[i]==m) c++;
}
}
if(c>(n/2)) return m;
else return -1;
}
(3)时间复杂度为O(n),空间复杂度为O(1)。
05.【2018统考】给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
(1)给出算法的基本设计思想
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计的算法的时间复杂度和空间复杂度
解答：（先思考，题目只要求时间上尽可能高效，那意思就是我们可以设计一个用空间换时间的算法）
(1)对于n个整数的数列，最多只有n个不同的正整数，那么我们只需要再开辟一个n+2大小的辅助全0数列，我们令1号位置放正整数1出现的次数，依次类推，我们再遍历一遍数组，得到是负数或0就不管，正整数就令对应下标的数组元素加一，之后再从下标为1开始遍历一遍辅助数列，读到的第一个为0的元素的下标即为数组中未出现的最小正整数。
(2)
int Un_min(int A[],int n){
int B[n+2],m; //m为未出现的最小正整数
memset(B,0,sizeof(int)*(n+2)); //构造全0辅助数组
cout<<B[6];
for(int i=0;i<n;i++){
if(A[i]>0) B[A[i]]++;
}
for(int i=1;i<n+2;i++){
if(B[i]==0){
m=i;
break;
}
}
return m;
}
(3)算法的时间复杂度和空间复杂度都是O(n)。
06.定义三元组 (a,b,c)（a,b,c 均为整数）的距离 D=|a−b|+|b−c|+|c−a|。
给定 3 个非空整数集合 S1,S2,S3，按升序分别存储在 3 个数组中。
请设计一个尽可能高效的算法，计算并输出所有可能的三元组 (a,b,c)（a∈S1,b∈S2,c∈S3）中的最小距离。
例如 S1={−1,0,9},S2={−25,−10,10,11},S3={2,9,17,30,41} 则最小距离为 2，相应的三元组为 (9,10,9)。要求：
(1)给出算法的基本设计思想
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计的算法的时间复杂度和空间复杂度
解答：(这题想要拿满分可能有点难度，但是对于一般情况下来说，暴力破解即可，T(n)=O(n3)
(1)
观察上图可得，当c点在a点和b点中间的时候，三者相加一定是最短的。因为当c点在外面时，一定会使得|a-c|+|b-c|>|a-b|，而在内时，|a-c|+|b-c|=|a-b|。
所以考虑c在a，b里时，|a-c|+|b-c|+|a-b|=2|a-b|，所以只要找出俩点|a-b|最短并且使c在a，b之间即可。所以，我们取S1,S2,S3中第一个点为初始点，每次只向右移动最小的那个点，记录已经遍历的D的最小值，当某个集合的点都被遍历完之后，此时的D即为所需求的最小值。
(2)
int Ismin(int a,int b,int c){ //判断a是否为abc三个数中最小的数
if(a<=b&&a<=c) return 1; //是则返回1
else return 0;
int func(int S1[],int S2[],int S3[],int n1,int n2,int n3){
int m=abs(S1[0]-S2[0])+abs(S1[0]-S3[0])+abs(S2[0]-S3[0]); //m初始化为最小距离
int i=j=k=0;
while(i<n1&&j<n2&&k<n3){
D=abs(S1[i]-S2[j])+abs(S1[i]-S3[k])+abs(S2[j]-S3[k]);
if(D<m) m=D;
if(Ismin(S1[i],S2[j],S3[k])==1) i++;
else if(Ismin(S2[j],S1[i],S3[k])==1) j++;
else k++;
}
return m;
}
(3)算法的时间复杂度为O(n),空间复杂度为O(1)。
三.线性表的链式表示
1.单链表
线性表的链式存储称为单链表。对于每个链表结点，由一个数据域和一个指针域构成，数据域用来存放结点元素自身的信息，指针域next指向后继结点（存放后继结点的地址）。
结点类型描述如下：
typedef struct LNode{ //单链表
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList; //数据类型定义
由上一章可以知道，链表可以解决顺序表需要大量连续存储单元的缺点，但由于其需要指针域又会浪费存储空间，对于链表而言插入和删除操作比较方便，但是不能随机读取。
通常我们用一个头指针来标识一个单链表，如某单链表L，头指针为NULL时，L为空表。在单链表第一个结点之前附加一个结点称为头结点。头结点的数据域可以不设任何信息，一般用来记录表长。
注意区分头结点和头指针的区别噢。
为什么要引入头结点呢？
可以使对链表任何一个结点的操作都变得一样（头结点一般不需要操作）；使头指针始终非空，指向头结点，对于空表和非空表的处理也得到了统一。
2.单链表上的基本操作
（1）头插法和尾插法建立单链表：比较简单就不过多描述。
（2）按序号查找结点 LNode *GetElem(LinkList L,int i)。
（3）按值查找结点LNode *LocateElem(LinkList L,ElemType e)。
（4）插入结点:注意分为前插和后插，后插比较简单，前插可以通过先后插再交换data域的方法进行。
（5）删除结点：算法主要耗时在查找上。
（6）求表长：计算（不含头结点）结点个数
3.双链表
在单链表结点的基础上，每个结点多了一个前驱指针，prior域。
插入删除操作比较简单不过多累赘，有需要的uu可以自行看书。
4.循环链表
在单链表的基础上，使最后一个结点的指针不是NULL，而是指向头结点，因此循环链表非空的条件为：
头结点的指针等于头指针。
5.循环双链表
在循环单链表的基础上，添加前驱指针域，使头结点的前驱指向最后一个结点。非空条件为：
头结点的prior和next都等于头指针L。
6.静态链表
一般不用。
个人错题&统考真题
01.给定有n个元素的一维数组，建立一个有序单链表的最低时间复杂度是(D)
A.O(1) B.O(n) C.O(n2) D.O(nlog2n)
解答：先排序再建立单链表，数组中排序的最低时间(快排，2路归并，堆排序)为nlog2n,建立单链表的时间为O(n),所以建立有序单链表的最低时间复杂度为O(nlog2n)，
02.【2009统考】已知一个带有表头结点的单链表,结点结构为
data | link
假设该链表只给出了头指针list。在不改变链表的前提下,请设
个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为
正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,
只返回0。要求
(1)描述算法的基本设计思想。
(2)描述算法的详细实现步骤。
(3)根据设计思想和实现步骤,采用程序设计语言描述算法(
用C或C++或JAVA语言实现),关键之处请给出简要注释。
解答：本题的评分俩次遍历（包括俩次）以上的算法都最高分为10分，所以需要找到一个一次遍历就能找到答案的写法
(1)我们设一个头遍历指针和一个尾遍历指针，让头指针和尾指针之间宽带为k，即让头指针先移动k个位置后，头指针和尾指针一起移动，若头指针到达表尾结点还没有移动k个位置说明，查找失败。否则查找成功，倒数第k个结点为尾指针所指向的结点。
(2)
①初始化头遍历指针和尾遍历指针h、t，使其都指向头结点的next结点。
②初始化计数辅助量count=0；
③当h不为NULL时，若count=k，则t也开始遍历，否则count++，h继续遍历
④当h为NULL时，count=k，则查找成功，输出t现在所指向结点的数据域，返回1；否则，说明k超过了线性表的长度，查找失败，返回0。
(3)
typedef int ElemType; //链表数据类型
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
int Search(LinkList list,int k){
LNode *h=list->next,*t=list->next; //初始化h，t
int count=0; //初始化辅助计数变量
while(h!=NULL){
if(count==k){
t=t->next;
}
else count++;
h=h->next;
} //结束while
if(count==k){ //若头遍历指针遍历结束后count=k
cout<<q->data<<endl;
return 1;
}
else return 0;
}
03.【2019统考】设线性表L=(a1，a2，a3，……,an)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node{
int data;
struct node ∗next;
}NODE;
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各节点，得到线性表L’=(a1，an，a2，a(n-1)，a3，…)。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或者C++语言描述算法，关键之处给出注释。（3）说明你所设计的算法的时间复杂度。
解答：（刚看到题目就想到将后面n-1个元素逆置然后再将后面n-2个元素逆置这样达到，但是每次逆置的时间复杂度为O(n),n次就会达到O(n2)这样一个效果，看了答案之后发现还有O(n)时间复杂度的方法）
(1)观察重排后的线性表其实是原表中第一个元素和最后一个元素，第二个元素和倒数第二个元素的组合顺序，为了方便在后半段取结点，我们先要将后半段链表逆置，否则每次都需要重新读链表浪费时间。
①通过上题一样的思想，双指针遍历法，前指针每次移动后指针步数的俩倍，为了减小误差，设后指针每次一步，前指针俩步。
②找到中间结点后，将链表后半段逆置
③从单链表前后俩段中依次各取一个结点，按要求重排
(2)
void change_list(LinkList &L){
LNode *p,*q,*r,*s;
p=q=L;
while(q->next!=NULL){
p=p->next; //后指针走一步
q=q->next;
if(q->next!=NULL) q=q->next; //前指针走俩步
}
q=p->next; //q指向后半段链表首结点
p->next=NULL; //将链表断开
while(q!=NULL){ //将表后半段逆置
r=q->next; //临时存储q的后继结点
q->next=p->next;
p->next=q; //使p指向当前q所指的结点
q=r; //配上前面的r=q->next，相当于q一直在++往后移
}
s=L->next; //s为前辈的首结点
q=p->next; //q为后半段首结点
p->next=NULL;
while(q!=NULL){ //重新组合
r=q->next;
q->next=s->next;
s->next=q;
s=q->next;
q=r;
}
}
（3）时间复杂度为3个O(n)之和为O(n)。
总结
本章是算法设计题的重点考点，一定要多多留意代码的写法。如果有时候来不及想思路，直接暴力解题也未尝不是一种好方法。能用伪代码的形式尽量用伪代码，实在不行就写个文字叙述也无伤大雅。
汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家，助力解决“卡脖子”问题
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)