北京科技大学数据结构试验报告(附录含代码)

一 一 1 功能描述功能描述 输入数据 设为整型 建立单链表 并求相邻两节点 data 值之和为最大的第一节点 2 详细设计详细设计 遵循链表建立的基本思想 建立一个新的链表 H 为表头 r 为新节点 p 为表尾节点 指针 没存入一个新的数据则申请一个新的节点 知道没有数据输入 利用循环和打 擂台法 比较和的大小 并输出 3 测试分析测试分析 程序调试完成后 选取两组数据进行测试 都得出了正确结果 数据以 0 为结束符 若有相同和 则取第一组 结果截图结果截图 4 心得体会心得体会 通过做第一题 学习到链表的建立以及链表里指针的使用 并且复习了比较法里面的 打擂台法 二 二 1 功能描述功能描述 实现算术表达式求值程序 栈的运用 输入中缀表达式 可将其转换成后缀表达式 2 详细设计详细设计 本题目的程序是根据课本上的程序改进之后得出的 课本上有完整的程序 但是有 bug 按照课本上的程序 结果会出现 烫烫烫烫烫 原因是对于优先级的比较没有 处理好 因此加了两行代码 将优先级的比较处理好 即现在的程序 3 测试分析测试分析 程序调试完成后 选取题目所给的式子进行测试 得出了正确后缀表达式结果 结果截图结果截图 4 心得体会心得体会 通过做第二题 对于课本上的知识表示得出 实践出真知 的真理 即使书上的东西 也不一定就是正确的 尤其是代码 最好是个人自己真正实践一下 三 三 1 功能描述功能描述 实现链式队列运算程序 队列的运用 2 详细设计详细设计 本题目是队列相关应用 队列和栈是相反的 队列是先进的先出 因此输入 12345 先出的是 1 本着队列的这一特性 根据课本所学的队列的算法 设计了如下程序 3 测试分析测试分析 程序调试完成后 选取 12345 进行测试 后缀加 0 则一个字符出队 只输入 0 则继 续出队 输入 则打印剩余全部元素 结果截图结果截图 4 心得体会心得体会 通过做第三题 对于队列的特点有了更加深刻的认识 尤其区分队列与栈的不同点 需要特别注意 四 四 1 功能描述功能描述 构造关于 F 的 Huffman 树 求出并打印 D 总各字符的 Huffman 编码 2 详细设计详细设计 本题目是 Huffman 树的应用以及 Huffman 编码的应用 参照课本上关于 Huffman 树的 建立以及 Huffman 编码的应用的实现 将所给数据依权值最小原则建立 Huffman 树 并实现 Huffman 编码 3 测试分析测试分析 程序调试完成后 给出数据 abcdefgh 相应频率为 运行代码得出结果如图 同时选 取另一组数据测试也得出了正确结论 结果截图结果截图 4 心得体会心得体会 通过做第四题 对于 Huffman 树有了更加深刻的体会 同时练习也使得对课本知识进 行实践 有助于更好的理解 Huffman 树的算法 五 五 1 功能描述功能描述 设英文句子 everyone round you can hear you when you speak 1 依次读入句中各单词 构造一棵二叉排序树 2 按 LDR 遍历此二叉排序树 LDR can everyone hear round speak when you 有序 2 详细设计详细设计 本题目是有关二叉树的建立和中序遍历的 二叉树作为数据存储一个很重要的结构 它的建立也是很重要的 本题目代码设计上采用课本上的对于二叉树建立的方法 将 所给单词以二叉树形式建立并存储 然后中序遍历的到字典顺序 3 测试分析测试分析 程序调试完成后 给出单词串 everyone round you can hear you when you speak 运行 代码得出中序遍历结果如图 结果截图结果截图 4 心得体会心得体会 通过做第五题 练习运用二叉树模型解决了一些实际问题如现实中字典的编排问题 在熟悉算法的基础上 同时得出结论 好的算法可以应用与实际生活生产 使之更为 便捷 附录 程序代码 实验一 include stdio h include malloc h typedef struct node int data struct node next list List List Creatlist 建立链表函数 List H p r H 为表头 r 为新节点 p 为表尾节点指针 H List malloc sizeof list 建立头节点 r H p List malloc sizeof list 申请新节点 while scanf d p 新节点链入表尾 r p p List malloc sizeof list r next NULL 将尾节点的指针域置空 return H 返回已创建的头节点 List Adjmax List H 比较相邻两数之和 返回相邻两数之和最大的第一个数指针 List p r q int sum 0 p H next if H next NULL 判断是否为空 printf Empty List q List malloc sizeof list q data 0 while p NULL 比较相邻两数之和 r p next if p sum r data p data 不断赋给 sum 新的最大值 else p p next return q int main char ch printf 请输入整形数据 以空格隔开 0 结束 n printf Ready nY N enter y or Y to continue n while scanf c H Creatlist pmax Adjmax H printf 相邻两数之和最大的第一个数为 d nContinue Y N pmax data free H scanf c return 0 实验二 include include include typedef struct node 栈节点类型 char data 存储一个栈元素 struct node next 后继指针 snode slink int Emptystack slink S 检测栈空 if S NULL return 1 else return 0 char Pop slink top 出栈 char e slink p if Emptystack top return 1 栈空返回 else e top data 取栈顶元素 p top top top next 重置栈顶指针 free p return e void Push slink top char e 进栈 slink p p slink malloc sizeof snode 生成进栈 p 节点 p data e 存入元素 e p next top p 节点作为新的栈顶链入 top p void Clearstack slink top 置空栈 slink p while top NULL p top next Pop top 依次弹出节点直到栈空 top p top NULL char Getstop slink S 取栈顶 if S NULL return S data return 0 符号优先级比较 int Precede char x char y 比较 x 是否 大于 y switch x case x 0 break case case x 1 break case case x 2 break default x 1 switch y case case y 1 break case case y 2 break case y 3 break default y 100 if x y return 1 else return 0 中后序转换 void mid post char post char mid 中缀表达式 mid 到后缀表达式 post 的转换的算法 int i 0 j 0 char x slink S NULL 置空栈 Push 结束符入栈 do x mid i 扫描当前表达式分量 x switch x case while Emptystack S post j Pop break case while Getstop S post j Pop 反复出栈直至遇到 Pop 退掉 break case case case case case while Precede Getstop S x 栈顶运算符 Q1 与 x 比较 post j Pop Q1 x 时 输出栈顶符并退栈 Push Q1front Q rear int Emptyqueue sq Q if Q rear Q front return 1 else return 0 void Enqueue sq Q char ch if Q rear max printf FULL QUEUE else Q ch Q rear ch Q rear void Dequeue sq Q if Emptyqueue Q printf Empty QUEUE n else printf 出队 c n Q ch Q front Q front void Printqueue sq Q if Emptyqueue Q else printf 队列中全部元素 n while Q front Q rear 1 printf c Q ch Q front Q front printf n int main sq Queue char f printf n printf 请输入字符 X nX 并且 X 字符入队 n printf X 0 字符出队 n printf X 打印队列中各元素 n printf n Queue sq malloc sizeof squeue Queue front Queue rear 0 while scanf c else Dequeue Queue if f Printqueue Queue else return 0 实验四 include stdio h include malloc h define N 8 define MAX 100 define M 2 N 1 typedef struct char letter int w int parent lchild rchild Huffm typedef struct char bits N 1 int start char ch ctype void inputHT Huffm HT M 1 int i for i 1 i M i HT i w 0 HT i parent 0 HT i lchild 0 HT i rchild 0 printf 请输入电文字符集 for i 1 i N i scanf c printf 请输入字符出现的频率 for i 1 i N i scanf d void CreatHT Huffm HT M 1 int i j min1 min2 int tag1 tag2 权值最小两个点标号 for i N 1 i M i tag1 tag2 0 min1 min2 MAX for j 1 j i 1 j if HT j parent 0 if HT j w min1 min2 min1 min1 HT j w tag2 tag1 tag1 j else if HT j w min2 min2 HT j w tag2 j HT tag1 parent HT tag2 parent i HT i lchild tag1 HT i rchild tag2 HT i w HT tag1 w HT tag2 w void Huffmcode Huffm HT M 1 Huffm 编码函数 int i j p tag ctype mcode code N 1 for i 1 i N i code i ch HT i letter for i 1 i N i mcode ch code i ch mcode start N 1 tag i p HT i parent for j 0 j N j mcode bits j while p 0 mcode start if HT p lchild tag mcode bits mcode start 0 else mcode bits mcode start 1 tag p p HT p parent code i mcode for i 1 i N i printf c 的 Huffm 编码为 code i ch for j 0 jword p word 0 free s return T if strcmp s word p word lchild else p p rchild if strcmp s word f word lchild s else f rchild s return T BST CreatBst BST T s char keyword 20 T NULL gets keyword while keyword 0 0 s BST malloc sizeof BStree strcpy s word keyword s lchild s rchild NULL T BSTins