错误！未找到引用源。
void BubbleSortDec ( DataType a[], int n ) {
for ( i=0; i for( j=0; j 错误！未找到引用源。 分析：计算语句频度是计算时间复杂度的基础。可以用观察和归纳进行简单的计算。 1) 问题规模n 执行次数 1 1 2 2+1 3 3+2+1 ... ... n n+...+2+1=n(n+1)/2 结论：语句频度为n(n+1)/2。 2) 问题规模n 执行次数 1 1 2 2 3 2 4 3 ... ... k 2 k+1 结论：语句频度为?logn??1。 错误！未找到引用源。 void Reverse ( SqList& L ) { for ( i=0; i 错误！未找到引用源。 思路1：先查找适合插入的位置i 向后移动元素（从后向前处理） 插入元素，表长加1 思路2：从后向前查找插入位置，同时向后移动大于x的元素 插入元素，表长加1 注意：表满时不能插入。 // 顺序表结构 ① 用边界值验证法说明对于偶数个元素的表会有何种情况。 const int MAXSIZE = 1024; typedef struct { DataType elem[MAXSIZE]; int length; } SqList; // 向非递减有序的顺序表L中插入元素x，仍保持非递减有序 // 插入成功返回true，否则返回false bool OrderListInsert ( SqList &L, DataType x ) { if ( L.length==MAXSIZE ) return false; // 表满，插入失败 // 将大于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++; return true; } 错误！未找到引用源。 void Remove ( SqList &L, DataType x ) { i = 0; // 剩余元素个数，同时是下一个元素的插入位置 for ( j=0; j L.length = i; // 剩余元素个数 } 本算法的时间复杂度为O(n)；若改用反复调用查找和删除算法，时间复杂度会达到O(n2)。 错误！未找到引用源。 思路：设已经唯一化的序列是(a0, … , ai-1)，剩余序列是(aj,…, an)。所要做的就是在已经唯一化的序列L.elem[0..i-1]中查找L.elem[j]，如果未找到则复制到L.elem[i]处。如此重复直到剩余序列为空。 void Unique ( SqList &L ) { if ( L.length<=1 ) return; // 空表或只有一个元素的表已经唯一化了 i = 1; // 开始L.elem[0..0]是唯一化序列 for ( j=1; j // 在L.elem[0..i-1]中查找L.elem[j] for ( k=0; 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)，但是与以上算法相比要移动更多元素。 错误！未找到引用源。 分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。 思路：类似习题错误！未找到引用源。，但是查找部分只要与L.elem[i-1]比较就可以了。 void Unique ( SqList &L ) { i = 0; // 开始的唯一化序列为空(○?对比习题错误！未找到引用源。思考为什么不用i=1开始①) for ( j=1; 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.错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。节)重新建表。 void Reverse ( LinkList &L ) { p = L->next; // 原链表 L->next = NULL; // 新表(空表) while ( p ) { // 从原链表中取下结点s s = p; p = p->next; // 插入L新表表头 s->next = L->next; L->next = s; } } 错误！未找到引用源。 void InsertionSort ( LinkList &L ) { h = L->next; // 原链表 L->next = NULL; // 新空表 while ( h ) { // 从原链表中取下结点s s = h; h = h->next; ① 原因是这里不能确定表是否为空，而习题2.4则用开始的if语句排除了空表的情况。事实上，习题2.4也可以仿照此 处修改，请读者自己完成。 // 在新表中查找插入位置 p = L; while ( p->next && p->next->data<=s->data ) p = p->next; // 在p之后插入s s->next = p->next; p->next = s; } } 错误！未找到引用源。 void SelectionSort ( LinkList &L ) { p = L; while ( p->next ) { // 选择最小(从p->next至表尾) q = p; // 最小元素的前驱q s = p; while ( s->next ) { if ( s->next->data < q->next->data ) q = s; s = s->next; } m = q->next; // 找到最小m // 最小元素m插入有序序列末尾(p之后) if ( q!=p ) { q->next = m->next; // 解下最小m m->next = p->next; // 插入p之后 p->next = m; } p = p->next; // L->next至p为有序序列 } } 错误！未找到引用源。 // 将非递减有序的单链表lb合并入la，保持非递减有序 // 结果la中含有两个链表中所有元素，lb为空表 void Merge ( LinkList &la, LinkList &lb ) { p = la, q = lb; while ( p->next and q->next ) { // 跳过la中较小的元素 while ( p->next and (p->next->data <= q->next->data) ) p = p->next; // 把lb中较小的元素插入la中 while ( p->next and q->next and (q->next->data < p->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; } } 错误！未找到引用源。 分析：什么是不可能的出栈序列？如果后入栈的数(如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][]? [][][][f r][] 队列空 ? ... ?[f][r][][fd][e]?[f][g][r][fd][e] 队列满。 错误！未找到引用源。 思路：先将队列中的元素入栈，然后从栈中取出重新入队列。 void Reverse ( SqQueue &Q ) { InitStack ( S ); while ( ! QueueEmpty(Q) ) { DeQueue ( Q, x ); Push ( S, x ); } while ( ! StackEmpty(S) ) { Pop ( S, x ); EnQueue ( Q, x ); } } 错误！未找到引用源。 思路：对子串长度归纳。 子串的长度是0，1，2，...，n，对应子串的个数分别是1(空串)，n，n-1，...，1，总起来就是1+n+(n-1)+...+2+1=1+n(n+1)/2。 错误！未找到引用源。 分析：分别从结点个数和分支个数考虑。 设叶子个数为n0，结点总数：n = n0+n1+n2+...+nk，分支数目：n-1 = n1+2 n2+...+k nk，于是得到叶子个数 n0?1??(i?1)ni i?1k 错误！未找到引用源。 分析：完全二叉树中度为1的结点至多有一个。 完全二叉树中的结点数n+(n-1) ≤ N ≤ n + (n-1) + 1，即2n-1 ≤ N ≤ 2n，二叉树的高度是 ?log(2n?1)??1?h??log(2n)??1
