《數(shù)據(jù)結(jié)構(gòu)及其算法》PPT課件

1、數(shù)據(jù)結(jié)構(gòu)及其算法http:/ 東信息學院6系中國科學技術(shù)大學Data Structure and Algorithm選學內(nèi)容第3章：靜態(tài)鏈表第4章：N皇后問題、用隊列打印楊輝三角第5章：模式匹配2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第3章 線性表2當程序不允許動態(tài)分配內(nèi)存時，如何實現(xiàn)鏈表？ 有些高級語言(如Java)不提供指針3.4.2 靜態(tài)鏈表靜態(tài)鏈表：以預(yù)分配內(nèi)存的相對地址（數(shù)組下標）替代絕對地址（指針）而實現(xiàn)的鏈表靜態(tài)鏈表中如何管理內(nèi)存？ 方案1：附設(shè)bool數(shù)組，記錄預(yù)分配內(nèi)存是否已被占用 方案2：附設(shè)另一個靜態(tài)鏈表，管理尚未被占用的內(nèi)存2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第3章 線

2、性表3數(shù)組下標數(shù)據(jù)域指針域0212zhao43zhou84qian65li36sun57zheng98wu79wang-110靜態(tài)鏈表的實現(xiàn)靜態(tài)鏈表的實現(xiàn)結(jié)點靜態(tài)鏈表2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第3章 線性表4typedef struct ElemType data; / 數(shù)據(jù)域 int next; / 指針域 SLNode;typedef struct SLNode *space; / 預(yù)分配內(nèi)存 int listsize; / 預(yù)分配內(nèi)存大?。p去1） int head; / 鏈表的頭指針（鏈表中有頭結(jié)點） int freespace; / 空閑內(nèi)存的頭指針 SLinkList;

3、2 3 5 8 4 6 102 5 9 8 4 6 10插入9、刪除3 0 0 1 1 2 2 2 3 3 3 5 4 4 8 5 5 4 6 6 6 7 7 10 -1 8 0 9 9 0 1010 0 -1headfreespace 0 0 1 1 2 3 2 3 9 3 5 8 4 8 5 5 4 6 6 6 7 7 10 -1 8 9 4 9 0 1010 0 -1headfreespace靜態(tài)鏈表插入元素2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第3章 線性表5void ListInsert_SL(SLinkList &L, int i, ElemType e) int s =

4、L.freespace; if (s = -1) ErrorMsg(List is full); L.freespace = L.spaces.next; L.spaces.data = e; int q = L.head; int j = 0; while (q != -1 & j i-1) ErrorMsg(Invalid i value); L.spaces.next = L.spaceq.next; L.spaceq.next = s;例：N皇后問題 國際象棋中的“后”可以吃掉與她同一行、同一列、同一對角線的棋子，如何在NN的棋盤擺上N個皇后，使得她們彼此吃不到對方？典型算法：

5、試探-回溯法2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第4章 棧和隊列6思路： 逐行試探，先在第一行擺一個，再在第二行擺一個， N行全部擺好，說明找到一種解法 如果某一行無法擺放，說明之前行的擺法不可行，退回到上一行重新擺放數(shù)據(jù)結(jié)構(gòu)： 采用棧記錄皇后擺放位置，以便回溯 附設(shè)列、左下對角線、右下對角線三個數(shù)組防止皇后沖突2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第4章 棧和隊列7void queen(int N) / 使用棧求解N皇后問題 bool *A = new boolN, *B = new bool2*N-1, *C = new bool2*N-1; for (int i=0; iN; +i)

