2023年數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告全集

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告全集實(shí)驗(yàn)一線性表基本操作和簡樸程序.實(shí)驗(yàn)?zāi)康腶(1)掌握使用Visua1C++6.0上機(jī)調(diào)試程序的基本方法;a(2)掌握線性表的基本操作：初始化、插入、刪除、取數(shù)據(jù)元素等運(yùn)算在順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)上的程序設(shè)計(jì)方法。.實(shí)驗(yàn)規(guī)定1。)認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。(2)認(rèn)真閱讀和掌握本章相關(guān)內(nèi)容的程序。(3)上機(jī)運(yùn)營程序。(4)保存和打印出程序的運(yùn)營結(jié)果，并結(jié)合程序進(jìn)行分析。(5)按照你對線性表的操作需要，重新改寫主程序并運(yùn)營，打印出文獻(xiàn)清單和運(yùn)營結(jié)果實(shí)驗(yàn)代碼:1)頭文獻(xiàn)模塊ttincludeiostream.h>//頭文獻(xiàn)動態(tài)分派內(nèi)存空間動態(tài)分派內(nèi)存空間動態(tài)分派內(nèi)存空間ttinclude<ma11oc.h>〃庫頭文獻(xiàn)typedefintelemtype;//定義數(shù)據(jù)域的類型typedefstruct1inknode//定義結(jié)點(diǎn)類型動態(tài)分派內(nèi)存空間elemtypedata;//定義數(shù)據(jù)域structlinknode*next;〃定義結(jié)點(diǎn)指針}nodetype;voidmain()nodetype*head;〃定義節(jié)點(diǎn)指針變量head=create();〃創(chuàng)建一個單鏈表disp(head)；〃輸出單鏈表cout<<“單鏈表長度：“<<len(head)?endl；ins(head,2,0);〃在第二個節(jié)點(diǎn)之后插入以0為元素的節(jié)點(diǎn)disp(head);//輸出新鏈表de1(head,2);〃刪除第二個節(jié)點(diǎn)disp(head);//^^fr^}5.實(shí)驗(yàn)結(jié)果建立一個單鏈表：輸入第1結(jié)點(diǎn)data域值：1輸入第2結(jié)點(diǎn)data域值：2輸入第3結(jié)點(diǎn)data域值：3輸入第4結(jié)點(diǎn)data域值：4輸入第5結(jié)點(diǎn)data域值:5輸入第6結(jié)點(diǎn)data域值:6輸入第7結(jié)點(diǎn)data域值：7輸入第8結(jié)點(diǎn)data域值：8輸入第9結(jié)點(diǎn)data域值:9輸入第10結(jié)點(diǎn)data域值0：輸出一個單鏈表：123456789單鏈表長度：9輸出一個單鏈表：1023456789輸出一個單鏈表：12345678實(shí)驗(yàn)二順序棧的實(shí)現(xiàn).實(shí)驗(yàn)?zāi)康恼莆枕樞驐５幕静僮鳎撼跏蓟瘲！⑴袟？辗瘛⑷霔?、出棧、取棧頂?shù)據(jù)元素等運(yùn)算以及程序?qū)崿F(xiàn)方法。.實(shí)驗(yàn)規(guī)定

