数据结构实验指导书(2012.9)

1 1 21 2 实验报告实验报告 文档文档 书写规范书写规范 实验报告 文档 应包括以下 7 个方面的内容 1 1 问题分析 问题分析 根据对实验任务的理解 以无歧义的陈述说明程序设计的任务 强调的是程序要做什 么 指出解决问题的关键步骤 如果问题复杂 应将问题分解成若干个子问题 明确规定 1 本实验的任务以及程序所能达到的功能 2 完成该任务需要解决的关键问题 3 程序设计中输入数据的类型 形式及输入值的范围 4 设置测试数据 包括正确的输入及预计的输出结果和含有错误的输入及预计输出 结果 2 2 概要设计 概要设计 针对问题分析中提出的关键问题进行分析 可以列举实例进行分析 从而总结出关键 问题的解决思路 给出解决关键问题的算法思想 说明本程序中用到的所有程序模块 各程序模块日之间的层次 调用 关系以及主程序 的流程 各程序模块使用中文名称即可 3 3 详细设计 详细设计 根据概要设计中提出的关键问题的解决思路 设计本程序中用到的所有数据结构 要 求做到 1 在所设计的数据结构下分析关键问题的具体解决方案和步骤 给出相应的用类 C 语言描述的算法 2 分析设计程序中需要用到的变量 全局变量及其数据类型定义 3 设计程序中的所有模块 自定义函数和主函数 通过分析定义函数的类型 描 述函数参数 说明函数名称 并给出相应类 C 语言描述的算法 类 C 语言算法达到的详细 程度建议为 按照该算法可以直接写出高级程序设计语言程序 4 画出函数和过程的调用关系图 4 4 调试分析 调试分析 程序调试主要实现程序的语法错误检查和功能性错误检查 调试最好分模块进行 自 底向上 即先调试低层过程或函数 在实验报告中应有如下内容 1 记录调试过程中遇到的问题及其解决方案 如果由此反映出程序设计的不足 应 对设计与实现进行回顾讨论和分析 并修正 2 算法的时空分析 包括基本操作和其他算法的时间复杂度和空间复杂度的分析 和 改进设想 3 经验和体会等 5 5 测试结果 测试结果 将程序的测试结果截图 展示出你的测试过程和结果 包括输入和输出 这里的测试 数据应该完整和严格 最好多于问题分析中所列 6 6 附录 附录 带注释的源程序 如果提交源程序电子档 可以只列出程序文件名的清单 值得注意的是 实验报告文档的前三部分要在程序开发的过程中逐渐充实形成 而不 是最后补写 2 实验一实验一 算法设计 算法设计 1 用指向指针的指针的方法对 n 个整数排序并输出 要求将排序单独写成一个函数 n 和各整数在主函数中输入 最后在主函数中输出 2 编程求出 10000 以内的所有符合如下条件的数 其高位数字小于低位数字 如 25 349 2468 等 但 32 845 不符合条件 3 编程求出数列的所有升或降的最大子序列 如数列 1 20 30 12 3 5 7 4 6 100 11 8 的所有升或降的最大子序列如下 1 20 30 30 12 3 3 5 7 7 4 4 6 100 100 11 8 实验二实验二 顺序表实验顺序表实验 实验任务实验任务 1 程序验证 程序验证 1 建立含有若干个元素的顺序表 并实现顺序表的插入 删除 查找等操作 2 阅读下列程序 指出算法的功能 写出其运行结果 并通过运行来验证 include malloc h define maxlen 50 typedef struct int data maxlen int last Sequenlist Sequenlist ABC Sequenlist A Sequenlist B int i j Sequenlist C C malloc sizeof Sequenlist C last 1 for i 0 ilast i for j 0 jlast j if A data i B data j C last C data C last A data i break return C Sequenlist SqLset Sequenlist L int i L malloc sizeof Sequenlist L last 1 3 scanf d 输入表长 if i 0 for L last 0 L last last scanf d L last return L main Sequenlist A B C int i A SqLset B SqLset C ABC A B for i 0 ilast i printf 4d C data i 3 下面算法的预定功能是实现顺序表的倒置 试检查其中是否有错 若有错 指出错误 所在 并修改之 然后通过运行来验证 include malloc h define maxlen 50 typedef struct int data maxlen int last Sequenlist Sequenlist SqLset Sequenlist L int i L malloc sizeof Sequenlist L last 1 scanf d 输入表长 if i 0 for L last 0 L last last scanf d return L Sequenlist reverse Sequenlist L int i j x for i 0 j L last i 1 idata i L data i L data j L data j x return L main Sequenlist A int i A SqLset 4 for i 0 ilast i printf 4d A data i printf n A Sequenlist for i 0 ilast i printf 4d A data i printf n 2 算法填空 算法填空 请在下面算法的空格处填入适当内容 以使算法能求出顺序表中的最大和最小值 并通 过运行来验证 include malloc h define maxlen 50 typedef struct int data maxlen int last Sequenlist Sequenlist SqLset Sequenlist L int i L malloc sizeof Sequenlist L last 1 scanf d 输入表长 if i 0 for L last 0 L last last scanf d return L void maxmin Sequenlist L int min max i if max min L data 0 for i 1 i i if max data i max L data i if min L data i min L data i printf max d min d n max min main Sequenlist A A SqLset maxmin A 3 算法设计 算法设计 1 设计算法实现删除顺序表中多余重复元素 如 对于顺序表 1 2 3 1 3 4 3 5 删除第四个元素 1 及第五 第七个元素 3 5 2 设计算法 实现在一个递增有序的顺序表的适当位置插入元素 x 使得该顺序表仍然 递增有序 分析算法的时间复杂度 实验三实验三 链表实验链表实验 实验任务实验任务 1 程序验证 程序验证 建立含有若干个元素的链表 并实现链表的插入 删除 查找等操作 2 算法填空 算法填空 1 下面建立以 head 为头指针的单链表 完善该算法 并输出表中元素 已知单链表节点类型为 typedef struct node int data struct node next LinkList LinkList create LinkList p q int k q head scanf d InitStack while num int k num 16 Push 8 while StackEmpty if x 10 printf d x else switch case 10 printf A break case 11 printf B break case 12 printf C break case 13 printf D break case 14 printf E break case 15 printf F break Pop printf n 3 算法设计 算法设计 1 编写算法 利用栈判断所给字符串是否具有中心对称关系 要求用尽可能少的时间完 成判断 提示 字符串的中心对称是如 xyzyx 和 abcddcba 的形式 字符串可以考虑顺序存储或链接存储 判断该字符串是否中心对称 可以将一半字符先入栈 2 设计算法判断一个算术表达式的圆括号是否正确配对 提示 对表达式进行扫描 凡遇 就入栈 遇 就将栈顶元素 出栈 表 达式被扫描完毕 栈应为空 3 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出 实验五实验五 队列实验队列实验 实验任务实验任务 1 程序验证 程序验证 1 分别建立含有若干个元素的循环队列和链队列 并分别实现循环队列和链队列的入队 和出队操作 2 写出下列程序段的输出结果 并通过运行来验证 void print SeqQueue q char x y 9 x e y c InitQueue q Add q h Add q r Add q y x GetHead q Delete q Add q x x GetHead q Delete q Add while QueueEmpty q 0 y GetHead q Delete q printf c y printf c x 2 算法设计 算法设计 1 假设以数组 se m 存放循环队列的元素 同时设变量 rear 和 num 分别作为队尾指针和 队中元素个数记录 试讨论判别此循环队列的队满条件 写出相应入队和出队算法 并通 过运行验证之 2 假设以带头结点的循环链表表示队列 并且只设一个指针指向队尾结点 试编写相应 的置空队 判队空 入队和出队等算法 并通过运行验证之 3 3 设顺序栈 S 中有 2n 个元素 从栈顶到栈底的元素依次为 a2n a2n 1 a1 要求通过一 个循环队列重新排列栈中元素 使得从栈顶到栈底的元素依次为 a2n a2n 2 a4 a2 a2n 1 a2n 3 a3 a1 请设计算法实现该操作 要求空间复杂度和时间复杂度均为 O n 实验六实验六 矩阵实验矩阵实验 实验任务实验任务 1 程序验证 程序验证 1 建立一个 n n 的对称矩阵 并将该对称矩阵用一维数组存储 2 采用三元组表存储稀疏矩阵 并实现其转置 2 算法填空 算法填空 1 完善该算法 并通过运行来验证 设有一对角矩阵 A 用一维数组 B 存放 A 中的对 角线上的元素 aij 按行优先存放 试设计由 A 确定 B 中元素的算法 算法描述如下 void exstorge int a n n int n int b 3 n int p j k for p 0 p n p for j 0 j 10 if a p j 0 k b k a p j 2 完善该算法 并通过运行来验证 对于二维数组 A m n 其中 m 80 n 80 先 读入 m n 然后读该数组的全部元素 对如下 3 种情况分别编写相应算法 求数组 A 靠边元素之和 求从 A 0 0 开始的互不相邻的各元素之和 当 m n 时 分别求两条对角线的元素之和 否则打印 m n 的信息 main int A 80 80 m n int s1 s2 s3 scanf d d for i 1 i m i for j 1 j n j scanf d s1 fun1 A m n s2 fun2 A m n if m n s3 fun3 A m else printf d d n m n int fun1 int A 80 80 int m int n int i s 0 for i 0 i n i s for i 1 i m 1 i s return s int fun2 int A 80 80 int m int n int i j s 0 for i 0 i m i for j j n s A i j return s int fun3 int A 80 80 int m int i s 0 for i 0 ilchild Preorder T rchild 2 中序遍历递归算法 void Inorder Bitree T if T Inorder T lchild visite T Inorder T rchild 3 后序遍历递归算法 void Postorder Bitree T if T Postorder T lchild Postorder T rchild visite T 二叉树的遍历也可以采用非递归的算法来实现 在二叉树的非递归遍历算法中 我们可以定义一个栈 利用栈存储已访问 或经过 过的节点 二叉树的递归遍历思想将二叉树的遍历简化为对根节点的访问 利用这一特点 适当 修改访问操作的内容 就可以得到许多实际问题的求解算法 实验任务实验任务 1 程序验证 程序验证 1 建立一棵含有 n 个结点的二叉树 采用二叉链表存储 2 前序 或中序 后序 遍历该二叉树 3 采用孩子兄弟表示法建立一棵树 4 基于孩子兄弟表示法存储的树实现前序遍历操作 5 阅读程序 写出程序的功能 并通过运行验证之 typedef struct node int data struct node lchild rchild Bitree p NULL void delete Bitree root int x if root if root data x if p root NULL 14 else if p lchild root p lchild NULL else p rchild NULL else p root delete root lchild x delete root rchild x 6 阅读程序 写出程序功能 并通过运行验证之 typedef struct char data CSTreeNode firstChild CSTreeNode nextSibling CSTreeNode int dep CSTreeNode root if root return 0 else n1 dep root firstChild n2 dep root nextSibling return max n1 1 n2 7 对给定的一组无序序列 建立一棵二叉排序树 8 对建立的二叉排序树实现查找操作 2 算法填空 算法填空 1 完善下述算法 并通过运行来验证 设二叉树采用链式存储结构 试设计一个算法计 算一棵给定二叉树中双孩子结点的数目 算法描述如下 struct bitree elemtype data bitree lchild rchild int twochild bitree t int num1 num2 if t NULL return 0 else if t lchild NULL num2 return num1 num2 1 else 15 num1 num2 return num1 num2 2 完善下述算法 并通过运行来验证 求给定结点在二叉排序树中所在的层数 int level Bstnode root Bstnode p if p return 0 if p root return 1 else if p key key return else return 3 算法设计 算法设计 1 设二叉树采用链式存储结构 试设计一个算法计算一棵给定二叉树中叶子结点的数目 2 在二叉树中查找值为 x 的结点 试设计打印值为 x 的结点的所有祖先结点的算法 提示 对二叉树进行先序遍历 查找值为 x 的结点 找到值为 x 的结点时 栈中存放的是 x 的所有祖先结点 3 编写算法交换二叉树中所有结点的左右子树 4 试写一算法判别给定的二叉树是否为二叉排序树 设此二叉树以二叉链表存储 且树 中结点的关键字均不相同 5 编写算法 在二叉排序树上找出任意两个不同结点的最近公共祖先 6 以孩子兄弟链表作为存储结构 求树中结点 x 的第 i 个孩子 实验八实验八 图实验图实验 实验任务实验任务 1 程序验证 程序验证 1 1 阅读下列程序 指出程序的功能 并通过运行验证之 typedef struct node int adjvex struct node next edgnode typedef struct vextype vertex edgnode link vexnode vexnode ga n 16 void creatdjlist vexnode ga int i j k edgnode s for i 0 i n i ga i vertex getchar ga i link NULL for k 0 kadjvex j s next ga i link ga i link s s malloc sizeof edgnode s adjvex i s next ga j link ga j link s 2 2 在第 1 题的基础上编写广度优先遍历程序 输出遍历序列 3 建立无向图的邻接矩阵存储 并分别对建立的无向图进行深度优先遍历和广度优先遍 历 4 4 建立有向图的邻接表存储 并分别对建立的有向图进行深度优先遍历和广度优先遍历 2 算法填空 算法填空 1 下列函数 MDFSForest 的功能是 对一个采用邻接矩阵作存储结构的图进行深度优先 搜索遍历 输出所得深度优先生成森林中各条边 请在空缺处填入合适内容 使其成为一 个完整的算法 define MaxMun 20 图的最大顶点数 typedef struct char vexs MaxNum 字符类型的顶点表 int edges MaxNum MaxNum 邻接矩阵 int n e 图的顶点数和边数 MGraph 图的邻接矩阵结构描述 typedef enum FALSE TRUE