数据结构》课程设计

1、精品文档 沈 阳 工 程 学 院课 程 设 计 课程设计题目： 数据结构与算法课程设计 系 别 信息工程学院 班级 物联本 学生姓名 许 学号 2 指导教师 职称 讲师 任 务 下 达 时 间： 2021 年 6 月 24 日起止日期：2021年6月24日起至 2021年 7 月5日止 沈 阳 工 程 学 院 课程设计任务书 设计题目：写出图的广度优先搜索算法的非递归算法 哈夫曼编码系 别 信息工程学院 班级 物 21 学生姓名 许 学号 2 指导教师 职称 讲师 任 务 下 达 时 间： 2021 年 6 月 24 日起止日期：2021年6月24日起至 2021年 7 月5日止 欢迎下载精品

2、文档一、课程设计的原始资料及依据数据结构与算法课程设计是在完成数据结构理论课程学习之后进行的一个综合性的实践教学环节，是对课程理论和课程实验的一个补充。通过课程设计，培养学生综合运用已学过的理论和技能去分析和解决实际问题的能力，并使所学知识得到进一步稳固、深化和扩展。二、课程设计主要内容及要求设计内容：1、 写出图的广度优先搜索算法的非递归算法。2、 哈夫曼编码l 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。这就要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完成的

3、编译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。l 根本要求：1. 初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。 2. 编码。利用已建好的哈夫曼树,对正文进行编码。 3. 译码。对编码好的内容进行译码。 4. 打印编码。 设计要求：(1)每名同学任选三题；标号的题为选做题，完成有加分；(2)学生应明确设计任务和要求，并拟定设计方案，按时完成；(3)设计分阶段进行，每一阶段的设计没有原那么错误时才能允许进行下一阶段设计；(4)设计过程中，提倡独立思考、深入钻研，主动地、创造性地进行设计；(5)要求设计态度严肃认真、有错必改。三、对课程设计说明书撰写内容、格式、

4、字数的要求1课程设计说明书是表达和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、功能模块图、算法流程图等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结局部主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的方法以及今后的目标。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距1

5、8磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书中指定的功能，运行结果正确。2课程设计报告。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第1天阅读资料及系统分析设计2第2-5天程序编制3第6-7天程序调试4第8-9天成绩评定5第10天书写课程设计说明书六、主要参考资料文献1?数据结构?，清华大学出版社，2001，严蔚敏 吴伟民 2?数据结构题集?，清华大学出版社，1999，严

6、蔚敏 吴伟民 3?数据结构习题与解析?，清华大学出版社，2006，李春葆4?数据结构?，高等教育出版社，2006，许卓群5?数据结构习题解析?，清华大学出版社，2021，殷人昆 沈 阳 工 程 学 院数据结构与算法课程设计成绩评定表系部： 信息工程学院 班级： 物联本121 学生姓名： 许荣燊 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.254

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

8、 月 日 摘 要 “数据结构是一门专业技术根底课。它的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的标准。图作为数据结构的重要一局部，它的应用十分广泛。一方面由于很多实际问题跟图有关，例如通信线路、交通运输、集成电路布线图等；另一方面在于还有很多实际问题可间接地用图来表示，处理起来比拟方便，例如工程进度的安排等。图的遍历过程：假设从图中的某个顶点V出发，在访问V之后依次访问V的各

9、个未曾访问的邻接顶点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先访问的顶点的邻接点先于“后访问的顶点的邻接点被访问，直到图中所有已被访问的顶点的邻接点都被访问到。哈夫曼的优点：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。创立赫夫曼树之后，从树根开始标志赫夫曼码，赫夫曼码是由0和1所组成的，左子树填入0，右子树填入1，因此欲知每一个数据元素的赫夫曼树的方法为：对数据中出现过的每一个元素各自产生一树叶节点，并赋予树叶节点该元素的出现频率。令L是所有树叶节点所成之集合： 产生一个新节点N 令N为L1和L2的父亲节点L1 ，L2和L2是L中出现频率最低的俩

10、个节点。令N节点的出现频率等于L1和L2的出现频率总和。从L中删除L1和L2，并将N参加L中。标志树中各个节点的左子树衔接为0，右子树衔接为1。 关键词：广度，非递归，队列，树的构建，哈夫曼 欢迎下载精品文档第一章 问题分析1.1引言图是比树更为复杂的一种非线性数据结构，在图结构中，每个节点都可以和其他任何节点相连接，图结构可以描述复杂的数据对象。图有广泛的应用，一方面由于有很多实际问题与图有关，例如通信线路，交通线路，交通运输，集成电路布线图等；另一方面在于还有很多实际问题可以间接地用图来表示，处理起来比拟方便，例如工程进度的安排等。1.2背景数据结构一般包括以下三方面内容：数据的逻辑结构是