(1)認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。(2)分析問題的規(guī)定，編寫和調(diào)試完畢程序。保存和打印出程序的運(yùn)營結(jié)果，并分析程序的運(yùn)營結(jié)果。3?實(shí)驗(yàn)內(nèi)容a運(yùn)用棧的基本操作實(shí)現(xiàn)一個判斷算術(shù)表達(dá)式中包含圓括號、方括號是否對的配對的程序。具體完畢如下：(1)定義棧的順序存取結(jié)構(gòu)。(2)分別定義順序棧的基本操作(初始化棧、判?？辗?、入棧、出棧等)。(3)定義一個函數(shù)用來判斷算術(shù)表達(dá)式中包含圓括號、方括號是否對的配對。其中，括號配對共有四種情況:左右括號配對順序不對的;右括號多于左括號；左括號多于右括號;左右括號匹配對的。設(shè)計(jì)一個測試主函數(shù)進(jìn)行測試。對程序的運(yùn)營結(jié)果進(jìn)行分析。實(shí)驗(yàn)代碼：ftinclude<stdio.h>A#defineMaxSize100typedefstruct{aintdata[MaxSize]；ainttop;}SqStack；voidInitStack(SqStack*st)//初始化棧a{ast->top=-1;}^intStackEmpty(SqStack*st)〃判斷棧為空a{return(st->top==11)；printf(〃棧上溢voidPush(SqStack*st,intx)〃元素進(jìn)棧if(st—>top==MaxSize~l)aprintf(〃棧上溢出！\n〃）；{ast->top++；st->data[st—>top]=x；a出！\n〃）；{aqStack*st)〃退棧(if(st->top==-l)Aprintf(〃棧下溢出\n〃);elsest->top一;}intGettop(SqStack*st)〃獲得棧頂元素if(st—>top==-1)a{aprintf("?？誠n〃);return0;}aelsereturnst—>data[st—>top];}AvoidDisplay(SqStack*st)//打印棧里元素{ainti;printf(〃棧中元素：〃)；afor(i=st—>top;i>=0;--i”printf(n%dn,st->data[i]);printf(〃\n")；)intmain()〃測試]SqStackL；aSqStack*st=&L；aInitStack(st)；aprintf(〃棧空：%d\n〃，StackEmpty(st));for(inti=l;i<10;++i)

