数据结构课设

1、沈沈 阳阳 工工 程程 学学 院院课 程 设 计设计题目：设计题目：校园导航、文章编辑校园导航、文章编辑 沈 阳 工 程 学 院课程设计任务书 课程设计题目：课程设计题目： 校园导航校园导航 一、问题描述当我们参观某校园时，就会遇到这样一个问题：从当前所在位置出发去校园另外某个位置，要走什么样的路线最省时？本课程设计实例再给出校园各主要建筑的名称信息及有路线连通的建筑之间的行进时间的基础上，利用校园导航系统计算出给定的起点到终点之间行进时间最短的行进路线。二、课程设计主要内容及要求1. 从地图文件中读取校园主要建筑信息及建筑间行进时间的信息。2计算出给定的起点到终点之间行进时间最短的行进路线。

2、3输出该路线（包含路过哪些建筑）及其总行进时间。4. 若输入错误，则给出提示信息。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后

3、的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋体小四号字，行间距 18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说 明书。 五、时间进度安排顺序阶段日期计 划 完

4、成 内 容备注1第 1 天（12 月 27 日）阅读资料2第 23 天（12 月 28 日12 月 30 日）系统分析设计3第 48 天（12 月 31 日1 月 5 日）程序编制、调试及运行4第 9 天（1 月 6 日）成绩评定5第 10 天（1 月 7 日）撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C 语言版）. 北京:清华大学出版社.20072谭浩强.C 程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C

5、 语言版）习题与解析.北京:清华大学出版社.2002.04沈沈 阳阳 工工 程程 学学 院院课 程 设 计设计题目：设计题目： 文章编辑文章编辑 系系 别别 信息工程系信息工程系 班级班级 计本计本 091091 学生姓名学生姓名 姚大州姚大州 朱思坤朱思坤 学号学号 2121 1212 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 起止日期：起止日期：20102010 年年 1212 月月 2727 日起日起至至 20112011 年年 1 1 月月 7 7 日止日止沈 阳 工 程 学 院课程设计任务书课程设计题目：课程设计题目： 文章编辑文章编辑 系系

6、别别 信息工程系信息工程系 班级班级 计本计本 091091 学生姓名学生姓名 姚大州姚大州 朱思坤朱思坤 学号学号 2121 1212 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师课程设计进行地点：课程设计进行地点： 实训实训 F F 座座 任任 务务 下下 达达 时时 间：间： 20102010 年年 1212 月月 2727 日日起止日期：起止日期：20102010 年年 1212 月月 2727 日起日起至至 20112011 年年 1 1 月月 7 7 日止日止教教研研室室主主任任 张欣张欣 2 20 01 10 0 年年 1 12 2 月月 2

7、27 7 日日批批准准一、课程设计的原始资料及依据在现今社会中，越来越多的人们意识到读书的益处，因此，涌现出大量的好文章。这时，文章编辑工具便起到了很好的帮助作用。根据数据结构的原理应用 C 语言制作文章编辑的程序需要统计文章中的所有文字信息，需要分行显示，处理起来虽然不是很复杂却设计到很多方面，需要使用链表来存储文章。查阅有关程序设计的案例资料，进一步理解程序设计模块化的思想，并利用此思想，根据对程序设计学习编写一个简单的文章编辑系统。二、课程设计主要内容及要求1. 分别统计出其中英文字母数和空格数及整篇文章总字数。2. 统计某一字符串在文章中出现的次数，并输出该次数。3. 删除某一子串，并

8、将后面的字符前移，并输出删除后的文章。4. 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，

9、哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋体小四号字，行间距 18 磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间

10、进度安排顺序阶段日期计 划 完 成 内 容备注1第 1 天（12 月 27 日）阅读资料2第 23 天（12 月 28 日12 月 30 日）系统分析设计3第 48 天（12 月 31 日1 月 5 日）程序编制、调试及运行4第 9 天（1 月 6 日）成绩评定5第 10 天（1 月 7 日）撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C 语言版）. 北京:清华大学出版社.20072谭浩强.C 程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.20

