数据结构A是一门计算机类课程，延续了计算机程序设计的C语言风格，旨在向学生讲授线性表、栈、队列、字符串、数组、树、图等数据结构的性质和算法，灵活应用学到的知识肉编求解如仿真系统、文件压缩、搜索、排序等实际问题。

语言：C语言、伪C代码，可以用C++的引用参数，部分时间禁用STL库等C++高级库（按照助教的说法后期甚至考试也能用？）。绝大部分问题通过C语言+引用参数即可解决。

讲授内容：数据结构和算法的有关定义（ADT、T(n)、S(n)等），线性表的数据结构定义及操作、栈和队列、串操作、数组的存储、广义表、树和二叉树、哈夫曼编码、图的存储结构、最小生成树、拓扑排序、有向带权图最短路径、搜索（查找）算法、内部排序等。

讲授方式：嘴巴、PPT

给分：包括考勤、作业、实验、期末考。比例尚未可知。

考勤：本学期课程为每次2课时，每周2次。助教一般会在两节课之间的课间（有例外）发布需要定位的签到码，限时5分钟。

作业：每周1-2次，由万老师随堂布置，内容为数据结构习题集上的算法编写，写伪代码即可。DDL1周。

实验：5次，每周有专门的线下验收时间和机房。若时间冲突可向助教说明并随堂验收。

期末考：李金龙老师出题，据说第一节课他们班上跑了一半人，这下看懂了，🐎🌶🕊🖊の。

老师风格：红太狼万寿红老师非常慈祥，上课和风细雨，下课乐于回答同学的问题，讲课有条理，语调略显平缓，秋冬季节容易打瞌睡。不知是不是由于资深美女和神秘的穿搭，我每次上课都隐隐约约觉得万老师有种小学数学老师的感觉。

助教：本学期的三名助教都是万老师的研究生，不辞劳苦，呕心沥血，4-14周每周一都要着急忙慌地赶9点钟回高新的班车，期末还要改一大堆之前没改的作业、巨量实验报告和期末卷子。

实验指南

实验综述：下列实验应该是万老师的祖传实验了，如果你有认识的学长学姐可以求帮忙。学期末需要提交一份实验报告，五个实验缝合到一个文件里面。

实验1：一元多项式计算器。要求利用带头结点的单链表表示一元多项式并完成带入求值、加减乘除、微积分等运算。

评价：这个实验主要考察单链表操作，遍历插入删除换序等等。只要链表操作熟悉基本拿下。基础功能包括存储、修改、打印、带入求值、多项式加减法等，要求全部完成；进阶功能包括定积分、不定积分、高阶导、多项式乘法、多项式带余除法等，选三个即可。进阶部分还提供了用户界面设计，虽然但是好像没几个人写。

注意事项：由于题目只涉及一元多项式，积分部分的样例不含\(x^{-1}\)项。

奇技淫巧：可以写几个函数化简多项式链表，比如将链表按照指数顺序排序、合并相同指数的结点等，会对后面的运算有帮助。

实验2：二元多项式计算器栈和队列。下有5道小题，关于栈和队列的各选一道。

1.行文本编辑器。参见书上和实验要求的描述，要完成行输入、行编辑、退格等基本操作，并写入txt文件。行操作对应到栈操作并不难，如果对文件指针比较熟悉的话基本拿下。

2.括号检验。请输入文本，利用栈来检验括号的匹配以及优先级，是实验2最简单的实验，在C语言程序设计好像就做过了。

3.迷宫路径求解。要求随机生成迷宫并输出可行路径。老师上课时会展示一个编写非常精美的程序，生成一个必有唯一路径的迷宫。注意实验的要求是要能判断无可行路径的情况的所以如果直接抄AI的可能就错了。这个实验属于栈的部分，需要用到一些DFS的知识，因此在前期没学的情况下可能会比较牢。

4.银行模拟。利用两个队列模拟顾客从银行存钱取钱的情况。办理业务排第一队，如果顾客要取钱但银行没有钱就要排第二队。兄啊如果银行穷到这种程度的话也没有开下去的必要了罢（悲）。程序需要记录每个顾客到来和离开的时间间隔，并在打烊时让所有人滚蛋并计算平均等待时间。实验要求程序能够正确处理边界情况（如很久没人来、银行没钱等），胡闹银行这一块。

5.电梯模拟。利用队列模拟电梯的指令处理，据说很牢，我没写所以我也不知道。

