数据结构试验最终总结

摘要：本学期我完成的主要实验任务有1、斐波那契序列，2、约瑟夫环，3、算术表达式的求值4、赫夫曼树，5、成绩统计程序。在每个试验中分别进行了概要设计和储存结构分析、主要算法分析、实验结果和结论分析等。并且对本学期所写程序提供相关数据结构理论和对本课程的相关建议。关键字：数据结构、实验、算法、分析、结论、结果实验一实验名称：斐波那契序列实验目的及要求：熟悉开发工具的编程环境。体会算法和程序的不同。学习用不同算法实现同一程序功能，并能熟练编程实现。4.学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点。要求：试编写求k阶（k>=2）裴波那契序列的第m项值的不同算法，并编程实现。k和m均以值调用的形式在函数参数中表现。要求：至少用两种不同的算法（如，递推、递归等等）。实验主要内容：概要设计和存储结构概要设计：先定义一个数组，用来储存从键盘输入的数据，通过调用核心算法，最终实现斐波那契序列本实验的存储结构是第一个程序使用了一个一数组，用来储存第m项的值，第二程序是开辟了一个空间用来接收用函数返回的值主要算法intk,m,a[20],i,sum=0;scanfk//intk,m,a[20],i,sum=0;scanfk//输入一个k的值for(i=0;i<=k;i++){if(i==k)a[i]=1;elsea[i]=0;} //对前k项经行赋值Scanfm//输入m的值for(i=k+1;i<=m;i++){sum=sum-a[i-k-1]+a[i-1];a[i]=sum;}printfa[m]}intt(intm,intk);〃声明函数intm1,k1,s;scanf kl;〃输入k1的值scanf ml;//输入mlprintf s=t(m1,k1));〃输出第m项的值intt(intm,intk){if(m<=k-1)return0;elseif(m==k+1||m==k)return1;else return(2*t(m-1,k)-t(m-k-1,k));//计算第m项的值}//定义函数〃输出第m项的值253实验结果和结论253取a[0]=0,a[1]=1;所以a[4]=3取a[0]=0,a[1]=0;a[2]=1,584所以a[4]=2584a[0]=0,a[1]=0,a[2]=0,a[3]=0,a[4]=1;所以a[8]=4-实验分析：第一个程序是先输入前k项，则第k+1项的值等于前k的和减去第1项的值，循环m-k次，就能求出第m项的值。第二个函数是从数学的方法推到一个公式2*t(m-1,k)-t(m-k-1,k),通过这个公式来实现求第m项的值。实验二实验名称：约瑟夫环实验目的及要求：假设有n个编号为1,2,3,…，n的人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，并将其密码值作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，以此类推下去，直到所有的人全部出列为止。试设计一个程序，可以在用户确定了人数和密码的情况下，求出对应的出列顺序。本实验的目的是1、熟悉开发工具的编程环境。2、 体会算法和程序的不同。3、 学习用不同算法实现同一程序功能，并能熟练编程实现。4、 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点。实验主要内容：概要设计和存储结构本次试验是定义一个结构体用来储存密码、序号、和指针等变量在主函数中创建一个单链表，通过调用核心算法和循环函数查找要删除的变量和删除该变量等操作等本实验的储存结构是在本程序中定义了一个链表作为储存单位，将序号和密码都放在里面structyue*p1,*p2,*p3,*p4;n=1;p1=p2=p3=p4=(structyue*)malloc(LEN);p1->num=1;scanf("%d",&p1->password);

