2023年新版数据结构实验报告

姓名:关宏新学号：班级：计08４班指导教师:储岳中实验一线性表基本操作的实现一、实验目的1、掌握使用TｕrbｏC2．0上机调试线性表的基本方法；２、掌握线性表的基本操作:插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。二、实验规定1、链表插入、删除和查找算法的代码;2、程序运营结果及分析;3、实验总结。三、实验内容1、认真阅读和掌握本实验的参考程序。2、上机运营本程序,并完善删除、查找等运算。3、保存程序的运营结果,并结合程序进行分析。4、按照你对链表操作需要，重新改写算法并运营，实现链表的插入、删除、查找等运算，并保存运营结果。四、程序流程图、算法及运营结果1-１#iｎｃludｅ＂ｓtdio.h＂#ｉnclude"stｄlｉb.h＂#dｅｆineMAXSＩZE1０0ｓtructSeqＬｉｓt｛ｉｎtｄata[MAXSIZE]；intｌｅｎgｔh;｝;typeｄｅfstructSeqList＊PＳｅqＬｉst;ＰSeｑＬistｃｒeaeNullＬisｔ_seq(){ＰＳeqLｉstpaliｓt=（PSｅｑLiｓｔ)ｍalｌoc(siｚeof（strｕctＳeqLisｔ));if(pａlist！=NULL）｛palist-＞lｅｎｇth=０;ｒeturn（palist);}printf(＂Ｏutofｓpaｃｅ!！\n")；rｅtuｒnNULL;｝ｉntiｓNullLiｓt＿seq(PSeqLｉstpalｉst){return(paｌist->length==0);｝iｎtｉnserｔPre_ｓｅq(PSｅqＬiｓｔｐalｉst，intp,intx）{intq；if（ｐaｌｉst－>ｌenｇth＞=MAXSIZE){printf("oｖerfloｗ!\n")；rｅｔurn(０）;}iｆ(ｐ＜０｜｜p>palist-＞leｎgtｈ){pｒｉnｔf（＂Nｏteｘiｓt!\ｎ"）;rｅturｎ（０)；}ｉf（isNulｌＬｉｓt＿ｓeq(pａｌｉst)){paｌist->ｄａtａ[０]＝ｘ；palist->lenｇtｈ=1;ｒeturn(1);｝ｆor(q=palist->leｎgth-1;q>=ｐ;q－-)ｐａｌiｓt-＞data[q+1]=paliｓt->dａta［q];paｌist->dａta[ｐ]=x;palｉst－>lｅｎgth＝ｐalist-＞lｅngth+1；return（１);｝ｖoidmain(){inｔi；PSeqＬistlｉsｔ;ｌisｔ=ｃreaeNullＬist_seｑ();ｐrintf("插入前的顺序表为：\ｎ");for（i=０；i<=9;i++){insertPre＿ｓeq(list,ｉ,i*i);printｆ(＂%d",ｌiｓｔ-＞daｔa[i]);}iｎsertPre_ｓeq(liｓt,５,5５);printf("\n插入后的顺序表为：\n"）;for（i=0;i<liｓｔ->lｅｎｇth;i+＋)priｎtf("%d",lisｔ－>ｄaｔa［ｉ]);prｉntf("\n");getch();}1-2#iｎclｕde"sｔdiｏ.h＂＃ｉｎｃlude"stdlib.h"#dｅfineＭAXＳIZE１00ｓｔruｃtSｅｑＬisｔ｛iｎtdatａ［MAXSIＺＥ];iｎtlenｇｔh;｝;tyｐeｄefｓtｒuctSeｑList*PＳｅqList；PSeqＬistcrｅａｅNulｌＬist＿seｑ(){PSｅqＬisｔpaliｓt=(PＳeqＬｉsｔ)mａlloc(ｓizeof（ｓtrｕｃtSeqLｉsｔ));ｉｆ（pａlist!＝NULＬ){ｐalｉｓt-＞lｅngtｈ=０;ｒeturn（paｌist);｝prｉnｔｆ(＂Outofｓpａcｅ！!\n"）;rｅｔｕrnＮUＬL;}iｎtisNullＬist＿seq（PSeqLｉｓtpａlisｔ）{ｒetｕrｎ(palｉst-＞length=＝０);}／＊插入*/inｔiｎseｒｔPｒe_ｓeq(PＳeqLｉstpａlist,intp,intx）｛ｉnｔq;if(palist-＞ｌeｎgth＞=MＡXSIZＥ)｛prｉntｆ（"oｖeｒflow!\ｎ"）；reｔurn(0);}if(p＜０|｜p>ｐaｌist->ｌength){prinｔf("Noｔｅｘiｓt!\n");reｔｕｒn(0);}ｉf(isNuｌlList＿seｑ(palisｔ)){ｐａｌist－>data［0］＝x;palist->ｌeｎgｔｈ＝1;ｒeｔurn(1);}fｏr(q=ｐalisｔ-＞lengtｈ-1;q>＝p；q－-）pａlist->daｔa[q+1]=paliｓt－>data[ｑ];palｉｓt－＞dａta[p]＝ｘ;palist->ｌength=ｐaｌist-＞ｌｅngth＋1；ｒeturn(１)；}／*删除*/inｔdeletePre_seq(PＳeqＬiｓtpalisｔ,ｉntｉ){inｔj;ｉf(!pａlist){ｐrintｆ（"表不存在");rｅturn(-1);}if（i<１|｜i＞paｌist->length)｛prｉntｆ（＂删除位置不合法"）;retｕrn(0）;}for(j＝i;j<paｌist－>lｅｎgtｈ;j++)palisｔ->daｔａ［j-1]=palist－>dａtａ[ｊ］;palｉst->lｅnｇth--;retｕrn(1);}/*检索ElｅｍｅntTｙpe*/iｎｔloｃatｉonＰre_sｅq(PSeqLiｓｔｐａｌisｔ,ｉntx)｛intｉ＝0;ｉｆ(!palist){prinｔf（＂表不存在")；ｒeturn(－1）;}while(i<palｉst－>lengｔh＆&palisｔ->data[i]!=x）ｉ++;if(i＞=ｐａlist-＞ｌengtｈ)retuｒn0；elsereｔurn(i+1）;}vｏiｄｍaｉn(）{ｉｎｔi;ＰＳeqListliｓt;lｉsｔ=ｃreａｅNullLｉｓt_sｅｑ(）;printf("插入前的顺序表为：＼n＂)；for（i=0;ｉ<=9;i+＋)｛iｎsertＰre_sｅq（ｌiｓt，i,i*ｉ);priｎtf("%ｄ"，lｉｓｔ－>datａ［i]);}inｓｅrtPｒe_seq(lｉｓt，5，５5);pｒintf(＂\n插入后的顺序表为：\n");foｒ(i＝0;ｉ<lｉｓｔ－>leｎgtｈ;ｉ+＋）ｐriｎtf("%d",list－>ｄatａ［i]);printf（"\n")；printｆ("删除前的顺序表为:＼n");for（ｉ=0;i<=9；i＋+){insｅrtＰre_ｓeｑ（ｌist,i,i*i）；ｐｒiｎtf(＂%d",ｌｉsｔ－>datａ[i]);}deleteＰre＿seq(lｉst,5);printf("\n删除后的顺序表为:\n＂）;for（ｉ=0;i＜=8;i++)prｉnｔｆ（"%d",ｌisｔ->ｄaｔa[i]);printｆ（"\n"）;ｉf(ｌocａｔioｎPre_ｓeq（list，9)=＝０)prｉntf("检索的内容不存在！"）;ｉｆ(locａtｉｏnPre_sｅq(list,9)!=0&&ｌocationPre_ｓeq(list，9)!＝-１)ｐrintｆ("检索的内容下标为:%d＂,ｌocaｔionPｒe＿ｓeｑ(lｉst，9)）;ｐrｉntf(＂＼ｎ＂);ｇeｔch();｝实验二栈的基本操作一、实验目的掌握栈的基本操作:初始化栈、判栈为空、出栈、入栈等运算。二、实验规定1．认真阅读和掌握本实验的算法。2．上机将本算法实现。3.保存程序的运营结果,并结合程序进行分析。三、实验内容运用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为:１、定义栈的顺序存取结构２、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等)3、定义一个函数用来实现上面问题：(1)十进制整数X和Ｒ作为形参（２)初始化栈(3）只要X不为0反复做下列动作将Ｘ%Ｒ入栈,X=X/R(4)只要栈不为空反复做下列动作栈顶出栈,输出栈顶元素四、程序流程图、算法及运营结果2-1#include<ｓtdio．ｈ>＃ｉnclude＜ｓtｄlib.h＞#include＜malloｃ.h>#defiｎeｓｔaｃｋ_iｎｉｔ＿sｉze1０0＃definesｔackincreｍｅnt10typｅdefsｔructsｑstaｃk{int＊base;inｔ*top;intstacｋｓize;}sqｓtａck;iｎtStackIniｔ(sqsｔack＊s){s->bａse=(int*)mａlloc(stacｋ_init_sizｅ*ｓizｅｏf(int));ｉf(！s－>base）ｒｅtｕrn0；ｓ->top＝ｓ－>ｂａse;s->ｓtaｃksizｅ=stacｋ_iｎｉt_sｉze；reｔurn1；｝ｉntＰuｓh（sｑstack*s,ｉnte)｛if(s->ｔop-ｓ->base＞=ｓ->stacksizｅ）｛s->baｓe=(int*)reaｌｌoc(s－>basｅ,(s->ｓｔacｋsizｅ+sｔackiｎcrement)*sizeｏf(ｉnｔ));if（!ｓ->baｓe)retｕrn0；s－>toｐ=ｓ->base+s->ｓtacksize;s－>ｓtackｓｉzｅ+=ｓtacｋincreｍｅnt;}*(s->tｏp++)=e;ｒetuｒｎe;}iｎtPop(ｓqsｔaｃk*s,inte){ｉf（ｓ-＞ｔop==s－＞bａｓe)return0;e=*-－s->top；ｒetｕrne;}intstａckempｔｙ(sqstａｃk*s)｛ｉｆ(ｓ－>top=＝ｓ->ｂａsｅ){reｔurn1；}elｓｅ｛retｕrｎ0;｝｝intcｏnverｓｉｏn(ｓqsｔaｃk*s）{ｉntn,e=0,flag＝0；printf("输入要转化的十进制数:\n＂);scａnf（"%d",&n)；prｉntf("要转化为多少进制：2进制、8进制、16进制填数字!\ｎ");scanf（"%ｄ",＆fｌａg);priｎtf("将十进制数%d转化为%d进制是:\n＂,ｎ，flag);wｈiｌe(n){Push(s,n%ｆｌａg)；n＝ｎ／ｆlａg；}wｈile(！sｔaｃｋeｍpty(ｓ)){e＝Pop(s,e)；swｉｔch（e){casｅ10:printf(＂A"）;brｅak;caｓe11:ｐrｉntf("B");breａｋ;caｓe12:printf("C");breaｋ；caｓｅ13:ｐｒinｔｆ("D")；breａk;caｓe14：ｐrinｔf("E＂)；break;case１5:prｉｎtf("F")；break;ｄeｆauｌt:ｐriｎtf（"％d＂,e);}｝ｐrｉｎtｆ(＂\n");retuｒn0;}intmain（）{sqstａｃks;StackIｎit(&s);conveｒsioｎ(＆s);retuｒn0;｝2－２#ｉnclｕde<ｓｔdlib.h>#deｆｉｎｅMAＸSＩZE１０0stｒuｃtｓtａck{intdata[MAXSIＺE];inｔｔｏｐ;｝;vｏidｉniｔ(strｕcｔstacｋ＊s){s->top=-1;}inｔｅmｐｔy(sｔｒuｃtstaｃk*s）｛iｆ(s->top＝=-１)rｅturn1;ｅlseretuｒn０;}voidpusｈ（structｓtack*s，iｎｔi)｛ｉｆ(s->ｔop==MＡXＳIZE-1){pｒiｎtf（"Ｓtackiｓfull．\ｎ＂）;rｅｔurｎ;}s->toｐ++;s->dａta[s-＞tｏp］=i；}inｔpｏｐ(sｔrｕctsｔacｋ＊s){if(empｔy（s)){ｐrｉｎtf("Stacｋisempｔy．");retｕrn-１;}ｒｅｔｕrｎ(s-＞data[s-＞top-－］)；}voidｔrans(ｉntｎｕｍ)｛strucｔsｔacks;intk；inｉt(＆ｓ);whｉle(nｕm){ｋ=ｎum%１６;push(&s，k）;ｎum=ｎum/16;｝while(!eｍｐty(＆s)){k＝pop(&s);ｉf(k<10)ｐｒintf("%d",k);eｌseｐrｉntf(＂%c",k+55)；}prｉntｆ("＼n");｝mａｉn(）｛inｔnｕｍ；clrscｒ（)；printｆ（"Inpuｔanuｍ（-1ｔｏquiｔ）:\ｎ＂)；ｓｃanf（"%d"，&num);ｗhｉｌe(num!=－１)｛traｎs(ｎum);scanf("%d",&num）;}getch（）;｝实验三串的模式匹配一、实验目的１.运用顺序结构存储串，并实现串的匹配算法。２.掌握简朴模式匹配思想,熟悉ＫＭＰ算法。二、实验规定ﻫ１.认真理解简朴模式匹配思想，高效实现简朴模式匹配；2.结合参考程序调试KＭP算法,努力算法思想；3.保存程序的运营结果,并结合程序进行分析。三、实验内容

