程序設計與數(shù)據(jù)結構教學大綱

1、西安電子科技大學 “卓越工程師教育培養(yǎng)計劃”試點課程教學大綱“程序設計與數(shù)據(jù)結構”教學大綱課程名稱：程序設計與數(shù)據(jù)結構 英文名稱：Program Design and Data Structure 學 時：96 學 分：6課程類型：必修 課程性質：專業(yè)基礎課適用專業(yè)：自動化（交通信息工程及控制） 先修課程：計算機科學與編程導論開課學期：第1、2學期 開課院系：信息科學與技術學院一、課程的教學目標與任務本課程培養(yǎng)學生較熟練地掌握C語言程序設計的基本技能，掌握各種基本數(shù)據(jù)結構和算法。通過本課程的學習，掌握C語言基礎知識；掌握簡單算法和數(shù)據(jù)結構的基本設計方法；掌握復雜數(shù)據(jù)結構（例如棧和隊列以及鏈表）

2、的含義并能簡單應用，建立程序設計的思想，培養(yǎng)學生的問題解決能力和實際編程能力；了解并初步掌握當前軟件行業(yè)公認的程序設計風格和編程實踐。學生應掌握各種基本數(shù)據(jù)結構的概念、實現(xiàn)方法及涉及的基本算法，并能用這些數(shù)據(jù)結構和算法解決相關的應用問題，為進一步學習相關學科打下堅實的基礎。通過本課程的學習。重點是闡述程序設計思想和各種數(shù)據(jù)結構及其相關算法，培養(yǎng)學生分析問題和使用程序和數(shù)據(jù)結構解決問題的能力。二、本課程與其它課程的聯(lián)系和分工“計算機科學與編程導論”是本課程的先修課程。具體分工是:由計算機科學與編程導論課程建立對計算機的基本認識，了解軟件的構成及分類，了解程序的運行原理和過程；由本課程介紹程序設計

3、基礎和軟件開發(fā)方法，C語言的基本語法和語義（包括變量、簡單數(shù)據(jù)類型、表達式和語句、輸入和輸出基礎、順序、條件和循環(huán)控制結構、函數(shù)定義、函數(shù)調用和參數(shù)傳遞等關于程序設計的基本要素），基本數(shù)據(jù)結構和算法，使用C語言進行程序設計的方法以及使用程序解決問題的方法。與本課程關聯(lián)的有相同學期開設的“程序語言設計實驗”獨立實驗課，此外，為增強軟件開發(fā)能力，在短二期設置相應的能力訓練實踐課程“軟件基礎訓練”。本課程為計算機學科的多個后續(xù)課程打下基礎，如計算機網(wǎng)絡、課外創(chuàng)新實踐等。三、課程內容及基本要求第一部分：C語言程序設計（一）計算機與程序設計概述（2學時）主要內容：（1）計算機軟件分類（2）計算機語言（3

4、）程序執(zhí)行的原理和過程（4）軟件開發(fā)方法1.基本要求了解計算機軟件的分類以及計算機語言的分類；理解程序執(zhí)行的原理和過程；了解基本的軟件開發(fā)方法和應用軟件的開發(fā)方法。2.重點、難點重點：程序執(zhí)行的原理和過程由于在計算機科學與編程導論課程中已經(jīng)講授了基本的計算機概念和軟件的基礎知識，因此這里僅需進行內容回顧，并重點討論程序執(zhí)行原理和過程，介紹軟件開發(fā)方法。(二) C程序基礎（2學時)主要內容：（1）字符集、保留字集、標識符、算符等基本詞法元素（2）變量聲明和數(shù)據(jù)類型（3）可執(zhí)行語句（4）鍵盤輸入和屏幕輸出等輸入/輸出基礎（5）運算符與表達式（6）C預處理：include、define（7）C程序的

5、一般形式1.基本要求記住C所用的字符集和保留字，了解C的基本數(shù)據(jù)類型；明確常量、變量與字面量的含義；掌握運算符的使用、表達式的含義和計算過程；掌握用標準函數(shù)實現(xiàn)輸入和輸出的基本方法；掌握各類可執(zhí)行語句的使用；了解C編譯器的基本工作過程和各類預編譯語句的使用；能熟練運用上述基本元素進行簡單的C程序設計。2.重點、難點重點： 基本數(shù)據(jù)類型、運算符與表達式、基本的輸入和輸出處理、語句由于這是第一門程序設計課程，因此需要讓學生深入理解變量、表達式的內涵，掌握C程序的一般形式，并建立良好的編程風格。(三) 基本程序控制結構（8學時)主要內容：（1）控制結構（2）條件語句：if語句和switch語句；嵌套

