《高级数据结构》ppt课件

《《高级数据结构》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高级数据结构教材：《数据结构（C++描述）》（金远平编著，清华大学出版社）讲课教师：金远平，软件学院ypjin@seu.edu.cn1JYP代价分摊（1.5.4）将孤立地分析一次算法调用得出的结论应用于一个ADT的相关操作序列会产生过于悲观的结果。例1.12整数容器Bag。classBag{public:Bag(intMaxSize=DefaultSize);//假设DefaultSize已定义intAdd(constintx);//将整数x加入容器中intDelete(constintk);//从容器中删除并打印

2、k个整数private:inttop;//指示已用空间int*b;//用数组b存放整数intn;//容量};2JYP各操作的实现如下：Bag::Bag(intMaxSize=DefaultSize):n(MaxSize){b=newint[n];top=-1;}intBag::Add(constintx){if(top==n-1)return0;//返回0表示加入失败else{b[++top]=x;return1;}}3JYPintBag::Delete(constintk){if(top+1

3、//容器内元素不足k个，删除失败else{for(inti=0;i

4、能大于m1次Add操作的总代价。因此，在最坏情况下，一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m1)。操作失败时，Add(x)和Delete(k)的时间复杂性都是O(1)。因此，在操作可能失败的情况下，一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m1+m2)。5JYP常规分析并没有错，只是其推导出的总代价上界远大于实际可得的上界。其原因是这种分析法没有注意到连续的最坏情况删除是不可能的。为了取得更准确的结果，还应该度量ADT数据结构的状态。对于每一个可能的状态S，赋

5、予一个实数(S)。(S)称为S的势能，其选择应使得(S)越高，对处于S状态的数据结构成功进行高代价操作的可能越大。例如，将容器元素个数作为容器状态的势能就很合理，因为元素越多，对容器成功进行高代价操作的可能越大。6JYP考虑一个由m个对ADT操作的调用构成的序列，并设ti是第i次调用的实际代价，定义第i次调用的分摊代价ai为ai=ti+(Si)–(Si-1)Si-1是第i次调用开始前ADT数据结构的状态，Si是第i次调用结束后ADT数据结构的状态。设的选择使得(Sm)≥(S0)，则7JYP即，分摊代

6、价的总和是实际代价总和的上界。例1.12将容器元素个数作为(S)。若操作序列始于空容器，则(Sm)≥(S0)总是成立。下表反映了容器(S)的典型变化情况。8JYP对于Add操作，ti=1，(Si)–(Si-1)=1，所以ai=2；对于Delete操作，ti=k，(Si)–(Si-1)=–k，所以ai=0。任何一个调用Add操作m1次，Delete操作m2次的序列的总代价为O(m12+m20)=O(m1)。9JYP可见，分摊分析法将偶尔出现的高价操作调用的代价分摊到邻近的其它调用上，故而得名。而且

7、，当用分摊分析法得到的一个操作调用序列的代价总和比用常规分析法得到的代价总和小时，人们就得到了更接近实际代价的分析结果，或者说对算法时间复杂性的判断更准确了。10JYP两个字符串的最长公共子序列（2.4.3）一个字符串的子序列通过从字符串中删除零或多个任意位置的字符得到。两个字符串x和y的最长公共子序列记为lcs(x,y)。例如，x=abdebcbb，y=adacbcb，则lcs(x,y)是adcbb和adbcb，如下所示：11JYP问题的基本求解方法：用标记空串，则lcs(x,)=lcs(,y)=。lcs

8、(xa,ya)=lcs(x,y)a，即xa和ya的最长公共子序列由x和y的最长公共子序列后接a构成。若xa和yb的最后一个字符不相等，则当lcs(xa,yb)不以a结尾时一定等于lcs(x,yb)，当lcs(xa,yb)不以b结尾时一定等于lcs(xa,y)。因此lcs(xa,yb)等于lcs(x,yb)与lcs(xa,y)中较长者。12JYP由此可得计算两