对单链表元素置逆 o Node* LinkList reverse(node head Node *Newhead, *p, *nextNode if (head==NULLreturn NULL /空链表 if(head->next==NULL) return head;/仅一个元素 p=head: NewHead=NULL:/初始化 while(p).i nex+Noe=p->next://先记录下一个结点 > next= NewHead;∥/改变链表方向(逆置) behEad 新链表的头为当前结点 p= nextNode //向后推移一个结点 return NewHead //旧链表遍历完毕,直接返回新头 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 对单链表元素置逆 Node* LinkList_reverse(Node* head) { Node *NewHead, *p, *nextNode; if (head==NULL) return NULL; //空链表 if (head->next == NULL) return head; //仅一个元素 p = head; NewHead=NULL; //初始化 while (p) { nextNode = p->next; //先记录下一个结点 p->next = NewHead; //改变链表方向（逆置） NewHead = p; //新链表的头为当前结点 p = nextNode; //向后推移一个结点 } return NewHead; //旧链表遍历完毕，直接返回新头 }
置逆完成循环右移压位 void Reverse(int Array, int n, int k)t for (int i=0; kn/2: i++) swap(array, i, n-i-1) for(i=0: i<k/2: i++) swap(Array, i, k-i-1): for (i=0; k<(n-k)/2; i++) swap(Array, k+i, n-i-1) 口时间代价为O(n),空间代价为O(1) +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 置逆完成循环右移k位 void Reverse(int *Array, int n, int k) { for (int i=0; i<n/2; i++) swap(Array, i, n-i-1); for (i=0; i<k/2; i++) swap(Array, i, k-i-1); for (i=0; i<(n-k)/2; i++) swap(Array, k+i, n-i-1); } 时间代价为O(n)，空间代价为O(1)
3.MM算法 208“十一五”版本,蓝皮书。若i位失配,则 =next[j 口序号i012345678 c aa k 00011212∥/这是原始值 Pk pi ≠≠=≠=≠ m110010200∥这是优化 2004“五”版本,红皮书。若位失配,则i= next[-1] 口序号i012345678 P a b c aa b a b c k。000112123 +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 3. KMP算法 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 3 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 // 这是原始值 pk= pi? ≠ ≠ = ≠ = ≠ = = next[i] -1 0 0 -1 1 0 2 0 0 // 这是优化 2008“十一五”版本，蓝皮书。若i位失配，则i=next[i] 2004“十五”版本，红皮书。若i位失配，则i=next[i-1]
序号01234 aaaa b 优化的意义 0123∥这是原始值 pk= pi? nex-11-1-13这是优化 口不优化 aaa aaaa aaa next[3]=2 aa a nexI a ax& aa next[1=0 aaa next[O aaaa 优化 aaa aaaa aaa头b next[3]=-1 aaaa +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 优化的意义 不优化 a a a b a a a a b a a a a b next[3] = 2 a a a a b next[2] = 1 a a a a next[1] = 0 a a a a next[0] = -1 a a a a b 优化 a a a b a a a a b a a a a b next[3] = -1 a a a a b 序号i 0 1 2 3 4 P a a a a b 0 1 2 3 // 这是原始值 pk= pi? = = = ≠ next[i] -1 -1 -1 -1 3 // 这是优化
字符串特征向量的定义 口特证数n1+1〔0sn11sJ的递归定义如下: 1.如果==0,令=1;j=0令m1=0;对于n+1,假定已 知前一位置的特征数n=k 2.如果>1,k20且P=Pk,则n+1=k+1 3.当k20,且P1≠R时,则令k三nk,并让步骤3循环直 到条件不满足(变为P或k=1);则吗中= k+1 4.当K<0此时,k=-1),则n+=0 for j=0 next[j]=max(k: 0<k<j&p(o.k-1)=P-kj-1)),if such a exists otherwise +一依规数也是王线零x,《物不故索盐们,,m滤亲
“十一五”国家级规划教材。张铭，赵海燕，王腾蛟，宋国杰，《数据结构与算法实验教程》，高教社，2010.12 字符串特征向量的定义 特征数nj+1 ( 0≤ nj+1 ≤ j)的递归定义如下： 1. 如果j == 0 , 令n0 = -1； j==0, 令n1 = 0；对于nj+1 ，假定已 知前一位置的特征数 nj = k； 2. 如果j > 1，k ≥ 0 且 Pj == Pk ，则nj+1 = k+1； 3. 当k ≥ 0, 且P j ≠ Pk 时，则令k = nk，并让 步骤3循环直 到条件不满足（变为P j == Pk 或 k == -1）；则nj+1 = k+1； 4. 当 k<0 (此时，k ＝ -1), 则 nj＋1= 0。 = − = = 0, otherwise max{k :0 k j & P(0...k -1) P(j- k...j-1)} , if such a k exists 1, for j 0 next[j]