12数据结构经典算法

1.1编写冒泡排序算法，使结果从大到小排列。voidBubbleSortDec(DataTypea[],intn){for(i=0;in-1;i++){change=false;for(j=0;jn-i-1;j++)if(a[j]a[j+1]){//逆序swap(a[j],a[j+1]);change=true;}if(notchange)break;//没有交换则完成排序}}1.2计算下面语句段中指定语句的频度：1)for(i=1;i=n;i++)for(j=i;j=n;j++)x++;//@2)i=1;while(i=n)i=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;iL.length/2;i++)//?还是=1[①]L.elem[i]L.elem[L.length-i-1];}2.2在非递减有序的顺序表中插入元素x，并保持有序。思路1：先查找适合插入的位置i向后移动元素（从后向前处理）插入元素，表长加1思路2：从后向前查找插入位置，同时向后移动大于x的元素插入元素，表长加1注意：表满时不能插入。//顺序表结构constintMAXSIZE=1024;typedefstruct{DataTypeelem[MAXSIZE];intlength;}SqList;//向非递减有序的顺序表L中插入元素x，仍保持非递减有序//插入成功返回true，否则返回falseboolOrderListInsert(SqList&L,DataTypex){if(L.length==MAXSIZE)returnfalse;//表满，插入失败//将大于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;jL.length;j++)if(L.elem[j]!=x){//复制不等于x的元素组成新表if(i!=j)L.elem[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){if(L.length=1)return;//空表或只有一个元素的表已经唯一化了i=1;//开始L.elem[0..0]是唯一化序列for(j=1;jL.length;j++){//在L.elem[0..i-1]中查找L.elem[j]for(k=0;ki;k++)if(L.elem[k]==L.elem[j])break;if(k==i){//L.elem[j]未出现过，复制到L.elem[i]处if(j!=i)L.elem[i]=L.elem[j];i++;}}L.length=i;//表长为i}以上算法的时间复杂度为O(n2)。当然，可以反复将重复元素删除达到唯一化，时间复杂度仍是O(n2)，但是与以上算法相比要移动更多元素。错误!未找到引用源。分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。思路：类似习题2.4，但是查找部分只要与L.elem[i-1]比较就可以了。voidUnique(SqList&L){i=0;//开始的唯一化序列为空(?对比习题2.4思考为什么不用i=1开始2[②])for(j=1;jL.length;j++)if(L.elem[j]!=L.elem[i-1]){//Note：写成L.elem[j]!=L.elem[j-1]亦可if(j!=i)L.elem[i]=L.elem[j];i++;}L.length=i;//表长}错误!未找到引用源。思路：从链上依次取下结点，按照逆序建表的方法(参见2.3.(8)2°.节)重新建表。voidReverse(LinkList&L){p=L-next;//原链表L-next=NULL;//新表(空表)while(p){//从原链表中取下结点ss=p;p=p-next;//插入L新表表头s-next=L-next;L-next=s;}}错误!未找到引用源。voidInsertionSort(LinkList&L){h=L-next;//原链表L-next=NULL;//新空表while(h){//从原链表中取下结点ss=h;h=h-next;//在新表中查找插入位置p=L;while(p-next&&p-next-data=s-data)p=p-next;//在p之后插入ss-next=p-next;p-next=s;}}错误!未找到引用源。voidSelectionSort(LinkList&L){p=L;while(p-next){//选择最小(从p-next至表尾)q=p;//最小元素的前驱qs=p;while(s-next){if(s-next-dataq-next-data)q=s;s=s-next;}m=q-next;//找到最小m//最小元素m插入有序序列末尾(p之后)if(q!=p){q-next=m-next;//解下最小mm-next=p-next;//插入p之后p-next=m;}p=p-next;//L-next至p为有序序列}}错误!未找到引用源。//将非递减有序的单链表lb合并入la，保持非递减有序//结果la中含有两个链表中所有元素，lb为空表voidMerge(LinkList&la,LinkList&lb){p=la,q=lb;while(p-nextandq-next){//跳过la中较小的元素while(p-nextand(p-next-data=q-next-data))p=p-next;//把lb中较小的元素插入la中while(p-nextandq-nextand(q-next-datap-next-data)){s=q-next;q-next=s-next;s-next=p-next;p-next=s;p=s;}}if(lb-next){//表lb剩余部分插入la末尾p-next=lb-next;lb-next=NULL;}}3.1元素1,2,3,4依次入栈，不可能的出栈序列有哪些？分析：什么是不可能的出栈序列？如果后入栈的数(如4)先出栈，则此前入栈元素(如1,2,3)在栈中的顺序就确定了，它们的出栈顺序一定是逆序(如3,2,1)，否则就是不可能的出栈序列(如2,1,3)。不可能的出栈序列有：4123，4132，4213，4231，4312，3412，3142，3124。其中后3种都含312这一不可能序列。错误!未找到引用源。[fa][r][][][][fa][b][r][][][fa][b][c][r][][][fb][c][r][][][][fc][r][][][][][fr][]队列空...[f][r][][fd][e][f][g][r][fd][e]队列满。错误!未找到引用源。思路：先将队列中的元素入栈，然后从栈中取出重新入队列。voidReverse(SqQueue&Q){InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,x);Push(S,x);}while(!StackEmpty(S)){Pop(S,x);EnQueue(Q,x);}}4.1长度为n的串的子串最多有多少个？思路：对子串长度归纳。子串的长度是0，1，2，...，n，对应子串的个数分别是1(空串)，n，n-1，...，1，总起来就是1+n+(n-1)+...+2+1=1+n(n+1)/2。6.1度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点。分析：分别从结点个数和分支个数考虑。设叶子个数为n0，结点总数：n=n0+n1+n2+...+nk，分支数目：n-1=n1+2n2+...+knk，于是得到叶子个数错误!未找到引用源。分析：完全二叉树中度为1的结点至多有一个。完全二叉树中的结点数n+(n-1)≤N≤n+(n-1)+1，即2n-1≤N≤2n，二叉树的高度是于是，(1)当n=2k时，，当没有度为1的结点时；，当有1个度为1的结点时。(2)其他情况下，。错误!未找到引用源。voidPrintBinaryTree(BinTreebt,intindent){if(!bt)return;for(i=0;iindent;i++)print(“”);//缩进print(bt-data);PrintBinaryTree(bt-lchild,indent+1);PrintBinaryTree(bt-rchild,indent+1);}错误!未找到引用源。voidPrintBinaryTree(BinTreebt,intlevel){if(!bt)return;PrintBinaryTree(bt-rchild,level+1);//旋转后先打印右子树for(i=0;ilevel;i++)print(“”);//缩进print(bt-data);PrintBinaryTree(bt-lchild,level+1);}错误!未找到引用源。分析：按层遍历完全二叉树，当遇到第一个空指针之后应该全都是空指针。boolIsComplete(BinTreebt){//按层遍历至第一个空指针InitQueue(Q);EnQueue(Q,bt);while(!QueueEmpty(Q)){DeQueue(Q,p);if(p){EnQueue(Q,p-lchild);EnQueue(Q,p-rchild);}elsebreak;//遇到第一个空指针时停止遍历}//检查队列中剩余元素是否全部是空指针while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)returnfalse;//不是完全二叉树}returntrue;//完全二叉树}错误!未找到引用源。分析：进行后序遍历时，栈中保存的是当前结点的所有祖先。所以，后序遍历二叉树，遇到该结点时，取出栈中的内容即是所有祖先。//求二叉树bt中结点xptr的所有祖先vectorAncestors(BinTreebt,BinTreexptr){stacks;stacktag;p=bt;while(p||!s.empty()){if(p){s.push(p);tag.push(1);p=p-lchild;}else{p=s.pop();f=tag.pop();if(f==1){s.push(p);tag.push(2);p=p-rchild;}else{if(p==xptr){v=s;//当前栈的内容就是xptr的所有