1、第一章 概論 1·1 數據結構的概念 一、基本概念和術語l       數據(Data)：是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。是計算機加工的“原料”。l       數據元素(Data Element):是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。有些情況下，數據元素也稱為元素、結點、頂點、記錄。有時數據元素可以由若干數據項（也稱為字段、域、屬性）組成，數據項是數據的有獨立含義的最小標識單位。l 

2、      數據類型：（Data Type）:是一個值的集合和定義在這個值集上的所有的操作。例如，整數類型。數據類型可分為：原子數據類型和結構數據類型。原子類型的值是不可分解的，結構類型的值是由若干成分按某種結構組成的。二、    數據的三個層次數據是計算機加工的對象，是數據元素的集合；數據元素是數據的基本單位，常稱為結點、元素、記錄等，作為一個整體出現；數據項是數據的最小不可分割的單位。三、什么是數據結構(Data Structure)：數據之間的相互關系，即數據的組織形式。包括以下三方面：  

3、; 數據元素之間的邏輯關系，也稱為數據的邏輯結構；   數據元素及其關系在計算機存儲器內的表示，稱為數據的存儲結構；   數據的運算，即對數據施加的操作。四、數據的邏輯結構分兩類：線性結構和非線性結構。（有的教材稱四種結構: 集合、線性結構、樹形結構、圖形結構或網狀結構）五、數據的存儲結構：數據結構在計算機中的表示（又稱映象）稱為數據的物理結構，又稱存儲結構：數據元素及其關系在計算機存儲器的表示。用于表示數據元素的位串稱之為元素或結點，用于表示數據項的位串稱之為數據域。算法的設計取決于選定的數據邏輯結構，而算法的實現依賴于采用的存儲結構。數據有四種存儲結

4、構： 順序存儲結構：把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。通常順序存儲結構是借助于語言的數組來描述的。 鏈式存儲結構：不要求邏輯上相鄰的結點物理上也相鄰，結點間的邏輯關系是由附加的指針字段表示的，通常要借助于語言的指針類型來描述。 索引存儲方法 散列存儲方法六、數據結構課程及其重要性1968年美國克努特教授開創了數據結構的最初體系。數據結構是一門綜合性的專業課程，是一門介于數學、計算機硬件、計算機軟件之間的一門核心課程。是設計和實現編譯系統、操作系統、數據庫系統機其他系統程序和大型應用程序的基礎。 1·2 為什么要學

5、習數據結構 一、     用計算機解題的過程具體問題數學模型算法程序。然而在現實社會中存在著許多非數值計算問題，其數學模型難以用數學方程描述。二、     幾個例子說明數據結構研究的內容1 學生成績表的管理圖書館的書目檢索自動化問題-計算機處理的對象之間存在著線性關系，稱為線性的數據結構。電話號碼查詢問題-按順序查找和按索引表查找效率不同。2       人機對奕問題(game playing)計算機處理的對象是一個個格局。所有可能出現的格局是一

6、棵倒置的樹。計算機能與人對奕，是因為人們將博奕規則存入計算機，利用高速運算，早期chess 4.6程序能每步查找400000500000個結點，而心理學家認為，人類選手只能預見50步。3       田徑賽的時間安排問題-數學模型是圖的數學結構。綜合以上例子，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如表、樹和圖之類的數據結構。因此，簡單說，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。 1·3 算法描述 一、算法（Algorithm）算法是對

7、特定問題求解步驟的一種描述，它是指令的有限序列。每條指令表示一個或多個操作。算法具有五個重要特性：有窮性、確定性、可行性、輸入、輸出。二 、算法設計的要求正確性、可讀性、健壯性和效率與低存儲量要求三 、算法的描述形式：自然語言表示法；偽代碼表示法；流程圖表示法；結構化流程圖（NS圖）表示法；PAD圖表示法。四 、本書算法用C語言描述。1       函數的形式函數類型 函數名（函數參數表）形式參數說明 內部語句說明； 執行語句；2       條件語句的兩種形式3 

8、      循環語句的三種形式4       情況語句5       賦值語句6       輸入、輸出語句7       注釋形式 1·4 算法分析 一 、算法的評價時間度量；空間度量；易理解，易編制，易調試。二 、舉例說明算法復雜度的計算算法時間是由控制結構和原操作的決定的。

