《數(shù)據(jù)結(jié)構(gòu)與嵌入式軟件設(shè)計》教學(xué)大綱

第頁《數(shù)據(jù)結(jié)構(gòu)與嵌入式軟件設(shè)計》教學(xué)大綱課程編號：10140095英文名稱：DataStructureandSoftwareDesignforEmbeddedSystems學(xué)分：3學(xué)時：總學(xué)時56學(xué)時，其中理論40學(xué)時，實踐16學(xué)時先修課程：程序與算法設(shè)計課程類別：專業(yè)基礎(chǔ)課程授課對象：電子信息工程專業(yè)學(xué)生教學(xué)單位：數(shù)理信息學(xué)院修讀學(xué)期：第3學(xué)期一、課程描述和目標(biāo)本課程是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是嵌入式軟件算法實現(xiàn)的基礎(chǔ)，是嵌入式系統(tǒng)開發(fā)中必不可少的重要組成部分。本課程從嵌入式系統(tǒng)的實際軟硬件環(huán)境出發(fā)，主要介紹常見數(shù)據(jù)結(jié)構(gòu)及其基本操作和存儲結(jié)構(gòu)，并適當(dāng)介紹基于常見數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用和常見算法，提高學(xué)生程序設(shè)計能力，為今后的進一步學(xué)習(xí)、研究和工作打下扎實基礎(chǔ)。本課程擬達到的課程目標(biāo):課程目標(biāo)1：學(xué)生能較好地掌握各種常見數(shù)據(jù)結(jié)構(gòu)及其實現(xiàn)等專業(yè)知識；樹立實事求是、結(jié)構(gòu)來源于生活的基本意識。課程目標(biāo)2：學(xué)生能在深刻地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的基礎(chǔ)上，設(shè)計實現(xiàn)基于各種數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和應(yīng)用等專業(yè)能力。課程目標(biāo)3：學(xué)生能綜合運用所學(xué)數(shù)據(jù)結(jié)構(gòu)設(shè)計解決常見典型問題，培養(yǎng)學(xué)生良好的數(shù)據(jù)抽象能力和嵌入式程序設(shè)計技能，具備初步分析問題和抽象建模能力以及嵌入式系統(tǒng)開發(fā)的綜合能力。二、課程目標(biāo)對畢業(yè)要求的支撐關(guān)系畢業(yè)要求指標(biāo)點課程目標(biāo)權(quán)重2.1能夠?qū)?shù)學(xué)、自然科學(xué)和工程科學(xué)的基本原理運用到電子信息領(lǐng)域的復(fù)雜工程問題的適當(dāng)表述中。課程目標(biāo)10.5課程目標(biāo)20.3課程目標(biāo)30.22.2能夠識別、判斷電子信息領(lǐng)域復(fù)雜工程問題的關(guān)鍵環(huán)節(jié)和參數(shù)。課程目標(biāo)10.5課程目標(biāo)20.52.4.能夠運用基本原理，分析過程的影響因素，證明方案的有效性。課程目標(biāo)20.4課程目標(biāo)30.6三、教學(xué)內(nèi)容、基本要求與學(xué)時分配序號教學(xué)內(nèi)容基本要求學(xué)時教學(xué)方式對應(yīng)課程目標(biāo)1數(shù)據(jù)結(jié)構(gòu)概述：介紹數(shù)據(jù)結(jié)構(gòu)含義及其基本概念和術(shù)語，邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)介紹；講解算法和算法分析。了解數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史及其在計算機學(xué)科中的地位，類Ｃ語言的主要特點；了解常見邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)；理解時間復(fù)雜度概念和基本的估算方法，并在后面章節(jié)的學(xué)習(xí)中逐步掌握它。2集中講授課程目標(biāo)12線性表：介紹線性表的類型定義；講解線性表的順序表示和實現(xiàn)，線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)，一元多項式的表示及相加，線性表在嵌入式系統(tǒng)中的應(yīng)用實例。了解線性表的結(jié)構(gòu)特點；了解順序的和鏈?zhǔn)降拇鎯Y(jié)構(gòu)各自特色；熟練掌握線性表的操作，特別是指針運算和各種鏈表的操作。8集中講授+討論+實練課程目標(biāo)1、2、33隊列和棧：講解隊列及其結(jié)構(gòu)和主要操作，循環(huán)隊列、鏈隊列概念和操作，隊列應(yīng)用實例；講解棧及其結(jié)構(gòu)和主要操作，順序棧、鏈棧概念和操作，棧應(yīng)用實例；介紹堆棧、隊列在嵌入式系統(tǒng)中的應(yīng)用實例。理解棧和隊列的操作特點及遞歸程序的執(zhí)行過程；掌握編寫遞歸程序的基本方法和循環(huán)隊列的應(yīng)用。4集中講授+討論+實練課程目標(biāo)1、2、34串：講解串類型的定義及其結(jié)構(gòu)，串的主要操作，基本模式匹配算法及串在嵌入式系統(tǒng)中的應(yīng)用實例。掌握串的主要操作及常用模式匹配算法2集中講授+討論+實練課程目標(biāo)1、2、35數(shù)組：講解數(shù)組的定義，數(shù)組的順序表示和實現(xiàn)，三元組順序表壓縮存儲，數(shù)組在嵌入式系統(tǒng)中的應(yīng)用實例。掌握計算給定元素在存儲區(qū)中的地址；掌握矩陣的三元組壓縮存儲方法。4集中講授+討論+演示+實練課程目標(biāo)1、2、36樹和二叉樹：介紹樹的定義和基本術(shù)語；講解二叉樹，遍歷二叉樹，樹的應(yīng)用實例，哈夫曼樹，二叉樹在嵌入式系統(tǒng)中的應(yīng)用實例。掌握樹和二叉樹的基本概念及存儲結(jié)構(gòu)；熟練掌握二叉樹的性質(zhì)和操作；掌握樹和二叉樹的互相轉(zhuǎn)換、哈夫曼樹和哈夫曼算法。8集中講授+討論+實練課程目標(biāo)1、2、37圖：介紹圖的定義和術(shù)語；講解圖的存儲結(jié)構(gòu)，圖的遍歷，最小生成樹，最短路徑，圖在嵌入式系統(tǒng)中的應(yīng)用實例。理解圖的概念；掌握圖的幾種存儲結(jié)構(gòu)、基本操作及應(yīng)用特點，注意鄰接點次序的確定；掌握幾種典型的應(yīng)用算法。6集中講授+討論+實練課程目標(biāo)1、2、38排序：介紹排序概述；講解插入排序、選擇排序、快速排序等的算法實現(xiàn)以及排序在嵌入式系統(tǒng)中的應(yīng)用實例。了解各種典型的內(nèi)部排序算法的特點和適用范圍；熟練掌握各排序算法。4集中講授+討論課程目標(biāo)2、39查找：講解順序查找，折半查找，索引查找的算法實現(xiàn)；介紹查找在嵌入式系統(tǒng)中的應(yīng)用實例。理解查找的基本概念；掌握典型的查找表的構(gòu)造和查找算法及其應(yīng)用特點。2集中講授+討論課程目標(biāo)2、310循環(huán)鏈表理解并掌握循環(huán)鏈表概念及操作0自主學(xué)習(xí)課程目標(biāo)1、211棧與遞歸了解棧與遞歸的聯(lián)系及實現(xiàn)0自主學(xué)習(xí)課程目標(biāo)1、2、312廣義表了解廣義表的概念及基本結(jié)構(gòu)與操作0自主學(xué)習(xí)基本目標(biāo)1、2、3合計40實驗部分序號實驗項目實驗內(nèi)容與要求學(xué)時類型對應(yīng)課程目標(biāo)1線性表基本操作實驗內(nèi)容：設(shè)計實現(xiàn)順序存儲的線性表插入與刪除操作。實驗要求：必修2驗證課程目標(biāo)1、22隊列和棧的應(yīng)用實驗內(nèi)容：設(shè)計實現(xiàn)通用數(shù)制轉(zhuǎn)換程序：將一個十進制數(shù)轉(zhuǎn)換成其他進制（二進制、八進制、十六進制）的數(shù)。實驗要求：必修2驗證課程目標(biāo)1、23串的基本操作實驗內(nèi)容：設(shè)計實現(xiàn)計算字符串的長度、字符串的復(fù)制、字符串的比較、字符串的連接、字符串的插入等基本操作。實驗要求：必修2驗證課程目標(biāo)1、24數(shù)組基本操作實驗內(nèi)容：稀疏矩陣的加法--假設(shè)稀疏矩陣A和B（具有相同的大小m*n）都采用三元組表示，編寫一個函數(shù)計算C＝A+B，要求C也采用三元組表示。實驗要求：必修2驗證課程目標(biāo)1、25樹的遍歷及應(yīng)用實驗內(nèi)容：二叉樹的遍歷及其應(yīng)用--采用二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，實現(xiàn)如下功能：輸入二叉樹的特殊先序序列，建立二叉樹；實現(xiàn)二叉樹的中序遍歷；求二叉樹的深度；求二叉樹中葉子結(jié)點的數(shù)目。實驗要求：必修2綜合課程目標(biāo)1、26圖的遍歷及應(yīng)用實驗內(nèi)容：設(shè)計實現(xiàn)圖的深度優(yōu)先搜索。實驗要求：必修2驗證課程目標(biāo)1、27排序?qū)崿F(xiàn)實驗內(nèi)容：設(shè)計實現(xiàn)直接插入排序、簡單選擇排序、快速排序和堆排序的算法，并比較這幾種算法的時間復(fù)雜度。實驗要求：必修2驗證課程目標(biāo)1、2、38查找實現(xiàn)實驗內(nèi)容：分別利用順序表查找法和二分查找的方法對有序順序表進行查找。實驗要求：必修2驗證課程目標(biāo)1、2、3合計16注：實驗要求包括必修、選修；實驗類型包括演示、驗證、綜合、設(shè)計等。四、課程教學(xué)方法以集中講授為主，結(jié)合討論、演示、實訓(xùn)練習(xí)等教學(xué)方式為輔的教學(xué)方法。五、學(xué)業(yè)評價和課程考核考核依據(jù)建議分值考核/評價細(xì)則對應(yīng)課程目標(biāo)平時成績40%出勤0%缺課根據(jù)課程課時按比例扣分；若缺課累計超過課程本學(xué)期學(xué)時數(shù)三分之一及以上，取消考試資格。課程目標(biāo)1階段測驗5%根據(jù)階段測驗情況計分課程目標(biāo)1、2作業(yè)7%缺交作業(yè)根據(jù)課程作業(yè)次數(shù)按比例扣分；若缺交作業(yè)達三分之一及以上，取消考試資格課程目標(biāo)1、2綜合表現(xiàn)8%根據(jù)課程學(xué)習(xí)狀態(tài)和活動參與情況計分課程目標(biāo)1、2、3實驗成績20%實驗操作60%；實驗報告40%課程目標(biāo)1、2、3期末考核60%根據(jù)期末考核成績按百分制計分課程目標(biāo)1、2、3六、教材與參考書（一）推薦教材《數(shù)據(jù)結(jié)構(gòu)（C語言版）第2版》，嚴(yán)蔚敏主編，人民郵電出版社，2017年8月版；《嵌入式系統(tǒng)軟件設(shè)計中的數(shù)據(jù)結(jié)構(gòu)》，陸玲主編，北京航空航天大學(xué)出版社，2008年8月版。（二）參考資料《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語言版）第2版》，朱仲濤（譯）主編，清華大學(xué)出版社，2009年3月版；