算法與數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列實(shí)驗(yàn)報(bào)告5400字

算法與數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列實(shí)驗(yàn)報(bào)告5400字

實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算一、實(shí)驗(yàn)?zāi)康募耙螅?、掌握棧和隊(duì)列的基本操作：建立、插入、刪除、查找、合并2、掌握用棧和隊(duì)列的儲(chǔ)存3、熟悉C語(yǔ)言上機(jī)編程環(huán)境4、掌握編譯、調(diào)試程序的方法二、實(shí)驗(yàn)內(nèi)容：采用棧進(jìn)行表達(dá)式的求值，表達(dá)式求值是程序設(shè)計(jì)語(yǔ)言編譯中的一個(gè)最基本問(wèn)題。它的實(shí)現(xiàn)是棧應(yīng)用的又一個(gè)典型例子，本報(bào)告使用的是“算符優(yōu)先法”求表達(dá)式的值。要把一個(gè)表達(dá)式翻譯成正確求值的一個(gè)機(jī)器指令序列，或者直接對(duì)表達(dá)式求值，首先要能夠正確解釋表達(dá)式。若要正確翻譯則首先要了解算術(shù)四則運(yùn)算的規(guī)則。即：（1）、先乘除，后加減；（2）、從左算到右；（3）、先括號(hào)內(nèi)后括號(hào)外。任何一個(gè)表達(dá)式都是由操作數(shù)、運(yùn)算符和界限符組成的，我們稱它們?yōu)閱卧~。一般地，操作數(shù)既可以是常數(shù)也可以是被說(shuō)明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符3類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。為了敘述的簡(jiǎn)潔，我們僅討論簡(jiǎn)單算術(shù)表達(dá)式的求值問(wèn)題。這種表達(dá)式只包含加、減、乘、除4種運(yùn)算符。我們把運(yùn)算符和界限符統(tǒng)稱為算符，它們構(gòu)成的集合命名為OP。根據(jù)上述3條運(yùn)算規(guī)則，在運(yùn)算的每一步中，任意兩個(gè)相繼出現(xiàn)的算符系之一：?1和?2之間的優(yōu)先級(jí)之多是以下3種關(guān)?1??2?1的優(yōu)先級(jí)低于?2?1??2?1的優(yōu)先級(jí)等于?2?1??2?1的優(yōu)先級(jí)高于?2根據(jù)實(shí)際情況推導(dǎo)出如下的優(yōu)先關(guān)系算符間的優(yōu)先關(guān)系表實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算有規(guī)則（3），+、-、*和/為?1時(shí)優(yōu)先性均低于“（”但高于“），”由規(guī)則（2），當(dāng)?1??2時(shí)，令?1??2，“#”是表達(dá)式的結(jié)束符。為了算法簡(jiǎn)潔，在表達(dá)式左右括號(hào)的最左邊也虛設(shè)了一個(gè)“#”構(gòu)成整個(gè)表達(dá)式的一對(duì)括號(hào)。表中的“（”=“）”表示當(dāng)左右括號(hào)相遇時(shí)，括號(hào)內(nèi)的運(yùn)算已經(jīng)完成。同理，“#”=“#”表示整個(gè)表達(dá)式求值完畢。“）”與“（、“#”與“）”以及“（”與“#”之間無(wú)優(yōu)先級(jí)，這是因?yàn)楸磉_(dá)式中不允許它們相繼出現(xiàn)，一旦遇到這種情況，則可以認(rèn)為出現(xiàn)語(yǔ)法錯(cuò)誤。為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)棧。一個(gè)稱作OPTR，用以寄存運(yùn)算符；另一個(gè)稱作OPND，用以寄存操作數(shù)戶喲運(yùn)算結(jié)果。算法的基本思想是：（1）首先輸入一個(gè)表達(dá)式，用一數(shù)組記錄；（2）置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素；（3）依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則進(jìn)OPND棧，若是運(yùn)算符則和OPTR棧的棧頂元素比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。三、程序代碼#include<stdio.h>#include<stdlib.h>#include<string.h>#defineerror0//錯(cuò)誤標(biāo)志#defineok1//正確標(biāo)志#defineoverflow-1//溢出標(biāo)志#defineStack_Size100//一般表達(dá)式運(yùn)算符和運(yùn)算數(shù)不會(huì)很長(zhǎng)，100足夠用#defineOP_Size7//一共7種運(yùn)算符charOP[OP_Size]={'+','-','*','/','(',')','#'};//運(yùn)算符unsignedcharPrior[7][7]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','','>','>','>','>','','>','>','<','<','<','<','<','','='};//算符間的優(yōu)先關(guān)系template<typenameT>structSqStack{T*top;T*base;intstacksize;};//順序棧結(jié)構(gòu)模板實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算template<typenameT1,typenameT2>intInitStack(T1&S){S.base=(T2*)malloc(Stack_Size*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base;S.stacksize=Stack_Size;returnok;}//初始化棧函數(shù)模板template<typenameT1,typenameT2>intPush(T1&S,T2e){if(S.top-S.base>=S.stacksize){S.base=(T2*)realloc(S.base,(S.stacksize+1)*sizeof(T2));S.top=S.base+S.stacksize;S.stacksize+=1;}*S.top++=e;returnok;}//入棧函數(shù)模板template<typenameT1,typenameT2>intPop(T1&S,T2&e){if(S.top==S.base)returnerror;e=*--S.top;returnok;}//出棧函數(shù)模板template<typenameT1,typenameT2>T2GetTop(T1S){if(S.top==S.base)returnerror;elsereturn*(S.top-1);}//獲取棧頂元素模板intIn(charTest,char*TestOp){boolFind=false;if(!S.base)exit(overflow);實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算for(inti=0;i<OP_Size;i++){if(Test==TestOp[i])Find=true;}returnFind;}//判斷是否為運(yùn)算符floatOperate(floata,unsignedchartheta,floatb){switch(theta){case'+':returna+b;case'-':returna-b;case'*':returna*b;case'/':returna/b;default:return0;}}//運(yùn)算intReturnOpOrd(charop,char*TestOp){inti;for(i=0;i<OP_Size;i++){if(op==TestOp[i])returni;}return0;}charprecede(charAop,charBop){returnPrior[ReturnOpOrd(Aop,OP)][ReturnOpOrd(Bop,OP)];}//ReturnOpOrd和precede組合，判斷運(yùn)算符優(yōu)先級(jí)floatEvaluateExpression(){//算術(shù)表達(dá)式求值的算符優(yōu)先算法。//設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OPSET為運(yùn)算符集合。SqStack<char>OPTR;//運(yùn)算符棧，字符元素SqStack<float>OPND;//運(yùn)算數(shù)棧，實(shí)數(shù)元素charTempData[20];floatData,a,b;chartheta,c,x,Dr[2];InitStack<SqStack<char>,char>(OPTR);Push(OPTR,'#');InitStack<SqStack<float>,float>(OPND);strcpy(TempData,"\0");//將TempData置為空c=getchar();while(c!='#'||GetTop<SqStack<char>,char>(OPTR)!='#'){if(!In(c,OP))實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算{Dr[0]=c;Dr[1]='\0';//存放單個(gè)數(shù)strcat(TempData,Dr);//將單個(gè)數(shù)連到TempData中，形成字符串c=getchar();if(In(c,OP))//如果遇到運(yùn)算符，則將字符串TempData轉(zhuǎn)換成實(shí)數(shù)，入棧，//并重新置空{(diào)Data=(float)atof(TempData);Push(OPND,Data);strcpy(TempData,"\0");}}else{//不是運(yùn)算符則進(jìn)棧switch(precede(GetTop<SqStack<char>,char>(OPTR),c)){case'<'://棧頂元素優(yōu)先權(quán)低Push(OPTR,c);c=getchar();break;case'='://脫括號(hào)并接收下一字符Pop(OPTR,x);c=getchar();break;case'>'://退棧并將運(yùn)算結(jié)果入棧Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//forswitch}}//forwhilereturnGetTop<SqStack<float>,float>(OPND);}//EvaluateExpressionvoidmain(){printf("請(qǐng)輸入表達(dá)式，并以#結(jié)尾：\n");printf("%f\n",EvaluateExpression());}實(shí)驗(yàn)二棧和隊(duì)列實(shí)現(xiàn)四則運(yùn)算四、運(yùn)行結(jié)果：五、實(shí)驗(yàn)心得運(yùn)用棧來(lái)實(shí)現(xiàn)最簡(jiǎn)單的四則運(yùn)算，從實(shí)例中了解棧和隊(duì)列的結(jié)構(gòu)，以及進(jìn)棧和出棧的過(guò)程。有關(guān)棧的構(gòu)造、入棧、出棧等模塊的代碼都有源程序可參考，完成本實(shí)驗(yàn)的代碼只需要組合學(xué)過(guò)的各個(gè)模塊，結(jié)合起來(lái)進(jìn)行相應(yīng)的調(diào)試就可以實(shí)現(xiàn)。從中學(xué)會(huì)了寫程序不一定所有代碼都是自己重新寫的，只要會(huì)運(yùn)用、會(huì)調(diào)試就能高效地完成。這就要求在學(xué)習(xí)的過(guò)程中多積累好的源代碼以備不時(shí)之需，也應(yīng)該多嘗試著自己去調(diào)試程序完成一些功能。這樣在學(xué)好了算法與數(shù)據(jù)結(jié)構(gòu)的前提下就能很快地寫出自己需要的程序。

