數(shù)據(jù)結(jié)構(gòu)C語言版講義

1、PAGE PAGE 137第一章 緒論第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)？估猜以下軟件的共性：學(xué)生信息管理、圖書信息管理、人事檔案管理。數(shù)學(xué)模型：用符號、表達式組成的數(shù)學(xué)結(jié)構(gòu)，其表達的內(nèi)容與所研究對象的行為、特性基本一致。信息模型：信息處理領(lǐng)域中的數(shù)學(xué)模型。數(shù)據(jù)結(jié)構(gòu)：在程序設(shè)計領(lǐng)域，研究操作對象及其之間的關(guān)系和操作。忽略數(shù)據(jù)的具體含義，研究信息模型的結(jié)構(gòu)特性、處理方法。第二節(jié) 概念、術(shù)語一、有關(guān)數(shù)據(jù)結(jié)構(gòu)的概念 數(shù)據(jù)：對客觀事物的符號表示。 例：生活中還有什么信息沒有被數(shù)字化？ 身份證，汽車牌號，電話號碼，條形代碼 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于記錄。 一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成，相當(dāng)于域。 數(shù)據(jù)對象

2、：性質(zhì)相同的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)：相互之間存在特定關(guān)系的數(shù)據(jù)集合。 四種結(jié)構(gòu)形式：集合、線性、樹形、圖(網(wǎng))狀 形式定義：(D，S，P) D：數(shù)據(jù)元素的集合(數(shù)據(jù)對象) S：D上關(guān)系的有限集 P：D上的基本操作集 邏輯結(jié)構(gòu)：關(guān)系S描述的是數(shù)據(jù)元素之間的邏輯關(guān)系。存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計算機中的存儲形式。 順序映象、非順序映象、索引存儲、哈希存儲邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系： 邏輯結(jié)構(gòu)：描述、理解問題，面向問題。 存儲結(jié)構(gòu)：便于機器運算，面向機器。程序設(shè)計中的基本問題：邏輯結(jié)構(gòu)如何轉(zhuǎn)換為存儲結(jié)構(gòu)？二、有關(guān)數(shù)據(jù)類型的概念數(shù)據(jù)類型：值的集合和定義在該值集上的一組操作的總稱。 包括：原子類型、結(jié)構(gòu)類型

3、。抽象數(shù)據(jù)類型(ADT)：一個數(shù)學(xué)模型及該模型上的一組操作。 核心：是邏輯特性，而非具體表示、實現(xiàn)。課程任務(wù)：學(xué)習(xí)ADT、實踐ADT。如：線性表類型、棧類型、隊列類型、數(shù)組類型、廣義表類型、樹類型、圖類型、查找表類型實踐指導(dǎo)：為了代碼的復(fù)用性，采用模塊結(jié)構(gòu)。 如：C中的頭文件、C+中的類第三節(jié) ADT的表示與實現(xiàn)本教材中，算法書寫習(xí)慣的約定。數(shù)據(jù)元素類型ElemType：int,float,char, char 引用參數(shù) &算法：void add(int a,int b,int &c) c=a+b; 程序：void add(int a,int b,int *p_c) *p_c=a+b; 第四節(jié)

