《算法與數(shù)據(jù)結構》(C語言)講義

1、算法與數(shù)據(jù)結構（C語言）講義計算機科學系 陳雄峰一、課程目標 l、課程性質 算法與數(shù)據(jù)結構是計算機軟件和計算機應用專業(yè)的核心課程。在眾多的計算機系統(tǒng)軟件和應用軟件中都要用到各種數(shù)據(jù)結構。因此，僅掌握幾種計算機語言是難以應付眾多復雜的課題。要想有效地使用計算機，就必須學習數(shù)據(jù)結構的有關知識。算法與數(shù)據(jù)結構課程不僅為數(shù)據(jù)庫系統(tǒng)、操作系統(tǒng)、軟件工程等后繼課程提供必要的基礎知識，而且是實踐技能訓練的一個重要的教學環(huán)節(jié)。 2、教學方法：課堂講授和實驗上機結合為主 3、課程學習目標和基本要求 (1)通過學習學生要掌握基本數(shù)據(jù)結構的組成及其實現(xiàn)方法。學會分析研究計算機加工的數(shù)據(jù)對象的特性，以便選擇適當?shù)臄?shù)據(jù)

2、結構和存儲結構及相應的算法，并初步掌握抽象數(shù)據(jù)類型的設計及其相關算法的時間分析和空間分析技巧。 (2)通過學習，強化學生運用基本數(shù)據(jù)結構進行復雜程序設計的訓練過程。通過閉實驗和開實驗，體會計算機方法學的理論、抽象和設計這三個過程，提高利用計算機解決實際問題的實踐技能。 4、課程學時72學時，其中授課56學時，閉開實驗(上機)16學時 5、課程類型：必修課 6、先修課程：C程序設計，離散數(shù)學 二、課程內容 1、緒論(4學時) 知識點：數(shù)據(jù)與數(shù)據(jù)類型、數(shù)據(jù)結構、抽象數(shù)據(jù)類型、算法復雜性分析 重點：數(shù)據(jù)類型、數(shù)據(jù)結構難點：抽象數(shù)據(jù)類型本章介紹了數(shù)據(jù)結構這門學科誕生的背景、發(fā)展歷史以及在計算機科學中所

3、處的地位，重點介紹了數(shù)據(jù)結構有關的概念和術語，讀者學習本章后應能掌握數(shù)據(jù)、數(shù)據(jù)元素、邏輯結構、存儲結構、數(shù)據(jù)處理、數(shù)據(jù)結構、算法設計等基本概念，并了解如何評價一個算法的好壞。11 什么是數(shù)據(jù)結構:（1） 知識信息（現(xiàn)實世界）數(shù)據(jù)（計算機）（2） 解決問題的過程：物理模型數(shù)學模型（描述非數(shù)值計算需用數(shù)據(jù)結構）-算法程序結果（運行）例：線性結構、樹、圖1.2基本概念和術語（1） 數(shù)據(jù)（Data） （2） 數(shù)據(jù)元素（Data Element）數(shù)據(jù)項（Data Item）多個數(shù)據(jù)項數(shù)據(jù)元素->記錄文件（大量記錄）（3） 數(shù)據(jù)對象（Data Object）（4） 數(shù)據(jù)結構（Data Structu

4、re） 是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關系，這種數(shù)據(jù)元素相互之間的關系稱為結構（Structure）。通常有下列四類基本結構：（1） 集合 結構中的數(shù)據(jù)元素之間除了"同屬于一個集合"的關系外，別無其它關系；數(shù)據(jù)元素各不相同（2） 線性結構 結構中的數(shù)據(jù)元素之間存在一個對一個關系；（3） 樹形結構 結構中的數(shù)據(jù)元素之間存在一個對多個的關系；（4） 圖形結構或網(wǎng)狀結構 結構中的數(shù)據(jù)元素之間存在多個對多個的關系。A、數(shù)據(jù)結構的形式定義為：數(shù)據(jù)結構是一個二元組Data-Structure=（D，S） (1-1)其

5、中：D是數(shù)據(jù)元素的有限集，S 是D上關系的有限集。下面舉兩個簡單例子說明之。例1-4 在計算機科學中，復數(shù)可取如下定義：復數(shù)是一種數(shù)據(jù)結構例1-5課題小組設計一個數(shù)據(jù)結構。假設每個小組由一位教師、一至三名研究生及一至六名本科生組成，小組成員之間的關系是：教師指導研究生，而由每位研究生指導一至兩名本科生。則可以如下定義數(shù)據(jù)結構：B、邏輯結構。結構定義中的"關系"描述的是數(shù)據(jù)元素之間的邏輯關系，因此又稱為數(shù)據(jù)的邏輯結構。C、物理結構，又稱存儲結構。數(shù)據(jù)結構在計算機中的表示（又稱映象）稱為數(shù)據(jù)的物理結構，又稱存儲結構。它包括數(shù)據(jù)元素的表示和關系的表示。位(bit)，元素（Elem

