[工学]数据结构课程设计报告.doc

沈 阳 工 程 学 院课 程 设 计设计题目： 数据结构及算法的设计与实现 系 别 信息系 班级 计本081 学生姓名 李城龙 学号 2008412109 指导教师 职称 起止日期：2009年12月28日起至2010年1月8日止VI沈 阳 工 程 学 院计算机组成原理课程设计成绩评定表系（部）： 信息工程系 班级： 计本081 学生姓名： 李城龙 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评 阅 教 师 签 名： 年 月 日答 辩 小 组 评 审 意 见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55432答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名： 年 月 日数据结构课程设计任务书一、设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类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.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。2.编码，利用建好的huffman树生成huffman编码；3.输出编码；4.译码功能；5.字符和频度如下：字符 空格 A B C D E F G H I J K L M N O P Q频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1字符 R S T U V W X Y Z频度 48 51 80 23 8 18 1 16设计题目二 文章编辑设计要求功能：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；设计题目三 利用Hash技术统计C源程序中关键字的频度设计要求一、任务描述扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的度。用线性探测法解决Hash冲突。设Hash函数为：Hash(Key)=(Key的首字母序号)*100+(Key的尾字母序号) Mod 41。关键字39个，参考C语言教材。二、数据结构设计关键字表的存储结构；Hash表中的结点结构。频度、冲突次数 三、功能设计从一个大字符串中分解单词识别是否是关键词；用哪种方法：有序表查找、二叉查找树？Hash函数，解决冲突，统计冲突次数。key = 地址插入Hash表，或调整Hash表项中的频度输出Hash表，关键词总数，冲突次数自己想象，功能要多，设计要合理。设计题目四 设计实现利用普里姆算法构造最小生成树的程序.设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书进度安排设计工作4学时实现与调试12学时课程设计说明书4学时设计考核要求考勤20%课程设计说明书50%答辩30%五、参考书目1 佟伟光，杨政 实用数据结构（第二版） 科学出版社2 严蔚敏 数据结构（C语言版） 清华大学出版社3 李保春编著，数据结构习题与解析，清华大学出版 2001年第一版4 徐孝凯编著，数据结构课程实验，清华大学出版 2002年第一版5 张乃笑编著，数据结构与算法，电子工业出版社 2004年10月6 王卫东编著，数据结构辅导课，西安电子科技大学出版社 2001年7 陈文博 朱青著，数据结构与算法，机械工业出版社 1996年8 赵文静等编，数据结构辅导，西安交通大学出版社 1999年沈阳工程学院课程设计（报告） 摘要摘 要 “数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重.点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词 ：线性表，栈和队列，二叉树，图，查找，排序VII 目录数据结构及算法课程设计成绩评定表I课程设计任务书.III摘 要.VII第一章 哈夫曼编译码器.11.1 问题分析.11.2 数据结构与算法分析.11.3 核心代码.31.4 运行结果8第二章 文章编辑101.1 问题分析.101.2 数据结构与算法分析101.3 核心代码121.4 运行结果17第三章 利用Hash技术统计C源程序中关键字的频度.191.1 问题分析191.2 数据结构与算法分析191.3 核心代码211.4 运行结果32第四章 设计实现利用普里姆算法构造最小生成树的程序341.1 问题分析.341.2 数据结构与算法分析.341.3 核心代码.351.4 运行结果.39总 结40致 谢41参考文献42沈阳工程学院课程设计（报告） 第二章 文章编辑第一章 哈夫曼编译码器当今社会，计算机技术和通信技术已不断发展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。1.1 问题分析在程序的运行过程中，我们小组遇到了一些问题：不知该用哪种方法、按什么样的顺序查找各个结点。如何建立哈夫曼树，怎样能最简单的通过主函数去逐步调用其他各个函数以达到题目的要求。如何利用建好的huffman树生成huffman编码及如何实现译码功能。通过查找资料我们解决了所有问题，构造哈夫曼树时，首先将由n各字符形成的n个叶子节点存放到数组HTNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树，每次构成的新子树的根节点顺序放到HTNode数组中的前n个分量的后面。译码功能，假定电文中只使用A、B、C、D、E、F6种字符，若进行等长编码，它们分别需要3位二进制字符，可一次编码为000、001、010、011、100、101。1.2 数据结构与算法设计哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。其主要流程图如图1-1所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是图1-1 哈夫曼树编译码器流程图1.3 核心代码哈夫曼编译码器程序的主要代码如下所示:#include #include /要用system函数要调用的头文件#include /用getch()要调用的头文件#include #define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，当flag为0时跳出循环 printf(n); printf( ); printf(n A-显示编码 ); printf(n B-进行编码 ); printf(n C-进行译码 ); printf(n D-退出 n); printf( ); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case b: case B: system(cls); printf(请输入要进行编码的字符串(以#结束):n); editHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); printf(请输入编码(以#结束):n); deHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 1.4 运行结果下面是程序的运行结果：1. 第一步运行程序为进入主菜单，如下图1-2所示。图 1-2 主菜单界面2. 第二步输入编号A显示编码，输出结果如下图1-3所示。图1-3 输出哈夫曼编码界面3. 第三步返回主菜单后输入B进行编码，输入“LeonLee#”回车后显示编码，界面如图1-4所示。图1-4 编码界面4. 第四步返回主菜单后输入C进行译码，输入“01100101110001100111000#”，回车后显示译码，界面如图1-5所示。图1-5 译码界面第二章 文章编辑文章编辑需要统计文章中的所有文字信息，需要分行显示，处理起来虽然不是很复杂却设计到很多方面，需要使用链表来存储文章。2.1 问题分析功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求： 分别统计出其中英文字母数和空格数及整篇文章总字数。 统计某一字符串在文章中出现的次数，并输出该次数。 删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能。输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式： 分行输出用户输入的各行字符。 分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”。 输出删除某一字符串后的文章。在编辑过程中，遇到的问题有对字符的统计过程中需要用ASCII码，在自已开始直接用的是字母或者数字。不知道怎么结束文章输入操作，最后在查找ASCII码时发现可以用ASCII码中的end控制符结束文章的输入。2.2 数据结构与算法设计文章编辑程序的主要功能是统计文章中的全部字母数、数字个数、空格个数和文章总字数，并且能准确的查找、删除字符串。主要应用的函数和语句有循环，查找，删除等。由程序开始运行后进行字符串的录入，之后进行字符的输出，然后是利用循环和查找，进行字符的统计并输出已经找到的字符（包括字母、数字、空格）出现的次数以及总共的字符数。在这些运行完之后，根据要求还有一项功能-删除，对指定的字符进行删除，同样，这里也需应用到循环，查找和删除。其主要流程图如图2-1所示。是是是开始ID=1Create()ID=2output()ID=3Count()ID=4FindString()ID=5delstringword()ID=66输出breakoutput ()否否是否否否main()输出菜单输入IDWhile(1)退出是图 2-1 文章编辑流程图2.3 核心代码文章编辑程序代码如下：#include#include#include#define LEN sizeof(struct line)typedef struct linechar *data; /文本每行以字符串形式存储，行与行之间以链表存储 struct line *next;LINE;/创建一链表，同时向里面输入文本数据void Create(LINE * &head)char tmp100;LINE *p;p=(struct line *)malloc(LEN); /开辟一个LINE结构体类型的空间，并把头地址给p head=p; /将p赋给 表头指针printf(请输入文本，以Ctrl+E(E)为结尾，每行最多输入80字符！n); /ASCII码中第5个 end结束符 while(1) gets(tmp); /输入字符串！ if(strlen(tmp)80) printf(每行最多输入80字符); break; if(tmp0=5) break; /如果一开始发现输入 E，则退出输入 p=p-next=(struct line *)malloc(LEN); /新的一行 重新开辟空间 p-data=(char *)malloc(strlen(tmp); /为结点分配空间 strcpy(p-data,tmp); if(tmpstrlen(tmp)-1=5) /除去最后一个控制符 E，并且退出 p-datastrlen(tmp)-1=0; break; p-next=NULL; /最后的一个指针为空。 head=head-next;/统计字母数int CountLetter(LINE * &head)LINE *p=head;int count=0;do int Len=strlen(p-data); /计算当前 data 里的数据元素的个数 for(int i=0;idatai=a&p-dataidatai=A&p-datainext)!=NULL); /下一个节点不为空return count; /返回文章的字母总数/统计数字数int CountNumber(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p-data); /计算当前 data 里的数据元素的个数 for(int i=0;idatai=48 & p-datainext)!=NULL); return count;/统计空格数int CountSpace(LINE * &head) LINE *p=head; int count=0; do int Len=strlen(p-data); /计算当前 data 里的数据元素的个数 for(int i=0;idatai=32)count+; /根据空格的ASCII码值计算个数 while(p=p-next)!=NULL); return count;/统计文章的总字数int CountAll(LINE * &head) LINE *p=head; /保存链表的首地址 int count=0; do /计算总字符数 count=count+strlen(p-data); while(p=p-next)!=NULL); /遍历 链表 return count;/统计str在文章中出现的次数int FindString(LINE * &head,char *str) LINE *p=head; int count=0; int h=0; int len1=0; /保存当前行的总字符数 int len2=strlen(str); /待统计字符串的长度 int i,j,k; do len1=strlen(p-data); /当前行的字符数for(i=0;idatai=str0)k=0; for(j=0;jdatai+j=strj) /与输入的字符串进行比较相同的就k加1k+;if(k=len2) /若K与字符串的长度相等count+;i=i+k-1; /跳过找到的字符串继续找 while(p=p-next)!=NULL); return count;/删除指定的字符串void delstringword(char *s,char *str) / *s为输入的字符串，*str为将要删除的字符 char *p=strstr(s,str); /从字符串s中寻找str第一次出现的位置 char tmp80; int len=strlen(s); int i=len-strlen(p); int j=i+strlen(str); int count=0,m,n; for(m=0;mi;m+)tmpcount+=sm; /把删除字符串的前面字符串给数组tmp for(n=j;ndata,str)!=NULL) /这一行中有匹配的字符串delstringword(p-data,str);while(p=p-next)!=NULL); /遍历 链表/向屏幕输出文章void OutPut(LINE * &head) LINE *p=head; do /按行输出文章 printf(%sn,p-data); while(p=p-next)!=NULL); /下一个节点不为空，符合条件则输出下一行/主函数int main()LINE *head;char str120,str220;int letter,number,space,all,countstr1;Create(head);printf(文章为：n);OutPut(head);letter=CountLetter(head);printf(n全部字母数：%d,letter);number=CountNumber(head);printf(n数字个数：%d,number);space=CountSpace(head);printf(n空格个数: %d,space);all=CountAll(head);printf(n文章总字数: %d,all);printf(n请输入要统计的字符串:);scanf(%s,str1);countstr1=FindString(head,str1);printf(%s出现的次数为:%d,str1,countstr1);printf(n请输入要删除的某一字符串：);scanf(%s,str2);DelString(head,str2);printf(删除%s后的文章为：n,str2);OutPut(head); printf(n谢谢使用!n);2.4 运行结果以下是文章编辑程序的运行结果：1. 第一步按提示输入如下文章“everyone has a great dream in his heart,what we should do is that try our best.E”输出统计的各种信息，输出界面如图2-2所示。图2-2 输入文章信息2. 第二步输入要统计的特定字符串，如下图2-3所示。图2-3 统计特定字符串3. 第三步输入要删除的字符，回车后显示删除完指定字符的文章，显示界面如图2-4所示。图2-4 删除字符1沈阳工程学院课