李勁朱艷萍金鑫秦（本實驗項指導書的編寫受“教育部人才培養(yǎng)模式創(chuàng)新實驗區(qū)”項目資助本書是以《數(shù)據(jù)結構》09版課程教學大綱和實驗教學大綱為指導，分別從實驗（包含ABC三個級別的實驗）的九個方面（實驗目的、問題描述、基本要求、CDIO項目要求、實驗內容、實現(xiàn)提示、參考程序、教學環(huán)節(jié)組織以及思實驗題目作進一步的解釋；CDIOCDIO詳細設計的目的是對子程序（過程或函數(shù)）IFWHILE程序的每一行最好不超過60個字符。每個子程序（或過程、函數(shù)）不要太長，以40行為宜。子程序（或過程、函數(shù)）包含的程序行數(shù)太多，容易造成理解的。控制IF、WHILE等語句的連續(xù)嵌套的深度。程序的目的性必須明確。對每一段程序完成的作用，除非常明顯的除外（如：xx1;注 實驗一抽象數(shù)據(jù)類型設計與實及構造復數(shù)；個人完成，評分最高70分。B：A人完成，評分最高至90分。合運算。由2-3個人的團隊完成，評分最高可至100分。一個抽象數(shù)據(jù)類型ADT就是：數(shù)據(jù)+操作，例如CpxNum其數(shù)據(jù)部分包括設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;//復數(shù)的實部/*復數(shù)類型接口函數(shù)的定義部分,此部分對cpxNum類型的使用者公開/*用doublerdoublei初始化復數(shù)/*以‘1+2i或1-3i’的形式將復數(shù)c輸出到控制臺窗口*/voidprint(cpxNum&c);/*實現(xiàn)兩個復數(shù)c1,c2的加法,和作為函數(shù)cplus的返回值*/cpxNumcplus(constcpxNum&c1,constcpxNum&c2);/*實現(xiàn)兩個復數(shù)c1,c2的減法,差作為函數(shù)cmilus的返回值/*實現(xiàn)兩個復數(shù)c1,c2的乘法,積作為函數(shù)cmultiply的返回值*/cpxNumcmultiply(constcpxNum&c1constcpxNum&/*實現(xiàn)兩個復數(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初始化‘復數(shù)’c1cout<<"您生成的第一個復數(shù)是:";coutendl請輸入第二個復數(shù)的實部和虛部cin>>real>>imag;assign(c2realimag初始化‘復數(shù)’c2cout<<"您生成的第二個復數(shù)是:";cout<<cout<<"c1+c2的結果是:";print(cplus(c1,c2));cout<<endl;cout<<"c1-c2的結果是:";print(cmilus(c1,c2));cout<<endl;cout"c1*c2的結果是print(cmultiply(c1c2coutendl;cout<<"c1/c2的結果是:";print(cdivide(c1,c2));cout<<endl;降序輸出多項式；個人完成，評分最高70分。評分最高至90分。的求解，包括判斷是否有解、如果有解，輸出基礎解系及通解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;指向多項式鏈表的‘頭結點’、‘尾結點’的指針int_len;//多項式鏈表中除去頭結點后的結點數(shù)，即多項式的項數(shù)typedefLinkListPolynomial定義一元稀疏多項式類型/*根據(jù)用戶輸入的多項式的系數(shù)和指數(shù)floatcoef,intexpn，生成多項式結點，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ù)組的表示及其應以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和。設【CDIO項目要求【實驗內容】印迷宮中各個位置的狀態(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；之一。樹結構的特點在于“非線性”。本實驗單元繼續(xù)突出數(shù)據(jù)結構+操作構評分最高70分。B：A高至90分。難度C：實現(xiàn)一個簡單的哈夫曼編碼/譯，能根據(jù)一段電文設計赫夫曼typedefstruct emTypedatastructBiTNode*lchild,*rchild;StatusCreateBiTree(BiTree//構造二叉鏈表表示的二叉樹TemTypescanf("%c",&chif(ch==’’elseT=(BiTree)malloc(sizeof(BiTNodeT->data=ch;//將值賦給TCreateBiTree(T->lchildCreateBiTree(T->rchild}ReturnT存在，VisitT，對每個結點調用函數(shù)VisitInOrderTraverse(T->lchild,Visit)Visit(T->data);//再根結InOrderTraverse(T->rchild,Visit)}}{//采用二叉鏈表結構，Visit是對數(shù)據(jù)元素操作的應用函數(shù)T的非遞歸算法(利用棧)，對每個數(shù)據(jù)元素調用函數(shù)VisitSqStackS;BiTreeInitStack(S);//初始化棧SPush(S,T);//根指針進棧while(!StackEmpty(Swhile(GetTop(S,p)&&p)Push(S,p->lchildPop(S,p);//空指針退棧，退掉最棧的空指針if(!StackEmpty(S))//結點，向右一步Pop(S,pVisit(p->data);//剛彈出的結點(目前棧頂元素的左孩子)Push(S,p->rchild);//入棧其右孩子指針}}}分析待編碼的電文中出現(xiàn)的字符集，并統(tǒng)計各字符出現(xiàn)的頻度(作為權值利用已建立好的哈夫曼樹對正文進行編碼，并顯示編碼結利用已建立好的哈夫曼樹對編碼后的代碼進行譯利用教科書例6-2中的數(shù)據(jù)的編碼和譯碼“THISPROGRAM FVORITEABCDEFGHIJK15LMNOPQRSTUVW8X1YZ1實驗 圖及其應從某筑到另筑的最短路徑。(最短路徑問題使用戶可以不重復地瀏覽各建筑，最后回到出口（出口就在旁邊【實驗內容】實現(xiàn)校園內主要地點的遍歷。個人完成，評分最高70分。評分最高90分。成，評分最高可至100分。【實現(xiàn)提示】2.構造一個無向圖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："); /*計算兩個建筑之間的最短路徑*/ /*輸出結果*/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++語言設計并實現(xiàn)動態(tài)查找表中的二叉排序樹的建立與查找，包【實驗內容】難度A：設計一個可進行動態(tài)查找表的二叉排序樹的建立與查找的演示程序，包括新結點的插入和刪除等操作；個人完成，評分最高70分。和查