【主要內容】
1．資料結構的研究目的和研究內容
2．資料結構中的幾個重要概念和術語
3．演算法設計的基本要求以及演算法複雜度的分析和計算方法
【教學目標】
1．了解資料結構的研究目的和研究內容
2．掌握資料結構中的重要概念和術語
3．掌握演算法設計的基本要求以及演算法複雜度的分析和計算方法
【所需課時】
2次課。
[第一次課]
1．資料結構的研究目的和研究內容
2．資料結構中的重要概念和術語
[第二次課]
3．演算法設計的基本要求以及演算法複雜度的分析和計算方法
1．概念和術語
資料：是能輸入到計算機中並能被電腦程式處理的符號的總稱。
資料元素：是資料的基本單位，它在計算機處理和程式設計中通常作為乙個整體進行考慮和處理。乙個資料元素可由若干資料項組成。
資料物件：是具有相同特徵的資料元素的集合，是資料的乙個子集。
資料結構：是資料元素的組織形式，或資料元素相互之間存在一種或多種特定關係的集合。
資料的邏輯結構：是指資料結構中資料元素之間的邏輯關係。
資料的儲存結構：是資料的邏輯結構在計算機記憶體中的儲存方式，又稱物理結構。
資料型別：是一組具有相同性質的操作物件以及該組操作物件上的運算方法的集合。
抽象資料型別：是指乙個數學模型以及在該模型上定義的一套運算規則的集合。
演算法：建立在資料結構基礎上的，為解決問題而採取的步驟和方法。
2．邏輯結構的四種基本形態
根據資料元素之間關係的不同特徵，通常有下列四類基本結構：
（1）集合：結構中的資料元素間除了「同屬於乙個集合」的關係外，別無其它關係。
（2）線性結構：結構中的資料元素之間存在乙個對乙個的關係。
（3）樹型結構：結構中的資料元素之間存在乙個對多個的關係。
（4）圖型結構或網狀結構：結構中的資料元素之間存在多個對多個的關係。
3．資料儲存結構的基本組織方式
資料儲存結構有順序和鏈式兩種方式。
（1）順序儲存結構的特點：要借助資料元素在儲存器中的相應位置來體現資料元素相互間的邏輯關係，常用高階程式語言中的「一維陣列」來描述或實現。
（2）鏈式儲存結構的特點：通過表示資料元素儲存位址的指標來表示資料元素之間的邏輯關係，通常用鍊錶來實現。
在順序儲存結構的基礎上，又可延伸變化出另外兩種儲存結構，即索引儲存和雜湊儲存。
（1）索引儲存就是在資料檔案的基礎上增加了乙個索引表檔案。通過索引表建立索引，可以把乙個順序表分成幾個順序子表，其目的是在查詢時提高查詢效率，避免盲目查詢。
（2）雜湊儲存就是通過資料元素與儲存位址之間建立起某種對映關係，使每個資料元素與每乙個儲存位址之間盡量達到一一對應的目的。這樣，查詢時同樣可大大提高效率。
4．資料結構的研究內容
資料結構的核心研究內容包括三個方面：資料的邏輯結構、儲存結構以及相應的基本操作運算的定義和實現。
5．演算法的五個重要特徵
（1）有窮性：乙個演算法必須保證在執行有限步驟之後結束，而不是無限的。
（2）確定性：演算法中每一條指令必須有明確的含義，而不能是模稜兩可的。
（3）可行性：每乙個操作步驟都必須在有限的時間內完成。
（4）輸入：乙個演算法可以有乙個或多個輸入，也可以沒有輸入。
（5）輸出：乙個演算法可以有乙個或多個輸出。沒有輸出的演算法是沒有實際意義的。
6．演算法的評價標準
（1）正確性。
（2）易讀性。
（3）高效性。
（4）可維護性。
7．演算法分析的目的
演算法分析主要是指分析演算法的效率。演算法效率的度量主要從兩個方面：演算法的執行時間和演算法所需的儲存空間。
分析的目的是通過考察演算法的時間和空間效率，以求改進演算法或對不同的演算法進行比較。一般情況下，鑑於運算空間（記憶體）較為充足，所以把演算法的時間複雜度分析作為重點。
8．演算法的時間複雜度分析
（1）演算法運算時間的度量的兩種方法：事後統計的方法和事前分析估算的方法。
（2）演算法執行時間的分析規則
通常把乙個程式的執行時間定義為乙個t（n），其中n是該程式輸入資料的規模，而不是某乙個具體的輸入。t(n)的單位是不確定的，一般把它看成在乙個特定計算機上執行的指令條數。通常記作：
t(n)=o(f(n))，其中f(n)表示資料輸入規模。
常見的演算法時間複雜度的形式按效能降序的排列如下：
o(1)【例1-1】分析以下程式段的時間複雜度。
for(i=0;ifor(j=0;j a[i][j]=0;
解：該程式段的時間複雜度為o(m*n)。
【例1-2】分析以下程式段的時間複雜度。
i=s=0; ①
while(s
解：語句①為賦值語句，其執行次數為1次，所以其時間複雜度為o(1)。語句②和語句③構成while迴圈語句的迴圈體，它們的執行次數由迴圈控制條件中s與n的值確定。
假定迴圈重複執行x次後結束， 則語句②和語句③各重複執行了x次。其時間複雜度按線性累加規則為o(x)。此時s與n滿足關係式：
s≥n，而s=1+2+3+…+x。所以有：1+2+3+…+x≥n，可以推出：
x=x與n之間滿足x=f(），所以迴圈體的時間複雜度為o()，語句①與迴圈體由線性累加規則得到該程式段的時間複雜度為o(）。
【例1-3】分析以下程式段的時間複雜度。
i=1; ①
while(i<=n)
i=2*i; ②
解：其中語句①的執行次數是1，設語句②的執行次數為f(n)，則有：。
得：t（n）=o()
【例1-4】有如下遞迴函式fact(n)，分析其時間複雜度。
fact(int n)
解：設fact（n）的執行時間函式是t(n)。該函式中語句①的執行時間是o(1)，語句②的執行時間是t(n-1)+ o(1)，其中o(1)為常量執行時間。
由此可得fact（n）的時間複雜度為 o(n)。
9．演算法空間複雜度的含義
空間複雜度是對乙個演算法在執行過程中臨時占用儲存空間大小的量度。演算法在計算機儲存器內占用的儲存空間主要分為三部分：演算法源**本身占用的儲存空間；演算法輸入輸出資料所占用的儲存空間；演算法執行過程中臨時占用的儲存空間。
考慮乙個演算法的空間複雜度時，要綜合分析這三個方面的因素。通常記作：s(n)=o(f(n))，其中n為問題的規模（或大小）。
1. 資料結構是指（ a ）。
a.資料元素的組織形式 b.資料型別
c.資料儲存結構d.資料定義
2. 資料在計算機儲存器內表示時，實體地址與邏輯位址不相同的，稱之為（c ）。
a.儲存結構b.邏輯結構
c.鏈式儲存結構d.順序儲存結構
3. 樹形結構是資料元素之間存在一種（d ）。
a.一對一關係b.多對多關係
c.多對一關係d.一對多關係
4. 設語句x++的時間是單位時間，則以下語句的時間複雜度為（ b ）。
for(i=1; i<=n; i++)
for(j=i; j<=n; j++)
x++;
5. 演算法分析的目的是（1），演算法分析的兩個主要方面是（2）。
（1） a.找出資料結構的合理性b.研究演算法中的輸入和輸出關係
c.分析演算法的效率以求改進 d.分析演算法的易懂性和文件性
（2） a.空間複雜度和時間複雜度 b.正確性和簡明性
c.可讀性和文件性d.資料複雜性和程式複雜性
6. 計算機演算法指的是（1），它具備輸入，輸出和（2）等五個特性。
（1） a.計算方法b.排序方法
c.解決問題的有限運算序列 d.排程方法
（2） a.可行性，可移植性和可擴充性 b.可行性，確定性和有窮性
c.確定性，有窮性和穩定性 d.易讀性，穩定性和安全性
7. 資料在計算機內有鏈式和順序兩種儲存方式，在儲存空間使用的靈活性上，鏈式儲存比順序儲存要（b ）。
a.低b.高c.相同d.不好說
8. 資料結構作為一門獨立的課程出現是在（d ）年。
a.1946b.1953c.1964d.1968
9. 資料結構只是研究資料的邏輯結構和物理結構，這種觀點（b ）。
a.正確b.錯誤
c.前半句對，後半句錯d.前半句錯，後半句對
10. 計算機內部資料處理的基本單位是（b ）。
a.資料b.資料元素 c.資料項 d.資料庫
1. 資料結構按邏輯結構可分為兩大類，分別是線性結構和非線性結構。
2. 資料的邏輯結構有四種基本形態，分別是_集合、___線性數和__圖
3. 線性結構反映結點間的邏輯關係是____一對一_____的，非線性結構反映結點間的邏輯關係是_一對多或多對多的。
4. 乙個演算法的效率可分為____時間效率和______空間效率。
5. 在樹型結構中，樹根結點沒有_____前驅結點，其餘每個結點的有且只有一________個前趨驅結點；葉子結點沒有____後繼結點；其餘每個結點的後續結點可以________多
6. 在圖型結構中，每個結點的前趨結點數和後續結點數可以____有多個
7. 線性結構中元素之間存在_____一對一關係；樹型結構中元素之間存在______一對多關係；圖型結構中元素之間存在_____多對多_________關係。
8. 下面程式段的時間複雜度是____ o
for(i=0;ifor(j=0;ja[i][j]=0;
9. 下面程式段的時間複雜度是_______ o
i=s=0;
while(s
10. 下面程式段的時間複雜度是______ o
s=0;
for(i=0;i 一 內容要點 一 演算法 1 演算法的基本概念 演算法是指解題方 而完整的描述。即是一組嚴謹地定義運算順序的規則，並且每乙個規則都是有效的，且是明確的，沒有二義性，同時該規則將在有限次運算後可終止。1 演算法的基本特徵 1 可行性 由於演算法的設計是為了在某乙個特定的計算工具上解決某乙個實際的問題而... 1.演算法時間複雜度 當問題規模n趨向無窮大時，時間複雜度t n 的數量級 階 稱為演算法的時間複雜度 t n o f n 簡稱為時間複雜度，不作特別說明下，我們討論的時間複雜度是最壞情況下的時間複雜度。2.氣泡排序另一種寫法 void bubblesort int a,int n i lastex... 第一章習題 一 單項選擇題1.資料結構是一門研究非數值計算的程式設計問題中計算機的 以及它們之間的 和運算等的學科。a 操作物件 b 計算方法 c 邏輯儲存 d 資料映象 a 結構 b 關係 c 運算 d 演算法2.演算法分析的目的是 演算法分析的兩個主要方面是 a 找出資料結構的合理性 b 研究演...第一章資料結構與演算法
演算法與資料結構第一章概論筆記
資料結構第一章習題