湖南文理学院课程设计报告

湖南文理学院课程设计报告湖南文理学院课程设计报告 课程名称 计算机基础课程设计 系 部 电气工程系 专业班级 学生姓名 丁纯 指导教师 曹玲玲 完成时间 2006 年 9 月 28 日 报告成绩 评阅意见 评阅教师 日期 2 目录目录 一 一 计题目及要求计题目及要求 1 1 二 设计的作用目的二 设计的作用目的 三 具体设计三 具体设计 四 四 问题及解决方法问题及解决方法 五 五 心得体会心得体会 六 六 参考文献参考文献 3 课程设计报告课程设计报告 一 计题目及要求 1 设计题目 二叉树遍历演示 2 要求 收集资料 全面分析课题 分解问题 形成整体编程思路 深入分析各个小问题 编写各部分程序模块 对于设计中用到的关键函数 要联系问题进行具体介绍 上机调试 确保程序能正确运行 完成设计报告 并进行答辩 二 设计的作用目的 通过本项课程设计 培养学生独立思考 综合运用所学有关相应知识的能力 使学生巩固 C 语言程序设计 课程学习的内容 掌握工程软件设计的基本方法 强化上机动手编程能力 闯过理论与实践相结合的难关 为了培养学生综合运用所学知识 独立分析和解决实际问题的能力 培养创 意识和创新能力 使学生获得科学研究的基础训练 为后续各门计算机课程的学习和毕业设计打下坚实基础 同时 可以利用这次机会来检验自己的 c 语言水平 提高自己的写作水平 锻炼自己的动手能力 三 具体设计 1 问题分析 二叉树的递归定义 4 二叉树 BinaryTree 是 n n 0 个结点的有限集 它或者是空集 n 0 或 者由一个根结点及两棵互不相交的 分别称作这个根的左子树和右子树的二叉树 组成 二叉树的五种基本形态 二叉树可以是空集 根可以有空的左子树或右子树 或者左 右子树皆为空 二叉树的五种基本形态如下图所示 二叉树不是树的特例 二叉树与无序树不同 二叉树中 每个结点最多只能有两棵子树 并且有左右之分 二叉树并非是树的特殊情形 它们是两种不同的数据结构 二叉树与度数为 2 的有序树不同 在有序树中 虽然一个结点的孩子之间是有左右次序的 但是若该结点只有 一个孩子 就无须区分其左右次序 而在二叉树中 即使是一个孩子也有左右之 分 例 下图中 a 和 b 是两棵不同的二叉树 它们同右图中的普通树 作为 有序树或无序树 很相似 但却不等同于这棵普通树 若将这三棵树均看做普通 树 则它们就是相同的了 二叉树的遍历 5 二叉树是数据结构中一种非常重要的非线形结构 二叉树的一个重要运算是 按深度遍历二叉树 即前序遍历和后序遍历 用程序实现图形演示这三种遍历二 叉树的过程 二叉树是一种特殊的树 这种特殊不仅仅在于其分支最多为 2 以及其它特 征 一个最重要的特殊之处是在于 二叉树是有序的 即 二叉树的左右孩子是 不可交换的 如果交换了就成了另外一棵二叉树 这样交换之后的二叉树与原二 叉树我们认为是不相同的两棵二叉树 但是 对于普通的双分支树而言 不具有 这种性质 二叉树的遍历算法有三种 先序 中序和后序 其划分的依据是视其每个算 法中对根结点数据的访问顺序而定 不仅要熟练掌握三种遍历的递归算法 理解 其执行的实际步骤 并且应该熟练掌握三种遍历的非递归算法 由于二叉树一章 的很多算法 可以直接根据三种递归算法改造而来 比如 求叶子个数 所以 掌握了三种遍历的非递归算法后 对付诸如 利用非递归算法求二叉树叶子个 数 这样的题目就下笔如有神了 2 总体设计思想 遍历方案 从二叉树的递归定义可知 一棵非空的二叉树由根结点及左 右子树这三个 基本部分组成 因此 在任一给定结点上 可以按某种次序执行三个操作 访问结点本身 N 遍历该结点的左子树 L 遍历该结点的右子树 R 以上三种操作有六种执行次序 NLR LNR LRN NRL RNL RLN 注意 前三种次序与后三种次序对称 故只讨论先左后右的前三种次序 三种遍历的命名 根据访问结点操作发生位置命名 NLR 前序遍历 PreorderTraversal 亦称 先序遍历 访问结点的操作发生在遍历其左右子树之前 LNR 中序遍历 InorderTraversal 访问结点的操作发生在遍历其左右子树之中 间 LRN 后序遍历 PostorderTraversal 访问结点的操作发生在遍历其左右子树之后 注意 由于被访问的结点必是某子树的根 所以 N Node L Left subtlee 和 R Right subtree 又可解释为根 根的左子树和根的右子树 NLR LNR 和 LRN 分别又称为先根遍历 中根遍历和后根遍历 6 遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同 如下图虚线所示 具体线路为 从根结点出发 逆时针沿着二叉树外缘移动 对每个结点均途径三次 最后 回到根结点 遍历序列 中序序列 中序遍历二叉树时 对结点的访问次序为中序序列 例 中序遍历上图所示的二叉树时 得到的中序序列为 D B A E C F 先序序列 先序遍历二叉树时 对结点的访问次序为先序序列 例 先序遍历上图所示的二叉树时 得到的先序序列为 A B D C E F 后序序列 后序遍历二叉树时 对结点的访问次序为后序序列 例 后序遍历上图所示的二叉树时 得到的后序序列为 D B E F C A 注意 1 在搜索路线中 若访问结点均是第一次经过结点时进行的 则是前序 遍历 若访问结点均是在第二次 或第三次 经过结点时进行的 则是中序遍历 或后序遍历 只要将搜索路线上所有在第一次 第二次和第三次经过的结点分 别列表 即可分别得到该二叉树的前序序列 中序序列和后序序列 2 上述三种序列都是线性序列 有且仅有一个开始结点和一个终端结点 其余结点都有且仅有一个前趋结点和一个后继结点 为了区别于树形结构中前趋 即双亲 结点和后继 即孩子 结点的概念 对上述三种线性序列 要在某结点的 前趋和后继之前冠以其遍历次序名称 7 例 上图所示的二叉树中结点 C 其前序前趋结点是 D 前序后继结点是 E 中序前趋结点是 E 中序后继结点是 F 后序前趋结点是 F 后序后继结点是 A 但是就该树的逻辑结构而言 C 的前趋结点是 A 后继结点是 E 和 F 遍历算法 中序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 1 遍历左子树 2 访问根结点 3 遍历右子树 先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 1 访问根结点 2 遍历左子树 3 遍历右子树 后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 1 遍历左子树 2 遍历右子树 3 访问根结点 8 3 流程图 0 一一 top pointer 0 pointer 1 一一 pointer 2 sign top 1right pointer I 一一 1 pointer 9 4 源程序 include include define MAXSIZE 100 int k 1 全局变量 为 create 递归取值 通过 Get 依次取得 str MAXSIZE 中的值 typedef struct binode char data struct binode lchild struct binode rchild Binode char Get 从磁盘文件中获取字符 char ch str MAXSIZE 定义字符形变量 int i 0 FILE fp fp fopen b txt r if fp 0 printf cannot open this file n exit 0 else ch fgetc fp while ch EOF str i ch i ch fgetc fp fclose fp k 每调用一次 Get k 加一 return str k Binode create 先序构造一颗二叉树 char ch Binode t ch Get if ch t NULL 10 else t Binode malloc sizeof Binode t data ch t lchild create t rchild create return t char putcharacter char ch 输入字符函数 return putchar ch void Preorder Binode t char visit char 先序遍历二叉树 if t visit t data Preorder t lchild visit Preorder t rchild visit void Inorder Binode t char visit char 中序遍历二叉树 if t Inorder t lchild visit visit t data Inorder t rchild visit void Postorder Binode t char visit char 后序遍历二叉树 if t Postorder t lchild visit Postorder t rchild visit visit t data main char ch Binode t 0 以下为函数声明 char Get Binode create 11 char putcharacter char ch void Preorder Binode t char visit char void Inorder Binode t char visit char void Postorder Binode t char visit char printf nto create bintree n n t create printf Preorder visit bintree n Preorder t putcharacter printf n printf Inorder visit bintree n Inorder t putcharacter printf n printf Postorder visit bintree n Postorder t putcharacter getch 4 运行结果 To create bintree Preorder visit bintree abdecf Inorder visit bintree dbeacf Postorder visit bintree debfca 四 问题及解决方法 1 书写标识符时 忽略了大小写字母的区别 main int a 5 printf d A 编译程序把 a 和 A 认为是两个不同的变量名 而显示出错信息 C 认为大写字母 和小写字母是两个不同的字符 习惯上 符号常量名用大写 变量名用小写表示 以增加可读性 2 忽略了变量的类型 进行了不合法的运算 main 12 float a b printf d a b 是求余运算 得到 a b 的整余数 整型变量 a 和 b 可以进行求余运算 而实型 变量则不允许进行 求余 运算 3 将字符常量与字符串常量混淆 char c c a 在这里就混淆了字符常量与字符串常量 字符常量是由一对单引号括起来的单个 字符 字符串常量是一对双引号括起来的字符序列 C 规定以 作字符串结 束标志 它是由系统自动加上的 所以字符串 a 实际上包含两个字符 a 和 而把它赋给一个字符变量是不行的 4 忽略了 与 的区别 在许多高级语言中 用 符号作为关系运算符 等于 如在 BASIC 程序中可 以写 if a 3 then 但 C 语言中 是赋值运算符 是关系运算符 如 if a 3 a b 前者是进行比较 a 是否和 3 相等 后者表示如果 a 和 3 相等 把 b 值赋给 a 由于习惯问题 初学者往往会犯这样的错误 5 忘记加分号 分号是 C 语句中不可缺少的一部分 语句末尾必须有分号 a 1 b 2 编译时 编译程序在 a 1 后面没发现分号 就把下一行 b 2 也作为上一行 语句的一部分 这就会出现语法错误 改错时 有时在被指出有错的一行中未发 现错误 就需要看一下上一行是否漏掉了分号 z x y t z 100 printf f t 对于复合语句来说 最后一个语句中最后的分号不能忽略不写 这是和 PASCAL 不 同的 6 多加分号 对于一个复合语句 如 z x y t z 100 printf f t 13 复合语句的花括号后不应再加分号 否则将会画蛇添足 又如 if a 3 0 I 本是如果 3 整除 a 则 I 加 1 但由于 if a 3 0 后多加了分号 则 if 语句到 此结束 程序将执行 I 语句 不论 3 是否整除 a I 都将自动加 1 再如 for I 0 I 5 I scanf d printf d x 本意是先后输入 5 个数 每输入一个数后再将它输出 由于 for 后多加了一个 分号 使循环体变为空语句 此时只能输入一个数并输出它 7 输入变量时忘记加地址运算符 scanf d d a b 这是不合法的 Scanf 函数的作用是 按照 a b 在内存的地址将 a b 的值存进 去 输入时 不能用逗号作两个数据间的分隔符 如下面输入不合法 3 4 输入数据时 在两个数据之间以一个或多个空格间隔 也可用回车键 跳格键 tab scanf d d C 规定 如果在 格式控制 字符串中除了格式说明以外还有其它字符 则在输 入数据时应输入与这些字符相同的字符 下面输入是合法的 3 4 此时不用逗号而用空格或其它字符是不对的 3 4 3 4 又如 scanf a d b d 输入应如以下形式 a 3 b 4 9 输入字符的格式与要求不一致 在用 c 格式输入字符时 空格字符 和 转义字符 都作为有效字符输入 scanf c c c 如输入 a b c 字符 a 送给 c1 字符 送给 c2 字符 b 送给 c3 因为 c 只要求读入 一个字符 后面不需要用空格作为两个字符的间隔 14 10 输入输出的数据类型与所用格式说明符不一致 例如 a 已定义为整型 b 定义为实型 a 3 b 4 5 printf f d n a b 五 心得体会 通过这次编程实习 使我体会到了很多道理 也明白了不少事情 刚开始的时候 老师说编写很简单 用不了多久就能做出来 于是我在那一 周基本上没为我的实习报告做多少事情 因为连我自己也觉得万年历实在是太简 单了 就没必要浪费时间查资料了 后来 同组的人说我们的程序编译的要求很 难做到 他们都编了好多遍了 得到的结果却要么是编译出错 要么是只能查询 不能在运行后马上显示日期 这时 我才从懒散中醒悟过来 不能小看任何事情 然后同组的人聚在了一起 讨论程序编译出错的草稿有哪些地方错了 哪些地方 需要修改 哪些地方需要重新来过 我们为此探讨了整整一天时间 竟然毫无所 获 因为在以前的学习中 我们没有涉及 显示日期 并且 随系统的时间而改 变 的程序 但是 我们没有放弃 化整为零 有的去图书馆查资料 有的去上 网搜索 还有的就找相关的杂志 剩下的就执笔记下所有查来的信息 最终 皇 天不负有心人 经过全组人的努力 我们成功的解决了 随系统时间而改变 的 难题 同时 也使我体会到 团结的力量和坚持不懈的精神的可贵之处 这次的 c 语言程序设计我才知道自己的计算机知识还是多么的薄弱 使我认 识到我们一定要学好计算机这门高科技 而对于我这样的初学者的知识基础较薄 弱 对一些应用操作理解起来较为困难 我想要能从整体概念上较好地理解和把 握计算机的基本应用和应用软件 不是仅仅靠听别人说自己不动手 买几本培训 的书籍 囫囵吞枣地看一遍 然后上机练习几次就可以大功告成的 因此学习过 程中我们应该要注意多做笔记 要注意结合实际应用 因为我们不仅要掌握大量 的计算机应用方面的知识和技能 并且还经常要把这些知识传授给别人 求学者切记贪多嚼不烂 而初学者最易犯 大而全 和 速成 的错误 须 知 罗马非一日之功 所能建成 什么都学 肯定什么都学不透 要集中精力打 攻坚战 我认为学习计算机首先要明白自己的学习目标究竟是什么 你可以根据 自己的实际工作出发 是做系统维护 软件开发 图像加工 公文处理 网页制 作还是数据库管理 然后再有针对性的在相应的学习方向上进行提高 要制定出 详细的学习规划 包括需要购买什么书籍 家里如果没有电脑可供练习 是否需 要购买一台电脑等问题 如果没有学习规划 不投资学习机器 没有实践场所 没有学习资