數(shù)據(jù)結(jié)構完整版教學課件全書電子講義(最新)

1、數(shù)據(jù)結(jié)構目 錄 第一章 緒論第二章 線性表第三章 棧和隊列第四章 字符串、數(shù)組和廣義表第五章 樹第六章 圖第七章 查找第八章 排序第一章 緒論1.1 數(shù)據(jù)結(jié)構與算法1.2 算法的描述和分析 1.1 數(shù)據(jù)結(jié)構與算法1.1.1、基本概念數(shù)據(jù)：對現(xiàn)實世界的事物采用計算機能識別、存儲和處理的形式所進行的描述。簡言之，數(shù)據(jù)是計算機程序能加工和處理的對象或數(shù)據(jù)就是計算機化的信息。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，又稱為結(jié)點。在計算機程序中通常作為一個整體進行考慮和處理。有時一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。如一本書的書目信息為一數(shù)據(jù)元素，而書目信息中的每一項（如書名、作者名等）為一個數(shù)據(jù)項。數(shù)據(jù)項是數(shù)據(jù)的不可分割

2、的最小單元。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合是數(shù)據(jù)的一個子集?；靖拍?續(xù))數(shù)據(jù)結(jié)構：相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構是指數(shù)據(jù)對象及其相互關系和構造方法。一個數(shù)據(jù)結(jié)構DS可以形式地用一個二元組表示為：DS=（D，R）其中：D是數(shù)據(jù)結(jié)構中的數(shù)據(jù)（稱為結(jié)點）的非空集，R是定義在D上的關系的非空有限集合。結(jié)構是指結(jié)點之間的關系，數(shù)據(jù)結(jié)構就是結(jié)點的有限集合和關系的有限集合。 數(shù)據(jù)結(jié)構中，結(jié)點及結(jié)點間的相互關系是數(shù)據(jù)的邏輯結(jié)構，數(shù)據(jù)結(jié)構在計算機中的存儲內(nèi)容，一般包括結(jié)點的值和結(jié)點間的關系，數(shù)據(jù)結(jié)構的存儲形式是數(shù)據(jù)的存儲結(jié)構（或物理結(jié)構） 基本概念(續(xù)) 數(shù)據(jù)結(jié)構： 數(shù)據(jù)結(jié)構按邏

3、輯關系的不同分為線性結(jié)構和非 線性結(jié)構兩大類，其中非線性結(jié)構又分為樹形結(jié)構和圖結(jié)構，而樹形結(jié)構又可分為樹結(jié)構和二叉樹結(jié)構。 在計算機中表示信息的最小單位是二進制數(shù)的一位叫做位（bit），可以用一個或若干位組合起來形成的一個位串表示一個數(shù)據(jù)元素或結(jié)點。元素或結(jié)點可看成是數(shù)據(jù)元素在計算機中的映象有【順序映象、非順序映象】，由此存儲結(jié)構可分為【順序存儲結(jié)構、鏈式存儲結(jié)構】。順序映象的特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。非順序映象的特點是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。 數(shù)據(jù)類型：指某種程序設計語言所允許使用的 變量種類。1.1.2算法的概念和特性 算

4、法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。在計算機科學中算法則是描述計算機解決給定問題的操作過程。 算法的特性是有窮性、確定性、可行性、輸入和輸出。1、有窮性：求解問題的步驟是有限的，且每一步都可在有限時間內(nèi)完成。2、確定性：在任何情況下，對同一問題的求解結(jié)果必須是唯一的。 3、可行性：算法的實現(xiàn)必須在法律上，經(jīng)濟上，技術上都可行。4、輸入：沒有輸入，對問題的求解方法僅能適用于這一個特定問題。5、輸出：沒有輸出，看不到結(jié)果，對問題的求解將失去任何意義。1.2 算法的描述和分析1.2.1算法的描述 算法需要用一種語言來描述，同時，算法可有各種描述方法

5、以滿足不同的需求。例如，一個需在計算機上運行的程序（程序也是算法）必須嚴格按照語法規(guī)定用機器語言或匯編語言或高級語言編寫，而一個為了人的閱讀和交流的算法可以用偽碼語言或框圖等其它形式來描述。偽碼語言是一種包括高級程序語言訴三種基本控制結(jié)構（順序、判定和重復）和自然語言成分的“面向讀者”的語言。 本書采用C語言描述數(shù)據(jù)結(jié)構及相應的算法。1.2.2 算法的分析 一、 從時間方面分析 算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。一個算法是由控制結(jié)構（順序、分支和重復三種）和原操作（指固有數(shù)據(jù)類型的操作）構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算

