数据结构篇_编程思想板块_第一章顺序表和链表

2022年05月11日 阅读数:4
这篇文章主要向大家介绍数据结构篇_编程思想板块_第一章顺序表和链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
  • 编程思想板块最主要的内容是数据结构经典题目及解答题目所需的编程思想,愿对您能有所帮助
各数据结构程序名称
顺序表 Sqlist
链表结点 LinkList(结构体类型指针,malloc处不用加*)LNode(结构体类型对象)![img](file:///C:\Users\ADMINI~1\AppData\Local\Temp\ksohtml\wps60C8.tmp.jpg)
顺序栈链式栈 SqStake,LiStake(结构体类型指针,malloc处不用加*)
顺序队列链式队列 SqQueue,LinkQueue
顺序串堆中串链式串KMP算法中 SString,HString,LinkString,String
链式二叉树线索二叉树双亲表示法时的树孩子兄弟表示法时的树 BiTNode,*BiTree(指向根节点,下同)ThreadNode,*ThreadTree,PTree,CSNode,*CSTree
邻接矩阵存储图邻接表存储图图遍历 MGraph,ALGraph,Graph
顺序查找折半查找 SSTable,SeqList

1、顺序表和链表

① 若以线性表表示集合并进行集合的各类运算,应先对表中元素进行排序html

② 常考将两个有序链表合成一个新的有序表node

③ 在这一章中哈希表的思想很经常使用算法

④ 注意:代码后记得要更新length值编程

⑤ 逆置的常见方法:数组

(1) 头插法数据结构

(2) 递归函数

(3) 借助栈设计

⑥ 链表中:3d

(1) 前插操做时:将待插入结点s依旧插入P后面,而后交换s和p的值,此时时间复杂度为O(1)指针

(2) 删除结点p:将后继结点的值赋给本身p,而后删除后继结点,此时时间复杂度为O(1)

(3) 若题目中只要求在时间上尽量高效,则采用空间换时间的方法

1)顺序表经典题目的编程思想

1. 对长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为0(1)的算法,该算法删除线性表中全部值为x的数据元素经典的顺序表删除元素的方法

思想:

① 用k记录顺序表L中不等于x的元素个数(即须要保存的元素个数),边扫描L边统计k,并将不等于x的元数向前移动k个位置(初始k=0),最后修改L的长度

② 用k记录顺序表L中等于x的元素个数,边扫描L边统计k,并将不等于x的元素前移k个位置,最后修改L的长度

2. 从有序顺序表中删除全部其值重复的元素,使表中全部元素的值均不一样若为无序的可用哈希表解决

思想:

① 用相似于直接插入排序的思想,初始时将第一个元素视为非重复的有序表。以后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同,则继续问后判断,若个同,则插入前面的非重复有序表最后,直至判断到表尾为止

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

思想:

① 首先,按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。而后,看哪一个表还有剩余,将剩下的部分加到新的癞序表后面

4. 已知在一维数组A[m+n]中依次存放两个线性表(a,a2,...,am)和(b1,b2,b3,..,bn)。试编写一个函数,将数组中两个顺序表的位置互换,即将(b1,b2,b3,..,bn)放在(a,a2,...,am)的前面

思想:

① 

5.

思想:

6. 一个长度为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的中位数

思想:

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

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

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

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

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

7. 已知一个整数序列A=(a_0,a_1,...,a_(n-1)),其中0≤a_i<n(0≤i<n)。若存在a_p1=a_p2=...=a_pm=x且m>n/2(0≤P_k<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该思想也可用于求数组最长子序列(数组数据包括负数和正数))

思想:

① 给出算法的基本设计思想:算法的策略是从前向后扫描数组元繁,杯记出一个可能成为主元素的元素Num。而后从新计数,确认 Num是不是主元素。算法可分为如下两步:(摩尔投票法)

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

(2) 判断c中元素是不是真正的主元素。再次扫描该数组,统计c中元素出现的次数,若大于n/2,则为主元素:不然,序列中不存在主元素

8. 给定一个含n(n≥I)个整数的数组,请攻订一个杜时间一公马)向效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是l;数组{1,2,3}中未出现的最小正整数是4

思想:

① 要求在时间上尽量高效,所以采用空问换时间的办法。分配一个用于标记的数组B[n]用来记录A中是否出现了1~n中的正整数,B[0]对应正整数1,B[n-1]对应正整数n,初始化B中所有为0。因为A中含有n个整数,所以可能返回的值是 1n+1,当A中n个数刚好为1n 时返回n+1。当数组A中出现了小于等于0或大于n的值时,会致使1~~n中出现空余位置,返回结果必然在1~n中,所以对于A中出现了小于等于0或大于n的值,能够不采起任何操做

② 通过以上分析能够得出算法流程:从A[0]开始遍历A,若0<A[i]<=n.则令B[A[i]-1]=1;不然不作操做。对A遍历结束后,开始遍历数组B,若能查找到第一个知足B[i]==0的下标i,返回i+1即为结果,此时说明A中未出现的最小正整数在1~n之间。若Bii]所有不为0,返回i+1(跳出循环时i=n,i+1等于n+1),此时说明A中未出现的最小正整数是n+1