6、ent）或結點（Node），數(shù)據(jù)域（Data Field）。數(shù)據(jù)元素之間的關系在計算機中有兩種不同的表示方法：順序映象和非順序映象，并由此得到兩種不同的存儲結構：順序映象結構和鏈式存儲結構。順序映象的特點是借助元素在存儲中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。非順序映象的特點是借助指示元素存儲的指針（Pointer）表示數(shù)據(jù)元素之間的邏輯關系。如：Z1=3.0-2.3i和z2=-0.7+4.8i，虛部的存貯地址圖1。6復數(shù)存儲結構示意圖D、數(shù)據(jù)結構分類:（1）邏輯結構：.線性結構 ² 線性表² 棧和隊列² 串² 數(shù)組/廣義表非線性結構 ² 樹

7、及二叉樹² 圖 ² 文件(2)物理結構（存儲結構）² 順序存儲結構² 非順序存儲結構：鏈式存儲結構、散列表式（索引）存儲結構（5）數(shù)據(jù)類型（Data Type）：程序設計語言中變量可取的數(shù)據(jù)種類；表示數(shù)據(jù)對象的特性，隱含取值范圍和操作。（6）抽象數(shù)據(jù)類型（Abstract Data Type 簡稱ADT）是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型 的定義僅取決于它的一組邏輯特性，而與其在計算機內部如何表示和現(xiàn)實無關，即不論其內部結構如何 變化，只要它的數(shù)學 特性 不變，都不影響其外部的使用。若按其值的不同特性，可分為三種類型：原子類型（A

8、tomic Data Type）屬原子類型的變量的值是不可分解的。固定聚合類型（Variable-Aggregate Data Type)屬該類型的變量，其值由確定數(shù)目的成分按某種結構組成?？勺兙酆项愋停╒ariable-Aggregate Data Type）和固定聚合類型相比較，構成可變聚合類型“值”的成分數(shù)目不確定。抽象數(shù)據(jù)類型可用以下三元組表示（D,S,P）其中，D是數(shù)據(jù)對象， S是D上的關系集，P是對D的基本操作集。本書采用以下格式定義抽象數(shù)據(jù)類型：ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對象：數(shù)據(jù)對象的定義數(shù)據(jù)關系：數(shù)據(jù)關系的定義基本操作：基本操作的定義ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對象和數(shù)據(jù)關系

9、的定義用偽碼描述，基本操作的定義格式為基本操作名（參數(shù)表）初始條件：初始條件描述操作結果：操作結果描述基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值以外，還將返回操作結果，“初始條件”描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息?！安僮鹘Y果”說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。如初始條件為空，則省略之。例 1-6抽象數(shù)據(jù)類型三元組的定義：ADT Triplet數(shù)據(jù)對象：D=e1,e2,e3 /e1,e2,e3 ElemSet(定義了關系運算的某個集合)數(shù)據(jù)關系：R1=<e1,e2&g

10、t;,<e2,e3>基本操作：InitTriplet(&T,v1,v2,v3)操作結果：結構了三元 T ，元素 e1 ，e2 和 e3 分別被賦以參數(shù) v1 ，v2 和v3 的值。DestroyTriplet(&T)操作結果：三元組T被銷毀。Get(T,i,&e)初始條件：三元組 T 已存在，1<=i<=3.操作結果：用e 返回T 的第i 元的值。Put(&T,i,e)初始條件：三元組 T已存在，1<=i<=3.操作結果：改變 T 的第i 元的值為e 。IsAscending(T)初始條件：三元組T 已存在。操作結果：如果T

11、的三個元素按升序排列，則返回1，否則返回0。IsDescending(T)初始條件：三元組T 已存在。操作結果：如果T 的三個元素中的按降序排列，則返回1，否則返回0。Max(T,&e)初始條件：三元組T 已存在。操作結果：用 e 返回T 的三個元素中的最大值。Min(T,&e)初始條件：三元T 已存在。操作結果：用e 返回T 的三個元素中的最小值。ADT Triplet（7）多形數(shù)據(jù)類型 （Polymorphic Data Type ）：數(shù)據(jù)成分不確定的數(shù)據(jù)類型。1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)（1） 預定義常量和類型/ 函數(shù)結果狀態(tài)代碼#define TRUE 1#defi