11、05.055李春葆.数据结构（C 语言版）习题与解析.北京:清华大学出版社.2002.04沈沈 阳阳 工工 程程 学学 院院程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本091091 学生姓名：学生姓名： 张小军张小军 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满

12、完成规定的设计任务，工作量饱满，难度适宜。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

13、说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主

14、要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈沈 阳阳 工工 程程 学学 院院程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本091091 学生姓名：学生姓名： 姜志兴姜志兴 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课

15、程设计方案和日程安排。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） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评

16、价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表

17、达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈沈 阳阳 工工 程程 学学 院院程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本0

18、91091 学生姓名：学生姓名： 姚大州姚大州 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩指导教师评审成

19、绩（加权分合计乘以（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评

20、 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成

21、成 绩绩分分沈沈 阳阳 工工 程程 学学 院院程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本091091 学生姓名：学生姓名： 朱思坤朱思坤 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书

22、的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩指导教师评审成绩（加权分合计乘以（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符

23、号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩

24、答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈阳工程学院课程设计报告 摘要摘摘 要要数据结构与算法在计算机学科中的地位十分重要，是设计系统程序和大型应用程序的重要基础。数据结构和算法课程是计算机科学及其相关专业的一门核心课程，本课程的学习将为我们以后后续的操作系统、数据库、编译技术等专业基础课和专业课程的学习，以及软件设计水平的提高打下良好的基础。本课程的学习过程是一个复杂程序设计的训练过程，我们所要编写的程序要结构清楚和正确易读，符合软件工程的规范。我

25、们进行课程设计的目的是要掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。算法的实现是课程设计的灵魂，也就是我们学习设计的重中之重。算法的设计靠的不是语法规则，而是解题的思路。所以在开始设计前，我们要掌握好课本的基本内容，并且查阅一系列的课外资料，锻炼我们设计算法的思路。本次数据结构课程设计校园导航这个题目，在存储方式上是运用了图的邻接矩阵存储结构，同时在编写程序中使用的基本操作有建立有向网、输入起点和终点、输出该路线（包含路过哪些建筑）及其总行进时间，在编写程序的过程中遇到了许多问题。例如：如何判断起点和终点之间没有路径，两结点相同时该如何处理等一系列问题，但经过讨论和

26、改正，使程序达到预期的要求。在文章编辑中，使用链表来存储文章。利用模块化设计思想，主要实现的功能有：统计某一字符串在文章中出现的次数，并输出该次数、删除某一子串，并将后面的字符前移，并输出删除后的文章。经过讨论和修正以及老师耐心的指导使文章编辑系统不断完善。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词关键词 链表，有向网，邻接矩阵沈阳工程学院课程设计报告 目录目录摘摘 要要.I I第一章第一章 问题分析问题分析.1 11.1 引言 .11.2 背景.11.3 分析 .11.3.1 校园导航系统 .11.3.2 文章编辑系统 .2第二章第二章 原理与运行环境原理与运行环境.

27、3 32.1 数据结构理论 .32.1.1 校园导航系统数据结构理论 .32.1.2 文章编辑系统数据结构理论 .32.2 运行环境 .42.2.1 打开方法.42.2.2 打开 CodeBlocks 中的 C 环境 .42.2.3 源程序的建立与编辑、连接.5第三章第三章 系统分析与设计系统分析与设计.6 63.1 校园导航分析与设计 .63.1.1 系统的功能 .63.1.2 系统模块分析及其流程图.63.2 文章编辑系统分析与设计 .83.2.1 文章编辑系统的功能 .83.2.2 系统模块分析及其流程图 .9第四章第四章 系统功能实现系统功能实现.13134.1 校园导航系统功能实现

28、.134.1.1 定义主函数 .134.1.2 定义存储结构 .154.1.3 构建有向网.154.1.4 调用迪杰斯特拉算法.164.2 文章编辑功能实现 .184.2.1 定义主函数 .184.2.2 定义存储结构 .204.2.3 初步统计功能 .214.2.4 统计字符串功能 .244.2.5 删除字符串功能.25结论结论.2727致谢致谢.2828参考文献参考文献.2929沈阳工程学院课程设计报告 第一章问题分析0第一章 问题分析1.1 引言数据结构的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时

29、间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别