4、 算法的描述及分析一、有關(guān)算法的概念 算法：特定問題求解步驟的一種描述。 1)有窮性 2)確定性 3)可行性二、算法設(shè)計的要求好算法：1)正確性2)可讀性3)健壯性4)高效，低存儲三、時間復(fù)雜度 事前估算：問題的規(guī)模，語言的效率，機器的速度 時間復(fù)雜度：在指定的規(guī)模下，基本操作重復(fù)執(zhí)行的次數(shù)。 n：問題的規(guī)模。f(n)：基本操作執(zhí)行的次數(shù) T(n)=O(f(n) 漸進時間復(fù)雜度(時間復(fù)雜度)例：求兩個方陣的乘積 CA*Bvoid MatrixMul(float an,float bn,float cn) int i,j,k; for(i=0; in; i+) / n+1 for(j=0; jn

5、; j+) / n(n+1) cij=0; / n*n for(k=0; kn; k+) / n*n*(n+1) cij+ = aik * bkj; / n*n*n 時間復(fù)雜度： 一般情況下，對循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，可以忽略循環(huán)體中步長加1、終值判斷、控制轉(zhuǎn)移等成分。 最好/最差/平均時間復(fù)雜度的示例：例：在數(shù)組An中查找值為k的元素。 for(i=0; in-1; i+) if(Ai=k) return i; 四、常見時間復(fù)雜度 按數(shù)量級遞增排序： 將指數(shù)時間算法改進為多項式時間算法：偉大的成就。五、空間復(fù)雜度實現(xiàn)算法所需的輔助存儲空間的大小。S(n)=O(f(n) 按最壞

6、情況分析。六、算法舉例例1：以下程序在數(shù)組中找出最大值和最小值void MaxMin(int A, int n) int max, min, i; max=min=A0; for(i=1; imax) max=Ai; else if(Aimax)：n-1次 if(Aimax)：n-1次 if(Aimin): 0次例2：計算f(x)=a0+a1x+a2x2+anxn解法一：先將x的冪存于power，再分別乘以相應(yīng)系數(shù)。float eval(float coef,int n,float x) float powerMAX, f; int i; for(power0=1,i=1;i=n;i+) po

7、weri=x*poweri-1; for(f=0,i=0;i=0;i-) f=f*x+coefi; return(f);五、思考題1、問：“s=s+i*j;”的執(zhí)行次數(shù)？時間復(fù)雜度？for(i=1;i=n;i+) if(5*i=n)for(j=5*i;j=n;j+) s=s+i*j;2、問：“aij=x;”的執(zhí)行次數(shù)？時間復(fù)雜度？for(i=0; in; i+)for(j=0; j=i; j+) aij=x; 第二章 線性表 線性結(jié)構(gòu)：在數(shù)據(jù)元素的非空集中，存在唯一的一個首元素，存在唯一的一個末元素，除首元素外每個元素均只有一個直接前驅(qū)，除末元素外每個元素均只有一個直接后繼。第一節(jié) 邏輯結(jié)構(gòu)

8、形式定義： Linear_list=(D，S，P) D = ai| aiElemSet, i=0,1,2,n-1 S = | ai-1,aiD, i=1,2,n-1為序偶，表示前后關(guān)系 基本操作P：插入、刪除、修改，存取、遍歷、查找。 void ListAppend(List L, Elem e) ; void ListDelete(List L, int i) ; int SetElem(List L, int i, Elem e); int GetElem(List L, int i, Elem &e); int ListLength(List L); void ListPrint(Lis

9、t L); int LocateElem(List L, Elem e);合并、分解、排序 基本操作的用途：集合的并、交、差運算 有序線性表的合并、多項式的運算 例：利用線性表LA和LB分別表示集合A和B，求A=AB。void union(List &La，List Lb) int La_len, Lb_len; La_len=ListLength(La); / 計算表長 Lb_len=ListLength(Lb); for(i=1; i=i; j-) A.elemj+1 = A.elemj; A.elemi=e; A.length+; 2、刪除ai：a0a1ai-1aiai+1an-1如何移

10、動元素？a0a1ai-1ai+1an-1void SqList_Delete(SqList A, int i) for(j=i+1; jA.length; j+) A.elemj-1 = A.elemj; A.length-;三、效率分析 插入、刪除時，大量時間用在移動元素上。 設(shè)插入位置為等概率事件，時間復(fù)雜度？例1：增序順序表的合并，設(shè)其中無相同元素Status SqList_Merge(SqList La,SqList Lb,SqList &Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; Lc.listsize=Lc.length=La.lengt

11、h+Lb.length; Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) return ERROR; pa=La.elem; pb=Lb.elem; pc=Lc.elem; pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa=pa_last & pb=pb_last) if(*pa=*pb) *pc=*pa; pc+; pa+; else *pc=*pb; pc+; pb+; while(pa=pa_last) *pc=*p

12、a; pc+; pa+; while(pb 1 2 3 4 5 6 7 8 9void del(int A,int n) int i,k; / k是0元素的個數(shù) for(k=0,i=0; inext=p-next; p-next=q; 在*p之前插入？ 時間復(fù)雜度？ 各種插入方法：首插：插入在首結(jié)點前；尾插：入在尾結(jié)點后。有序插：保持結(jié)點的順序，插在表中間； 編程細(xì)節(jié)：首插：修改頭指針尾插：鏈表為空時，修改頭指針。有序插：鏈表為空時，修改頭指針。鏈表不空時，可能修改頭指針/ 首插LNODE * LinkList_InsertBeforeHead(LNODE *head, LNODE *newp

13、) newp-next=head; return(newp); / 遍歷打印void LinkList_Print(LNODE *head) LNODE *p; for(p=head; p; p=p-next) printf(.,p-data);/ 尾插LNODE * LinkList_InsertAfterTail(LNODE *head, LNODE *newp) LNODE *p; if(head=NULL) newp-next=NULL; return(newp); for(p=head-next; p-next; p=p-next); newp-next=NULL; p-next=p

14、; return(head); 簡化程序細(xì)節(jié)的方法：特殊頭結(jié)點/ 首插（有特殊頭結(jié)點）void LinkList_InsertBeforeHead(LNODE *head, LNODE *newp) newp-next=head-next; head-next=newp;/ 尾插（有特殊頭結(jié)點）void LinkList_InsertAfterTail(LNODE *head, LNODE *newp) LNODE *p; for(p=head; p-next; p=p-next); newp-next=NULL; p-next=p; 2、刪除結(jié)點 刪除*p的后繼結(jié)點： q=p-next; p

15、-next=q-next; free(q); 刪除*p？ 時間復(fù)雜度？ 各種刪除方法：首刪除： 尾刪除： 思考查找刪除：思考/ 首刪除（有特殊頭結(jié)點）void LinkList_DeleteHead(LNODE *head) LNODE *p; if(head-next=NULL) return; p=head-next; head-next=p-next; free(q);三、單個鏈表的例程（設(shè)以下鏈表有特殊頭結(jié)點）例1、按序號查找：取鏈表第i個結(jié)點的數(shù)據(jù)元素。i1,n/ 注意計數(shù)次數(shù)的邊界條件Status LinkList_GetElemBySID(LNODE *head,int i,El

16、emType &e) LNODE *p; int j;for(p=head-next,j=1; p & jnext; if(p=NULL) return ERROR; e=p-data; return OK;例2、按值查找：取鏈表中值為e的結(jié)點的地址。LNODE * LinkList_GetElemByValue(LNODE *head, ElemType e) LNODE *p; for(p=head-next; p; p=p-next)if(p-data=e) break; return(p);例3、釋放鏈表中所有結(jié)點。void LinkList_DeleteAll(LNODE *head

17、) LNODE *p; while(head) p=head-next; free(head); head=p; 例4、復(fù)制線性鏈表的結(jié)點/ 適合有/無特殊頭結(jié)點的鏈表LNODE * LinkList_Copy(LNODE *L) LNODE *head=NULL,*p,*newp,*tail; if(!L) return(NULL); for(p=L; p; p=p-next) newp=(LNODE *)malloc(sizeof(LNODE); if(head=NULL) head=tail=newp; else tail-next=newp; tail=newp; newp-data=

18、p-data; tail-next=NULL; return(head);例5、線性鏈表的逆序LNODE * LinkList_Reverse(LNODE *head) LNODE *newhead,*p;newhead=(LNODE *)malloc(sizeof(LNODE);newhead-next=NULL; while(head-next!=NULL) p=head-next; head-next=p-next; /卸下 p-next=newhead-next; newhead-next=p; /安裝 free(Head); return(newhead);例6、利用線性表的基本運算

19、，實現(xiàn)清除L中多余的重復(fù)節(jié)點。 3 5 2 5 5 5 3 5 6= 3 5 2 6void LinkList_Purge(LNODE *head) LNODE *p, *q, *prev_q; for(p=head-next; p; p=p-next) for(prev_q=p,q=p-next; q; ) if(p-data=q-data) prev_q=q-next; free(q); q=prev_q-next; else prev_q=q; q=q-next; 四、多個鏈表之間的例程（設(shè)以下鏈表有特殊頭結(jié)點）例1、增序線性鏈表的合并，設(shè)其中無相同元素。/破壞La和Lb，用La和Lb的

20、結(jié)點組合LcLNODE *LinkList_Merge(LNODE *La,LNODE *Lb) LNode *pa,*pb,*pctail,*Lc;Lc=pctail=La; / Lc的頭結(jié)點是原La的頭結(jié)點pa=La-next; pb=Lb-next; free(Lb); while(pa!=NULL & pb!=NULL) if(pa-data data) pctail-next=pa; pctail=pa; pa=pa-next; else pctail-next=pb; pctail=pb; pb=pb-next; if(pa!=NULL) pctail-next=pa; else

21、pctail-next=pb; return(Lc);例2、無序線性鏈表的交集AB/不破壞La和Lb，/新鏈表Lc的形成方法：向尾結(jié)點后添加結(jié)點 LNODE *LinkList_Intersection(LNODE *La,LNODE *Lb) LNode *pa,*pb,*Lc,*newp,*pctail;Lc=pctail=(LNODE *)malloc(sizeof(LNODE); for(pa=La-next; pa; pa=pa-next) for(pb=Lb-next; pb; pb=pb-next)if(pb-data=pa-data) break;if(pb) newp=(LN

22、ODE *)malloc(sizeof(LNODE); newp-data=pa-data; pctail-next=newp; pctail=newp;pctail-next=NULL; return(Lc);作業(yè)與上機：(選一)1、A-B2、AB3、AB4、(A-B)(B-A)第五節(jié) 循環(huán)鏈表 尾結(jié)點的指針域指向首結(jié)點。 實際應(yīng)用：手機菜單 遍歷的終止條件？例：La、Lb鏈表的合并 / 將Lb鏈表中的數(shù)據(jù)結(jié)點接在La鏈表末尾void Connect(LNODE * La，LNODE * Lb) LNODE *pa, *pb;for(pa=La-next; pa-next!=La; pa=p

23、a-next);for(pb=Lb-next; pb-next!=Lb; pb=pb-next); pa-next=Lb-next; pb-next=La; free(Lb);第六節(jié) 雙向鏈表 非空表 空表 typedef struct DuLNode ElemType data; struct DuLNode *lLink, *rLink;DuLinkNode;1、在*p之后插入結(jié)點*q q-rLink=p-rLink; q-lLink=p; p-rLink=q; q-rLink-lLink=q 在*p之前插入結(jié)點*q ?2、刪除*p (p-lLink)-rLink=p-rLink; (p-

24、rLink)-lLink=p-lLink; free(p); 刪除*p的前驅(qū)結(jié)點? 刪除*p的后繼結(jié)點?第七節(jié) 實例：一元多項式的存儲、運算多項式的存儲結(jié)構(gòu) f(x) = anxn +a2x2 + a1x + a01、順序結(jié)構(gòu) int coefMAX;f(x) = 14x101+ 5x50 - 32、鏈?zhǔn)浇Y(jié)構(gòu)typedef struct polynode int coef; int index; struct node *next;PolyNode;3、示例輸入數(shù)據(jù)（指數(shù)無序）輸出多項式(指數(shù)降序)多項式1多項式2count=2coef=5,index=3coef=1,index=5count

25、=3coef=2,index=7coef=7,index=2coef=6,index=3count=4coef=2,index=7coef=1,index=5coef=11,index=3coef=7,index=24、結(jié)構(gòu)細(xì)節(jié)設(shè)計帶特殊頭結(jié)點的單向鏈表； 結(jié)點按指數(shù)降序排列；特殊頭結(jié)點的index域：多項式的項數(shù)。5、程序框架設(shè)計main() PolyNode *L1,*L2; L1=PolyNode_Create(); PolyNode_Print(L1); L2=PolyNode_Create(); PolyNode_Print(L2); PolyNode_Add(L1,L2); / L

26、1+L2=L1 PolyNode_Print(L1);void PolyNode_Print(PolyNode *head) PolyNode *p; printf(count=%dn,head-index); /打印項數(shù) for(p=head-next; p; p=p-next) printf(coef=%d,index=%dn,p-coef, p-index);二、以插入為基礎(chǔ)的算法1、將*newp插入到降序鏈表*head中void PolyNode_Insert(PolyNode *head, PolyNode *newp); PolyNode *p,*pre;/ 定位for(pre=h

27、ead,p=pre-next; p; pre=p,p=p-next) if(p-index index) break;if(p=NULL | p-index index) /在*pre之后插入 newp-next=p; pre-next=newp; head-index+; else p-coef += newp-coef; /合并同類項 free(newp); if(p-coef=0) /刪除 pre-next=p-next; free(p); head-index-; 2、利用PolyNode_Insert函數(shù)，建立有序鏈表PolyNode *PolyNode_Create() int i

28、,count; PolyNode *head,*newp; scanf(%dn,&count); head=(PolyNode *)malloc(sizeof(PolyNode); head-coef=0; head-next=NULL; for(i=0; icoef,&newp-index); PolyNode_Insert(head, newp); return(head);3、利用PolyNode_Insert函數(shù)，實現(xiàn)多項式加法/ L1+L2=L1 不破壞L2鏈表 void PolyNode_Add(PolyNode *L1, PolyNode *L2) NODE *p,*newp;

29、for(p=L2-next; p; p=p-next) newp=(PolyNode *)malloc(sizeof(PolyNode); newp-coef=p-coef; newp-index=p-index; PolyNode_Insert(L1,newp); 時間復(fù)雜度？設(shè)L1長度為M，L2長度為N，則O(M*N)。三、兩表合并算法L1+L2=L1 破壞L2鏈表 將L2中的每個結(jié)點卸下，合并到L1中void PolyNode_Add(PolyNode *L1, PolyNode *L2) PolyNode *p1, *p1pre; / *p1pre 是*p1的直接前驅(qū) PolyNode

30、 *p2, *p2next; / *p2next是*p2的直接后繼 p1pre=L1; p1=L1-next; / p1指向L1中第一個數(shù)據(jù)結(jié)點 p2=L2-next; free(L2); / p2指向L2中第一個數(shù)據(jù)結(jié)點 while(p1 & p2) switch(compare(p1-index, p2-index) case : / *p1指數(shù)大于*p2指數(shù) p1pre=p1; p1=p1-next; break; case next; / 小心：準(zhǔn)備在*p1pre后插入*p2 p2-next=p1; p1pre-next=p2; p1pre=p2; / 小心：保持p1pre和p1的關(guān)系

31、 p2=p2next; / p2指向下一個待合并的結(jié)點 break; case =: / *p1和*p2是同類項 p1-coef+=p2-coef; / 系數(shù)合并 p2next=p2-next; free(p2); / 刪除*p2 p2=p2next; / p2指向下一個待合并的結(jié)點 if(pa-coef=0) / 合并后系數(shù)為0 p1pre-next=p1-next; free(p1); / 刪除*p1 p1=p1pre-next; / 保持p1pre和p1的關(guān)系 / switch / while if(p2) p1pre-next=p2; / 鏈上p2的剩余結(jié)點時間復(fù)雜度？設(shè)L1長度為M，

32、L2長度為N，則O(M+N)。作業(yè)與上機：(選一) 一、多項式加法、減法 二、多項式乘法:a*b=c(建立新表c) 三、任意整數(shù)的加法、乘法第三章 棧與隊列棧與隊列：限定操作的線性表。第一節(jié) 棧一、邏輯結(jié)構(gòu)1、棧的定義限定只能在表的一端進行插入、刪除的線性表。棧頂top，棧底bottom。后進先出LIFO表(Last In First Out)實例：“進制數(shù)轉(zhuǎn)換”、“表達式求值”、“函數(shù)調(diào)用關(guān)系”、“括號匹配問題”、“漢諾塔問題”、“迷宮問題” 2、基本操作進棧Push/出棧Pop取棧頂元素GetTop判別棧空StackEmpty/棧滿StackFull3、棧的應(yīng)用背景許多問題的求解分為若干步

33、驟，而當(dāng)前步驟的解答，是建立在后繼步驟的解答基礎(chǔ)上的。=問題分解的步驟和求解的步驟次序恰好相反。二、順序存儲結(jié)構(gòu)動態(tài)順序存儲結(jié)構(gòu)：存儲空間隨棧的大小而變化。#define STACK_INIT_SIZE 100 /初始化時分配的空間typedef struct /定義棧類型 ElemType *base,*top; /棧底、棧頂指針 int stacksize; /棧的存儲空間大小SqStack; SqStack S; /定義一個棧結(jié)構(gòu)1、初始化棧Status SqStack_Init(SqStack &S) S.base=malloc(STACK_INIT_SIZE*sizeof(ElemT

34、ype); if(!S.base) return(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return(OK);?？眨?S.top=S.base棧滿： S.top=S.base+S.stacksize2、進棧Status SqStack_Push(SqStack &S,ElemType e) if(S.top=S.base+S.stacksize) return(OVERFLOW); S.top=e; S.top+; return(OK);3、出棧算法Status SqStack_Pop(SqStack &S,ElemType

35、 &e) if(S.top=S.base) return(UNDERFLOW); S.top-; e=S.top; return(OK);缺點：空間浪費思考：二棧合用同一順序空間？ #define maxsize=100int stackmaxsize, top0=0, top1=maxsize-1;int push0(int e) if(top0 top1) return(0); stacktop0=e; top0+; return(1);int push1(int e) if(top0 top1) return(0); stacktop1=e; top1-; return(1);int p

36、op0(int *e) if(top0=0) return(0); top0-; *e=stacktop0; return(1);int pop1(int *e) if(top0=0) return(0); top0+; *e=stacktop1; return(1);三、鏈棧typedef struct linknode / 棧中結(jié)點類型 ElemType data; struct linknode *link; LinkNode;typedef struct / 定義棧類型 LinkNode *top; / 棧頂指針 int stacksize; / 棧的大小(可選)LinkStack;

37、LinkStack S; 初始化: S.top=NULL; S.stacksize=0棧 空：S.top=NULL棧 滿：系統(tǒng)內(nèi)存不夠1、進棧Status LinkStack_Push(LinkStack &S，ElemType e) LinkNode *p;p=(LinkNode *)malloc(sizeof(LinkNode);if(p=NULL) return(OVERFLOW); /上溢 p-data=e; p-link=S.top; S.top=p;return(OK); 2、出棧Status LinkStack_Pop(LinkStack &S,ElemType &e) Link

38、Node *p;if(S.top=NULL) return(UNDERFLOW); p=S.top; e=S.top-data; S.top=S.top-link; free(p); return(OK); 3、特殊頭結(jié)點的討論進棧、出棧是最常用的操作=鏈棧的頭指針頻繁變更=參數(shù)傳遞的負(fù)擔(dān)=應(yīng)約定鏈棧具有特殊頭結(jié)點。第二節(jié) 棧的應(yīng)用1、函數(shù)調(diào)用棧 f(n)=f(n-1)+f(n-2)int f(int n) int x,y; if(n=1 | n=2) return(1); x=f(n-1); y=f(n-2); return(x+y); main() printf(%dn,f(5); 2、將

39、十進制數(shù)轉(zhuǎn)換為八進制數(shù)。例如 (1348)10=(2504)8，除8取余的過程：nn / 8n mod 8134816841682102125202void Conversion(int dec,int oct) InitStack(S); for(; dec!=0; dec=dec/8) push(S, dec%8); /* 進棧次序是個位、十位. */ for(i=0; !StackEmpty(S); i+) octi=pop(S); /* 先出棧者是高位，最后是個位 */3、括號匹配的檢驗Equal( (a)(b) ) : 0Equal( (a)(b) ) : 1Equal( (a)(b

40、) ) : -1int Equal(char s) int i=0; for(i=0; si; i+) switch(si) case (: push(si); break; case ): if(StackEmpty(S) return(-1); / )多 pop(); break; if(!StackEmpty(S) return(1); / (多 return(0); / 完全匹配4、進棧出棧的組合問題 已知操作次序：push(1); pop(); push(2); push(3); pop(); pop( ); push(4); pop( ); 請寫出出棧序列。5、中綴表達式求值的算法

41、如： 1 + 2 *（3 + 4 *（5 + 6）分析：先乘除，后加減；從左到右；先括號內(nèi)，再括號外。后算符前算符()#(#=一個運算是否立即執(zhí)行？必須和“上一個運算符”比較優(yōu)先級。 3 * 5 + 2 3 - 5 * 2 + 8“上一個運算符”存于何處？ 運算符棧對應(yīng)的運算數(shù)存于何處？ 運算數(shù)棧為保證第一個運算符有“上一個運算符”： Push(OPTR,#)為保證最后一個運算符能被執(zhí)行： 3*5+2#：優(yōu)先級最低的運算符。運算結(jié)果：運算數(shù)棧最后的元素。跟蹤示例：3*(7-2)#c=3C=*c=(c=7c=-c=2C=)c=)c=#charStack： 類型定義： 基本函數(shù)：InitStack

42、1(charStack *); char GetTop1(charStack *); void Push1(charStack *, char); char Pop1(charStack *); intStack:類型定義： 基本函數(shù)：InitStack2(intStack *); int GetTop2 (intStack *); void Push2(intStack *, int); int Pop2(intStack *); float MidExpression_Eval(char Express) / Express:3*5+2# int i=0; char c,pre_op; c

43、harStack OPTR; intStack OPND;InitStack1(&OPTR); Push1(&OPTR,#); /* 運算符棧 */ InitStack2(&OPND); /* 運算數(shù)棧 */ while(Expressi!=# | GetTop1(&OPTR)!=#) c=Expressi; if(!InOPTR(c) Push2(&OPND, c-0); i+; /* getnum(Express,&i) */ else pre_op=GetTop1(&OPTR); switch(Precede(pre_op, c) case : / pre_op : / pre_op c

44、 執(zhí)行pre_op b=Pop2(&OPND); a=Pop2(&OPND); Pop1(&OPTR); Push2(&OPND,Operate(a,pre_op,b); return(GetTop2(&OPND); / 優(yōu)先級的處理技巧 + - * / ( ) #int priority77=, , , , , , / + , , , , , , / - , , , , , , / * , , , , , , / / , , , , , , , , , , , / ) , , , , data=e; p-link=NULL; if(Q.front=NULL) Q.front=Q.rear=p

45、; else Q.rear-link=p; Q.rear=p; return(OK);2、出隊列Status LinkQueue_Leave(LinkQueue &Q,ElemType &e) QueueNode *p;if(Q.front=NULL) return(UNDERFLOW); p=Q.front; Q.front=p-link; if(Q.rear=p) Q.rear=NULL; e=p-data; free(p); return(OK); 3、銷毀隊列void LinkQueue_Destroy(LinkQueue &Q) QueueNode *p; while(Q.front

46、) p=Q.front; Q.front=p-link; free(p); Q.rear=NULL;三、順序存儲結(jié)構(gòu)動態(tài)順序存儲結(jié)構(gòu)：#define QUEUE_SIZE 100 /初始化時分配的空間typedef struct ElemType *base; /存儲空間的起始地址int front,rear; SqQueue; SqQueue Q; /定義一個隊列結(jié)構(gòu)rear為下一個進隊列元素的位置。front在隊列不空時，指向首元素；在隊列為空時，等于rear。1、初始化隊列Status SqQueue_Init(SqQueue &Q) Q.base=malloc(QUEUE_SIZE*s

47、izeof(ElemType); if(!Q.base) return(OVERFLOW);Q.front=Q.rear=0; return(OK);隊列空： Q.front=Q.rear進隊列：*(Q.base+Q.rear)=e; Q.rear+; 出隊列：e=*(Q.base+Q.front); Q.front+; 隊列滿： Q.rear=QUEUE_SIZE =假溢出進隊列：Q.rear =(Q.rear +1) % QUEUE_SIZE出隊列：Q.front=(Q.front+1) % QUEUE_SIZE隊列空：Q.front=Q.rear當(dāng)隊列中有QUEUE_SIZE個元素時：

48、Q.front=Q.rear=必須浪費一個結(jié)點空間隊列滿：(Q.rear +1) % QUEUE_SIZE = Q.front2、入隊列Status SqQueue_Enter(SqQueue &Q,ElemType e) if(Q.rear +1) % QUEUE_SIZE=Q.front) return(OVERFLOW); *(Q.base+Q.rear)=e;Q.rear=(Q.rear +1) % QUEUE_SIZE; return(OK); 3、出隊列Status SqQueue_Leave(SqQueue &Q,ElemType &e) if(Q.rear=Q.front) r

49、eturn(UNDERFLOW); e=*(Q.base+Q.front); Q.front=(Q.front+1) % QUEUE_SIZE; return(OK);4、元素計數(shù)(Q.rear-Q.front+QUEUE_SIZE)% QUEUE_SIZE值的范圍0 QUEUE_SIZE-1思考：一定要浪費一個結(jié)點空間？利用一個標(biāo)志變量Q.flag (0:非滿，1:非空)。typedef struct ElemType dataM; int front,rear; int flag; SqQueue; int Empty(SqQueue Q) if(Q.front=Q.rear & Q.fl

50、ag=0) return(1); return(0);int Full(SqQueue Q) if(Q.front=Q.rear & Q.flag=1) return(1); return(0);1、初始化隊列Status SqQueue_Init(SqQueue &Q) Q.front=Q.rear=0; Q.flag=0; 2、入隊列Status SqQueue_Enter(SqQueue &Q,ElemType e) if(Full(Q) return(OVERFLOW); Q.flag=1; /非空 return(OK); 3、出隊列Status SqQueue_Leave(SqQue

51、ue &Q,ElemType &e) if(Empty(Q) return(UNDERFLOW); ;Q.flag=0; /非滿return(OK);第四節(jié) 隊列的實例：離散事件的模擬一、排隊問題加油站的問題：一個加油站只有一臺加油機,平均為每輛車加油需要5分鐘,假定一個小時內(nèi),有20輛車隨機進入加油站加油,計算每輛車的平均等待時間.銀行營業(yè)所應(yīng)設(shè)置幾個柜臺？1、設(shè)置N柜臺時，計算顧客的平均等待時間；2、選擇合適的N值。二、兩個棧組合出一個隊列制定兩個棧與一個隊列的對應(yīng)規(guī)則：S2S1a0,ai進隊列a0出隊列ai+1,an-1進隊列a1,ai出隊列ai+1出隊列stack s1,s2;void

52、 Enter(ElemType e) Push(s1,e); ElemType Leave() ElemType e; if( !Empty(s2) ) return( Pop(s2) ); while( !Empty(s1) ) Push(s2, Pop(s1); return( Pop(s2) );第四章 串串：限定數(shù)據(jù)元素類型的線性表。應(yīng)用實例： 編輯軟件(本質(zhì)上是字符串處理)信息檢索、病毒查找(字符串比較)第一節(jié) 邏輯結(jié)構(gòu)一、定義串是由字符組成的線性表。 STRING=(D，S，P) D = ai| aiCHARACTER(字符集), i=0,1,2,n-1 ASCII碼串: CHAR

53、ACTER為ASCII碼字符集。位串：CHARACTER=0,1 S = | ai-1,aiD, i=1,2,n-1a0a1an-1的長度為n?？沾洪L度為0。 子串：串中任意個連續(xù)字符組成的子序列。 兩串相等：兩串長度相等，對應(yīng)的每個字符相等。例：根據(jù)字符串比較運算的定義，完善該函數(shù)： int strcmp(char s , char t ) int i; for (i=0; si & ti; i+) if (si!=ti) ; ; 二、基本運算 線性表注重單個元素的操作串注重整體或部分整體的操作賦值 StrAssign(&S,T) 判斷 StrEmpty(S) StrComp(S,T)求長

54、度 StrLen(S) 聯(lián)接 Concat(&T,S1,S2)求子串 SubStr(&Sub,S,pos,len)子串定位Index(S,T,pos) 替換 Replace(&S,T,V) 插入 StrInsert(&S,pos,T)刪除 StrDelete(&S,pos,len)釋放 DestroyString(&S)第二節(jié) 存儲結(jié)構(gòu)一、順序存儲串中相鄰的字符存放在內(nèi)存的相鄰單元中。靜態(tài)順序結(jié)構(gòu)：typedef char StringMAXSIZE+1;動態(tài)順序結(jié)構(gòu)之一：typedef struct char *ch; /起始地址 int length; /串長String;動態(tài)順序結(jié)構(gòu)之二

55、：typedef struct / C語言的約定 char *ch; /起始地址，結(jié)束標(biāo)記符String;優(yōu)點：訪問子串方便，缺點：空間大小不靈活，插入、刪除費時。二、鏈?zhǔn)酱鎯θ绾卧O(shè)置結(jié)點的大??？ 一個結(jié)點存儲1個字符：非緊縮格式。 空間浪費，操作簡單。一個結(jié)點存儲多個字符：緊縮格式。 空間效率高，操作復(fù)雜。/ 緊縮格式的塊結(jié)構(gòu)#define CHUNKSIZE 80typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;CHUNK;typedef struct CHUNK *head,*tail; int length; /串的長度

56、LString;如何在緊縮格式的鏈串中插入、刪除？第四章 串第三節(jié) 模式匹配模式匹配Index(S, T, pos)主串S中尋找模式串T的起始位置。pos是主串中進行模式匹配的起始位置。Index(abcdef,cde)：2Index(abcdef,ab) ：0Index(abcdef,ad) ：-1一、BF算法(Brute-Force)主 串S=s0s1.sm-1模式串T=t0t1.tn-1匹配過程：si=tj時：i+; j+;sitj時：如何回溯？ t0 t1 . tj-1 tj . = = = . si-j si-j+1 . si-1 si . =i=i-j+1; j=0;匹配結(jié)果：tj

57、=0: 成功，返回S中的起始位置。 t0 . tj-2 tj-1 tj 此時j=n = = = =.si-j . si-2 si-1 si . 起始位置=i-jtj!=0: 失敗，返回-1。int index_BF(char s,char t) int i=0,j=0; while(si & tj) if(si=tj) i+; j+; else i=i-j+1; j=0; if(tj=0) return(i-j); else return(-1);問題分析：S=aaaaaaaaaaaaaaab 長度為m T=aaaab 長度為n回溯次數(shù)=m-n最差時間復(fù)雜度：O(m-n)*n) O(n*m)再

58、例：S=abcabcabcde T=abcabcd 二、KMP算法(Knuth等3人)Donald E. Knuth在算法分析和編程語言設(shè)計方面有杰出貢獻，著作有art of computer programming。獲1974年圖靈獎。1、推導(dǎo)琢磨模式串的內(nèi)在規(guī)律，使得：在sitj時，i不回溯，j適當(dāng)回溯，再重新比較。 當(dāng)sitj時，i不變，j=k。 求k=？ (kj)此時有： t0t1.tj-1=si-j.si-1 t0 t1 . tj-k tj-k+1 . tj-1 tj = = . = = . = si-j si-j+1 . si-k si-k+1 . si-1 si = = . =

59、? t0 t1 . tk-1 tk顯然，k應(yīng)具有性質(zhì)：t0t1.tk-1=si-k.si-1=tj-ktj-k+1.tj-1 即：t0t1.tk-1=tj-ktj-k+1.tj-1即：當(dāng)tj與si失配時，由于tj的前k個字符等于模式串的開頭k個字符,所以可將si與tK比較。為達到更高效率，k越大越好。(kj)2、next每個tj與對應(yīng)一個k值，所以設(shè)立next存儲所有k值。 計算方法：1、j=0時：nextj=-1;2、存在t0t1.tk-1=tj-ktj-k+1.tj-1，(kj)：例如：t0=tj-1 t0t1=tj-2tj-1 t0t1t2=tj-3tj-2tj-1nextj=max(k

60、)。 3、否則：nextj=0;3、KMP程序/預(yù)先求出nextint index_kmp(char s,char t,int next) int i=0, j=0; while(si & tj) if(j=-1 | si=tj) i+; j+; else j=nextj; if(tj=0) return(i-j); else return(-1); 體會j=-1 體會j=nextj 例1： a b c a b c d -1 0 0 0 1 2 3 a b c a b c a b c d e a b c a b c d匹配過程i=6i=6i=7i=8i=9i=10j=6j=3j=4j=5j=6