6、if語句和多選項決策（3）循環(huán)語句：for語句；do-while語句;嵌套循環(huán)1.基本要求了解什么是控制結構；掌握基本的程序控制結構（包括順序結構、條件選擇和循環(huán)結構）及其執(zhí)行流程；掌握不同程序控制結構的C語言實現(xiàn)；掌握嵌套的程序控制結構及其執(zhí)行流程；熟練使用C語言控制結構設計程序。2. 重點、難點重點：條件結構和循環(huán)結構的基本形式及執(zhí)行流程難點：if語句的匹配原則；循環(huán)語句的結束條件和執(zhí)行次數(shù)；復合控制結構的流程?？梢圆捎昧鞒虉D來闡述不同控制結構的執(zhí)行流程，便于學生理解。這部分內容需特別加強應用舉例。(四) 數(shù)組與字符串（6學時)主要內容：（1）聲明和引用數(shù)組及數(shù)組下標（2）多維數(shù)組（3）字

7、符數(shù)組與字符串（4）字符串庫函數(shù)的使用1.基本要求掌握聲明數(shù)組和引用數(shù)組的語法；掌握數(shù)組初始化的方法；掌握C語言數(shù)組下標的特殊性；了解多維數(shù)組的聲明及引用語法；掌握字符數(shù)組與字符串的區(qū)別；掌握初始化字符串變量的方法；掌握常用的字符串操作庫函數(shù)。2. 重點、難點重點：聲明數(shù)組和引用數(shù)組的語法；字符串的特殊性；字符串操作庫函數(shù)的使用。難點：數(shù)組的存儲和訪問方法；C語言數(shù)組下標的特殊性；字符串與字符數(shù)組的區(qū)別。(五) 函數(shù)與模塊化編程（10學時)主要內容：（1）函數(shù)的基本概念（2）函數(shù)的定義、聲明和調用（3）參數(shù)傳遞和變量的作用域（4）遞歸（5）標準函數(shù)或預定義函數(shù)（6）模塊化編程1.基本要求了解函

8、數(shù)是過程抽象的基本形式，掌握函數(shù)的定義、聲明和調用方法；了解函數(shù)、變量等先聲明后引用的一般原則；理解參數(shù)傳遞的內涵，了解函數(shù)操作的對象的不同形式、作用域和使用方法；了解遞歸函數(shù)的運行過程，掌握遞歸函數(shù)的編寫方法；掌握標準函數(shù)或預定義函數(shù)的使用方法；理解模塊化編程的內涵并掌握自頂向下設計的方法。2.重點、難點重點：函數(shù)的定義、聲明和調用，參數(shù)傳遞，變量（數(shù)據(jù)）的作用域，遞歸函數(shù)的運行過程和遞歸函數(shù)的編寫，標準函數(shù)的使用；模塊化編程的意義難點：參數(shù)傳遞，尤其是數(shù)組作為函數(shù)參數(shù)；變量的作用域；遞歸函數(shù)的運行過程和遞歸函數(shù)的編寫。這部分內容需特別加強應用舉例。(六) 結構體與共用體（聯(lián)合）（6學時）主

9、要內容：（1）結構體的聲明及數(shù)據(jù)程遠引用（2）共用體的聲明與使用（3）共用體與結構體的區(qū)別1.基本要求掌握結構類型的定義和使用，了解聯(lián)合數(shù)據(jù)類型的定義和使用；理解共用體與結構體的區(qū)別。2.重點、難點重點：結構類型的定義和應用。這部分內容需特別加強應用舉例。(七) 動態(tài)數(shù)據(jù)結構（指針）（8學時)主要內容：（1）指針的概念及其含義以及如何使用指針引用變量（2）指針運算的意義及其使用（3）動態(tài)內存分配（4）使用指針實現(xiàn)鏈表、二叉樹等動態(tài)數(shù)據(jù)結構1.基本要求理解指針其實是一個內存地址；掌握如何通過指針引用變量；理解只恨運算的意義及合法性；掌握分配內存和回收內存的方法；了解如何使用指針實現(xiàn)鏈表等動態(tài)數(shù)據(jù)