1、通过键盘初始化目的串和模式串,通过简朴模式匹配算法实现串的模式匹配,匹配成功后规定输出模式串在目的串中的位置;２、参考程序给出了两种不同形式的nｅｘt数组的计算方法，请完善程序从键盘初始化一目的串并设计匹配算法完整调试KMP算法,并与简朴模式匹配算法进行比较。四、程序流程图、算法及运营结果３－1#iｎｃlude<sｔdio.h>＃incluｄe<stｒiｎg.h>#defｉｎeMAXSＩZＥ10０ｉntStrＩndex_BF(chars[MAXSIＺＥ］,chａrt[MAＸSIZE]){ｉｎtｉ＝1,j=１;whiｌｅ（ｉ<＝s[0]&&j＜=t[０]）｛ｉf(s[ｉ]==ｔ[j]){ｉ++;j++;}ｅlse｛i=i-j+2;j=１；}｝if（ｊ＞t[0]）retｕrｎ（ｉ-t[0]);elｓereturn-1;}inｔmaｉｎ(){chars［ＭAXSIZE];chart[MAXSIZE］;iｎtaｎsｗeｒ，i;ｐｒｉnｔf("SSｔring-->\n＂);gets(ｓ）；printf("ＴString-->＼n")；gｅts(ｔ)；prinｔf("%d",StrIndex＿BF(s,t))；/＊验证*/ｉｆ((anｓｗer=SｔrIndｅx_BF(s，t))>＝０){prinｔf（"\n＂);prinｔf("％s\ｎ＂,s)；for(i=0;i<answer；i+＋）ｐrintf("");ｐｒintf（＂%ｓ",t);pｒiｎtｆ("＼n\nＰaｔteｒnFｏｕndａｔｌoｃatｉon：％d\ｎ"，ａnswer)；}elseprｉntf("＼nPatteｒnNOＴFOUNＤ.\ｎ");ｇetch（)；returｎ0;}3－2#iｎcｌude<sｔｄio．h>＃ｉnｃlude<ｓtriｎg.ｈ＞#dｅfｉneMAXSIZＥ100vｏidｇet_nexｔval(uｎsignedcharpａｔ[]，ｉntneｘtｖａｌ［]）{ｉntleｎｇth=stｒleｎ（pat);ｉnｔｉ=１;ｉｎｔj=0;nextｖａl［1]＝0;while（i<length){if(j==0||ｐaｔ[i-１]==ｐat[j－１]){++i；＋+ｊ;if（pat[ｉ－１]!=pａt[j－1］)ｎｅxtｖaｌ[i］=ｊ;elseｎeｘtvaｌ［i]=nｅxｔｖａl[j］；}ｅlseｊ=nextval[j］;}}ｉntＩnｄex_KＭP(unsiｇｎｅdcｈaｒｔext[］,unｓigｎeｄcharpat[],ｉnｔnexｔｖal[]){intｉ=1；inｔｊ=1;intt_len＝strlen(texｔ)；inｔp_ｌen＝ｓtrlen(pat);wｈile(i＜=ｔ＿len&＆j<＝p＿ｌen）{if(ｊ==0｜|tｅxt[ｉ-１］=＝pat[j-1]){++i;++j;}eｌｓｅj=nextｖal[j];}if(j>ｐ_ｌeｎ)retuｒni－１－ｐ_leｎ;elseretｕrn－１；｝iｎtmaiｎ（）{unｓignedchａrtexｔ［MAＸSＩZE］;ｕnsignedｃhａrpat［MAＸSIＺE]；intneｘtval[ＭAXＳＩZＥ］;ｉntａｎsｗeｒ,i；prinｔf(＂\nBoyｅr－MoorｅStringＳｅａrｃhｉｎgＰrｏgｒａm"）;ｐｒintf("\n===＝＝=＝=＝==＝＝＝＝=＝=====＝==＝==========")；pｒｉntf(＂\n\nTexｔStrｉnｇ-->");gets(text);priｎｔｆ(＂\ｎPａttｅｒｎStriｎg--＞＂);ｇets(pat);ｇet_nexｔval(pａt,nｅxｔｖal）;ｉf((aｎswer=Ｉndｅｘ_ＫMＰ(text,paｔ,neｘtval))>=0){prinｔｆ(＂＼ｎ");pｒinｔf(＂%ｓ\n",texｔ）;ｆor(i=0；ｉ<answer;ｉ++)pｒinｔf（"")；printｆ("%s",ｐat)；ｐｒｉnｔf("＼ｎ\ｎPaｔternFoｕｎdatlｏcation%d\n",aｎｓwｅｒ）；｝ｅlseprintf("\ｎPａtｔｅｒnNOTFOUND.\n"）；gｅtｃh();retuｒn０;｝3-３#iｎｃluｄe"stdiｏ．ｈ＂ｖｏidGetＮexｔ1（ｃｈａr＊ｔ,ｉntnexｔ[］)｛ｉnｔｉ=1,j＝0;neｘt[1］=0;ｗhile(ｉ<=9）{if(j==０｜|t［i］=＝ｔ[ｊ]){++i；++ｊ;neｘt[ｉ]=j;}ｅlｓej＝nｅxt[j];}}ｖoidＧetNext2(chaｒ*t,iｎtnｅｘｔ[]){inｔi＝１,j＝0；next[1]=0;while（ｉ<=９){ｗhｉｌe(j>=1＆＆t[ｉ］!=ｔ[j])j=ｎext[j];ｉ+＋;ｊ++;iｆ（ｔ[i]==t[j］)nｅxt[i］＝nｅｘt[j];elsｅneｘt[i]=ｊ;}}vｏidmain（){chａｒ*p="abcaababｃ＂;iｎtｉ,sｔr[10］;GeｔＮext１(p,str）;ｐrintｆ(＂Putout:\n");ｆｏr(i=１;i<10;i++)prｉntｆ(＂％d",ｓtr［i]);ＧｅｔＮｅｘt2（p,str);prｉｎtf("\n");for（i=1;i<１0;i＋＋)prｉntf("%ｄ",str［i])；ｐriｎtf("\n");getｃｈ();}实验四二叉树操作一、实验目的１.进一步掌握指针变量的含义。2．掌握二叉树的结构特性,以及各种存储结构的特点及使用范围。３．掌握用指针类型描述、访问和解决二叉树的运算。二、实验规定

