《数据结构chapter 10 选讲内容》由会员分享，可在线阅读，更多相关《数据结构chapter 10 选讲内容（44页珍藏版）》请在金锄头文库上搜索。
1、*1补充内容*2静态链表某些高级语言中可能不支持指针操作，在这种情况下可以 用数组来实现链表结构，这种链表称为静态链表静态链表中各个节点均是数组的元素，它的定义如下： #define MAXSIZE 1000 typedef struct ElemType data; int cur; component, SLinkListMAXSIZE;在这种结构中，除了一个数据域之外，还有一个游标域， 它用来代替指针表示下一个节点在数组中的位置在静态链表中插入和删除元素时只需要游标的值而不需要 移动元素*3静态链表示例假设线性表为ZHAO,QIAN,SUN,LI,ZHOU 则用静 态链表表示为：删除元素
2、SUN之后的结构为：ZHAO2QIAN3SUN4LI5ZHOU0101234567下标数组内容ZHAO2QIAN4LI5ZHOU0101234567下标数组内容*4静态链表的查找算法int LocateElem_SL(SLinkList S, ElemType e)/在静态链表中查找第1个值为e的元素/若找到则返回其位置，否则返回0 i = S0.cur; while(!i return i;*5静态链表的空间分配与回收由于静态链表是用数组来实现的，因此l在插入元素时候，需要从数组的空余空间中找出一个 单元给新插入的元素使用l当删除元素后，该元素所占用的空间需要进行回收， 以便该空间能被重新使
3、用为此可以采用下面的方法：l初始时，将数组所有空余空间组成一个链式结构，头 节点的cur域指向第一个空余的空间l当插入新元素的时候，将头节点cur域指向的空间分给 新插入的元素使用，同时修改cur指向下一个空余空间l当删除一个元素时候，将该空间的插入空余空间链表 的头部*6数组空间初始化void InitSpace_SL(SLinkList i T0) return i-T0; else return 0; *26简单模式匹配算法示例a b a b c a b c abca bSposTijijij第一趟匹配 i=3,j=3i=i-j+2=2,回退1a b a b c a b c abca b
4、STij第二趟匹配i=2,j=1i=i-j+2=3,前进a b c a ca b c a ca b a b c a b c abca bSTij第三趟匹配i=7,j=5i=i-j+2=4,回退3a b c a cijijijij*27简单模式匹配算法的问题当出现不匹配的时候，主串的指针需要回退，影 响效率极端情况下比较的次数与NM成正比经过人们的努力，发现了一种改进算法，它可以 在N+M数量级上完成模式匹配。这种算法称为KMP算法，其改进之处在于：在每 一趟比较中，当出现不匹配的情况时，不需要回 退指针，而是根据已经得到的“部分匹配”的结 果，将指针后移一段距离后再进行比较*28改进算法说明示
5、例a b a b c a b c abca bSTi=3j第一趟匹配a b c a ca b a b c a b c abca bSTij=1第二趟匹配a b c a ci=7a b a b c a b c abca bSTi第三趟匹配a b c a ci=7j=2因为主串i=2必然为b, 而T(1)=a肯定不匹配因为主串i=4,5必然为 bc,T(1)=a肯定不匹配, 主串6为a不需要比较*29讨论一般情况假设主串为s1s2sn而模式串为p1p2pm，当sipj 时，模式串应该向右滑行多长的距离？换句话说，主串中 第i个字符（i指针不回退）该与模式串中哪个字符比较呢假设此时应该与模式串中的第
6、k（k T0) return i-T0;else return 0; 由此可见改进算法是以next(j)为基础来运行的 ，对于给定的模式串，显然根据定义我们可以手 工推算出next(j)的值，但是右没有更好的方法 可以得到 它的值呢？*33next(j)的计算特别注意：从上面的分析可以知道，next(j) 的值完全取决于模式串，与主串没有任何关系首先，根据定义有：next1=0假定nextj=k，这表明jk模式串*34next(j+1)与next(j)的关系假定nextj=k，那么nextj+1有两种可能：（1）pk=pj,这表明在模式串中存在：于是有：nextj+1=k+1jkj+1j+1k
7、+1*35next(j+1)计算（2）pkpj,这相当于一个模式匹配问题，只 不过主串和模式串是同一个串，这个时候应该 将模式向右移动，使主串第j个字符和模式串中 的第nextk=k个字符比较l如果pk=pj，则说明在主串第j+1个字符前面有k个 字符的最大子串与模式中从首字符开始的长度为k的 子串相等，于是有nextj+1=nextk+1lpjpk,则继续将模式串向右滑动nextk个字符 ，再比较，依次类推，直到找到某个匹配字符或不存 在任何k，这个时候根据定义 nextj+1=1*36第二种情况演示kj+1k子串jk主串 相当于串比较next(k)=k相当于j+1前面由k个字符组成 的串与
8、子串头k个字符组成的子 串相同，因此 next(j+1)=k+1=next(k) +1假定next(j)=k*37next(j)计算示例j1 2 3 4 5 6模式串a b a a b cnext(j )0 1 1 2 2 3当j=7时，next(6)=3,需要比较p6和p3,由于p6p3,所以需 要继续比较;由于next(3)=1,故需比较p6和p1,由于p6p1, 所以需要继续比较,由于next(1)=0,所以next(7)=1;当j=8时，next(7)=1,需要比较p7和p1,由于p7=p1,所以 next8=next7+1=27a18c2*38next(j)函数C描述void get
9、_next(SString T,int next1=0; k=0; while(j T0) if (k=0 | Tj=Tk) +j;+k;nextj=k; else k=nextk; *39Huffman编码存储C描述typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode;*40Huffman编码算法(初始化）void HuffmanCoding(HuffmanTree m = 2*n-1; / 节点总数目 HT=(
10、HuffmanTree)malloc(m+1)* sizeof(HTNode);/0号未使用 for(p=HT,i=1;i=n;i+,p+,w+) *p=*w,0,0,0; for(;i=m;i+,p+) *p=0,0,0,0;*41Huffman编码算法(建树）for(i=n+1;i=m;i+) Select(HT,i-1,s1,s2);/从前面i-1元素中选两个最小的值 HTs1.parent = i; HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight; *42Huffman编码算法(编
11、码）HC=(HuffmanCode)malloc(n+1)sizeof(char *); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if (HTf.lchild = c) cd-start=0; else cd-start=1; HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi, /end of for free(cd); *43无栈非递归遍历Huffma
12、n树HC=(HuffmanCode)malloc(n+1)sizeof(char *); p=m;cdlen=0; for(i=1;i=m;i+) HTi.weight=0; while(p) if (HT(p).weight=0) /向左 HTp.weight = 1; if (HTp.lchild !=0) p=HTp.lchild;cdcdlen+=0; else if (HTp.rchild = 0) HCp=(char *)malloc( (cdlen+1)*sizeof(char); cdcdlen=0;strcpy(HCp,cd); *44无栈非递归遍历Huffman树（续）else if (HTp.weight=1) HTp.weight = 2; if(HTp.rchild!=0) p=HTp.rchild; cdcdlen+=1; else HTp.weight=0; p=HTp.parent; -cdlen;