11、从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。1.3分析图是一种复杂的非

12、线形数据结构。在图中数据元素之间的联系是任意的，即任何两个顶点都可能存在邻接关系。图的存储方式主要有两种：邻接矩阵和邻接表，我们在此次课程设计时候选择邻接表作为图的存储方式。图的遍历就是从图的某一个顶点出发，访问图中每个顶点一次，切仅一次。如果采用非递归算法就需要用到一个栈。广度优先遍历是一种逐层横向搜索的过程。不是递归过程，算法设计时候需要一个队列。在无向图中，如果从顶点Vi到顶点Vj之间有路径，那么称这两个顶点是连通的。如过图中任意一对顶点都是连通的，那么称此图为连通图。此题目要求判断是否是连通图，根据邻接表的一些特性以及邻接表的概念。设计一个简单的算法可以判断是否是连通图了。 第二章 理

13、论与运行环境2.1 数据理论数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。链表是一种有序的列表，链表的内容通常是存储与内存中分散的

14、位置上。链表的方式有两种：一种是利用数组结构串连的有序列表。例如；两个数组，一个存放数据，另一个存放连接的关系。这种缺乏弹性。另一种以动态内存配置的链表，通常指的链表是一动态内存分配的链表动态内存配置的链表，是由许许多多的node所链接而成的，每一个结点，包含了数据局部和指向下一个结点的指针Pointer。以动态内存配置的链表，在插入和删除元素的时候，只需要将指针改变指向就可以。链表和数组一样是一种数据结构，如何使用完全基于你的应用需求。 链表和C+语言本身没有任何联系。很多语言都可以实现链表数据结构。 我讲一下数据和链表的区别有可能帮助你对链表的使用有个感觉。 数组是将元素在内存中连续存放，

15、由于每个元素占用内存相同，所以你可以通过下标迅速访问数组中任何元素。但是如果你要在数组中增加一个元素，你需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果你想删除一个元素，你同样需要移动大量元素去填掉被移动的元素。 链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比方：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果你要访问链表中一个元素，你需要从第一个元素开始，一直找到你需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了， 只要修改元素中的指针就可以了。 链表是指将假设干个数据项按

16、一定的规那么连接起来的表，其中的数据项成为结点。链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点，每个结点都应包括两个局部：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；，直到最后一个元素，该元素不再指向其它元素，它称为“表尾，它的地址局部放一个“NULL表示“空地址，链表到此结束。2.2 运行环境Visual C+ 6.0的工作环境可以划分为三块区域，最左边的区域是工作区，最下面的区域是

17、输出区，最右边的区域是编辑区。编辑区用来对源文件进行编辑，现在的编辑区是灰色的，表示还没有源文件在进行编辑，输出区的作用是对程序进行编译和连接后，如果程序有错误或者警告，那么显示在输出区，可以对照错误或者警告提示进行程序修改。如下列图：Visual C+ 6.0的工作环境图2.1 Visual C+ 6.0的工作环境第3章 算法分析及实现3.1 程序流程图1. 广度优先遍历的流程图；1.1主要流程图如下： 图3.1.1为广度优先遍历 1.2遍历实现：接受v顶点并找出相应的i数值visitedi= =0开始输出vVisitedi=1;queuerear=v;入队rear!=frontfront=