1．认真阅读和掌握本实验的参考程序。2．按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。3．保存程序的运营结果，并结合程序进行分析。三、实验内容ﻫ以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建对的与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.４初始化方式创建二叉树:所有的空指针均用＃表达,如教材图6-1３相应的二叉树，建立时的初始序列为:AB#D＃#CE##F＃#。四、程序流程图、算法及运营结果4-1#iｎclｕdｅ"sｔdio.h＂#ｄｅfinemaｘ30#dｅfｉneNULL０tｙpedefstｒuctBNoｄe{chardaｔa;/*数据域*/ｓtructBＮｏｄe＊lｃｈild，*rcｈild；/*指向左右子女*/}BinTree;voidpreｏrdeｒ(BinTree＊t）；／*声明先根遍历函数＊/vｏｉdiｎorｄer(ＢinTree*t);／＊声明中根遍历函数*/voiｄpostoｒdｅr(BinTree*ｔ）；/*声明后根遍历函数＊/ｉntleafs(BinTrｅe*b);/*声明求叶子数函数＊/ｉnttｒeｅdeeｐ(BｉnTrｅe*p);/*声明求树的深度函数*/BinTree*ｓwａｐ(BinTree*ｐ);/＊声明互换二叉树的所有结点的左右子树的函数*//＊将字符串中的第ｉ个字符开始的m个字符作为数据生成相应的二叉树＊／BiｎTｒee*crｅ＿tree(ｃhaｒ*str,inｔｉ,iｎtｍ)｛BinＴｒee*ｐ;if(ｉ>=m)/＊无效结点*／reｔｕrnNUＬL；ｐ＝(BｉnTreｅ*)mａlloc（siｚeof（BiｎTrｅe));/*生成新结点*/p->data=str[i];p->lcｈiｌd＝cｒe_tｒee(str,２*ｉ+1，ｍ);/*创建新结点的左子树*/ｐ->rｃhｉld=ｃre_tree(ｓtr，2*ｉ+2，m);/*创建新结点的右子树*/retuｒnp;}voｉｄmaiｎ()｛ｉnti，n；cｈaｒｓtr[max]；ＢinTree*rooｔ;/＊根结点*/pｒintf("请输入二叉树的结点数:")；ｓcaｎf("%d",&n);getcｈａr（）;/*输入数字*／prinｔｆ(＂请输入长度为%d的字符串:",n);for(i=0；i<n;ｉ++)scaｎf("%ｃ＂,&sｔr[ｉ]）;printｆ（"\ｎ＂);rｏot=cre_tｒee(sｔr,0,ｎ)；prｉntf（＂二叉树已成功创建!结点序列为:");foｒ(i＝0;i<n;i++)printf（＂％c",sｔr[ｉ]);prｉntｆ("＼n"）;/*先根遍历*/pｒiｎｔf("\ｎ先根遍历结果:"）;ｐrｅorder(ｒｏｏt）；prinｔf（"\ｎ"）；/*中根遍历*/printｆ(＂\ｎ中根遍历结果:"）;inｏrder(ｒoot）;priｎtf("\ｎ＂)；/*后根遍历＊／pｒintf("\n后根遍历结果：");ｐostorｄer（root);priｎtf("\ｎ");pｒintf(＂＼n叶子数为:%d＼n",lｅafｓ（rｏot)）;pｒintｆ(＂\n树的深度为：%ｄ\ｎ"，trｅedeeｐ(rｏot));printｆ("\n互换左右子树后先序遍历序列为:");pｒeｏrdｅｒ(swaｐ（root));printｆ(＂\n＼ｎ");}voidpｒeorder(BｉnTｒeｅ＊t）{if（t!=NＵLL){printf("%c",t－＞data);if(t－>lｃhｉｌd）{pｒintf("->");prｅoｒder（ｔ->lcｈiｌd）；｝iｆ(ｔ－＞rcｈiｌd){pｒinｔf("－>");ｐreoｒder(t-＞ｒｃhｉld);}}｝vｏidinorder(BｉｎTree＊t）{iｆ(ｔ！＝ＮULL){ｉnｏｒder(t-＞lcｈilｄ）；pｒintf("%c＂，ｔ－>ｄａtａ）；ｉnｏｒｄer(t-＞rcｈｉｌd）;}}ｖoidpoｓtｏrdｅr(BinTree*t){if(t!=NULL){poｓtorｄer(t-＞lcｈilｄ）;pｏsｔoｒｄeｒ（t-＞rcｈｉld）;ｐrｉnｔf(＂％c",ｔ->daｔa);｝}inｔleafs(BiｎTree*b)/*求叶子数*／｛intｎum1,num２;iｆ(b＝=ＮULＬ)returｎ(0）;ｅlseｉf(b->lcｈiｌｄ=＝NUＬＬ&&b->ｒｃｈｉlｄ=＝ＮULL)return（1)；ｅlｓｅ{num1=leafｓ（b->ｌchild）；num２＝leafｓ(b->ｒchiｌd);ｒetuｒn（nｕm1+ｎum2)；｝｝inttrｅedeep(BiｎTreｅ*ｐ）/*求树的深度*/{intｌdeep,rdｅeｐ，deeｐ;if（p==NUＬL)dｅep=0；eｌｓe{lｄｅep=tｒeeｄｅep（p－>ｌcｈiｌd）;rdeｅp=treｅdeeｐ(p-＞rcｈild）;ｄeｅp=(ｌdeep>rdeep?ｌdeeｐ：ｒdeｅp)+1;｝ｒeturndeep；}ＢinTｒee*swap（BｉｎＴree*ｐ)/*互换二叉树的所有结点的左右子树*/{BinTreｅ＊ｓｔack［maｘ];intk＝０;stａｃk[k]＝NULＬ;if（ｐ!=ＮULL）｛ｓtack[+＋k]=p－>lｃhilｄ;ｐ－>lｃｈilｄ=p->rchiｌｄ；p-＞rｃhｉld=stａcｋ[k];ｐ-＞lchild=swａp（p->lchiｌｄ）;p->rchｉｌｄ=swaｐ(p-＞rcｈｉld);｝ｒetｕｒnp；}实验五图的创建与遍历.一、实验目的1.掌握图的含义;２.掌握用邻接矩阵和邻接表的方法描述图的存储结构;3．理解并掌握深度优先遍历和广度优先遍历的存储结构。二、实验规定

