template <class T> void LinkedStack<T>::SetNull() { Node<T> *q; while (top) { q=top->link; delete top; top=q; } }
i k(循环次数) 2*i 1 1 21<n 2 2 22<n 2k-1 n 2k<n 2k<n, k<log2n, k=log2n
划线语句的执行次数为 log2n。O(log2n) (3) for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) for (int k=1;k<=j;k++) x++;
习题三（第50页）
3.1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问 能否得到下列序列。若能得到，则给出相应的push和pop序列；若不 能，则说明理由。 1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此 时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3） 也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop
template <class T> bool LinkedStack<T>::IsEmpty() const { return !top; }
template <class T> bool LinkedStack<T>::IsFull() const { return false; }
template <class T> bool LinkedStack<T>::GetTop(T &x) { if (IsEmpty()) { cout<<"Empty stack"<<endl; return false; } x=top->data; return true; } template <class T> bool LinkedStack<T>::Push(const T x) { Node <T> *q=new Node<T>; q->data=x; q->link=top; top=q; return true; }
3.2 设计共享栈。
0
n-1
↑ bottom1
↑ top1
↑ top2
↑ bottom2
定义一个足够大的栈空间。该空间的两端分别设为两个栈的 栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和 top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生 溢出。 栈空，两栈均空：top1=0且 top2=n-1 栈满：top1=top2-1
2.2 (2) 在类LinearList 中增加一个成员函数，将顺序表逆置，实现 该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接 实现。 template <class T> void SeqList<T>::Invert() { T e; for (int i=0;i<length/2;i++) { e=elements[i]; elements[i]=elements[length-i-1]; elements[length-i-1]=e; } }
}
//解法三 不用栈，也不用数组，只用一个计数器top,记录“(”的个数 。 bool match(char a[],int n) { int top=-1; for (int i=0;i<n;i++) if (a[i]=='(') top++; else if (a[i]==')') if (top>-1) top--; //继续检查 else return true; //不匹配 if (top>-1) return true; return false; //匹配 //不匹配
O(n)
2.5 在类SingleList中增加一个成员函数，将单链表逆置运算， 直接实现该函数并分析其时间复杂度。 template <class T> void SingleList<T>::invert() { Node<T> *p=first,*q; first=NULL; while (p) { q=p->link; p->link=first; first=p; p=q; } }
//解法二 不用栈，用一个字符数组 bool match(char a[],int n) { char c[n]; int top=-1; for (int i=0;i<n;i++) if (a[i]==‘(’) { top++; s[top]=a[i]; } else if (a[i]==')') if (top>-1) { s[top]=0; top--; } //继续检查 else return true; //不匹配 if (top>-1) return true; return false; //匹配 //不匹配
3.4写出下列表达式的后缀形式。 ① /+ab+cd ③ -*~ac/b^c2 ② -^b2**4ac ④ +*+abc/d+ef
⑤ -*+ab+*cde*ac
3.9 利用栈可以检查表达式中括号是否配对，试编写算法实现之。 //若不匹配，则返回true,否则返回false //解法一 bool match(char a[],int n) { SeqStack<char> s(n); char c; for (int i=0;i<n;i++) if (a[i]==‘(’) s.Push(a[i]) //判栈满？ else if (a[i]==')') if (!s.Empty()) s.Pop(); //继续检查 else return true; //不匹配 if (!s.Empty()) return true; //不匹配 return false; //匹配 }
template <class T> void Difference(SeqList<T> &LA,SeqList<T> &LB) { int m=LA.Length(); SeqList<T> LC(10); T x; for (int i=1;i<=m;i++) { LA.Find(i,x); if (LB.Search(x)==0) LC.Insert(LC.Length()+1,x); } cout<<LC; } void main() { SeqList <int> LA(10),LB(10); for (int i=1;i<=8;i++) LA.Insert(i,i); for (i=1;i<=3;i++) LB.Insert(i,i+3); InterSection(LA,LB); Difference(LA,LB); }
b
// 解法2 template<class T> void Merge1(CircularList<T> &a,CircularList<T> &b) { Node<T> *p=b.first->link; b.first->data=b.first->link->data; b.first->link=a.first->link; a.first->link=p->link; p->link=p; b.first=p; b.length=0; } // O(1)
a=5，b=13
first
2
5
7
9
13
15
2.8 设有单循环链表类CircularList，要求在类CircularList中增加一个 成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表 的算法，并分析其时间复杂度。
// 解法1 template<class T> void Merge(CircularList<T> &a, CircularList<T> &b) { Node<T> *p=b.first; while (p->link!=b.first) p=p->link; p->link=a.first->link; a.first->link=b.first->link; b.first->link=b.first; b.length=0; } a // O(b.length)
1
i 1 j 1 43;1)(n+2)/6 。O(n3)
(4）x=n;y=0; while(x>=(y+1)*(y+1)) y++;
n>k2
划线语句的执行次数为 n 。O( n )
习题二（第37页）
2.1 利用线性表类LinearList提供的操作，实现两个集合的交和差运算。 #include <iostream.h> #include "seqlist0.h" #include "conio.h" template <class T> void InterSection(SeqList<T> &LA,SeqList<T> &LB) { int m=LB.Length(); SeqList<T> LC(10); T x; for (int i=1;i<=m;i++) { LB.Find(i,x); if (LA.Search(x)) LC.Insert(LC.Length()+1,x); } cout<<LC; }