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

李勁朱艷萍金鑫秦（本實驗項指導(dǎo)書的編寫受“教育部人才培養(yǎng)模式創(chuàng)新實驗區(qū)”項目資助本書是以《數(shù)據(jù)結(jié)構(gòu)》09版課程教學(xué)大綱和實驗教學(xué)大綱為指導(dǎo)，分別從實驗（包含ABC三個級別的實驗）的九個方面（實驗?zāi)康?、問題描述、基本要求、CDIO項目要求、實驗內(nèi)容、實現(xiàn)提示、參考程序、教學(xué)環(huán)節(jié)組織以及思實驗題目作進一步的解釋；CDIOCDIO詳細設(shè)計的目的是對子程序（過程或函數(shù)）IFWHILE程序的每一行最好不超過60個字符。每個子程序（或過程、函數(shù)）不要太長，以40行為宜。子程序（或過程、函數(shù)）包含的程序行數(shù)太多，容易造成理解的?？刂艻F、WHILE等語句的連續(xù)嵌套的深度。程序的目的性必須明確。對每一段程序完成的作用，除非常明顯的除外（如：xx1;注 實驗一抽象數(shù)據(jù)類型設(shè)計與實及構(gòu)造復(fù)數(shù)；個人完成，評分最高70分。B：A人完成，評分最高至90分。合運算。由2-3個人的團隊完成，評分最高可至100分。一個抽象數(shù)據(jù)類型ADT就是：數(shù)據(jù)+操作，例如CpxNum其數(shù)據(jù)部分包括設(shè)z1=a+bi，z2=c+di，（a，b，c，d∈R，以下不再說明□加減法：（abi）±（cdi）=（ac）+（b□乘法：（abi）*（cdi）=（acbd）+（ad abi(abi)(cdi)(acbd)(bcad)icdi c2d2 c2d2typedefstructdouble_real;//復(fù)數(shù)的實部/*復(fù)數(shù)類型接口函數(shù)的定義部分,此部分對cpxNum類型的使用者公開/*用doublerdoublei初始化復(fù)數(shù)/*以‘1+2i或1-3i’的形式將復(fù)數(shù)c輸出到控制臺窗口*/voidprint(cpxNum&c);/*實現(xiàn)兩個復(fù)數(shù)c1,c2的加法,和作為函數(shù)cplus的返回值*/cpxNumcplus(constcpxNum&c1,constcpxNum&c2);/*實現(xiàn)兩個復(fù)數(shù)c1,c2的減法,差作為函數(shù)cmilus的返回值/*實現(xiàn)兩個復(fù)數(shù)c1,c2的乘法,積作為函數(shù)cmultiply的返回值*/cpxNumcmultiply(constcpxNum&c1constcpxNum&/*實現(xiàn)兩個復(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<<"您生成的第一個復(fù)數(shù)是:";coutendl請輸入第二個復(fù)數(shù)的實部和虛部cin>>real>>imag;assign(c2realimag初始化‘復(fù)數(shù)’c2cout<<"您生成的第二個復(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;降序輸出多項式；個人完成，評分最高70分。評分最高至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;多項式的系數(shù)int_expn;//多項式的指數(shù)structLNode*_next;typedefLink_head,_tail;指向多項式鏈表的‘頭結(jié)點’、‘尾結(jié)點’的指針int_len;//多項式鏈表中除去頭結(jié)點后的結(jié)點數(shù)，即多項式的項數(shù)typedefLinkListPolynomial定義一元稀疏多項式類型/*根據(jù)用戶輸入的多項式的系數(shù)和指數(shù)floatcoef,intexpn，生成多項式結(jié)點，boolMakeNode(Link&p,floatcoef,intvoidInitList(LinkList&L);voidDestroyList(LinkList&vector<double>&coef,vector<int>&expon生成一元稀疏多項式鏈表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)→則魔王語言B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae12（包含產(chǎn)生式中的大寫字母及1個括3難度12...m(12...n)nn1Asae(θδ1δ2δn)θδnθδn-1意義的人類語言（中文；個人完成，評分最高至90分。1001、將魔王的語言自右至左進棧，總是處理棧頂字符。若是開括號，則逐一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)隊列元素空間的指intfront;intrear;//循環(huán)隊列的隊尾指針

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