Push(st,i)；aDisp1ay(st)；printf(H退一次棧\nPush(st,i)；aDisp1ay(st)；printf(H退一次棧\n);Pop(st)；aprintf(〃棧頂元素:%d\n〃，Gettop(st));Pop(st)Display(st)；實(shí)驗(yàn)結(jié)果:.?元次元元空牡一頂牡.?元次元元空牡一頂牡殘廢根戔廢ynasserp76543254321tocontinue實(shí)驗(yàn)三串的基本操作和簡程序.實(shí)驗(yàn)?zāi)康恼莆沾静僮鳎撼跏蓟?、?lián)接、替換、子串等運(yùn)算在堆分派存儲儲結(jié)構(gòu)上的程序設(shè)計(jì)方法。.實(shí)驗(yàn)規(guī)定1。）認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。（2）認(rèn)真閱讀和掌握本章相關(guān)內(nèi)容的算法并設(shè)計(jì)程序序。（3）上機(jī)運(yùn)營程序。(4)保存和打印出程序的運(yùn)營結(jié)果，并結(jié)合程序進(jìn)行分析。實(shí)驗(yàn)代碼:Windude<stdio.h>#defineMaxSize50typedefstruct{chardata[MaxSize];//存放字符串intlength;//字符串長度}SqString;〃將一個字符串常量賦給串svoidStrAssign(SqString&s,charcstr[]){inti;for(i=0;cstr[i]!='\0';i++)〃這個，\0'代表字符串結(jié)束標(biāo)志，編譯系統(tǒng)自動加上的s.data[i]=cstr[i]；s.length=i;)〃字符串的復(fù)制voidStrCopy(SqString&s,SqStringt)for(i=0；i<t.1ength;i++)s.data[i]=t.data[i];s.length=t.1ength;printf(〃字符串復(fù)制成功了\n〃)；)//判斷字符串是否相等voidStrEqual(SqStrings,SqStringt)(inti,same=l;if(s.1ength!=t.length)same=0;else(for(i=0;i<s.length；i++)if(s.data[i]!=t.data[i])(same=0;break;if(same==0)printf("這兩個字符串不相等\n〃)；e1seprintf(〃這兩個字符串相等\n〃)；}〃字符串的長度voidStrLength(SqStrings){printf("此字符串長度為:％d\n”，s.1ength)；}〃合并字符串SqStringConcat(SqStrings,SqStringt)(SqStringstr；inti;str.length=s.1ength+t.length;for(i=0；i<s.length；i++)str.data[i]=s.data[i];for(i=0;i<t.length;i++)str.data[s.Iength+i]=t.dataEi];returnstr;}〃求子字符串voidSubStr(SqStrings,inti,intj)SqStringstr;intk;str.length=0;if(i<=0||i>s.length||0IIi+j-l>s.1ength)printf(〃子字符串復(fù)制失敗\n〃)；for(k=i-1;k<i+j-l；k++)str.data[k—i+l]=s.data[k]；str.length=j;printf("子字符串復(fù)制成功長度為：%d\n\j);printf("下面輸出此子字符串：\n");for(i=0；i<j；i++)printf('%c”,str.dataEi]);printf(”\n")；)//插入字符串SqStringInserStr(SqStringsi,inti,SqStrings2)intj；SqStringstr;str.1ength=0；if(i<=01|i>s1.length+1)(printf("字符串插入失敗\n〃);returnstr;)for(j=0;j<i-l；j++)str.data[j]=sl.data[j]；for(j=0;j<s2.1ength；j++)str.data[i—l+j]=s2.data[j]；for(j=i-l;j<s1.length;j++)str.data[s2.length+j]=sl.data[j]；str.Iength=sl.Iength+s2.length;printf("插入字符串成功長度為:％d\n",str.length)；returnstr;)〃刪除字符串SqStringDeleStr(SqStrings,inti,intj){intk;SqStringstr；2）創(chuàng)建單鏈表nodetype*create()//建立單鏈表，由用戶輸入各結(jié)點(diǎn)data域之值,〃以0表達(dá)輸入結(jié)束(e1emtyped;〃定義數(shù)據(jù)元素dnodetype*h=NULL,*s,*t;〃定義結(jié)點(diǎn)指針inti=l;cout<V”建立一個單鏈表“VVend1;while(l)(cout?〃輸入第"v<i<<〃結(jié)點(diǎn)data域值：〃；cin?d；..if(d==0)break;//以0表達(dá)輸入結(jié)束if(i==l)//建立第一個結(jié)點(diǎn)h=(nodetype*)mal1oc(sizeof(nodetyPe));〃表達(dá)指針hstr.1ength=O;if(i<=0||i>s.length||i+j>s.1ength+1)(printf("字符串刪除失敗\n");returnstr;)for(k=0;k<i-l；k++)str.data[k]=s.data[k];for(k=i+j-1;k<s.length;k++)str.data[k—j]=s.data[k];str.length=s.1ength-j;printf(〃刪除子字符串成功剩余長度為：％d\n〃,str,length);returnstr;)〃替換字符串voidRepStr(SqStrings,inti,intj,SqStringt)(intk;SqStringstr;str.1ength=0;if(i<=0I|i>s.1ength||i+j-1>s.length)printf（〃字符串替換失敗了\n〃）；for(k=0;k<i—1;k++)str.data[k]=s.data[k];for(k=O;k<t.Iength;k++)str.data[i+k—l]=t.data[k];for(k=i+j-l；k<s.Iength;k++)str.data[t.1ength+k-j]=s.data[k];str.Iength=s.1ength-j+t.1ength；Printf(〃替換字符串成功新字符串長度為：％d\n〃，str.length))//字符串的輸出voidDispStr(SqStrings)inti；if(s.1ength>0)(printf(〃下面輸出這個字符串\n”)；for(i=0；i<s.Iength；i++)printf("%c",s.data[i]);printf(^Xn”)；elseprintf(〃目前空字符串無法輸出\n〃)；?voidmain()(SqStrings;chara口={"wenxian1iangn);〃字符串常量aStrAssign(s,a)；DispStr(s);StrLength(s);SqStringsl,s2,t;//si是待復(fù)制的字符串變量printf(n請輸入一個字符串t:\n〃)；seanf("%sn,t.data);StrAssign(t,t.data);StrCopy(sl,t);〃復(fù)制字符串StrLength(si);DispStr(si);Printf(〃下面判斷字符串s1和字符串s是否相等\n〃);StrEqua1(s,s1);printf(〃下面將字符串si和字符串s合并一起\n”)；SqStringstr;str=Concat(s,si);〃合并字符串DispStr(str);StrLength(str)；SubStr(str,22,7);//求子字符串str=DeleStr(str,15,4);〃刪除字符串DispStr(str)；StrLength(str);printf(“請插入一個字符串s2\n");scanf(n%sH,s2.data);StrAssign(s2,s2.data);str=InserStr(str,15,s2);〃插入字符串DispStr(str)；StrLength(str);printf(〃順序字符串的基本運(yùn)算到此結(jié)束了\n〃)；實(shí)驗(yàn)結(jié)果:-口c<"E:\VC6EN\C0D0U\ISDEV98\BIli\Debug\Textl.exe*4L出an串7串了：符功為字成瞿這等相是S串符字一并合S串符和等字電為長$:SI相和符ab,?敗功符串不si字ng為失成字符子字—這{此g復(fù)率g斷.{X千出anffi呂ffitti一一共弓72序g1S功符ef..串成字ng為符*ia度字符這san串一輸Xi父ef串■非判個將輸xi^J^<子輸Xi攵56

