【正文】 ，根據(jù)情況得4，5分；2）完成前3題，根據(jù)情況得5至7分；3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。四）高級應(yīng)用題（1）實(shí)現(xiàn)Prim算法（2）實(shí)現(xiàn)Kruskal算法（3）實(shí)現(xiàn)迪杰斯特拉算法（4）實(shí)現(xiàn)拓?fù)渑判蛩惴ǎ?）實(shí)現(xiàn)關(guān)鍵路徑算法第二篇：數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)一 圖[推薦]北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二——圖 學(xué)生姓名： 佘晨陽 班級： 2014211117 班內(nèi)序號： 20 學(xué)號： 2014210491 日期： 2015年12月05日1．實(shí)驗(yàn)要求根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實(shí)現(xiàn)一個圖。k++){ vertex[k] = a[k]。arc[convert(s1)][convert(s2)] = height。amp。i vnum。//U=U+{Vk}for(int j = 0。while(k vnum1){int m = vedgelist[j].fromv, n = vedgelist[j].endv。} } 時間復(fù)雜度O(nlogn)，適合稀疏圖六．最短路徑——Dijkstra算法 ? 按路徑長度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。} s[v] = 1。j vnum。} else {coutreturn true。詳細(xì)設(shè)計：提交帶注釋的源程序或者用偽代碼寫出每個操作所涉及的算法。}Lnode, *LinkList。coutfor(int i=0。} void LinkListLengh(LinkList amp。p=pnext。}} coutdata=x。p=L。free(q)。free(p)。PrintLinkList(L)。LinkListLengh(L)。L, int i, int x)（3）鏈表的打印int PrintLinkList(LinkList amp。三﹑實(shí)驗(yàn)內(nèi)容：對順序循環(huán)隊(duì)列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對頭指針用于指示當(dāng)前的対頭位置下標(biāo)。}LinkQueue。Q,int e){ QueuePtr p。next=p。void DeQueue(LinkQueue amp。free(p)。QueuePtr p。while(p!=next){} printf(“該隊(duì)列的長度為:%d”,f)。printf(“1:初始化鏈隊(duì)列，2:判斷鏈隊(duì)列是否為空, 3:進(jìn)入隊(duì)列，4:取出隊(duì)首元素n”)。n)。case 2: QueueEmpty(Q)。case 4: GetHead(Q)。break。三、實(shí)驗(yàn)步驟與程序：include include include typedef struct BiTNode { char data。 39。PreOrder(Tlchild)。} } void main()//主函數(shù) {printf(“二叉樹的遍歷n”)。printf(“中序遍歷:”)。通過這個實(shí)驗(yàn)，我體會到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。int seqsearch(element list[],int searchnum,int num)。iprintf(“請輸入要查詢的數(shù)據(jù)元素:”)。} return 0。數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報告5 一﹑實(shí)驗(yàn)名稱：實(shí)驗(yàn)五—內(nèi)部排序二﹑實(shí)驗(yàn)?zāi)康模和ㄟ^實(shí)現(xiàn)下述實(shí)驗(yàn)內(nèi)容，學(xué)習(xí)、實(shí)現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應(yīng)用。printf(“內(nèi)部排序n”)。void charu(){ int a[7],j,i,m。i){if(a[i]break。key=L[first]。quick_sort(L,first,split1)。quick_sort(a,0,9)。2． 演示程序以用戶和計算機(jī)的對話方式執(zhí)行，即在計算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運(yùn)算結(jié)果顯示在其后。L,i,amp。//定義頭節(jié)點(diǎn)，和指針for(i=2。i{p=pnext。//約瑟夫環(huán)的結(jié)果輸出其他函數(shù)代碼數(shù)值的輸入限制int input(){int y,k,z=0。putch(c)。}continue。比如是輸入字母，或者輸入0，大于32767溢出；早期的循環(huán)過程中沒有進(jìn)行優(yōu)化，導(dǎo)致循環(huán)次數(shù)過多，浪費(fèi)時間；為了輸出時美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費(fèi)了資源；算法的時空分析為了限制在輸入過程中不會上溢，只在輸入中限定為四個不全為零的數(shù)字，但是做的是do……while循環(huán)，復(fù)雜度為o（1）。七、附錄源程序頭文件名清單：include “”//內(nèi)存空間分配頭文件include “”//輸入輸出函數(shù)頭文件include “”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 include “”//最后顯示結(jié)果、清屏函數(shù)頭文件。時間復(fù)雜度為o（m%n1）當(dāng)n=1時，復(fù)雜度為o（1）。//確定最終輸入數(shù)字的值printf(“n”)。if(c==39。//元素類型char a[4]。//找到要刪除節(jié)點(diǎn)pnext=qnext。//分配新結(jié)點(diǎn)空間scode=i。2． 程序包含四個模塊：1）主程序模塊：void main(){初始化；for（。4． 測試數(shù)據(jù)m 的初值為20；n=7，7個人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序?yàn)?，1，4，7，2，1，3，5）。for(i=0。}} void kuaisu(){int a[7],i。if(leftL[left++]=L[right]。}a[i+1]=m。printf(“請輸入個您想排序的數(shù)據(jù):n”)。printf(“選擇排序：n”)。二、實(shí)驗(yàn)內(nèi)容：插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。list[num].key=searchnum。searchnum)。printf(“數(shù)據(jù)結(jié)構(gòu)查找實(shí)驗(yàn)n”)?？傊还茏鍪裁磳?shí)驗(yàn)，我們在做實(shí)驗(yàn)前都要先預(yù)習(xí)，對所做的實(shí)驗(yàn)有較深的理解，在做實(shí)驗(yàn)的時候需要很嚴(yán)謹(jǐn)，仔細(xì)的查找錯誤，從而能在實(shí)驗(yàn)中收獲知識，提升自己。InOrder(Ta)。BiTree Ta。} } void InOrder(BiTree T)//中序 { if(T!=NULL){ InOrder(Tlchild)。else { T=(BiTNode *)malloc(sizeof(BiTNode))。} BiTNode,*BiTree。} break。case 5:printf(“該隊(duì)列的元素為:”)。case 3:int j。for(e=1。while(flag){printf(“n請輸入操作符:”)。f++。if(==)printf(“該鏈隊(duì)為空”)。} if(==)printf(“該鏈隊(duì)為空”)。Q){ QueuePtr p。printf(“元素%d入隊(duì)成功”,e)。QueuePtr p。Q){} ==(QueuePtr)malloc(sizeof(QNode))。（2）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊(duì)列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊(duì)列，出隊(duì)列，取對頭元素和判斷隊(duì)列是否為空；（3）編寫主函數(shù)進(jìn)行測試。L,int i)（5）編寫鏈表銷毀子函數(shù)void DestroyLinkList(LinkList amp。coutDestroyLinkList(L)。coutx。free(L)。void DestroyLinkList(LinkList amp。amp。pnext=s。int j=0。int i=0