30、是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课程设计主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。通过本次课程设计，相信我们一定能加强对数据结构这门课程的学习，尤其在动手实践上会有很大的进步。1.2 背景随着全国各大高校不断地扩建以及建筑的增加，当我们参观某校园时，找到一条从当前位置到另外某个位置的路径是最省时的，并把该路径上都有哪些建筑输出的问题愈加凸显现出来。所以设计一个校园导航系统是很实用和必要的。在现今社会中，越来越多的人们意识到读书的益处，因此，涌现出大量的好文

31、章。而文章编辑人员需要随时了解文章文本的相关信息。因此，编写一个文章编辑系统是有非常必要的，为相应编辑需求特开发此文章编辑系统。文章编辑需要统计文章中的所有文字信息，需要分行显示，处理起来虽然不是很复杂却设计到很多方面，需要使用链表来存储文章。1.3 分析1.3.1 校园导航系统校园导航系统运用的是有向网的邻接矩阵表示方法。将校园景点作为图的结点，将景点间的路径作为图的边，路径行进时间作为边的权值。这样一来，求两景点间行进最短时间的问题就抽象成了求图中一结点到另一结点的问题。校园导航适合用有向网，方便校园景点的储存以及景点间路径行进时间的储存。一个景点是一个顶点，如果两顶点间有路径则该边的权值

32、为它们的行进时间否则为无穷大。校园导航系统分为三个大部分，分别为建筑相关信息的读入，利用迪杰斯特拉算法求解沈阳工程学院课程设计报告 第一章问题分析1给定顶点对之间最短行进时间的路径，输出所找到的最短行进时间的路径。建筑相关信息的读入，当地图文件满足条件时，系统会从地图文件中读取建筑数目，建筑间的行进时间数据，建筑名称及有路径存在的建筑信息，形成图的邻接矩阵。建筑间的行进时间的信息相当于顶点间边的权值，构造有向网络。当两建筑间无直接路径时，用整型最大值代表正无穷大。利用迪杰斯特拉算法求解给定顶点对之间最短行进时间，首先要对求解到的顶点集 U 和待求解的顶点集 V-U 及最短路径结构数组进行初始化

33、，首先录入要然后在 V-U 顶点集中找到最短路径的顶点 u 降至并入顶点集 U 中，并从顶点集 V-U 中删除 u，接下来依次调整到顶点V-U 中每个顶点的当前最短路径值；直到 V=U 为止。主函数，主函数是程序的入口，先对有向网络进行初始化，在调用迪杰斯特拉算法求解给定顶点对之间最短行进时间，并将结果保存到最短路径数组中。找到路径上的各个顶点及顶点间的距离并输出。 1.3.2 文章编辑系统文章编辑系统运用的数据结构是线性表中的单链表。单链表是多个数据元素的有限序列，至于每个数据元素的具体含义，在不同的情况下各不相同，他可以是一个数或是一个符号等等。文章编辑适合用单链表，其方便随时进行对相应的

34、字符进行查找统计和删除相应的字符，实现动态管理。其中每一个节点当中包括两方面信息，分别为字符数据信息和此数据的后继结点信息。该节点类型为结构体，结构体中的域表示字符的相应属性。文章编辑系统分为三个大模块，分别为初步统计功能、统计字符串出现次数模块以及删除字符串模块。在进行统计字符串出现次数模块和删除字符串模块是，文章编辑系统中会调用一些系统默认函数。在函数的开始阶段，系统会执行创建链表函数。在这个过程中，需要用户进行录入操作，即输入要统计的文章文本。当完成录入工作后，文章编辑系统会继续调用输出文章文本函数对所输入的信息进行输出。之后，此系统继续调用统计字母函数来统计所输入文本当中字母的个数；继

35、续调用统计数字函数来统计所输入文本当中数字的个数；继续调用统计空格函数来统计所输入文本当中空格的个数；继续调用统计文本总字数函数来统计所输入文本当中所有字符的个数。统计字符串出现次数功能，首先要输入要统计的字符串，然后判断要统计的字符串的第一个字符是否在文本当中出现。若有出现，再比较后面字符串与文本当中的是否匹配，若匹配成功，使计数器加一。以此类推，直到遍历完整个链表为止，并返回计数器的值。这个值即为该字符串在此文本当中出现的个数。删除字符串功能，首先要输入要删除的字符串，然后判断要删除的字符串的第一个字符是否在文本当中出现。若有出现，再比较后面字符串与文本当中的是否匹配，若匹配成功，便通过对

