数据结构复习

由于复习比较个人向,因此主要记录的是我容易混淆的知识点以及自己一直记不住的一些题

另外题目基本全部来自某考研复习资料,因此建议辅助该书学习为佳

数组和链表

重要知识点

题目

1.找出数组中出现次数最多的元素

时间复杂度:O(N)

空间复杂度:O(1)

依次扫描所给数组中的每个整数,将第一个遇到的整数Num保存到c中,记录Num出现的次数为1;若遇到的下一个整数仍等于Num,则计数加1,否则计数减1;当计数减到0时,将遇到的下一个整数保存到c中,计数重新记为1,开始新一轮计数,即从当前位置开始重复上述过程,直到扫描全部数组元素。

2.求两个等长升序序列合并后的中位数

时间复杂度:O(logN)

空间复杂度:O(1)

分别求两个升序序列A、B的中位数,设为a和b,求序列A、B的中位数过程如下:

(1)若a=b,则a或b即为所求中位数,算法结束;

(2)若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等;

(3)若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等;

在保留的两个升序序列中,重复过程(1)~(3),直到两个序列中均只含一个元素时为止,较小者即为所求的中位数。

3.从尾到头反向输出带头结点的单链表中每个结点的值

时间复杂度:O(N)

空间复杂度:O(N)

利用递归函数,思路如下:

1
2
3
4
5
6
7
void R_Print(LinkList L)
{
if (L->next != nullptr)
R_print(L->next);
if (L!=nullptr)
cout<<L->data<<" ";
}

4.将带头结点的单链表就地逆置。

时间复杂度:O(N)

空间复杂度:O(1)

将头结点摘下,然后从第一个结点开始,依次插入到头结点之后(即头插法建立单链表)。

5.给定两个单链表,找出两个链表的公共结点。

时间复杂度:O(len1+len2)

空间复杂度:O(1)

由于两个链表有一个公共结点,则该公共结点之后的所有结点都是重合的。

因此假设一个链表比另一个链表长k个结点,只需在较长的链表上先遍历k个结点,然后再同步遍历。接下来,一一比较即可找出公共结点。

6.遍历一遍找出带头结点的单链表倒数第k个结点。

定义两个指针变量p和q,初始时均指向头结点的下一个结点(链表的第一个结点),p指针沿链表移动;当p指针移动到第k个结点时,q指针开始与p指针同步移动;当p指针移动到最后一个结点时,q指针所指结点为倒数第k个结点。关键:让一个结点先走一定距离。

7.将线性表L=(a1,a2,…,an-2,an-1,an)重新排列为L’=(a1,an,a2,an-1,a3,an-2…)。

时间复杂度:O(N)

空间复杂度:O(1)

分为三个重要的步骤:

(1)找出链表L的中间结点:与第6题思路相同,设置两个指针p和q,指针p每走一步,q走两步。当指针q到达链表尾的时候,p恰好在链表的中间结点位置;

(2)原地逆置:参考第4题思路,利用头插法逆置;

(3)从单链表前后两段各取一个结点,按要求重排。

以上三步时间复杂度均为O(N),因此总的时间复杂度也为O(N)。

栈和队列

重要知识点

1.n个不同元素进栈,出栈元素不同排列的个数为1/(n+1)*C(2n,n)

2.顺序表存储的队列(依照ppt):

front指向队头元素的前一个元素,rear指向队尾元素

skAnH0.jpg

3.循环队列:

skVhcQ.jpg

  • 队头指针进1: front = (front + 1) % maxSize;
  • 队尾指针进1: rear = (rear + 1) % maxSize ;
  • 队列初始化:front = rear = 0;
  • 队空条件:front == rear;
  • 队满条件:(rear + 1) % maxSize

4.队列中,注意入队只改变rear的值,出队只改变front的值。

5.运算符优先级(中缀表达式转后缀表达式):

操作符 ( *,/ +,- )
isp(栈内优先级) 1 5 3 6
icp(栈外优先级) 6 4 2 1

​ 读取字符ch:

  • 若ch是操作数,则直接输出,同时继续读取;
  • 若ch是操作符,则需要判断ch的优先级icp和当前位于栈顶的操作符op的优先级isp,执行下面的循环过程:
    • 若icp(ch)>isp(op),则ch进栈,继续读取;
    • 若icp(ch)<isp(op),则退栈并输出;
    • 若icp(ch)==isp(op),退栈但不输出,若退出的是’(‘则继续读取。

题目

1.若一个栈的输入序列是P1,P2,…Pn,输出序列是1,2,3,…n,若P3=1,则P1的值?

P1可以取除了2以外的所有值。

P2可以取除了n以外的所有值。

P4可以取除了n-1,n以外的所有值。

2.一个栈的入栈序列为1,2,3,…,n,出栈数列是P1,P2,P3,…,Pn。若P2=1,则P3的可能取值个数为多少?

n-1个。

很显然:3之后的4,5,…,n都是P3可取的数(持续进栈直到该数入栈后立即出栈)。

接下来考虑1和2:当P1=1时,P3可取2;当P1=2时,P3可取1。

3.若用数组A[0…5]来实现循环队列,且当前rear和front的值分别为1和5,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为?

3和0。本题需要注意的是从循环队列中删除操作的方法是front=(front+1)%maxSize,注意不要反向。

稀疏矩阵

重要知识点

1.稀疏矩阵中采用结构体存储数据:

1
2
3
4
5
struct Trituple
{
int row,col; //非零元素所在的行号、列号
Type value; //非零元素的值
}

2.快速转置算法:

建立辅助数组rowSize 和 rowStart,记录矩阵转置后各行非零元素个数各行元素在转置三元组表中开始存放位置

扫描矩阵三元组表,根据某项的列号,确定它转置后的行号,查 rowStart表,按查到的 位置直接将该项存入转置三元组表中。