文本编辑器.doc

沈沈 阳阳 工工 程程 学学 院院 课 程 设 计 设计题目 数据结构及算法的设计与实现 系 别 信息系 班级 计本 081 学生姓名 张 博 学号 2008412121 指导教师 杨政 代钦 职称 讲师 讲师 起止日期 2009 年 12 月 28 日起 至 2010 年 1 月 8 日 止 沈阳工程学院课程设计报告 成绩评定表 I 沈沈 阳阳 工工 程程 学学 院院 数据结构课程设计成绩评定表数据结构课程设计成绩评定表 系 部 系 部 信息工程系信息工程系 班级 班级 计本计本081081 学生姓名 学生姓名 张张 博博 指指 导导 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 调研 论证 能独立查阅文献 收集资料 能制定课程设计 方案和日程安排 0 15 54 43 32 2 工作能力 态度 工作态度认真 遵守纪律 出勤情况是否良好 能够独立完成设计工作 0 25 54 43 32 2 工作量 按期圆满完成规定的设计任务 工作量饱满 难度适宜 0 25 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 55 54 43 32 2 指导教师评审成绩指导教师评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 指指 导导 教教 师师 签签 名 名 年年 月月 日日 评评 阅阅 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 查阅 文献 查阅文献有一定广泛性 有综合归纳资料的能 力 0 25 54 43 32 2 工作量工作量饱满 难度适中 0 55 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 35 54 43 32 2 评阅教师评审成绩评阅教师评审成绩 加权分合计乘以 加权分合计乘以 4 4 分分加权分合计加权分合计 评评 阅阅 教教 师师 签签 名 名 年年 月月 日日 答答 辩辩 小小 组组 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 学生汇报 汇报准备充分 思路清晰 语言表达准确 概 念清楚 论点正确 有层次 有重点 基本上 反映了所完成任务的全部内容 时间符合要求 0 55 54 43 32 2 答 辩 思路清晰 回答问题有理论依据 基本概念清 楚 主要问题回答准确 深入 有说服力 0 55 54 43 32 2 答辩小组评审成绩答辩小组评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 沈阳工程学院课程设计报告 成绩评定表 II 答辩小组教师签名 答辩小组教师签名 年年 月月 日日 沈阳工程学院课程设计报告 任务书 I 数据结构课程设计任务书数据结构课程设计任务书 一 设计目的一 设计目的 数据结构是计算机专业的核心课程 是一门实践性很强的课程 课程设计 是加强学生实践能力的一个强有力手段 要求学生掌握数据结构的应用 算法 的编写 类 C 语言的算法转换成 C C 程序并上机调试的基本方法 还要求 学生在完成程序设计的同时能够写出比较规范的设计报告 严格实施课程设计 这一环节 对于学生基本程序设计素养的培养和软件工作者工作作风的训练 将起到显著的促进作用 二 设计要求设计要求 1 课程设计题目每组三题 每个学生必须独立完成 2 课程设计时间为 2 周 3 设计语言 C C 不限 4 课余时间完成源程序和课程设计报告等文档书写工作 上机时间只能做 调试工作 上机时带上源程序 数据结构教材 C 语言教材 5 上机任务 1 选择合适的数据结构 并定义数据结构的结构体 2 根据程序所要完成的基本要求 设计出完整的算法 3 设计出主程序 main 函数 使其成为完整的程序 6 上机时间 按照实验室上机时间安排计划执行 7 无论在校外 校内 都要严格遵守学校和所在单位的学习和劳动纪律 规章制度 学生有事离校必须请假 课程设计期间 无故缺席按旷课处理 缺 席时间达四分之一以上者 其成绩按不及格处理 三 报告书写格式报告书写格式 1 封皮 2 成绩单 3 任务书 4 目录 5 正文 6 参考文献 四 成绩评定四 成绩评定 评定成绩根据课程设计表现 成绩测验 课程设计报告等进行综合评定 评定等级 不及格 及格 中 良好 优秀 五 设计题目五 设计题目 设计题目一设计题目一 航空客运订票系统航空客运订票系统 设计要求 1 每条航线所涉及的信息有 终点站名 航班号 飞机号 飞行周日 星 期几 乘员定额 余票量 已订票的客户名单 包括姓名 订票量 舱位等级 1 2 或 3 以及等候替补的客户名单 包括姓名 所需的票量 沈阳工程学院课程设计报告 任务书 II 2 作为示意系统 全部数据可以只放在内存中 3 系统能实现的操作和功能如下 a 查询航线 根据旅客提出的终点站名 输出下列信息 航班号 飞机号 星期几飞行 最近一天航班的日期和余票 b 承办订票业务 根据客户提出的要求 航班号 订票数额 查询该航班票额 情况 若尚有余票 则为客户办理订票手续 输出座位号 若已满员或余票额 少于订票额 则需重新询问客户要求 若需要 可登记排队候补 c 承办退票 业务 根据客户提供的情况 日期 航班 为客户办理退票手续 后人内查询 该航班时候有人排队候补 首先询问排在第一的客户 若所退票额能满足他的 要求 则为他办理订票手续 否则依次询问其他排队候补的客户 设计题目二设计题目二 简易文本编辑器简易文本编辑器 设计要求 1 具有图形菜单界面 2 查找 替换 等长 不等长 插入 插串 文本块的插入 块移动 行块 列块移动 删除 3 可正确存盘 取盘 4 正确显示总行数 设计题目三设计题目三 学生搭配问题学生搭配问题 设计要求 一班有 m 个女生 有 n 个男生 m 不等于 n 现要开一个舞会 男女生分别编 号坐在舞池的两边的椅子上 每曲开始时 依次从男生和女生中各出一人配对跳 舞 本曲没成功配对者坐着等待下一曲找舞伴 请设计一系统模拟动态地显示出上述过程 要求如下 1 输出每曲配对情况 2 计算出任何一个男生 编号为 X 和任意女生 编号为 Y 在第 K 曲配对 跳舞的情况 至少求出 K 的两个值 3 尽量设计出多种算法及程序 可视情况适当加分 提示 用队列来解决 比较方便 设计题目四设计题目四 设计实现哈夫曼编码程序 设计内容与步骤设计内容与步骤 选择合适的数据结构 结点结构的设计 算法设计与分析 程序设计 实现 调试 课程设计说明书 进度安排进度安排 设计工作 4 学时 实现与调试 12 学时 课程设计说明书 4 学时 设计考核要求设计考核要求 考勤 20 课程设计说明书 50 答辩 30 沈阳工程学院课程设计报告 任务书 III 六 参考书目六 参考书目 1 谭浩强著 C 程序设计 清华大学出版社 2005 2 张居敏著 C 语言编程精要 电子工业出版社 2006 3 张仁杰著 C 语言实训教程 中国电力出版社 2006 4 佟伟光 杨政 数据结构与算法 北京大学出版社 2008 5 徐考凯著 数据结构课程实验 清华大学出版社 2001 沈阳工程学院课程设计报告 摘要 IV 摘摘 要要 数据结构 是一门专业技术基础课 它的教学要求是 学会分析研究计 算机加工的数据结构的特征 以便为应用涉及的数据选择适当的逻辑结构 存 储结构及其相应的算法 并初步掌握算法的时间分析和空间分析的技术 另一 方面 本课程的学习过程也是复杂程序设计的训练过程 要求学生编写的程序 结构清楚和正确易读 符合软件工程的规范 在学习中 先要学习程序设计课程的目的掌握设计程序的思路 学习会用 计算机语言编写程序 以实现所需要处理的任务 要正确处理算法与语法的关 系 算法是程序的核心 是灵魂 语法是外壳 是工具 不应把学习重 点放在 语法规则上 语法是重要的 不掌握语法规则就无法编写出正确的程序 一定 要把重点放在解题的思路上 通过思考 和大量的阅读 来构造一个完整的程 序 请记住 重要的是学会编程 而不是背语法 程序设计是为了锻炼我们的实际动手能力 在一定程度上 又增加了我们 的各方面的知识 特别是一些联系实际的课程设计 它的完成需要自己平时积 累的大量知识 并且需要勤于思考的能力和无限的激情 本次课设主要是学习 程序设计的方法 进行程序设计的基本训练 大多数的学生应该把精力放在最 基本 最常用的内容上 学好基本功 最后 感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲 关键词关键词 线性表 栈和队列 二叉树 查找 排序 字符串模式匹配 沈阳工程学院课程设计报告 目录 目 录 第一章第一章 航空客运订票系统航空客运订票系统 1 1 1 问题分析 1 1 2 数据结构与算法分析 1 1 2 1 结构与算法分析 1 1 2 2 系统运行流程图 1 1 3 核心代码 2 1 4 运行结果 12 1 4 1 航空客运订票系统主界面 12 1 4 2 系统功能 12 第二章第二章 简易文本编辑器简易文本编辑器 14 2 1 问题分析 14 2 2 数据结构与算法分析 14 2 2 1 结构与算法分析 14 2 2 2 系统运行流程图 14 2 3 核心代码 15 2 4 运行结果 27 2 4 1 文本编辑器主界面 27 2 4 2 系统功能 28 第三章第三章 学生搭配问题学生搭配问题 31 3 1 问题分析 31 3 2 数据结构与算法分析 31 3 2 1 结构与算法分析 31 3 2 2 系统运行流程图 31 3 3 核心代码 32 3 4 运行结果 33 第四章第四章 哈夫曼编码程序哈夫曼编码程序 35 4 1 问题分析 35 4 2 数据结构与算法分析 35 4 2 1 结构与算法分析 35 4 2 2 系统运行流程图 35 4 3 核心代码 36 4 4 运行结果 40 总总 结结 41 致致 谢谢 42 参考文献参考文献 43 沈阳工程学院课程设计报告 航空客运订票系统 1 第一章 航空客运订票系统 1 1 问题分析 航空客运订票的业务活动包括 查询航线 客票预订和办理退票等 每条 航线所涉及的信息有 终点站名 航班号 飞机号 飞行周日 星期几 乘员 定额 余票量 已订票的客户名单 包括姓名 订票量 舱位等级 1 2 或 3 以及等候替补的客户名单 包括姓名 所需的票量 作为示意系统 全部数据 可以只放在内存中 1 2 数据结构与算法分析 1 2 1 结构与算法分析 两个客户名单可分别由线性表和队列实现 为查找方便 已订票客户的线 性表应按客户姓名有序 并且 为插入和删除方便 应以链表作存储结构 由 于预约人数无法预计 队列也应以链表作存储结构 整个系统需汇总各条航线 的情况登录在一张线性表上 由于航线基本不变 可采用顺序存储结构 并按 航班有序或按终点站名有序 每条航线是这张表上的一个记录 包含上述 8 个 域 其中乘员名单域为指向乘员名单链表的头指针 等候替补的客户名单域为 分别指向队头和队尾的指针 队列 Queue 是只允许在一端进行插入 而在另一端进行删除的运算受 限的线性表 用队列来进行客户信息的存储 编辑用户使用菜单 内容包括 输入航班信息 保存航班信息 读取航班信息 查找航班信息 删除航班信息 订票信息 退票信息以及修改信息 具体分为 输入航班信息 首先将航班的信息输入进电脑中 并将数据置入文件 中 浏览航班信息 将输入的航班信息从文件中读出并输出 修改航班信息 可以将已经输入的错误航班信息进行修改 查找航班信息 分为按航班号查找 按终点站查找 按航线查找三种查 找方式进行查找 删除航班信息 将错误信息进行删除 订票功能 客户对想要购买的票进行订票 退票功能 将不想要的票进行退票 退出 退出程序 沈阳工程学院课程设计报告 航空客运订票系统 2 1 2 2 系统运行流程图 航空客运订票系统运行的流程图 如图 1 1 所示 图 1 1 航空客运订票系统运行的流程图 1 3 核心代码 include include include define M 30 define N 100 define g 200 1 航班结构 typedef struct char num 20 1 航班号 char number 10 2 飞机号 沈阳工程学院课程设计报告 航空客运订票系统 3 char upcity 10 3 起飞城市 char downcity 10 4 降落城市 float price 5 航票价格 int ticketnum 6 航票数量 int seat g 1 7 座位状态 char uptime 20 8 起飞时间 char downtime 20 9 降落时间 char day 20 起飞日期 char weekday 20 起飞周日 Plane Plane plane M 2 客户结构 typedef struct char name 10 客户姓名 char update 8 所乘飞机起飞日期 long int document 证件号 按证件号将客户信息写入文 char planeNum 20 订票的航班号 int ticketNum 订票数量 int seat g 1 坐号 int level 舱位等级 Client Client client N 3 打印选择菜单 static void Instruction void printf 欢迎使用此航空售票模拟系统 n printf n n printf n printf n printf 0 结束 n printf 1 输入航班信息 n printf 2 查找航班 n printf 3 购买及预定机票 n printf 4 退票 n printf 5 建立航班文件 n 沈阳工程学院课程设计报告 航空客运订票系统 4 printf 6 建立客户文件 n printf n printf n n printf 请选择您希望的服务 8 查询航班 static void Searchplane void FILE fp char city 10 plane 20 way1 20 way2 20 Plane p int i 0 j do printf 按地名查询按 1 按航班号查询按 2 或按航线查找 3 scanf d while j 1 if j 1 printf 输入想去的地方 scanf s city if j 2 printf 输入航班号 scanf s plane if j 3 printf 输入航线 n scanf s way1 scanf s way2 if fp fopen d plane rb NULL 打开 2 进制使用文件 printf 不能打开航班文件 n 沈阳工程学院课程设计报告 航空客运订票系统 5 exit 0 文件打开失败退出 while feof fp 打印出所有开往客户所到城市的航班 fread if strcmp p downcity city 0 strcmp p num plane 0 printf s s s s 4 2f d s s s s n p num p number p upcity p downcity p price p ticketnum p uptime p downtime p day p wee kday i else if strcmp p upcity way1 0 printf s s s s 4 2f d s s s s n p num p number p upcity p downcity p price p ticketnum p uptime p downtime p day p wee kday i if j 1 if i 0 没有开往客户所到城市的航班 printf 没有开往 s 的航班 n city else if i 0 printf t 有 d 个航班开往 s 请从中选择 t n i city 提示客户选择 if j 2 if i 0 printf 没有 s 航班号的的航班 n plane 沈阳工程学院课程设计报告 航空客运订票系统 6 if j 3 if i 0 printf 没有 s 开往 s 的航线 n way1 way2 fclose fp 9 买票及预定 static void Buyticket void FILE fp1 fp2 int i j k m ticket char planenum 20 if fp1 fopen d plane rb NULL 打开 2 进制使用文件 printf 不能打开航班文件 n exit 0 文件打开失败退出 if fp2 fopen d client rb NULL 打开 2 进制使用文件 printf 不能打开客户文件 n exit 0 文件打开失败退出 for i 0 i 30 i fread for i 0 i 100 i fread fclose fp1 fclose fp2 printf 输入航班号 scanf s planenum 读入所定航班号 printf 输入要购买的机票数量 scanf d 读入定票数量 沈阳工程学院课程设计报告 航空客运订票系统 7 printf n for i 0 i 30 i if strcmp plane i num planenum 0 break if i 30 printf 没有此航班飞机 n printf 返回菜单 n for m 0 m ticket printf 输入姓名 scanf s client m name printf 输入起飞日期 scanf s client m update printf 输入证件号 scanf ld do printf 选择舱等级 1 2or3 scanf d while client m level3 printf 票序 航班 座位号 起飞日期 姓名 证件号 舱位等级 n for j 1 j ticket j for k 1 k 200 k 确定客户座位号和此座位是否卖出 沈阳工程学院课程设计报告 航空客运订票系统 8 if plane i seat k 0 plane i seat k 1 client m seat j k break printf t d t s t d t s t s t ld t d n j plane i num client m seat j client m update client m name client m document client m level strcpy client m planeNum plane i num plane i ticketnum ticket client m ticketNum ticket printf n printf t 您一共购票 d 张 祝您旅途愉快 t n n ticket if plane i ticketnum0 余票不足但未卖完 printf 所剩机票不足 d n ticket do printf 是否购买 1 0 scanf d while k 1 if k 1 do printf 输入要购买的机票数量 继续购买 scanf d while ticket plane i ticketnum goto leap1 沈阳工程学院课程设计报告 航空客运订票系统 9 if fp1 fopen d plane wb NULL 格式化 2 进制使用文件 printf 清空文件失败 n exit 0 文件清空失败退出 for i 0 i 30 i if fwrite if fp2 fopen d client wb NULL 格式化 2 进制客户使用文件 printf 清空文件失败 n exit 0 文件清空失败 for i 0 i 100 i if fwrite fclose fp1 fclose fp2 10 退票 static void Refundticket void FILE fp1 FILE fp2 char update 8 char planenum 20 int i j k m n long int document if fp1 fopen d plane rb NULL 打开 2 进制使用文件 printf 不能打开航班文件 n exit 0 文件打开失败退出 沈阳工程学院课程设计报告 航空客运订票系统 10 if fp2 fopen d client rb NULL 打开 2 进制使用文件 printf 不能打开客户文件 n exit 0 文件打开失败退出 for i 0 i M i fread for i 0 i N i fread fclose fp1 fclose fp2 printf 输入航班号 scanf s planenum 读入所定航班号 printf 输入你的证件号 scanf ld 读入证件号码 printf 输入航班起飞日期 scanf s update for i 0 i M i if strcmp plane i num planenum 0 break if i M printf 您还没有定此航班的票 请返回菜单操作 n if i M for m 0 m N m if strcmp client m planeNum planenum 0 沈阳工程学院课程设计报告 航空客运订票系统 11 plane i ticketnum client m ticketNum k client m ticketNum for j 1 j k j n client m seat j plane i seat n 0 if fp1 fopen d plane wb NULL 格式化 2 进制使用文件 printf 清空文件失败 n exit 0 文件清空失败退出 for i 0 i M i if fwrite if fp2 fopen d client wb NULL 格式化 2 进制客户使用文件 printf 清空文件失败 n exit 0 文件清空失败 for i 0 i N i if i m if fwrite client N 1 document 0 删除一客户后 让最后一客户结构可用 if fwrite printf 退票成功 共退票 d 张 n client m ticketNum fclose fp1 fclose fp2 沈阳工程学院课程设计报告 航空客运订票系统 12 1 4 运行结果 1 4 1 航空客运订票系统主界面 主界面 如图 1 2 所示 图 1 2 航空订票系统界面 1 4 2 系统功能 预定航班功能 如图 1 3 所示 图 1 3 购买机票界面 沈阳工程学院课程设计报告 航空客运订票系统 13 退票功能 如图 1 4 所示 图 1 4 退票界面 沈阳工程学院课程设计报告 简易文本编辑器 14 第二章 简易文本编辑器 2 1 问题分析 一个简易文本编辑器应该具有图形菜单界面 包括查找 替换 等长 不 等长 插入 插串 文本块的插入 块移动 行块 列块移动 删除文本信 息等功能并可正确存盘 取盘 正确显示总行数 2 2 数据结构与算法分析 2 2 1 结构与算法分析 为实现数据的有序存储 该编辑器应该用顺序表来存储输入的信息 顺序 表是数据结构中线性表的一种 它是用一块地址连续的存储空间依次存储线性 表的元素 其特点为 在顺序表上逻辑关系相邻的俩个元素在物理位置上也相 邻 在顺序表上可以随即存取表中的元素 在编辑器的主界面中应有如下提示 信息 清空以前的文本信息 将用数组存的数据内容全部置为 0 显示当前文本信息 遍历用数组存入的信息 并输入到外部显示器上 编辑信息 定义一个结构体 并在结构体中定义一个字符型的一维数组 和一个整型变量 这个整型变量用于记录一维数组中存入数据的个数 替换文本信息 首先在数组中查找要被替换的信息 如果找到该信息 提示输入要替换的信息内容 否则提示未找到要被替换的信息 插入文本信息 首先在数组中查找要插入点 如果找到该插入点 提示 输入插入信息 确认插入信息后 提示选择向前插入信息还是向后插入信 息 如果未找到插入点 显示未找到要插入的位置 移动文本信息 首先在数组中查找要移动的信息 如果找到该信息 提 示是进行列移动还是进行行移动 否则提示未找到要移动的信息 删除文本信息 首先在数组中查找要删除的信息 如果找到该信息 提 示是否确认删除该信息 通过确认来删除信息 如果未找到要删除的信息 提示未找到该信息 退出编辑器 显示感谢使用该软件并退出 2 2 2 系统运行流程图 文本编辑器的运行流程图 如图 2 1 所示 沈阳工程学院课程设计报告 简易文本编辑器 15 图 2 1 文本编辑器流程图 2 3 核心代码 include include include include include define MAXSIZE 100 int ntext 全局变量 int b 0 typedef struct char sr MAXSIZE int hang 沈阳工程学院课程设计报告 简易文本编辑器 16 int lie shuru int strindex shuru m char t int i2 int l 查找要操作的数据的位置 模式匹配 int i4 l j 0 while i4 ntext 返回匹配的第一个字符的下标 else return 1 模式匹配不成功 void charu shuru int i t 0 t2 0 a 1 char cr 20 pd x 500 c d int i2 printf n 当前文本信息为 n for i2 0 i2 ntext 1 i2 printf c k sr i2 printf n 输入您要在哪个内容前插入 以 结束 fflush stdin while c getchar 用一个数组接收要插入在哪个内容之前 if c break else cr t c t continue a strindex k cr t l 查找并返回要插入的位置点 if a 1 l a t int hs 1 ls 0 for b 0 b a b ls if k sr b n hs ls 0 沈阳工程学院课程设计报告 简易文本编辑器 18 if a 1 printf n 查找到结尾没有找到插入点 nR 重新查找点 n 双击回车键返回菜单 n l 0 fflush stdin d getchar fflush stdin else int i2 printf n 当前文本信息为 n for i2 0 i2 a i k sr i t2 k sr i for i 0 i t2 i k sr i a x i ntext ntext t2 printf n 当前文本信息为 n for i2 0 i2 ntext 1 i2 printf c k sr i2 printf 插入成功 n fflush stdin getchar if d r d R pd r pd R l 0 charu k l FILE fp int b11 fprintf fp The contents is n for b11 0 b11 ntext 1 b11 fprintf fp c k sr b11 fclose fp 沈阳工程学院课程设计报告 简易文本编辑器 20 void tihan shuru char c th 20 d d1 bth 20 int i2 printf n 当前文本信息为 n for i2 0 i2 ntext 1 i2 printf c r sr i2 printf n 输入要被替换的内容 以 结束 fflush stdin while c getchar t 指替换前内容的长度 if c break else bth t c t continue a strindex r bth t l 查找要被替换的内容的位置 if a 1 l a t int hs 1 ls 0 for b 0 b a b ls 沈阳工程学院课程设计报告 简易文本编辑器 21 if r sr b n hs ls 0 if a 1 printf n 查找到结尾没有找到要被替换的内容 n 继续查找请按 R 双击回车键退出 n l 0 printf n d a printf n d i1 printf n d ntext fflush stdin d getchar fflush stdin else printf n n 已经找到要查找的数据 n t t 在第 d 行 第 d 列 nR 继续向后查找相同 内容 nA 进一步进行替换操作 n 请选择 hs ls 1 printf n d a printf n d i1 printf n d ntext fflush stdin d getchar if d r fflush stdin d1 getchar if d1 a d1 A 沈阳工程学院课程设计报告 简易文本编辑器 22 printf n 输入要替换的内容 以 结束 fflush stdin while c getchar t1 指替换后的内容长度 if c break else th t1 c t1 continue if t t1 将要被替换的内容和替换后的内容 进行长度比较 for i 0 it1 for i 0 i t1 i r sr i a th i for i a t1 i a i r sr i t1 t r sr i for i 0 i t1 i r sr i a th i ntext ntext t1 t printf 替换成功 printf n 当前文本信息为 n for i2 0 i2 ntext 1 i2 printf c r sr i2 getchar if d R d r tihan r l FILE fp int b11 fprintf fp The contents is n for b11 0 b11next NULL 入队函数 void EnQueue LinkQueue p QueuePtr malloc sizeof QNode p num num 沈阳工程学院课程设计报告 学生搭配问题 33 p next NULL Q rear next p Q rear p 出队函数 void DeQueue LinkQueue if Q front Q rear printf 队列为空 p Q front next num p num Q front next p next q p next if Q rear q Q rear Q front free p 输出第 i 首曲子时女队的情况 void printF LinkQueue int n 1 while nnext while F rear p printf d p num p p next printf d n p num 3 4 运行结果 该搭配问题的运行结果 如图 3 2 所示 沈阳工程学院课程设计报告 学生搭配问题 34 图 3 2 运行结果 沈阳工程学院课程设计报告 哈夫曼编码 35 第四章 哈夫曼编码程序 4 1 问题分析 哈夫曼编码 Huffman Coding 是一种编码方式 哈夫曼编码是可变字长编码 VLC 的一种 在计算机信息处理中 哈夫曼编码是一种一致性编码法 用于 数据的无损耗压缩 构建一个哈弗曼树 规定哈夫曼树中的左分支代表 0 右 分支代表 1 则从根节点到每个叶子节点所经过的路径分支组成的 0 和 1 的序 列便为该节点对应字符的编码 即所要得到的哈夫曼编码 4 2 数据结构与算法分析 4 2 1 结构与算法分析 1 哈夫曼的构建 哈夫曼树 给定 n 个权值作为 n 个叶子结点 构造一棵二叉树 若带权路 径长度达到最小 称这样的二叉树为最优二叉树 也称为哈夫曼树 Huffman tree 对于哈夫曼树的构建 假设有 n 个权值 则构造出的哈夫曼树有 n 个叶子 结点 n 个权值分别设为 w1 w2 wn 则哈夫曼树的构造规则为 将 w1 w2 wn 看成是有 n 棵树的森林 每棵树仅有一个结点 在森林中选出两个根结点的权值最小的树合并 作为一棵新树的左 右 子树 且新树的根结点权值为其左 右子树根结点权值之和 从森林中删除选取的两棵树 并将新树加入森林 重复 2 3 步 直到森林中只剩一棵树为止 该树即为所求得的哈夫 曼树 2 哈夫曼编码 哈夫曼动态编码 动态哈夫曼编码使用一棵动态变化的哈夫曼树 对第 t 1 个字符的编码是根据原始数据中前 t 个字符得到的哈夫曼树来进行的 编码和 解码使用相同的初始哈夫曼树 每处理完一个字符 编码和解码使用相同的方 法修改哈夫曼树 所以没有必要为解码而保存哈夫曼树的信息 编码和解码一 个字符所需的时间与该字符的编码长度成正比 所以动态哈夫曼编码可实时进 行 4 2 2 系统运行流程图 哈夫曼编码流程图 如图 4 1 所示 沈阳工程学院课程设计报告 哈夫曼编码 36 图 4 1 哈夫曼编码流程图 4 3 核心代码 include stdio h include stdlib h include string h typedef char ElemType typedef struct 树的结构体 ElemType elem 元素类型 unsigned int m weight 元素的权值 unsigned int parent lchild rchild 结点 HTNode HuffmanTree typedef char HuffmanCode 定义二维编码数组 typedef int Status typedef struct weight 字符结构体 沈阳工程学院课程设计报告 哈夫曼编码 37 char elem unsigned int m weight Weight Status main void HuffmanTree HT HuffmanCode HC Weight w char c the symbolizes int i n the number of elements int wei the weight of a element printf 请输入哈夫曼节点数 scanf d w Weight malloc n sizeof Weight for i 0 i n i printf 请输入变量 scanf 1s d w i elem c w i m weight wei HuffmanCoding OutputHuffmanCode HT HC n system pause return 1 void HuffmanCoding HuffmanTree HT HuffmanCode HC Weight w int n int i m s1 s2 start c f char cd HuffmanTree p if n 1 return m 2 n 1 二叉树的结点个数等于 y 叶子节点数的二倍减一 沈阳工程学院课程设计报告 哈夫曼编码 38 HT HuffmanTree malloc m 1 sizeof HTNode 申请二叉树的内存空间 for i 1 i n i 初始化二叉树 叶子节点 HT i elem w i 1 elem HT i m weight w i 1 m weight HT i parent HT i lchild HT i rchild 0 for i m i 初始化二叉树的非叶子节点 HT i elem 0 HT i m weight HT i parent HT i lchild HT i rchild 0 哈夫曼编码树生成 for i n 1 i m i Select HT i 1 HT s1 parent i HT s2 parent i HT i lchild s1 HT i rchild s2 HT i m weight HT s1 m weight HT s2 m weight 编码赋值的操作 HC HuffmanCode malloc n sizeof char cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 for c i f HT i parent f 0 c f f HT f parent if HT f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char strcpy HC i void Select HuffmanTree HT int n int s1 int s2 沈阳工程学院课程设计报告 哈夫曼编码 39 int i s1 s2 0 for i 1 i n i if HT i m weight HT s2 m weight s1 i else s2 i if s1 0 s2 0 else if s2 0 if HT i m weight s2 i s1 s1 s2 s2 i ret