12、ne FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/ status 是函數(shù)的類型，其值是函數(shù)結果狀態(tài)代碼typedef int Status;(2)數(shù)據(jù)結構的表示（存儲結構）用類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType,由用戶在使用該數(shù)據(jù)類型時自行定義。(3) 基本操作的算法都用以下形式的函數(shù)描述：數(shù)據(jù)類型 函數(shù)名（函數(shù)參數(shù)表）/算法說明語句序列 / 函數(shù)名（4）賦值語句有（5）選擇語句有(6)循環(huán)語句有(7)結束語句有(8)輸入和輸出語句有(10)基本函數(shù)有(11）

13、邏輯運算約定1.4 算法和算法分析1.4.1 算法算法（Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；此外，一個算法還具有下列五個重要特征：² 有窮性 ² 確定性 ² 可行性 ：時間、費用。² 輸入 ² 輸出 1.4.2 算法設計的要求通常設計一個“好”的算法應考慮達到以下目標：² 正確性（Correctness） ² 可讀性（Readability） ² 健壯性（Robustness） ² 效率與存儲量需求 ² 執(zhí)行時間短的算法效率高

14、² 低存儲量需求這兩者都與問題的規(guī)模有關1.4.3 算法效率的度量² 事后統(tǒng)計的方法 ² 事前分析估算的方法 例如，在如下所示的兩個N*N矩陣相乘的算法中，“乘法”運算是“矩陣相乘問題”的基本操作。整個算法的執(zhí)行時間與該基本操作（乘法）重復執(zhí)行的次數(shù)n成正比，記作T(n)=O(n).for (i=1;i<=n;+i)for (j=1;j<=n;+j)cij=0;for (k=1;k<=n;+k)cij+=aij*bkj;一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作T（n）=O(f(n)，它表示隨問題規(guī)

15、模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度（Asymptotic Time Complexity）,簡稱時間復雜度。語句的頻度（Frequency Count）指的是該語句重復執(zhí)行的次數(shù)。例如：在下列三個程序段中，² +=x;s=0; ² for (i=1;i<=n;+i)+x;s+=x; ² for (j=1;j<=n;+j)for (k=1;k<=n;+k)+x;s+=x; 含基本操作“x增1”的語句的頻度分別為1，n和n，則這三個程序段的時間復雜度分別為O(1),O(n)和O(n)，分別稱為常量階、線性

16、階和平方階。Log2n n nlog2n n2 n3 2n n!1.4.4 算法的存儲空間要求空間復雜度（Space Complexity）作為算法所需存儲空間的度量，記作S(n)=O(f(n)其中n為問題的規(guī)模（或大?。１菊滦〗Y本章主要介紹了如下一些基本概念：數(shù)據(jù)結構：數(shù)據(jù)結構是研究數(shù)據(jù)元素之間抽象化的相互關系和這種關系在計算機中的存儲表示（即所謂數(shù)據(jù)的邏輯結構和物理結構），并對這種結構定義相適應的運算，設計出相應的算法，而且確保經(jīng)過這些運算后所得到的新結構仍然是原來的結構類型。數(shù)據(jù)：數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述。在計算機科學中，數(shù)據(jù)

17、的含義非常廣泛，我們把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。結點：結點也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。邏輯結構：結點和結點之間的邏輯關系稱為數(shù)據(jù)的邏輯結構。存儲結構：數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構。數(shù)據(jù)處理：數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。數(shù)據(jù)類型：數(shù)據(jù)類型是指程序設計語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設計語言中的一個基本概念，它和數(shù)據(jù)結構的概念密切相關。 （線性結構）2、線性表(8學時)知識點：ADT表的概念、表的各種實現(xiàn)方法、循環(huán)鏈表和雙鏈表重點：表的數(shù)組和鏈接實現(xiàn)

18、難點：表的鏈接實現(xiàn)線性表（Linear list）是最簡單且最常用的一種數(shù)據(jù)結構。這種結構具有下列特點：存在一個唯一的沒有前驅的（頭）數(shù)據(jù)元素；存在一個唯一的沒有后繼的（尾）數(shù)據(jù)元素；此外，每一個數(shù)據(jù)元素均有一個直接前驅和一個直接后繼數(shù)據(jù)元素。通過本章的學習，讀者應能掌握線性表的邏輯結構和存儲結構，以及線性表的基本運算以及實現(xiàn)算法。 2.1 線性表的邏輯結構一個線性表是n0個數(shù)據(jù)元素a0，a1，a2，an-1的有限序列（p）。抽象數(shù)據(jù)類型線性表的定義如下：LinearList=(D,R)其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1 R=<ai-1，ai>

19、| ai-1，aiD, i=0,1,2, ，n-1 Elemset為某一數(shù)據(jù)對象集；n為線性表的長度。數(shù)據(jù)項數(shù)據(jù)元素->記錄文件（大量記錄）線性表的主要操作有如下幾種：(p)講解用已有的基本操作實現(xiàn)特定功能。實現(xiàn)基本操作因物理結構不同分為：順序和非順序（鏈式）；2.2.2 線性表在順序存儲結構下的運算可用C語言描述順序存儲結構下的線性表（順序表）如下：#define TRUE 1 #define FALSE 0#define MAXNUM <順序表最大元素個數(shù)>Elemtype ListMAXNUM ; /*定義順序表List*/int num=-1; /*定義當前數(shù)據(jù)元素下

20、標，并初始化*/我們還可將數(shù)組和表長封裝在一個結構體中：struct Linear_list Elemtype ListMAXNUM; /*定義數(shù)組域*/int length; /*定義表長域*/1. 順序表的插入操作(P)順序表的刪除操作 3順序表存儲結構的特點線性表的順序存儲結構中任意數(shù)據(jù)元素的存儲地址可由公式直接導出，因此順序存儲結構的線性表是可以隨機存取其中的任意元素。也就是說定位操作可以直接實現(xiàn)。高級程序設計語言提供的數(shù)組數(shù)據(jù)類型可以直接定義順序存儲結構的線性表，使其程序設計十分方便。但是，順序存儲結構也有一些不方便之處，主要表現(xiàn)在：（1）數(shù)據(jù)元素最大個數(shù)需預先確定，使得高級程序設計

21、語言編譯系統(tǒng)需預先分配相應的存儲空間。（2）插入與刪除運算的效率很低。為了保持線性表中的數(shù)據(jù)元素的順序，在插入操作和刪除操作時需移動大量數(shù)據(jù)。這對于插入和刪除操作頻繁的線性表、以及每個數(shù)據(jù)元素所占字節(jié)較大的問題將導致系統(tǒng)的運行速度難以提高。（3）順序存儲結構的線性表的存儲空間不便于擴充。當一個線性表分配順序存儲空間后，如果線性表的存儲空間已滿，但還需要插入新的元素，則會發(fā)生“上溢”錯誤。在這種情況下，如果在原線性表的存儲空間后找不到與之連續(xù)的可用空間，則會導致運算的失敗或中斷。2.3 線性表的鏈式存儲結構2.3.1 線性鏈表 1線性鏈表在C語言中，定義鏈表結點的形式如下：struct 結構體名

22、 數(shù)據(jù)成員表；struct 結構體名 * 指針變量名；例如，下面定義的結點類型中，數(shù)據(jù)域包含三個數(shù)據(jù)項：學號、姓名、成績。Struct student char num8; /*數(shù)據(jù)域*/char name8; /*數(shù)據(jù)域*/int score; /*數(shù)據(jù)域*/struct student *next; /*指針域*/假設h,p,q為指針變量，可用下列語句來說明：struct student *h,*p,*q;在C語言中，用戶可以利用malloc函數(shù)向系統(tǒng)申請分配鏈表結點的存儲空間，該函數(shù)返回存儲區(qū)的首地址，如：p=(struct student *)malloc(sizeof(struct

23、student);指針p指向一個新分配的結點。如果要把此結點歸還給系統(tǒng)，則用函數(shù)free(p)來實現(xiàn)。線性鏈表的基本操作下面給出的單鏈表的基本操作實現(xiàn)算法都是以圖2-7所示的帶頭結點的單鏈表為數(shù)據(jù)結構基礎。單鏈表結點結構定義為：Typedef struct slnode Elemtype data;struct slnode *next;slnodetype; slnodetype *p,*q,*s;（1）初始化【算法2.3 單鏈表的初始化】int Initiate(slnodetype * *h) if(*h=(slnodetype*)malloc(sizeof(slnodetype)=NU

24、LL) return FALSE;(*h)->next=NULL;return TRUE; 注意：形參h定義為指針的指針類型，若定義為指針類型，將無法帶回函數(shù)中建立的頭指針值。（2）單鏈表的插入操作1）已知線性鏈表head，在p指針所指向的結點后插入一個元素x。在一個結點后插入數(shù)據(jù)元素時，操作較為簡單，不用查找便可直接插入。操作過程如圖2-8所示。相關語句如下：【算法2.4 單鏈表的后插入】 s=(slnodetype*)malloc(sizeof(slnodetype);s->data=x;s->next=p->next;p->next=s;2）已知線性鏈表he

25、ad，在p指針所指向的結點前插入一個元素x。前插時，必須從鏈表的頭結點開始，找到P指針所指向的結點的前驅。設一指針q從附加頭結點開始向后移動進行查找，直到p的前趨結點為止。然后在q指針所指的結點和p指針所指的結點之間插入結點s。 操作過程如圖2-9所示。相關語句如下：【算法2.5 單鏈表的結點前插入】q=head; while(q->next!=p) q=q->next; s=(slnodetype*)malloc(sizeof(slnodetype); s->data=x; s->next=p; q->next=s;算法2.6 單鏈表的后插入】int inser

26、t(slnodetype *h,int i,Elemtype x)/*在鏈表h中，在第i個數(shù)據(jù)元素插入一個數(shù)據(jù)元素x */ slnodetype *p,*q,*s; int j=0; p=h; while(p!=NULL&&j<i-1) p=q->next;j+; /*尋找第i-1個結點*/ if ( j!=i-1) printf(“Error!”);return FALSE; /*插入位置錯誤*/ if (s=(slnodetype*)malloc(sizeof(slnodetype)=NULL) return FALSE; s->data=x; s->

27、;next=p->next; q->next=s; return TRUE;例：下面C程序中的功能是，首先建立一個線性鏈表head=3，5，7，9，其元素值依次為從鍵盤輸入正整數(shù)（以輸入一個非正整數(shù)為結束）；在線性表中值為x的元素前插入一個值為y的數(shù)據(jù)元素。若值為x的結點不存在，則將y插在表尾。#include “stdlib.h”#include “stdio.h”struct slnodeint data;struct slnode *next; /*定義結點類型*/main()int x,y,d;struct slnode *head,*p,*q,*s; head=NULL;

28、 /*置鏈表空*/ q=NULL; scanf(“%d”,&d); /*輸入鏈表數(shù)據(jù)元素*/ while(d>0)p=(struct slnode*)malloc(sizeof(struct slnode); /*申請一個新結點*/ p->data=d; p->next=NULL; if(head=NULL) head=p; /*若鏈表為空，則將頭指針指向當前結點p*/ else q->next=p; /*鏈表不為空時，則將新結點鏈接在最后*/ q=p; /*將指針q指向鏈表的最后一個結點*/ scanf(“%d”,&d);內循環(huán)結束 scanf(“%d

29、,%d”,&x,&y); s=(struct slnode*)malloc(sizeof(struct slnode); s->data=y; q=head;p=q->next; while(p!=NULL)&&(p->data!=x) q=p;p=p->next; /*查找元素為x的指針*/ s->next=p;q->next=s; /*插入元素y*/ ² 比較有無head的建立。² 比較是否用第三條鏈的歸并。² 比較刪除條件P!=NULL與P->next!=NULL² 思考：單

30、鏈表倒置、判斷對稱。（3）單鏈表的刪除操作請讀者比較插入算法與刪除算法中所用的條件(p!=NULL&&j<i-1)與(p->next!=NULL&&j<i-1)的不同。雖然在線性鏈表中插入或刪除結點不需要移動別的數(shù)據(jù)元素，但算法尋找第i-1個或第i個結點的時間復雜度為O(n)。例：假設已有線性鏈表La，編制算法將該鏈表逆置。利用頭結點和第一個存放數(shù)據(jù)元素的結點之間不斷插入后繼元素結點。如圖2-11所示。2.3.2 循環(huán)鏈表循環(huán)鏈表(Circular Linked List)是另一種形式的鏈式存儲結構。是將單鏈表的表中最后一個結點指針指向鏈表的表

31、頭結點，整個鏈表形成一個環(huán)，這樣從表中任一結點出發(fā)都可找到表中其他的結點。圖2-12（a）為帶頭結點的循環(huán)單鏈表的空表形式，圖2-12（b）為帶頭結點的循環(huán)單鏈表的一般形式。帶頭結點的循環(huán)鏈表的操作實現(xiàn)算法和帶頭結點的單鏈表的操作實現(xiàn)算法類同，差別在于算法中的條件在單鏈表中為p!=null或p->next!=null；而在循環(huán)鏈表中應改為p!=head或p->next!=head。在循環(huán)鏈表中，除了頭指針head外，有時還加了一個尾指針rear，尾指針read指向最后一結點，從最后一個結點的指針又可立即找到鏈表的第一個結點。在實際應用中，使用尾指針代替頭指針來進行某些操作，往往更簡

32、單。例：將兩個循環(huán)鏈表首尾相接。La為第一個循環(huán)鏈表表尾指針，Lb為第二個循環(huán)鏈表表尾指針。合并后Lb為新鏈表的尾指針。Void merge(slnodetype *La,slnodetype *Lb) slnodetype *p; p=Lb->next; /*p為lb的頭結點*/ Lb->next= La->next; La->next=p->next; free(p); 2.3.3 雙向鏈表1雙向鏈表typedef struct nodeElemtype data; struct node *prior,*next; dlnodetype;若p為指向雙向鏈表中

33、的某一個結點ai的指針，則顯然有：p->next->prior=p->prior->next=p在雙向鏈表中，有些操作如：求長度、取元素、定位等，因僅需涉及一個方向的指針，故它們的算法與線性鏈表的操作相同；但在插入、刪除時，則需同時修改兩個方向上的指針，兩者的操作的時間復雜度均為O(n)。2雙向鏈表的基本操作（1）在雙向鏈表中插入一個結點2）在雙向鏈表中刪除一個結點討論：我們在雙向鏈表中進行刪除操作時，還需注意下面兩種情況：1）當刪除鏈表的第一個結點時，應將鏈表開始結點的指針指向鏈表的第二個結點，同時將鏈表的第二個結點的prior置為NULL。2）當刪除鏈表的最后一個結

34、點時，只需將鏈表的最后一個結點的上一個結點的next置為NULL即可。但是鏈式存儲結構也有不足之處：（1）每個結點中的指針域需額外占用存儲空間。當每個結點的數(shù)據(jù)域所占字節(jié)不多時，指針域所占存儲空間的比重就顯得很大。（2）鏈式存儲結構是一種非隨機存儲結構。對任一結點的操作都要從頭指針依指針鏈查找到該結點，這增加了算法的復雜度。2.4 一元多項式的表示及相加符號多項式的表示及其操作是線性表處理的典型用例，在數(shù)學上，一個一元多項式Pn(x) 可以表示為 ：Pn(x)=a0+a1x+a2x2+anxn (最多有n+1項)aixi是多項式的第i項（0in），其中ai為系數(shù)，x為變量，i為指數(shù)。它有n+1

35、個系數(shù)，因此，在計算機里，它可用一個線性表P來表示：P=（a0,a1,a2,，an）假設Qn(x)是一元m次多項式，同樣可用線性表Q來示：Q=（b0,b1,b2,，bm）采用鏈式存儲結構表示多項式時，多項式中每一個非零系數(shù)的項構成鏈表中的一個結點，而對于系數(shù)為零的項則不需表示。則采用鏈表表示多項式時，每個結點的數(shù)據(jù)域有兩項：ak表示系數(shù)，em表示指數(shù)。（注意：表示多項式的鏈表應該是有序鏈表）struct poly int exp; /*指數(shù)為正整數(shù)*/ double coef; /*系數(shù)為雙精度型*/ struct poly *next; /*指針域*/將兩個多項式相加為 C17(x)=8+1

36、1x+14x7+5x17，其運算規(guī)則如下：假設指針qa和qb分別指向多項式A17(x)和多項式B8(x)中當前進行比較的某個結點，則比較兩個結點的數(shù)據(jù)域的指數(shù)項，有三種情況：（1）指針qa所指結點的指數(shù)值指針qb所指結點的指數(shù)值時，則保留qa指針所指向的結點，qa指針后移；（2）指針qa所指結點的指數(shù)值指針qb所指結點的指數(shù)值時，則將qb指針所指向的結點插入到qa所指結點前，qb指針后移；（3）指針qa所指結點的指數(shù)值指針qb所指結點的指數(shù)值時，將兩個結點中的系數(shù)相加,若和不為零，則修改qa所指結點的系數(shù)值，同時釋放qb所指結點；反之，從多項式A17(x)的鏈表中刪除相應結點，并釋放指針qa和

37、qb所指結點。本章小結本章主要介紹了如下一些基本概念：線性表：一個線性表是n0個數(shù)據(jù)元素a0，a1，a2，an-1的有限序列。線性表的順序存儲結構：在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結構。線性表的鏈式存儲結構：線性表的鏈式存儲結構就是用一組任意的存儲單元結點（可以是不連續(xù)的）存儲線性表的數(shù)據(jù)元素。表中每一個數(shù)據(jù)元素，都由存放數(shù)據(jù)元素值的數(shù)據(jù)域和存放直接前驅或直接后繼結點的地址（指針）的指針域組成。循環(huán)鏈表：循環(huán)鏈表(Circular Linked List)是將單鏈表的表中最后一個結點指針指向鏈表的表頭結點，整個鏈表形成一個環(huán)，從表中任一結點出

38、發(fā)都可找到表中其他的結點。雙向鏈表：雙向鏈表中，在每一個結點除了數(shù)據(jù)域外，還包含兩個指針域，一個指針（next）指向該結點的后繼結點，另一個指針（prior）指向它的前驅結點。除上述基本概念以外，學生還應該了解：線性表的基本操作（初始化、插入、刪除、存取、復制、合并）、順序存儲結構的表示、線性表的鏈式存儲結構的表示、一元多項式Pn(x)，掌握順序存儲結構（初始化、插入操作、刪除操作）、單鏈表（單鏈表的初始化、單鏈表的插入、單鏈表的刪除）。3、棧和隊列(6學時)知識點：棧及其各種實現(xiàn)方法、隊列及其各種實現(xiàn)方法、映射及其各種實現(xiàn)方法 重點：棧和隊列的概念及實現(xiàn)難點：棧的隊列的綜合應用 本章學習導讀

39、從數(shù)據(jù)結構上看，棧和隊列也是線性表，不過是兩種特殊的線性表。棧只允許在表的一端進行插入或刪除操作，而隊列只允許在表的一端進行插入操作、而在另一端進行刪除操作。因而，棧和隊列也可以被稱作為操作受限的線性表。通過本章的學習，讀者應能掌握棧和隊列的邏輯結構和存儲結構，以及棧和隊列的基本運算以及實現(xiàn)算法。 3.1 棧 在各種程序設計語言中都有子程序（或稱函數(shù)、過程）調用功能。而子程序也可以調用其它的子程序，甚至可以直接或間接地調用自身，這種調用關系就是遞歸。下面以求階乘的遞歸方法為例，來分析計算機系統(tǒng)是如何處理這種遞歸調用關系的。求n！的遞歸方法的思路是：相應的C語言函數(shù)是：3.1.1 棧的定義及其運

40、算（1）棧的定義棧（stack）是一種只允許在一端（通常在表尾）進行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂（top），另一端稱為棧底(bottom)。棧的插入操作通常稱為入?；蜻M棧(push)，而棧的刪除操作則稱為出?；蛲?棧(pop)。當棧中無數(shù)據(jù)元素時，稱為空棧。棧也被稱為“后進先出”的線性表。（2）棧的基本運算（3）棧的表示和實現(xiàn)1）棧的順序存儲結構（順序棧的數(shù)組表示）用C語言定義的順序存儲結構的棧如下：# define MAXNUM <最大元素數(shù)>typedef struct Elemtype stackMAXNUM;int

41、top; sqstack;鑒于C語言中數(shù)組的下標約定是從0開始的，因而使用C語言的一維數(shù)組作為棧時，應設棧頂指針top=-1時為空棧。2）順序棧的基本運算算法（1）初始化棧（2）入棧操作（3）出棧操作（4）取棧頂元素操作取棧頂元素與出棧不同之處在于出棧操作改變棧頂指針top的位置，而取棧頂元素操作不改變棧的棧頂指針。（5）判?？詹僮鳎?）置空操作（3）多棧共享鄰接空間1）雙向棧在一維數(shù)組中的實現(xiàn)2）共享棧的基本操作（1）初始化操作（2）入棧操作（3）出棧操作（4） 棧的鏈式存儲結構1）入棧操作（2）出棧操作多個鏈棧的操作在程序中同時使用兩個以上的棧時，使用順序棧共用鄰接空間很不方便，但若用多個

42、單鏈棧時，操作極為方便，這就涉及多個鏈棧的操作。我們可將多個單鏈棧的棧頂指針放在一個一維數(shù)組slStacktype *topM;之中，讓top0，top1，topi，topM-1指向M個不同的鏈棧，操作時只需確定棧號i，然后以topi為棧頂指針進行棧操作，就可實現(xiàn)各種操作。 （1）入棧操作【算法3.12 多個鏈棧的入棧操作】int pushDupLs(slStacktype *topM,int i,Elemtype x)/*將元素x壓入鏈棧topi中*/slStacktype *p;if(p=(slStacktype *)malloc(sizeof(slStacktype)= =NULL) r

43、eturn FALSE; /*申請一個結點*/p->data=x; p->next=topi; topi=p; return TRUE;（2）出棧操作【算法3.13 多個鏈棧的出棧操作】Elemtype popDupLs(slStacktype *topM,int i)/*從鏈棧topi中刪除棧頂元素*/slStacktype *p;Elemtype x;if (topi= =NULL) return NULL; /*空棧*/p=topi; topi=topi->next; x=p->data;free(p);return x;在上面的兩個算法中，當指定棧號i(0iM-

44、1)時，則只對第i個鏈棧操作，不會影響其它鏈棧。圖3-7 表達式的計算過程(c)讀出),作運算T1=4/2=2top6 2 5 top-#(+(d)作運算T2=6-2=4OPRDtop54OPTRtop+#(h)重新考慮#,作運算T4=5+18=23OPRDtop23OPTRtop#(g)讀#,作運算T3=6*3=18OPTRtop+#OPRDtop185(a)初始狀態(tài)OPTROPRDtoptop#(b)讀出5,+,(,6,-,4,/,2OPTRtop/-(+#OPRDtop5246(e)退(OPTROPRDtop54top#+(f)讀出*,3OPRDtop3&#

45、160;54OPTRtop#+*OPRDOPTR思考：按1234順序入戰(zhàn)可能的出展順序：4321 3421 3241 2431 2341 2314 2143 2134 1234 1432 1324 1342 1243 3.2 算術表達式求值表達式求值是程序設計語言編譯中的一個最基本問題。它的實現(xiàn)方法是棧的一個典型的應用實例。（P）圖3-7給出了表達式5+(6-4/2)*3的計算過程，最后的結果為T4，置于OPRD的棧頂。3.3 棧與遞歸調用：不用遞歸則要用棧。34隊列在日常生活中隊列很常見，如，我們經(jīng)常排隊購物或購票，排隊是體現(xiàn)了“先來先服務”（即“先進先出”）的原則。3.4.1 隊列的定義及

46、其運算（1）隊列的定義（2）隊列的基本運算（1）initQueue(q) 初始化：初始化一個新的隊列。（2）empty(q) 隊列非空判斷：若隊列q不空，則返回TRUE；否則，返回FALSE。（3）append(q,x) 入隊列：在隊列q的尾部插入元素x，使元素x成為新的隊尾。若隊列滿，則返回FALSE；否則，返回TRUE。（4）delete(s) 出隊列：若隊列q不空，則返回隊頭元素，并從隊頭刪除該元素，隊頭指針指向原隊頭的后繼元素；否則，返回空元素NULL。（5）getHead(q) 取隊頭元素：若隊列q不空，則返回隊頭元素；否則返回空元素NULL。（6）length(q) 求隊列長度：返

47、回隊列的長度。隊列是一種特殊的線性表，因此隊列可采用順序存儲結構存儲，也可以使用鏈式存儲結構存儲。3 4。2的鏈式存儲結構（1）鏈隊列的表示（2）鏈隊列的主要運算算法（1）初始化隊列（2）入隊列操作（3）出隊列操作3.4.3 隊列的順序存儲結構（1）順序隊列的數(shù)組表示C語言中，數(shù)組的下標是從0開始的，因此為了算法設計的方便，在此我們約定：初始化隊列時，空隊列時令front=rear=-1，當插入新的數(shù)據(jù)元素時，尾指示器rear加1，而當隊頭元素出隊列時，隊頭指示器front加1。另外還約定，在非空隊列中，頭指示器front總是指向隊列中實際隊頭元素的前面一個位置（避免當只有一個元素時被認為隊空

48、），而尾指示器rear總是指向隊尾元素。（2）順序隊列的基本運算算法（1）初始化隊列（2）入隊列操作（3）出隊列操作（4）取隊頭元素操作（5）判隊列非空操作（6）求隊列長度操作（3）循環(huán)隊列在順序隊列中，當隊尾指針已經(jīng)指向了隊列的最后一個位置時，此時若有元素入列，就會發(fā)生“溢出”。在圖3-9（c）中隊列空間已滿，若再有元素入列，則為溢出；在圖3-9（d）中，雖然隊尾指針已經(jīng)指向最后一個位置，但事實上隊列中還有3個空位置。也就是說，隊列的存儲空間并沒有滿，但隊列卻發(fā)生了溢出，我們稱這種現(xiàn)象為假溢出。解決這個問題有兩種可行的方法：（1）采用平移元素的方法，當發(fā)生假溢出時，就把整個隊列的元素平移到存

49、儲區(qū)的首部，然后再插入新元素。這種方法需移動大量的元素，因而效率是很低的。（2）將順序隊列的存儲區(qū)假想為一個環(huán)狀的空間，如圖3-10所示。我們可假想q->queue0接在q->queueMAXNUM-1的后面。當發(fā)生假溢出時，將新元素插入到第一個位置上，這樣做，雖然物理上隊尾在隊首之前，但邏輯上隊首仍然在前。入列和出列仍按“先進先出”的原則進行，這就是循環(huán)隊列。很顯然，方法二中不需要移動元素，操作效率高，空間的利用率也很高。在循環(huán)隊列中，每插入一個新元素時，就把隊尾指針沿順時針方向移動一個位置。即：q->rear=q->rear+1;if(q->rear= =MA

50、XNUM) q->rear=0;在循環(huán)隊列中，每刪除一個元素時，就把隊頭指針沿順時針方向移動一個位置。即：q->front=q->front+1;if(q->front= =MAXNUM) q->front=0;，為循環(huán)隊列的三種狀態(tài)， 為了區(qū)分循環(huán)隊列是空還是滿，我們可以設定一個標志位s：s= 0時為空隊列，s=1時隊列非空。用C語言定義循環(huán)隊列結構如下：typedef structElemtype queueMAXNUM;int front; /*隊頭指示器*/int rear; /*隊尾指示器*/int s; /*隊列標志位*/qqueue;下面給出循環(huán)隊列

51、的初始化、入隊列及出隊列的算法。（1）初始化隊列【算法3.20 循環(huán)隊列的初始化】int initQueue(qqueue *q)/*創(chuàng)建一個空隊列由指針q指出*/ if (q=(qqueue*)malloc(sizeof(qqueue)= =NULL) return FALSE; q->front= MAXNUM; q->rear=MAXNUM;q->s=0;return TRUE;（2）入隊列操作【算法3.21 循環(huán)隊列的入隊列操作】int append(qqueue *q,Elemtype x)/*將元素x插入到隊列q中，作為q的新隊尾*/if ( q->s= =

52、1)&&(q->front= =q->rear) return FALSE; /*隊列滿*/ q->rear+; if (q->rear= =MAXNUM) q->rear=0; q->queueq->rear=x; q->s=1; /*置隊列非空*/return TRUE;（3）出隊列操作【算法3.22 循環(huán)隊列的出隊列操作】Elemtype delete(qqueue *q)/*若隊列q不為空，則返回隊頭元素*/Elemtype x;if (q->s= =0) retrun NULL; /*隊列為空*/q->fro

53、nt+;if (q->front= =MAXNUM) q->front=0;x=q->queueq->front;if (q->front = =q->rear) q->s=0; /*置隊列空*/ return x; 3 5離散事件模擬補充：其它隊列除了棧和隊列之外，還有一種限定性數(shù)據(jù)結構，它們是雙端隊列（double-ended queue）。雙端隊列是限定插入和刪除操作在線性表的兩端進行，我們可以將它看成是棧底連在一起的兩個棧，但它與兩個棧共享存儲空間是不同的。共享存儲空間中的兩個棧的棧頂指針是向兩端擴展的，因而每個棧只需一個指針；而雙端隊列允許兩

54、端進行插入和刪除元素，因而每個端點必須設立兩個指針，如圖3-13所示。在實際使用中，還有輸出受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許插入）；輸入受限的雙端隊列（即一個端點允許插入和刪除，另一個端點只允許刪除）。如果限定雙端隊列從某個端點插入的元素只能從該端點刪除，則雙端隊列就蛻變?yōu)閮蓚€棧底相鄰接的棧了。盡管雙端隊列看起來比棧和隊列更靈活，但實際中并不比棧和隊列實用，故在此不再深入討論。本章小結 本章主要介紹了如下一些基本概念：棧：是一種只允許在一端進行插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂（top），另一端稱為棧底(bottom

55、)。棧頂元素總是最后入棧的，因而是最先出棧；棧底元素總是最先入棧的，因而也是最后出棧。因此，棧也被稱為“后進先出”的線性表。棧的順序存儲結構：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)母鱾€數(shù)據(jù)元素，稱為棧的順序存儲結構。雙向棧：使兩個棧共享一維數(shù)組stackMAXNUM，利用棧的“棧底位置不變，棧頂位置動態(tài)變化”的特性，將兩個棧底分別設為-1和MAXNUM，而它們的棧頂都往中間方向延伸的棧稱為雙向棧。棧的鏈式存儲結構：棧的鏈式存儲結構就是用一組任意的存儲單元（可以是不連續(xù)的）存儲棧中的數(shù)據(jù)元素，這種結構的棧簡稱為鏈棧。在一個鏈棧中，棧底就是鏈表的最后一個結點，而棧頂總是鏈表的第一個結點。隊列：隊列（queue）是一種只允許在一端進行插入，而在另一端進行刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入的一端稱為隊尾（rear），只允許進行刪除的一端稱為隊頭(front)。隊頭元素總是最先進隊列的，也總是最先出隊列；隊尾元素總是最后進隊列，因而也是最后出隊列。因此，隊列也被稱為“先進先出”表