9、做法：選取一種是基本操作的原操作，以該基本操作重復的次數作為算法的時間量度。時間復雜度：算法中基本操作重復執行的次數是問題規模n的某個函數f（n），T（n）=O（f（n）。它表示隨問題規模n的增大，算法執行時間的增長率和f（n）的增長率相同。 語句的頻度：是該語句重復執行的次數。例1：交換i和j的內容。temp=i; i=j; j=temp;以上三條語句的頻度均為1，該程序的執行時間是與問題規模n無關的常數，因此算法的時間復雜度為常數階，記作T（n）=O（1）。例2：變量計數。(1）x=0;y=0;(2)for(k=1;k<=n;k+)(3) x+;(4)for(i=1;i<=n;

10、i+)(5) for(j=1;j<=n;j+)(6) y+;以上語句中頻度最大的語句是（6），其頻度為f(n)= n2,所以該程序段的時間復雜度為T(n)=O(n2)例3：求兩個n階方陣的乘積C=A×B，其算法如下：#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i<=n;+i) /* 次數 n+1 */for (j=1;j<=n;+j) /* 次數 n*(n+1)*/ Cij=0; /* 次數 n2 */for (k=1;k<=n,k+) /* 次數

11、n2(n+1) */ Cij=Cij+Aik*Bkj;/* 次數 n3 */T(n)=2n3+3n2+2n+1lim（T(n)/ n3)=2 T(n)=O(n3)例4： （1）+x;s=0;（2）for (i=1;i<=n;+i) +x;s+=x;（3）for (j=1;j<=n;+j)（4） for (k=1;k<=n;k+)+x;s+=x;(5) i=1; while(i<=n) i=i*2;執行次數與n的關系是n=23       算法的漸進時間復雜度與算法的時間復雜度。4  

12、0;    算法的最佳、最差、平均時間復雜度5       算法的存儲空間需求6 計算機內存的增大與速度的提高并不能降低選擇合適算法與數據結構的重要性。例如，百元錢買百支筆問題(鋼筆3元一支，圓珠筆2元一支，鉛筆0.5元一支)，用三層循環，內循環100萬次，在某機器上運行用了50分鐘。for (i=1,i<=100;i+) for (j=1,j<=100;j+) for (k=1,k<=100;k+) if (i+j+k=100) && (3*i+2*j+0.5*k=10

13、0) printf(“%d,%d,%d”,i,j,k)而經過分析，鋼筆最多買20支，圓珠筆最多買30支，優化后只運行了2秒，相差1500倍。for (i=0,i<=20;i+) for (j=0,j<=34-i;j+) if (3*i+2*j+0.5*(100-i-j)=100) printf(“%d,%d,%d”,i,j,k)  第二章         線性表 2·1 線性表的概念及運算 2·1·1 線性表的邏輯結構1線性表的定義。

14、2線性表的特點：在數據元素的非空有限集中 存在唯一的一個被稱做“第一個”的數據元素； 存在唯一的一個被稱做“最后一個”的數據元素； 除第一個之外，每個元素都只有一個前驅； 除最后一個之外，每個元素都只有一個后繼。 線性表中結點之間的邏輯關系是結點之間的鄰接關系。2·1·2 線性表的運算1          線性表的運算 置空表SETNULL（L）：將線性表L置成空表。 求表長LENGTH（L）：求線性表L中結點的個數。 取表中的結點GET（L，i）。 定位LOCATE（L，x）：當線性

