數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(shū)-09版

李勁朱艷萍金鑫秦（本實(shí)驗(yàn)項(xiàng)指導(dǎo)書(shū)的編寫(xiě)受“教育部人才培養(yǎng)模式創(chuàng)新實(shí)驗(yàn)區(qū)”項(xiàng)目資助本書(shū)是以《數(shù)據(jù)結(jié)構(gòu)》09版課程教學(xué)大綱和實(shí)驗(yàn)教學(xué)大綱為指導(dǎo)，分別從實(shí)驗(yàn)（包含ABC三個(gè)級(jí)別的實(shí)驗(yàn)）的九個(gè)方面（實(shí)驗(yàn)?zāi)康?、?wèn)題描述、基本要求、CDIO項(xiàng)目要求、實(shí)驗(yàn)內(nèi)容、實(shí)現(xiàn)提示、參考程序、教學(xué)環(huán)節(jié)組織以及思實(shí)驗(yàn)題目作進(jìn)一步的解釋?zhuān)籆DIOCDIO詳細(xì)設(shè)計(jì)的目的是對(duì)子程序（過(guò)程或函數(shù)）IFWHILE程序的每一行最好不超過(guò)60個(gè)字符。每個(gè)子程序（或過(guò)程、函數(shù)）不要太長(zhǎng)，以40行為宜。子程序（或過(guò)程、函數(shù)）包含的程序行數(shù)太多，容易造成理解的?？刂艻F、WHILE等語(yǔ)句的連續(xù)嵌套的深度。程序的目的性必須明確。對(duì)每一段程序完成的作用，除非常明顯的除外（如：xx1;注 實(shí)驗(yàn)一抽象數(shù)據(jù)類(lèi)型設(shè)計(jì)與實(shí)及構(gòu)造復(fù)數(shù)；個(gè)人完成，評(píng)分最高70分。B：A人完成，評(píng)分最高至90分。合運(yùn)算。由2-3個(gè)人的團(tuán)隊(duì)完成，評(píng)分最高可至100分。一個(gè)抽象數(shù)據(jù)類(lèi)型ADT就是：數(shù)據(jù)+操作，例如CpxNum其數(shù)據(jù)部分包括設(shè)z1=a+bi，z2=c+di，（a，b，c，d∈R，以下不再說(shuō)明□加減法：（abi）±（cdi）=（ac）+（b□乘法：（abi）*（cdi）=（acbd）+（ad abi(abi)(cdi)(acbd)(bcad)icdi c2d2 c2d2typedefstructdouble_real;//復(fù)數(shù)的實(shí)部/*復(fù)數(shù)類(lèi)型接口函數(shù)的定義部分,此部分對(duì)cpxNum類(lèi)型的使用者公開(kāi)/*用doublerdoublei初始化復(fù)數(shù)/*以‘1+2i或1-3i’的形式將復(fù)數(shù)c輸出到控制臺(tái)窗口*/voidprint(cpxNum&c);/*實(shí)現(xiàn)兩個(gè)復(fù)數(shù)c1,c2的加法,和作為函數(shù)cplus的返回值*/cpxNumcplus(constcpxNum&c1,constcpxNum&c2);/*實(shí)現(xiàn)兩個(gè)復(fù)數(shù)c1,c2的減法,差作為函數(shù)cmilus的返回值/*實(shí)現(xiàn)兩個(gè)復(fù)數(shù)c1,c2的乘法,積作為函數(shù)cmultiply的返回值*/cpxNumcmultiply(constcpxNum&c1constcpxNum&/*實(shí)現(xiàn)兩個(gè)復(fù)數(shù)c1,c2的乘法,商作為函數(shù)cdivide的返回值*/cpxNumcdivide(constcpxNum&c1,constcpxNum&c2);{result._real=c1._real+c2._real;result._imag=c1._imag+c2._imag;returnresult;}int_tmain(intargc,_TCHAR*{doublereal,cin>>real>>imag;assign(c1realimag初始化‘復(fù)數(shù)’c1cout<<"您生成的第一個(gè)復(fù)數(shù)是:";coutendl請(qǐng)輸入第二個(gè)復(fù)數(shù)的實(shí)部和虛部cin>>real>>imag;assign(c2realimag初始化‘復(fù)數(shù)’c2cout<<"您生成的第二個(gè)復(fù)數(shù)是:";cout<<cout<<"c1+c2的結(jié)果是:";print(cplus(c1,c2));cout<<endl;cout<<"c1-c2的結(jié)果是:";print(cmilus(c1,c2));cout<<endl;cout"c1*c2的結(jié)果是print(cmultiply(c1c2coutendl;cout<<"c1/c2的結(jié)果是:";print(cdivide(c1,c2));cout<<endl;降序輸出多項(xiàng)式；個(gè)人完成，評(píng)分最高70分。評(píng)分最高至90分。的求解，包括判斷是否有解、如果有解，輸出基礎(chǔ)解系及通解2-31003A(x)73x3B2(x)=-A3(x)B2(x)9x81x7(0.2)x1A3(x)B2(x)9x8(1)x76.2x1A3(x)*B2(x)9x15(28.8)x93x87x7(9.6)x2A3(1.0)*B2(1.0)hA(x)73xhClass8913891307Class007 typedefstructLNode{float_coef;多項(xiàng)式的系數(shù)int_expn;//多項(xiàng)式的指數(shù)structLNode*_next;typedefLink_head,_tail;指向多項(xiàng)式鏈表的‘頭結(jié)點(diǎn)’、‘尾結(jié)點(diǎn)’的指針int_len;//多項(xiàng)式鏈表中除去頭結(jié)點(diǎn)后的結(jié)點(diǎn)數(shù)，即多項(xiàng)式的項(xiàng)數(shù)typedefLinkListPolynomial定義一元稀疏多項(xiàng)式類(lèi)型/*根據(jù)用戶(hù)輸入的多項(xiàng)式的系數(shù)和指數(shù)floatcoef,intexpn，生成多項(xiàng)式結(jié)點(diǎn)，boolMakeNode(Link&p,floatcoef,intvoidInitList(LinkList&L);voidDestroyList(LinkList&vector<double>&coef,vector<int>&expon生成一元稀疏多項(xiàng)式鏈表voidCreatPolyn(Polynomial&p,vector<double>&coef,vector<int>&voidDestroyPolyn(Polynomial&34X^100+45X^60–4X^2+3*/voidPrintPolyn(constPolynomial&voidAddPolyn(Polynomial&Pa,Polynomial&Pb,Polynomial&PSum);voidSubPolyn(Polynomial&Pa,Polynomial&Pb,Polynomial&PSub);voidMultiplyPolyn(Polynomial&Pa,Polynomial&Pb,Polynomial&4B→tAdA；A→sae；(ehnxgz)→則魔王語(yǔ)言B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae12（包含產(chǎn)生式中的大寫(xiě)字母及1個(gè)括3難度12...m(12...n)nn1Asae(θδ1δ2δn)θδnθδn-1意義的人類(lèi)語(yǔ)言（中文；個(gè)人完成，評(píng)分最高至90分。1001、將魔王的語(yǔ)言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址?。若是開(kāi)括號(hào)，則逐一2 #defineSTACK_INIT_SIZE100//棧元素的初始空間大#defineSTACK_INCREMENTtypedefchartypedefstructSElemType*base;SElemType*top;//順序棧的棧頂指針intStackSize;//棧元素空間的大小

