数据结构经典算法.doc

《数据结构经典算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.1编写冒泡排序算法，使结果从大到小排列。voidBubbleSortDec(DataTypea[],intn){for(i=0;i

2、析：计算语句频度是计算时间复杂度的基础。可以用观察和归纳进行简单的计算。1)问题规模n执行次数1122+133+2+1......nn+...+2+1=n(n+1)/2结论：语句频度为n(n+1)/2。2)问题规模n执行次数11223243......2kk+1结论：语句频度为。2.1将顺序表中的元素反转顺序。voidReverse(SqList&L){for(i=0;i

3、插入的位置i向后移动元素（从后向前处理）插入元素，表长加1思路2：从后向前查找插入位置，同时向后移动大于x的元素插入元素，表长加1注意：表满时不能插入。//顺序表结构constintMAXSIZE=1024;typedefstruct{DataTypeelem[MAXSIZE];intlength;}SqList;//向非递减有序的顺序表L中插入元素x，仍保持非递减有序//插入成功返回true，否则返回falseboolOrderListInsert(SqList&L,DataTypex){if(L.length==MAXSIZE)returnfalse;/

4、/表满，插入失败//将大于x的元素后移for(i=L.length-1;i>=0&&L.elem[i]>x;i--)L.elem[i+1]=L.elem[i];//插入x(因为最后执行i--，故应在i+1处)L.elem[i+1]=x;L.length++;returntrue;}2.3删除顺序表中所有等于x的元素。voidRemove(SqList&L,DataTypex){i=0;//剩余元素个数，同时是下一个元素的插入位置for(j=0;j

5、lem[i]=L.elem[j];//当i==j时不必复制i++;}L.length=i;//剩余元素个数}本算法的时间复杂度为O(n)；若改用反复调用查找和删除算法，时间复杂度会达到O(n2)。2.4编写算法实现顺序表元素唯一化(即使顺序表中重复的元素只保留一个)，给出算法的时间复杂度。思路：设已经唯一化的序列是(a0,…,ai-1)，剩余序列是(aj,…,an)。所要做的就是在已经唯一化的序列L.elem[0..i-1]中查找L.elem[j]，如果未找到则复制到L.elem[i]处。如此重复直到剩余序列为空。voidUnique(SqList&L){i

6、f(L.length<=1)return;//空表或只有一个元素的表已经唯一化了i=1;//开始L.elem[0..0]是唯一化序列for(j=1;j

7、元素删除达到唯一化，时间复杂度仍是O(n2)，但是与以上算法相比要移动更多元素。Error!Referencesourcenotfound.分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。思路：类似习题2.4，但是查找部分只要与L.elem[i-1]比较就可以了。voidUnique(SqList&L){i=0;//开始的唯一化序列为空(?对比习题2.4思考为什么不用i=1开始[②])for(j=1;j

8、m[j]!=L.elem[j-1]亦可if(j!=i