數(shù)據(jù)結(jié)構(gòu)實驗指導書

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