36、文章文本的地址进行操作，从而删除该字符串。沈阳工程学院课程设计报告 第二章原理与运行环境2第二章第二章 原理与运行环境原理与运行环境2.1 数据结构理论2.1.1 校园导航系统数据结构理论图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集合组成。它可以定义为一个二元组：G=(V,E)其中，G 表示一个图，V 表示图 G 中全部顶点组成的非空集合，E 是图 G 中全部边组成的集合。按照图中边是否有方向性，图分为有向图和无向图两类。图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight） 。如果每一条边都有与它相关的数，称为权，我们将这种带权的图叫做网。如果图中边是

37、无方向的带权图，则图是一个无向网；如果图中边是有方向的带权图，则就是一个有向网。在本系统中我们使用的是有向网的邻接矩阵存储结构以及其相关的应用。校园导航系统应用的是有向网的邻接矩阵存储结构，有向网的邻接矩阵存储结构的特点：用邻接矩阵可以很方便的表示出顶点的信息以及顶点间的相邻关系，可以很方便地从有向图邻接矩阵中得到从某一建筑出发到其它建筑有没有路径，如果有路径则可以得到它们之间的行进时间。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。我们将任务分成多个最简化的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。在校园导航系统中，有向网邻接矩阵数据结构中有保存顶

38、点个数的整型变量，顶点信息的一维字符数组以及保存边信息的整型二维数组；保存最短路径上结点的数据结构有保存最短路径长度、前一个顶点的整型变量。 读取功能：读取是将地图文件中的信息读取到有向网中。查找功能：对于给定的起点和终点利用迪杰斯特拉算法找到最省时的路径。输出功能：将找到路径上的各个顶点及顶点间的距离并输出。2.1.2 文章编辑系统数据结构理论链接方式存储的线性表简称为链表。 链表是一种动态存储结构，所占用的存储空间在程序的执行过程中得到，当线性表需要增加一个结点时，要为该结点向系统申请一个存储空间。当线性表删除一个结点时，要将已删除的结点的存储空间释放，归还给系统。每个存储结点不仅包含有所

39、存储元素本身的信息（称之为数据域） ，而且包含所有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息（这称为指针域） ，这样可以通过前驱结点的指针域方便地找到后继结点的位置，提高数据查找速度。文章编辑管理系统应用的是链式线性表存储结构，线性表的链式存储结构的特点：是用一组任意的存储单元存储线性表的数据元素。数据元素的映象用一个结点来表示。结点的一个域表示元素本身，另一个是能指示其后继的指针，用来表示线性表数据元素的逻辑关系。但失去了顺序表的可随机存取特点。我们将任务分成多个最简化的模块，增强了可读性和简单性，同时为日后的编写，调试，维护提供了极大地方便。其方便随时进行对相应的字符进沈阳

40、工程学院课程设计报告 第二章原理与运行环境3行查找统计和删除相应的字符，实现动态管理。在文章编辑系统中，适合用单链表，其中每一个节点当中包括两方面信息，分别为字符数据信息和此数据的后继结点信息。该节点类型为结构体，结构体中的域表示字符的相应属性。其中，数据的形式和范围可以输入大写、小写的英文字母、任何数字及标点符号。初步统计功能：分别统计出其中英文字母数、数字数、空格数以及整篇文章文本总字数。统计字符串功能： 统计所输入的字符串在文章文本当中出现的次数，并显示出来。删除字符串功能：在文章文本当中删除所输入的字符串，完成删除后，显示出删除文本中第一次该字符串后的文本。2.2 运行环境在数据结构程

