《数据结构及其算法》PPT课件

1、数据结构及其算法http:/ 东信息学院6系中国科学技术大学Data Structure and Algorithm选学内容第3章：静态链表第4章：N皇后问题、用队列打印杨辉三角第5章：模式匹配2021-12-13数据结构及其算法 第3章 线性表2当程序不允许动态分配内存时，如何实现链表？ 有些高级语言(如Java)不提供指针3.4.2 静态链表静态链表：以预分配内存的相对地址（数组下标）替代绝对地址（指针）而实现的链表静态链表中如何管理内存？ 方案1：附设bool数组，记录预分配内存是否已被占用 方案2：附设另一个静态链表，管理尚未被占用的内存2021-12-13数据结构及其算法 第3章 线

2、性表3数组下标数据域指针域0212zhao43zhou84qian65li36sun57zheng98wu79wang-110静态链表的实现静态链表的实现结点静态链表2021-12-13数据结构及其算法 第3章 线性表4typedef struct ElemType data; / 数据域 int next; / 指针域 SLNode;typedef struct SLNode *space; / 预分配内存 int listsize; / 预分配内存大小（减去1） int head; / 链表的头指针（链表中有头结点） int freespace; / 空闲内存的头指针 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静态链表插入元素2021-12-13数据结构及其算法 第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数据结构及其算法 第4章 栈和队列6思路： 逐行试探，先在第一行摆一个，再在第二行摆一个， N行全部摆好，说明找到一种解法 如果某一行无法摆放，说明之前行的摆法不可行，退回到上一行重新摆放数据结构： 采用栈记录皇后摆放位置，以便回溯 附设列、左下对角线、右下对角线三个数组防止皇后冲突2021-12-13数据结构及其算法 第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数据结构及其算法 第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 队列的应用例：打印二项式系数常规算法（使用两个辅助数组）2021-12-13数据结构及其算法 第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数据结构及其算法 第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)法算法分析：设子串长度为m，主串长度为n，则BF算法复杂度为O(mn)2021-12-13数据结构及其算法

13、 第5章 串和数组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;改进算法 子串一般较短，能否对子串进行预先分析？ 发生失配时，能否“重用”之前计算的结果？2021-12-1

14、3数据结构及其算法 第5章 串和数组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.？对子串预先分析可发现P0!=P1，而P1=S1，故不可能匹配BF算法将子串右移2位，S2.=P0.？同理，不可能匹配BF算法将子串右移3位，S3.=P0.？对子串预先分析可发现P0.2=P3.5，则S6.=P3.？因为P3!=P6，则从i=6,j=3开始KMP(Knuth-Morris-Pra

15、tt)算法 发生失配时，设Si!=Pj，则必有：Si-j.i-1=P0.j-1且Si!=Pj 如果我们预先分析子串，并找到：P0.k-1=Pj-k.j-1且Pk!=Pj 则可直接将子串右移并从Si=Pk？开始比较 如果找不到，就从Si+1=P0？开始比较对子串预先分析就是对每个j，找到一个最大的k(0=kj)使得满足P0.k-1=Pj-k.j-1且Pk!=Pj，记为k=nextj 约定：如果找不到就令k=-12021-12-13数据结构及其算法 第5章 串和数组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数据结构及其算法 第5章 串和数组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数组朴素算法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数据结构及其算法 第5章 串和数组15第一步：已知k=next1j，如何求next1j+1证明next1j+1=k+1（反证法）如果Pk=Pj，则next1j+1=k+1如果Pk!=Pj，说明子串在自身匹配时发生失配，根据KMP算法，右移至nextk继续匹配第二步：已知k=next1j，如何求nextj证明nextj=k（反证法）如果Pk!=Pj，则nextj=k如果Pk=Pj，说明长度为k的匹配不可用，KMP应在nextk进行，故nextj=nextk2021-12-13数据结构及其算法 第5章 串和数组16子串：p0 . pk-1 . pj-k . pj-1 pj pj+1子串： p0 . pk-1 pk pk+1算