【MOOC课程】浙大数据结构记录(上)

【MOOC课程】浙大数据结构记录(上) 数据结构

一些碎碎念：其实以前听过清华大学的 数据结构 OJ小记录（差不多快正好一年前了），而且也看到过一个博主曾经这两门课都上过对比过不同【清华看重课程深层的理论，浙大更轻松易懂一点】，可惜清华大学的上到上半段后就没有坚持下去搞完（主要是又看其他的课去了 热度变得好快哦 😂） 这次的笔记也主要是关于编程作业和自己一开始理解错了的地方。希望这次重拾能更深刻一点，这次尽量不像上次一样遇到不会就搜 至少我先挣扎个2小时… 不过做完一般我都会对比优劣和简易 如果有的话 wa 眼前一亮的那种 我会再次引用说明 之所以没有直接刷算法题，是因为我还是想从理论抓起的感觉会更扎实一点？虽然刷算法题也能接触到

【MOOC课程】浙大数据结构记录(下) 在这里：https://blog.csdn.net/qq_39537898/article/details/120015082 其实有想过把他们合并，但是太太太太长了 hhhh 所以就还是分一下上下 当做自我记录了。 giteee代码链接：https://gitee.com/kin_zhang/data-structure

第一周的题目是：

1. 最大子列和问题：是本次课最后讲到的4种算法的实验题，属于基本要求，一定要做；
2. Maximum Subsequence Sum：是2004年浙江大学计算机专业考研复试真题，要求略高，选做。其实也不难，是本次课最后讲到的算法的改造，挑战一下吧~
3. 二分查找：配合课后讨论题给出这道函数填空题，学有余力、并且会C语言编程的你可以尝试一下。你只需要提交一个函数，而不用交如main函数之类的其他函数。不会C语言的话，就研究一下课后关于二分法的讨论题吧~

01-复杂度1 最大子列和问题

给定K个整数组成的序列，“连续子列”被定义为{ N，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性； 数据2：102个随机整数； 数据3：103个随机整数； 数据4：104个随机整数； 数据5：105个随机整数；

输入格式: 输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。 输出格式: 在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。 输入样例: 6 -2 11 -4 13 -5 -2 输出样例: 20

这个四种方法，二分法我是照着伪代码直接复制了，数组传地址进去就OK的😂

然后是四种方法的运行截图对比

01-复杂度2 Maximum Subsequence Sum

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification: Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤). The second line contains K numbers, separated by a space.

Output Specification: For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input: 10 -10 1 2 3 4 -5 -23 3 7 -21

Sample Output: 10 1 4

自己C语言写的 感觉没有很简洁，主要是第一次没有审题… 题目里要求，如果全部为负数，输出首尾，和为0，我一开始苦恼了很久… 为啥我的负数输出是错的 看了别人的才发现哦…霍没审题

看到过用C++ vector写的很简洁的方式

01-复杂度3 二分查找

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、 <进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

emmm 我又掉进自己自己挖的坑了，我以为要用迭代来做… 然后发现这个List指向地址，因为迭代过程中有新List所以新List地址未变导致迭代失败（主要是传不了left,right啥的） 后面看提示说讨论区，一看 大家伪代码里咋都带while呢，还有就是！元素从1开始存储啊！！！ 从0开始的我… 怎么试怎么不对 顺带给大家这个：【好调试 但是之前的那位仁兄写的是i=0开始存储】

解答：

也就是如果比中间的大，尾端直接到mid前一个数，这时候你可能疑惑如果是第二个数（总数为奇数）怎么办，程序上 第一次是end=2,begin=1,mid=1了，下一次发现比mid=1的大，所以begin=2,end=2,mid=2那么这时候检查第二个数， 也就是说如果是 1 2 4 5 6，你输出的是查找2， 那么这个程序是检查完4，直接到mid=1(此时begin=1,end=1)，对比1<2然后mid再回到2这时候输出；如果你输入的是3，那么mid回2的时候不符合，end=1<begin循环结束 感觉这个难点不在于二分法了，而是在于审题和理清楚begin,end直接的变化

如果将链式存储中FindKth的函数实现（如下）做个修改：把函数最后的if语句判断条件改为判断p是否为NULL，即：

或者说直接简化为：return p; 对于这样的修改，程序还正确吗？为什么？

