2023年数据结构实验报告2.pdf

《2023年数据结构实验报告2.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验报告2.pdf（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、湖南师范大学工程与设计学院数据结构实验报告姓 名:熊富豪年 级:202 3 级专 业:计算机科学与技术学 号：任课教师：肖柳明开课时间：20232023学年第一学期实验（一）实验时间2 023年12月8日星期四实验地点前栋403实验题目线性表的存储及操作实验目的1）掌握N页序存储结构和链式存储结构的特点；2）掌握常见算法.实验内容一 内容：已知两个按元素值有序的线性表A和B,编程实现：将A和B有序归并成一个按元素值有序的线性表，然后删除值相同的元素。二.环 节：1）从键盘输入两个按元素值有序的线性表A和B的 值；2）根据输入把数据元素分别以顺序存储结构和线性链表存储；3）有序归并成一个新的按元

2、素值有序的线性表C;4）输出显示合并后的线性表C;5）分别在顺序存储结构和线性链表存储结构上删除值相同的元素，并显示删除后的线性表。一.结构定义(逻辑结构、存储结构)：s t r u ct Node in t*elem;in t le n g t h;in t I i stsize;A,B,C;struc t nod e(in t da t a;s tru e t node*n ext;*H A/H B/H C ;二.算法描述(类C 语言+流程图):先将两个表的元素从键盘输入，然后再将两个表相加，得到第三个表。在合并后的表中找到值相同的元素，将后面的元素前移以删除值相同的元素，最后将表的长度减

3、1得到最终的结果。顺序表LA,L B L CSqlis t Merge L is t _ s q(S q list La,S qlist L b,S q 1 i s t Lc)pa=L a.e I e m,p b=Lb.elem,*p c;pa_las t=La.elem+L a.lengt h-1；p b_la s t=Lb.e lem+L b.leng t h-1;Lc.listsiz e=Lc.1 eng t h=L a.length+Lb.length;。p c=Lc.elem=(in t*)ma 1 loc(Lc.1 ist s i z e*s i z e of(i n t);if(

4、!Lc.e lem)分派失败exi t(0);owh i le(pa=pa_ 1 ast&pb 二 pbast)/判断La,Lb 是否结尾“f(*p a=*p b)/比较大小，影响插入的顺序p c+=*pa+;空 1 s e08*pc+=*p b+;。whi 1 e(pa=p a ja s t)也许存在没有插完的情况*pc+=*pa+;w h ile(p b n e xt;p b=Lb-n e xt;Lc=pc=La;whi 1 e(p a&pb)“i f(pa-datad a t a)pc-n ext=pa;pc=pa;pa=pa-n ext;els e g p c-n ext=pb;p c

5、=pb；p b=pb-ne x t;)pc-n e x t=pa?pa:pb;free(L b);ar e t urn Lc;)三.程序清单(关键模块和语句加以注释说明)：#incl u de#inclu d e s t r uct N ode i nt*el e m;int 1 e ngth;i nt listsize;A,B,C;s t ru c t n ode(int data：st r u c t n ode*n e xt;*HA,*HB,*HC；void de 1 _o r d er()(int i,j;f o r(i=0;i C.1 is t si z e-l;i+)if(C.e

6、1 e mi=C.elemi+l)for(j=i+2；j=C.1 i s t siz e-1;j+)o C.elemj-1 =C.elemjJ;)C.I i sts i z e-;)prin t f(n删除后线性表C 的值:n)；for(i=0；i C.1 i stsi z e；i+)(。pr i n t f(u%d”,C.elem i);)int m e rge_ o r der()(in t i=0 J =0,k=0;C.1 i stsize=A.listsize+B.1 is t si z e；C.e lem=(int*)maUoc(C.1 i s t size*s izeof(in t

7、);i f(C.e lem=N U LL)ret u r n 0;wh i 1 e(iA.listsi z e&jB.1 istsize)i f(A.elem i B.elem j)C.e 1 em k+=A.el e mi+;elseC.e 1 e m k+=B.e 1 e m|j+;while(iA.list s ize)(C.e 1 em k+J=A.e 1 e m i+;)while(j B.listsiz e)(C.elemk+=B.e 1 em)+;)p rin t f (线性表C 的值为:n);f or(k=0；k C,li s ts i z e；k+)(pri n t f(d,

8、C.el e mk);)del_o r d er();i nt creat_or d e r()int i;printf(请输入线性表A 和表B 的长度：n”)；s c anf(%d%d n,&A,list s i ze,&B.listsi z e);A.length=A.listsize;B.1 e ngt h=B.1 i s t s i z e;A.e lem=(int*)ma 1 loc(A.lis t size*sizeof(i nt);B.elem=(i nt*)ma 1 lo c(B.list s i ze*si z eof(int);i f(A.e 1 em=NULL|B.ele

9、m=NU LL)retu r n 0;printf(”请有序输入线性表A 的值n )；f o r (i=0;i A.listsize;i+)(s ca n f(u%d”，&(A.elemi);pri n tf(M请有序输入线性表B 的值n”)；for(i=0;i next；whi 1 e(q!=NULL)if(q-da t a!=p-dat a)pr i ntf(%d n,q-dat a);。P=q；q=q-n ex t;)v oid m e rgeis t()(st r u c t node*pa,*p b,*q;HC=q=(struct n o d e *)ma 1 1 o c(size

10、o f(st r uc t nod e);while(HA!=NULL&HB!=NULL)(i f(H A-data da t a)6。q-n e xt=HA；HA=H A-n e xt;else(q-n ex t=HB;HB=HB-ne x t;)q=q n ex t;)wh i le(HA!=NULL)q-nex t=HA;HA=HAne x t;q=q-next;)whil e(HB!=NUL L)q-n ext=HB;HB=HB n e x t;q=q-next;)q=NULL;pr i ntf(“线性表C 的值为:n)；f o r(q=HC-nex t;q!=NULL;q=q-n e

11、 xt)(pr i nt f(%d”,q-data);)deljis t();)v o id creat_ 1 ist()(str u c t n o d e *p,*q;int la,1 b;printf(n请输入线性表A 和 B 的长度:n)scanf(H%d%d ,&la,&1 b)；HA=p=(st r u c t n o d e*)malloc(s i z e o f(s t r u c t n o d e);print f(请输入线性表A 的值：n );wh i le(la 0)esc a n f(%dn,&p data)；Q=p；p=(s t ru c t n ode*)ma 1

12、 Io c(sizeo f(s tr u ct nod e);q-next=p;0)q-n e xt=NULL;HB=p；printf(请输入线性表B 的值:n);wh i 1 e(lb-0)(s canf(n%dn,&p-d a ta)；q=P；。p=(s t r uc t node*)malloc(si z eo f(s tru c t n o d e);q-n e x t=p；)q-next=NULL;m e rge_ 1 is t();main()(c h a r ch;GO：p r i ntf(na：顺序存储 nb:线性链表 n)；ch=g e tc h a r();if(ch=,a

13、)ere a t_o r d e r()；else i f(c h=b )c r e a t _ 1 i s t ();g o t o GO；四.运 营 结 果（运营界面图及说明）:测试数据:A=(3,5,8,11),B=(2,6,8,9,11,15,2 0)1.线性表为顺序存储类型时:2.线性表为链式存储类型时:唱E:展SJ构实验 实验l.exeI o I I 0h:顺序存储 线性检表b请输入线性表A和B的长度：4 7请输入线性表A的值：3 5 8 11情输入线性表B的值：2 6 8 9 11 15 20随性表C的值为:2 3 5 6 8 8 9 11 11 15 20删除后线性表C的值：2

14、 3 5 6 8 9 11 15 20Process exited with return ualue 0rPress any key to continue .3.在选择线性表数据存储类型时输入数据不合法:.:顺序存储，:线性稔表，储表，储表性举质戋莘质戋一选a:b:选a:b:请重新选择!请重新选择!五.分析与总结(算法的时间、空间分析，以 及 改 善)：时间复杂度：O(n)空间复杂度：0(1)这是第一次上数据结构实验课,虽然之前学过C语言，可是真到了自己编写程序的时候，还是不知道该从何下手，编写的过程中更是错误连连，主线就无法运营，后来出来了一个简朴的结果，成就感还是有的。然后继续在现有程

15、序上进行改善，最后出来了这个结果。编写程序还是需要耐心,注意大小写，中文括号之类的小问题，再多看书，基本就能编出简朴的程序，最后在现有程序上进行改善，就能一步步做好.实验（二）实验时间2023年12月1 5日星期四实验地点前栋40 3实验题目栈、队列实验目的L掌握栈、队列的思想及其存储实现2、掌握栈、队列的常见算法的程序实现及应用一、结构定义：（逻辑结构、存储结构）实验内容实验内容：1）运用栈和算符优先算法，实现表达式求值。2）采用顺序存储实现循环队列的初始化、入队、出队和求队列长度的操作。实验环节：1）从键盘输入表达式，求 值，并显示求值结果；2）每次入队或出队操作后，显示队列情况和队列长度

16、。栈：#define S T ACK_ IN I T _ S IZ E 10 0#d e f i n e S T ACKINCR EMEN T 1 0t y p e d e f s t r u e t i n t *b a s e;i n t *t o p；i n t s t a c k s i z e；S q S t a c k ;队 列：t y p e d e f s t r u c t Q No d e （i n t d a t a;s t r u c t Q No d e *n e x t;Q No d e,*Q u e u e Pt r；t y p e d e f s t r u c

17、 t Q u e u e P t r f r o n t;Que u e P tr rear;LinkQueue;二、算法描述：(类 C 语言+流程图)(一)、算术表达式算法基本思想：1、一方面置操作数栈为空栈,表达式起始符#为运算符栈的栈底元素。2、依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶运算符比较优先权后进行相应的操作，直至整个表达式求值完毕(即0 P T R 栈的栈顶元素和当前读入 的 字 符 均 为。op e ran d Typ e e v a lua t eExpression()/算术表达式 求值的算符优先算法。设 OPTR和 OPND分别为运

18、算符栈和运算数栈/0 P 为运算符号的集合In itS tate(O P TR)；Push(OPTR,#)；In i t Sta t e(0 P ND);c=g etchar();W h ile(c!=#|g e t o p(OPT R)!=#)If(!In(c,OP)/当前输入若为运算数则压入OP ND栈。Push(O P N D,c);c=getcha r()；Else S witch(P r e cede(getop(OPND),c)/比较输入运算符和运算符栈顶元素的优先级大小。Case 1，：。/弹出O P T R 栈顶元素和O P N D 的两个栈顶元素进行运算并将结果入O P N

19、D 栈。Pop(OPTR,the t a);弹出 O P T R 栈顶元素Pop(OPND,b)；Pop(OPND,a);/弹出 O P N D 的两个栈顶元素。Pu s h(OPND,Oper a te (a,theta,b)；/进行运算并将结果入 O P N D 栈。Break;0 R e tur n GeTop(OPND);/返回运算结果，此时O P N D 的栈顶元素即为最终运算结果。)二)、队列/构造一个空队列Qin t Ini t Q ueue(S qQueue*Q)(Q-b a se=(QEI e mTy p e*)mal 1 oc(MAX Q SIZE*si z eof(Q E

20、 lemT y p e)；。i f(!Q-base)/存储分派失败ex i t(0);Q f ront=Q re a r=0;下标初始化为 0o r etu r n 1;(/返回Q 的元素个数,即队列的长度i n t Queu e L e ngth(SqQu e ue Q)oretur n(Q.re a r-Q.fr o nt+MA XQSIZ E)%MAX Q SIZE;)/插入元素e为Q的新的队尾元素int EnQueu e(SqQue u e*Q,QElem T y p e e)(“f(Q-rea r+1)%MAXQSIZE=Q-fr ont)/队列满dre t urn 0;Q-b a

21、se Q-re a r=e;oQ-rear=(Q-r e a r+l)%MAXQ S I ZE;re t u r n 1;/若队列不空，则删除Q的队头元素，用e返回其值,并返回1;否则返回0int DeQueue(Sq Queue*Q,QElemTy p e*e)(i f(Q-fr o nt=Q rear)/队列空。return 0；o*e=Q-b aseQ-fro n t;Q-fron t=(Q-fro n t+1)%MAXQ S IZE;r e tur n 1;)三、程序清单：(关键模块和语句加以注释说明)栈：#in c lude#i nclu d e#i nclude OPND栈s t

22、r uc t N D(in t*b ase;int*to p;i nt si z e；OPND；/OPTR 栈struct TRchar*bas e;ch a r*to p;int s i z e;OPTR;/构建OPND空栈st r uct ND InitSt a ck_ND(struc t N D*S)(S-b as e=(i nt*)malloc(10*sizeof(int)；S-top=S-base;S-s i z e=1 ；)/构建OPTR空栈s t ruct TR I n itSta c k _ TR(st r uct T R*S)S-base=(ch a r*)mallo c(1

23、 0*s i z e of(ch a r);S-to p=S-b a se；S-s i ze=l;)用e 返回OPND栈的顶元素s t ruct ND TOP_ND(s t r u c t N D*S,in t*e)(“/if(S-b a se=S-top)/r etur n 0;*e=*(S-top-l);)用e 返回O PTR 栈的顶元素str u c t TR TOP_TR(struct TR S,cha r*e)(“/i f(S-b ase=S-top)/r etu r n 0;*e=*(Stop1);)在O PN D 栈中插入estruc t ND PUSH_ND(str u c t

24、 N D*S,int e)*(S-top)=e；。+(S top);)在OPTR栈中插入es t r uc t TR P U S H_ T R(str u c t T R*S,char e)*(S top)=e;+(S-t op);)/删除OPND顶栈struc t ND P 0 P_ND(struct N D*S,int*e)(/if(S-base=S-top)/r e t u m 0;-(S t o p)；*e=*(S-t op);)删 除 OPTR顶栈st r u c t TR POP_TR(str u ct TR*S,ch a r*e)(”/i f(S-b a s e=S-t op)。

25、/re t ur n 0；-(S-t o p)；*e=*(S-top);)运算符优先级c ha r Precede(char a,char b)in t i,j;char c7J7=。；,；,；),；,。；/=/),：,；：=；swi t ch(a)(cas e i=O;bre a k;。case r i=l;b r e ak;3 case i=2;br e ak;。ca s e 7：i=3;break;ca s e(：i=4;break;case)：i=5;br e ak;。case#：i=6;break；)sw i tch(b)(o case +:j=0；break;case j=1;b

26、re a k;case:j=2;break；。c a s e 7:j=3；break;ca s e(:j=4;br e ak;e case):j=5；br e ak;cas e j=6;b re a k;r e tu r n c i j;)/计 算a和b的值i n t Operate(int a,char th e t a,int b)(int i,j,resu 1 t；i=a;j=b；sw i t ch(t h eta)(ca s e+：r e sul t=i+j；break;ca s e -:r esult=i-j;b r e a k;ca s e*:resul t=i*j;break;c

27、as e 7：r esult=i b r e a k;)r e t u r n r e suit;)i n 11 n(c h ar c)switch(c)c a seoca s e:oc a s e *：cas e 7 :oc a seocas e y：c a s e *#：r e t urn l;b r e a k；d efault:r e t u rn 0；)in t C(cha r z)(in t i,s=0；for(i=0；zi!=0;i+)o s=s*l 0+(z;r etur n s；)int E x pression()(int i,d;ch a r z 5；ch a r x,t

28、heta,c；i nt a,b;InitSt a ck_T R(&OPTR)；P USH _TR(&O P TR,铲)；I n i t S t a c k _ N D(&O P N D);TO P _TR(&O P TR,&x)；c=g e t c h a r()；w h i 1 e(c!=#|x!=,#)(i f(I n (c)=0)(i=0;d o(z i =c;i+；c =g e t c h a r();w h i l e(c =/O&c =9);z i =0;d=C(z );PU S H_ ND(&O P N D,d);)e l s e(s w i t c h(Pr e c e d e

29、(x,c )c a s e 栈顶元素优先级低PUSH_TR(&OPTR,c);c=g e t ch a r();break;case=：-POP_TR(&OPT R,&x);/脱括号并接受下一字符c=g etchar();break;ca s e/退栈并将运算结果入栈POP_T R(&OPT R,&th e ta);POP_N D(&OPND,&b);PO P_N D (&OPND,&a);/deletePUSH_ND(&OPND,Ope rate(a,the t a,b);b reak;)TOP_TR(&OPTR,&x);)T 0 P_ND(&OPND,&d)；r et u m d;ma i

30、 n()(i nt c;printf(请输入要计算的表达式，以字符#结束:n );c=Expr e s s i on();pr i nt f(R e s ult=%d n,c);队列：#inc 1 u d e#in c lu d e s t r u c t N o de(char*e lem；i n t leng h t;int front;i n t r e ar;)Q；创建队列voi d I n i t Queue()(printf(”请输入队列Q 的长度：n H);scan f(d”,&Q.l e n ght);Q.e 1 em=(char*)m a H o c(Q.Ie n g h t

31、*s izeo f(c h a r);Q.front=Q.rea r=1;)队列情况void i npu t _Queue()int i 二 Q.front；print f(nn 此时队列长为dn”，(Q.rea r-Q.f ron t+Q Jen g ht)%Q.1 e n ght);P rint f(n 此时队列Q 中的情况为:n ”)；whi 1 e(i!=Q.rear)(0prin tff%c,Q.elemi);i=(i+l)%Q.leng h t;)入队voi d e n q u eue(cha r*s)(while(*s!=,0,)(i f(Q.re a r+l)%Q.1 e ng

32、 h t=Q.fro n t)0 printf(u队列已满，不能入队n”)；retu r n；Q.el e mQ.r ear=*s;Q.r e a r=(Q.r ear+1)%Q.len g ht;s+；/出队void D e Q u e u e(i n t n u m)(i f(Q .f r o n t=Q.r e a r )(叩r i (。队列为空3”);r e t u r n ;)p r i n t f(”n出队的数据为：nH);w h i l e(n u m 1=0)(i f(Q.f r o n t=Q .r e a r)6 o o p r i n t f(u 队列为空 n)；s”e

33、t u r n ；6)。p r i n t f(M%c ,Q.e 1 e m f Q.f r o n t );Q.f r o n t=(Q .f r o n t+1)%Q.1 e n g h t;n u m-；)i n t C()(c h a r s 20；i n t b;i n t a；In i tQue u e()；whi 1 e(b)P r intf(请选择1.入队 2.出队 0.结束n”)；scanf(n%dn,&b);if(b=1)printf(n请输入要入队的数据：n);s c a n f(s”,&s);enqueue(s);i n p ut_ Que u e()；prin t f

34、(nn);)e 1 se i f(b=2)p i i n if(”请输入出队数据个数:n)；sc a n f(H%d,&a)；De Q ueue(a)；inpu t _Q u eu e();prin t f(u nu);)e 1 s e if(b=0)r etu r n 0;)elseopr i ntf(”请重新输入n)；)m a i n ()c()；四、运营结果：(运营界面图及说明)测试数据：(1)3x6+9-5x(8-3)(2)循环队列大小为ll;d,e ,b,g,h入队;d,e出 队；i,j,k,1,m入队;b出 队;n,o,p,q,r入队表达式求值：循环队列:五、分析与总结：(算法的时

35、间、空间分析，以及改善)时间复杂度：0 (n)空间复杂度：0(1)用栈来做算式的运算最重要的就是排好不同运算符之间的优先级关系，假如OP N D 栈和OPT R 栈做好了的话基本就很简朴了,只需要注意进栈和出栈不要犯错即可。实 验（三）实验时间2023年12月1 5日星期四实验地点前栋4 03实验题目二叉树的常见操作实验目的L掌握二叉树的存储实现。2、掌握二叉树的遍历思想。3、掌握二叉树的常见算法的程序实现。1、输入字符序列，建立二叉链表。2、求先序、中序和后序遍历序列，并显示输出。实验内容3、求二叉树的深度，并显示输出.4、求二叉树的结点总数，并显示输出。一、结构定义:(逻辑结构、存储结构)

36、#in c lu d e#i n c lu d e#include#d efi n e char c h artype d e f struct B iTN ode(cha r d a ta;Bi T Node*lch i 1 d,*r c h i I d;*BiT r ee；二、算法描述：(类C 语言+流程图)void Cr e ate B iTree(B iT r ee*T)/创建树oTElemT y p e ch;o s ca n f(%c,&c h);oif(ch=Nil)/空*T=NU L L；e Ise(*T=(B i Tree)ma 1 loc(sizeo f(B i TNo d

37、 e);。i f(!*T)o exit(O)；d a t a=ch;/生成根结点 C r e ateBiTree(&(*T)-lch i 1 d);/构造左子树CreateB i Tre e(&(*T)-rchil d);/构造右子树0)/返回T 的深度int B iTreeDepth(BiTree T)(in t i,j；if(!T)oreturn 0；“f(T-lchi 1 d)3 i=BiT r eeDepth(T-l c h i l d );“/递归求深度e ls e。i=0;oif(T-rchild)何=BiTre e Depth(T-r c h i I d);吒1 sej=0；re

38、tur n i j?i+1：j+1;)/先序递归遍历T,对每个结点调用函数Visit 一次且仅一次v o id P r eOr d erTr a v e rse(BiT r e e T,i n t(*V i sit)(TEl e m T yp e)(oif(T)T 不空Vi s it(T-data);/先访问根结点PreOrde r Trave r s e(T 1 c h i 1 d,V is it);/再先序遍历左子树“PreOrd e r Traverse(T-rchild,Vi s it)；/最后先序遍历右子树。/中序递归遍历T,对每个结点调用函数Visit 一次且仅一次v oi d I

39、nOr d e r T r a v e r s e (BiTr e e T,in t(*V i si t)(TElemType)(oif(T)(o I n Orde r Tr a v erse(T-lc h ild,Visit)；/先中序遍历左子树。Visi t(T-d a ta);/再访问根结点g I nOrd e rTraverse(Trc h ild,Visit)；/最后中序遍历右子树)/后序递归遍历T,对每个结点调用函数Vis i t 一次且仅一次int PostOrd e rTraverse(B i Tr e e T,int(*Visit)(T E 1 emType)/返回结点个数(

40、oif(T)/T 不空(P ostOrde r Trav e rse(T-l c hi 1 d,Vi s i t)；/先后序遍历左子树。PostOrde r Tr a v e rse(T-rchil d,Vi s it)；/再后序遍历右子树。；/最后访问根结点e int m；8m二 V i sit(T-d ata)；re t u rn m;)三、程序清单:(关键模块和语句加以注释说明)#incl u de#in c lu d e static int k=0：s t r u c t BiTN od e(char d a ta;str u ct BiTNod e*Ichi 1 d,*r ch i

41、 1 d；*head;先序遍历v oi d P r eO r d e r Traver s e(st r u c t B i TN o de*T)(i f(T)(p r in tf (c n,T-data);Pr e Ord e rTrav e rse(T-1 c hild);。Pre0 rderT rav e rse(T-rc h il d)；)中序遍历v o id InOrderTr a vers e(struct B i TNod e*T)(if(T)I n Orde r Traver s e(T 1 child);p r i ntf(%c”,T d a ta);In O rd e rT

42、 ra v e rs e(T-r c hil d);)后序遍历voi d PostOr d erTra v erse(s t r u c t B i TNode*T)(“f(T)P o s t OrderTrav e r s e(T-lchild);P o stO r d erTra v e r s e(T-rchild);pr i ntfC%cu,T-data);)struct B iTNo d e*crea t _ B i()(st r uct BiTNode*p;c h a r c h;ch=get c h a r();i f(ch=,*)p=NULL;els e(i f(!(p=(s

43、t r u c t BiTNo d e*)ma 1 loc(sizeof(s truct BiTNode)retur n 0：p-d a t a=c h；p-lc h ild=c r eatB i()；p-r c hi 1 d=c r ea t _B i();re t urn p；i nt d e p t h(struct Bi T Node*T)(i n t dl,d r;if(T=NULL)re t u r n 0;else(o d 1 =dep t h(T-c h i I d);dr=dep t h(T-r c hi 1 d);if(d l=dr)retu r n d 1 +1;e l

44、s er e tur n d r+1;)计算二叉树的节点个数int s tat i s t i e s (str u ct B i TN o de*T)(if(T=N U LL)retur n 0；else if(T-lc h i Id=NULL&T-rchi 1 d=NULL)k+;r e turn s t at i s t i cs(Tlchil d)+stat i Stic s(T-rchild)+1;)v o id e r g odi c _sta t istic s()(pr i ntf(n二叉树hea d 的先序遍历 为:nH);Pr e Ord e rT r ave r s e(

45、hea d);pr i nt f(n二叉树he a d 的中序遍历为:n);InOrderTraverse(he a d);pri n tf(u n 二叉树h ead的后序遍历为:n)；P ostOr d erTraverse(h e ad)；print f(n 二叉树 h e a d 的深度为:dn”,d epth(h ea d)；pri n t f(二叉树 h ead 的节点总数为：%dn,s t a t istics(head)；ma i n()(he a d=c r eat_Bi()；ergodic_s t a t istics();prin t f(d”，k)；)四、运营结果：(运营

46、界面图及说明)测试数据:输入字符序歹U A B C00 D E0G00F000I D H回旧用RBC DE G F二叉树head的先序遍历为：A B C D E G F二叉树head的中序遍历为：C B E G D F A二叉树head的后序遍历为：C G E F D B A二叉树head的速度为：5二叉树head的平点总数为3Process exited with return value 0Press any key to continue.五、分析与总结:(算法的时间、空间分析，以及改善)时间复杂度0(n)空间复杂度0(n)做二叉树最重要的思想就时递归，在一个函数中可以反复递归，最后求出

47、二叉树的深度、节点数以及它的各种遍历。实验(四)实验时间2023年12月2 2日星期四实验地点前栋40 3实验题目查找的有关操作实验目的1、掌握顺序查找算法的思想及程序实现。2、掌握折半查找算法的思想及程序实现。实验内容1、根据输入数据，采用顺序查找实现某一已知的关键字的查找，并显示查找结果。2、运用实验一建立有序表，采用折半查找实现某一已知的关键字的查找，并显示查找结果。一、结构定义：(逻辑结构、存储结构)#i n elude#in c lude#i n cl u de us i n g nam e s pace std;#defin e i nt i n t#define S SNUM 1

48、1#define BST N UM 6s truct SS T able(i nt*e 1 e m;i n t le n g t h；)；t y p edef struc t B i TNo d e(int d a ta;BiTNode*lc h i Id,*r chi 1 d；*B iTree;二、算法描述:(类 C 语言+流程图)S tatus Sea r c h_Se q(SSTable ST,int key)/顺序查找NT.elem0=k e y;fo r(i=ST.length;!EQ(ST.e 1 e m i,k e y)；-i)；retum i;)St a tus S e arc

49、h_ Bi n(SSTable ST,i nt k e y)折半查找low=l,h i g h=S T Jen g th;while(lo w=high)“mi d=(1 ow+h i gh)/2;qf(EQ(key,ST.e 1 emm i d)ret u r n mid;else i f(LT(k e y,ST.elemmi d)high=mi d-1;else 1 o w=mi d+1;)ret u r n 0;)三、程序清单：(关键模块和语句加以注释说明)#inclu d e#in c 1 ude str u c t(int*a d;i nt 1 e nght;v oid searc

50、h _ fold()int a Jow,mid,high;-P rintf(请输入要查找的数据:n M;s c a n f(d”，&a);1 ow=I；oh i gh=s.len g h t;m i d=(1 ow+h i g h)/2;wh i 1 e(lowV二 high)。if(a=s.adlmi d-1 1)。b r eak;。e 1 se。if(a h ig h)。prin t f(d 在有序表S 中不存在”,a);e Is ep ri n t f(”d 是有序表S 中第(1个数”，a,mid);voi d ere a t_fold()int i；print f(”请输入表格S 的长