(论文)数据结构及算法的设计与实现 数据结构课程设计报告最新优秀毕业论文资料搜集呕血奉献

课 程 设 计设计题目： 数据结构及算法的设计与实现 I课程设计（报告） 摘要摘 要 “数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重.点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词 ：线性表，栈和队列，二叉树，图，查找，排序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沈阳工程学院课程设计（报告） 第四章 设计实现利用普利姆算法构造最小生成树的程序第三章 利用Hash技术统计C源程序中关键字的频度随着社会的发展，出现了减少冲突的一种散列函数，它就是哈希函数。所谓的“哈希函数”就是表尚未被占用的地址，当插入的记录所选地地址已被占用时，即转而寻找其它尚未开发的地址。开放地址法又称为散列表处理冲突的方法。散列表按结构形式可分为散列表和闭散列表，所谓的闭散列表的结构是一个向量，也是一维数组，表中记录按关键字经散列函数运算所得的地址直接存入数组中。3.1问题分析在这个程序设计中,我们小组遇到的不少的问题:1.我们小组决定不下要用哪种查询方法。2.统计关键字发生的冲突的次数,到底应该怎么来记数,怎么样解决冲突,最后我们用了开放地址的线型探测法来解决冲突。3.在插入哈希表之后应该怎样重新来计算发生的冲突和频数(频度)。除留余数法式一种最简单、最常用的构造哈希函数方法，这种方法关键在于m的选择，选定m值后就可以决定存储地址的数目了，为了使哈希函数的取值尽可能“分散”一些，以减少冲突，m的选择要适当。形成探查地址序列最简单的方法是线性探测法，线性探测法的基本思想是沿着哈希表顺序向后查探，直至找到开放地址为止，如到达表末端仍未找到开放地址，则将表看做是循环的，返回到表的首端再向后找，只要尚有开放地址最终总可以找到。3.2数据结构与算法分析此哈希函数的主要功能是扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度，用线性探测法解决Hash冲突。还查询某指定关键字在Hash表中的情况，也能输出Hash表，关键词总数，冲突次数。其主要流程图如图3-1所示。开始输入orzWhile(orz)main()orz=A否是是Read(filename)否orz=BShow(i)1是否I=C是否Show(Findhx(word)I=D是2否breakbreakbreakGetKey()break输出输出输出输出12I=E是否输出GetKey(KeyWordsi)I=F是breakbreak图3-1 哈希表流程图3.3 核心代码哈希表主要程序代码如下：#include #include #include #include #define TOTAL 39 /39个关键字#define MAXLEN 10 /关键字长度#define HASHLEN 41 /哈希表长度typedef struct /哈希表 结构体 char keywordMAXLEN; /关键字int count; /记录频度int con; /记录冲突次数HASH;/全局变量int cont=0; /统计关键词个数char KeyWordsTOTALMAXLEN=asm,auto,break,case,cdecl,char, const,continue,default,do,double, else,enum,extern,far,float,for, goto,huge,if,int,interrupt,long, near,pascal,register,return,short, signed,sizeof,static,struct,switch, typedef,union,unsigned,void,volatile, while; /C语言中的39个关键字存入二维数组中HASH HSHASHLEN; /建立结构体HS/函数声明void Show(int key);int Read(char *filename); int isLetter(char ch);int isKeyWords(char *word);int FindHX(char *keyword);int CreatHX(char *keyword);int GetFreePos(int key);int GetKey(char *keyword);void main() char orz; int flag=1,i,count,key,has;char filename128,wordMAXLEN; while(flag) printf(ttA.读取一个文件n); printf(ttB.输出Hash表(关键字总数，冲突次数)n); printf(ttC.查询某关键字在Hash表中的情况n); printf(ttD.显示Hash表中的冲突关键字n); printf(ttE.显示C语言关键字的Hash函数值(作为对照)n); printf(ttF.退出nn);printf(tt请输入序号(A-F):); scanf(%c,&orz);switch(orz) case a:case A:system(cls); /清屏函数 printf(请输入要读取的文件名(文件必须与程序在同一目录下):); /比如输入：a.cppscanf(%s,&filen