6、Ai = false; for (int i=0; i2*N-1; +i) Bi = false; for (int i=0; i2*N-1; +i) Ci = false; Stack S; InitStack(S); int sj = 0; while (true) int i = StackLength(S); bool feasible = false; if (i N) for (int j = sj; j N; +j) if (place(i, j, N, A, B, C) mark(i, j, N, true, A, B, C); Push(S, j); if (i = N-1)

7、 print(S); return; feasible = true; break; if (!feasible) int j; if (!Pop(S, j) break; mark(i-1, j, N, false, A, B, C); sj = j+1; else sj = 0; bool place(int i, int j, int N, bool *A, bool *B, bool *C) return !(Aj | Bi+j | Ci-j+N-1);void mark(int i, int j, int N, bool flag, bool *A, bool *B, bool *C

8、) Aj = Bi+j = Ci-j+N-1 = flag;思考：如何對程序進行修改以找出所有的解？算法4.32 N皇后問題的遞歸算法2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第4章 棧和隊列8void queen_recur(int i, int N, bool *A, bool *B, bool *C, int *result) for (int j = 0; j N; +j) if (place(i, j, A, B, C) mark(i, j, true, A, B, C); resulti = j; if (i=N-1) for (int k=0; kN; +k) cout result

9、k ; cout endl; else queen_recur(i+1, N, A, B, C, result); mark(i, j, false, A, B, C); void queen2(int N) / 遞歸算法求解N皇后問題 bool *A = new boolN, *B = new bool2*N-1, *C = new bool2*N-1; for (int i=0; iN; +i) Ai = false; for (int i=0; i2*N-1; +i) Bi = false; for (int i=0; i2*N-1; +i) Ci = false; int *res =

10、 new intN; queen_recur(0, N, A, B, C, res);思考：對比前頁算法，修改程序找出第一組解就返回4.6 隊列的應(yīng)用例：打印二項式系數(shù)常規(guī)算法（使用兩個輔助數(shù)組）2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第4章 棧和隊列9void yanghui(int n) int *k_line = new intn+1, *kp_line = new intn+1; k_line0 = 1; k_line1 = 1; int k = 1; while (k = n) for (int i=0; in-k; +i) cout ; for (int i=0; ik+1; +i)

11、 cout k_linei ; cout endl; if (k = n) break; kp_line0 = 1; for (int i=1; ik+1; +i) kp_linei = k_linei-1 + k_linei; kp_linek+1 = 1; int *p = kp_line; kp_line = k_line; k_line = p; +k; 算法4.27（使用隊列）2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第4章 棧和隊列10void yanghui_queue(int n) SqQueue Q; InitQueue_sq(Q, n+3); EnQueue_sq(Q, 0);

12、 EnQueue_sq(Q, 1); EnQueue_sq(Q, 1); int k = 1; int s, e; while (k n) for (int i=0; in-k; +i) cout ; EnQueue_sq(Q, 0); do DeQueue_sq(Q, s); GetHead_sq(Q, e); if (e) cout e ; else cout 0) DeQueue_sq(Q, e); cout e ; cout endl;5.4 模式匹配蠻力(brute-force)法算法分析：設(shè)子串長度為m，主串長度為n，則BF算法復(fù)雜度為O(mn)2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法

13、 第5章 串和數(shù)組11int index_BF(char *S, char *P, int start) if (start strlen(S) - strlen(P) ErrorMsg(Input error); int i=start, j=0; while (istrlen(S) & jstrlen(P) if (Si = Pj) +i; +j; else i=i-j+1; j=0; if (j=strlen(P) return (i-j); else return -1;改進算法 子串一般較短，能否對子串進行預(yù)先分析？ 發(fā)生失配時，能否“重用”之前計算的結(jié)果？2021-12-1

14、3數(shù)據(jù)結(jié)構(gòu)及其算法 第5章 串和數(shù)組12主串S：a b c a b c a b c d子串P：a b c a b c d a b c a b c d a b c a b c d a b c a b c d首次失配，i=6,j=6，表明S0.5=P0.5,S6!=P6BF算法將子串右移1位，S1.=P0.？對子串預(yù)先分析可發(fā)現(xiàn)P0!=P1，而P1=S1，故不可能匹配BF算法將子串右移2位，S2.=P0.？同理，不可能匹配BF算法將子串右移3位，S3.=P0.？對子串預(yù)先分析可發(fā)現(xiàn)P0.2=P3.5，則S6.=P3.？因為P3!=P6，則從i=6,j=3開始KMP(Knuth-Morris-Pra

15、tt)算法 發(fā)生失配時，設(shè)Si!=Pj，則必有：Si-j.i-1=P0.j-1且Si!=Pj 如果我們預(yù)先分析子串，并找到：P0.k-1=Pj-k.j-1且Pk!=Pj 則可直接將子串右移并從Si=Pk？開始比較 如果找不到，就從Si+1=P0？開始比較對子串預(yù)先分析就是對每個j，找到一個最大的k(0=kj)使得滿足P0.k-1=Pj-k.j-1且Pk!=Pj，記為k=nextj 約定：如果找不到就令k=-12021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第5章 串和數(shù)組13主串：a b a a b a a b a d子串：a b a a b a dj=6時，k=1滿足條件，但最大的k=3算法5.720

16、21-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第5章 串和數(shù)組14int index_KMP(char *S, char *P, int start) if (start strlen(S) - strlen(P) ErrorMsg(Input error); int *next = new intstrlen(P); get_next(P, next); int i=start, j=0; while (istrlen(S) & jstrlen(P) if (j=-1 | Si = Pj) +i; +j; else j=nextj; if (j=strlen(P) return (i-j); e

17、lse return -1;子串：a a a a b主串：a a a b a a a a b主串：a a a a a a a b求KMP算法中的next數(shù)組樸素算法for(j=0; j=0; -k) if(P0.k-1=Pj-k.j-1&Pk!=Pj) nextj=k; break;高級算法 先求解問題：對每個j，找到一個最大的k(0=kj)使得滿足P0.k-1=Pj-k.j-1且Pk!=Pj，記為k=next1(j) 再求解問題：已知next1(j)如何求next(j)2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第5章 串和數(shù)組15第一步：已知k=next1j，如何求next1j+1證明next1j+1=k+1（反證法）如果Pk=Pj，則next1j+1=k+1如果Pk!=Pj，說明子串在自身匹配時發(fā)生失配，根據(jù)KMP算法，右移至nextk繼續(xù)匹配第二步：已知k=next1j，如何求nextj證明nextj=k（反證法）如果Pk!=Pj，則nextj=k如果Pk=Pj，說明長度為k的匹配不可用，KMP應(yīng)在nextk進行，故nextj=nextk2021-12-13數(shù)據(jù)結(jié)構(gòu)及其算法 第5章 串和數(shù)組16子串：p0 . pk-1 . pj-k . pj-1 pj pj+1子串： p0 . pk-1 pk pk+1算