計算機科學與技術專業(yè)本科

1、數據結構,第一講 緒 論,計算機科學與技術專業(yè)（本科）,,● 關于該課程和課程學習,● 數據結構的基本術語,● 數據結構的分類和表示,● 數據結構的算法評價,● 數據結構的算法工具,目 錄,教學要求 理解數據結構的基本術語，掌握邏輯結構和物理結構的概念。 理解各類數據結構的特征及表示方法。 理解數據結構的評價標準，掌握時間復雜性的分析方法。 了解數據結構使用的算法工具。,●下單元導學,,,

2、一、關于該課程和課程學習,1、關于課程,,◎ 課程任務：掌握各種數據結構的特征、性質 、表示和操 作運算， 掌握對數據進行搜索和排序等運算 的基本方法,◎ 課程性質：屬專業(yè)基礎課和技術基礎課，是該專業(yè)的主干 課程 之一,◎ 課程屬性：中央統(tǒng)設，4個學分,◎ 課程特點：概念多，算法多，算法分析難,◎ 文字教材：殷人昆編著《數據結構》、徐孝

3、凱等編的實驗 指導、習題解答和中央電大編的形成性考核冊,,,2、關于課程學習,,◎課堂輔導：重點內容講授、難題解析,◎上機實驗：做實驗指導書中的七個,◎平時作業(yè)：形成性考核冊中的全部題目，提交 4次，批改2次，檢查完成情況2次,◎上機考試：期末進行，按題目自行編程、調試， 一個小時完成◎考核方法：作業(yè)和實驗15%，上機

4、考試15%， 期末閉卷筆試統(tǒng)考70%,,,3、《數據結構》課程教學模式 ---- 單元循環(huán)式 根據課程內容的內在聯(lián)系將其分成若干單元，以單元循環(huán)重復教學。 第一循環(huán)是參考輔導教師的導學意見，學生初讀主教材該單元的內容，思考對主要知識點的理解并提出疑難 第二循環(huán)是學生在校園網“專業(yè)論壇”的本課程平臺就單元內容提問和討論，或用電子郵件和電話方式向請求輔導

5、教師解答 第三循環(huán)是輔導教師在廣泛收集學生提問的基礎上，篩選出帶有普遍性的問題，進行集中答疑 第四循環(huán)是學生完成《形成性考核冊》中相應的作業(yè) 第五循環(huán)是從《實驗指導書》中選擇一兩個與單元內容相關的實驗上機編程調式 第六循環(huán)是學生借助《數據結構課程網站》（sjjg.ougz.com.cn）的“同步練習”平臺按6種題型進行練習和測試 第七循環(huán)是輔導教師作單元小結，并提出下單元的

6、導學意見,二、基本術語,1、數據—用文字符號、數字符號及其它規(guī)定的符號對現實世界的事物及其活動的抽象描述,2、數據元素—數據整體中相對獨立的單位,3、數據結構,◎數據結構是指數據及其相互之間的聯(lián)系 ◎數據結構有邏輯結構和物理結構之分 ◎物理結構是一種邏輯結構在存儲器中的存儲方式，存貯方式有順序、鏈接、索引、散列等多種，所以一種邏輯結構可以采用多種物理結構存貯 ◎邏輯結構所關注的是數據之間的聯(lián)系，是這種聯(lián)系的抽象描述 ◎通

7、常所說的數據結構就是指邏輯結構,,三、數據結構的分類及表示方法,實例：教務處人事簡表（表1—1）,◎目錄行包括六個數據項，這些定義了表的結構 ◎共有十條記錄，一個記錄就是一個數據元素 ◎“職工號”的值能唯一地標識一個記錄，該數據項叫做 關鍵項,設表1—1中只考慮年齡大小的排列 ◎圖形表示,◎二元組表示 line＝ (K，R) K＝{01，02，03，04，05，06，07，08，09，10}

8、R＝{r} r＝{〈05,01〉, 〈01,03〉, 〈03,08〉, 〈08,02〉, 〈02,07〉, 〈07,04〉, 〈04,06〉, 〈06,09〉, 〈09,10〉},◎結構特點：數據元素之間最多只有一個前驅，最多只有一個后繼，元素之間是一對一聯(lián)系，即1︰1,1、線性結構,,設表1—1中只考慮領導和被領導關系,◎圖形表示,◎二元組表示 tree＝(K，R) K＝{01,05,03,

9、08,04,06,02,07,09,10} R＝{r} r＝{〈 01,02〉, 〈01,03〉, 〈01,04〉, 〈02,05〉, 〈03,06〉，〈03,07〉, 〈03,08〉, 〈04,09〉,〈04,10〉},◎結構特點：每個元素最多有一個前驅，但可有多個后繼，元素之間是一對多關系，即1︰N，有層次關系,2、樹形結構,3、圖形結構 設表1—1中只考慮個人之間的關系,◎ 圖示,◎二元組表示

