数据结构实验报告剖析

1、数据结构实验报告(一)提交日期:班级名称线性表姓名67线性表是最简单的线性结构。线性表的主要操作特点是可以在任意位置插入和删除一个数据元素。一、线性表的顺序存储结构线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1,ai,在存储地址中也是相邻的，既地址连续。我们采用的是含静态一维数组和线性表长的结构体。测试数据与运行记录如下：步骤一，建立线性表。输入“1”。回车键入，得到“n=?”输入的n即为线性表所要存储的元素长度，由于建立线性表时已规定MAXSIZE=20，因此所输入的n应该小于等于20。此处实验输入n=6。然后，将想要插入的数据元素分别输入数据域data0到data5。回车

2、键入，程序得出一段由6个数据元素组成的如下图所示的线性链表。测试 数据 与运 行记 录链表数据为：1,2,3,4,5,6。*'C:LlserslenovoDesktop5S5sHt5Debog1,exe'1 .建立线性表2 .在i瓦亶插入元素e3 .删除第i个元素，返回其值4 .查找值为e的元素6 .结束程序运行请输入您的选择(L2,3,4,6)1门=?6data0=?1data1=?2data2二73data3=?4data4=75data5=?6123456打回车键，继续。4.查找值为e的元素6.结束程序运行请输入您的选择(L2,3,4,6)4e=?4已找到，元素位置是4e

3、=?10未找到T最后，程序运行完毕，回车退出。二、线性表的链式存储结构线性表链式存储的操作同样包括几个方面：线性表的建立、元素的插入、删除、查询等。其本质是：在逻辑上相邻的两个数据元素ai-1,ai,在存储地址中可以不相邻，既地址不连续。根据指针域的不同和结点的构造链的方式不同，链表主要有单链表、单循环链表和双向循环链表。其中，单链表是最经常使用的链表。试据运记 测数与行录步骤一，建线性链表选择“1”。输入元素组成一个链表。链表的建立与顺序表不同，它是一种动态结构。建立线性表的链式存储结构的过程就是一个动态生成链表的过程。因此每输入一个元素即重新分配新的结点，本次实验输入元素为：5,1,2,3

4、,4,5,6,7。步骤二，插入元素链表和顺序表的插入运算不同，顺序表在插入时要移动大量的结点，而链表在插入时不需要移动结点，但需要移动指针来进行位置的查找。先使p指向ai-1,然后生成一个数据域值为x的新结点*s,再进行插入操作。2 .在i位置插入元素日&删除第i个元素，返回其值4 .查找值为e的元素5 .结束程序运行请输入您的选择(1,2,3,4,5)2i产？5,115123114567步骤三，删除第i个元素选择“3”，回车键入，输入想要删掉的第“i”个元素工删除第i个元素，返回其值4 .查找值为e的元素5 .结束程序运行请输入您的选择(1,2,3,4,5)3i=7251311456

