【正文】 當(dāng)n大于1時：在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時間復(fù)雜度為o（n1）在約瑟夫環(huán)實現(xiàn)程序中，為for循環(huán)。}else{y。}q=pnext。e)初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個元素，并用e返回其值，L長度減1。printf(“排序成功:”)。while(left{ while((left=key))right。printf(“插入排序n”)。掌握各種排序時間復(fù)雜度的分析方法。scanf(“%d”,amp。二叉樹的先序，中序與后序的輸出都用了遞歸的算法，而且用起來不是很復(fù)雜，這使我更進(jìn)一步理解了函數(shù)遞歸調(diào)用并得到靈活運(yùn)用；在實現(xiàn)算法上，從算法的效率看，遞歸方法書寫形式較為簡潔，更為直觀，一般具有較好的空間效率。printf(“請輸入要遍歷的數(shù)：”)。)T=NULL。case 8: system(“cls”)。break。printf(“5:輸出該隊列的所有元素,6:輸出該隊列的長度，7:結(jié)束程序，8:清屏n”)。if(==)QueuePtr p。Q){} void GetHead(LinkQueue amp。p=(QueuePtr)malloc(sizeof(QNode))?，F(xiàn)要求：（1）掌握棧和隊列的特點(diǎn)，即后進(jìn)先出和先進(jìn)先出的原則。PrintLinkList(L)。} p=q。while(pnextamp。} coutLinkList p,s。i{p=(LinkList)malloc(sizeof(Lnode))。調(diào)試分析：（1）調(diào)試過程中所遇到的問題及解決方法；（2）算法的時空分析；（3）經(jīng)驗與體會。j++)if(!s[j] amp。? 1)設(shè)置集合s存儲已求得的最短路徑的頂點(diǎn)，? 2)初始狀態(tài)：s=源點(diǎn)v ? 3)疊代算法：? 直接與v相連的最近頂點(diǎn)vi,加入s ? 從v經(jīng)過vi可以到達(dá)的頂點(diǎn)中最短的，加入s……第10頁 北京郵電大學(xué)信息與通信工程學(xué)院emplate void Graph::ShotPath(f x)//關(guān)于最短路徑的初始化 { int v=convert(x)。j vnum。(arc[v][j] = 1))DFS(j)。}//初始化頂點(diǎn)for(k = 0。第一篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗圖數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗六實驗內(nèi)容:圖的基本操作實驗要求:1)))：可單獨(dú)完成，也可兩人一組。kfor(i = 0。//當(dāng)存在回路時，則連通深一層遍歷} 時間復(fù)雜度：O(n2)空間復(fù)雜度：棧的深度O(n)輔助空間O(n)第4頁 北京郵電大學(xué)信息與通信工程學(xué)院三．廣度遍歷BFS ①訪問頂點(diǎn)v ②依次訪問v的所有未被訪問的鄰接點(diǎn)v1,v2,v3…③分別從v1,v2,v3…出發(fā)依次訪問它們未被訪問的鄰接點(diǎn) ④反復(fù)①②③，直到所有和v路徑相通的頂點(diǎn)都被訪問到；，visited[v]=1(隊列非空) v=隊頭元素出隊 訪問隊頭元素的所有未訪問的鄰接點(diǎn) 時間復(fù)雜度：O(n2)空間復(fù)雜度：輔助空間O(n)——普里姆算法1,關(guān)鍵思路一般情況下，假設(shè)n個頂點(diǎn)分成兩個集合：U(包含已落在生成樹上的結(jié)點(diǎn))和VU(尚未落在生成樹上的頂點(diǎn))，則在所有連通U中頂點(diǎn)和VU中頂點(diǎn)的邊中選取權(quán)值最小的邊。j++)//設(shè)置輔助數(shù)組{if((lowcost[j]!= 0 amp。for(int i = 0。amp。用戶使用說明：說明如何使用你的程序，詳細(xì)列出每一步操作步驟。cinpdata。int j=0。amp。free(L)。coutDestroyLinkList(L)。（2）設(shè)計一個使用對頭指針和計數(shù)器的順序循環(huán)隊列抽象數(shù)據(jù)類型，其中操作包括：初始化，入隊列，出隊列，取對頭元素和判斷隊列是否為空；（3）編寫主函數(shù)進(jìn)行測試。QueuePtr p。Q){ QueuePtr p。if(==)printf(“該鏈隊為空”)。while(flag){printf(“n請輸入操作符:”)。case 3:int j。} break。else { T=(BiTNode *)malloc(sizeof(BiTNode))。BiTree Ta。總之，不管做什么實驗，我們在做實驗前都要先預(yù)習(xí)，對所做的實驗有較深的理解，在做實驗的時候需要很嚴(yán)謹(jǐn)，仔細(xì)的查找錯誤，從而能在實驗中收獲知識，提升自己。searchnum)。二、實驗內(nèi)容：插入排序：依次將待排序的序列中的每一個記錄插入到先前排序好的序列中，直到全部記錄排序完畢。printf(“請輸入個您想排序的數(shù)據(jù):n”)。if(leftL[left++]=L[right]。for(i=0。2． 程序包含四個模塊：1）主程序模塊：void main(){初始化；for（。//找到要刪除節(jié)點(diǎn)pnext=qnext。if(c==39。時間復(fù)雜度為o（m%n1）當(dāng)n=1時，復(fù)雜度為o（1）。比如是輸入字母，或者輸入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）。putch(c)。i{p=pnext。L,i,amp。quick_sort(a,0,9)。key=L[first]。void charu(){ int a[7],j,i,m。數(shù)據(jù)結(jié)構(gòu)上機(jī)實驗報告5 一﹑實驗名稱：實驗五—內(nèi)部排序二﹑實驗?zāi)康模和ㄟ^實現(xiàn)下述實驗內(nèi)容，學(xué)習(xí)、實現(xiàn)、對比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況，并加以靈活應(yīng)用。iprintf(“請輸入要查詢的數(shù)據(jù)元素:”)。通過這個實驗，我體會到了理解數(shù)據(jù)結(jié)構(gòu)的重要性，這有真正理解了定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。} } void main()//主函數(shù) {printf(“二叉樹的遍歷n”)。 39。break。case 2: QueueEmpty(Q)。printf(“1:初始化鏈隊列，2:判斷鏈隊列是否為空, 3:進(jìn)入隊列，4:取出隊首元素n”)。QueuePtr p。void DeQueue(LinkQueue amp。Q,int e){ QueuePtr p。三﹑實驗內(nèi)容：對順序循環(huán)隊列，常規(guī)的設(shè)計方法是使用対尾指針和對頭指針，對尾指針用于指示當(dāng)前的対尾位置下標(biāo)，對頭指針用于指示當(dāng)前的対頭位置下標(biāo)。LinkListLengh(L)。free(p)。p=L。p=pnext。coutfor(int i=0。詳細(xì)設(shè)計：提交帶注釋的源程序或者用偽代碼寫出每個操作所涉及的算法。j vnum。} } 時間復(fù)雜度O(nlogn)，適合稀疏圖六．最短路徑——Dijkstra算法 ? 按路徑長度遞增的次序產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。//U=U+{Vk}for(int j = 0。amp。k++){ vertex[k] = a[k]。實驗?zāi)康?1)熟悉C/C++基本編程,)通過實驗,：1)只完成第一和第二題，根據(jù)情況得4，5分；2）完成前3題，根據(jù)情況得5至7分；3）在2）基礎(chǔ)上，選做四）中題目，根據(jù)情況得8至10分。i n。主數(shù)據(jù)結(jié)構(gòu)：鄰接矩陣 輔助數(shù)據(jù)結(jié)構(gòu)：intadjvex[MAXSIZE]。amp。i vnum。(disk[j]arc[v][j] + disk[v])){第11頁 北京郵電大學(xué)信息與通信工程學(xué)院disk[j] = arc[v][j] + disk[v]。測試結(jié)果：列出對于給定的輸入所產(chǎn)生的輸出結(jié)果。pnext=qnext。p=L。j} if(!(pnext