数据结构实验题目2016解析.ppt

数据结构实验内容及要求 2016 * * 要求 独立完成 实验课前自主完成部分实验或实验的部分内容 检查：实验课内由指导教师现场检查 查看程序代码 回答指导教师提出的问题 每人提交一份打印版实验报告 双面打印，格式及内容见模板 模板中所有红色文字为提示或解释作用，请在提交报告前将所有红色文字删除 未提交实验报告者实验成绩为0 实验成绩根据现场检查的完成情况和实验报告进行综合评定 * 实验1：链表的应用 题目：求相邻k个节点数值之和最大的第一节点 输入数据（设为整型）建立单链表，并求相邻k个节点data值之和为最大的第一节点。例如输入k = 2，数据为2 6 4 7 3 #（#为结束符），建立下面链表，运行结果输出（序号3，data值4）： 程序结构： 类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L, k); main( ) { 变量说明； 调用Creatlist(L)建表；调用Adjmax(L, k)求值； 打印数据；释放链表空间； Y 继续？ N 停止 } H 2 6 4 7 3 ^ 实验2：栈的应用 题目：算术表达式求值 输入中缀算术表达式，如：5+(4-2)*3，将其转换成后缀表达式并输出：542-3*+，再对后缀表达式求值（本例结果为11）并将结果输出。 操作数支持多位数和小数； 运算符仅考虑+、-、*、/、（、）、#（#可用作结束符）； 中缀表达式从键盘输入或从文件输入。对输入的中缀表达式要进行合法性检查（表达式头尾以及运算符左右可以包含若干空格）。 程序结构： 类型说明及子函数定义； main（） { 变量说明； 输入中缀表达式，存入E[n]； 调用Mid-post(E, B)； 调用Postcount(B)； 打印表达式结果； Y 继续？ N 停止 } 4 实验3：队列的应用 题目：链式队列的基本操作 将从键盘输入的一系列字符存储到链式队列中，当输入的字符为’0’时，执行出队操作并将出队元素打印到屏幕上；当输入的字符为’@’时，队列中剩余所有元素依次出队并打印到屏幕上；当输入其他字符时，字符入队。 程序结构：类型说明； Clearqueue(q)、Emptyqueue(q)、Enqueue(q)、Dequeue(q)； main（） { 变量说明； ? 建空队列； ? ? 是 否 } X=？ 键盘输入字符? X 停止 X≠‘@’and X ≠‘0’ X入队 X =‘@’ 打印队中各元素 X =‘0’ 出队 继续 5 实验4：二叉树的应用 题目：二叉排序树的构建与遍历 输入一个英文句子，按照字典顺序构造一棵二叉排序树； 例如：英文句子：“everyone round you can hear you when you speak.”，依次读入句中各单词，构造其二叉排序树如下： 采用非递归算法对此二叉排序树进行中序遍历，将遍历序列输出到屏幕： LDR： can everyone hear round speak when you everyone can round speak hear you when 6 实验5：图的应用 题目：图的存储结构及拓扑排序 从键盘或文件读入有向图的顶点信息和弧信息（输入格式自拟）； 建立有向图的十字链表存储结构； 利用拓扑排序方法判断该图是否为有向无环图。 程序结构： 类型说明及子函数定义； main（） { 变量说明；