10、結構。2.重點、難點重點：指針的概念及其含義了；使用指針變量的方法；指針運算的含義。難點：指針是C語言中初學者比較難以理解和掌握的一個問題，需要從指針的本質來闡明它的實際意義及使用方法；使用指針實現(xiàn)動態(tài)數(shù)據(jù)結構是一種高效的方法，但也是初學者容易犯錯誤的地方，需要特別加強引用舉例。(八) 文件處理（6學時）主要內容：（1）文件指針變量（2）文件的打開與關閉、打開文件的不同方式（3）文件讀寫和定位1.基本要求了解磁盤文件的不同組織形式；掌握打開文件的不同方式和關閉文件的方法；掌握讀寫文件和在文件中定位的方法。2.重點、難點重點：文件的打開方式；文件讀寫和定位。第二部分：數(shù)據(jù)結構(一) 數(shù)據(jù)結構的基

11、本概念（2學時） 主要內容：(1) 數(shù)據(jù)結構的概念，包括數(shù)據(jù)、數(shù)據(jù)元素、結構；(2) 邏輯結構和物理結構的概念和區(qū)別；(3) 抽象數(shù)據(jù)類型的概念、表示和實現(xiàn)；(4) 算法的概念、特性、設計要求；(5) 算法性能評價方法，大O記法。1 基本要求應了解數(shù)據(jù)結構的基本含義、課程所研究的主要內容，了解四類基本結構：集合、線性結構、樹形結構、圖狀結構。掌握邏輯結構和物理結構的定義與區(qū)別,了解兩類存儲結構：順序存儲結構和鏈式存儲結構。掌握抽象數(shù)據(jù)類型ADT的定義、表示和實現(xiàn)。掌握算法的定義、特性、設計要求和性能度量方法，包括時間復雜度和空間復雜度，能用大O記法表示時間、空間復雜度。2 重點與難點重點：數(shù)據(jù)

12、結構的定義，四類基本結構；邏輯結構和物理結構的區(qū)別，兩類存儲結構；ADT的定義；算法的性能度量方法。難點：邏輯結構、物理結構的區(qū)別；時間復雜度的定義與大O表示法。（二）線性表（6學時）主要內容：(1) 線性表的概念與基本運算；(2) 線性表的順序表示和實現(xiàn)；(3) 線性表的鏈式表示和實現(xiàn)，包括單鏈表、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表；(4) 線性表的應用：一元多項式的表示與相加。1. 基本要求掌握線性表的概念和基本運算，能用基本運算實現(xiàn)一些應用。熟練掌握順序表的表示，理解隨機存取的含義，掌握順序表的基本算法，包括插入、刪除、查找。熟練掌握鏈式存儲的表示和實現(xiàn)，理解頭指針、頭結點的含義，掌握單鏈表、

13、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表的概念和基本運算實現(xiàn)，包括插入和刪除。2. 重點與難點重點：線性表的概念；順序表的表示、特點，插入、刪除操作的實現(xiàn)與復雜度分析；鏈式表示的特點，各種鏈表的概念，插入、刪除操作的實現(xiàn)。難點：順序表與鏈表的特性對比與選取，插入、刪除操作的實現(xiàn)。（三）棧和隊列（4學時）主要內容：(1) 棧的概念、基本運算；(2) 棧的兩種實現(xiàn)：順序棧和鏈棧，入棧與出棧操作的實現(xiàn)；(3) 棧的應用，特別是棧與函數(shù)調用、遞歸的關系；(4) 隊列的概念、基本運算；(5) 隊列的兩種實現(xiàn)：鏈隊列和循環(huán)隊列，入隊列和出隊列操作的實現(xiàn)。1. 基本要求掌握棧的基本概念：后進先出的特點、棧底、棧頂。熟練