15、表L中存在一個值為x的結點時，結果是該結點的位置；若表中存在多個值為x的結點，則是首次找到的結點位置；若沒有值為x的結點，結果為0。 插入結點INSERT（L，x，i）。 刪除結點DELETE（L，i）。2 線性表運算舉例例利用線性表的基本運算實現清除表L中多余的重復結點。void PURGE(List *L) int i=1,j,x,y; while(i<LENGTH(L)x=GET(L,i); j=j+1; while(j<=LENGTH(L) y=GET(L,j); if(x=y) DELETE(L,j); else j+; i+; 2·2 線性表的順序存儲

16、0;2·2·1 順序表1、線性表的順序表示：指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。用物理位置來表示邏輯結構。LOC(ai+1)=LOC(ai)+cLOC(ai)=LOC(a1)+(i-1)*c2、順序表的特點：隨機存取的存儲結構。只要確定了存儲線性表的起始位置，線性表中的任一數據元素可隨機存取。3、線性表的C語言描述方式（用一維數組）#define maxsize 1024typedef int datatype;typedef struct datatype datamaxsize;int last; /* last表示終端結點在向量中的位置 */seq

17、uenlist;2·2·2 順序表上的基本運算順序表容易實現訪問操作，可隨機存取元素。但插入和刪除操作主要是移動元素。1 插入操作算法思想：在第i個位置上插入一個新元素，將第n 至（i+1）個元素逐一向后移動一個位置。即(a1,ai-1,ai,an)變成(a1,ai-1,x,ai,an)。算法：int INSERT(sequenlist *L, datatype x, int i )int j;if (*L).last)>=maxsize-1)printf(“overflow”); return(NULL); else if(i<1) | (i>(*L).

18、last)+1)printf(“error”); return(NULL); else for(j=(*L).last; j>=i-1; j-)(*L).dataj+1=(*L).dataj;(*L).datai-1=x;(*L).last+; return (1); 時間復雜度的分析：最好情況下無移動（插入在表的最后），最壞情況下移動n次（插入在表的最前面），平均移動n/2次，時間復雜度為O(n)。2 刪除操作：算法思想：刪除第i個元素，將第（i+1）至第n個元素逐一向前移動一個位置。即(a1,ai-1,ai, ai+1,an)變成(a1,ai-1,ai+1,an)算法：int DEL

19、ETE(sequenlist *L，int i) int j; if(i<1)|(i>(*L).last+1) print(“error”); return(NULL); else for(j=i; j<=(*L).last; j+) (*L).dataj-1=(*L).dataj; (*L).last-; return (1);2·3 線性表的鏈式存儲結構 順序存儲結構的特點：線性表的鏈式存儲結構的特點：是用一組任意的存儲單元存儲線性表的數據元素。數據元素的映象用一個結點來表示。結點的一個域表示元素本身，另一個是能指示其后繼的指針，用來表示線性表數據元素

20、的邏輯關系。結點（Node）、數據域、指針域、指針、鏈、頭指針鏈式存儲結構的特點：插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機存取特點。鏈表可分為單鏈表、循環鏈表和雙向鏈表。2·3·1 單鏈表鏈表中的每一個結點中只包含一個指針域的稱為單鏈表或線性鏈表。datanext單鏈表可由頭指針唯一確定，在C語言中，用結構指針來描述。typedef int datatype;typedef struc nodedatatypedata; struct node *next linklist;linklist *head,*p;兩個C語言的標準函數：malloc( ),

