數(shù)據(jù)結構算法設計課程教學大綱

數(shù)據(jù)結構算法設計課程教學大綱課程名稱：數(shù)據(jù)結構算法設計英文名稱：AlgorithmDesignofDataStructures課程編號：x2050731學時數(shù)：32其中實驗（實訓）學時數(shù)：28課外學時數(shù)：0學分數(shù)：2.0適用專業(yè)：網(wǎng)絡工程一、課程的性質和任務本課程是網(wǎng)絡工程專業(yè)的專業(yè)基礎課程，它是《數(shù)據(jù)結構》課程的繼續(xù)和延伸。通過該課程的學習，在掌握數(shù)據(jù)結構中的基礎算法的基礎上，進一步掌握、理解一些經(jīng)典算法和應用算法及其程序實現(xiàn)，了解算法設計的基本理論及算法效率評價，培養(yǎng)學生算法設計能力、程序設計能力和程序調(diào)試能力，為后續(xù)課程的學習打下堅實的基礎。二、課程教學內(nèi)容的基本要求、重點和難點（一）線性表的操作1、掌握順序表的操作（1）基本操作：插入、刪除、查找、逆置、構造、析構、遍歷；（2）典型算法：有序表的插入、合并；2、掌握單向鏈表的操作（1）基本操作：插入、刪除、查找、逆置、遍歷；（2）典型算法：有序表的插入、合并；正整數(shù)鏈表的分解兩個奇數(shù)、偶數(shù)表；3、掌握雙向鏈表的插入、刪除、對稱判斷等；4、理解應用算法（拓展）構造一個循環(huán)表，實現(xiàn)約瑟夫問題，一元多項式相加等；重點：實現(xiàn)基本內(nèi)容中的經(jīng)典算法及應用算法難點：雙向鏈表的操作及一元多項式相加（二）棧和隊列的操作1、掌握順序棧的基本操作；2、掌握順序隊列的基本操作（循環(huán)隊列）：入隊、出隊、判斷隊滿等；3、掌握應用算法（1）利用棧實現(xiàn)回文判斷，括號匹配判斷，表達式求值，迷宮求解（拓展）。（2）循環(huán)隊列中利用count記錄隊中元素個數(shù)/設置標志位來區(qū)分隊空/隊滿，實現(xiàn)基本操作。重點：應用算法中各個問題的程序實現(xiàn)難點：迷宮求解及表達式求值（三）二叉樹的操作1、以二叉鏈表為存儲結構,實現(xiàn)二叉樹的3種遞歸遍歷算法；先序、中序非遞歸算法、層次遍歷算法；2、以此為基礎實現(xiàn)簡單應用算法：求高度，求葉子個數(shù)，拷貝二叉樹等；3、設定一些權值，實現(xiàn)哈夫曼樹的構造，計算哈夫曼編碼*;重點：二叉樹的非遞歸遍歷及哈夫曼編碼難點：哈夫曼編碼（四）圖的操作1、構造一個圖的鄰接表、計算各結點的度；以鄰接表為存儲結構實現(xiàn)深度、廣度遍歷算法。2、構造一個無向圖的鄰接表，實現(xiàn)算法判斷任意兩個頂點間是否有路徑可達;3、構造一個無向圖的鄰接表，計算連通分量的個數(shù)；4、構造一個有向圖的鄰接表，實現(xiàn)拓撲排序算法，并運行；5、根據(jù)無向帶權圖的鄰接矩陣，分別按照prim算法、kruskal算法，構造最小生成樹*。重點：判斷頂點間是否有路徑可達算法，計算連通分量個數(shù)算法，拓撲排序算法，prim算法難點：拓撲排序，prim算法的程序實現(xiàn)（五）查找及排序1、構造一個二叉排序樹，實現(xiàn)查找、插入、刪除等操作2、設定一下散列函數(shù)，利用拉鏈法處理沖突，構造一個散列表，實現(xiàn)查找操作3、實現(xiàn)插入排序、快速排序、堆排序*、希爾排序算法，并比擬它們的時間效率，其中快速排序利用棧實現(xiàn)非遞歸算法重點：快速排序的非遞歸算法的程序實現(xiàn)及各個算法時間效率的比擬難點：快速排序非遞歸算法及時間效率的比擬三、教學方式及學時分配序號主要內(nèi)容主要教學方式學時分配輔導答疑比例1布置任務，講解算法：表達式求值，迷宮求解，哈夫曼編碼算法，快速排序的非遞歸算法等講授42：12線性表的應用算法實驗42：13棧和隊列的應用算法實驗82：14二叉樹的應用算法實驗42：15圖的應用算法實驗42：16排序和查找實驗42：17實驗考核考核4四、課程其他教學環(huán)節(jié)要求（-）實驗環(huán)節(jié)1、線性表的操作（4學時）2、棧和隊列的操作（8學時）3、二叉樹的操作（4學時）4、圖的操作（4學時）5、查找及排序（4學時）6、實驗考核（4學時）（二）實驗報告要求：（1）學生上實驗之前按照要求查閱相關資料，準備實驗題目，實驗中獨立完成教師布置的任務，編寫程序，實驗結束時含有提交實驗報告電子版（實驗內(nèi)容、實驗要求、程序源代碼、運行結果截圖及實驗總結）。（2）實驗考核：平時實驗過程中隨時考核，最后一次進行實驗綜合測試及辯論（三）考核方式考勤10%,實驗報告質量40%,實驗測試50%五、本課程與其他課程的聯(lián)系本課程的先修課程是C++程序設計和數(shù)據(jù)結構等，后續(xù)課程是ASP.net程序設計等。六、教學參考書目1、《數(shù)據(jù)結構》（C++版）第二版王紅梅等主編清華大學出版社2011.72、《數(shù)據(jù)結構》（C++版）學習輔導與實驗指導王紅梅等