《數據結構課程設計》教學大綱課程中文名稱(課程英文名稱)：數據結構課程設計(CourseProjectforDataStructure)課程代碼：1021616006學分/總學時：1.0學分/1周開課單位：物理與電子信息工程學院面向專業：計算機科學與技術專業、計算機科學與技術（專升本）專業、信息管理與信息系統專業課程的性質、目的和任務本課程為計算機科學與技術專業和信息管理與信息系統專業的學科綜合實踐課程，為必修課程。本課程在學生完成“程序設計基礎”、“離散數學”、“數據結構”等相關課程之后開設，除了關注對理論的深入理解之外，非常強調實踐與應用能力。其目的在于：1）進一步深化學生對于基本數據結構與典型算法思想的掌握；2）培養學生合理或靈活運用基本數據結構與典型算法解決實際問題的計算思維能力；3）培養學生進行規范化軟件設計的能力；4）提升學生的程序編寫與調試能力；5）培養學生的信息獲取能力、溝通與表達能力以及團隊合作能力；6）培養學生的學習能力。學習本課程學生應掌握的前設課程知識程序設計基礎離散數學數據結構項目及學時分配序號項目名稱時數項目類別項目類型要求每組人數課內課外1棧、隊列和樹的應用12學時12學時專業綜合性必做12圖、排序和查找的應用12學時12學時專業綜合性必做1四、教學方法（1）項目組式的合作學習，每5位學生建成一組項目組，共同討論項目的功能需求和總體設計，而具體實現過程和實驗報告必須獨立完成。（2）采用以教師為引導，以學生為主體的研討式教學方法。項目準備階段由各組學生設計出數據結構、算法與流程等的總體方案，項目實現過程中組內學生可以互相交流解決實際遇到的問題，項目完成后，每組派學生代表演示實驗結果，然后進行提問與點評等互動環節，分析其項目實施方案的可行性、不足處及其優點。（3）采取課內與課外學習相結合的方式，利用課程案例庫、課外技術參考資料以及網上答疑等課外教學方式，幫助學生更好地達成課程目標。五、教學內容及要求項目一、棧、隊列和樹的應用教學目的：1、掌握用模塊化程序設計思想。2、掌握基本的軟件系統的設計思想。3、掌握動態管理內存。4、深入了解隊列、棧和樹的特性，以便在解決實際問題中靈活運用它們。5、理解隊列、棧和樹的原理。6、掌握用數組和動態鏈表實現隊列、棧和樹。教學要求：描述程序所要解決的問題，給出程序達到的具體的目標；設計出所使用的隊列和棧自定義數據類型，描述解決相應問題的算法設計思想以及各個模塊的功能，能夠靈活運用各種不同的隊列和棧；設計所需要的測試數據，能夠全面地測試程序的所有功能，并分析測試結果。教學時數：12學時教學內容：參考選題（至少選做一個，也可自主選擇其它經過審核的題目）：迷宮問題求解迷宮問題是隊列和棧應用的一個典型例子。求解過程可采用回溯法。回溯法是一種不斷試探且及時糾正錯誤的搜索方法。在求解過程中，為了保證在到達某一點后不能向前繼續行走（無路）時，能正確返回前一點以便繼續從下一個方向向前試探，則需要用一個棧保存所能夠到達的每一點的下標及從該點前進的方向，棧中保存的就是一條迷宮的通路。計算器表達式求值是程序設計語言編譯中的一個最基本問題。它的實現是棧應用的一個典型例子。可以運用一種簡單直觀的“算符優先法”，把一個表達式翻譯成一個機器指令序列，涉及到運算符的優先級處理和算術表達式的計算。球的碰撞與運動判斷一個球與其它多個球的碰撞需要用到樹型數據結構，夠能大大減少處理的時間復雜度。每個球作為樹數據結構中的一個葉子結點，自上而下建立包圍盒，碰撞檢測則從最大的包圍盒開始計算，逐步計算到最終的真實球物體，并確定該相應的運動方向。主要設備：個人計算機、VisualStudio開發環境。項目二、圖、排序和查找的應用教學目的：1、掌握用模塊化程序設計思想。2、掌握基本的軟件系統的設計思想。3、掌握動態管理內存。4、掌握文件的一般概念及訪問應用。5、掌握圖的原理和特性。6、掌握基本的排序算法。7、掌握查找的效率及應用。教學要求：描述程序所要解決的問題，給出程序達到的具體的目標；設計出所使用的自定義數據類型，描述解決相應問題的算法設計思想以及各個模塊的功能，能夠靈活運用各種不同的排序和查找的方法，并且能夠綜合運用數據結構的其他相關知識點；設計所需要的測試數據，能夠全面地測試程序的所有功能，并分析測試結果。教學時數：12學時教學內容：參考選題（至少選做一個，也可自主選擇其它經過審核的題目）：連連看游戲連連看游戲是圖數據結構的一個應用。要連接的兩點上的圖形是相同的，兩點間存在一條沒有“障礙”的并且折點不超過兩個的路線。尋路查找算法是整個游戲的核心算法，尋找被替換的折點是關鍵。為了使地圖上的所有動物都能被連接成功，需要能成對地產生動物，即要求動物產生時能兩兩配對，那么使用合理的查找算法。積分排行榜保存了前十位分數最高的玩家分數，需要運用有效的排序算法來實現。俄羅斯方塊游戲俄羅斯方塊游戲是圖數據結構的一個應用。俄羅斯方塊游戲原本是前蘇聯科學家阿列克謝·帕基特諾夫所開發的教育用軟件。通過預先設置的隨機發生器不斷地輸出方塊到場地頂部，以一定的規則進行移動、旋轉、下落和擺放，鎖定并填充到場地中。每次擺放如果將場地的一行或多行完全填滿，則組成這些行的所有小正方形將被消除。而未被消除的方塊會一直累積，運用碰撞檢測算法對后來的方塊擺放發生影響。積分排行榜保存了前十位分數最高的玩家分數，需要運用有效的排序算法來實現。主要設備：個人計算機、VisualStudio開發環境。六、主要教材（指導書）及參考用書1、教材：《數據結構與算法課程設計指導書》，自編。2、參考書目：《數據結構——C語言描述》，耿國華主編，高等教育出版社，2005年。3、其他參考資料：1、《數據結構課程設計案例精編（用C/C++描述）》，李建學、李光元、吳春芳編著，清華大學出版社，2007年2、《數據結構題集》，嚴蔚敏、吳偉民編著，清華大學出版社，1999年3、《數據結構課程設計》，蘇仕華等編著，機械工業出版社，2005年七、考核與成績評定采用過程評價與技能考核相結合的方式進行。過程考核主要從考勤情況和項目組成員交流表現等平時成績進行考核。技能考核依托兩個實驗項目的成果演示及實驗報告來進行，考核學生的數據結構課程的綜合運用以及編程實踐能力。具體成績評定如下表所示：評價因子平時成績(20%)實驗成績(80%)考勤情況交流表現實驗一實驗二成果演示實驗報告成果演示實驗報告比例10%10%20%20%20%20%八、其他說