奇技淫巧：选括号检验和银行。银行的样例比较混乱，建议在编写的时候搞清楚生成顾客都需要什么参数，比如存钱借钱数目、到行时间、业务时间、离开时间、等待时间等。

实验3：哈夫曼树和哈夫曼压缩。第一题要求对文本进行哈夫曼压缩并计算压缩率，第二题要求对所有类型的文件进行压缩并解压，计算压缩率。

评价：牢，第一题就开始上强度，不过把哈夫曼树的逻辑搞清楚，结点弄明白还是可以做出来的。第二题需要利用二进制读写文件并写入新文件，涉及巨量的文件操作和编辑。由于某名字里很多水的程设老师没教会我文件读写，我在这道题夙兴夜寐废寝忘食身先士卒十二指肠。

奇技淫巧：第二题需要我们可以独立解压文件，要求文件中含有哈夫曼编码规则，所以在写压缩文件的时候就要设计一个文件头。下面提供一个文件头的设计：

压缩文件结构：哈夫曼编码的总数，码长、对应的编码、译码和权重，正文。

解压流程：先读取个int（）32位，得出一共几个码，再做个循环来读取编码规则，重构哈夫曼树，最后翻译正文。

要保证按你的流程编写出来的压缩文件能够按你的规则解压，剩下的就是二进制读写建议使用AI编程法能省不少事反正我让AI给我写的二进制读写玛德我真写不动都怪zsh

实验4：图。任意使用邻接表或邻接矩阵，完成图的打印、执行图的DFS、BFS并显示顺序、编写Prim、Kruskal、Dijstra算法并通过样例测试。

评价：比较麻烦。打印和遍历都比较好写，学到后期了DFS和BFS也该会了。Prim要管理顶点是否在连通分量中和与当前连通分量的最小距离，Kruskal要管理并查集（各顶点所属的连通分量编号），Dijstra要管理各顶点是否已经找到与源点的最小距离和更新最小距离。

奇技淫巧：Prim和Dijstra书上就有比较完整的算法伪代码。Kruskal管理并查集有两种手段，一种是通过Find函数递归查找连通分量编号，另一种是每次选边时更新所有顶点的连通分量。前者在时间复杂度上远远优于后者。还有验收时注意提前输入样例，样例输入会比较废时间。

实验5：哈希表。除留余数法，哈希函数直接对一个质数取余数即可。编写哈希数组和哈希链表，分别实现线性探测法和拉链法解决冲突，计算查找成功和不成功的平均查找长度。注意对于拉链法，直接查到空结点也算一次。

评价：比较简单，但验收时间会比较紧。建议提前做提前验收。

奇技淫巧：提前学哈希表，很简单，能避免后期验收排队。

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊宝宝你是一个数据结构抽象数据类型集合线性结构树形结构网状结构有序偶逻辑结构物理结构存储结构结点数据域顺序结构链式结构算法时间复杂度空间复杂度Order1OrderNOrderN平方线性表指针不带头结点单链表带头结点单链表循环单链表双向链表循环双链表顺序栈链式栈栈顶栈底先进后出LIFOInitStackDestroyStackClearStackStackEmptyStackLengthPushPopGetTop括号匹配器行文本编辑器迷宫生成器迷宫求解器前缀表达式中缀表达式后缀表达式递归栈递归函数单端队列双端队列链式队列循环队列InitQueueDestroyQueueClearQueueQueueEmptyQueueLengthEnqueueDequeueGetHead银行业务模拟电梯模拟订票系统模拟定长顺序存储字符串堆分配存储字符串块链串空串空白串子串Brute-Force算法KMP算法next数组行优先数组列优先数组矩阵的压缩存储对角矩阵三对角矩阵稀疏因子三元组顺序表十字链表广义表原子子表表头表尾树子树根节点叶节点中间节点度为1的结点度为2的结点度为114的结点二叉树三叉树四叉树误差树左子树右子树完全二叉树满二叉树先根遍历中根遍历后根遍历层序遍历线索二叉树孩子兄弟树哈夫曼树哈夫曼编码回溯法遍历树有向图无向图邻接表邻接矩阵顶点弧头弧尾完全图稀疏图稠密图回路子图强连通图强连通分量生成树DFSBFSPrimKruskalDijstraFloyd有向无环图AOVAOE拓扑排序静态查找表顺序查找折半查找平均查找长度索引查找二叉排序树平衡二叉树左单旋右单旋左右双旋B-树B+树键树哈希表哈希函数直接定址法数字分析法平方取中法折叠法除留余数法线性探测法再哈希法拉链法插入排序希尔排序冒泡排序快速排序选择排序堆排序归并排序基数排序啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