boolInitStack(SqStackvoidDestroyStack(SqStack&S);boolClearStack(SqStackboolStackEmpty(SqStack&S);intStackLength(SqStack&S);boolGetTop(SqStack&S,SElemType&e);boolPush(SqStack&S,SElemTypeboolPop(SqStack&S,SElemType&e); #defineMAXQSIZE100typedefstruct{QElemType*base;//指向循環(huán)隊(duì)列元素空間的指intfront;intrear;//循環(huán)隊(duì)列的隊(duì)尾指針

boolInitQueue(SqQueueintQueueLength(SqQueue&Q);boolEnQueue(SqQueue&Q,QElemTypeboolDeQueue(SqQueue&Q,QElemType&e);stringBeelzebubLangcout<<"請(qǐng)輸入魔王語(yǔ)言串:";cin>>SqStackChStack;//定義一個(gè)字符棧變量ChStackSqQueueChQueue;ChQueueSqStackTransLang;for(inti=0;i<BeelzebubLang.size();i++){case}}//endcasecase'A':{}//endcase')':{//說(shuō)明需要處理 }//endcasecase'(':{//}default:TransLang}}//end}//end4（符合規(guī)則，有意義的字符）實(shí)驗(yàn) 數(shù)組的表示及其應(yīng)以一個(gè)m×n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和。設(shè)【CDIO項(xiàng)目要求【實(shí)驗(yàn)內(nèi)容】印迷宮中各個(gè)位置的狀態(tài)。個(gè)人完成，評(píng)分最高70分。B：A終點(diǎn)的通路；個(gè)人完成，評(píng)分最高90分。C：B2-3100int struct{intm,n; arr[RANGE]}voidInitMaze(MazeType&maze,inta[][],introw,intboolMazePath(MazeType&maze,PosTypestart,PosTypevoidPrintMaze(MazeTypemaze)typedef directiveType ) typedefstructNodeType{ElemType struct{LinkTypetop;intStack；StatusMazePath(MazeTypemaze.PosTypestart,PosType{InitStack(S);curpos=start； jf FootPrint(maze,curpos);e=(curstep,curpos,1); ifSame(curpos,endfound curstep ) if(Pop (e.di==4&&!StackEmpTycurstep Push(S,e); curpos=NextPos(e.seat,e.di}returnfound；之一。樹(shù)結(jié)構(gòu)的特點(diǎn)在于“非線(xiàn)性”。本實(shí)驗(yàn)單元繼續(xù)突出數(shù)據(jù)結(jié)構(gòu)+操作構(gòu)評(píng)分最高70分。B：A高至90分。難度C：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的哈夫曼編碼/譯，能根據(jù)一段電文設(shè)計(jì)赫夫曼typedefstruct emTypedatastructBiTNode*lchild,*rchild;StatusCreateBiTree(BiTree//構(gòu)造二叉鏈表表示的二叉樹(shù)TemTypescanf("%c",&chif(ch==’’elseT=(BiTree)malloc(sizeof(BiTNodeT->data=ch;//將值賦給TCreateBiTree(T->lchildCreateBiTree(T->rchild}ReturnT存在，VisitT，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)VisitInOrderTraverse(T->lchild,Visit)Visit(T->data);//再根結(jié)InOrderTraverse(T->rchild,Visit)}}{//采用二叉鏈表結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)T的非遞歸算法(利用棧)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitSqStackS;BiTreeInitStack(S);//初始化棧SPush(S,T);//根指針進(jìn)棧while(!StackEmpty(Swhile(GetTop(S,p)&&p)Push(S,p->lchildPop(S,p);//空指針退棧，退掉最棧的空指針if(!StackEmpty(S))//結(jié)點(diǎn)，向右一步Pop(S,pVisit(p->data);//剛彈出的結(jié)點(diǎn)(目前棧頂元素的左孩子)Push(S,p->rchild);//入棧其右孩子指針}}}分析待編碼的電文中出現(xiàn)的字符集，并統(tǒng)計(jì)各字符出現(xiàn)的頻度(作為權(quán)值利用已建立好的哈夫曼樹(shù)對(duì)正文進(jìn)行編碼，并顯示編碼結(jié)利用已建立好的哈夫曼樹(shù)對(duì)編碼后的代碼進(jìn)行譯利用教科書(shū)例6-2中的數(shù)據(jù)的編碼和譯碼“THISPROGRAM FVORITEABCDEFGHIJK15LMNOPQRSTUVW8X1YZ1實(shí)驗(yàn) 圖及其應(yīng)從某筑到另筑的最短路徑。(最短路徑問(wèn)題使用戶(hù)可以不重復(fù)地瀏覽各建筑，最后回到出口（出口就在旁邊【實(shí)驗(yàn)內(nèi)容】實(shí)現(xiàn)校園內(nèi)主要地點(diǎn)的遍歷。個(gè)人完成，評(píng)分最高70分。評(píng)分最高90分。成，評(píng)分最高可至100分?！緦?shí)現(xiàn)提示】2.構(gòu)造一個(gè)無(wú)向圖G并用鄰接矩陣來(lái)p[i][]d[i]存放；i的范圍：0～20。一維數(shù)組#include"string.h"#include"stdio.h"#include"stdio.h"#include"malloc.h"#include"stdlib.h"#defineMax20000#defineNUM9int /*相鄰接的建筑之間的路程 /*定義邊的類(lèi)型*/typedefstructVertexType{int /*建筑編號(hào)char*sight; /*建筑名稱(chēng)*/char*description/**/ /**/typedefstruct{ArcCellarcs[NUM][NUM];/*圖中的邊，即為建筑間的距離*/ um;/*頂點(diǎn)數(shù)，邊數(shù)*/ /*定義圖的類(lèi)型*/MGraphG; /*把圖定義為全局變量*/intP[NUM][NUM]; longintD[NUM]; /*輔助變量最短路徑長(zhǎng)度*/ voidCreateUDN(intv,inta);/*造圖函數(shù)*/voidnarrate(); voidShortestPath(intnum);/*最短路徑函數(shù)*/voidoutput(intsight1,intsight2*輸出函數(shù)*/char();/*主菜單*/voidsearch(); /*查詢(xún)建筑信息*/charSearenu(); /*查詢(xún)子菜單*/ /*哈密爾頓圖的遍歷*/ display(/**/voidmain()/*主函數(shù)*/{intv0,v1;charck;system("colorfc");{{case（0～8：");（0～8："); /*計(jì)算兩個(gè)建筑之間的最短路徑*/ /*輸出結(jié)果*/printf("\n\n\t\t\t\t請(qǐng)按任意鍵繼續(xù)caseprintf("\n\n\t\t\t\t請(qǐng)按任意鍵繼續(xù)...\n");} /*主菜單{charc;printf("\t\t\t\t請(qǐng)輸入您的選擇：");returnc;}CC++語(yǔ)言設(shè)計(jì)并實(shí)現(xiàn)動(dòng)態(tài)查找表中的二叉排序樹(shù)的建立與查找，包【實(shí)驗(yàn)內(nèi)容】難度A：設(shè)計(jì)一個(gè)可進(jìn)行動(dòng)態(tài)查找表的二叉排序樹(shù)的建立與查找的演示程序，包括新結(jié)點(diǎn)的插入和刪除等操作；個(gè)人完成，評(píng)分最高70分。和查