面n字輸cd符字面cd面兩面面2XX子面燙除面n字插34下世此請a囂下lab下這下下R7e此子子下此請g?E:\VC6EM\C0IM01i\ISDEV98\BIB\Debug\Textl.exe4?e2f9此nu^1:7e至t1wr56票on17S2警3424運(yùn)c:串長符12..本to為符功字ng為基y度字成個iamske長個長串y串一7符出an串符an符A56字輸Xi符字S字插34入面n停es匕青2雨Fe匕頁*實(shí)驗(yàn)四編程建立二叉樹,對樹進(jìn)行插入刪除及遍歷的程序1.實(shí)驗(yàn)?zāi)康?1)進(jìn)一步掌握指針變量的用途和程序設(shè)計(jì)方法。(2)掌握二叉樹的結(jié)構(gòu)特性，以及鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)及程序設(shè)計(jì)方法。掌握構(gòu)造二叉樹的基本方法。(4)掌握二叉樹遍歷算法的設(shè)計(jì)方法。.實(shí)驗(yàn)規(guī)定(1)認(rèn)真閱讀和掌握和本實(shí)驗(yàn)相關(guān)的教材內(nèi)容。(2)掌握一個實(shí)際二叉樹的創(chuàng)建方法。(3)掌握二叉鏈存儲結(jié)構(gòu)下二叉樹操作的設(shè)計(jì)方法和遍歷操作設(shè)計(jì)方法。.實(shí)驗(yàn)內(nèi)容1。)定義二叉鏈存儲結(jié)構(gòu)。(2)設(shè)計(jì)二叉樹的基本操作(初始化一棵帶頭結(jié)點(diǎn)的二叉樹、左結(jié)點(diǎn)插入、右結(jié)點(diǎn)插入、中序遍歷二叉樹等)。(3)按照建立一棵實(shí)際二叉樹的操作需要，編寫建立二叉樹、遍歷二叉樹的函數(shù)。(4)編寫測試主函數(shù)并上機(jī)運(yùn)營。打印出運(yùn)營結(jié)果，并結(jié)合程序運(yùn)營結(jié)果進(jìn)行分析。實(shí)驗(yàn)代碼：Winc1ude<iostream.h>typedefstructbitnode(chardata;structbitnode*1chiId,*rchiId；}binode,*bitree?voidereatebitree(bitree*T){charch;cin?ch；if(ch==,O')“*T)=NULL;e1se{K*T)=newbitnode;fi(*T)->data=ch；ereatebitree(&(*T)—>lchild)；ocreatebitree(&(*T)->rchiId);voidinorderout(bitreeT){if(T){^inorderout(T->lchild)；6cout<<T->data?endl；inorderout(T->rchild)5})voidposterder(bitreeT){if(T){?postorder(T->lchild)；postorder(T->rchi1d);。cout?T->data<<end1；intcountleaf(bitreebt){if(!bt)fireturn0;if(bt->lchild==NULL&&bt->rchi1dNULL)return1;(bt->lchi1d)+countle(bt->lchi1d)+countlevoidmain(){bitreebt;createbitree(&bt)inorderout(bt);cout?z//z?endl;postorder(bt);countleaf(bt);c、E:\VC6EN\C0D0N\lSDEV98\BIli\Debug\Textl.exe|ABD0G000CE00F00DECFbFbPressanykeytocontinue實(shí)驗(yàn)五建立有序表并進(jìn)行折半查找1.實(shí)驗(yàn)?zāi)康恼莆者f歸算法求解問題的基本思想和程序?qū)崿F(xiàn)方法。2a,實(shí)驗(yàn)規(guī)定1。)認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法思想。(2)編寫和調(diào)試完畢程序。(3)保存和打印程序的運(yùn)營結(jié)果，并對運(yùn)營結(jié)果進(jìn)行分析。3,實(shí)驗(yàn)內(nèi)容(1)分析掌握折半查找算法思想，在此基礎(chǔ)上，設(shè)計(jì)出遞歸算法和循環(huán)結(jié)構(gòu)兩種實(shí)現(xiàn)方法的折半查找函數(shù)。(2)編寫程序?qū)崿F(xiàn)：在保存于數(shù)組的1000個有序數(shù)據(jù)元素中查找數(shù)據(jù)元素x是否存在。數(shù)據(jù)元素X要包含兩種情況：一種是數(shù)據(jù)元素X包含在數(shù)組中；另一種是數(shù)據(jù)元素X不包含在數(shù)組中(3)數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時實(shí)現(xiàn)，也可以設(shè)計(jì)一個排序函數(shù)實(shí)現(xiàn)。(4)根據(jù)兩種方法的實(shí)際運(yùn)營時間，進(jìn)行兩種方法時間效率的分析對比。實(shí)驗(yàn)代碼：#inc1ude<stdio.h>#include<stdlib.h>#defineMAX_LENGTH100typedefintKeyType;typedefstruct(。intkey;}E1emType;typedefstruct〃。號單元空出(〃。號單元空出ElemTypeelem[MAX_LENGTH];n11ength;}SSTable;intSearch_Bin(SSTableST,KeyTypekey)(ntlow,high,mid;olow=1;high=ST.length；while(1ow<=high)mid=(1ow+high)/2;h->data=d；h->next=NULL;t=h;//h是頭指針else//建立其余結(jié)點(diǎn)(s=(nodetype*)malloc(sizeof(nodetype));s->data=d；s->next=NULL;t->next=s;t=s；//t始終指向生成的單鏈表的最后一個節(jié)點(diǎn))i++；)returnh;)3)輸出單鏈表中的元素voiddisp(nodetype*h)//輸出由h指向的單鏈表的所有data域之值(nodetype*p=h;cout?”輸出一個單鏈表:〃V<end1?M。if(key==ST.elem[mid].key)o。returnmid;else。if(key<ST.elem[mid].key)eghigh=mid-1;oelsegolow=mid+1;)return0;)voidmain()(inti,resuIt;SSTab1eST;KeyTypekey;printf(”pleaseinputlength:11);oscanf(“%d"，&ST.1ength)；ofor(i=l;i<=ST.1ength;i++)(printf(npleaseinputST.e1em:n);。scanf("%d",&ST.elem[i]);oprintf("pleaseinputkeyword:")；oscanf("％d"，&key);result=Search_Bin(ST,key)；

Af(result==O)^printf(nDon*tfind\nn)；。eIse叩rintf(HFindthekey,thepositionis%d\n"，resu1t);)實(shí)驗(yàn)結(jié)果:c\"E:\VC6EK\C0D0N\ISDEV98\BIH\Debug\Text1.ezerindthekey,thepositionis4pleaseinputlength：5pleaseinputST.elen：lpleaseinputST.elen：2pleaseinputST.elen：3pleaseinputST.elen：4pleaseinputST.elen：5pleaseinputkeyword：4Pressanykeytocontinue實(shí)驗(yàn)六建立一組記錄并進(jìn)行插入排序.實(shí)驗(yàn)?zāi)康?1)掌握插入排序算法的思想。(2)掌握順序隊(duì)列下插入排序算法的程序設(shè)計(jì)方法。.實(shí)驗(yàn)規(guī)定(1)認(rèn)真閱讀和掌握教材中插入排序算法的思想。(3)編寫基于順序隊(duì)列的插入排序排序算法并上機(jī)實(shí)現(xiàn)。.實(shí)驗(yàn)內(nèi)容(1)編寫基于順序隊(duì)列的插入排序函數(shù)。(2)設(shè)計(jì)一個測試主函數(shù)，實(shí)現(xiàn)對基于順序隊(duì)列結(jié)構(gòu)的插入排序算法的測試。(3)分析程序的運(yùn)營結(jié)果。實(shí)驗(yàn)代碼：#include<stdio.h>#include<stdIib.h>#defineMAXSIZE100typedefstruct{intkey；}sortkey;typedefstruct{sortkeye1em[MAXSIZE];intlength;}sorte1em；voidInsertSort(sortelem*p){inti,j；for(i=2；i<=p->length;i++){if(p->elem[i].keyvp—〉elem[i-1].key)/*小于時，需將elem[i]插入有序表*/p—>elem[O].key=p->elem[i].key；/*為統(tǒng)一算法設(shè)立監(jiān)測*/for(j=i-l;p->elem[O].key<p->elem[j].key;j--)P->e1e+.key=p->elem[j].key;/*記錄后移*/p->elem[j+l].key=p->elem[0].key;/*插入到對的位置*/)})voidmain(){sorte1em*p;inti;intb[6]={45,23,54,6,4,46};p=(sortelem*)malloc(sizeof(sorte1em));p->length=O;for(i=l;i<7;i++){P->e1em[i].key=b[i—1]；p->length++；}InsertSort(p);for(i=1;i<7;i++){printf("%d",p->eIem[i].key);system("pause")；}實(shí)驗(yàn)結(jié)果：N:\VC6EH\C0Q0H\ISDEV98\BIR\Debug\Text1.exe4623454654字短任意盥祿續(xù).??Pressanykeytocontinue.實(shí)驗(yàn)七建立一組記錄并進(jìn)行快速排序.實(shí)驗(yàn)?zāi)康?1)掌握快速排序算法的思想。(2)掌握順序隊(duì)列下快速排序算法的程序設(shè)計(jì)方法。.實(shí)驗(yàn)規(guī)定(1)認(rèn)真閱讀和掌握教材中快速排序算法的思想。(3)編寫基于順序隊(duì)列的快速排序排序算法并上機(jī)實(shí)現(xiàn)。3,實(shí)驗(yàn)內(nèi)容(1)編寫基于順序隊(duì)列的快速排序函數(shù)。(2)設(shè)計(jì)一個測試主函數(shù)，實(shí)現(xiàn)對基于順序隊(duì)列結(jié)構(gòu)的快速排序算法的測試。(3)分析程序的運(yùn)營結(jié)果。實(shí)驗(yàn)代碼：#include<iostream.h>voidquick_sort(inta[],intlow,inthigh)inti,j,pivot；if(1ow<high){pivot=a[low];i=low;j=high;while(i<j){〃從頂端開始比較值，假如小于標(biāo)準(zhǔn)值，停止while(i<j&&a[j]>=pivot){j;}〃將比pivot小的元素移到低端，下標(biāo)加加if(i<J)a[i++]=a[j];//從底端開始比較值，假如大于標(biāo)準(zhǔn)值，停止

while(i<j&&a[i]<=pivot){i++；}//將比pivot大的元素移到頂端，下標(biāo)減減if(i<j)a[j-]=a[i];}//pivot移動到最終位置a[i]=pivot;〃對左區(qū)間進(jìn)行遞歸排序quick_sort(a,Iow,i-1)；//對右區(qū)間進(jìn)行遞歸排序quick_sort(a,i+1,high);}}voidprint_array(inta[],intn){for(inti=0；i<n;i++){cout<<a[i]<<"，"；}}intmain(){intdata[9]={54,38,96,23,15,72,60,45,83)；quick_sort(data,0,8);print_array(data,9)；return0；}實(shí)驗(yàn)結(jié)果:c：＜"E:\VC6EH\C0H01i\ISDEV98\BIII\Debug\Text1.exe*15,23,38-45,54,60,72,83」96「Pressanykeytocontinueif(p==N