数据结构 学生摸底课件

1、数据结构陈荣可信软件与移动计算实验室1学时数：72（50讲课+20上机+2考试）学分：4教材：数据结构（C语言版）严蔚敏 吴伟民 编著 清华大学出版社参考书：数据结构题集 (C语言版) 严蔚敏、吴伟民著 数据结构学习指导曹桂琴等编著 大连理工大学出版社 数据结构题集(C语言篇)习题与解析（修订版）李春葆编著 清华大学出版社第一次上机实习：第4周，周一7-8节 ，扬帆楼201室TSMC2009, Rong Chen, All rights reserved.内容安排章内容学时章内容学时1绪论27图62线性表88动态存储管理略3栈和队列69查找64串610内部排序65数组和广义表411外部排序略6

2、树和二叉树612文件略TSMC2009, Rong Chen, All rights reserved.复习1 int amount_to(int score) 2 int i=sum=0;3 for (i=0; i53; i+) 4 sum = sum + scorei;5 printf(“sum=%dn, sum);6 return sum; 53是一个有问题的数，为什么？怎么改？TSMC2009, Rong Chen, All rights reserved.调查解释以下语句的作用1 #define MAX 2552 typedef unsigned char SStringMAX;3

3、#define EVEN(a) (a%2)=0写出程序语句4 从键盘输入整型变量max的值5 用typedef定义一个数据元素ElemType，它由SString类型的字符串指针str和一个整型的表示长度的len组成;6用typedef定义一个数据元素Node，它由ElemType类型的指针elem和一个Node型的指针next组成;TSMC2009, Rong Chen, All rights reserved.调查解释以下语句的作用7 SString str=(SString )malloc(MAX*sizeof(char);8 for (int i=0; iMAX; i+) stri=a