贴这个的原因主要是一开始，我觉得 哎 挺对的呀。😂 后面发现同学回答的：因为你要考虑，如果输入的K不合理不合法 比如我输入个 K =-1 第-1个数，应该要返回空，但是改了之后的是返回的p也就是第一个链表

1. 在矩阵的多重链表表示中，第i行的head和第i列的head实际上是同一个结点 对 理由：在矩阵的多重链表表示中，每行、每列都需要有个头指针来指示相应链表的头一个元素结点。每个head结点有down、right和next三个指针，第 i 个head结点用它的right把第i行的结点串起来，同时用它的down指针把第i列串起来，而通过next把每行（每列）的head结点串起来。所以，第i行的head和第i列的head实际上是同一个结点，图中只是为了方便理解和图的简洁把同一个结点画在两处。

2. 下列函数试图求链式存储的线性表的表长，是否正确？

因为这里p++ 不是数组，地址不是连续的指向。 字面上，p++指p=p+1, 跟 p=p->next显然不一样。 说一下应用场景上的区别： 数组的每个元素在内存里是挨在一起的，p指向一个元素，p++就是下一个元素，相当于一排人站一起，p++就指向旁边的下一个人。 链表是不同的结点通过指针，逻辑上连在一起。两个相连的结点在内存里不一定是连续。相当于你口袋里放着下一个人的联系方式，那个人可能在天涯海角。p=p->next, 就是p指向口袋里联系方式的那个人，而不是旁边那个人（p++).

参考：讨论区老师回答了 第一个 head同一结点 讨论区第二个 p++和p->next区别

1. 两个有序链表序列的合并 这是一道C语言函数填空题，训练最基本的链表操作。如果会用C编程的话，一定要做；

2. 一元多项式的乘法与加法运算 在“小白专场”里，我们会详细讨论C语言实现的方法。对于不会C语言而不能做第1题的同学，本题一定要做；

3. Reversing linked List 根据某大公司笔试题改编的2014年春季PAT真题，不难，可以尝试；

4. Pop Sequence 是2013年PAT春季考试真题，考察队堆栈的基本概念的掌握，应可以一试。

02-线性结构1 两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

这一题非常有意思，主要是一开始我对链表的地址指向不明确，我以为是整体包括head一起的地址，后面才知道相等是地址与地址之间的不变，head算作一个数；【可能是C语言基础不扎实，对于链表这种地址的Next指针有点迷迷的 不知道我调试出来的解释方法能不能听懂】

自问：线性链表为什么相等之后 Next自动指向下一个？ 自答：

是这样的，第二行我们已经初始化了pL的head，然后L与pL绑定好了 此时 如果我们输入pL->Next=L2，我们可以看到L head后整个都是L2的。(L与pL的head一致，Next也一致，所以pL掌握着L的Next) 因为是地址指向 那么这样我们在替代的时候pL->Next=L2;后 pL=pL->Next;就是将L的Next再往后移了一个也就是整个L 而这里当pL=pL->Next;的时候为什么L没有变呢？因为pL掌握的是L的Next地址，pL=pL->Next的时候 Next地址并没有直接发生改变

可以采取断点调试看一下整个list的替代关系 第一幅图是运行 可以看到L与pL绑定了 地址一致 第二幅是：第78行运行后，L与pL的地址一致 但是第三幅图，这里，我们可以看到运行后，L与pL彻底断连了，没有联系了 地址不一样了【这里是与第二幅图不一定的赋值程序了】 感兴趣的可以复制代码到vscode调试起来试一下不同的赋值，不同的顺序会对L产生的变化，整个程序逻辑上很简单对比大小，主要是链表的操作可能会引起一直不成功的现象。 比如最后L1,L2需要NULL也不是（如下）。所以对地址的操作才是不设限的

02-线性结构2 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式: 输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式: 输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出

这个不同于02-线性结构1的是，和一些坑：

1. header 空的没有了，从一开始就是有coef和expon值的…
2. MOOC小白专场里其实把程序逻辑及思路基本理清了，但是留了个小bug也就是coef==0的时候其实是不需要attach的所以if一下就好了

这里面我留了个问题，但是实践了一下，如果去掉是会导致死机的… 具体死在哪里也不太知道… 代码：

02-线性结构3 Reversing linked List

