序言1、課程簡介
資料結構是計算機及應用專業的一門專業基礎課，在計算機軟體的各個領域中均會使用到資料結構的有關知識。隨著對軟體發展的需求越來越高；需要越來越多的人挖掘設計高效能軟體技術，以推動社會資訊化的發展。同時，因為無論是系統軟體還是應用軟體，其核心是資料結構及其演算法，所以作為軟體設計技術的理論基礎，「資料結構」就不僅是計算機的核心課程，也應該是所有計算機的其它學科所必須掌握的課程。
本書是為配合函授教育計算機及應用專業資料結構課程第一章到第十章的學習而編寫的輔助教材，該課程的主教材是《資料結構基礎》（第四版）（曹桂琴編著大連理工大學出版社）。
2、學習方法
（1）資料結構作為計算機及應用專業的一門專業基礎課，具有內容多、難度大的特點。學習資料結構前需要具備相關方面的知識，特別是高階程式語言的知識。由於本書中對演算法的描述採用的是c語言，所以學習本書之前要熟練地掌握c語言（尤其c語言的指標部分和結構體部分），且能靈活應用。
（2）對於本書提到的各種資料結構要深入理解它們之間的關係，要從定義和實現兩個層次去分析各種資料結構。
（3）本書的難點是關於資料結構的各種演算法，在設計演算法前，一定要針對課本先閱讀一定數量的演算法，理清其思路，弄清演算法的基本思想，然後由淺到深，自己設計演算法。當然這不是一件容易的事，除了要掌握必要的方法外，還要自己進行大量的練習，培養自己分析問題並解決問題的能力。設計演算法的步驟如下：
①確定解題的目標；②選擇合適的資料結構；③確定在所選擇的資料結構上應該進行哪些操作，寫出相應的演算法；④確定合適的儲存結構，寫出最終程式。
（4）資料結構儘管有各種不同的形式，但是在學習時，不要將各章的內容孤立起來，要注意分析各種資料結構之間的相互聯絡，找出它們之間的共同點和不同點。
（5）在學習完每章內容之後，做一定量的習題是很有必要的。做好本書所提供的習題，有助於讀者理解、消化所學教材內容，找到自己的不足之處，有助於提高讀者分析問題、解決問題的能力。
（6）在學習過程中，要注意實踐，培養自己的上機操作能力，在操作過程中能加深對基礎知識尤其是演算法的理解。
考前，做幾套模擬試題，一方面有助於讀者鞏固所學知識，針對自己的實際情況查漏補缺；另一方面可以訓練和提高自己應試的心理素質。
自學進度表
第一章緒論
一、 內容提示
1． 概念和術語
（1）資料：是對客觀事物的符號表示，在電腦科學中是指所有能輸入到計算機中並被電腦程式處理的符號的總稱。資料是資訊的載體。
（2）資料元素：是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。有時，乙個資料元素可由若干資料項組成。
例如，一本書的書目資訊為乙個資料元素，而書目資訊中的每一項（如書名、作者名、出版社等）為乙個資料項。
（3）資料結構：是相互之間存在一種或多種特定關係的資料元素的集合，簡言之，就是資料之間的相互關係，即資料的組織形式。在任何問題中，資料元素都不是孤立存在的，而是在它們之間存在著某種關係，這種資料元素之間的相互關係稱為結構。
根據資料元素之間關係的不同特性，通常有：集合、線性、樹形、圖狀或網狀這4類基本結構。
（4）資料的邏輯結構：結構定義中的「關係」描述的是資料元素之間的邏輯關係，是對操作物件的一種數學描述，亦即從操作物件抽象出來的數學模型。例如，同一陣列中各元素的先後次序關係等。
資料的邏輯結構有兩類：線性結構和非線性結構。線性結構的邏輯特徵是：
若結構是非空，則有且僅有乙個開始元素和乙個終端元素，並且所有元素只有乙個直接前趨和乙個直接後繼。非線性結構的特徵是乙個元素可能有多個直接前趨和直接後繼。
（5）資料的物理結構：資料結構在計算機中的表示（又稱映象）稱為資料的物理結構，也稱儲存結構。它包括資料元素的表示和關係的表示。
在計算機中，可以用乙個二進位制位串表示乙個資料元素，通常稱這個位串為元素或結點。當資料元素由若干資料項組成時，位串中對應於各個資料項的子位串稱為資料域。因此，元素或結點可看成是資料元素在計算機中的映象。
資料元素之間的關係在計算機中有兩種不同的表示方法：順序映象和非順序映象，並由此得到幾種不同的儲存方式：①順序儲存方式，此方法主要應用於線性的資料結構；②鏈式儲存方式，此方法不要求邏輯上相鄰的結點在物理位置上也相鄰，結點的邏輯關係是由附加的指標字段表示的；③索引儲存方法，此方法通常是在儲存結點資訊的同時，還建立附加索引表；④雜湊儲存方法，此方法的基本思想是根據結點的鍵值直接計算出該結點的儲存位址。
（6）資料型別：是乙個值的集合和定義在該值集上的運算集合的總稱。例如c語言中的整型變數，其值集為整數，定義在其上運算為：
加、減、乘、除等。按「值」的不同特性，程式語言中的資料型別可分為原子型別和結構型別。
（7）抽象資料型別：是指抽象資料的組織和與之相關的操作。它可以看作是資料的邏輯結構及其定義在邏輯結構上的操作。
或說，抽象資料型別是指乙個數學模型以及定義在該模型上的一組操作。抽象資料型別的定義僅取決於它的一組邏輯特性，而與其在計算機內部如何表示和實現無關。抽象資料型別和資料型別實質上是乙個概念。
例如，各個計算機都擁有「整數」型別是乙個抽象資料型別，儘管它們在不同的計算機上的實現方法可以不同，但是由於其定義的數學特性相同，在使用者看來都是相同的。因此，「抽象」的意義在於資料型別的數學抽象特性。
（8）漸近時間複雜度：乙個演算法所耗費的時間，應該是該演算法中每條語句的執行時間之和，也就是演算法的時間複雜性（或者叫做演算法的時間複雜度），它是該演算法所求問題規模n的函式，表示為t(n)。當問題的複雜度n趨向無窮大時，將時間複雜度的數量級稱為演算法的漸近時間複雜度，簡稱時間複雜度。
時間複雜度的數量級的形式表示為：
t(n)=o(f(n))
其中大寫字母o為英文「數量級」一詞（order）的字頭，若f(n)是正整數n的函式，則t(n)=o(f(n))表示存在乙個正整數c，使得對所有n≥n0時，都有t(n)≤cf(n0)。
用數量級的形式表示t(n)，當t(n)為多項式時，可只取其最高次冪項，且它的係數也可略去不寫。例如若有
t(n)=3n3+5n+12
則t(n)=o(n3)。因為若令n0=1，對所有n≥n0，都有
3n3+5n+12≤3n3+5n3+12n3=20n3
當取c=20時，即有t(n)≤cn3。
用數量級表示t(n)時，只需取其最高次冪項，也可以這樣理解：無論該項的係數比起低次冪項的係數小多少，當n大到一定程度時總是最高次冪項佔t(n)的主要部分。如若有
t(n)=n2+1000 n
當n較小時，第二項較n2項數值要大，但當n >1000 以後，n2項就佔t(n)的主要部分了，故t(n)=o(n2)。由此可見，用數量級的形式表示，對n較大的情況是很合適的。
（9）語句的頻度：是指該語句重複執行的次數。
2． 描述演算法的類c語言
類c語言的書寫規範，值傳遞和位址傳遞的區別，輸入、輸出的方式以及錯誤處理方式。
3． 演算法設計的基本要求
（1） 正確性 （2）可讀性 （3）健壯性 （4）高效性。
4． 演算法分析
演算法是解決某一特定型別問題的有限運算的序列。描述乙個演算法可以採用某一種計算機語言，也可以採用流程圖。本書的演算法是採用c語言描述的。
評價乙個演算法一般從4個方面進行：正確性、執行時間、占用空間和簡單性。
正確性是指演算法的正確性。執行時間是指乙個演算法在計算機上執行所花費的時間，採用時間複雜度來度量。占用空間是指在計算機儲存器上所占用的儲存空間，主要考慮在演算法執行過程中臨時占用的儲存空間的大小，稱之為空間複雜度，一般以數量級形式給出。
簡單性是指演算法的易讀性等。
演算法分析包括從時間和空間方面對演算法進行特性分析，從時間方面的分析稱為時間複雜度；從空間方面的分析稱為空間複雜度。時間複雜度從好到壞的級別依次是：常量階o(1)、對數階o(log2n)、多項式階o(nk)、指數階o(2n)。
二、學習要求
1． 基本內容
（1）熟悉各名詞、術語的含義，掌握基本概念，特別是資料的邏輯結構和儲存結構之間的關係。分清哪些是邏輯結構的性質，哪些是儲存結核的性質。
（2）熟悉類c語言的書寫規範，特別要注意值傳遞和位址傳遞的區別。
2．重點與難點
（1） 理解判斷乙個演算法好壞的幾個主要標準
（2） 掌握計算語句頻度和估算演算法時間複雜度的方法
二、 例題與解答
1．試描述資料結構和抽象資料結構型別的概念與程式語言中資料型別概念的區別。
答案：簡單地說，資料結構定義了一組按某些關係結合在一起的陣列元素。資料型別不僅定義了一組帶結構的資料元素，而且還在其上定義了一組操作。
資料結構自學指導大綱
一 課程性質和特點 資料結構是計算機及應用專業的一門專業基礎課，在計算機軟體設計的各個領域中均會使用到資料結構的有關知識，也是各類計算機應用考核和計算機應用專業研究生考試必考科目。本課程要求學生較全面掌握各種常用資料結構，為學習後續軟體課程提供必要基礎，提高運用資料結構解決實際問題的能力。二 本課程...
資料結構實驗指導書
第一部分課程概述 資料結構是計算機程式設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已成為其它立功專業的熱門選修課。資料結構實驗可以使學生對資料結構課程所教授的內容通過實驗環節加以實踐，提高學生的程式設計 編寫及除錯能力，是一門基礎的實驗課程。第二部分實驗要求 通過實驗，學生對常用資料結...
資料結構實驗指導書
實驗名稱資料結構試驗 課程名稱資料結構 專業班級學生姓名 學號成績 指導老師實驗日期 2010年3月 5月 實驗報告如列印，紙張用a4，左裝訂 頁邊距 上下2.5cm，左2.5cm，右2.0cm 字型 字型小四號，1.25倍行距。驗證性 綜合性實驗報告應包含的主要內容 一 實驗目的及要求 1 實驗目...