4、;stri=0；改正错误，写出正确语句9 ElemType e=malloc(sizeof(ElemType);10 *(&e.str0)=b;举例说明什么是字符串？字符串都有哪些操作？TSMC2009, Rong Chen, All rights reserved.上机实习注意事项减少调试程序的时间上机前：准备例子，想象算法流程，理解设计；在理解设计的基础上认真编写代码，避免语句错；“滚雪球”式地编写更多代码（注意备份程序）；程序运行有错时，不要“逐行比对代码” ，使用准备好的例子排错TSMC2009, Rong Chen, All rights reserved.实验报告开头应给出题目名称

5、、班级、姓名、学号和完成日期，具体内容包括：一、需求分析 陈述程序设计的任务，明确规定：（1）输入和输出的形式，举例说明；（2）程序功能；（3）测试用例设计。二、概要设计 说明主程序流程，以及在函数级上说明各程序的调用关系三、详细设计 详细的数据类型定义；主程序和其他模块的伪代码算法四、调试分析 包括：（1）编辑代码、编译运行所遇到的问题及其解决办法；（2）对返工的设计与实现进行讨论和分析；（3）算法的时空分析；（4）心得体会。五、用户使用说明 主屏幕截图告诉如何使用所编写的程序六、测试结果 根据设计的测试用例，列出详细的测试结果，包括输入、输出和是否通过。七、附录 源程序清单TSMC2009

6、, Rong Chen, All rights reserved.Ch2 课内习题严题集2.6a.在P结点后插入S结点b.在P结点前插入S结点c.在表首插入S结点d.在表尾插入S结点严题集2.7a.删除P结点的直接后继c.删除P结点d.删除尾元结点ab/xLP/zSTSMC2009, Rong Chen, All rights reserved.Ch2 课堂测验在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。线性表顺序存储的缺点是： 。线性表中结点的集合是 的，结点间的关系是 的。向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 个元素。 表中一半表长

7、和该元素在表中的位置插入和删除时需要移动大量元素有限一对一n-iTSMC2009, Rong Chen, All rights reserved.Ch2 课堂测验5、【严题集2.7 】已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点。要求必须使用free(Q)释放被删结点的内存。试写出合适的语句序列。a.删除P结点的直接后继结点的语句序列是 A 。b.删除P结点的直接前驱结点的语句序列是 B 。c.删除P结点的语句序列是 C 。d.删除首元结点的语句序列是 D 。6、编写程序：写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。 TSMC2009, Rong Ch

8、en, All rights reserved.Ch3 课内习题【严题集3.1】若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：（2）如果进站的车厢序列为123456，则能够得到435612和135426的出站序列？说明为什么不能得到或者如何得到。 【第3章自测题四、2】设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 TSMC2009, Rong Chen, All rights reserved.Ch3 课堂提问栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和

9、删除运算的一端称为 。向栈中压入元素的操作是先 ，后 。 写出5种常见的栈运算。栈顶栈底移动栈顶指针存入元素TSMC2009, Rong Chen, All rights reserved.Ch3 课堂提问队列是一种特殊的线性表，允许插入运算的一端称为 ；允许删除运算的一端称为 。向队中增加元素的操作是先 ，条件满足时再 ， 。 写出5种常见的队列运算。队尾队头移动队尾指针存入元素判断队列是否满TSMC2009, Rong Chen, All rights reserved.Ch3 课堂测验设计表格对比循环队列和栈：判定它们为空、为满的语句？求元素个数的语句？两者都要再分顺序存储和链式存储两种

10、情况对比。 请写出递归算法C(20)执行过程中的所有输出。 1 int C(int m) 2 int n;3 if (m ve: (vs,ve) C其中vs是起点序号，ve终点序号，C表示路径代价。按照这种格式，书中P188图7.34的输出结果是：0-1: () 327670-2: (0,2) 100-3: (0,4,3) 50TSMC2009, Rong Chen, All rights reserved.Ch7 课堂提问关键路径是由权值最大的边构成的。在AOE网中，减小任一关键活动上的权值后，整个工期也就相应减小。在AOE网中工程工期为关键活动上的权值之和。在关键路径上的活动都是关键活动，

11、而关键活动也必在关键路径上。关键活动不按期完成就会影响整个工程的完成时间。任何一个关键活动提前完成，将使整个工程提前完成。所有关键活动若提前完成，则整个工程将提前完成。存在环路的有向图可以进行拓扑排序。AOE网络中不存在环路。TSMC2009, Rong Chen, All rights reserved.Ch9 课堂提问线性表（顺序表）可采取的三种查找方法是什么？它们对表中元素的要求是什么？对于n个元素的线性表，在等概率情况下查找成功的平均查找长度各是什么？折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失

12、败。 链表对于数据元素的插入和删除不需要移动 A ，只需要移动 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 只适合于按键值顺序存储的结构，它的效率 E ；而 D 是一种对顺序和链式存储结构均适用的方法。 TSMC2009, Rong Chen, All rights reserved.Ch9 课堂提问在二叉排序树中，每个结点的键值要满足： A ， B 遍历一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，它在结构上的特点是 C 。 当 D 时，折半查找与二叉排序树查找的时间性能相同。平衡二叉

13、树是一种最佳的二叉排序树，它要求 E 。 已知键值序列为46,57,84,32,73,36,15,48, 90,20，请（1）按键值排列顺序构造一棵二叉排序数；（2）在等概率的情况下，该树查找成功的平均查找长度；（3）对于这10个键值，构造一棵最佳二叉排序树和一颗最坏二叉排序树；（4）在最佳二叉排序树上删除结点46后，画出调整后的二叉排序树。TSMC2009, Rong Chen, All rights reserved.Ch9 课堂测验画出对20个元素的顺序表(1,2,3,20)进行折半查找的判定树，并指出在等概率情况下，查找成功的平均查找长度以及失败时所需最多与关键字值比较的次数。在各种查

14、找方法中，平均查找长度与结点个数n无关的查找方法是 A ,基本思想是由 B 决定数据的存储地址。 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为010，表长为11的散列表，22，41，53，08，46，30，01，31，66。 TSMC2009, Rong Chen, All rights reserved.DoIt选取散列函数H(key)=key%13，用线性探测法处理冲突。对下列关键码序列构造一个散列地址空间为015，表长为16的散列表，19，14，23，01，68，20，84，27，55，11，10，79。 196，141，2

15、310，011，683，207，846，271，553，1111，1010，791TSMC2009, Rong Chen, All rights reserved.物理存储、逻辑结构及运算顺序的链式的散列的索引的B树31顺序结构顺序表数据元素顺序存放，使用下标访问特点P22顺序表SqList, P46栈SqStack, P64队SqQueue, P75字符串HString, P216查找SSTable, P264排序SqList/P282堆排序(完全二叉树)HeapType数组（一维/二维）P73字符串SString, P126二叉树/完全二叉树SqBiTree, P163图的邻接表表示法中的

16、顶点表AdjList, P225索引顺序表, P283归并排序RcdType ST,P161图的数组表示法/邻接矩阵MGraph静态链表P32 SLinkList, P135树的双亲表示法PTree, P147赫夫曼树*HuffmanTree, P269表插入排序SLinkListType, P286链式基数排序基本运算：查找、插入、删除注意： P259哈希表HashTable的物理结构与顺序表类似，但数据元素的访问采用哈希函数，所以归入散列结构。TSMC2009, Rong Chen, All rights reserved.链式结构单链表特点P28单链表*LinkList，P47链栈，P6

17、1链队，P48字符串LString，广义表P109表结点和原子结点构成的*GList，树/二叉树P127二叉树*BiTree，P133线索二叉树*BiThrTree，P136树的孩子-兄弟表示法*CSTree，P228二叉排序树*BiTree，P236平衡二叉树*BSTree，P240 B树*BTree图P163邻接表(=一维数组+多个单链表)ALGraph基本运算：查找、插入、删除TSMC2009, Rong Chen, All rights reserved.散列结构哈希表哈希表建立了记录关键字和存储位置之间的对应关系，查找非常快。而顺序表上没有这种关系，所以查找记录时要和关键字进行一列的

18、比较。哈希函数H(key)的构造方法除留余数、 折叠法、平方取中、直接定址、数字分析、随机法冲突解决开放定址法、链地址法、再哈希法、公共溢出区评价：平均查找长度ASLTSMC2009, Rong Chen, All rights reserved.相同的逻辑结构，不同的运算栈和队列不同特点：FILO vs. FIFO初始化，压栈/入队，弹栈/出队，空，满串的模式匹配next和nextval数组计算任意数据元素的存储位置广义表取头、取尾、表长、表深度顺序表查找：顺序查找、折半查找、分块查找（内部）排序直接插入排序、折半插入排序、表插入排序、希尔排序起泡排序、快速排序锦标赛排序/树形选择排序、堆排

19、序归并排序链式基数排序TSMC2009, Rong Chen, All rights reserved.树/二叉树二叉树5个性质P123完全二叉树1度结点的个数不超过1个；叶子结点个数n/2；最后一个非终端结点位置n/2 树和森林与二叉树的转换遍历二叉树先序遍历DLR先根遍历树/先序遍历森林树/森林中序遍历LDR后根遍历树/中序遍历森林后序遍历LRD二叉树先序遍历DLR深度优先搜索DFS图中序遍历LDR后序遍历LRD层次遍历广度优先搜索BFSTSMC2009, Rong Chen, All rights reserved.树/二叉树线索二叉树采用左右孩子链式存储，n个结点的二叉树中有n+1个空指针最优二叉树（赫夫曼树）树的带权路径长度WPL=wili如何根据给定的n个权值wi构造