1.认真阅读和掌握本实验的参考程序。２．按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3.保存程序的运营结果，并结合程序进行分析。三、实验内容ﻫ以下参考程序是按邻接表的方法创建图,然后用深度优先遍历方法遍历图。请认真理解程序,然后实现图的广度优先遍历。四、程序流程图、算法及运营结果5-１＃includｅ"stdio．ｈ"#dｅfinemaxｓize１02４/*假定线性表的最大长度为1０2４*/#ｄｅｆinｅn10０／＊图的顶点最大个数*/ｔｙpedeｆｉntdatａtype；/*假定线性表元素的类型为整型＊／typedeｆｃｈarVＥXTＹPE；/*顶点的数据类型*/typedeffｌoatADＪTYPE；/＊权值类型*／tｙpedeｆstrｕcｔ{ＶEXTＹPＥvexs[n];／*顶点信息数组*／ADJTYPEaｒｃs[n]［n];/＊边权数组*/ｉntｎum;/*顶点的实际个数*/}GＲＡＰH;／*1.置空图*/ｖoidGraphInit(GRAＰH＊Ｌ){L->nｕm＝０;｝/*2．求结点数*／intGraphVexs(GＲAＰH＊L){ｒｅtｕrｎ(L->nｕm);}／*3.创建图*/voidGraｐｈCreａtｅ(ＧRＡＰH*L)｛iｎti,j;GraphＩniｔ(L)；printf（"请输入顶点数目:");scａnｆ（"%d",&L->ｎum);printf（"请输入各顶点的信息(单个符号）:");fｏr（i=0;i<Ｌ-＞num;i++)｛ffluｓh(sｔdiｎ);ｓcanｆ(＂％ｃ＂,&L->ｖeｘs[ｉ]);}printｆ（"请输入边权矩阵的信息：");foｒ(i＝０;i＜L->num;i++)｛foｒ（j＝0;ｊ<L->nｕm;ｊ＋+){scaｎf("％f",&L->ａrcs[i][j])；}}pｒｉｎtf("图已经创建完毕!");}/*４.图的输出＊/voｉｄGｒａphOｕt(GRAＰＨL){ｉnti,j;priｎｔｆ(＂＼n图的顶点数目为：%d",L.nuｍ);priｎtf("＼n图的各顶点的信息为：\n");for(i=0；ｉ<L.ｎum;ｉ++)prｉntf("%c",L．ｖｅxｓ[i]);ｐrintf("\ｎ图的边权矩阵的信息为：\n"）;for（i=0;ｉ＜L.num;i++){ｆor（j=０;j＜Ｌ.num;ｊ++){pｒintf("%6．2ｆ＂，Ｌ.arcs[i］[ｊ]）;}ｐriｎｔf(＂\n"）;}ｐrｉｎｔf("图已经输出完毕!")；}／*5.图的深度环游*/voｉdDFS(GRAPHg,ｉｎｔｑidian,iｎtmａrｋ[])/*从第ｑｉdian个点出发深度优先环游图g中能访问的各个顶点*／｛intｖ1;mark[qidiaｎ］=1；pｒintf("％c",g.veｘs[qｉdian]);foｒ（ｖ１=０；v1<g.num；v1++){ｉf(ｇ.ａrcｓ[qiｄiａn]［v1]!＝0＆＆ｍaｒk[ｖ1］＝=０)DＦS(ｇ,ｖ1,mａｒk);}}/*６.图的深度环游*/voidGrapｈDFS(GRAＰＨｇ）／＊深度优先环游图g中能访问的各个顶点*／{ｉｎtqidiaｎ,v,v1，mａｒｋ[maxsize］;pｒiｎtf("\n深度环游:＂);prinｔf("\ｎ请输入起点的下标:");sｃaｎf("%ｄ＂，＆qｉｄian);for(v＝０；v＜ｇ．num;v++）{mark[v]=０;｝ｆor(v=ｑiｄiａｎ;ｖ＜g.nｕm＋qidian;v++){v1=v%ｇ.num;if（mark[v1］＝＝0)ＤFS(g,v1,mark）;｝｝/*队列元素的数据类型*／typedeｆinｔDＡTＡTYPE；tｙｐｅdｅfstｒuct｛DＡＴAＴＹPEdata[maxsｉzｅ];/＊队中元素*/inｔｆronｔ,rear;／*队头元素下标、队尾元素后面位置的下标＊/}SＥQQＵEＵE;ｖoidQｕeueIｎit（ＳEQQＵEUＥ*ｓq)/*将顺序循环队列sｑ置空(初始化)＊/{ｓq－>ｆｒont=0;ｓq->rear＝0；}intＱueueIsＥmpｔｙ（SＥQQUＥUEｓq)/*假如顺序循环队列sq为空,成功返回1,否则返回０*/｛iｆ(ｓq.ｒｅar==sq.ｆｒｏnt)ｒeturn(1);elsｅｒetｕrn(0);}ｉntQueueFrｏnt(SEQQUＥUEｓq,DＡＴＡTYＰE*e)/＊将顺序循环队列sｑ的队头元素保存到e所指地址,成功返回1，失败返回0*／{if(ＱｕeuｅIsEmpty(ｓｑ)){printf（"qｕeueisemｐty！\n")；ｒｅturn0;}eｌse｛*ｅ=sq.dａtａ［（sq.fronｔ)];return1;}｝inｔＱueuｅＩn(SEQQUEUＥ*ｓｑ,DAＴATYPEx)/*将元素x入队列sq的队尾,成功返回1，失败返回0*／{ｉf(ｓq－＞fｒonｔ=＝(ｓq－＞ｒear+１)%maxｓize）｛printf("qｕeueisfull!\n")；reｔurｎ0；}elsｅ｛sq-＞ｄaｔa［sq－＞rear］=x;sq－>rear=（sq-＞rｅaｒ＋1)％ｍaxsize;ｒｅtuｒn（１);}}ｉntQueueOut(SEQＱＵEUE＊sｑ)/*将队列sq队首元素出队列,成功返回１,失败返回0*/｛ｉｆ(QueueIｓEmpty(＊ｓq))｛priｎtｆ("ｑｕｅueisｅｍpｔy!\ｎ＂);retuｒn0;}eｌse｛sq-＞ｆroｎｔ=(ｓq->ｆｒｏｎｔ＋1)％ｍaxｓｉze；return1;}}/*7.图的广度环游*/voidBFS(GＲAPＨg，intv,intmarｋ[])/*从v出发广度优先环游图ｇ中能访问的各个顶点*/{intv1,v2；SEＱＱUEUＥｑ;QueuｅIｎit(&q）；QｕeｕeIｎ(&q,v)；mark[v］=1;printｆ(＂%c＂,g.veｘs［ｖ]);while(QueueIｓEｍｐtｙ(q）＝=0){QueuｅＦront(q,&v1)；QuｅｕeOut（&q）;fｏr(v2=0;ｖ2<g.ｎum;v2+＋）{iｆ(ｇ.ａrcs[v1][v2］!=0&＆ｍarｋ[v２]=＝0){QueueIn（&ｑ,v2);mark[v2]＝1；ｐrｉntf("％c＂,ｇ.vexｓ[v2])；}}}}/*8.图的广度环游*/voidGｒapｈBFS(GRAPＨg)/＊深度优先环游图ｇ中能访问的各个顶点＊/｛iｎtｑidian,v,v1,mark[mａxsｉze］;prｉntf("＼n广度环游:"）;ｐrinｔf(＂\n请输入起点的下标:");scanｆ（"％d",＆qｉｄｉａn);for(ｖ=０;v<g.num;v++)｛ｍａrk[ｖ]=0;｝fｏr（ｖ=qidiaｎ;ｖ＜g．num＋qidiａn;v＋+){v1=v%ｇ.nｕm;if(mark[v１]==０)ＢFS(g,v1,mａrk);｝}voｉdmaiｎ()｛GRAＰHtu；ＧrａphCｒｅate(&tu）;ＧraｐhＯut(tu)；GraｐhDFS(tu)；ＧraphＢＦＳ(tu);}实验六查找的实现一、实验目的1.通过实验掌握查找的基本概念;2．掌握顺序查找算法与实现；３.掌握折半查找算法与实现。二、实验规定１．认真阅读和掌握本实验的参考程序。2.保存程序的运营结果，并结合程序进行分析。三、实验内容1、建立一个线性表,对表中数据元素存放的先后顺序没有任何规定。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段,数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。2、查找表的存储结构为有序表，输入待查数据元素的关键字运用折半查找方法进行查找。此程序中规定对整型量关键字数据的输入按从小到大排序输入。四、程序流程图、算法及运营结果算法:6-1#incｌｕdｅ"tｙpe.ｈ"intseａｃh_seq（SＳTableA,EｌemTypekeｙ)｛ｉnti,n;n=Ａ．ｌength;A.eｌem[n].key＝kｅy；for（i=0;A．ｅlem[i］.key!＝key;++i）rｅｔurni；}6－２#incｌｕｄｅ"type.h"iｎtBinsｃh(SSＥｌemenｔA[],intlｏw,iｎｔhiｇｈ,EｌemＴypeK）｛iｎtmid;if(low<＝ｈｉｇh){iｎｔmid=（lｏw+high)/２;iｆ(K==A[miｄ].keｙ)rｅｔurnmid;／＊查找成功，返回元素的下标*/ｅlseif（K<Ａ［miｄ].key)ｒeｔurnBinｓch（Ａ，low,ｍid-１,K);/*在左子表上继续查找*/elseretuｒnBiｎｓch（A，mｉｄ+1，high,K);／*在右子表上继续查找*/}ｅlsereｔurn0;/*查找失败，返回0*/}实验七各种排序方法的比较一、实验目的1．通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的结识。2．掌握各种排序方法的基本思想和算法实现。３.可以灵活地选用某种排序方法解决问题。二、实验规定1.认真阅读和掌握本实验的参考程序。2.保存程序的运营结果，并结合程序进行分析。三、实验内容编写一个程序,对所给的数据(程序中给出或通过键盘初始化均可)进行排序，规定尽也许多的选择不同的排序算法,并显示排序前和排序后的结果。四、程序流程图、算法及运营结果算法：常用排序算法总结及Ｃ源程序ﻫ／*直接插入排序＊/

vｏidInｓertＳoｒｔ(ｉnt*ouｔ，int*oｐ,intｌengtｈ)ﻫ{ﻫinｔi,j;ﻫinｔdata;ｍemcｐy(out,op，lengｔh＊sizｅof(iｎｔ）);ﻫfor(i=1；i<ｌength;i++)

｛ﻫｄata=ouｔ;ﻫfｏr(j＝i-1;data<oｕt［ｊ]＆&ｊ>＝0;j--)ﻫ｛ﻫ

out[j+１]=ｏｕt[j];ﻫ}ﻫout［j＋１]=ｄａtａ;ﻫ}

}

/＊折半插入排序*／

voidBＩnseｒtＳｏｒt(iｎt*oｕt,iｎt*op,inｔlengｔh)ﻫ{ﻫｉntlow,mid，high;

inti,j，daｔa;ﻫmｅmcｐy(oｕ