資料結構——緒論

1.1 學習資料結構的意義和要求

意義：算法和資料結構是計算機科學的兩大支柱。

計算機科學早期定義為：研究算法的科學。

計算機科學近期定義為：研究資料的科學。

資料結構是程式設計的基礎。

程式 = 算法 + 資料結構。

資料結構是設計OS、DBMS、編譯等系統程式和各種應用程式的重要基礎。

要求：

1. 掌握各類基本資料結構類型和相應的存儲結構。

2. 提高閱讀和編寫算法的能力。

3. 能針對給定問題，選擇相适應的資料結構，并能設計和分析算法。

1.2 資料結構的主要内容

例1： 在計算機中有如下一串資料： 980803 3202670 610054 510102780618748。

整理之後： 980803 班号 3202670 電話号碼 610054 郵政編碼 510102780618748 其他資訊編碼

結論一：雜亂的資料不能表達和交流資訊。

例2： 電話号碼簿(a1 b1) (a2 b2) ...... (an bn)。 其中：ai為某人姓名，bi為該人的電話号碼。 要求：設計一個算法，給定一個姓名時，能查出此人的電話号碼。

算法一：如果姓名和電話号碼的排列次序無規律，則隻能逐一比較姓名進行查找。 算法二：如果姓名按字典順序組織，則查找就快捷多了。

結論二：資料之間是有聯系的。

例3： 某大學生管理機構：

學校 —— 系 系 —— 年級 年級 —— 班級 班級 —— 學生

例3中資料之間呈分層結構（樹狀結構）。

結論三：資料之間是有結構的。

例4： 圖書目錄管理 設每個書目含：書名、作者、登陸号、分類、出版年月 對圖書目錄常有如下操作： 查找：某書在書庫中是否存在。 插入：購進新書時的錄入。 删除：報廢和丢失的書，需從目錄中去掉。

結論四：在某種資料結構上可定義一組運算。

綜上所述： DS主要研究内容： 1. 資料的各種邏輯結構和實體結構，以及它們之間的相應關系。 2. 并對每種結構定義相适應的各種運算。 3. 設計出相應的算法。 4. 分析算法的效率。

1.3 基本術語

資料：所有能被計算機處理的符号的集合。

資料元素：是資料這個集合中的一個個體。 設給定資料集合為：D = {d1 d2 ... dn}，則di屬于D，并稱di為資料元素。

資料項：資料元素常常還可分為若幹個資料項，資料項是資料具有意義的最小機關。

資料對象：具有相同特性的資料元素的集合。 設資料集合D = {0 1 ... A B ... Z}，則：資料對象正整數N = {0 1 ... }，資料對象字母C = {A B ... Z}。 資料元素是資料的一個個體，資料對象是資料的一個子集。

資料結構：是帶有結構的資料元素的集合。

所謂結構就是資料元素之間的關系，即描述資料之間的運算及運算規則。

用集合的形式描述，資料結構就是一個二進制組：DS = (D R)。 其中：D是資料元素的集合，R是D上關系的集合。 簡言之，資料元素和其互相關系稱為資料結構。

邏輯結構：指資料元素之間的結構關系。 實體結構：指資料結構在計算機内的表示。

1.4 算法描述和算法分析

算法概念：算法是一個有限的指令集，遵循指令流可以完成特定的功能。

算法的基本特性： 1. 有窮性：算法經有限步後結束。 2. 确定性：下一步必須是明确的。 3. 可行性：每一步是可執行的。

算法與程式的差別： 算法是解決問題的一種方法或一個過程，考慮如何将輸入轉換成輸出，一個問題可以有多種算法。

程式是用某種程式設計語言對算法的具體實作。

主要差別在：有窮性、正确定和描述方法。 1. 程式可以是無窮的，例如OS，算法是有窮的。 2. 程式可以是錯誤的，算法必須是正确的。 3. 程式是用程式設計語言描述，在機器上可以執行。 4. 算法還可以用框圖、自然語言等方式描述。

算法分析： 如何衡量一個正确算法的好壞？ 衡量的三個尺度： 1. 運作所花費的時間（算法的時間特性）。 2. 所占用存儲空間的大小（算法的空間特性）。 3. 其他（可讀性、易調性、健壯性等）。

語句頻度：語句可能重複執行的最大次數。

時間複雜度：設算法中所有語句的語句頻度為t(n)，f(n)是當n趨向無窮大時與t(n)為同階無窮大，則算法的時間複雜度T(n)=O(f(n))。 其中：n為算法計算量或為規模，f(n)是運算時間随n增大時的增長率，O(f(n))是算法時間特性的量度。

例如： 程式段                    語句頻度                    時間複雜度 x=x+1                      1                                 O(1) 常數階

for(i=0;i<n;i++)      n+1                            O(n) 線性階    x=x+1

for(i=0;i<n;i++)      n+1    for(j=0;j<n;j++)   n(n+1)                       O(n^2) 平方階        x=x+1

算法與時間複雜性的關系 設A1，A2和A3是求解同一問題的不同算法，其時間複雜度分别為：O(n) O(nlogn) O(n!)。 C1和C2為計算機，且C2的計算速度是C1的10倍。

複雜度          C1可解規模          C2可解規模          可解規模關系 O(n)              N11                        N21                       N21 = 10 N11 O(nlogn)      N12                        N22                       N22 = 10 N12 O(n!)             N13                        N23                       N23 = N13 + 小常數