5、7步骤四，查找元素6 .查找值为e的元素7 .结束程序运行请输入您的选择(L2,3,4,5)4e=74已找到，元素位置是5最后，程序运行完毕，回车退出。一、线性表的顺序结构存储(1)创建顺序表create_listL并输出表out_listL(注：本程序中未进行顺序表的初始化InitListL,其效果与create_listL的效果一样，据部实总的序程 根本分验结程流对实验无影响。)/*建立线性表*/voidcreat_list(SqList*L)inti；printf("nn=?");scanf("%d”,&L->length);for(i=0;i

6、<L->length;i+)printf("ndata%d=?",i);scanf("%d”,&(L->ai);/*creat_list*/【说明】由于函数中要改变参数L的一维数组MAXSIZE的值，因此参数L应设计为输出型参数，即L设计为SqList的指针类型，否则，一维数组子域的修改值将不能带回去。(2)插入数据元素insert_sqvoidinsert_sq(SqList*L,inti,ElemTypee)intj;if(L->length=MAXSIZE)printf("noverflow!");else

7、if(i<1|i>L->length+1)printf("nerroei!");elsefor(j=L->length-1;j>i-1;j-)L->aj+1=L->aj;/*向后移动数据元素*/L->ai-1=e;/*插入元素*/L->length+;/*线性表长加1*/*insert_sq*/【说明】数据元素个数size比数组下标，即参数i的值大1,所以插入位置参数i应大于等于0且小于等于宏定义的MAXSIZE20.当参数i不在上述区间内时，即可判定参数出错。数组的存储空间是有限的，若当前已存满数组的MAXSIZE的存

8、储空间，则不能继续插入。(注：本程序先把存储单元i-1至存储单元i中的数据元素依次后移，然后把数据元素e插入到存储单元i中，最后把数据元素+1.)(3)删除数据元素delete_sqElemTypedelete_sq(SqList*L,inti)据部实总的序程 根本分验结程流ElemTypex;intj;if(L->length=0)printf("n是空表。underflow!”);elseif(i<1|i>L->length)printf("nerrori!");x=-1;elsex=L->ai-1;for(j=i;j<=L

9、->length-1;j+)L->aj-1=L->aj;L->length-;return(x);/*delete_sq*/【说明】若顺序表中当前没有一个数据元素，则无法进行删除，判断为函数调用出错。删除位置参数i应大于等于0且小于等于i-1,当参数i不在上述区间，即为参数出错。删除步骤总结如下：首先把存储单元i中的数据元素，即ai存放到参数x中，然后从前向后依次前移从存储位置i到存储单元i-1中的数据元素，最后把数据元素个数-1。(4)查找数据元素locat_sq(注：此处为按结点值查找方法，另有按结点序号查找get_sq)/*查找值为e的元素，返回它的位置*/int

10、locat_sq(SqListL,ElemTypee)inti=0;while(i<=L.length-1&&L.ai!=e)i+;if(i<=L.length-1)return(i+1);elsereturn(-1);/*locat_sq*/【说明】在表中按值查找结点，即从链表的开始结点出发，顺链逐个将结点的值和给定的值e进行比较，若遇到相等的，则返回结点的存储位置，否则返回一1(按值查找法比按序号查找更为简单，建议使用前者)。三、线性表的链式存储结构(1)建立线T链表*creat_L并输出链表out_L1133A(1)插入数据元素insert_Lvoidinse

11、rt_L(LNode*L,inti,ElemTypee)LNode*s,*p;intj;p=L;/*找第i-1个结点*/j=0;根据 本部 分实 验总 结的 程序 流程while(p!=NULL&&j<i-1)p=p->next;j+;if(p=NULL|j>i-1)printf("niERROR!");elses=(LNode*)malloc(sizeof(LNode);s->data=e;s->next=p->next;p->next=s;/*insert_L*/【说明】要在带头结点的单链表第i(0wiwsiNe

12、个结点前插入一个存放数据元素e的结点，首先在单链表中寻找到第i-1个结点并由p指示，然后动态申请一个结点存储空间并由s指示，并s->data=e,最后修改新结点指针域指向ai：s->next=p->next,并修改ai-1指针域使之指向s,即p->next=s。(2) 删除数据元素delete_L删除运算就是将链表中的第i个结点从表中删去。由于第i个结点的存储位置存储在第i-1个结点的指针域next中，因此要先使p指向第i-1个结点，然后使得p->next指向第i+1个结点，再将第i个结点释放掉。(3) 查找数据元素locat_L在单链表中按值查找结点，就是从链表

13、的开始结点出发，顺链逐个将结点的值和给定的e进行比较，若相等，则返回结点的存储位置，否则程序return(-1)。1、 VC6.0自动检测出的错误显示为“getch:undeclaredidentifier”。实验 中遇 到的 问题 及解 决情 况问题分析："undeclaredidentifier"意为未声明的标识符。未声明的标识符有以下两种情况：一为没有声明的语句直接使用；二为没有声明语句，直接使用函数。因此此处可以添加头文件。头文件的作用是避免多个代码文件全局变量(函数)，防止定义冲突。因此可以在函数声明处添加#include<conio.h>另外，get

14、ch()函数在此程序中并未起实际作用，可以删去。2、VC6.0检测错误显示“'main':functionshouldreturnavalue;'void'returntypeassumed'。问题分析："main：functionshouldreturnavalue意'为主函数没有返回值，有三种改正方法：(1)改为空类型，即把main()改为voidmain();(2)不加void的话主函数默认返回值是int,所以可以把main()改为intmain(),再在主函数末尾加入return(0);(3)直接只加入return(0)。3、在

15、程序运行过程中因为输入法问题导致程序运行错误，如下图所示:2.在i位置插入元素e3,删除第i个元素，返回其值工查找值为e的元素仅结束程序运行请输入您的选择(1,2,3,4,6)21-858993460234打回车键，继续.麒拼音半：问题分析：程序中只识别英文编辑状态下的字符，不能识别中文输入的字符，上图中的逗号是中文方式输入，程序无法识别，导致程序终止。将逗号输入切换到英文状态下即可。实验 完成 后的 体会通过本次实验，我对线性表的顺序存储结构和链表存储结构有了新的认识。线性表的顺序存储结构优点是空间利用率高，可以随机存取。缺点是插入元素和删除元素存在元素移动，耗时较多，并且顺序存储结构有空间

16、限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现"溢出”问题.当元素个数远少于预先分配的空间时，空间浪费大。线性表在单链表存储结构上的基本运算有建表、插入、删除和查找。链表存储结构弥补了顺序存储结构的缺憾，其插入元素和删除元素速度快并且没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关。缺点是占用额外的空间以存储指针(浪费空间)，存取某个元素速度慢。顺序存储结构和链表存储结构对比如下：(1)顺序结构可以进行随机存取顺序存储表中的第i个元素，链式存储不能进行随机的存储，每次访问数据元素都需要从头指针开始进行。(2)顺序存储不需要为表示表中元素之间的逻辑关系增加额外

17、的存储空间一个存储单位就存储一个数据元素，即存储密度大。链式存储数据元素之间的逻辑关系与物理关系位置不对应，需要指示结点之间关系的指针域，因而在存储空间要付出代价。(3)顺序存储采用静态分配的内存空间，存储容量难以事先确定，分配过大或过小都不好；链式存储的存储空间采用动态分配的方式，不会存在分配不够用或浪费的情况。(4)在顺序存储表上进行大量的插入和删除操作时，需要移动大量的元素，使操作运行时间长；链式存储进行插入和删除数据时，不需要移动大量的元素，只需要修改指针。另外，实验过程中发现许多在课堂上忽视的问题，在实验室中，从自己动手调试程序，修改程序中错误，再到成功运行出程序，在此过程中有屡次调

18、试失败的灰心丧气，也有成功后的莫大喜悦，这应该就是学习数据结构的魅力所在了吧。与此同时，我更深刻认识到了自己的不足，有时候一个小小的标点就能使一个大的程序卡死或者停止运行。记得老师说过“细节决定成败”，在调试程序的时候，我就是因为对输入法的不在意，中文状态下的标点符号不被程序识别，结果耽误了整整半堂实验，到最后经过逐一排查，终于找到了问题所在，最终成功运行出了程序。由此可以看出实践不光是检验真理的唯一标准，还是发现自身错误的最好方法。通过这次实验，我不仅对老师在课堂上讲过的内容加深了理解，更深刻的体会到自己自身的缺点带来的麻烦。在今后的学习过程中，我更要加倍努力改正自己的缺点，尽可能将粗心带来

19、的实验误差降到最低。数据结构实验报告(二)提交日期:级号验称班学实名姓名±W¥67栈的顺序存储结构及实现假设栈S=(a1,a2,，an),则称al为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，退栈的第一个元素为栈顶元素，即栈的修改是按后进先出(LIFO)或先进后出(FILO)的原则。程序运行如下：1、进栈1 .数据元素巳进栈2,出栈一个元素，返回其值工结束程序运行请输入您的选择(1.2,3)1试据运记 测数与行录进栈e=?6data=6data-5data=4data=3data=2data=l2、出栈L数据元素日进栈2 .出栈一个元素，返回其值3 .结

20、束程序运行请襦又您而1择(1,2,3)2匕栈元素：6data=5data=4data=3data=2data=l最后，运行结束，回车退出程序。本次实验内容为栈的顺序存储结构及实现。由于栈是运算受限的线性表，因此线性表的存储结构对栈也适用。栈的顺序存储结构简称为顺序栈。因为栈底位置是固定不变的，所以可以讲栈底位置设置在数组的最低端(即下标为0);栈顶位置是随着进栈和退栈操作而变化的，故用一个整型量top来指示当前栈顶位置，则top为栈顶指针。因此，顺序栈的类型定义仅仅是将顺序表类型定义中的长度length改为top,SqList改为SqStack。因此可定义顺序栈如下:#include<s

21、tdio.h>#include<stdlib.h>/*数组最大界限*/*数据元素类型*/* 一维数组子域*/*栈顶指针子域*/*栈的顺序结构体类型*/#defineMAXSIZE20typedefintElemType;typedefstructElemTypeaMAXSIZE;据部实总的序程 根本分验结程流inttop;SqStack;SqStacks1;顺序栈的操作实现如下：初始化空栈init_s步骤如下：(1)分配空间并检查空间是否分配失败，若失败则返回错误设置栈底和栈顶指针S.top=S.base;(3)设置栈大小2、进栈pushvoidpush(SqStack*s,

22、ElemTypee)if(s->top=MAXSIZE-1)printf("nSstackisOverflow!");elses->top+;s->as->top=e;/*push*/【说明】先判断是否栈满，若满则出错；然后将元素e压入栈顶，同时，栈顶指针加1。1、出栈popElemTypepop(SqStack*s)ElemTypex;if(s->top=-1)printf("nStackisUnderflow!");x=-1;elsex=s->as->top;s->top-;return(x);/*po

23、p*/【说明】首先判断是否栈空，若空则出错；接着获取栈顶元素e,同时，栈顶指针减1。另外，本实验中程序没有涉及到取顺序栈栈顶元素，即GetTop,其运行思路为：首先，判断是否空栈，若空则返回错误；否则通过栈顶指针获取栈顶元素。实验中遇至1的问题及解决情况1、VC6.0测试出现错误"errorC2018:unknowncharacter'0xa3'errorC2018:unknowncharacter'0xbb'"。问题分析：“printf（"nn2.出栈一个元素，返回其值“）；”原程序段中的“；”是在中文状卷下输入的字符，程序无法识

24、别导致出错。应使用英文输入法输入程序语言。2、调试出现"syntaxerror:missing''beforeidentifier'push'"问题分析："case1:printf（"n进栈e=?"）;scanf（"%d",&e）"末尾缺少"；”，应在句末加上一个分号，并且是英文状态吓的字符形式。3、VC6.0测试出现错误如下：errorC26Q1:outs':localfunctiondefinitionsareillegalerrorC2601:*pus

25、h':localfunctiondefinitionsareillegalerror02691:4pop1:localfunctiondefinitionsareillegal问题分析：localfunctiondefinitionsareillegal息为函数te义出错。调试错误原因是主应用程序的函数少了一个“"。用“Ctrl+”逐一排查函数（一般报错位置并不是真正的出错位置，通常是报错位置的上一个函数）。实验完成后的体会通过在课堂内外的学习和实践，我了解到栈是一种重要的线性结构。从数据结构角度看，栈也是线性表，其特殊性在于栈的基本操作是线性表操作的子集，它是操作受限的线性

26、表，因此，可称为限定性的数据结构。与前面学的关于顺序表的知识对比发现，顺序栈和顺序表的数据成员是相同的，不问的是，顺序栈的入栈和出栈操作只能对于当前栈顶元素进行。n:Cpp1-Uin32Debug(1)：uarning2867：unexpectedtokensfollowingpreprocessordirective-expectedanw】ig):errorC2065:'MftXSIZE':und«tlaeedidentifier(4) :errorC2U57：expectedconstantexpression(5) :earningC42B0:nonstand

27、ardextensionused:zero-sizedarrayinstruct/union(6) :errorC2229:struct'_unnamed1hasanillegalzero-sizedarrap(19) :errorC2G18:unknouncharacter'1(20) :errorC2018:unknouncharacter'Oxbbh(21) :errorC71U6:到ntaKerror:nissingb;'beForeidentifier'printf-(32) ：errorC2O65:dexitb：undeclaredident

28、ifier(37) :errorC2仙6:syntaxerror:nissing'HbeFureidentifierbprintF'(38) :errorC2M5:'getch':undeclaredidentifier(39) :learningC45冏:'main':functionshouldreturnavalue;'void'returntypeassuned(46) :errorC2S19:type'SqStack'doesnothaveanoverloadedmenber'operator-&

29、gt;'cpp1.cpp(4):seedeclarationoF'SqStack'(47) :errorC2227:LeftoF*->tcp'nustpainttoclass/struct/union(48) :errorC2819:typeb$q£tack'doesnothaueanourLaadedmenber'operatorcpp1.cpp(ii):seedeclarationof'qtck'(117) :errorC2227:LeftoF->top-nustpointtoclss/struct/un

30、ion(iiS):errorC2819:typeFSqStackFdoesnothauanouerLoadedmenberOperatorcppl.cpp(i>):Seedeclarationof'SqStack'(48):errorC2227:LeftoF'->aFmustpointtoclass/5truct/union个人体会：刚开始调试程序时，VC6.0检测出上图所示的长长的一串错误来，让人看了都觉得十分发愁。后来通过老师的指导，我和身边的同学分工合作，将困难化整为零，认真考虑程序的可能存在错误点，最后我们终于把程序成功的运行了出来。经过这次实验，我

31、深深地体会到耐心对于学好程序的重要性。随着学习的不断深入，我们所学的问题深度越来越多，所需要处理的程序也就越来越长，只用耐下心来分析问题，才能得到正确的结果。同时，在运行程序的时候一定不要害怕麻烦,静下心来做，慢慢把错误的一个大的程序慢慢分解成一个个小的问题，化繁为简，认真细心地分析函数中的每一个语句和运算，隐藏在程序语句中的错误最终都会被纠正。数据结构实验报告（三）提交日期:班级实验队列名称队列也是一种特殊的线性表，队列的数据元素及数据元素间的逻辑关系和线性表的完全相同，其差别是：线性表允许在任意位置插入和删除数据元素，而队列只允许在其一端进行插入操作（队尾），另一端进行删除操作（队头）。队

32、列中，最先进入队列的数据元素总是最先出队列，所以队列是一种先进先出表。和线性表类似，队列也有两种存储表示一一循环队列（顺序存储）和链队列。一、循环队列（即队列的顺序存储结构）实现用数组实现队列时，随着数据的不断读写，会出现假满队列情况。即尾数组已满而头数是空的；循环队列在逻辑上把数组的头尾相连，能够很好的利用有限的资源。1、进队1 .数据元素曰进队列测试 数据 与运 行记 录2 .出队一个元素，返回其值3 .结束程序运行请输入您的选择（1,2,3）1进队e=?ldata=5data=4data=3data=2data=l2、出队1.数据元素E进队列Z出队一个元素，返回其值工结束程序运行请输入您

33、的选择（1,233）2年队：4data=3data=2data-l最后，程序运行结束，回车退出。二、队列的链表存储结构及实现链队就是采用链式存储结构存储队列，这里采用单链表来实现。链表的特点是不存在队列溢满的情况。链队同循环队列的程序运行步骤相同，都是进队和出队两个步骤。、步骤如下：1、进队试据运记 测数与行录据部实总的序程 根本分验结程流1 .数据元素&进队列2 .出队一个元素，返回其值3 .结束程序运行请看工您正虚择(1,2,3)1进队e=?634562、出队L数据元素日进队列2.出队一个元素，返回其值品结束程序运行请输入您的选择(1,22出队元素；3456最后，程序运行结束，回车

34、退出。一、循环队列通过顺序队列的“假溢出”现象优化得到循环队列结构。循环队列结构存在两种状态和两种操作，如下：1、两种状态(1) 队空状态：Q->front=Q->rear。(2) 队满状态：(Q->rear+1)%MAXSIZE=Q->front)2、两种操作(1)进队EnQueue:Q->rear=(Q->rear+1)%MAXSIZE;Q->aQ->rear=e;(2)出队DeQueue：Q->front=(Q->front+1)%MAXSIZE;x=Q->aQ->front;程序流程为：1、初始化空队列init_Q

35、并输出队列out_Q2、进队EnQueue3、出队DeQueue根据 本部 分实 验总 结的 程序 流程实验 中遇 到的 问题 及解 决情 况二、链队列1、入队EnQueue_voidEnQueue(L_Queue*Q,ElemTypee)QNode*s;s=(QNode*)malloc(sizeof(QNode);s->data=e;s->next=NULL;Q->rear->next=s;Q->rear=s;/*EnQueue*/【说明】元素插入到队列中只能在队尾插入，队头指针始终指向头结点，队尾指针指向队列的最后一个元素。首先开辟一个新结点s,再在队尾才1入

36、结点Q->rear->next=s;最后修改队尾指针：Q->rear=s;(2)出队操作DeQueueElemTypeDeQueue(L_Queue*Q)ElemTypex;QNode*p;if(Q->front=Q->rear)printf("nQueueisNULL!");x=-1;elsep=Q->front->next;x=p->data;Q->front->next=p->next;if(Q->rear=p)Q->rear=Q->front;free(p);return(x);/*

37、DeQueue*/【说明】首先判断此队列是否为空，若为空，则返回-1,结束进程。否则，使p指向队头元素，再使队头元素p出队。如果队中只有一个元素，则p出队后成为空队。最后释放存储空间。1、'SqQueue':illegaluseofthistypeasanexpression原程序如图所示：switch(k)case1：printf("n进队e=?");scanf(Iatda,;EnQueue(SqQueue&Q1,e);out_Q(&Q1);>break;问题分析：编译不允许在用到函数的时候，再去声明这个函数，即应把声明函数放在函数体

38、最前面。此处SqQueue重复声明，直接把声明去掉即可。2、“'Free':undeclaredidentifier”问题分析：voidfree(void*p)动态释放函数内存空间的函数，这个函数包含在头文件malloc.h中。在程序中，用malloc()函数申请的内存空间要用一个指针类型的变量指示其首地址。此处Free(p)改为free(p),在程序编译中，需要区分大小写。实验中遇至1的问题及解决情况3、调试检测到的错误如下(8):seedeclarationof'SqQueue1rrorC2819:type*SqQueue1docsnothzv电anouerload

39、edmember*op&rdtor(6):seedeclarationoF'SqQueue'rrorC2227:leftof'->Frnntbmustpointtoclss/struct/unionrroirC2819:type'SqQueue'doesnothaveanouerlcuadednember'operator->'(6):seedeclarationof'SqQueue'rrorC2227:leftof'->rear'mustpointtoclass/struct/u

40、nionrrorC28U9:tyipe'SqQueue'doesnothaueanouerlcuadedmenber'operator->'(6):se(?declarationof'SqQueue*rrorC2227:leftof'->Front'mustpointtoclass/struct/unionrrorC2819：type1SqQueue'doesnothaveanouerloadednember1operator'(6):seedeclarationof'SqQueue*问题分析：must

41、pointtoclass/struct/union息为左边必须有类/结构/联合，te义一个后指针变量的函数时，若有“一>”指向一个变量时，所定义的指针变量前面必须加“*”，因此out_Q函数中定义的变量Q应该为*Q,修改如下：voidout_Q(SqQueue裳Q)(charch;inti;if(Q->Front=Q->rear)printF("nQueueisNULL.;Blsei=(Q->Front+1)HAXSIZE;uhile(i?=Q->rear)printf("ridata=d*Q->ai)：|L=(i+1)WXSiZE;&g

42、t;printf("nGata=制d”，Q->ai);printf(fin打回车键，继续")；ch=getch();实验完成后的体会通过上述的实验使我对队列有了一个更加深刻地理解。对于循环队列与链队列的比较，可以从两方面来考虑：从时间上，其实它们的基本操作都是常数时间，即都为0(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储兀素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需野-个指针域，会产一些空间上

43、的开销，但也可以接受。所以在空间上，链队列更加灵活。总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。在实验的过程中，程序的运行出现了很多的错误，所以我必须了严格的检查程序中的每个字符，不断地进行调试。在调试的过程中，也发现了很多应该注意的问题，例如函数的声明应该与函数的应用相一致、函数的名称不能有重复、函数中的指针的引用等。通过实验使我对琐碎的知识点有了一个更加清晰的认识，使很多的知识点联系在一起，问时也锻炼了我的计算机操作的能力，所以我们应该增加这样的实验操作，提高我们的动手能力。在实践操作的同时，也要培养自己严谨的学习态度，在细节上更要注

44、下。例如，函数Free(p)和free(p)的区别，虽然两个函数的意思是一样的，但是在程序编写中意思截然不问，“失之毫厘，差之千里”，平时只有多加注意小枝末节，不粗心大意，才能将不必要的失误尽量避免掉，并且能够节省更多的练习时间。数据结构实验报告（四）提交日期:班级姓名学号上机号67实验树与二叉树名称树形结构是一类非线性数据结构。树结构包括树和二叉树。在树结构中，每个结点都只允许有一个直接前驱结点，但允许有一个以上直接后继结点。树的存储结构和操作实现都比较复杂，但树可以转换为二叉树进行处理。树的建立、二叉树的遍历和哈夫曼编码。一、二叉树的建立和遍历建立二叉树有各种不同的方法。一种方法利用二叉树

45、的性质5来建立二叉树，输入数据时将结点的序号和数据同时给出：序号数据元素。1、用二叉树性质5建二叉树输入数据：11,22,33,44,65,76,13159。测试 数据 与运 行记 录2、中序遍历3 .中序递归遍历二叉树4-计算树中结点个数5 .结束程序运行鬲於原而以择（1,2总4,5,6）34215738693、计算树中结点数4.计算树中结点个数E.结束程序运行请输入您的选择（1,2,3,4,5,6）4421573869二叉树结点总数口=9二叉树叶子结点数n0=4度为1的结点数hl二2度为2的结点数n2=3二、哈夫曼编码利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。哈夫曼树中，从根到

46、每个叶子都有一条路径，对路径上的各分支约定指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”和“1”的序列作为和各个叶子对应的字符的编码，就是哈夫曼编码。1、输入权植输入8个权植5,29,7,8,14,23,3,11.2、输入字符，得出哈夫曼编码请输入字符"dfghjk第1个字符且的编码为QQ01第2个字符制编码为10第3个字符d的编码为111Q第4个字符f的编码为1111第5个字符后的编码为110第6个字符h的编码为01第7个字符j的编码为0000第2个字符k的编码为001一、二叉树的建立和遍历实验中的非递归遍历算法特点是，在所有未被访问的结点中，最后

47、访问结点的左子树的根结点将最先被访问。实验原理如下：根据如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i(1<=i<=n)有：1 .如果i=1,则节点是二叉树的根，无双亲，如果i>1,则其双亲节点为i/2,向下取整2 .如果2i>n那么节点i没有左孩子，否则其左孩子为2i3 .如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1据部实总的序程 根本分验结程流中序遍历：若二叉树非空，则依次执行以下操作：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树voidinorder(BiTNode*p)if(p)inorder(p->lc

48、h);printf("%3d”,p->data);inorder(p->rch);/*inorder*/二、哈夫曼编码对于同一组结点，构造出的哈夫曼树可能不是唯一的。但是对于同一组结点，虽然会产生多棵哈夫曼树，但是它们的带权路径长度(WPL)是相同的，即一组结点有唯一的WPL和它对应。算法如下：1、输入权植。首先将这n个权值分别看作是只有根的n棵二叉树，这些二叉树构成一个集合2、筛选最小权值。选出两棵根结点的权值最小的树作为左、右子树构造一棵新的二叉树，新二叉树的根结点的权值为左、右子树根结点权值之和。voidselectmin(huffmantreeht,inti,in

49、t*p1,int*p2)/*在ht1.i中选两个权值最小的根结点，其序号为*p1和*p2,*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/intj,min1,min2;/*min1,min2分别是最小权值和次小权值*/min仁min2=32767;*p1=*p2=0;for(j=1；j<=i；j+)if(htj.parent=0)/*j为根结点*/if(htj.weight<min1|min1=32767)if(min1!=32767)min2=min1;*p2=*p1;min1=htj.weight;*p1=j；elseif(htj.weight<mi

50、n2|min2=32767)min2=htj.weight;*p2=j;3、从集合中删除左、右子树，加入新构造的树。重复步骤2和3,直到集合中剩下一棵树为止，这棵树就是哈夫要树。实验中遇至1的问题及解决情况1、检测出错误为"function'void_cdeclinorder(structBiTNode*)'alreadyhasabody”。问题分析：alreadyhasabody意为函数名称重复te义，即有两个以上一样的函数名称。解决方法是修正其中的一个函数名称使得函数名称都是独立的。2、程序语句无错，执彳flink.exe时出错，显小为：unresolvedext

51、ernalsymbol"void_cdeclnumb(structBiTNode*)”(?numbYAXPAUBiTNodeZ)”问题分析：所使用的numb(BiTNode*p)只是经过声明，并没用定义函数的内容，因此函数无法使用。应该将numb()函数重新定义再使用。3、检测出相同的4条错误，如图所示：,cpp(21t):errorC2039:'Ichild*:isnotamenberof1htnode1:opCpp1.cpp(9):seedeclarationoF*htnode*cpp(24):errorC2039:1rchildO*:isnotamembernF'

52、;htniode,;opXCppi.cpp(9):seedeclarationof1htnode,cpp(63):errorC2039:'Ichild:isnotamemberof'htnode':opCpp1.cpp(9):seedeclarationof*titnoile,WP(84):errorC2039:'Ichild*:isnotamenberof1htnode1:opCpp1.cpip(9):seedeclarationof1htnoide*问题分析：意为htnode()函数中没有te义lchild这个变重，但是函数体中存在此变量，因此，应该在函数的

53、开始部分添加该变量的定义。4、程序语法没有问题，调试不出错误，但是程序在运行期出错导致程序运行终止。请输入8个权值 请输入第1个权值睛输入第2个权值实验 中遇 到的 问题 及解 决情 况请输入第3个权值： 请输入第4个权值： 请输入第5个权值； 请输入第6个权值； 请输入第?个权值： 请输入第8个权值； 请输入字符adsf gjk529781423311Cppkexe已停止工作出现了一介问题,导致程序停止正配年如累有可用的解决方赛，Windows将关闭程序并通知你.调试Q)问题分析：在哈夫曼树初始化函数中，缺少了十分重要的步骤：指定双亲结点。结果导致运算不能继续，程序终止。应该在选择两个权值最

54、小的根结点之后，添加指定双亲结点的语句：“htp1.parent=htp2.parent=i;"本次实验中，我们主要针对的是二叉树的建立、遍历以及哈夫曼树进行练习。我感觉其中最有难度的就是二叉树的遍历以及赫夫曼编码。通过这次实验使我对二叉树遍历有了一个更深的认识。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数值域的值，那么遍历的实验 完成 后的 体会结果得到一个线性序列。对于树的遍历包括三种：先序遍历、中序遍历、后序遍历。此三种遍历的算法都是递归的，递归终止的条件是二叉树为空。在构造赫夫曼树的过程中可知，在赫夫曼树中不存在度为一的

55、结点。对于每个结点而言，既需要知道双亲的信息，又需知孩子结点的信息。由此，可设定每个结点含有4个域：一个存放权值的数据域以及三个指针域，分别指向双亲和孩子在数组中的下标。在实验过程中，我发现一个很突出的问题，就是平时我们在调试程序时太过于依赖VC6.0软件自带的语句错误检测系统，导致我们错误的认为将自己的程序改到状态显示“0error(s),0warning(s)”就万事大吉了，从而忽视了最基础的对程序结构的检查。最后的结果是程序的语法虽然没有错误了，但是程序依然还是运行不了。因此，在平时的实验过程中，我们不能一开始拿到程序就急于对程序错误的修改。首先拿到程序，我们应该明确这段程序的运行目标，

56、并且大体找出程序的各个函数的框架，接下来需要逐个对每个函数声明及变量的声明进行确认，然后自己试着对函数中的运算进行检查，看是否符合和是否能够达到预想的目标。最后，上机调试，将程序中存在的小毛病、小问题一一改正，只有有条不紊的逐一排查问题，才能又快又好地完成试验任务。数据结构实验报告（五）提交日期:班级姓名学号上机号：67实验名称图图是一种非线性结构。在图的结构中，数据元素之间的关系是多对多的，。之前在运筹学中从理论方面学习过图，本次数据结构实验中主要从图的存储结构和操作实现方面学习图。一、图的邻接矩阵存储（数组表示）、简单输出图有多种存储方式，主要应用的是邻接表和邻接矩阵。本次实验中使用的存储

57、方式是邻接矩阵。输入顶点数n,边数e,然后输入一条边连接的两个顶点的编号i和j。本次实验输入的n=6,e=10,i和j的数值分别为65,61,23,12,54,43,64,14,13,63。011101101000110101101011000101101110测试 数据 与运 行记 录2、回车键入，得到0-1邻接矩阵。二、图的邻接链表存储及递归深度优先遍历i和jo本次实3 6, 3 7, 6 7。图的深度优先遍历类似于二叉树的先序遍历。1、输入顶点数n,边数e,然后输入一条边连接的两个顶点的编号验输入的n=8,e=9,i和j分别为：12,13,24,25,58,48,2、回车键入得到每个顶点的邻接链表i=l32i=25411=3761i=4S2i=582i=673i=763i=845打回车键，维续.俞人¥3、输入V,从顶点Vi开始，对图进行深度优先遍历®Av113762534根据本部分实验总结的程序流程一、邻接矩阵邻接矩阵是图的顺序存储结构，由邻接矩阵的行数或列数可知图中的顶点数。对于无向图，