10、 graph＝(K，R) K＝ {01，02，03，04，05，06，07，08，09，10} R＝{r} r＝{(01,02)，(01,05)，(04,01)，(02,03)，(05,03)，(03,06)，(07,06)，(07,10)，(08,07)，(04,07)，(04,09)},◎特點：每個元素可以有多個前驅和多個后即 N︰M ，包含回路，無層次關系。

11、 ◎圖有有向圖和無向圖之分。,,四、算法評價,1、算法,◎算法即解決特定問題的方法，可以描述為“數據結構＋程序語言” ◎對同一個問題，不同人所設計的算法互不同 ◎本課程的目的就是要對特定的問題，按照具體要求，選擇適當的數據結構，設計出較好的算法,2、算法評價標準,◎正確性——合理的數據輸入下，在有限的運行時間內得出正確的結果 ◎健壯性——對不合理的數據輸入的反應和處理能力 ◎可讀性——供人們閱讀的方便程度

12、◎簡單性——采用數據結構和方法的簡單程度 ◎時間復雜度（計算復雜度）——算法運行時間的相 對量度 ◎空間復雜度——算法運行中臨時占用空間大小的量度,3、時間復雜度（Time Complexity）,◎算法運行時間約等于計算機執(zhí)行一個簡單操作的時間與算法所包含簡單操作次數之積 ◎任何一個算法最終都分解成簡單操作來具體執(zhí)行，減小這種簡單操作的次數是本課程能有所作為的 ◎算法包含的簡單操作次數的多少叫做時間復雜度

13、 ◎若解決一個問題的規(guī)模為n，則TC＝f (n),例1：累加求和,原算法：int sum(int b[ ],int n) { int s＝0; for(int i＝0;i<n;i++) s+＝b[i]; return s;},分解算法： 簡

14、單操作次數： s＝0 // 1 i＝0; // 1 mark1:if(i>=n) goto mark2; // n+1

15、 s+＝b[i]; // n i++; // n goto mark1; // n mark2:return s; // 1

16、 TC＝f(n) ＝4n+4,,例2： 矩陣相加,原算法： void Matrixadd(int a[MS][MS], intb [MS][MS], int c[MS][MS],int n) //MS為大于等于n的常量 {

17、 int i,j; for (i＝0;i<n;i++) for (j＝0;j<n;j++) c[i][j] ＝a[i][j]+b[i][j]; },分解算法： 簡單操作次數： i＝0;

18、 // 1 mark1:if(!(i<n)) goto mark4; // n+1 j＝0; // n mark2:if(!(j<n)) goto mark3;

19、 // n(n+1) c[I][j] ＝a[I][j]+b[I][j]; // n﹡n j++; // n﹡n goto mark2; //

20、n﹡n mark3: i++ // n goto mark1; // n mark4: ; TC＝f(n) ＝4n² + 5n + 2,,,,4

21、、空間復雜性（Space Complexity）,◎ 算法運行中占用空間包括算法本身占用，輸入輸出數據占用和運行中的臨時占 ◎ 同一個問題，算法不同，運行中的臨時空間不同，即空間復雜性不同 ◎ SC只考慮在運行中為局部變量分配的存貯空間的大小，一般也以數量級表示,,,五、算法工具 1、 采用VC+ + 程序設計語言作為編程工具 2、 一般以類（包括模板類）方式描述 3、 關注的是實現函數，整個

22、程序（頭文件、 實現文件和主文件的組合）一般不給出 4、涉及C++ 語法問題，一般不多解釋,,,第一單元導學 1、單元組成：第2章至第4章，共3章。 2、共性：相同的邏輯結構 --- 線性結構。數組是順序存儲的線性表，鏈表是鏈式存儲的線性表，棧和隊列是運算位置被限定的線性表。 3、教學要求：掌握順序表的定義、特點和基本運算，數組的存儲方式，單鏈表的定義和基本運算，棧和隊列的特點、存儲結構和