21、 free( )p=malloc(sizeof(linklist); free(p);2·3·2 單鏈表上的基本運算1 建立單鏈表（1）頭插法建表linklist *CREATELIST( )char ch; linklist *head,*s; head=NULL; ch=getchar( ); while(ch!=$) s=malloc(sizeof(linklist); s->data=ch; s->next=head; head=s; ch=getchar( ); return head; （2） 尾插法建表linklist *CREATLISTR( )

22、char ch; linklist *head,*s,*r; head=NULL; r=NULL; ch=getchar(); while(ch!=$) s=malloc(sizeof(linklist); s->data=ch; if (head=NULL) head=s;else r->next=s; r=s; ch=getchar( ); if(r!=NULL) r->next=NULL; return head;2 查找運算（1） 按序號查找算法思想：單鏈表是非隨機存取結構。每個元素的位置信息都包含在前驅結點的信息中，所以取得第i個元素必須從頭指針出發尋找。設置一個指

23、針變量指向第一個結點，然后，讓該指針變量逐一向后指向，直到第i個元素。linklist GET(linklist *head, int i)int j; linklist *p;p=head; j=0;while(p->next!=NULL) && (j<i)p=pnext; +j; if(i=j) return p; else return NULL;（2） 按值查找linklist *LOCATE(linklist *head,datatype key) linklist *p; p=head->next; while(p) if (p->data!

24、=key) p=p->next; else break; return p; 3 插入運算 后插操作INSERTAFTER(linklist *p,datatype x) linklist *s; s=malloc(sizeof(linklist); s->data=x; s->next=p->next; p->next=s;4 刪除操作： pnext=pnextnextDELETEAFTER(linklist *p)linklist *r; r=p->next; pnext=rnext; free(r); 2·3·3 循環鏈表首尾相接的

25、鏈表循環鏈表是另一種形式的鏈式存儲結構，其特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。在實際應用中，循環鏈表往往只設尾指針，設rear該循環鏈表的尾指針，若有頭結點，則rear->next->next為第一元素；若無頭結點，則rear->next為第一元素。例2.4在鏈表上實現兩個線性表(a1,a2,an)和(b1,b2,bm)鏈接成一個線性表(a1,a2,an , b1,b2,bm)的運算。解題思路：若在設頭指針的單循環鏈表上做此操作，則需遍歷第一個鏈表找到an，時間復雜度為O(n)，但若在設尾指針的單循環鏈表上做此操作，則只需修改指針，時間復雜度為O(1

26、)。linklist *CONNECT(linklist *ra,*rb)linklist *p; p=ra->next; ra->next=rb->next->next; free(rb->next); rb->next=p; return rb; 2·3·4 雙(向)鏈表1、 雙(向)鏈表特點：在雙向鏈表的結點中有兩個指針域，分別指向前驅和后繼。 雙向鏈表也可以有循環鏈表。2、 雙（向）鏈表的存儲結構：typedef struct dnode dataype data;struct dnode *prior,*next;dlinkli

27、st;dlinklist *head;3、 雙向鏈表的操作：雙指針使得鏈表的雙向查找更為方便、快捷。查找前驅和后繼的執行時間為O（1）。僅需涉及一個方向的指針的操作和線性鏈表的操作相同。插入和刪除需同時修改兩個方向的指針。雙鏈表的前插操作算法：DINSERBEFORE(p,x)dlinklist *p; datatype x;dlinklist *s; s=malloc(sizeof(dlinklist); s->data=x; s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s;雙鏈表

28、上刪除*p自身的操作的算法：DELETENODE(p)dlinklist *p;p->prior->next=p->next; p->next->prior=p->prior; free(p); 2·4 順序表和鏈表的比較 1          基于空間的考慮2          基于時間的考慮3     

29、60;    基于語言的考慮 第三章         棧和隊列 3·1 棧 311 堆棧1          堆棧的定義 堆棧是只準在一端進行插入和刪除的線性表，稱為LIFO表。允許插入和刪除的一端叫棧頂，另一端叫棧底。2         棧的兩種工作方式（1） 棧頂固定，棧底可

30、動：壓入元素時依次下移，退棧時依次上移。（2） 棧底固定，棧頂可動（常見方式）3         堆棧的基本運算（1） 置空棧 SETNULL（S） 將棧S置成空棧；（2） 判?？?EMPTY（S）若?？眨瑒t結果為true,否則為false；（3） 進棧 PUSH（S,x） 往棧S中插入一個元素x；（4） 退棧 POP（S） 棧頂指針下移；（5） 取棧頂元素 TOP（S），取棧頂元素；3·1·2 順序棧1、類型定義 #define maxsize 64typedef int datatype;t

31、ypedef struct datatype datamaxsize; int top; seqstack,*s;2、在順序棧上實現棧的操作 (1) 置?？誗ETNULL(seqstack *s) s->top=-1;（2） 判?？?int EMPTY（seqstack s）if (s->top>=0) return FALSE; else return TRUE; （3） 進棧seqstack *PUSH（seqstack *s ,datatype x）if (s->top=maxsize-1) printf(“overflow”); return NULL; els

32、e s->data+s->top=x; return s; （4） 退棧datatype POP（seqstack *s ）if (EMPTY(s) printf(“overflow”); return NULL; else return(s->datas->top-); （4）取棧頂元素 TOP（S）；datatype TOP（seqstack *s ）if (EMPTY(s) printf(“overflow”); return NULL; else return(s->datas->top); 3、兩個棧共享一個向量空間#define maxsize

33、100typedef struct datatype datamaxsize; int top2;dstack, *s;一個棧從左（0）向右發展，另一個棧從右向左發展，?？諘r兩棧指針分別為-1和maxsize,棧滿的判斷是兩棧頂指針差的絕對值為1。3·1·3 鏈棧1、              棧的單鏈形式 上節講的“前插鏈表”就是鏈棧。由于棧的操作在棧頂，所以，鏈棧一般不設頭結點。typedef int datatype;typedef str

34、uct node datatype data; struct node *next; node,linkstack,*top;2、棧的基本操作在鏈棧下的實現（1）     壓棧（入棧）核心語句有：p=(linkstack*) malloc(sizeof(node);p->data=x;p->next=t; top=p; /*無頭結點棧*/（2）     退棧 pop(s)if (st=null) printf(“n underflow”);else p=s->next;s->next=p-&

35、gt;next;free(p); （3）     取棧頂元素 top(s)if (st=null) printf(“n underflow”); return NULL;else return(x=s->data)（4）     判棧空empty(s)if (s=null) return TRUE;else return(true) 3·3 棧的應用舉例 1數制轉換將十進制數N轉換成d進制N=(N div d)*d + N mod d計算過程是從低位到高位順序產生d進制數的各個數

36、位。算法思想：將計算過程的d進制數逐位進棧，然后逐個出棧。void conversion(seqstack *s)SETNULL(s); scanf(“%d%d”,N,d); while(N)PUSH(s,N%d); N=N/d; while(!EMPTY(s)e=pop(s); printf(“%d”,e);2、文字編輯器設計一個簡單的文字編輯器，使其具有刪除打錯字符的功能void EDIT(seqstack *s)char c; SETNULL(s); c=getchar(); while(c!=*) if(c=#) POP(s);else if (c=) SETNULL(s); else

37、 PUSH(s,c);c=getchar( ); 3 表達式求值 概念：前綴表達式，中綴表達式，后綴表達式 +a b, a+b, a b+ 算符：運算符和界符。算符的優先關系。<、=、> 算法的思想：設置兩個工作棧：運算符棧OPTR和操作數棧OPND。操作數棧也放表達式的運算結果。首先置操作數棧為空棧，置運算符棧的棧底為表達式的起始符#。依次讀入表達式中的每個字符，若是操作數則進OPND棧；若是運算符，則和OPTR中的棧頂元素做比較再操作，直至表達式求置完畢。 這里重點介紹中綴表達式轉為后綴表達式，并對后綴表達式求值。 （1） 中綴表達式轉為后綴表達式 設中綴表達式和后綴表達式分別

38、在向量IFX和PFX申，用棧S實現中綴式轉為后綴式，對IFX中表達式從左到右掃描，設TOKEN是掃描讀到的符號，轉換算法可描述如下。 (1)棧初始化。 (2)從左到右掃描向量IFX，重復下述兩步操作，直到表達式尾。 從IPX中取出下個TOKEN(數字、運算符、左括號、右括號)； CASE TOKEN OF '('：將TOKEN壓入棧S; 操作數：將操作數直接送入PFX; 操作符：如棧空或TOKEN比棧頂元素優先級高，將TOKEN進棧；否則，退棧并將退棧元素送入PFX，然后再將TOKEN與新棧頂元素比較之; ）：退棧并將退棧元素送PFX，直到碰到左括號，左括號退棧不送PFX。 (

39、3)當遇到中綴表達式結束符號，連續退棧并送退棧元素到PFX，直至?？铡＃?） 對后綴表達式求值 用實型數棧S存放計算后綴式的中間及最終結果，求值算法可描述如下。 (1)棧初始化。 (2)從左到右掃描向量PFX，重復下述兩步操作，直到表達式尾。 從PFX中取出下個TOKEN(操作數、運算符) CASE TOKEN OF 操作數：將操作數直接送入棧S1;操作符：出棧兩個操作數，對其進行TOKEN操作，結果壓人棧S1 (3)當遇到后綴表達式結束符號，棧頂的值就是結果(應是棧中唯一元素)。4、棧與遞歸的實現遞歸：在函數執行中，直接或間接調用自己的函數稱為遞歸函數。用棧實現遞歸函數：階乘函數int FA

40、CT(n)int n;if(n=1) return(1); else return(n*FACT(n-1);3·3 隊列 3·3·1 隊列的概念及運算1、             隊列的定義隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表（FIFO）。例：日常排隊，操作系統中打印作業的排隊。2、      

41、       隊列的基本運算（1）    置空隊列 SETNULL(Q)（2）    判隊列是否為空EMPTY(Q) 若隊列Q為空，返回true，否則，返回false。（3）    取隊頭元素FRONT(Q) 若隊列Q不空，取隊頭元素。（4）    入隊 ENQUEUE(Q, x) 在隊列Q的隊尾中插入元素x。（5）    出隊DEQUEUE(Q) 若隊列Q不空，則刪除其隊頭元素。3·3·2 順序隊列1定義：隊列的順序存儲結構。是運算受限的順序表。由于隊頭和隊尾都是變化的，因此要設置兩個指針，分別指示隊頭元素和隊尾元素在向量空間中的位置。類型說明如下：typedef struct datatype datamaxsize;int front; /* 指向隊頭元素的前一個位置 */int rear; /* 指向當前隊尾元素的位置 */sequeue;