14、掌握順序棧和鏈棧的表示方法，入棧、出棧操作的實現(xiàn)。了解棧的幾種應用，如數(shù)制轉換、括號匹配的檢驗、行編輯程序、迷宮求解、表達式求值。理解棧在函數(shù)調用與遞歸實現(xiàn)中的重要作用，會寫遞歸程序。掌握隊列的概念：先進先出的特點、隊頭、隊尾。熟練掌握鏈隊列、循環(huán)隊列的表示方法，入隊列、出隊列操作的實現(xiàn)，理解循環(huán)隊列設計的初衷。2. 重點與難點重點：棧的概念與特點；順序棧和鏈棧的表示，入棧和出棧的實現(xiàn)；棧與函數(shù)調用和遞歸實現(xiàn)的關系；隊列的概念與特點；鏈隊列與循環(huán)隊列的表示，入隊列、出隊列的實現(xiàn)。難點：棧與函數(shù)調用、遞歸的關系；循環(huán)隊列的設計初衷與基本運算實現(xiàn)。（四）串（2學時）主要內容：(1) 串的概念與基本

15、運算；(2) 串的三種表示與實現(xiàn)：定長順序串、堆分配順序串、塊鏈串；(3) 串的模式匹配算法：BF算法與KMP算法。1. 基本要求掌握串的基本概念：子串、主串、位置；掌握串的基本運算。掌握三種表示方法：定長順序存儲、堆分配順序存儲、塊鏈存儲。掌握樸素的模式匹配算法BF算法和改進的模式匹配算法KMP算法，理解改進的思路。2. 重點與難點重點：串的概念，與線性表的區(qū)別；基本運算；三種表示方法；BF算法；KMP算法。難點：KMP算法。（五）數(shù)組和廣義表（4學時）主要內容：(1) 數(shù)組的定義；(2) 數(shù)組的順序表示和實現(xiàn)；(3) 矩陣的壓縮存儲；(4) 廣義表1. 基本要求掌握數(shù)組的定義，理解數(shù)組與線

16、性表的區(qū)別。熟練掌握數(shù)組的順序表示和實現(xiàn)，特別是高維數(shù)組的兩種順序存儲方法：行序為主序與列序為主序。掌握特殊矩陣的壓縮存儲，包括對稱矩陣、三角矩陣和對角矩陣。掌握稀疏矩陣的壓縮存儲方法。掌握廣義表的定義和基本運算，了解廣義表的存儲結構。2. 重點與難點重點：數(shù)組的定義和存儲；特殊矩陣的壓縮存儲；廣義表的定義與運算。難點：高維數(shù)組的順序存儲方法；特殊矩陣的壓縮存儲方法。（六）樹和二叉樹（8學時）主要內容：(1) 樹的定義與基本術語；(2) 二叉樹的定義、基本性質、存儲結構；(3) 二叉樹的遍歷與線索化；(4) 樹與森林的存儲、遍歷，及與二叉樹的轉化；(5) 樹的應用：樹與等價類；(6) 樹的應用

17、：最優(yōu)二叉樹（Huffman樹）。1. 基本要求掌握樹的定義與基本術語：結點、度、葉子、孩子、雙親、兄弟、層次、深度；掌握二叉樹的定義和基本性質，掌握基本性質的證明方法；掌握二叉樹的順序存儲和鏈式存儲兩種實現(xiàn)方法，理解兩者的適用場合；熟練掌握二叉樹的遍歷方法：先序、中序和后序遍歷；掌握二叉樹的線索化，理解線索化的作用和意義；掌握樹的存儲方法：雙親表示法、孩子表示法、孩子兄弟表示法；掌握樹、森林與二叉樹的轉化方法；掌握樹與森林的遍歷方法；掌握用樹實現(xiàn)等價類的方法；掌握Huffman樹的構造方法與用途。2. 重點與難點重點：二叉樹的定義、性質與存儲結構；二叉樹的遍歷；樹與森林的存儲與遍歷。難點：二

18、叉樹遍歷的非遞歸算法實現(xiàn)；由先序、中序遍歷序列確定二叉樹與森林的方法；Huffman樹的構造方法。（七）圖（10學時）主要內容：(1) 圖的定義和術語；(2) 圖的存儲結構：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表；(3) 圖的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索；(4) 圖的連通分量與最小生成樹；(5) 拓撲排序與關鍵路徑算法；(6) 最短路徑算法：Dijkstra算法和Flody算法。1. 基本要求掌握圖的定義與術語：頂點、邊、弧、有向圖、無向圖、鄰接點、簡單路徑、回路、連通圖、連通分量、生成樹；掌握圖的存儲結構：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表；熟練掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷

19、方法；掌握最小生成樹的構造方法：Prim算法和Kruskal算法；掌握拓撲排序算法和關鍵路徑的求法；掌握單源最短路徑算法Dijkstra算法和任兩點間的最短路徑算法Flody算法。2. 重點與難點重點：圖的各種存儲結構；圖的遍歷算法；最小生成樹構造算法；拓撲排序算法；關鍵路徑求法；最短路徑算法。難點：鄰接矩陣和鄰接表的定義與特性；最短路徑算法。（八）查找（6學時）主要內容：(1) 查找的概念；(2) 靜態(tài)查找表：順序查找、折半查找、索引查找；(3) 動態(tài)查找表：二叉排序樹、平衡二叉樹、B樹；(4) 哈希表1. 基本要求掌握查找的基本概念：關鍵字、查找、平均查找長度；掌握順序查找、折半查找與索引

20、查找的概念、實現(xiàn)與性能分析方法；掌握二叉排序樹的概念、實現(xiàn)與性能分析方法；理解平衡二叉樹的設計思路；了解B-樹的定義與實現(xiàn)方法；掌握哈希表的設計思路、哈希函數(shù)的構造方法、處理沖突的方法和性能分析方法。2. 重點與難點重點：順序查找、折半查找、二叉排序樹的定義、實現(xiàn)和性能分析；哈希表的定義、哈希函數(shù)構造方法、處理沖突方法。難點：平衡二叉樹的實現(xiàn)；B-樹的實現(xiàn)；各種查找方法的性能分析。（九）排序（6學時）主要內容：(1) 排序的基本概念；(2) 插入排序：直接插入、折半插入、2-路插入、希爾排序；(3) 交換排序：起泡排序、快速排序；(4) 選擇排序：簡單選擇排序、樹形選擇排序與堆排序；(5) 歸

21、并排序與基數(shù)排序；(6) 各種內部排序算法的比較；(7) 外部排序1. 基本要求掌握排序的基本概念：穩(wěn)定與不穩(wěn)定、內部與外部排序；掌握各種插入排序算法的思路、實現(xiàn)與性能評價：直接插入、折半插入、2-路插入、希爾排序；掌握起泡排序、快速排序的思路、實現(xiàn)與性能評價；掌握簡單選擇排序、堆排序的思路、實現(xiàn)與性能評價；掌握歸并排序、基數(shù)排序的思路、實現(xiàn)與性能評價；掌握各種內部排序算法的性能比較與選取方法；了解外部排序的思路與基本方法。2. 重點與難點重點：直接插入排序、希爾排序；起泡排序、快速排序；簡單選擇排序、堆排序；歸并排序；基數(shù)排序；各種內部排序算法的性能分析與比較。難點：希爾排序；快速排序；堆排

22、序；各種內部排序算法的性能分析。四、教學安排及方式總學時 96 學時，講課 96學時。1課時安排 教學環(huán)節(jié)教學時數(shù)課程內容講 課習 題 課討 論 課上 機參觀或看錄像小 計第一部分：C語言程序設計(一) 計算機與程序設計概述2 2 (二) C程序基礎22 2(三) 基本程序結構828(四) 數(shù)組與字符串646(五) 函數(shù)與模塊化編程10610(六) 結構體與共用體626(七) 動態(tài)數(shù)據(jù)結構（指針）848(八) 文件處理646第二部分：數(shù)據(jù)結構(一) 緒論2 2 (二) 線性表66(三) 棧和隊列44(四) 串22(五) 數(shù)組和廣義表44(六) 樹88(七) 圖1010(八) 查找66(九) 排序662實踐環(huán)節(jié)：獨立實驗課程：程序語言設計實驗（第1學期）實踐內容：軟件基礎訓練（短I學期）3. 教學方法和建議程序設計和數(shù)據(jù)結構是計算機專業(yè)的基礎課，注重理論教學更注重上機實踐。教學過程中應加強應用舉例和作業(yè)講評環(huán)節(jié)，使學生切實掌握基本的程序設計技術。五