while(n<7){p1=(structyue*)malloc(LEN);p2->next=p1;p2=p1;scanf("%d",&p1->password);p1->num=++n;}p2->next=p3;首先开辟七个空间，并用指针指向首节点，将序号和密码放入链表的相应位置，将最后的指针指向首节点，形成环。主要算法p1=p2=p3=p4=(structyue*)malloc(LEN);//开辟首节点p1->num=1;scanfp1->password;//对首节点进行赋值，输入序号和密码while(n<7){p1=(structyue*)malloc(LEN);p2->next=p1;p2=p1;scanf("%d",&p1->password);p1->num=++n;}while(n>1){structyue*s;for(i=1;i<(m%n);p2=p1,p1=p1->next,iwhile(n>1){structyue*s;for(i=1;i<(m%n);p2=p1,p1=p1->next,i++);//找出删除点p2->next=p1->next;s=p1;printfs->num//输出该结点m=s->password;p1=p1->next;free(s);//释放节点n--;//形成循环链表-实验结果和结论147235Pressanykeytocontinue-实验分析：在本程序中用一个链表作为储存单位，形成循环链表，用一个for循环找到要删除的节点，用一个while循环输出要输出的序号实验三实验名称：算术表达式的求值实验目的及要求：以字符序列形式从终端输入语法正确的、不含变量的整数表达式。利用课本3.2.5节中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照课本上的例子演示在求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。实验目的：1、熟悉开发工具的编程环境。2、 体会算法和程序的不同。3、 学习用不同算法实现同一程序功能，并能熟练编程实现。4、 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点。实验主要内容：・概要设计和存储结构本次试验是通过分别定义三个不同的结构体，然后定义不同的调用函数，运算符函数，最后通过主函数调用各个函数，实现算术表达式的求值。本实验的存储结构是在本程序中分别开辟了两个栈分别储存数据和运算符，在开辟的时候运用调用函数的方式进行的。主要算法statueEvaluateExpression(){InitStack(OPTR);Push(OPTR,'#');initStack(OPND);c=getchar();while(c!='#'||GetTop(OPTR)!='#'){if(!In(c,OP)){Push((OPND),c);c=getchar();}elseswitch(Precede(GetTop(OPTR),c)){case'<':Push(OPTR,c);c=getchar();break;case'=':Pop(OPTR,x);c=getchar();break;case'>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}returnGetTop(OPND);}//主要函数，实现表达式的求值实验结果和结论Pleaseenteraexpressionenduith'if%.：3*<7-2>ttTheresultis15-000000Pressa:i^比亡¥toexitPressanvkeytocontinue取3*（7-2）;结果15PleaseenteraexpressionendwithJ#J:1+2+3+4#Theresul七is1^.000000Pressart#keytoexitPressans*keytoconti.nue取1+2+3+4;结果10Pleaseenteraexpressionendwith*#J-5*8/4#TheresultisPressanvkeytoexitPressanpkeyt鸡continue取5*8/4,结果10-实验分析：本次程采取的是总分式的，一个主程序调用其他函数的形式，每一个函数都需要定义，主题程序采用栈储存，在函数定义过程中用到了一维数组、二维数组。实验四实验名称：赫夫曼树实验目的及要求：一个完整的系统应具有以下功能：(1) 初始化。从终端读入字符集大小n以及n个字符和n个权值，建立哈夫曼树，并将它存储于文件hfmtree中。(2) 编码。利用建好的哈夫曼树，对要传输的文件tobefile中的正文进行编码，然后将结果存入另一个文件codefile中。(3) 译码。利用建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件文件textfile中。（4）印代码文件。将文件codefile以紧凑格式显示在终端屏幕上，每行50个代码，同时将此字符形式的编码文件写入文件codeprin中。（5）印哈夫曼树。将已在内存中的哈夫曼树以直观的形式（树或凹入表或其它形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。实验主要目的是1、熟悉开发工具的编程环境。2、体会算法和程序的不同。3、学习用不同算法实现同一程序功能，并能熟练编程实现。4、学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点。实验主要内容：概要设计和存储结构恒合法个数n枸造喑夫曼树哈夫恒合法个数n枸造喑夫曼树哈夫曼汩码至输第「页共19页场入各个字芹懸其枚値•「在大量的应用中，人们曾使用多种形式的存储结构来表示树，在本试验中所用的存储结构是数组，定义了一个数组来存储赫夫曼树。主要算法typedefstruct{//哈弗曼树和赫夫曼编码的存储表示unsignedintweight;unsignedintparent,lchild,rchild;}HENode,*HuffmanTree;//动态分配数组存储哈弗曼树typedefchar**HuffmanCode;//动态分配存储哈弗曼编码表}//无栈非递归遍历哈弗曼树，求哈弗曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));p=m;cdlen=0;for(i=1;i<=m;++i)Ht[i].weight=0;//遍历哈弗曼树是用作结点状态标志while(p){//向左voidHuffmanCoding(HuffmanTree&HT,Huffmancode&HC,int*w,intn){//w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC。if(n<=1)return;m=2*n-1;HT=(HuffmanTree),malloc((m+1)*sizeof(HTNode));//0号单元未用for(p=HT+1,i=1;i<=n;++n,++p,++w)*p={*w,0,0,0};for(;i<=m;++i,++p)*p={0,0,0,0};for(i=n+1;i<=m;++i){//建赫夫曼树//在HT[l..i-l]选择parent为0且weight最小的两个结点,其序号分别为s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;if(HT[p].weight==0){HC[p].weight=1;if(HC[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]="0";}elseif(HT[p].lchild==0){//登记叶子结点的字符的编码HT[p]=(char*)malloc((cdlen+1)*sizeof(char));cd[cdlen]="\0";strcpy(HT[p].cd);//复制编码(串)}}elseif(HC[p].weight==1){ //向右HC[p].weight=2;if(HC[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]="1";}}else{//HC[p].weight==2,退回HC[p].weight=0;p=HC[p].parent;--cdlen;//退到父结点，编码长度减1}//else}//while实验结果和结论输入4请输入你要编码的赫夫曼树字符种类个数：4请输入第1个字符及其权值并以空格分隔开=a1请输入笫2个字符及其权值并以空格分隔开:碁备入第3个字符及其权值并以空格分隔开:备為入第4个字符及其权值并以空格分隔开:d4根据提示分别输入4，Ei,bl2,Cs3,dI4R器no若要译码请喻人Y：若不译码嶽天'-输九£斤要编译的序列号：010105JB1111S0011001010译码的文本是：decddbcddadcc倉要译码请输入晔若不译码输入札Pressanvkeytocontinue根据提示，输入0101000111100011001010实验分析：在这次的试验中，采用的是主程序调用函数的方式进行的，在程序的开头定义了结构体，接着定义了四个函数，以供后面的主函数调用，最后写的主函数，主函数简单明了的引导着程序的一步一步的进行下去。实验五实验名称：成绩统计程序实验目的及要求：给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。1、假定有20位同学，每位同学有四门课，分数均为百分制。2、使用简单插入排序算法，按总数高低次序，打印出名次表，分数相同的为同一名次；3、按名次打印出每个学生的学号、姓名、总分以及各科成绩。实验主要目的是1、熟悉开发工具的编程环境。2、体会算法和程序的不同。3、学习用不同算法实现同一程序功能，并能熟练编程实现。4、学习分析算法。对比不同算法实现的效率有何不同，所占空间有何不同。对比不同算法的优点和缺点。实验主要内容：・概要设计和存储结构定义一个结构体，里面定义一个八个变量，再分别定义所需要的调用的函数，最后写一个主函数，在声明函数的时候需要用到随机函数struetaStu{char strName[20];//姓名intxh;//学号intEnglish;//英语成绩intMath;//数学成绩intChinese;//语文成绩intsjjg;//数据结构inttotal;//总成绩intPlace;//名次};-主要算法Statuepaixu(int&I,structAddstu){for(inti=0;i<COUNT;i++)//输入学生信息{printf(“该学生总成绩是：％lf\n",AddStu());}