妈耶… 这个也太难顶了… 总共耗时了我大概三小时… 断续的，而且我知道我的复杂度肯定没办法完成最大的那个【都开始for-for了】… 我真的尽力了，一共有150多行… 情况也总是在分，虽然很长，但是还是记录一下自己的愚蠢：主要是我觉得我没有get数据结构的优美精髓… 所以我会回来在后面补上我的愚蠢记录，这次学习打开做之前绝对不看别人的代码！所以很多时候都是很蠢的 Hhhh 毕竟我真的很喜欢暴力解决问题 另外温馨提示：可以按照往补0的方式补全五位，但是对于-1就变成-00001了哦，需要另开if，建议还是直接翻后面的参考的简洁高效的代码 ->这里是参考链接：C++版本

C++超简洁版本：markconca的博客 思路

在这里面用到了C++本身有的一个reverse函数 C++ reverse官方介绍 和sort用法基本相近，最常用两个参数时，第一个为起点地址，第二个为操作的数目。 eg1：reverse（a,a+10）; 类似于sort。 eg2：reverse (&a[3],&a[3+5]);为从下标三开始的五个数，进行反转。【是所有的3-8之间全部翻转】 0 1 2 3 4 5 6 7 8 9 - > 9 8 7 6 5 4 3 2 1 0 添加了一些我的注解，整体来说就是 妙啊！【其实主要是reverse都由函数完成了】

02-线性结构4 Pop Sequence

客观世界中许多事物存在层次关系，原因：高效

查找 searching：根据某个给定关键字K 从集合R中找出关键字与K相同的纪录

• 静态：集合固定
• 动态：集合动态变化，可能会发生插入和删除

顺序查找：从下标最大处一直往前找

二分查找

二叉树遍历的核心问题：二维结构的线性化

• 从结点访问其左、右 儿子结点
• 访问左儿子后，右儿子怎么办？
  • 需要一个存储结构来保存暂时不访问的节点
  • 存储结构：堆栈、队列

1. 有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？

2. 一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是： 首先是要注意到假定每个链以及表示节点的数据域都是一个单位空间不然容易陷入死胡同 百度参考

3. 有一颗二叉树，其两个儿子的结点个数为15个，一个儿子的结点个数为32个，问该二叉树的叶结点个数是多少？ 这里的两个儿子的结点个数为15是指 节点处有2个儿子的个数，也就是的值，而叶结点也就是下面没儿子了

树的集合称为森林

是否也可以使用“儿子-兄弟”表示法存储森林？如何实现？

在这里我们可以看到一颗树的表示方式，在根节点的Next Sibling是NULL所以可以把一颗颗树通过这个点连起来成为森林：

第一个方法：（增加虚拟节点）

需要增加一个虚拟的根节点。森林中的所有树的根节点都是该节点的孩子节点，然后再使用长子兄弟表示法。

第二个方法：（利用根节点的兄弟指针） 可以，根节点的兄弟指针域用作连接森林中不同树根节点的指针，森林入口就是最左侧树的根节点

讨论3.3 m叉树中各类结点数之间的关系

在二叉树中，我们知道叶结点总数与有两个儿子的结点总数之间的关系是： 那么类似关系是否可以推广到m叉树中？也就是，如果在m叉树中，叶结点总数是，有一个儿子的结点总数是，有2个儿子的结点总数是，有3个儿子的结点总数是，…。那么，之间存在什么关系?

首先和二叉树一样的是：全部结点总数想加-1 = 所有的边

化简后得：

1. 如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？

2. 设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1

1. 树的同构 小白专场会做详细讲解，基本要求，一定要做；
2. List Leaves 训练建树和遍历基本功，一定要做；
3. Tree Traversals Again 是2014年秋季PAT甲级考试真题，稍微要动下脑筋，想通了其实程序很基础，建议尝试。

03-树1 树的同构

03-树2 List Leaves

这里用的是书上说的层序遍历法，用的是队列来进行

03-树3 Tree Traversals Again

首先是中序遍历的建树，然后后序遍历输出

若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0

然后可以知道高度5至少需要20个，然后到高度6至少需要33个，所以21个节点数，高度至多为5,

1. 是否同一棵二叉搜索树 小白专场将详细介绍C语言实现方法，属于基本训练，一定要做；

2. Root of AVL Tree 2013年浙江大学计算机学院免试研究生上机考试真题，是关于AVL树的基本训练，一定要做；

3. Complete Binary Search Tree 2013年秋季PAT甲级真题，略有难度，量力而行。第7周将给出讲解。

