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

《數(shù)據(jù)結(jié)構(gòu)與算法》試驗(yàn)指導(dǎo)書(shū)試驗(yàn)二線形表基本操作的實(shí)現(xiàn)5試驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用14試驗(yàn)四二叉樹(shù)算法的實(shí)現(xiàn)24試驗(yàn)五圖的算法的實(shí)現(xiàn)36試驗(yàn)六查找算法的實(shí)現(xiàn)52試驗(yàn)七排序算法的實(shí)現(xiàn)62試驗(yàn)一C語(yǔ)言編程復(fù)習(xí)(1)輸入一行字符，計(jì)算該行字符中包含多少個(gè)單詞，單詞之間用空格復(fù)數(shù))cout<<"x1="<<x1.real<<"+imag"<<"x2="<realimagendlcout<<"x1+x2="<<sum.real<sumimagendlif(sum>max)//將某同學(xué)平均成果與目前的最高平均成果進(jìn)行比較選擇高的那個(gè)為最新最高平均成果for(i=0;i<n;i++)//輸出全部同學(xué)成果信息coutThehighestscoreisstudmaxinumst試驗(yàn)二線形表基本操作的實(shí)現(xiàn)一、試驗(yàn)?zāi)康?.熟識(shí)C語(yǔ)言的上機(jī)環(huán)境，進(jìn)一步把握C語(yǔ)言的結(jié)構(gòu)特點(diǎn)。2.把握線性表的挨次存儲(chǔ)結(jié)構(gòu)的定義及C語(yǔ)言實(shí)現(xiàn)。4.把握線性表在挨次存儲(chǔ)結(jié)構(gòu)即挨次表中的各種基本操作。5.把握線性表在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表中的各種基本操作。2.采用前面的試驗(yàn)先建立一個(gè)挨次表L={21,23,14,5,56,17,31}typedefstruct2.留意如何取到第i個(gè)元素，在插入過(guò)程中留意溢出狀況以及數(shù)組的下標(biāo)與位序(挨次表中元素的次序)的區(qū)分。typedefintelemtype;typedefstructnode留意結(jié)點(diǎn)的建立方法及構(gòu)造新結(jié)點(diǎn)時(shí)指針的變化。構(gòu)造一個(gè)結(jié)點(diǎn)需用到C語(yǔ)言的標(biāo)準(zhǔn)函數(shù)malloc(),如給指針變量p安排一個(gè)結(jié)點(diǎn)的地址：linklist的結(jié)點(diǎn)的地址空間，并將首地址存入指針變量p中。當(dāng)結(jié)點(diǎn)不需要時(shí)可以用標(biāo)準(zhǔn)函數(shù)free(p)釋放結(jié)點(diǎn)存儲(chǔ)空間，這時(shí)p為空值(NULL)。1.假如按由表尾至表頭的次序輸入數(shù)據(jù)元素，應(yīng)如何建立挨次表。2.在main函數(shù)里假如去掉L=&a語(yǔ)句，會(huì)消失什么結(jié)果?{//插入一個(gè)元素，勝利返回True,失敗返回Falsev.last++;//線性表長(zhǎng)度加一{//刪除一個(gè)元素，勝利返回True,并用ch返回該元素值，失敗返回False{//在線性表中查找ch的位置，勝利返回其位置，失敗返回-1voidprint(sqlistv)//顯示當(dāng)前線性表全部元素for(i=0;i<v.last;i++)printf("elem2.鏈?zhǔn)骄€性表的建立、插入及刪除。#defineLENsizeof(LNode)/LENenumBOOL{False,True};//定義BOOL型typedefstructnodevoidListPrint(LinkList);//顯示單鏈表全部元素charj,ch;print("可以進(jìn)行插入，刪除，定位，查找等操作。\n");intj=0;p=v;intj=0;p=v;intj=0;p=v;試驗(yàn)三棧和隊(duì)列基本操作的實(shí)現(xiàn)及應(yīng)用6.置空挨次棧typedefstructQnodetypedefstructtypedefintStatus;__typedefstruct{if(!S.base)exit(OVERFLOW);//存儲(chǔ)安排失效__printf("[%d:%d]",++i,*p++//用e返回其值，并返回OK;否則返回ERRORscanf("%d",&ch);}typedefintStatus;typedefintQElemType;printf("[%d:%d]",++i,p->data}一、試驗(yàn)?zāi)康?.通過(guò)試驗(yàn)，把握二叉樹(shù)的建立與存儲(chǔ)2.通過(guò)試驗(yàn)，把握二叉樹(shù)的遍歷方法1.練習(xí)二叉樹(shù)的建立與存儲(chǔ)2.練習(xí)二叉樹(shù)的遍歷1.建立自己的頭文件BT.H,內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹(shù)的建立、二叉樹(shù)的先序、中序與后序遍歷算法。2.建立二叉樹(shù)，并通過(guò)調(diào)用函數(shù)，,輸出先序遍歷、中序遍歷與后序遍歷建立二叉樹(shù)的代碼如下：intj,i,x;新結(jié)點(diǎn)q*|s[i]=q;/*q新結(jié)點(diǎn)地址存入s指針數(shù)組中*/typedefintStatus;typedefcharTElemType;結(jié)果輸入)樹(shù)printf("a\n");printf("\n");printf("b\n");printf("printf("\n");printf("printf("ef\n");printf("\n");printf("g\n");len=strlen(str);printf("printf("bprintf("printf("printf("printf("efprintf("printf("gpstr=gets(str);p=(BiTree)malloc(sizeofBiTNodep->lchild=p-rchildNULL}}printf("%c(%c)",p->data,childtype[level[top][1for(i=n+1;i<=MaxWidth;i+printftop--;iflchildDisplayBiTreeInBracket樹(shù)試驗(yàn)五圖的算法的實(shí)現(xiàn)假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一 3.定義求任意兩點(diǎn)最短路徑函數(shù)；4.寫(xiě)出主函數(shù)。typedefstructnodetypedefstructtypedefvexnodeGraph[n];inti,j,k;if(A[i][k]+A[k][j]<AtypedefstructArcNodetypedefstructvoidCreateGraph(Graph&);//生成圖的鄰接表廣度優(yōu)先搜尋遍歷圖charj='y;scanf("%d,%d",&Gvexnum,&Garcnum);//輸printf("DFSTraverse:"{//從第i個(gè)頂點(diǎn)動(dòng)身遞歸地深度遍歷圖Gfor(w=FirstAdjVex(Gi)NextAdjVex{//按廣度優(yōu)先非遞歸的遍歷圖G,使用幫助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visitedprintf("BFSTreverse:"{DeQueue(Q,u);//將隊(duì)頭元素出隊(duì)列并置為ufor(w=FirstAdjVex(G,NextAdjVexGuif(!visited[w])//對(duì)u的尚未訪問(wèn)的鄰接頂點(diǎn)w進(jìn)行訪問(wèn)并入隊(duì)列{//在圖G中查找第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)elsereturnAdjListadj{//在圖G中查找第v個(gè)頂點(diǎn)的相對(duì)于u的下一個(gè)鄰接頂點(diǎn)ifrearMAXQSIZEfrontreturnFaltypedefstructcharj='y;printf("然后輸入各弧和權(quán)值.\n格式：弧尾，弧頭，權(quán)值；例值voidShortestPathDiJGr{1/用迪杰斯特拉算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及其帶權(quán)路徑長(zhǎng)度D[v]//開(kāi)頭主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，并加v到S集for(i=1;i<=Gvexnum;i++)Gvexnum//查找當(dāng)前離v0最近的頂點(diǎn)v路徑，退出主循環(huán)for(w=1;w<=Gvexnum;w++)//更新當(dāng)前最短路徑及距離if(!final[w]&&(min+G.arcs[v][for(j=0;P[v][j]!=0:j++)P[w]voidPrintShortestPathGr{1/顯示從頂點(diǎn)u到其余頂點(diǎn)的最短路徑及距離printf("%d->",P[v][j])typedefstructNUM]);NUM]);voidPrintOnePathintintintBOOLMAXNUMMAXNUMcharj='y;離\n1,2,4\n2,1,6\n1,3,11\n3,1,3\n2,3,2\n"scanf("%d,%d",&Gvexnum,&Garcnum);//輸入圖的值voidShortestPathFloydGraphfor(u=1;u<=Gvexnum;u++Falseif(P[v][u][i]||P[u][w][i]TruevoidPrintShortestPathGraphG{//顯示每對(duì)頂點(diǎn)之間的最短路徑及距離if(D[v][w]<INFINITY)//頂點(diǎn)v和w之間有通路P[][MAXNUM][MAXNUM])if(i!=v&&i!=w&&P[v]Truebreak}試驗(yàn)六查找算法的實(shí)現(xiàn)3.用其它查找算法進(jìn)行排序(課后自己做)。typedefstructnode五、思索與提高1.用其它的查找方法完成該算法。2.比較各種算法的時(shí)間及空間簡(jiǎn)單度。#defineMAX30//定義有序查找表的最大長(zhǎng)度typedefstruct{charj;return0;//找不到時(shí)，i為0typedefstructBiTNode{chardata;//為了便利，數(shù)據(jù)域只有關(guān)鍵字一項(xiàng)//在二叉排序樹(shù)中刪除元素//中序遍歷二叉排序樹(shù)，即從小到大顯示printf("2.search\n")printf("3.insert\n")printf("4.delete\n")caseprintfInputthekeywortemp=InsertBSTkeywordcaseprintfInputthekeydefault:j='n';printfTheprogramisovernPressany{//以中序方式遍歷二叉排序樹(shù)T,即從小到大顯示二叉排序樹(shù)的全部元素printf("%2c",T->data{//在根指針T所指二叉排序樹(shù)中遞歸的查找其關(guān)鍵字等于key的元素，若查找勝利//則指針p指向該數(shù)據(jù)元素，并返回True,否則指針指向查找路徑上訪問(wèn)的最終一11個(gè)結(jié)點(diǎn)并返回False,指針f指向T的雙親，其初始調(diào)用值為NULL找{1/當(dāng)二叉排序樹(shù)T中不存在元素e時(shí)，插入e并返回True,否則返回False除}一、試驗(yàn)?zāi)康?.把握常用的排序方法，并把握用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法的方法；2.深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以敏捷應(yīng)用；3.了解各種方法的排序過(guò)程及其時(shí)間簡(jiǎn)單度的分析方法。統(tǒng)計(jì)成果給出n個(gè)同學(xué)的考試成果表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個(gè)(1)按分?jǐn)?shù)凹凸次序，打印出每個(gè)同學(xué)在考試中獲得的名次，分?jǐn)?shù)相(2)按名次列出每個(gè)同學(xué)的姓名與分?jǐn)?shù)。3.定出主程序，對(duì)數(shù)據(jù)進(jìn)行排序。for(j=i+1;j<n;j++)}1.快速排序算法解決本問(wèn)題。2.較各種排序算法的優(yōu)缺點(diǎn)及。3.使用其它排序算法實(shí)現(xiàn)該問(wèn)題(直接插入排序、希爾排序、簡(jiǎn)潔選擇排序、堆排序等)。1.直接插入排序