show();//在屏幕上输出排序好的信息}voidshow(){OrderByScore();printf("学生成绩排名")；printf("\n名次学号姓名英语数学语文数据结构 总成绩");for(inti=0;i<COUNT;i++){printf("\n%d%d%s%d%d%d%ld%d\n",bstrStu[i].Place,bstrStu[i].xh,bstrStu[i].strName,bstrStu[i].English,bstrStu[i].Math,bstrStu[i].Chinese,bstrStu[i].sjjg,bstrStu[i].total);}}//按排名显示实验结果和结论学号=206881126鮎泸连萨：武晨该学生总成绩是=236.000000请输入学号：200881127请影冷空姓名=王某该学生总成绩•杲：282.000000依|邈欺11■22008811272^8811282^«811262^881128姓名

王某李某武晨张某学号=206881126鮎泸连萨：武晨该学生总成绩是=236.000000请输入学号：200881127请影冷空姓名=王某该学生总成绩•杲：282.000000依|邈欺11■22008811272^8811282^«811262^881128姓名

王某李某武晨张某:200881128学号和姓名，有随机函H学号和姓名，有随机函数得到该200881128的总英语&蛍数学69语文65数据结构685161638741724Pressanykeytocontinue4967总成绩282262236234按回车键得到排名实验分析：本次程采取的是总分式的，一个主程序调用其他函数的形式，每一个函数都需要定义，主题程序采用结构体储存，在函数定义过程中用到了八个变量。综合分析部分相关理论及实验结论本学期开设的《数据结构》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程试验等方面进行学习总结。一、《数据结构与算法》知识点在课本的第一章便交代了该学科的相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。紧接着介绍了一些常用的数据运算。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。第二章具体地介绍了线性表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。第三章堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。第四章介绍了串的概念，串类型的定义，穿的变形和实现，定长顺序存储表示、堆分配存储表示、串的块链存储表示，重点在于串的模式匹配。第五章介绍了数组和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。第六章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。第七章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。、对各个实验的总结在实验一对比算法的时空效率之裴波那契序列中，通过两种不同的递推方法和一种递归方法，得出了实验结果，其中一种递推方法是通过递归方法推出递推方法的，主要是采用了temp[m]=2*temp[m-l]—temp[m-k-l]此公式采用了循环递推以及递推的方法得出结果。在定义存储结构时采用的是线性顺序表的顺序表示，即是用一组地址连续的存储单元依次存储线性表的数据元素。在设计和调试程序时，我遇到的主要问题是无法实现求第m项的值，解决方案是改进了for循环。本次实验不是很成功，但最后还是编出来了，因为本人的能力有限，所以刚开始只用了一种方法，后来慢慢想到了另外一种方法。经过这次编程发c语言并不是很难，只是当时没有好好学习，所以在以后的学习过程中，加强对c语言的学习，在编程的过程中，遇到了开辟内存的问题，我用的方法不是很好，分配的是静态空间，这样就会浪费许多的空间，还有可能造成资源的浪费，应该学会怎样开辟动态的空间，这样就可以很有效地利用内存资源，一个好的程序总是很精简的，而且效率是很高的，过多的语句只会造成资源的浪费，要学会精简语句，这样才能编出好的程序。当编出一道程序是是很令人高兴的事，如果不经常编程就会对c语言产生生疏感，就算简单的语句都会出错，在编程的过程中一定细心，任何一个小的语法错误都会造成编译的通不过，这样就会浪费时间在实验二线性表及其应用之约瑟夫环中，我采用了线性表的链式存储结构，是最常用且最简单的一种数据结构，简言之，一个线性表是n个数据元素的有序序列，其特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），线性表的链式存储结构不要求逻辑上相邻的元素在物理位置上相邻，因此它没有顺序表存储结构所具有的弱点，但是同时也失去了线性表的顺序存储结构可随机存取的优点。在设计和调试程序时，我遇到的主要问题是用两个for无法准确找出要删除的节点，解决方案是用一个while和for循环，从新改变了算法，因为那个算法有一些逻辑上的错误。本次实验不是很顺利，但最后还是编出来了，因为刚开始设计的程序有逻辑上的错误，所以刚开始只用了一种比较不好的方法，后来改用了另外一种方法。经过这次编程发c语言并还是很有趣的，只是当时学习的不是很好，所以在以后的学习过程中，加强对C语言的学习，在编程的过程中，遇到了寻找要删除节点的问题，因为那个发那个方法有逻辑上的错误，在分配空间上也有一些问题，这样就会浪费许多的时间，而且造成在编程上出现了不稳定性，应该学会如何更好的用for循环，这样就可以很有效地节约时间，一个好的程序总是很精辟的，而且效率是很高的，过多的语句只会造成资源的浪费，要学会精简语句，这样才能编出好的程序。当编出一道程序是是很令人高兴的事，如果不经常编程就会对c语言产生生疏感。在实验三栈和队列之算术表达式求值中，其实验目的在于通过上机实践掌握队列和栈的顺序存储结构和链式存储结构，以便我们能在相应的应用问题中正确选用它们；掌握栈和队列的特点，即先进后出与先进先出的原则；掌握栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存储结构和链式存储结构上的实现。此实验中的程序根据字符输入，通过栈整个数据结构来存储，在定义栈时，仅定义了一个栈的相关操作，建立两个栈名称数字或字符栈和操作符栈，先将输入全设为字符，将字符全存入两个栈中，通过函数调用将字符转换为其相应的字面数字进行加减乘除运算，最后得到最终结果，将运算结果存储于栈中并最终输出相应结果。在设计和调试程序时，函数参数值的返回问题，开始不知道如何通过指针实现函数值的返回；不知道字符与数字之间如何实现数值上的相互等值转；在定义变量时不知道是否应该定义为全局变量；在程序引入大量的函数模块时出现处理不清，OPND语句就可运行成功，其实没有开辟相应地址空间OPTR和OPND,应该用new语句开辟相应空间如STACKOPTR=newSqStack,OPND=newSqStack;。在设计和调试程序时，我遇到的主要问题是有些函数定义不会，个别函数的功能也不是很清楚。本次实验不是很顺利，但最后费力很长的时间编出来了，由于我的c语言学的不是很好，所以有一些函数的实现确实不会编，后来后来问别人和书本上查了一些函数的实现方法。慢慢将全部的函数都实现了，主程序是书本上用的，通过本次编程是我认识到自己在字符表示方面的不足，所以在以后的学习过程中，加强对字符和数组的学习，在编程的过程中，还遇到了函数调用的问题，对其定义不是很了解，需要继续好好学习C语言。在实验四树和二叉树之层序遍历二叉树中的先序遍历、中序遍历、后序遍历、层序遍历均采用递归算法，而构建二叉树时也采用的是递归算法。在层序遍历中采用队列的入队进队的方法从而实现层序遍历二叉树。对于二