41、序的运行环境为 CodeBlocks 中的 Console application 的 C 环境。2.2.1 打开方法开始所有程序CodeBlocks 如图 2-1 所示。图 2-1 打开CodeBlocks的方法2.2.2 打开 CodeBlocks 中的 C 环境其工作环境如图 2-2 所示。沈阳工程学院课程设计报告 第二章原理与运行环境4图 2-2 C CodeBlocks 中的 Console application 的 C 环境 CodeBlocks 中的 Console application 的 C 环境的材料如下：CodeBlocks 中的 Console applicatio

42、n 的 C 环境可以划分为三块区域。最左边的区域是工作区，最下面的区域是输出区，最右边的区域是编辑区。编辑区用来对原文件进行编辑，现在的编辑区是天蓝色的，表示等待源文件进行编辑。输出区的作用是对程序进行编译和链接后，如果程序有错误或警告，则显示在输出区。工作区的作用是用来管理各种源程序文件，在它的管理下，可以有条不紊的进行各种源文件的编辑。 总体来讲，CodeBlocks 中的 Console application 的 C 环境运行环境方便快捷。2.2.3 源程序的建立与编辑、连接建立 C 语言源程序文件。建立方法：选择“CodeBlocks” “Console application” “

43、C” “Project title” “Finish” 。程序的编辑与编译。编辑完成后，选择菜单栏中的“build”即可对程序进行编译。当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，当然有时提示位置不一定很准确。程序的执行。单击工具栏上的“深蓝色三角号”按钮，即可执行刚编写的程序，如图2-3 所示。图 2-3 对源程序进行编写沈阳工程学院课程设计报告 第三章系统分析与设计5第三章 系统分析与设计3.1 校园导航分析与设计3.1.1 系统的功能本次任务要求实现校园导航系统，根据

44、需要可以进行如下操作：构建有向网、调用迪杰斯特拉算法、输出。其功能模块图如图 3-1 所示校园导航系统构建有向网调用迪杰斯特拉算法输出图 3-1 校园导航功能模块图3.1.2 系统模块分析及其流程图主函数先对有向网络进行初始化，再调用迪杰斯特拉算法求解给定顶点对之间最短行进时间，并将结果保存到最短路径数组中并输出。主函数流程图，如图 3-2 所示。图 3-2 主函数流程图开始从地图文件中读取数据形成图的邻接矩阵调用迪杰斯特拉算法输出找到的路径结束沈阳工程学院课程设计报告 第三章系统分析与设计6构建有向网根据地图文件信息，读入图的顶点个数、顶点信息，初始化邻接矩阵，如果两个顶点间有路径则赋权值为

45、其行进时间。在读取完成后，关闭地图文件。其构建有向网流程图如图如图 3-3 所示。开始定义变量读入数据初始化邻接矩阵是否两建筑是否在网中利用迪杰斯特拉算法求最短行进时间迪杰斯特拉（DijkStra）算法求最短行进时间的实现思想是：设图 G=（V，A）其中，V=0，1，2，3n,如果结点 i,j 存在路径, G-arcsij的权为其行进时间否则 G-arcsij的权为无穷大(这里取值为 32767)。设 dist 是一个集合,其中的每个元素表示一个顶点,从源点到这些顶点的最短路径已经求出。设起点所对应的编号为 start,集合 dist的初态只包含顶点 start。数组 disti.len 记录

46、从起点到其他各个场所顶点当前的最短距离,其初值为 disti.len=G-arcsstarti,i=0,1,2,n。从 dist 之外的顶点集合 V-dist 中选出一个顶点 w,使 Di的值最小。于是从原点到达 w 只通过 dist 中的顶点,把 w 加入集合 dist 中,调整 dist 中记录的从单原点到 V-dist 中每个顶点 i 的距离:从原来的disti.len 和 distmin.len+ G-arcsmini中选择较小的值作为新的 disti。重复上述过程,直到 dist 中包含 V 中其余顶点的最短路径。其算法流程图如图 3-4 所示。赋权值结束读取错误图 3-3 构建有向