4. 二叉搜索树的操作集 用C语言的同学，可以在这里把老师讲过的各种操作都试用一下。

04-树4 是否同一棵二叉搜索树

！！找了差不多半小时的问题… 被这篇博文点醒

04-树5 Root of AVL Tree

04-树6 Complete Binary Search Tree

首先 这题我是间断了，间断的意思是：我中途断了3个月的学习，后面又拾起来的，然后这题我绞尽脑汁也没有能拿到满分（主要是快写了一天了 左右旋全完忘了 全靠trick来的）

其中层序输出因为用的不是C++（要是C++的话 vector就非常好用 emmm）二叉树的层序输出借鉴了：https://blog.csdn.net/verhappy/article/details/8859680

最后这是自己的代码：之所以说是trick是首先我的num就没对… 但是样例对了，我就真的… 有点改不下去了；其次我基本大感觉构思完了写完就开始调试，遇到什么问题加入if hhhh 我感觉我这样不太行

这是单独看到图中章节，有讲这道题，发现！卧槽 这是我想复杂了啊，用链表去表示一个完全二叉搜索树得不偿失啊，建议想要完整理解思路 可以跳转第七讲 图（中）的视频——树之习题选讲

emmm 我… 我写完了 然后发现 我之前写的是真的麻烦啊！主要是得知道完全二叉树层数的一系列关系是很重要的

04-树6 二叉搜索树的操作集

主要是和不 和 ，此处感谢CJT同学的回复

首先提出问题的原因是我看到课程样例对于typedef都是第一种模式，也就是

然后我就通过万能的必应搜了一下C/C++语法知识：typedef struct 用法详解_Shirven-CSDN博客

然后就是更疑惑了 为啥呢？带*和不带都可以呢，然后CJT同学上场：一种可以直接设变量，一种可以用指针 变量的话赋值不能直接将整个结构体赋值… 然后我就觉得 那为啥要前者呢直接不用不是更好吗 大家都走指针 走地址 [因为前者可以相对赋值，比如你弄个局部变量，你就可以把这个变量拿出来，**单独**对成员变量赋值，然后单独去将它拿出来]

然后如果用前者的话使用方式应该是 后者的话是

然后就设计到关于和的区别了

截图于C++中::和:， .和->的作用和区别? - 知乎 (zhihu.com)

关于结构体：我看C++ Primer书上P74写了 C++中允许在申明结构变量时省略关键字struct 所以使用方式也就不用了

优先队列的完全二叉树去表示 综合来看更好效率的删除 插入 查找操作

堆的两个特性:

• 结构性：用数组表示的完全二叉树

• 有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）

  “最大堆” 也称 “大顶堆”：最大值

  ”最小堆“ 也称 “小顶堆”：最小值

1. 堆中的路径 将在“小白专场”中介绍C语言的实现方法，是建立最小堆的基本操作训练，一定要做；
2. File Transfer 关于并查集，2005、2007年浙江大学计算机学院免试研究生上机考试题即由此题改编而来。“小白专场”中介绍了原始并查集算法的优化，听完课以后自己尝试一下；
3. Huffman Codes 考察对Huffman编码的理解，程序可能略繁，量力而为。

05-树7 堆中的路径

05-树8 File Transfer

这一题在小白专场里讲的很仔细了，主要是拿数组和原先设的点合理利用，比如数组的下标是所输入数字本身，然后数组里的数据是这个数字指向的 （我感觉这样的"优秀"操作似乎似曾相识 在 02-线性结构3 Reversing linked List）

一开始看完小白专场后，觉得 势在必得 肯定能行，然而翻车现场：

1. 使用Find的时候 忘记注意，输入的是数组下标 需要比原数字-1的！
2. 输入数字的范围是 然而一开始我把数组的 设为了1000 emmm

以下为运行通过的代码：

05-树9 Huffman Codes

emmm 基本从后面的输入到构造Huffman Tree后再到求WPL都可以，就是前半段输入数组的过程 构造Huffman和求WPL不太行，虽然大概知道思路，但是感觉好多东西又要排序（小的在前）然后又要删除合并，没有想到很好的求WPL的方式所以就在这个部分求助了一下百度，C++果然是香啊… 羡慕竟然有这种好东西 emmm vector我很久之前就知道了他是个好东西 但是为了意义上的锻炼 不到万不得已 一般都不会用C++ 对基础的数据结构来看总有种作弊的感觉 hhh。(我是认真的… 我确实一直没怎么研究过C++的库到底能干多少东西)