首先，十分奉上。以表达我对把我当煞笔教的万寿红老师的感谢。

万寿红老师上课有种高中老师上课的感觉，讲的很细，不跟我之前上的课的老师一样草草教完。对于ppt上的东西老师会一步步分析。虽然我个人感觉难的地方老师讲的有点乱。而且老师好像有点口音？不影响听课，就是听着很有意思。

顺便吐槽一下伪代码，我感觉伪代码成功做到了只能让写它的人看懂内涵，我每次看伪代码都得借助ai分析，不然根本看不懂课本上的伪代码在说啥。

作业上，留的不多，每周就两三个个算法题。。但是我写的不是很认真。

实验就是实现一些老师上课讲的算法，DFS，哈希表之类的。但由于ai太快了，所以本人有时候忍不住用了ai。。。现在有点后悔，感觉少学了很多东西。推荐再学的人一定要自己敲。

考试，各位在pksq应该能找到很多资料。本人就在这里推荐b站up“蓝不过海”，看他的视频有奇效。并且在这里放一本考研的参考书，个人感觉比课本和ppt讲的明白多了。

2025王道数据结构（带书签）.pdf

最后，这门课是我在科大上了一年多以来，为数不多（总数可能也就不超过5门）有用的课。希望后来的人能好好学吧。

本人卷面81，应该是够用了，从工院转出来，感觉别的地方给分和工院比真是活菩萨

刚查到卷面分，先来水一下评课。

万老师是非常好的老师，刚开学听了课感觉讲的很清楚，PPT逻辑也很清楚，很适合（期末速通）自学。不过个人感觉PPT和书上的代码对于初学者来说可读性不是很好，有时候前面的思路能理解后面的代码却一头雾水。可能是把理解部分放在了课堂吧（显然我没听）。

上课有签到点名，一般在课中，西区都能签，可以西图启动。实验内容十分复杂，作业也不少，不清楚别的班的情况。本人平时分应该满了，卷面也还行，如果46开的话应该是89，不知道能不能捞一手🥺

顺带提一嘴，最近这个Bpksq怎么每次都要发布好几次才能通过😡

出分了，被捞上91了🥰🥰🥰

学期初被李金龙老师过于激进的改革吓跑，而肖明军老师貌似不接受换班人（这个时候肖班已经有170+人了），因此误入了AI置课班，被AI人的卷度吓哭。

数据结构A这门课地位有一点点尴尬，貌似讲了不少东西，实际考察的时候考察深度又太浅，基本上是对一些基础算法的手操。个人感觉学习数据结构A并没有很好地为后续的算法基础等课程夯实一个扎实的基础。

虽然课程设计有一点问题，但是万老师的课还是非常推荐的。老师的PPT和严蔚敏《数据结构》课本内容相近，课堂上讲得特别细致，对于一些略微复杂的操作（B-树的操作等）会用PPT动画逐步展示，非常适合零基础的同学（但是班上（包括我）好像没什么人听，都在干自己的事情）。作业布置上，每周仅布置少量习题，以写伪代码为主，线上提交，大部分都比较有营养。

实验方面，本班的实验非常基础，基本上就是实现课上所提到的算法，不需要其他任何建模的能力。比如说第一次实验是链表多项式的计算，实现多项式加减乘除乘方等等操作，个人感觉没啥意思而且有点冗余。从培养学生能力的角度来看，可能学习一下隔壁肖明军老师班实验教教CMake的使用更有意义一些。

今年期末中规中矩，手操题考察了平衡树的构建、Dijkstra算法和Huffman树，伪代码题在算法上难度并不大，好像都是DFS。期末考试最大的问题是题目出得语焉不详，非常影响观感，不过和老师无关。

给分方面，比四六开还上调了一点，这真的是AI班的给分吗？老师真善良。

老师有考勤，讲的很好，给分也还行

唯一的问题就是司马课程组出期末考卷子话不讲清楚，完全不严谨，让一堆同学怒扣十几分。查卷的时候助教也很无奈，但是这和老师与助教无关，遂给10分满分。