9. 定义三元组(a, b,c)(a、b、c均为正数)的距离D=a-b+|b-c+Ic - a。给定3个非空整数集合S、S2和S,按升序分别存储在3个数组中。请设计一个尽量高效的算法,计算并输出全部可能的三元组(a, b,c) (aES,bES, cES)中的最小距离。例如S={H1, 0, 9}, S={-25,-10, 10,11}SJ={2,9,17, 30, 41},则最小距离为2,相应的三元组为(9, 10, 9)

思想:

2)链表经典题目的编程思想

1. 设计一个递归算法,删除不带头结点的单链表L中全部值为×的结点

思想:

① 设f(L,x)的功能是删除以工为首结点指针的单链表中全部值等于x的结点,显然有f(L->next,x)的功能是删除以L->next为首结点指针的单链表中全部值等于x的结点。由此,能够推出递归模型以下。

(1) 终止条件:f(L,x)=不作任何事情; 若L为空表

(2) 递归主体:f(L, x)=删除*L结点;f(L->next, x); 若L->data==X

(3) :f(L,x)=f(L->next, x); 其余状况

2. 在带头结点的单链表L中,删除全部值为×的结点,并释放其空间假设值为×的结点不惟一,试编写算法以实现上述操做

思想:

① 采用尾插法创建单链表。用p指针扫描工的全部结点,当其值不为x时,将其连接到L以后,不然将其释放

3. 试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间复杂度为O(1)

思想:

① 将头结点摘下,而后从第一结点开始,依次插入到头结点的后面(头插法创建单链表),直到最后一个结点为止,这样就实现了链表的逆置

4. 给定两个单链表,编写算法找出两个链表的公共结点

思想:

① 先把问题简化:如何判断两个单向链表有没有公共结点?应注意到这样:一个事实:若两个链表有一个公共结点,则该公共结点以后的全部结点都是重合的,即它们的最后一个结点必然是重合的。所以,咱们判断两个链表是否是有重合的部分时,只须要分别遍历两个链表到最后一个结点。若两个尾结点是:同样的,则说明它们有公共结点,不然两个链表没有公共结点。

② 然而,在上面的思路中,顺序遍历两个链表到尾结点时,并不能保证在两个链表上同时到达尾结点。这是由于两个链表长度不必定同样。但假设一个链表比另外一个长k个结点,咱们先在长的链表上遍历k个结点,以后再同步遍历,此时咱们就能保证同时到达最后一个结点。因为两个链表从第一个公共结点开始到链表的尾结点,这一部分是重合的,所以它们肯足也是同时到达第一公共结点的。因而在遍历中,第一个相同的结点就是第一个公共的结点。

③ 根据这一思路中,咱们先要分别遍历两个链表获得它们的长度,并求出两个长度之差。在长的链表上先遍历长度之差个结点以后,再同步遍历两个链表,直到找到相同的结点,或者一直到链表结束。此时,该方法的时间复杂度为 O(len1 + len2)

5. 已知两个链表A和B分别表示两个集合,其元素递增排列。编制函数、求A与B的交集,并存放于A链表中

思想:

① 算法思想:采用归并的思想,设置两个工做指针pa和pb,对两个链表进行归并扫描,只有同时出如今两集合中的元素才连接到结果表中且仅保留一个,其余的结点所有释放。当一个链表遍历完毕后,释放另外一个表中剩下的所有结点(链表归并类型的试题在各学校历年真题中出现的频率很高

6.

思想:

① 问题的关键是设计一个尽量高效的算法,经过链表的一次遍历,找到倒数第k个结点的位置。算法的基本设计思想是:定义两个指针变盘p和q,初始时均指向头结点的下一个结点(链表的第一个结点)p指针沿链表移动;当指针移动到第k个结点时,4指针开始与p指针同步移动;当指针移动到最后一个结点时,指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描

7.

思想:

① 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链表进行一趟扫描。由于|datal≤n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的各结点,同时检查q[ldatal]的值,若为0则保留该结点,并令q[ldatal]=1;不然将该结点从链表中删除

② 用哈希表:设长度为n+1的数组,每次插入一个元素因元素值与数组下标相同故在数组相应位置置为1,若检测为1则删除当前结点,反之为0插入且置为1

8. 设计一个算法完成如下功能:判断一个链表是否有环,若是有,找出环的入口点并返回,不然返回NULL

思想:

① (快慢指针也可做为求表长一半的方法)

9. 设线性表L=(a_1,a_2,…,a_(n-1),a_n)采用带头结点的单链表保存,链表中的结点定义以下:

typedef struct node

{int data;

struct node*next;

}NODE;

请设计一个空间复杂度为O(1)且时间上尽量高效的算法,从新排列L中的各结点,获得线性表L'=(a_1,a_n,a_2,a_(n-1),a_3,a(n-2),…)

思想:

① 先观察L=(a_1,a_2,…,a_(n-1),a_n)和L'=(a_1,a_n,a_2,a_(n-1),a_3,a(n-2),…),发现L'是由L摘取第一个元素,再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素,须要先将L后半段原地逆置[题目要求空间复杂度为O(1),不能借助栈],不然每取最后一个结点都须要遍历一次链表

(1) 先找出链表L的中间结点,为此设置两个指针p和q,指针p每次走一步,指针q每次走两步,当指针q到达链尾时,指针p正好在链表的中间结点

(2) 而后将L的后半段结点原地逆置

(3) 从单链表先后两段中依次各取一个结点