47、网流程图沈阳工程学院课程设计报告 第三章系统分析与设计7最终结果是:S 记录了从原点到该顶点存在最短路径的顶点集合,数组 distv记录了从原点到 V 中其余各顶点之间的最短路径顶点,path 最短路径的路径数组,其中 pathi表示从原点到顶点 i 之间的最短路径的前驱顶点。开始建立并置空最短路径终点集合数组建立并置初始最短路径值将源点入终点集，源点到源点的距离为 0从第二个结点开始是否循环至最后结点？是循环查找路径最小结点，将最小结点入终点集合HHEHE 合比较并替换最短路径值执行下一结点否输出该点到所有结点的最短路径结束图 3-4 迪杰斯特拉算法流程图3.2 文章编辑系统分析与设计3.2

48、.1 文章编辑系统的功能本课程设计任务要求实现文章编辑系统。根据需要可以进行如下操作：初步统计功能、统计字符串出现次数功能、删除字符串功能。其功能模块图如图 3-5 所示。沈阳工程学院课程设计报告 第三章系统分析与设计8 图 3-5 文章编辑系统功能模块图3.2.2 系统模块分析及其流程图文章编辑的主函数先对输入的文本进行初步统计，再分别调用查找和删除函数对输入的字符串进行统计和删除操作。其流程图如图 3-6 所示。开始输出主界面提示词输入文章文本输出文章的总字数、空格数、数字数相关信息对输入的文章文本进行相关统计文章编辑系统统计字符串功能初步统计功能删除字符串功能创建单链表统计文章字母数统计

49、文本数字数统计文本空格数统计文本总字数1沈阳工程学院课程设计报告 第三章系统分析与设计9图 3-6 主函数流程图初步统计功能初步统计功能是将文本当中的字母数、数字数、空格数以及文本总字数这些基本信息统计出来，其流程图如图 3-7 所示。 图 3-7 初步统计功能流程图是否进行删除操作是对输入的字符进行删除操作输出字符出现次数结束对输入的字符进行统计操作否输出删除相应字符后的文本 开始输入文章文本统计输入文本当中的字母数统计输入文本当中的数字数统计输入文本当中的空格数统计输入文本当中的总字符数数输出以上文章文本基本信息结束1沈阳工程学院课程设计报告 第三章系统分析与设计10统计字符串功能删除字符

50、串功能就是在文章文本当中删除所输入的字符串，完成删除后，显示出删除文本中第一次该字符串后的文本。 统计字符串功能就是统计所输入的字符串在文章文本当中出现的次数，并显示出来，其功能流程图如图 3-8 所示。图 3-8 统计字符串功能流程图删除字符串功能删除字符串功能就是在文章文本当中删除所输入的字符串。完成删除后，显示出删除文本中第一次该字符串后的文本，其功能流程图如图 3-9 所示。开始输入要统计的字符串从文章文本头地址起遍历链表字符串的首字符是否在文中出现文本中是否有与之匹配的字符串计数器加一链表是否遍历完成输出计数器的值结束是否是是否否沈阳工程学院课程设计报告 第三章系统分析与设计11图

51、3-9 删除字符串功能流程图开始输入要删除的字符串字符串的首字符是否在文中出现文本中是否有与之匹配的字符串对文本当中与之匹配的字符串进行删除操作从文章文本头地址起遍历链表整合删除第一个与之匹配字符串后的地址输出删除字符串后的文本结束是是否否沈阳工程学院课程设计报告 第四章系统功能实现12第四章第四章 系统功能实现系统功能实现4.1 校园导航系统功能实现4.1.1 定义主函数主函数是程序的入口，采用模块化设计，首先声明一些必要的变量，然后调用 Init 函数创建有向网，再调用迪杰斯特拉算法函数进行操作，输出所求到的最省时的路径，退出系统。源代码如下：int main (int argc,char

52、 *argv) GraphMatrix graph; ShortPath pathMAXVEX; int tmp,cnt=0,pre=-1; int temppathMAXVEX; int m,n; VexType va,vb; long totallen=0; long curlen=0; Init(&graph); printf(n 请输入您要查询的起点和终点n); scanf(%s%s,va,vb); m=LocateVex(&graph,va); n=LocateVex(&graph,vb); if (m!=-1&n!=-1) Dijkstra(&

53、;graph,path,m); for (tmp=0;tmpMAXVEX;tmp+) temppathtmp=-1; pre=n; while (pathpre.pre!=-1) temppathcnt=pre; pre=pathpre.pre; cnt+; temppathcnt=m; if (cnt%s 无路可走n!,graph.vexsm,graph.vexsn); else printf(您输入的顶点重合); else tmp=cnt; printf(%s-,graph.vexstemppathtmp); for (;tmp0;tmp-) printf(%s(%d)-,graph.ve

54、xstemppathtmp-1, graph.arcstemppathtmp temppathtmp-1); totallen+=graph.arcstemppathtmp temppathtmp-1; printf(共：%dn,totallen); else printf(%s%s)中有不存在的建筑，请您仔细检查!,va,vb); return 0;功能实现图如图 4-1 所示。图 4-1 初始化界面沈阳工程学院课程设计报告 第四章系统功能实现144.1.2 定义存储结构首先需要定义有向网的顶点名称为字符数组，边的权值为整型。具体代码如下：#include#include#include#d