第二篇：本科生《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告36100字《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)1：ADTList（線性表）（3學(xué)時(shí)）[問(wèn)題描述]線性表是典型的線性結(jié)構(gòu)，實(shí)現(xiàn)ADTList，并在此基礎(chǔ)上實(shí)現(xiàn)兩個(gè)集合的交運(yùn)算或并運(yùn)算。[實(shí)驗(yàn)?zāi)康腯（1）掌握線性表鏈表存儲(chǔ)結(jié)構(gòu)。（2）掌握在單鏈表上基本操作的實(shí)現(xiàn)。（3）在掌握單鏈表的基本操作上進(jìn)行綜合題的實(shí)現(xiàn)。[實(shí)驗(yàn)內(nèi)容及要求]（1）要求用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)兩個(gè)集合中的元素和最終的結(jié)果。（2）集合的元素限定為十進(jìn)制數(shù)，程序應(yīng)對(duì)出現(xiàn)重復(fù)的數(shù)據(jù)進(jìn)行過(guò)濾，即鏈表中沒(méi)有重復(fù)數(shù)據(jù)。（3）顯示兩個(gè)集合的內(nèi)容及其運(yùn)算結(jié)果。[測(cè)試數(shù)據(jù)]（1）set1={3,8,5,8,11}，set2={22,6,8,3,15,11,20}set1∪set2＝set1∩set2＝（2）set1={1,3,5,7}，set2={2,3,7,14,25,38}set1∪set2＝set1∩set2＝第1頁(yè)[思考]（1）分析你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度？(2)若輸入兩個(gè)集合內(nèi)的元素是遞增的，見(jiàn)測(cè)試數(shù)據(jù)(2)，請(qǐng)你提出一種時(shí)間復(fù)雜度更少的算法思想，并分析時(shí)間復(fù)雜度是多少？第2頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)2：利用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并進(jìn)行計(jì)算（3學(xué)時(shí)）[問(wèn)題描述]中綴表達(dá)式是最普通的一種書寫表達(dá)式的方式，而后綴表達(dá)式不需要用括號(hào)來(lái)表示，計(jì)算機(jī)可簡(jiǎn)化對(duì)后綴表達(dá)式的計(jì)算過(guò)程，而該過(guò)程又是棧的一個(gè)典型應(yīng)用。[實(shí)驗(yàn)?zāi)康腯（1）深入理解棧的特性。（2）掌握棧結(jié)構(gòu)的構(gòu)造方法。[實(shí)驗(yàn)內(nèi)容及要求]（1）（2）（3）中綴表達(dá)式中只包含＋、－、×、/運(yùn)算及（和）?？梢暂斎肴我庵芯Y表達(dá)式,數(shù)據(jù)為一位整數(shù)。顯示中綴表達(dá)式及轉(zhuǎn)換后的后綴表達(dá)式(為清楚起見(jiàn)，要求每輸出一個(gè)數(shù)據(jù)用逗號(hào)隔開(kāi))。（4）對(duì)轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算。棧的類定義如下：#include<iostream.h>constintStackSize=50;classStack{char*StackList;inttop;public:Stack(){StackList=newchar[StackSize];top=-1;}第3頁(yè)boolIsEmpty();boolIsFull();voidPush(charx);charPop();charGetTop();voidpostexpression();};//Stack[測(cè)試數(shù)據(jù)]（1）6＋3*(9-7)-8/2轉(zhuǎn)換后的后綴表達(dá)式為：計(jì)算結(jié)果為：（2）(8-2)/(3-1)*(9-6)轉(zhuǎn)換后的后綴表達(dá)式為：計(jì)算結(jié)果為：[思考]（1）把中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的好處？第4頁(yè)（2）考慮當(dāng)表達(dá)式中數(shù)據(jù)的位數(shù)超過(guò)一位時(shí)，如何修改你的程序？困難在哪？第5頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)3：n皇后問(wèn)題（6學(xué)時(shí)）[問(wèn)題描述]在一個(gè)n×n的國(guó)際象棋棋盤上按照每行順序擺放棋子，在棋盤上的每一個(gè)格中都可以擺放棋子，但任何兩個(gè)棋子不得在棋盤上的同一行、同一列、同一斜線上出現(xiàn)，利用遞歸算法解決該問(wèn)題，并給出該問(wèn)題的n個(gè)棋子的一個(gè)合理布局。[實(shí)驗(yàn)?zāi)康腯（1）深入理解棧的特性。（2）掌握使用遞歸實(shí)現(xiàn)某些問(wèn)題。（3）設(shè)計(jì)出應(yīng)用棧解決在實(shí)際問(wèn)題背景下對(duì)較復(fù)雜問(wèn)題的遞歸算法。[實(shí)驗(yàn)內(nèi)容及要求]（1）從棋盤的第一行開(kāi)始放起。（2）輸出最后每個(gè)棋子的在棋盤上的坐標(biāo)(最好以矩陣形式輸出)。[測(cè)試數(shù)據(jù)]自定n值。[思考]（1）設(shè)計(jì)一個(gè)遞歸算法的三要素是什么？第6頁(yè)（2）考慮用非遞歸實(shí)現(xiàn)該問(wèn)題，并從中總結(jié)遞歸算法和非遞歸算法的優(yōu)、缺點(diǎn)各是什么？（3）通過(guò)對(duì)遞歸算法的理解，總結(jié)把一個(gè)遞歸算法轉(zhuǎn)換為非遞歸算法的方法(可查參考書)，并把求n的階乘的遞歸算法轉(zhuǎn)換為非遞歸算法。第7頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)4：打印二項(xiàng)展開(kāi)式(a+b)n的系數(shù)（3學(xué)時(shí)）[問(wèn)題描述]將二項(xiàng)式(a+b)n展開(kāi)，系數(shù)構(gòu)成著名的楊輝三角形，這是典型的對(duì)隊(duì)列的應(yīng)用。[實(shí)驗(yàn)?zāi)康腯（1）深入理解隊(duì)列的特性。（2）掌握使用隊(duì)列實(shí)現(xiàn)某些問(wèn)題。[實(shí)驗(yàn)內(nèi)容及要求]要求打印形式為11121133114641……………[測(cè)試數(shù)據(jù)]自定n值。[思考]（1）楊輝三角形中系數(shù)之間的關(guān)系是什么？（2）棧和隊(duì)列各應(yīng)用于什么范圍？第8頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)5：實(shí)現(xiàn)二叉樹(shù)的基本操作(6學(xué)時(shí))[問(wèn)題描述]樹(shù)和二叉樹(shù)是最常用的非線性結(jié)構(gòu)(樹(shù)型結(jié)構(gòu))，其中以二叉樹(shù)最為常見(jiàn)，本實(shí)驗(yàn)題要求實(shí)現(xiàn)二叉樹(shù)的最基本操作，其中遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)，它分為先序、中序和后序。[實(shí)驗(yàn)?zāi)康腯（1）熟練掌握二叉樹(shù)的結(jié)構(gòu)特性。（2）掌握二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及實(shí)用范圍。（3）通過(guò)二叉樹(shù)的基本操作的實(shí)現(xiàn)，從而思考一般樹(shù)的基本操作的實(shí)現(xiàn)。（4）熟練掌握各種遍歷二叉樹(shù)的遞歸和非遞歸算法。[實(shí)驗(yàn)內(nèi)容及要求]（1）創(chuàng)建二叉樹(shù)：createBTree(…)所謂創(chuàng)建二叉樹(shù)是指按照某一種或某兩種遍歷序列建立起來(lái)的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。（2）求葉結(jié)點(diǎn)的數(shù)目：getLeavesNum()（3）畫二叉樹(shù)：drawBTree()（4）輸出二叉樹(shù)的中序遍歷序列。[測(cè)試數(shù)據(jù)]（1）以下圖所示1或2的形狀畫出二叉樹(shù)(不需畫線)，從中體會(huì)畫這兩種形狀的圖的難易程度。第9頁(yè)圖1中序遍歷序列結(jié)果為：（2）自己設(shè)定幾組序列來(lái)驗(yàn)證程序的正確性。[思考]（1）若二叉樹(shù)采用順序存儲(chǔ)，有什么缺點(diǎn)？（2）根據(jù)任意兩種遍歷序列重建二叉樹(shù)，然后給出另外一種遍歷序列。（3）在遍歷二叉樹(shù)的算法中，你用的是遞歸算法？還是非遞歸算法？若你用的是遞歸算法，請(qǐng)考慮用非遞歸算法實(shí)現(xiàn)對(duì)二叉樹(shù)的遍歷；反之考慮用遞歸算法實(shí)現(xiàn)對(duì)二叉樹(shù)的遍歷。第10頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)6：哈夫曼樹(shù)的編/譯碼器系統(tǒng)的設(shè)計(jì)(6學(xué)時(shí))[問(wèn)題描述]利用哈夫曼編碼進(jìn)行通訊可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)進(jìn)行預(yù)先編碼；在接受端將傳來(lái)的數(shù)據(jù)進(jìn)行解碼（復(fù)原）。對(duì)于可以雙向傳輸?shù)男诺?，每端都要有一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編譯碼系統(tǒng)。[實(shí)驗(yàn)?zāi)康腯（1）通過(guò)哈夫曼樹(shù)的定義，掌握構(gòu)造哈夫曼樹(shù)的意義。（2）掌握構(gòu)造哈夫曼樹(shù)的算法思想。（3）通過(guò)具體構(gòu)造哈夫曼樹(shù)，進(jìn)一步理解構(gòu)造哈夫曼樹(shù)編碼的意義。[實(shí)驗(yàn)內(nèi)容及要求](1)從終端讀入字符集大小為n（即字符的個(gè)數(shù)），逐一輸入n個(gè)字符和相應(yīng)的n個(gè)權(quán)值（即字符出現(xiàn)的頻度），建立哈夫曼樹(shù)，將它存于文件hfmtree中。并將建立好的哈夫曼樹(shù)以樹(shù)或凹入法形式輸出;對(duì)每個(gè)字符進(jìn)行編碼并且輸出。(2)利用已建好的哈夫曼編碼文件hfmtree，對(duì)鍵盤輸入的正文進(jìn)行譯碼。輸出字符正文，再輸出該文的二進(jìn)制碼。[測(cè)試數(shù)據(jù)]用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)：并實(shí)現(xiàn)以下報(bào)文的譯碼和輸出：THISPROGRAMISMYFAVORITE第11頁(yè)[思考](1)利用哈夫曼編碼，為什么能使報(bào)文中的電文總長(zhǎng)度減少?(2)為什么利用哈夫曼算法求出的一個(gè)字符的編碼都不是其它字符編碼的前綴？第12頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)7：圖的遍歷（6學(xué)時(shí)）[問(wèn)題描述]給定一個(gè)無(wú)向圖或有向圖，利用深度優(yōu)先遍歷和廣度優(yōu)先遍歷對(duì)給定圖進(jìn)行遍歷。[實(shí)驗(yàn)?zāi)康腯（1）熟悉圖的兩種常用的存儲(chǔ)結(jié)構(gòu)。（2）掌握對(duì)圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。（3）進(jìn)一步掌握利用遞歸或隊(duì)列結(jié)構(gòu)進(jìn)行算法設(shè)計(jì)方法。[實(shí)驗(yàn)內(nèi)容及要求]（1）構(gòu)造一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖或有向圖。（2）輸出以深度優(yōu)先遍歷和廣度優(yōu)先遍歷后的頂點(diǎn)序列。[測(cè)試數(shù)據(jù)]以下圖作為測(cè)試數(shù)據(jù)：輸出結(jié)果：第13頁(yè)[思考]（1）在你所設(shè)計(jì)的算法中，使用了什么數(shù)據(jù)結(jié)構(gòu)？（2）考慮如何把書上給出的遞歸實(shí)現(xiàn)的深度優(yōu)先遍歷算法改為非遞歸算法？第14頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)實(shí)驗(yàn)8：利用Kruskal算法求無(wú)向網(wǎng)的最小生成樹(shù)（6學(xué)時(shí)）[問(wèn)題描述]如要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是求一個(gè)無(wú)向網(wǎng)的最小生成樹(shù)問(wèn)題。[實(shí)驗(yàn)?zāi)康腯（1）掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)和基本操作。（2）對(duì)于實(shí)際問(wèn)題的求解會(huì)選用合適的存儲(chǔ)結(jié)構(gòu)。（3）通過(guò)Kruskal算法理解如何求無(wú)向網(wǎng)的最小生成樹(shù)。[實(shí)驗(yàn)內(nèi)容及要求]（1）構(gòu)造具有n個(gè)頂點(diǎn)的無(wú)向網(wǎng)，并利用Kruskal算法求網(wǎng)的最小生成樹(shù)。（2）以文本形式輸出所求得的最小生成樹(shù)中各條邊以及它們的權(quán)值。[測(cè)試數(shù)據(jù)]以下圖作為測(cè)試數(shù)據(jù)：輸出結(jié)果：第15頁(yè)[思考]（1）如何判斷輸入的無(wú)向網(wǎng)存在最小生成樹(shù)?若不存在，請(qǐng)分析是何緣故?（2）在輸入數(shù)據(jù)過(guò)程中，你如何處理一條邊(權(quán)值不同)輸入1次以上的情況?（3）在設(shè)計(jì)該算法時(shí)，你遇到的最大困難是什么?你是如何解決的?第16頁(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告學(xué)院專業(yè)姓名學(xué)號(hào)綜合設(shè)計(jì)實(shí)驗(yàn)題目以下綜合題目可根據(jù)實(shí)際情況選做。題目1：內(nèi)部排序算法比較（6學(xué)時(shí)）[問(wèn)題描述]排序是計(jì)算機(jī)程序設(shè)計(jì)中一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個(gè)按關(guān)鍵字有序的序列。本實(shí)驗(yàn)熟悉幾種典型的排序方法，并對(duì)各種算法的特點(diǎn)、使用范圍和效率進(jìn)行進(jìn)一步的了解。[實(shí)驗(yàn)?zāi)康腯（1）深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。（2）掌握各類排序的時(shí)間復(fù)雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。（3）理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。[實(shí)驗(yàn)內(nèi)容及要求]①數(shù)據(jù)由輸入或隨機(jī)函數(shù)產(chǎn)生。②實(shí)現(xiàn)快速排序、堆排序和歸并排序算法。③至少要用5組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于100），統(tǒng)計(jì)測(cè)試數(shù)據(jù)的準(zhǔn)確的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（需在算法的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)）④對(duì)結(jié)果作