數(shù)據(jù)結(jié)構(gòu)上機試驗報告

吉林大學(xué)數(shù)據(jù)結(jié)構(gòu)實驗報告班級姓名學(xué)號姓名學(xué)號實驗項目第一次上機實驗性質(zhì)□演示性實驗□驗證性實驗回操作性實驗□綜合性實驗實驗地點計算機樓A108機器編號指導(dǎo)教師江麗實驗時間2017年11月24日―分一、實驗?zāi)康募耙箢}目1線性表、堆棧、隊列相關(guān)算法的實驗驗證[實驗?zāi)康腯驗證單鏈表及其上的基本操作。[實驗內(nèi)容及要求]1、 定義單鏈表類、鏈?zhǔn)綏ｎ?、順序隊列類?、 實驗驗證如下算法的正確性、各種功能及指標(biāo)：1） 單鏈表插入操作：分別在當(dāng)前結(jié)點后、表頭、表尾插入值為x的結(jié)點；2） 單鏈表刪除操作：分別刪除表頭結(jié)點、表尾結(jié)點和當(dāng)前結(jié)點的后繼結(jié)點；3） 查找操作：查找值為x的元素在單鏈表中出現(xiàn)的位置（是鏈表中的第幾個元素）；4） 壓棧和彈棧操作；5） 出隊和入隊操作（順序存儲）3、 為便于觀察程序的運行結(jié)果，設(shè)計的輸出函數(shù)能在輸出設(shè)備上以圖形或表格或其它直觀的形式輸出計算結(jié)果。例如可將鏈表輸出成如下形式：[1]^[2]T[3]T[4]T[5]4、 測試程序時，對所有輸入變量取遍各種有代表性的值。5、 為了增強程序的可讀性，程序中要有適當(dāng)?shù)淖⑨?。題目2（選做題）：應(yīng)用單鏈表實現(xiàn)一元多項式及其相加。[實驗?zāi)康腯應(yīng)用單鏈表解決實際應(yīng)用問題。實驗內(nèi)容及要求：1、 使用自己已定義的單鏈表類。2、 編寫程序?qū)崿F(xiàn)一元多項式的輸入、輸出和加法運算。3、 為便于觀察程序的運行結(jié)果，設(shè)計的輸出函數(shù)能在輸出設(shè)備上以圖形或表格或其它直觀的形式輸出計算結(jié)果。4、 為程序制定測試方案，對所有輸入變量取遍各種有代表性的值。5、 為了增強程序的可讀性，程序中要有適當(dāng)?shù)淖⑨尅６?、實驗設(shè)備、軟件PC，windows10Professional，VS2015三、實驗過程（算法設(shè)計、代碼編寫、程序調(diào)試、測試數(shù)據(jù)設(shè)計、測試、報告撰寫)基本數(shù)據(jù)結(jié)構(gòu)選擇及算法設(shè)計：單鏈表類的使用，隊列類的使用，棧類的使用。1、單鏈表類先定義結(jié)點類，包括數(shù)據(jù)類型定義和指向下一個節(jié)點的指針，同時定義指針P,其中P為頭指針，為了讓P在程序結(jié)束后時刻指回頭指針，定義函數(shù)getHeadPoint()。構(gòu)造函數(shù)設(shè)置表頭指針為空。析構(gòu)函數(shù)用于清空鏈表，釋放內(nèi)存。append(intelement)函數(shù)為從尾部添加結(jié)點并保存數(shù)據(jù)element。addasFirst(intelement)函數(shù)為從頭部添加結(jié)點并保存element。addAfter(intelement,intlocation)函數(shù)從指定位置將元素生成節(jié)點添加鏈表，如從鏈表第location二二2個元素后，添加element==23remove(intelement)刪除指定元素值大小的所有結(jié)點，判斷是否存在。printAll()打印所有鏈表元素值2、棧實現(xiàn)較為簡單，操作函數(shù)僅有兩個，所以自己增加了難度使用類模板結(jié)點類：在結(jié)點中我加入了函數(shù)，使程序壓棧更加快捷。StackNode(TData,StackNode*p)p指向下一^指針。棧類：構(gòu)造函數(shù)Stack()：top(NULL){}；定義頂部節(jié)點為空。析構(gòu)函數(shù)~釋放內(nèi)存。Push(constT&item)，壓棧。調(diào)用結(jié)點類的構(gòu)造函數(shù)。Pop(),判斷棧內(nèi)是否還有元素，彈棧。Clear()，手動清空，類似析構(gòu)函數(shù)。IsEmpty(),判斷頭指針是否為空。3、隊列有了前兩次的調(diào)試，第三次應(yīng)用很順利，使用類模板。隊列定義結(jié)點類和定義類結(jié)點構(gòu)造函數(shù)為next為空。隊列類：其中定義頭指針first和尾指針rear。構(gòu)造函數(shù)定義頂部節(jié)點為空。析構(gòu)函數(shù)~釋放內(nèi)存。Push()判斷添加的結(jié)點是否為第一個，第一個單獨添加。Pop()判斷刪除的節(jié)點是否為最后一個，最后一個輸出出隊失敗。4、多項式使用單鏈表代碼，將鏈表結(jié)點改為多項式結(jié)點，數(shù)據(jù)存放分別為指數(shù)和系數(shù)，改造完成后重新編寫多項式創(chuàng)建代碼。插入部分大多沿用鏈表中的算法，在此僅對加法作出解釋。AP1.［判斷空］IFpa=NULLANDpb=NULLRETURN.AP2.［加法］IFpa-〉expn<pb-〉expnTHEN((s=paANDpc->next=pa.)IFpa->expn〉pb-〉expnTHEN(s=pbANDpc->next=pb.)ELSE(IFpa-〉coef+pb-〉coef!=OTHENtc-〉next=newnode)AP3?［未掃描完的余下結(jié)點復(fù)制并鏈接到pc單鏈表之后］IFpa!=NULLTHENpv-paELSEp-〈pbtc-〉next=newnodeRETURNpc.代碼編寫(僅填寫關(guān)鍵代碼)：單鏈表部分：//返回表頭指針node*getHeadPoint();//逐個添加鏈表元素， 尾部添加voidappend(intelement);//從首部添加鏈表元素voidaddasFirst(intelement);//從指定位置將元素生成節(jié)點添加鏈表，如從鏈表第location==2個元素后，添加element==23voidaddAfter(intelement,intlocation);//刪除指定鏈表元素值大小的所有結(jié)點voidremove(intelement);//打印所有鏈表元素值voidprintAll();棧部分：voidPush(constT&item)TPop()voidClear(void)intIsEmpty(void)const隊列部分：voidinitSqueue(Squeue*);voidemptySqueue(Squeue*);voidfullSqueue(Squeue*);voidInsqueue(Squeue*,int);voidOutsqueue(Squeue*,int*);voidPrintSqueue(Squeue*);多項式部分關(guān)鍵代碼：voidInitList(PolyNode*&L) //初始化多項式單鏈表，生成一個頭結(jié)點voidInsertNode(PolyNode*&L,floatc,inte,inti)//在多項式鏈表的第i個位置插入結(jié)點voidprint(PolyNode*L) //打印多項式voidCreateList(PolyNode*&L,floatC[],intE[],intn) //創(chuàng)建多項式單鏈表PolyNode*AddPoly(PolyNode*L1,PolyNode*L2) //一元多項式相加程序調(diào)試過程記錄：1、 從結(jié)尾添加結(jié)點，忘記了返回頭指針，導(dǎo)致接下來的程序不能運行。2、 刪除結(jié)點時，對于重復(fù)結(jié)點欠考慮，導(dǎo)致了很嚴(yán)重的問題。包括：刪不了頭，刪不了兩個頭，當(dāng)兩個重復(fù)節(jié)點相鄰時，只能刪除一個，都是邏輯問題。在第一次運行時均沒有發(fā)現(xiàn)。后來單獨寫了刪除頭結(jié)點的代碼并判斷，刪除重復(fù)節(jié)點后直接執(zhí)行下按一次循環(huán)(continue)，解決了這些問題。3、 發(fā)現(xiàn)只有邏輯刪除沒有物理刪除，又在加入了delete。4?多項式創(chuàng)建出現(xiàn)問題，重新調(diào)整類的結(jié)構(gòu)，定義了不同的數(shù)組。測試數(shù)據(jù)設(shè)計:單鏈表：創(chuàng)建鏈表，用頭、尾、選擇插入各個方法依次插入并輸出檢測。刪除時，刪除：不存在的一個數(shù)，頭，雙頭，中間，雙中間，尾，雙尾。（雙意思是重復(fù)的數(shù)據(jù)）充分考慮到這些問題。依次測試。lirt愉thswendi魚；11吐1伽譏衛(wèi)聞旳!規(guī)；LLstmtL.wendilJ;UEWestL.ajcmdJW1;丄L5tTestL.0tLDW.LI)；//cnut竝Ihl譏erd];LLStTestL.aiil^lTStl?)；ListTutL.aiduZimt>0);lirtTestl.aMLtfterl'LH:Li5i:TutL.aidlJtErl^,<1.MstTenLiiriDtULO://mt?'Nil'-<<end];丄LEtleStL.TflKWlll；LL5tTe51L.reK^i%l;ListTestL.tbkw?;LLstTestL.TfK^卿;LirtTutL.pricstUL;systiiCpausc')；刑巴Q； 棧：測試壓棧。彈棧。彈空棧。intmain(){//tout?kJiellci莎&rl『<<endl:StaLk<int\s;3.PUStl(l)；s.Push(2);s.Push(3);s.Pop0:s.Pop0;S.Pop0;2-POP0；systernCpause ;return0;隊列：測試入隊。出隊。出空隊.ccut?"岀錄的元素是廣?舊?$ndl;OMtsq口電□己l&au^iiBr4e1;wut?*岀趙的元圣是:*<<c<<cndl:Outsqucuc(Aqueue,.4eJ;ccsut?"岀Ik的TIG童擔(dān)；*■?e?ondl;OutsqueuetAqueue3Sc);com?"岀認(rèn)的苑栄是：*?e?endl;CXitsqueue(44jueue,4e):"CQUt?"岀臥.的7E當(dāng)是；*<<C<<ctldl： OutS^JUFWCliqiHHICjSfi}:cwt?"岀船.的元當(dāng)是;*<<c?cndl:Cutsqueuel'^ueuer4el;cour?"出臥.的元琴是「C<&?endl;I^squeue^iqdeli匕L0);Oitsqu^ue(&Queuet4e);ccut?"出/的祠專是廠?<a?eiidl;OutEQueuel&queuerAel;cout?"出錄的元呈■是：■?e?endl;Outsaucu亡l&Qg叫4eJ;ccxjt?*■岀毆的元S-S/?e?endl;PrintSqueue(S<jufub);

棧4l3)E2多項式:測試多項式的創(chuàng)建和加法測試結(jié)果記錄:單鏈表:隊列:冏I甜田鶯軸■.址1-棧4l3)E2多項式:測試多項式的創(chuàng)建和加法測試結(jié)果記錄:單鏈表:隊列:冏I甜田鶯軸■.址1-!intEl[]={L0.InitList(La);InitList(Lb);InitList(Lc);CreateList(La.CLCreateList(Lb,C2agit?"原多項式為孑*?endl;print(La);print(Lb);cout?"寥頂式相力D的結(jié)果為i刊<<endl;U二:AddPaly(La.Lb);print(Lc);Mi*■片最dt賽nd.帕、?||■肝加4]Lifitab-daiflm^tUiIIIIEIISQPolyNods+La,^Lb,*Lc;floatCJ[]={3a7a9,5：■,C2.]=(8,22,-9〕：8.17\E2[]-{1,7.8}：FFBnBlRtf-印圧多項式:^.ii-hai■.*eii?；.j'a±llly.*1r^riwra*-'--：iliiir.-Mix.-.?i實驗過程總結(jié)（對所作程序進行分析、評價運行效果，總結(jié)遇到的問題和解決辦法）：刪除結(jié)點時，在尾節(jié)點刪除會經(jīng)常遇到指針空導(dǎo)致程序崩潰?，F(xiàn)在在對尾結(jié)點進行操作的時候,多了保護指針。胡銳實驗項目實驗性質(zhì)實驗地點計算機樓A108學(xué)號第二次上機□演示性實驗□驗證性實驗操作性實驗□綜合性實驗機器編號I54160317胡銳實驗項目實驗性質(zhì)實驗地點計算機樓A108學(xué)號第二次上機□演示性實驗□驗證性實驗操作性實驗□綜合性實驗機器編號I54160317指導(dǎo)教師江麗實驗時間2017年12月1日―時分一、實驗?zāi)康募耙箢}目1：二叉樹相關(guān)算法的實驗驗證從文件創(chuàng)建一棵二叉樹，先根、中根、后根遍歷二叉樹；在二叉樹中搜索給定結(jié)點的父結(jié)點；搜索二叉樹中符合數(shù)據(jù)域條件的結(jié)點；從二叉樹中刪除給定結(jié)點及其左右子樹。題目2(選作)：森林的遍歷算法的實驗驗證創(chuàng)建森林；森林的先根遍歷的遞歸和迭代算法；森林的后根遍歷的遞歸和迭代算法；森林的層次遍歷算法。二、 實驗設(shè)備、軟件PC，windows10Professional，VS2015三、 實驗過程(算法設(shè)計、代碼編寫、程序調(diào)試、測試數(shù)據(jù)設(shè)計、測試、報告撰寫)基本數(shù)據(jù)結(jié)構(gòu)選擇及算法設(shè)計：1、 在二叉樹中搜索給定節(jié)點的父節(jié)點Fatherl.[t=NULL?]IFt=NULLTHEN(q<-NULL.RETURN.)Father2?[t為所求？]IFLeft(t)=pORRight(t)=pTHEN(q<-t.RETURN?)Father3?[遞歸]Father(Left(t),p.qL)IFqL!=NULLTHEN(q<-qL.RETURN.)ELSEFather(Right(t),p.qR.RETURN?)2、 搜索二叉樹中符合數(shù)據(jù)域條件的節(jié)點(遞歸)3、 從二叉樹中刪除給定結(jié)點及其左右子樹DST1.[t=NULL?]IFt=NULLTHEN(RETURN.)IFData(t)=itemTHEN(q<-t.RETURN?)DST2?［t=root?］IFt=rootTHEN(Del(t).rootv-NULL.RETURN)Find(Right(t),item.p)RETURN.DST3?［找t的父節(jié)點q］pv-t.Father(root.p.q)DST4?［修改q的指針域］IFLeft(q)=pTHENLeft(q)q=NULL.IFRight(q)=pTHENRight(q)q=NULL.DST5?［刪除p及其子樹］Del(p).3、刪除結(jié)點p及其左右子樹(遞歸)5、 先根遍歷算法(遞歸)6、 中根遍歷算法(遞歸)7、 后根遍歷算法(遞歸)8、 創(chuàng)建二叉樹CBT1.［讀數(shù)據(jù)］ifstreamfin("text.txt");CBT2?［p=stop?］IFp=stopTHEN(t=NULL.RETURNt.)CBT3?［構(gòu)造左子樹］CBT(Left(t)).CBT4.［構(gòu)造右子樹］CBT(Right(t)).代碼編寫(僅填寫關(guān)鍵代碼)：?題目1//先根遍歷并輸出以節(jié)點t為根節(jié)點的子樹voidPreOrder(BinTreeNode〈T〉*t)//中根遍歷并輸出以節(jié)點t為根節(jié)點的子樹voidInOrder(BinTreeNode<T>*t)//后根遍歷并輸出以節(jié)點t為根節(jié)點的子樹voidPostOrder(BinTreeNode〈T〉*t)BinTreeNode<T〉*BinTree〈T〉：：Create()//找到父節(jié)點BinTreeNode<T>*Father(BinTreeNode〈T〉*t,BinTreeNode<T>*p)//尋找結(jié)點BinTreeNode〈T〉*Find(BinTreeNode〈T〉*t,constT&item)?題目2程序調(diào)試過程記錄:1、文件輸入出錯。輸入值為12453.然而過程中跳過了第一個數(shù)，意識到是指針出了問題。以下是錯誤代碼和運行結(jié)果，其中第一位1并未輸入到數(shù)組s中。while((fin.get())!=EOF){fin>>s[i];i++;}?]C\U5&n5-\ThinkPacftDocunientsY2499旳的0二賈樹先棍遍歷結(jié)果為;—叉樹中棍遍歷結(jié)果為;42定叉樹后根飾結(jié)果為匚i5更改了操作順序，使用了dowhile。更改后：do{fin>>s[i];i++；}while((fin.get())!=EOF)測試成功測試數(shù)據(jù)設(shè)計:構(gòu)建一棵二叉樹如圖所示:構(gòu)建好之后先根中根后根遍歷輸出。中間兩個地址是先取某一個點的地址，然后尋找他孩子節(jié)點的父節(jié)點，測試父節(jié)點尋找函數(shù)，地址相同證明尋找正確。刪除2及其子樹后，二叉樹僅剩下13,輸出正確。測試結(jié)果記錄：二空擁中根盲歷結(jié)臬九a25L二夏盟后祁卷?円姑卑為?4523L（irrEESEOULClEau經(jīng)詛E賺二乂訶弟二I結(jié)點忌耳子冊右先抿遛用結(jié)累.為:1實驗過程總結(jié)（對所作程序進行分析、評價運行效果，總結(jié)遇到的問題和解決辦法）：題目1：程序運行比較穩(wěn)定，功能基本實現(xiàn)。題目2：功能基本實現(xiàn)。遇到的問題及解決辦法見調(diào)試經(jīng)過記錄。

姓名胡銳學(xué)號54160317實驗項目第三次上機實驗性質(zhì)□演示性實驗□驗證性實驗操作性實驗□綜合性實驗實驗地點計算機樓A108機器編號指導(dǎo)教師 江麗 實驗時間姓名胡銳學(xué)號54160317實驗項目第三次上機實驗性質(zhì)□演示性實驗□驗證性實驗操作性實驗□綜合性實驗實驗地點計算機樓A108機器編號指導(dǎo)教師 江麗 實驗時間題目1：鄰接矩陣存儲的圖及相關(guān)算法的實驗驗證實驗驗證如下算法的正確性、各種功能及指標(biāo)：1） 創(chuàng)建一個鄰接矩陣存儲的圖；2） 返回圖中指定邊的權(quán)值；3） 查找圖中某頂點的所有鄰接頂點；4） 圖的深度優(yōu)先遍歷；題目2鄰接表存儲的圖相關(guān)算法的實驗驗證1） 創(chuàng)建一個鄰接表存儲的圖；2） 返回圖中指定邊的權(quán)值；3） 插入操作：向圖中插入一個頂點，插入一條邊;4） 刪除操作：從圖中刪除一個頂點，刪除一條邊;6） 圖的廣度優(yōu)先遍歷；7） 基于迪杰斯特拉算法求最短路徑。【選做題】二、實驗設(shè)備、軟件PC，windows10Professional，VS2015三、實驗過程（算法設(shè)計、代碼編寫、程序調(diào)試、測試數(shù)據(jù)設(shè)計、測試、報告撰寫）基本數(shù)據(jù)結(jié)構(gòu)選擇及算法設(shè)計：題一、圖形結(jié)構(gòu)，鏈?zhǔn)綏＝Y(jié)構(gòu)。深度優(yōu)先遍歷中采用一個堆棧S來存儲訪問過程，使用迭代算法。當(dāng)頂點進棧后，visited【V】置1,初始時，其實頂點v0入棧，其對應(yīng)的迭代過程如下：（1） 檢測棧是否為空。若空，結(jié)束。（2） 棧中彈出一個頂點v,訪問v（3） 將v未被訪問的鄰接頂點壓入棧，并置1（4） 執(zhí)行（1）題二、圖形結(jié)構(gòu)，隊列結(jié)構(gòu)。廣度優(yōu)先遍歷中采用一個隊列來存儲訪問過程，使用迭代算法。當(dāng)頂點出隊后，visited【V】置1，初始時，其實頂點v0入隊，其對應(yīng)的迭代過程如下：檢測隊列是否為空，空，結(jié)束初始化后入隊第一個元素從隊中彈出一個結(jié)點，訪問執(zhí)行(1)代碼編寫(僅填寫關(guān)鍵代碼)：?題目1intGetNextNeighbor(constintvl,constintv2)intGetWeight(constint&vl,constint&v2)intGetFirstNeighbor(constintv)voidDFS_self(constintv)?題目2intgetweight(