55、efine MAXVEX 30#define MAXNAME 20#define INT_MAX 32767typedef char VexType MAXNAME;在有向网邻接矩阵数据结构 GraphMatrix 的基础上，还需要定义保存最短路径上结点的数据结构 ShortPath。具体代码如下：typedef struct int n; VexType vexs MAXVEX; AdjType arcs MAXVEXMAXVEX; GraphMatrix;typedef struct AdjType len; int pre; ShortPath;4.1.3 构建有向网初始化，从包含建筑及

56、建筑之间行进时间信息的地图文件中读取相关信息。具体代码如下：void Init(GraphMatrix*g) int i,j,k,w; int edgeNums; VexType va,vb; FILE * graphlist; graphlist=fopen(campusnav.txt,r); fscanf(graphlist,%d,&g-n); fscanf(graphlist,%d,&edgeNums); for(i=0;in;+i) fscanf(graphlist,%s,g-vexsi); for (i=0;in;+i) 沈阳工程学院课程设计报告 第四章系统功能实现1

57、5 for (j=0;jn;+j) g-arcsij=INT_MAX; for (k=0;karcsij =w ; else printf(%s%s 读取错误，请您仔细检查！,va,vb); for (i=0;in;i+) g-arcsii=0; fclose(graphlist); 4.1.4 调用迪杰斯特拉算法利用迪杰斯特拉算法求解给定顶点对之间最短行进时间。具体代码如下：void Dijkstra (GraphMatrix *pgraph,ShortPath dist,int start) int i,j,min; AdjType minw; dist start.len=0; dist

58、 start.pre=0; pgraph-arcsstartstart=1; for (i=0;in;i+) disti.len!=pgraph-arcsstarti; if (disti.len!=INT_MAX) disti.pre=start; else disti.pre=-1; diststart.pre=-1; for (i=0;in;i+) minw=INT_MAX; min=start;沈阳工程学院课程设计报告 第四章系统功能实现16 for (j=0;jn;j+) if (pgraph-arcsii=0)&(distj.lenarcsminmin=1; for (j=

59、0;jn;j+) if (pgraph-arcsjj=1) continue; if (distj.lendistmin.len+pgraph-arcsminj&distmin.len+pgraph-arcsminj0) distj.len=distmin.len+pgraph-arcsminj; distj.pre=min; 功能实现图如图 4-2 所示。图 4-2 功能实现图沈阳工程学院课程设计报告 第四章系统功能实现174.2 文章编辑功能实现4.2.1 定义主函数主函数是程序的入口，采用模块化设计，首先声明一些必要的变量，并为单链表头指针分配空间；然后调用 Creat 函数创建

60、单链表，输出文章文本。此时，单链表便不为空；调用CountLetter 函数进行统计文章文本当中字母数的操作；调用 CountNumber 函数进行统计文章文本当中数字数的操作；调用 CountSpace 函数进行统计文章文本当中空格数的操作；调用 CountAll 函数进行统计文章文本当所有字符数的操作；初步基本信息统计完成后，再根据选择进行统计字符串出现次数操作和删除字符串操作。其主函数源代码如下：int main() char ch; LINE *head; char str120,str220; int letter,number,space,all,countstr1; int choose; Create(head); printf(文章为：n); OutPut(head); lette