數(shù)據(jù)結構實例教程（C語言版）：第1章 緒論

1、第1章 緒論學習目標 了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項等基本概念。 掌握數(shù)據(jù)結構的概念和三大方面內(nèi)容。 了解學習數(shù)據(jù)結構的意義。 掌握時間復雜度的求解方法。 鞏固和掌握與數(shù)據(jù)結構課程相關的C語言知識。1.1基本概念與術語一、數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。 音樂 電影 word文件 二、數(shù)據(jù)元素：數(shù)據(jù)的基本單位，也稱為元素、結點、頂點或者記錄。數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成1.1基本概念與術語三、數(shù)據(jù)結構：數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。 四、直接前趨：對表中任意一個結點，與它相鄰且在它前面的結點稱為該結點的直接前趨。五、直接后繼：對表中任意一個結點，與它相鄰且在它后面的結點

2、稱為該結點的直接后繼。學號姓名C語言英語數(shù)據(jù)庫 31103001孫彬彬90908531103002朱明秀85908531103003李芳88888831103004季紅梅9080851.1基本概念與術語六、數(shù)據(jù)結構研究的內(nèi)容 邏輯結構數(shù)據(jù)結構存儲結構數(shù)據(jù)之間的運算：插入、刪除、查找、更新和排序等線性結構：線性表、棧、隊列和字符串非線性結構：樹和圖順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構1.2學習數(shù)據(jù)結構的意義一、軟件開發(fā)的基礎、提高學生邏輯思維能力的核心、各工程領域的橋梁。 二、舉例說明 1、電話號碼查詢問題 順序存儲結構索引存儲結構1.2學習數(shù)據(jù)結構的意義 2、教學計劃編排問題 課程

3、編號課程名稱先修課程C1信息基礎無C2數(shù)據(jù)結構C1、C4C3網(wǎng)頁制作C1C4C語言程序設計C1C5AC2、C3、C4C6JavascriptC3C7數(shù)據(jù)庫C2、C9C8JavaC4C9軟件工程C2 拓撲排序方法1.3算法的描述和分析 一、算法：任意一個良定義的計算過程。它以零個或多個值作為輸入，并產(chǎn)生一個或多個值作為輸出。 二、評價算法的效率包括時間復雜度和空間復雜度 三、時間復雜度的求解方法 1、時間復雜度為O(1)情況 int i=3; /執(zhí)行1次 while(i=99) /執(zhí)行34次 i=i+3; /執(zhí)行33次 執(zhí)行的次數(shù)是常數(shù)的，那么T(n)= O(1)。1.3算法的描述和分析 三、時

4、間復雜度的求解方法 2、時間復雜度為O(n)情況 int i,s=0; /執(zhí)行1次 for(i=0;in;i+) /執(zhí)行n+1次 s=s+1; /執(zhí)行n次 printf(“%d”,s); /執(zhí)行1次 程序共執(zhí)行2n+3次，那么只取最高級別的項，去掉該 項的系數(shù)，那么T(n)= O(n)。 1.3算法的描述和分析 三、時間復雜度的求解方法 3、時間復雜度為O(n2)情況 int i,j,s=0; /執(zhí)行1次 for(i=0;in;i+) /執(zhí)行n+1次 for(j=0;jn;j+) /執(zhí)行n(n+1)次 s=s+1; /執(zhí)行n2次 程序共執(zhí)行2 n2+2n+2次，那么只取最高級別的項，去 掉該項的系數(shù)，那么T(n)= O(n2)。 4、常見時間復雜度，按照數(shù)量級別遞增排列，則依次為： 常數(shù)階O(1)、對數(shù)階O (log2 n