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