6、法，通常的做法是，從算法中選取一種對于所研究的的問題（或算法類型）來說是基本操作的原操作，以該基本操作重復的次數(shù)作為算法的時間復雜度。算法的時間復雜度通常記作 T（n）=O(f(n) ，其中，n為問題的規(guī)模，f(n)表示算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)。上式表示隨問題規(guī)模n的增大算法執(zhí)行時的增長率與f(n)的增長率相同。從時間方面分析f(n)和T(n)是同數(shù)量級的函數(shù)，大寫字母O表示f(n)與T(n)只相差一個常數(shù)倍。算法的時間復雜發(fā)表要用數(shù)量級的形式表示后，一般可簡化為分析循環(huán)體內(nèi)基本操作的執(zhí)行次數(shù)即可。例1.1：（1）x+; (2) for(i=1;in;i+)x+; (

7、3) for(i=1;in;i+)x=x+1;含基本操作“x增1”的語句x+的頻度分別為1，n, n2 則這三上程序段的時間復雜度分別為O（1），O（n）和O（n2）分別稱為常量階，線性階和平方階。算法還可呈現(xiàn)的時間復雜度有：對數(shù)階O（log2n），指數(shù)階O（2n）等。算法的分析2 二、從空間方面分析類似于算法的時間復雜度，以空間復雜度作為算法所需存儲空間的量度，記為S(n)=O(f(n)其中，n為問題的規(guī)模（或大小）。算法在運行過程序中需輔助存儲空間的大小。在這里我們不多作討論。舉例 (1)P4.二.下列程序段的時間復雜度是（）。for (i=1;i=n;i+) Ai=0;7.下列程序段的時

8、間復雜度是（）。 s=0;for (i=1;i=n;i+) for (j=1;j=n;j+) s=s+bi j;sum=s;舉例 (2)P5.三.1、分析下列程序段的時間復雜度。. i=1;While(i=n) i=i*2; .舉例 (3)P5、三、5、設n為正數(shù)。試確定下列各程序段中前面加記號的語句的頻度：i=1;k=0;While(i=n-1)k+=10*i;i+; k=0;for(i=1;i=n;i+)for(j=1;j0時該線性表可記為：（A0,A1,Ai,An-1）其中，A0稱為起點，An-1稱為終點，每個元素的序號代表它在該線性表中的邏輯位置減1（與數(shù)組下標對應），除了起點（A0）

9、和終點(An-1)外，每個數(shù)據(jù)元素都有且只有一個直接前趨和一個直接后繼。Ai+1是Ai的直接前驅(qū)，Ai+1是Ai的直接后繼。線性表中的數(shù)據(jù)元素可以是各式各樣的，但同一線性表中的元素必定有相同的特性，即屬同數(shù)據(jù)對象，相鄰數(shù)據(jù)元素辶間存在著有序關系。線性表是一個相當靈活的數(shù)據(jù)結(jié)構，其表長可根據(jù)不同的操作增長或縮短。對線性表進行的基本操作有：存取、插入、刪除、合并、分解、查找、排序、求線性表的長度等。 2.2 線性表的順序存儲結(jié)構2.2.1 順序分配線性表的順序存儲結(jié)構是用一組地址連續(xù)的存儲單元依次存儲該線性表中的各個元素。假設線性表的每個數(shù)據(jù)元素占用L個存儲單元，并以所占的第一個單元的存儲地址為數(shù)

10、據(jù)元素的存儲位置，則第i+1個數(shù)據(jù)元素的存儲位置為： loc(Ai)=Loc(A0)+i*L.因此，在內(nèi)存中可以通過地址計算直接存取線性表中的任一元素，所以，線性表的順序存儲結(jié)構可以隨機存取。這種結(jié)構的特點是邏輯上相鄰的元素物理上也相鄰（如圖2-1所示）。順序表可用語言的一維數(shù)組實現(xiàn)，數(shù)組的類型隨數(shù)據(jù)元素的屬性而定。2.2.2 線性表的操作 線性表結(jié)構簡單、易于實現(xiàn)，但插入或刪除一個元素時需對其后繼的全部元素逐個進行移動（平均需移動表中的一半元素）操作不方便，需花費較多時間，特別是當插入元素而需動態(tài)擴大連續(xù)存儲時，線性表后面的存儲區(qū)可能已被占用從而無法擴大。所以，這種結(jié)構僅適用于數(shù)據(jù)元素個數(shù)不

11、經(jīng)常變動或只需在順序存取設備上做成批處理的場合。下面我們分情況討論線性表的插入和刪除操作。 (一)線性表插入操作(1) 1、在數(shù)組中下標為i的元 素前插入一個新元素。例2.1 某語言程序中，整型數(shù)組的個元數(shù)組成一個線性表。為了在i位置前插入一個新元素b，可用如下函數(shù)inst1來實現(xiàn)，當插入成功時返回1，否則返回0，所以該函數(shù)的返回值類型是整型。插入前后的線性表的示意圖如右： 舉例（續(xù)）分析：初始條件V,i,b執(zhí)行條件：0i98執(zhí)行結(jié)果：1 成功0 不成功N-S流程圖如右： 圖舉例（續(xù)） 用函數(shù)實現(xiàn)算法如下： int ins1( int V , int i, int b) int j；if(i9

12、8) printf(“The value of i is out of rangen”)； return 0; /*插入失敗*/ for (j=99；ji；j-) vj=vj-1;/*后移*/ vi=b； /*插入*/return 1； /*插入成功 */線性表的插入操作（2）2、在有序表中插入一個新元素 例2.2 設有一個有序線性表，用數(shù)組結(jié)構實現(xiàn)，最大元素個數(shù)為n。設當前元素個數(shù)是m。要求在該有序表中插入一個值為x的元素。當x=63時，插入前后的有序表的示意圖如右： 舉例（續(xù)）分析：初始條件：a,n,m,x插入條件：m=n) printf(“插入失敗”);return 0; /*插入失敗*

13、/for(i=m-1; i=0& aix ;i-) ai+1=ai; /*后移*/ai+1=x; m+; /*插入*/return 1; /*插入成功 */（二）線性表的刪除(1)1刪除下標為i的 數(shù)據(jù)元素例2.3 為在V0到V99中刪除一個元素Vi,引用del1函數(shù)。刪除前后的線性表的示意圖如右 舉例（續(xù)）分析：初始條件： 數(shù)組V，刪除下標i刪除條件：0i99執(zhí)行結(jié)果：1成功,0不成功N-S流程圖如右: 舉例（續(xù)）Del1函數(shù)定義如下：int del1 (int v ,int i )int j;if (i99) printf(“the value of I is out of rangen”

14、);return 0; /*刪除失敗*/for (j=i; j99; j+) Vj=Vj+1; /*從vI+1到v99逐個前移*/ V99=0; /*數(shù)組最后一個元素清0或某種結(jié)束標記*/return 1; /*刪除成功 */線性表的刪除操作(2)2在有序順序表中刪除一個數(shù)據(jù)元素例2.4 在有序表中刪除一個值為x的數(shù)據(jù)元素。當x的值為78時刪去前后的線性表的示意圖如右：舉例（續(xù)）分析：初始條件：數(shù)組a, 數(shù)組元素個數(shù)n,刪除元素值 x查找a中是否有x值的元素：有x,則刪除成功，返回1；無x,則刪除不成功，返回0。NS流程圖如右：舉例（續(xù)）對應算法實現(xiàn)函數(shù)如下：int del2(int a,in

15、t n,int x)int i,j;for(j=0;jn;j+) if(aj= =x)i=j;break;if (j= =n) printf(“找不到x，刪除不成功”);return 0; /*找不到x，刪除不成功*/for(;idata=ai； -link-data=ai+1。 2.3.2 線性鏈表的運算設p鏈表中某一結(jié)點的指針，可以說明如下：NODE *p；申請一個結(jié)點可用C語言的標準存儲分配庫函數(shù)malloc。調(diào)用如下：p = (NODE * ) malloc ( sizeof (NODE);當用完后釋放結(jié)點占用空間時調(diào)用函數(shù)free free(p); （一）線性鏈表的建立例.5 建立一

16、個如圖所示的鏈表。例2.5 函數(shù)定義如下NODE * create_linklist(NODE * head,int x,int y,int z) NODE * p, *q;p=(NODE *)malloc(sizeof(NODE);head=p;p-data=x;q=(NODE *)malloc(sizeof(NODE);p-link=q;p=q;p-data=y;q=(NODE *)malloc(sizeof(NODE);p-link=q;p=q;p-data=z;p-link=NULL;return (head);（二）線性鏈表的插入操作設鏈表結(jié)點類型的定義為：typedef struc

17、t node int data; struct node *link;NODE;在鏈接存儲的線性表中插入一個鍵值為x的新結(jié)點，分以下四種不同情況：1、在某指針P所指結(jié)點之后插入；2、插入首結(jié)點之前，使新結(jié)點為新的首結(jié)點；3、接在線性表的末尾；4、在有序鏈表中插入，使新的線性表依舊有序。 分情況討論（1）1、在線性鏈表中某指針p所指結(jié)點之后插入值為x的結(jié)點算法的NS流程圖 插入結(jié)點的函數(shù)函數(shù)定義如下：void lq_insl(p,x)NODE *p; /*新結(jié)點在P所指結(jié)點之后*/int x; /*新結(jié)點的鍵值*/ NODE *u;u=(NODE *)malloc(sizeof(NODE);u-

18、data=x;u-link=p-link;p-link=u; 分情況討論（2）2、首結(jié)點之前插入鍵值為x的新結(jié)點 算法的NS流程圖 算法的NS流程圖 首結(jié)點之前插新結(jié)點函數(shù)定義void lq_ins2(hpt,x)NODE *hpt; /*鏈表頭指針*/int x; /*新結(jié)點的鍵盤值*/NODE *u;u=(NODE *)malloc(sizeof(NODE);u-data=x;u-link=hpt;hpt=u; 分情況討論（3）3、在鏈式存儲的線性表的末尾接上一個鍵值為x的新結(jié)點算法的NS流程圖 線性表末尾接上新結(jié)點函數(shù)定義 void lq_ins3(hpt,x)NODE *hpt; /*

19、鏈表頭指針*/int x; /*新結(jié)點的鍵盤值*/ NODE*u,*p;u=(NODE)*malloc(sizeof(NODE);u-data=x;u-link=null;if (hpt=null) /*如鏈表為空鏈表*/hpt=u;return;/*x以鏈表首結(jié)點開始順序走向末尾結(jié)點*/for( p=hpt; p-link!=null;p= p-link);p-link=u;分情況討論（4）4、在有序鏈式存儲線性表中插入一鍵值為X的新結(jié)點(假設x=8)算法的NS流程圖 有序鏈式線性表中插入新結(jié)點函數(shù)voikd lq_ins4 (hpt,x) /*設鏈表從小到大有序*/NODE *hpt; /

20、*鏈表頭指針*/int x; /*新結(jié)點的鍵值*/NODE *u,*q,*p;u=(NODE *)malloc(sizeof(NODE);u-data=x; /*從鏈表首結(jié)點開始順序?qū)ふ?/for(p=htp;p&p-datalink);if(p= =hpt) hpt=u;else q-link=u;u-link=p （三）線性鏈表的刪除操作完成刪除算法可有以下幾個步驟組成： 1、如鏈表為空鏈表，則不執(zhí)行刪除操作 2、若鏈表的首結(jié)點的值為指定值，更改鏈表的頭指針為指向首結(jié)點的后繼結(jié)點； 3、在鏈表中找到指定值的結(jié)點； 4、將找到的結(jié)點刪除刪除操作示意圖算法的NS流程圖 鏈表中刪除指定值的結(jié)點的

21、函數(shù)定義 int lq_delete(hpt,a)NODE *hpt; /*鏈表頭指針的指針*/int a; /*要刪除的結(jié)點鍵值*/NODE p,q; if(q=hpt)=NULL) return 1; /*鏈表已為空鏈表*/if(q-data=a) /*要刪除鏈表的首結(jié)點*/ hpt=q-link; /*更改鏈表頭指針*/free(q); /*釋放被刪除結(jié)點的空間*/return 0; /*刪除成功*/for( ; q-data!=a&q-link!=NULL;p=q,q=q-link); /*尋找*/if(q-data=a) /*找到*/ p-link=q-link; /被刪除的結(jié)點從鏈

22、表脫鉤*/free(q); /*釋放被刪除結(jié)點的空間*/return 0; /*刪除成功*/return 1; /*沒有指定值勤的結(jié)點，未執(zhí)行刪除操作*/2.3.3 循環(huán)鏈表1.單向循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈式存儲結(jié)構，將單鏈表的形式稍加改，讓表中最后一個結(jié)點的指針域指向單鏈表的首結(jié)點，這樣就形成了一個環(huán)。如圖2-26所示。這種結(jié)構從表中任一結(jié)點出發(fā)均可找到其它結(jié)點。 單向循環(huán)鏈表的基本操作類似于普通鏈表，差別在于算法中循環(huán)條件不在是p或p-link是否為空，而是它們是否等于頭指針。 2.雙向鏈表在單鏈表中，從任何一個結(jié)點能通過指針域找到它的一繼結(jié)點，但要找它的前趨結(jié)點，則需從表頭出發(fā)

23、順鏈查找。雙向鏈表克服了這個缺點。雙向鏈表的每一個結(jié)點除數(shù)據(jù)域外，還包括兩個指針域，一個指向該結(jié)點的后繼結(jié)點，另一個指向它的前趨結(jié)點，結(jié)點結(jié)構如圖2-27所示。雙向鏈表也可以是循環(huán)鏈表，其結(jié)構如圖2-28所示示意圖雙向鏈表的結(jié)點類型可描述如下 struct nodeint data;struct node *ulink,*rlink;typedef struct node DNODE;在循環(huán)雙向鏈表中，若P先指向表中結(jié)點的指針，則有：(p-rlink)-llink=(p-link)-rlink=p1、插入在雙向鏈表中的p結(jié)點后插入一個q結(jié)點。假設q結(jié)點已生成，如圖2-29所示 主要操作步驟如下

24、：q-rlink=p-rlink;q-llink=p;p-rlink=q;(q-rlink)-llink=q; 2、刪除在雙向鏈表中刪除p結(jié)點主要操作步驟如下：（p-llink）-rlink=p-link;(p-rlink)-llink=p-llink;free(p); 例 2-7(1)head是一個鏈表的頭指針，該鏈表結(jié)點的域由小到大排列。函數(shù)insert(head,data)將一個值為data新結(jié)點插入到鏈表中，且保證插入后的鏈表仍是有序的。請在每組中選擇正確答案填空。 #include#include #include typedef struct nodeint data;struct

25、 node *next;NODE;例 2-7(2)NODE *insert(NODE *head,int data) NODE *new ,*front, *current; Current=head;While(current!=NULL& (1) ) front=current; current=current-next;new= (2) ;new-data=data;new-next=current;if ( (3) ) head=new;else front-next=new;return head;作業(yè)P25 四.1,2第三章 棧和隊列 3.1 堆棧 3.2 隊列3.1 堆棧3.1.

26、1 堆棧的定義和基本操作棧（stack）是一種特殊的線性表，這種表只能在其一端（稱為棧頂top）進行插入和刪除操作,如圖2-4-1所示。棧的概念來自存貨的堆棧，存貨時一件一件往上堆，每次取貨時都有只能從上面取。棧的存取特征是后進先出（Last In First Out,縮寫為LIFO）。棧頂將隨著棧中元素的增減而浮動，通過棧頂指針指明當前棧頂元素位置。棧的固定端稱為棧底（bottom），棧底指針并不移動。棧的基本操作包括：創(chuàng)建一個棧進棧 棧頂 出棧進棧（push），出棧（pop）讀取棧頂元素，判?？眨瑮Ｇ蹇眨ǔ跏蓟?，求當前棧中元素的個數(shù)，撤消一個棧等 棧底3.1.2 順序存儲?？捎庙樞虼鎯€

27、性表來表示棧，為了指明當前執(zhí)行插入和刪除運算的棧頂位置，需要一個游標變量top（習慣稱為棧頂指針，注意與指針變量的區(qū)別），top指出棧頂表元素在數(shù)組中的下標。當棧為空時，top =0;棧滿時，top=MAXN(數(shù)組元素個數(shù)),如圖2-4-1所示。順序存儲棧示意圖 MAXN-1 MAXN-1 top . . . . . . 1 1top-0 0 ?？?棧滿 1、順序存儲棧的進棧操作(1) 順序存儲棧的進棧操作(2)函數(shù)如下：int push(NODE stack,int maxn,int top,NODE x)/*設棧點的數(shù)據(jù)類型為NODE，?？臻g最多能存maxn個結(jié)點*/if (top=max

28、n) return 1; /*棧滿，進棧失敗返回*/stack top=x; /*完成進棧運算*/+top;return 0; /*進棧成功，返回0*/2、順序存儲棧出棧操作(1)順序存儲棧出棧操作(2)函數(shù)如下：int pop(NODE stack,int top,NODE cp)if(top=0) return 1; /*?？眨鰲Ｊ》祷?/-top; cp=stacktop; /*完成出棧運算*/return 0; /*出棧成功，返回*/3.1.3 鏈式存儲棧棧也可以用鏈表實現(xiàn)，用鏈表實現(xiàn)的棧稱為鏈式棧。鏈表的第一個元素是棧頂結(jié)點，鏈表的末尾元素是棧底結(jié)點，鏈表的首表指針是棧頂指針to

29、p ,top為null的空鏈表是空棧。設棧結(jié)點類型為：typedet struct node NODE data; /*棧元值，某種NODE類型*/struct node *link;LNODE;(一) 鏈式存儲棧的進棧函數(shù)示意圖 top top=p p-link=top p4 X 5 2 null函數(shù)定義函數(shù)如下：void L_push(NODE x,LNODE *top) /*設棧結(jié)點的數(shù)據(jù)類型為NODE*/LNODE *p=(LNODE *)malloc(sizeof(LNODE);p-data=x;p-link=top;top=p;（二 ）鏈接存儲棧的出棧函數(shù)示意圖Top p4 5 2

30、 Null 函數(shù)定義 int L_pop(NODE *cp,LNODE *top) /*設棧結(jié)點的數(shù)據(jù)類型為NODE*/LNODE *p=top;if(top=NULL) return 1;/*空棧*/*cp=p-data;top=p-link;free(p);return 0;/*出棧成功*/3.2 隊 列 一、隊列定義、隊列是只允許在一端進行插入，另一端正進行刪除的線性表，如圖3-7所示。 出隊 q0 q1 qi qi+1 qn-1 進隊 隊首 隊尾 圖3-7 隊列示意圖 隊列中允許刪除運算的一端稱隊首，允許插入運算的一端稱為隊尾。習慣稱在隊列中插入結(jié)點操作為進隊，隊列中刪除結(jié)點的操作為出

31、隊。若有隊Q=(q0,q1,qn-1),則q0為隊首結(jié)點，qn-1為隊尾結(jié)點。因最先進入隊列的結(jié)點將最先出隊，所以隊列具有先進先出（First In First Out簡稱FIFO）的特性。隊列的基本操作包括：創(chuàng)建一個隊列，入列，出隊，讀取隊首元素，判隊空，請隊列空，求當前隊列中的元素個數(shù)，撤消一個隊列等。3.2.1 順序存儲隊列可以用順序存儲線性表來表示隊列，為了指明當前執(zhí)行出隊運算的隊首位置，需一個游標變量front（習慣上稱為頭指針），為了指明當前執(zhí)行進隊運算的隊尾位置，需要一個游標變量rear（習慣上稱為尾指針）。開始時，讓隊列front度rear都指向數(shù)組的前端，這是一個空隊列。在隊

32、列未滿情況下，隊列可執(zhí)行進隊運算。進隊時，首先讓rear加1,變?yōu)橹赶蜿犃行陆Y(jié)點的存放下標，然后將新結(jié)點送到由rear所指的數(shù)組元素中。隊列非空時，可執(zhí)行出隊運算。出隊時，首先把front所指的隊列首結(jié)點送到接受結(jié)點的變量中，然后讓front加1，使front指向新的隊首結(jié)點。出入隊列的狀態(tài)示意圖環(huán)形隊列(1)若用有MAXN個元素的數(shù)組表示隊列，隨著一系列進隊和出隊運算，隊列的結(jié)點移向存放隊列的數(shù)組的尾端，會出現(xiàn)數(shù)組的前端空著，而隊列空間已用完的情況。一種可行的解決方法是當發(fā)生這樣的情況時，把隊列中的結(jié)點移到數(shù)組的前端，并修改頭指針和尾指針。另一種更好的解決辦法是采用環(huán)形隊列。環(huán)形隊列就是將實

33、現(xiàn)隊列的數(shù)組q的首元q0與末元qmax-1連接起來。隊空的初態(tài)為front=rear=0；在環(huán)形隊列中，當rear趕上front時，隊列滿。反之，當front趕上rear時，隊列為空。這樣隊空或隊滿的條件都同為front=rear，這給程序判別隊空或隊滿帶來不便。為此采用當隊列只剩下一個空閑結(jié)點的空間時，就認為隊列已滿的簡單辦法以區(qū)別隊空和隊滿。示意圖如下：隊列出、入隊操作示例： 環(huán)形隊列(2)在下面的入列和出隊算法中，queue數(shù)組用來存放隊列元素，頭指針為front，尾指針為rear，數(shù)據(jù)結(jié)構定義如下：#define MAX 50int queueMAX；int front=-1,rear

34、= -1;1、順序隊列的進隊列算法：隊滿時返回eof，否則返回0int insert_queue (int x) if (rear= =MAX-1) return(eof); queue+rear=x; return(0);環(huán)形隊列(3)2、順序隊列出隊列算法：隊空時返回eof，否則返回y值int delete_queue() int y ; if (front= =rear) return(eof); y=queue+front; return(y);3、入循環(huán)隊列int inset_q(int q, int x) int front,rear; if (rear+1)%MAX)= =fro

35、nt) return(eof);else rear=(rear+1)%MAX; qrear=x; return(1); 環(huán)形隊列（4）4、出循環(huán)隊列int delete_q(int q, int y) int front,rear; if(front= = rear) return(0); front=(front+1)%MAX; y=qfront; return(y);3.2.2鏈式存儲隊列 隊列也可以用鏈表實現(xiàn)，用鏈表實現(xiàn)的隊列稱為鏈式隊列。鏈表的第一個表示是隊列首結(jié)點，鏈表的末尾表示是隊列的隊尾結(jié)點，隊尾結(jié)點的鏈接指針值為null。隊列的頭指針hpt指向隊列的首結(jié)點，隊列的尾指針tpt指

36、向隊尾結(jié)點。當隊列的頭指針hpt值為null時，隊列為空。設有：typedef struct node node data; struct node *link; Lnode;一、鏈式隊列進隊函數(shù)示意圖 tpthpt p A X nullB C null鏈式隊列進隊函數(shù)定義void Len_queue(Lnode *hpt,Lnode *tpt,node x) Lnode *p=(Lnode *)malloc(sizeof(Lnode); p-data=x; p-link=null; if (hpt= =null)tpt=hpt=p;else tpt = (tpt)-link=p; 二、鏈式隊

37、列出隊函數(shù)示意圖 hpt=hpt-link tpthpt pA B C null鏈式隊列出隊函數(shù)定義int Lde_queue(Lnode *hpt,Lnode *tpt,node *cp) Lnode *p= hpt; if(hpt= =null) return 1; /* 隊空*/*cp= (hpt)-data;hpt=(hpt)-link;if(hpt= = null) tpt=null;free (p);return 0; 舉例(1)P33 二1向一個棧頂指針為Top的鏈棧中插入一個S所指的結(jié)點時，其進行的操作是（ ）。2從棧頂指針為Top的鏈棧中刪除一個結(jié)點，并將結(jié)點保存在X中，進行

38、的操作是（ ）。3在具有N個單元的循環(huán)隊列中，隊滿時共有（ ）個元素。4假設以S和X分別表示入棧和出棧操作，則對輸入序列a,b,c,d,e進行一系列操作SSXSXSSXXX之后，得到的輸出序列為（ ）。5設有數(shù)組A0.m作為循環(huán)隊列的存儲空間，front為隊頭指針，rear為隊尾指針，則元素x執(zhí)行入隊操作的語句是（ ）。舉例(2)P33 二6在一個鏈隊中，如果F、R分別為隊頭、隊尾指針，則插入S所指結(jié)點的操作是（ ）。7棧的邏輯特點是（ ），隊列的邏輯特點是（ ），二者的共同特點是（ ）。8（ ）可以作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構。9在隊列中，新插入的結(jié)點只能添加到（ ）。10鏈隊在一定范

39、圍內(nèi)不會出現(xiàn)（ ）的情況，當lq.front= =lq.rear時，隊中無元素，此時（ ）。 作業(yè)P33 三.1第四章 字符串、數(shù)組和廣義表 4.1 字符串的基本概念 4.2 字符串的存儲結(jié)構 4.3 字符串的模式匹配 4.4 數(shù)組的基本概念 4.5 矩陣的壓縮存儲 4.6 廣義表 4.1字符串基本概念字符已成為非數(shù)值應用重要的處理對象.如文字編輯,情報檢索,自然語言翻譯和各種事務處理系統(tǒng)等。字符串是由某字符集上的字符所組成的任何有限字符序列.當一個字符串不包含任何字符時,稱它為空字符串。一個字符串所包含的有效字符個數(shù)稱為這個字符串的長度。一個字符串中任一連續(xù)的子序列稱為該字符串的子串。包含子

40、串的串相應地稱為主串。在C語言中,字符串常量是用一對雙引導括起來若干字符來表示。通常稱字符在序列中的序號為該字符在串中的位置，子串在主串中的位置則以子串的第一個字符在主串中的位置來表示.例4.1:假如a,b,c,d為如下的四個串:a=“BEI”,b=“JING”c=“BEIJING”,d=“BEI JING”則它們的長度為：3，4 ，7和8；并且a和b都是c和d的子串；a在c和d中的位置都是1；而b在c中的位置是在d中的位置是5。另外，每個字符串的最后一個有效字符之后有一個字符串結(jié)束符，記為0。字符串通常存于足夠大的字符數(shù)組中。如要稱兩個串是相等的，當且僅當這兩面?zhèn)€串的值相等。也就是說，只有當

41、兩個串的長度相等，并且各對應位置的字符都相等時才相等。4.2字符串的存儲結(jié)構對于字符串常量，只需作為一個字符的序列存儲。對于字符串變量，賦給它一個串名，對串運算時，通過變量名訪問其值。其存儲分配有兩種形式，一是將字符串設計成一種結(jié)構類型（如pascal語言和c語言中，字符串都是用字符數(shù)組來實現(xiàn)），從字符串名可直接訪問到字符串值，字符串值的存儲分配是在編譯時完成的；另一是字符串值的存儲分配在程序運行時完成，在字符串名和字符串值之間需建立一個對照表（稱為串名的存儲映象），字符串的訪問通過串名的存儲映象進行。我們稱前一種為順序存儲結(jié)構，后一種為鏈式存儲結(jié)構。4.2.1串的存儲結(jié)構 和線性表的順序存儲

42、結(jié)構類似，用一組地址連續(xù)的存儲單元存儲串的字符序列。在C語言中用一維數(shù)組來實現(xiàn)。（一）緊縮格式假定，一個存儲單元可存放K個字符，而且給出的串長度為N，那么此字符串的字符串值就要占N/K個存儲單元緊縮格式是以字符為單位依次將字符存放在存儲單元里。（PASCAL語言中的緊縮數(shù)組）（二）非緊縮格式在一個存儲單元中存放一個字符，所需存儲單元個數(shù)就是串長。緊縮格式可節(jié)省存儲空間，但在進行串運算時需要花費較時間去分離同一存儲單元中的字符。4.2.2串的鏈式存儲結(jié)構和線性表的鏈式存儲結(jié)構類似，也可采用鏈表方式存儲串值。由于串結(jié)構的特殊性結(jié)構中的每個數(shù)據(jù)元素是一個字符，則可用鏈表存儲串值時，存在一個“結(jié)點大小

43、”的問題，即每個結(jié)點可以存放一個字符，也可存放多個字符。 head 結(jié)點大小為4示圖 head 結(jié)點大小為1示圖 ABDCEFGHI000A B C D 4.3 字符串的模式匹配設s和t是給定的兩個串，在串s中尋找等于t的子串的位置的過程稱為模式匹配，其中，s串稱為主串，t串稱為模式，如在s中找到等于t的子串，則稱匹配成功，并返回模式t在s串的序號：反之匹配失敗，并返回于序號為零。例4.2 : 1、s=“abcdefg”,t=“efg” 則模式t在主串s中的序號等于52、s=“abcdefg”,t=“abcdg”則t在s中的序號等于03s=“abcdefabc”,t=“abc”如從s串的第一個

44、字符開始搜索則序號等于1；如從s第三個字符開始搜索，則序號等于7。4.3.1模式匹配的BF算法算法的基本思想是：從主串s的第一個字符起和模式的第一趟匹配。第一個字符比較之，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從主串的第二個字符起再重新和模式的字符比較之。依次類推，直至模式t中的每個字符依次和主串s中的一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)值為和模式t中第一個字符相等的字符在主串s中的序號，否則稱匹配不成功，函數(shù)值為零。如果s=“ababcabcacbab”t=“abcac”t在s中的模式匹配過程如下 i=2第一趟匹配 a b a b c a b c a c b a b a b c j=2

45、i=1第二趟匹配 a b a b c a b c a c b a b a j=0 i=6第三趟匹配 a b a b c a b c a c b a b a b c a c j=4 i=3 t在s中的模式匹配過程(續(xù)) i=3第四趟匹配 a b a b c a b c a c b a b a j=0 i=4第五趟匹配 a b a b c a b c a c b a b a j=0 i=10第六趟匹配 a b a b c a b c a c b a b a b c a c j=5方法一： BF算法的實現(xiàn)函數(shù)：int index(char s,char t, int start) int I,j,m

46、,n; m=strlen(s); n=strlen(t);if(startm+1 | n=0) return(0);else i=start; /*從S中的第start位開始匹配*/ j=0; while(im & j=n) return(i-n); else return(0); 方法二：BF算法也可用如下函數(shù)表示： int simple match(char *s,char *t) int n=strlen(s),m=strlen(t),i,j,k; for(j=0;jn-m;j+) /*順序考察從si開始的子串*/ for(i=0;im&sj+i=ti;i+) /* 從sj開始的子串與t

47、比較*/ if(i= =m) return j+1; return 0 4.3.2模式匹配的KMP算法在執(zhí)行簡單匹配算法中的字符比較過程中，當出現(xiàn)sj+I!=tI時，有s0sj,sj+1 sj+i-1,sj+i != t0 t1 ti-1 ti 這時，簡單匹配算法對字符串S要回溯，回溯到從sj+1開始繼續(xù)與模式字符串T從頭開始逐一字符比較，KMP算法是對正文字符串比較不回溯的算法。如果對于模式字符串t存在一個整數(shù)k(kp&*q-1= = ) /* 設定字符串的結(jié)束符*/ 15 （4） ; 16 else *q=0; 17 return (5) ; 18 19 void main() 20 21

48、 char str =”we are Chinese “ 22 printf(“%sn”,sdel(str); 23 4.4 數(shù)組的基本概念在概念上，數(shù)組由固定個數(shù)的元素組成，全部元素的類型相同，元素依次順序存儲。每個元素對應一個下標，數(shù)組元素按數(shù)組名和元素的下標引用，引用數(shù)組元素的下標個數(shù)稱為數(shù)組的維數(shù)。在C語言中，約定數(shù)組的第一個元素的下標為0，其余依次類推，由n個元素組成的數(shù)組，其最后一個元素的下標為n-1。數(shù)組元素可以是任何類型的，當元素本身又是數(shù)組時就構成多維數(shù)組。數(shù)組通常是順序存儲的，對于多維數(shù)組，C語言按行優(yōu)先順序存放。如有以下數(shù)組定義： int a110,a289,a3789；

49、則數(shù)組a1是一維數(shù)組，a2是二維數(shù)組，a3是三維數(shù)組。記元素X的內(nèi)存地址為Loc(x),設每個元素所需內(nèi)存字節(jié)數(shù)為s，存儲元素a1 i,a2ij,a3ijk的內(nèi)存地址分別可由以下算式確定：內(nèi)存地址計算Loc(a1i)=Loc(a10)+i*sLoc(a2 ij)=Loc(a200)+(i*9+j)*sLoc(a3ijk)=Loc(a3000)+(i*8+j)*9+k)*s若用C語言的指針來描述，以上算式可分別簡成： &a1i=&a10+i &a2ij=&a200+i*9+j &a3ijk)=& a3000+(i*8+j)*9+k當然數(shù)組也可按列優(yōu)先順序存放。4.5 矩陣的壓縮存儲4.5.1 特

50、殊矩陣的壓縮特殊矩陣：假若值相同的數(shù)據(jù)元素或者零元 素在矩陣的分布有一定的規(guī)律，則我們稱此類矩為特殊矩陣。1對稱矩陣 若一個n階矩陣A中的元素滿足下述性質(zhì)：aij=aji , 0i,jn-1則稱為n階對稱矩陣。 一維數(shù)組下標k與i,j對應關系k= i(i+1)/2+j 當ij(下三角存貯) j(j-1)/2+i 當ij(上三角存貯) 如一一對應需n2個存儲單元的矩陣壓縮存儲僅需1+2+3+ +n= n(n+1)/2 個存儲單元。下三角存儲數(shù)組sak ，如圖4-7所示。則LocAij=LocA00+(i(i+1)/2)+j*s 2、三角矩陣若一個n階矩陣中的元素滿足下述性質(zhì)；當ij時aij=0且

51、oi,jn-1則稱為上三角矩陣。下三角矩陣示圖 3、對角矩陣所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中。即除了主對角線上和直接在對角線上、下方若干條對角線上的元素之外，所有其它的元素皆為零。地址計算公式：LocAij=LocA00+i(2d+1)+(2d+1)+(j-i)*s 4.5.2 稀疏矩陣當非零元素的個數(shù)只占矩陣元素總數(shù)的25%30%或低于這個有百分數(shù)時，我們稱這樣的矩陣為稀疏矩陣。 1、用三元組數(shù)組表示稀疏矩陣可以用一元組（i,j,aij）唯一確定矩陣中的非零元素壓縮存儲概念，只存稀疏矩陣的非零元素。圖4-9稀疏矩陣可表示為（0，1，12），（1，0，7）（1，4，1）（2，2

52、，8）（3，1，6）（4，0，18）（4，2，7）的一維數(shù)組。在C語言描述算法的數(shù)據(jù)結(jié)構定義如下：#define MAX 100struct node int row;int colum;int value;tyredef struct node NODE;NODE maxMAX;2、稀疏矩陣的十字鏈表表示法：在十字鏈表中，稀疏矩陣的每一行用一個帶表頭節(jié)點的循環(huán)表示，每一列也用一個帶表頭的循環(huán)鏈表表示。在這個結(jié)構中，除表頭節(jié)點外，每一個節(jié)點都代表矩陣中的一個非零元素，它由五個域組成；行域（row），列域（col）,值域(val),向下域(down)和向右域(right)。節(jié)點結(jié)構和存儲表示如下

53、： 表結(jié)點 行（列）頭結(jié)點 表頭結(jié)點 Down rowrightcowvolrightdown00linkmnlink舉例（）若有矩陣M如下: 例題目：求一個3*3矩陣對角線元素之和 1.程序分析：利用雙重for循環(huán)控制輸入二維數(shù)組，再將aii累加后輸出。2.程序源代碼：#include void main()float a33,sum=0;int i,j;printf(please input rectangle element:n);for(i=0;i3;i+)for(j=0;j3;j+)scanf(%f,&aij);for(i=0;i3;i+)sum=sum+aii;printf(dui

54、jiaoxian he is %6.2f,sum);例題目：將一個數(shù)組逆序輸出。1.程序分析：用第一個與最后一個交換。2.程序源代碼： #define N 5vod main() int aN=9,6,5,4,1,i,temp;printf(n original array:n);for(i=0;iN;i+)printf(%4d,ai);for(i=0;iN/2;i+)temp=ai;ai=aN-i-1;aN-i-1=temp;printf(n sorted array:n);for(i=0;itag) x= (4) ; else x= (5) ; if(x) return ( (6) );

55、return 0; 作業(yè)P56 二.4P57 三.1,4第五章 樹 5.1 樹的定義和術語 5.2 二叉樹 5.3遍歷二叉樹 5.4 線索二叉樹 5.5 樹和森林 5.6 樹的應用 5.1 樹的定義和術語一、樹的定義 樹（tree）是n(n0)個結(jié)點的有限集。在一棵非空樹中： （1）有且僅有一個特定的稱為根（root）的結(jié)點； （2）當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集（T1,T2,Tm），其中每一集合本身又是一棵樹，并且稱為根的子樹（subtree）。舉 例例51 （a）只有根結(jié)點的樹 （b）一般的樹圖5-1-1的（b）中A為根結(jié)點，其余結(jié)點分成三個互不相交的子集：T1=B，

56、E，F(xiàn)，K，L，T2=C，G，T3=D，H，I，J而T1，T2，T3本身又都是只有一個根結(jié)點的樹。ALKEFGHIJDCBAM二、樹結(jié)構中的一些基本術語：（1）結(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支（2）結(jié)點的度：結(jié)點擁有子樹數(shù)目稱為結(jié)點的度。如圖5-1-1的（b）中，A的度為3；C的度為1；M的度為0。（3）葉子（或終端）結(jié)點：度為零的結(jié)點。（4）分支結(jié)點（或非終端結(jié)點）：除根結(jié)點外度不為零的結(jié)點，也稱為內(nèi)部結(jié)點。 （5）樹的度：樹內(nèi)各結(jié)點的度的最大值。基本術語(續(xù))（6）孩子：結(jié)點的子樹的根稱為該結(jié)點的孩子。如圖5-1-1的（b）中，D為A的子樹T3的根，則D是A的孩子。（7）雙親：

57、和孩子定義相應地該結(jié)點稱為孩子的雙親。如圖5-1-1的（b）中，A為D的雙親。（8）兄弟：同一個雙親的孩子之間互稱兄弟。如圖5-1-1的（b）中的H，I，J。（9）祖先：從根到該結(jié)點所經(jīng)過分支上的所有結(jié)點。如：M的祖先為A，D，H（10）子孫：以某結(jié)點為根的子樹中的任一結(jié)點都稱為該結(jié)點的子孫。如圖5-1-1的（b）中B的子孫為E，F(xiàn)，K，L基本術語(續(xù))（11）層次：從根開始定義為第一層，根的孩子為第二層，依次例推。（12）深度（或高度）：樹中結(jié)點的最大層次。（13）有序樹：將樹中結(jié)點的各子樹看成從左到右是有序的。 無序樹：樹中結(jié)點的各子樹沒有次序的。有序樹中最左邊的子樹的根稱第一個孩子，最右

58、邊的稱為最后一個孩子。（14）森林：是m(m0)棵互不相交的樹的集合，對樹中每個結(jié)點而言，其子樹的集合即為森林。5.2 二叉樹一、 二叉樹的定義和性質(zhì)：1、定義：二叉樹是另一種樹型結(jié)構，它的特點是每個結(jié)點至多只有二棵子樹（即二叉樹中不存在度大于2的結(jié)點）并且二叉樹的子樹有左右之分，其次序不能任意顛倒。2、如圖5-2-1所示二叉樹的五種基本形態(tài) （a） (b) (c) (d) (e)二叉樹的性質(zhì)(1)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點（i1）。 (2)性質(zhì)2：深度為k的二叉樹的最大結(jié)點數(shù)為2k-1(k1)。(3)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n,度為2的結(jié)點數(shù)為 n2

59、,則n0=n2+1(4)一棵深度為k且有2k-1個結(jié)點的二叉樹稱滿二叉樹。特點：每層上的結(jié)點數(shù)都為最大結(jié)點數(shù)，除終端結(jié)點外，每個結(jié)點都有兩棵子樹。二叉樹的性質(zhì)(續(xù))（5）完全二叉樹：如深度為k，有N個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到N的結(jié)點一一對時，稱之為完全二叉樹。 完全二叉樹的特點是：深度為k的完全二叉樹，其前k-1層是一棵滿二叉樹，最后第k層結(jié)點都盡量排在靠左的位置上。顯然一棵滿二叉樹一定是完全二叉樹，但一棵完全二叉樹不一定是滿二叉樹。 二叉樹的性質(zhì)(續(xù))（6）完全二叉樹的兩個特性： 性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為Log2n+1。 性質(zhì)5：如

60、果對一棵有n個結(jié)點的完全二叉樹（其深度為Log2n+1）的結(jié)按順序編號，則任一結(jié)點i(1in)有：如i=1,則結(jié)點i是二叉樹的根結(jié)點，若i1，則i的雙親結(jié)點為結(jié)點i/2;如2in，則i的左孩子是結(jié)點2i，否則無左孩子；若2i+1n，則i的右孩子是結(jié)點2i+1 ,否則無右孩子。二叉樹二、二叉樹的存儲結(jié)構 （一）順序存儲結(jié)構 用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素，按滿二叉樹的結(jié)點順序編號依次存放二叉樹中數(shù)據(jù)元素。 0 1 2 3 4 5 T(6)圖5-3完全二叉樹ABCDEFABCDEF二叉樹的存儲結(jié)構（二）鏈式存儲結(jié)構鏈表的結(jié)點至少包含：數(shù)據(jù)域和左右指針域的鏈有時還需增一指向雙親的指針域，有