这道题从开写 构思各个部分实现什么 再到求助 再到写完 又是一个三小时 emmm 啥时候才能搞快点噢

这里曾经找过一个问题，当时函数就给加了 导致一直上传的时候片段错误（但实际在自己电脑运行的时候没有报错… 我也不知道为啥，当然结尾加了后才是完整的，迭代迭的自己给忘了

我重新听课的时候发现我根本没考虑… 放入的是叶子节点的问题（就是如果放在根节点 我也继续放了… 看来是WPL那个案例没有完全等 所以过了？），也就是说我可能放在根节点上了，我也不知道为啥我的测试案例过了 emmm

也就是说本身Huffman Codes应该满足：

1. 最优编码 —— 总长度（WPL）最小
2. 无歧义编码 —— 前缀码：数据仅存在于叶子结点
3. 没有度为1的节点 —— 满足1、2则必然有3

内心OS: ！终于 我进度过半了 虽然我觉得我刷完可能秋招已经结束了 😵 好了 进入正题

这个部分的图，我似乎好像真的有那么点熟悉(主要图形学和python那个networkx库 6010课 等一系列课程中都多多少少介绍过这个概念)，所以笔记可能显得非常少

程序中表示图的方式：邻接矩阵 ​个顶点从0到 ​ 编号

关于用链表表示图并且能方便地得到有向图的出、入度，你有什么其他的办法吗？ 在评论区看到几个挺好的：

1. 用树表示更好，顶点做根，左枝是出度，右枝是入度。

2. 修改Node的结构，多创建一个域，1表示入，0表示出，这样就能知道该节点到底是入还是出

3. 修改链表的整体结构，但是这个我觉得并没有那么容易，还没想出来。但是十字链表的确可以把邻接表和逆邻接表串起来

然后十字链表新概念，查一下后

1. 列出连通集 非常基础的训练，一定要做；
2. Saving James Bond - Easy Version 可怜的007在等着你拯救，你……看着办哈；
3. 六度空间 在听完课以后，这题的思路应该比较清晰了，不过实现起来还是颇有码量的，有时间就尝试一下。

06-图1 列出连通集

写完了 最近好多活 杂七杂八 这个在多次脑子切换间写出来的 一开始 第1个是单独点，最大N 这个案例一直过不了，后面搜也没搜出什么，但是搜到了 有人用C拿数组模拟队列的 感觉很聪明的做法哎，当然 我比较菜 所以我用了C++。对了前面提到的那个案例，后面找到原因了是因为

1. 建邻接表的时候没有排序，这次在里面判断了每次的排序
2. BFS的逻辑在一开始跳过了头的邻接点下标

然后怎么发现的呢？一步步调试 emmm 然后自己输入了一个这个的 案例：

06-图2 Saving James Bond - Easy Version

这个真是绝了，一开始一直过不了**最小跳，人工乱序**，然后我搜了一圈没啥感觉，然后仔细检查发现

1. 自己最后一个判断的等于号少了(我一开始都写成了小于号，没注意到等于号 后面再次读题的时候发现的)
2. 第二个是内的for循环需要i从0-N，一开始写成了

emmmm 我没找两天 就找了10分钟hhh 我搜的时候发现有个仁兄找了两天 hhhh 同道中人啊

06-图3 六度空间

这个题起码加起来的debug时间估计达到3小时了，主要是一开始自己写的 死活在深入算level的时候多算一层（然后这个debug和大规模修改函数基本上达到了三次还是没能改出来），导致输出的时候有错误。后面受不了了 想不出什么好办法就直接照着课上的伪代码 一句句的去实现，然而我还在看为什么输出还是错误 郁闷了半小时，最终发现%2f不是输出小数点后两位，得加个%0.2f 我真是… 当时 emmm 啊

大致原因：

1. 根本上来讲，可以看出 伪代码的实现是一次性看完所有BFS 而我的伪的 也就是看一次 OK 判断一次tail
2. 输出小数点后两位记错了
3. 在输入第一个点时，一开始的做法是先进行BFS 而不是像伪代码那里直接将第一个点加入队列统一处理
4. 前面reset visit矩阵和reset queue队列都忘了 emmm 问就是debug d出来的 发现哦吼 后面咋都是0,100%这种奇怪的数字