【正文】 （包括AVL樹(shù)、伸展樹(shù)等）、圖（包括網(wǎng)絡(luò)流等問(wèn)題的討論）、散列（Hash）等典型算法典型算法部分主要介紹了若干典型算法的實(shí)現(xiàn)，并給出必要的復(fù)雜性分析和比較過(guò)程，具體包括遞歸、排序、查找和內(nèi)存管理等復(fù)雜數(shù)據(jù)結(jié)構(gòu)復(fù)雜數(shù)據(jù)結(jié)構(gòu)部分主要包括優(yōu)先級(jí)隊(duì)列、不相交集合類和文件結(jié)構(gòu)等算法設(shè)計(jì)技巧典型算法設(shè)計(jì)技巧的介紹，主要包括貪婪算法、分治算法、動(dòng)態(tài)規(guī)劃、回溯算法和隨機(jī)化算法等應(yīng)用應(yīng)用部分是上述數(shù)據(jù)結(jié)構(gòu)和典型算法的一些應(yīng)用示例，具體包括事件驅(qū)動(dòng)模擬、等價(jià)類、殘缺棋盤(pán)和圖象壓縮等問(wèn)題的討論，在課時(shí)允許的情況下還會(huì)介紹攤還分析、紅黑樹(shù)等《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程實(shí)踐內(nèi)容體系主要內(nèi)容實(shí)踐教學(xué)單元模塊實(shí)踐教學(xué)基本要求實(shí)踐教學(xué)具體內(nèi)容趣味程序設(shè)計(jì)實(shí)踐、二周布置若干趣味程序設(shè)計(jì)題目，如奇數(shù)階幻陣算法、萬(wàn)年歷算法、迷宮算法等。（用拉鏈法解決碰撞時(shí)負(fù)載因子取2，用開(kāi)地址法時(shí)取1/2）航班信息查詢與檢索實(shí)驗(yàn)設(shè)計(jì)對(duì)于直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序和堆排序等六種算法進(jìn)行上機(jī)實(shí)習(xí)。 qdata=i。 pnext=qnext。 }/*主函數(shù)*/void main(){ LinkList R。define NEW(type, size) (type*)malloc(sizeof(type) * size)typedef struct _date { /* 日期 */ int m_year。typedef struct _passengernode { /* 乘客數(shù)據(jù) */ char m_szName[20]。/* 刪除乘客 */BOOL DelPassenger(PNODE psglist, int index)。amp。 fread(amp。 break。 p = pnext) i++。 for (p = psglistnext。 while ( = 10000 || 0) { printf(請(qǐng)重新輸入：)。 j++) q[j] = FALSE。 do { int k。 AddPassenger(psglist, amp。 printf(\n請(qǐng)選擇15：)。: fltdat(fltlist, psglist)。 int fltno, i。 printf(起飛時(shí)間：%2d:%02d 到達(dá)時(shí)間：%2d:%02d 飛行固定時(shí)間：%2d:%02d\n, fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i].)。 scanf(%s,name)。 while (c == 39。 printf(起飛時(shí)間：%2d:%02d 到達(dá)時(shí)間：%2d:%02d 飛行固定時(shí)間：%2d:%02d\n,fltlist[i].,fltlist[i].,fltlist[i].,fltlist[i].,fltlist[i].,fltlist[i].)。, amp。y39。, amp。 else printf(添加失敗，)。 } } if (!b) { printf(無(wú)\n按任意鍵返回。 while (c == 39。 scanf(%d, amp。) { DATE date。 i 40。 int people[40][7]。 i++) for (j = 0。 j n。 printf(\n)。439。\n)。 return。psglist)。: Book(fltlist, amp。psglist)。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。 qsercet=a[i]。 q=pnext。 coutinput the serect:endl。 break。 break。j4。 }}實(shí)驗(yàn)結(jié)果(分三次截圖):實(shí)驗(yàn)5 赫夫曼樹(shù)的建立任務(wù) ：建立建立最優(yōu)二叉樹(shù)函數(shù) 要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、 基本算法（可以使用程序流程圖） 、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；實(shí)驗(yàn)內(nèi)容：源程序： includeinclude include define m 100struct ptree /* define the type of banary tree*/{ int w。 for(i=1。 } } struct ptree *hafm(int w[m],int n) { struct pforest *inforest(struct pforest *f, struct ptree *t )。 /*take out frontal two trees*/ t1=p1root。 q=f。void inorder(TREE *Node)。 printf(\n)。Root,TREE *Node) //結(jié)點(diǎn)插入過(guò)程{ if(Root==NULL)//如果根結(jié)點(diǎn)為空 { Root=Node。 printf(%d , Nodedata)。 pNodeL=NULL。 NewNode(t)。void NewNode(int value)。} struct pforest * inforest(struct pforest *f, struct ptree *t){ struct pforest *p, *q, *r。 f=inforest (f,ti)。 printf( the hops of the node is: %d\n,n)。 printf(please input the sum of node\n)。i13。 int i,j,a[13][4]。 break。 break。 cinn。in。 for(i=0。psglist)。 break。 printf(\n請(qǐng)選擇15：)。}void main(void){ FLIGHT fltlist[40]。 if (n == 0) return。639。339。 printf(\n)。 } } } } for (i = 0。date[i].m_month, amp。 || c == 39。 p != NULL。 while (c == 39。)。 ClearBuffer()。 for (i = 0。)。 printf(請(qǐng)輸入到達(dá)港：)。 } } getch()。 i++) people[i] = 0。 i 40。 ClearBuffer()。) { char name[20]。fltno)。y39。: fromto(fltlist)。 printf(\n)。 printf(請(qǐng)輸入乘客單位：)。 } printf(\n請(qǐng)輸入訂票座位號(hào)：)。)。 PASSENGER psg。 p = pnext。}BOOL DelPassenger(PNODE psglist, int index){ int i = 0。 i 40。 } fclose(fp)。/* 退出 */void Quit(FLIGHT fltlist[], PNODE psglist)。/* 讀取乘客數(shù)據(jù) */void ReadPassenger(PNODE psglist)。 /* 起飛時(shí)間 */ TIME m_arrive。 printf(\n)。 if(i%10==0) printf(\n)。i++) { for(j=1。 R=q=(ListNode *)malloc(sizeof(ListNode))。1. 根據(jù)課堂介紹設(shè)計(jì)實(shí)現(xiàn)KMP算法2. 試設(shè)計(jì)一個(gè)簡(jiǎn)單的文本編輯器，使之具有對(duì)字符串的輸入、輸出、插入、刪除、查找和替換等功能3. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)通用的判定回文個(gè)數(shù)問(wèn)題的算法程序 稀疏矩陣和廣義表實(shí)驗(yàn)1．熟悉稀疏矩陣和廣義表結(jié)構(gòu)2．掌握稀疏矩陣和廣義表結(jié)構(gòu)上的各種操作3．學(xué)會(huì)運(yùn)用稀疏矩陣和廣義表結(jié)構(gòu)求解問(wèn)題1. 設(shè)計(jì)實(shí)現(xiàn)兩個(gè)普通矩陣相乘的算法2. 實(shí)現(xiàn)用三元組表示法實(shí)現(xiàn)稀疏矩陣相加及轉(zhuǎn)置算法3. 設(shè)計(jì)實(shí)現(xiàn)兩個(gè)N次一元多項(xiàng)式相加的算法程序 樹(shù)結(jié)構(gòu)實(shí)驗(yàn)1. 設(shè)計(jì)一個(gè)程序，根據(jù)二叉樹(shù)的先根序列和對(duì)稱序序列創(chuàng)建一棵用左右指針表示的二叉樹(shù)2. 根據(jù)哈夫曼算法創(chuàng)建哈夫曼樹(shù)，并求樹(shù)中每個(gè)外部結(jié)點(diǎn)的編碼3. 設(shè)計(jì)一個(gè)程序，把中綴表達(dá)式轉(zhuǎn)換成一棵二叉樹(shù)，然后通過(guò)后序遍歷計(jì)算表達(dá)式的值4. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)完成對(duì)BST樹(shù)進(jìn)行插入、刪除、查找操作的算法，并希望有部分同學(xué)能進(jìn)一步把該算法改寫(xiě)為針對(duì)AVL樹(shù)的相關(guān)算法圖結(jié)構(gòu)實(shí)驗(yàn)采用兩種不同的圖的表示方法，實(shí)現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的求解過(guò)程。 要求：給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過(guò)程的動(dòng)態(tài)演示效果三、 上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可1． 上交源程序：學(xué)生按照課程設(shè)計(jì)的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；2． 上交程序的說(shuō)明文件：（）在說(shuō)明文檔中應(yīng)該寫(xiě)明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；3． 課程設(shè)計(jì)報(bào)告：（保存在word 文檔中，文件名要求 按照姓名學(xué)號(hào)課程設(shè)計(jì)報(bào)告起名，如文件名為張三001課程設(shè)計(jì)報(bào)告.doc ）按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成；其中包括:l 需求分析：在該部分中敘述，每個(gè)模塊的功能要求l 概要設(shè)計(jì)：在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。請(qǐng)寫(xiě)出并在計(jì)算機(jī)上實(shí)現(xiàn)將這兩個(gè)鏈表合并為一個(gè)帶頭結(jié)點(diǎn)的有序循環(huán)鏈表的算法。輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，nm輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能 。 R=p。 return R。n)。 int m_min。 /* 航班號(hào) */ int m_seatno。void query(FLIGHT fltlist[], PNODE psglist)。}void ClearBuffer(void){ getchar()。 fread(amp。 pnext != NULL。 free(q)。y39。 i++) { if(fltlist[i].m_fltno == ) { PNODE p。) amp。 } else printf(這個(gè)座位有人了！)。 } } c = getchar()。 break。 default: continue。 printf(%d , fltlist[i].m_fltno)。 c = getchar()。 printf(訂票日期：%d%d%d , p, p, p)。 char from[30], to[30]。 ClearBuffer()。date, amp。 printf(請(qǐng)輸入航班號(hào)(1 10000)：)。)。 char c = 39。 scanf(%d, amp。 int i, fltno。 printf(起飛時(shí)間：%2d:%02d 到達(dá)時(shí)間：%2d:%02d 飛行固定時(shí)間：%2d:%02d\n, fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i].)。 i++) people[i] = 0。 } } printf(繼續(xù)管理嗎？(y/n))。 if (n 7 || n 1) printf(輸入非法，請(qǐng)重新輸入：)。 p = pnext) { for (j = 0。 c = getchar()。: Query(fltlist)。: Add(fltlist)。 fclose(fp)。 p = pne