1、數據結構,浙江工商大學信息學院,課程內容： 計算機軟件的基礎知識數據結構 課時安排： 數據結構64學時 上機30學時,教材： 數據結構 (C語言版）吳海燕 胡華 王勛 浙大出版社,最終成績 = 期末成績70% + 平時成績30%,平時成績： 出勤率，作業(yè)，上機情況，上機考試 等,學習方法： 掌握基本的技能。 熟練掌握一些常用的算法。,要求： 上機前將程序完成并輸入計算機。 嚴格要求，不許抄襲別人的程序，不能出現沒有格式的程序。,第一章 緒言,1.1 什么是數據結構 程序=數據結構+算法 例1 書目自動檢索系統,書目文件,例2 人機對奕問題,多叉路口交通燈管理問題,數據結構定義: 是一門研究程序

2、設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科,1.2 基本概念和術語 數據（data)所有能輸入到計算機中去的描述客觀事物的符號 數據元素（data element）數據的基本單位，也稱節(jié)點（node）或記錄（record） 數據項（data item）有獨立含義的數據最小單位，也稱域(field) 數據結構（data structure)數據元素和數據元素關系的集合,數據類型高級語言中指數據的取值范圍及其上可進行的操作的總稱,例 C語言中，提供int, char, float, double等基本 數據類型，數組、結構體、共用體、枚舉 等構造數據類型，還有指針、空(void)

3、類 型等。用戶也可用typedef 自己定義數據類型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,抽象數據類型（ADT）是指一個數學模型以及定義在該模型上的一組操作。,一個含抽象數據類型的軟件模塊通常應包含定義、表示和實現3個部分。 抽象數據類型可用三元組表示： (D，S，P）,例1-6 抽象數據類型三元組的定義： ADT Triplet 數據對象: D=e1,e2,e3| e1,e2,e3 ElemSet 數據關系: R1=, 基本操作： Inittriplet (/由In

4、itTriplet 分配3個元素存儲空間 /-基本操作的函數原型說明- Status InitTriplet(Triplet /InitTriplet,數據的邏輯結構只抽象反映數據元素的邏輯關系 數據的存儲（物理）結構數據的邏輯結構在計算機存儲器中的實現,索引存儲方法： 散列存儲方法：,數據的邏輯結構只抽象反映數據元素的邏輯關系 數據的存儲（物理）結構數據的邏輯結構在計算機存儲器中的實現,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈式存儲,h,1.3 算法的描述和算法分析簡介 算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列 算法特

5、性,算法的描述采用C語言 算法的評價衡量算法優(yōu)劣的標準 正確性(correctness) 可讀性(readability) 健壯性(robustness) 效率與低存儲量,算法效率用依據該算法編制的程序在計算機上執(zhí)行所消耗的時間來度量 1.事后統計利用計算機內記時功能，不同算法的程序可以用一組或多組相同的統計數據區(qū)分 缺點：必須先運行依據算法編制的程序 所得時間統計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本 身的優(yōu)劣 2.事前分析估計一個高級語言程序在計算機上運行所消耗的時間取決于： 依據的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產生機器代碼質量 機器執(zhí)行指令速度 同一個算法用不同的語言

6、、不同的編譯程序、在不同的計算機上運行，效率均不同，所以使用絕對時間單位衡量算法效率不合適,時間復雜度(time complexity)：算法執(zhí)行所需的 時間代價 T(n)=O(f(n) 空間復雜度(space complexity)：算法所消耗的存儲 空間 S(n)=O(f(n),問題規(guī)模n的函數,例1：NXN矩陣相乘 for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,n+1,n(n+1),n2,n2(n+1),n3,T(n)=n+1+n(n+1)+n2+n2(n+1)+n3 =2n3+3n2+2n+1,例2. 數字交換 . temp=i; i = j; j = temp; ,1次,1次,1次,時間復雜度: T(n)=O(1),例3： 求和 Sum=0; For(i=1;i=n;i+) for(j=1;j=n;j+) sum+;,1次,n+1 次,n(n