18、front+1;v=queuefrontP=gi.link;更新i值P!=0更新i值visitedi= =0输出该顶点visitedi=1;rear=rear+1;queuerear=p->adjvexp=p->next结束否是否否否是是 3.1.2图的遍历实现 2. 哈夫曼编码： 图3.2为哈夫曼遍历过程3.2算法分析及设计3.2.1创立图函数void create()for(i=1;i<=e;i+) printf("nplease input two vertex of a edge (s,d)n"); scanf("%c,%c",

19、&s,&d); for(j=1;j<n;j+) if(s=gj.data|d=gj.data) p=(struct edgenode *)malloc(sizeof(struct edgenode);p->adjvex=d;p->next=gs.link;gs.link=p;p=(struct edgenode *)malloc(sizeof(struct edgenode);p->adjvex=s;p->next=gd.link;gd.link=p; void CreateMGraph(MGraph *G) /创立图 int i,j,k; cha

20、r ch1,ch2; printf("请输入顶点数和边数(输入格式为:顶点数,边数):n"); scanf("%d,%d",&(G->n),&(G->e); printf("请输入顶点信息(顶点号<CR>)每个顶点以回车作为结束:n"); for(i=0;i<G->n;i+) getchar();scanf("%c",&(G->vexsi); for(i=0;i<G->n;i+) for(j=0;j<G->n;j+) G-&g

21、t;edgesij=0;printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j):n"); for(k=0;k<G->e;k+) getchar(); printf("请输入第%d条边的顶点序号：",k+1); scanf("%c,%c",&ch1,&ch2); for(i=0;ch1!=G->vexsi;i+); for(j=0;ch2!=G->vexsj;j+); G->edgesij=1;for(i=0;ch1!=G->vexsi;i+); for(j=0;ch2

22、!=G->vexsj;j+); G->edgesji=1; 先选择要操作的局部创立图,然后依次输入顶点和边,图创立完成后按任意键结束,界面显示如图3.2.1(1)所示: 3.2.1(1)创立图函数界面遍历图的非递归算法：void BFSTraverse (ALGraph *G,int v) /*从v出发遍历图G非递归算法*/ EdgeNode *p; int w,i; int queueMAXV,front=0,rear=0; /*定义循环队列*/ bool visitedMAXV; /*定义顶点的访问标志数组*/ for(i=0;i<G->n;i+) visitedi

23、=false; /*初始化*/ Visit(v); /*访问编号为v的顶点*/ visitedv=true; /*置已访问标记*/ rear=(rear+1)%MAXV; /*已访点v入队*/ queuerear=v; while (front!=rear) /*假设队列不空时循环*/ front=(front+1)%MAXV; w=queuefront; /*已访顶点出队，赋给w*/ p=G->adjlistw.firstedge ; /*从w的首邻接点出发*/ while(p) /*找w的所有邻接点*/ if (visitedp->adjvex=false) /*处理未访邻接点

24、*/ Visit(p->adjvex); /*访问邻接点*/ visitedp->adjvex=true; /*置已访标记*/ rear=(rear+1)%MAXV; /*已访点进队*/ queuerear=p->adjvex; p=p->next; /*找下一个邻接点*/ / while (p) / while (front!=rear) 运行的结果为： 图3.2.12图的非递归遍历3.2.2创立哈夫曼函数/ / 实现哈夫曼编/译码/-主函数- void main() char choice; while(choice!='q') cout<&l

25、t;"n*"<<endl; cout<<" 欢送使用哈夫曼编码解码系统"<<endl; cout<<"*"<<endl; cout<<"(1)要初始化哈夫曼链表请输入'i'"<<endl; cout<<"(2)要编码请输入'e'"<<endl; cout<<"(3)要译码请输入'd'"<<endl;

26、 cout<<"(4)要打印编码请输入'p'"<<endl; cout<<"(5)要打印哈夫曼树请输入't'"<<endl; cout<<"(6)要打印译码请输入'y'"<<endl; if(flag=0)cout<<"n请先初始化哈夫曼链表,输入'i'"<<endl; cin>>choice; switch(choice) case '

27、i': Initialization(); break; case 'e': Encoding(); break; case 'd': Decoding(); break; case 'p': Code_printing(); break; case 't': Tree_printing(HT,2*n-1); break; case 'y': Code_printing1(); break; default: cout<<"input error"<<endl;

28、free(z); free(w); free(HT); 如图运行如下：图3.2.21 哈夫曼树的创立 图3.2.21 哈夫曼树的创立/-初始化哈夫曼链表- void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;i<len;i+) k=0;flag=1; coui-a.data=stri; coui-a.count=1; while(i>k) if(stri=strk) a+; flag=0; k+; if(flag=0) break; if(flag) for(j=i+1;j<len;j+)

29、 if(stri=strj) +coui-a.count; n=len-a; for(i=0;i<n;i+) cout<<coui.data<<" " cout<<coui.count<<endl; for(i=0;i<=n;i+) *(z+i)=coui.data; *(w+i)=coui.count; HuffmanCoding(HT,HC,w,n); 遍历如下： 图3.2.22 图3.2.22初始化哈夫曼链表建立哈夫曼的算法：void HuffmanCoding(HuffmanTree &HT,Huf

30、fmanCode &HC,int *w,int n) / w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC int m,i,s1,s2,start; /unsigned c,f; int c,f; HuffmanTree p; char *cd; if(n<=1) return;/检测结点数是否可以构成树 m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for(p=HT+1,i=1;i<=n;+i,+p,+w) p->weight=*w; p->pa

31、rent=0; p->lchild=0; p->rchild=0; for(;i<=m;+i,+p) p->parent=0; for(i=n+1;i<=m;+i) / 建哈夫曼树 / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; / 从叶子到根逆向求每个字符的哈夫曼编码 HC=(Huffman

32、Code)malloc(n+1)*sizeof(char*); / 分配n个字符编码的头指针向量(0不用) cd=(char*)malloc(n*sizeof(char); / 分配求编码的工作空间 cdn-1='0' / 编码结束符 for(i=1;i<=n;i+) / 逐个字符求哈夫曼编码 start=n-1; / 编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码 if(HTf.lchild=c) cd-start='0' else cd-start='1'

33、 HCi=(char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(HCi,&cdstart); / 从cd复制编码(串)到HC free(cd); / 释放工作空间 /-编码函数- void Encoding() cout<<"下面对目录下文件tobetran.txt中的字符进行编码"<<endl; FILE *tobetran,*codefile; if(tobetran=fopen("tobetran.txt","rb")=NULL) c

34、out<<"不能翻开文件"<<endl; if(codefile=fopen("codefile.txt","wb")=NULL) cout<<"不能翻开文件"<<endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) cout<<"不能翻开文件"<<endl; bre

35、ak; for(i=0;*(tran+i)!='0'i+) for(j=0;j<=n;j+) if(*(z+j-1)=*(tran+i) fputs(HCj,codefile); if(j>n) cout<<"字符错误，无法编码!"<<endl; break; cout<<"编码工作完成"<<endl<<"编码写入目录下的codefile.txt中"<<endl<<endl; fclose(tobetran); fclose

36、(codefile); free(tran); 运行的结果为： 图3.2.23 图3.2.23建立哈夫曼编码/-译码函数- void Decoding() cout<<"下面对根目录下文件codefile.txt中的字符进行译码"<<endl; FILE *codef,*txtfile; if(txtfile=fopen("txtfile.txt","w")=NULL) cout<<"不能翻开文件"<<endl; if (codef=fopen("codef

37、ile.txt","r")=NULL) cout<<"不能翻开文件"<<endl; char *work,*work2,i2; int i4=0,i,i3; unsigned long length=10000; work=(char*)malloc(length*sizeof(char); fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char); i3=2*n-1; for(i=0;*(work+i-1)!='0'i+) i2=

38、*(work+i); if(HTi3.lchild=0) *(work2+i4)=*(z+i3-1); i4+; i3=2*n-1; i-; else if(i2='0') i3=HTi3.lchild; else if(i2='1') i3=HTi3.rchild; *(work2+i4)='0' fputs(work2,txtfile); cout<<"译码完成"<<endl<<"内容写入根目录下的文件txtfile.txt中"<<endl<<

39、endl; free(work); free(work2); fclose(txtfile); fclose(codef); 译码输出为：图3.2.24 图3.2.24译码输出/-打印编码的函数- void Code_printing() cout<<"下面打印根目录下文件CodePrin.txt中编码字符"<<endl; FILE * CodePrin,* codefile; if(CodePrin=fopen("CodePrin.txt","w")=NULL) cout<<"不能翻开文

40、件"<<endl; return; if(codefile=fopen("codefile.txt","r")=NULL) cout<<"不能翻开文件"<<endl; return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) cout<<"不能读取文件"<<endl; break; fputs(work3,CodeP

41、rin); puts(work3); while(strlen(work3)=50); free(work3); cout<<"打印工作结束"<<endl<<endl; fclose(CodePrin); fclose(codefile); 打印编码为：图3.2.25 图3.2.25打印编码输出/-打印哈夫曼树的函数- void coprint(HuffmanTree start,HuffmanTree HT) if(start!=HT) FILE * TreePrint; if(TreePrint=fopen("TreePri

42、nt.txt","a")=NULL) cout<<"创立文件失败"<<endl; return; numb+;/该变量为已被声明为全局变量 coprint(HT+start->rchild,HT); cout<<setw(5*numb)<<start->weight<<endl; fprintf(TreePrint,"%dn",start->weight); coprint(HT+start->lchild,HT); numb-; fclos

43、e(TreePrint); void Tree_printing(HuffmanTree HT,int w) HuffmanTree p; p=HT+w; cout<<"下面打印哈夫曼树"<<endl; coprint(p,HT); cout<<"打印工作结束"<<endl; 打印哈夫曼树为：图3.2.26 图3.2.26打印哈夫曼树/- 打印译码函数- void Code_printing1() cout<<"下面打印根目录下文件txtfile.txt中译码字符"<<endl; FILE * CodePrin1,* txtfile; if(CodePrin1=fopen("CodePrin1.txt","w")=NULL) co