清华大学：《数据结构及其应用》课程教学资源（试卷习题）试题5

4-2改写顺序栈的进栈成员函数Push(x),要求当栈满时执行一个 stacke硎()操作进行栈满处理。其功能 是:动态创建一个比原来的栈数组大二倍的新数组,代替原来的栈数组,原来栈数组中的元素占据新数组 的前 Maxsize位置。 【解答】 template≤ lass Type> void stack;psh( const Type&iem){ if( is Full()stackFull (; ∥栈满,做溢出处理 elements [+top]=item; ∥进栈 template void stack:: stackFul(t Type*lemp= new Type[3* maxie];∥创建体积大二倍的数组 for(inti=0;i<=p;汁+) ∥传送原数组的数据 delete elements 删去原数组 maxSice *=3: ∥数组最大体积增长二倍 elements temp: ∥新数组成为栈的数组空间 4-3铁路进行列车调度时,常把站台设计成栈式结构的站台,如右图所示。试问: (1)设有编号为123.456的六辆列车,顺序开入栈式结构的站台,则可能I 的出栈序列有多少种? 34 (2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641 154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何 得到即写出"进栈”或"出栈"的序列)。 【解答】 (1)可能的不同出栈序列有(1/(6+1)*CB2=132种。 (2)不能得到435612和154623这样的出栈序列。因为若在4,3,5,6之后再将1,2出栈,则1,2必须 直在栈中,此时1先进栈,2后进栈,2应压在1上面,不可能1先于2出栈。154623也是这种情况。 出栈序列325641和135426可以得到。 3253256 32564325641 135 1354 1354213542135426 4-4试证明:若借助栈可由输入序列1,2,3,…n得到一个输出序列p,P2P3,…,pn(它是输入序列的某 种排列),则在输出序列中不可能出现以下情况,即存在i<j<k,使得p<P<p。(提示:用反证法) 【解答】 因为借助栈由输入序列1,2,3,…,n,可得到输出序列p,P,p,…,p,如果存在下标i,j,k,满足< j<k,那么在输出序列中,可能出现如下5种情况:

(1/(6 1)) 132 6 + C12 = 4-2 改写顺序栈的进栈成员函数 Push (x )，要求当栈满时执行一个 stackFull ( )操作进行栈满处理。其功能 是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组 的前 MaxSize 位置。 【解答】templatevoid stack :: push ( const Type & item ) { if ( isFull ( ) ) stackFull ( ); //栈满，做溢出处理 elements [ ++top ] = item; //进栈 } template void stack :: stackFull ( ) { Type * temp = new Type [ 3 * maxSize ]; //创建体积大二倍的数组 for ( int i = 0; i <= top; i++ ) //传送原数组的数据 temp[i] = elements[i]; delete [ ] elements; //删去原数组 maxSize *= 3; //数组最大体积增长二倍 elements = temp; //新数组成为栈的数组空间 } 4-3 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为 1,2,3,4,5,6 的六辆列车, 顺序开入栈式结构的站台, 则可能 的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到 435612, 325641, 154623 和 135426 的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何 得到(即写出"进栈"或"出栈"的序列)。 【解答】 (1) 可能的不同出栈序列有 种。 (2) 不能得到 435612 和 154623 这样的出栈序列。因为若在 4, 3, 5, 6 之后再将 1, 2 出栈，则 1, 2 必须 一直在栈中，此时 1 先进栈，2 后进栈，2 应压在 1 上面，不可能 1 先于 2 出栈。154623 也是这种情况。 出栈序列 325641 和 135426 可以得到。 3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 3 32 32 325 325 3256 32564 325641 5 3 4 4 1 2 2 2 2 6 1 1 13 135 1354 13542 13542 135426 4-4 试证明：若借助栈可由输入序列 1, 2, 3, …, n 得到一个输出序列 p1, p2, p3, …, pn (它是输入序列的某一 种排列)，则在输出序列中不可能出现以下情况，即存在 i < j < k，使得 pj < pk < pi。(提示：用反证法) 【解答】 因为借助栈由输入序列 1, 2, 3, …, n，可得到输出序列 p1, p2, p3, …, pn ，如果存在下标 i, j, k，满足 i < j < k，那么在输出序列中，可能出现如下 5 种情况：

①i进栈,i出栈,j进栈,j出栈,k进栈,k出栈。此时具有最小值的排在最前面p位置,具有中间 值的排在其后P位置,具有最大值的排在pk位置,有pF)体注:按C+的优先级* (6)!(A&&!((BD))C!|1 6ABCI!&&ICEi2(=),退栈输 σ卹sp("#')ic('#'),退栈输出 ax*bx2↑

① i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最大值的排在 pk 位置，有 pi F) /*注：按 C++的优先级*/ (6) !(A && !( (B D) ) )||(C ! || (6) A B C || ! && ! C E icp ( ' - ' ), 退栈输出 # a x *  isp ( ' # ' ) icp ( ' # ' ), 退栈输出 # -/ a x * b x 2↑  isp ( ' / ' ) > icp ( ' # ' ), 退栈输出 # - a x * b x 2↑/  isp ( ' - ' ) > icp ( ' # ' ), 退栈输出 # a x * b x 2↑/ -

结束 4-9假设以数组Q[m]存放循环队列中的元素,同时以ream和 length分别指示环形队列中的队尾位置和队列 中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入( enqueue)和删除( dequeue) 元素的操作 【解答】 循环队列类定义 #include template class Queue i ∥循环队列的类定义 Queue( int10 ) void EnQueue(Type item ) Type Dequeue(片 Type GetFront ( 置空队列 int lsEmpry ()const i return length==0;1 ∥判队列空否 int Is Full( const i return length = maxSize; 1 ∥判队列满否 prvate int rear, length: /队尾指针和队列长度 ∥存放队列元素的数组 int maxsize; /队列最大可容纳元素个数 构造函数 template : Queue( int s=): rear(maxsie-1), length(0), maxIe(s=)i ∥建立一个最大具有 maxie个元素的空队列 ents new Type ∥创建队列空间 assert( elements =0); 断言:动态存储分配成功与否 插入函数 template void Queue: EnQueue( Type &item )i assert(! IsFull(): ∥判队列是否不满,满则出错处理 length++ ∥长度加1 rear+1)%max Size; /队尾位置进 elementsrear]= item ∥进队列 删除函数 template Type Queue: DeQueue()i assert(! IsEmpty()); ∥判断队列是否不空,空则出错处理 length; 队列长度减1 return elements[(rear-leng th+max Sie)% maxsice] 返回原队头元素值

 结束 4-9 假设以数组 Q[m]存放循环队列中的元素, 同时以 rear 和 length 分别指示环形队列中的队尾位置和队列 中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue) 元素的操作。 【解答】 循环队列类定义 #include template class Queue { //循环队列的类定义 public: Queue ( int=10 ); ~Queue ( ) { delete [ ] elements; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { length = 0; } //置空队列 int IsEmpty ( ) const { return length == 0; } //判队列空否 int IsFull ( ) const { return length == maxSize; } //判队列满否 private: int rear, length; //队尾指针和队列长度 Type *elements; //存放队列元素的数组 int maxSize; //队列最大可容纳元素个数 } 构造函数 template Queue:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) { //建立一个最大具有 maxSize 个元素的空队列。 elements = new Type[maxSize]; //创建队列空间 assert ( elements != 0 ); //断言: 动态存储分配成功与否 } 插入函数 template void Queue :: EnQueue ( Type &item ) { assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理 length++; //长度加 1 rear = ( rear +1) % maxSize; //队尾位置进 1 elements[rear] = item; //进队列 } 删除函数 template Type Queue :: DeQueue ( ) { assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 length--; //队列长度减 1 return elements[(rear-length+maxSize) % maxSize]; //返回原队头元素值

读取队头元素值函数 template Type Queue: GetFront(i assert(! IsEmpry() return elements[(rear-leng th+ 1+max Sie)% maxIe]; ∥返回队头元素值 4-10假设以数组Qm存放循环队列中的元素,同时设置一个标志tag,以lag==0和lag==1来区别在队 头指针(on)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入( enqueue)和 删除( dequeue)算法。 【解答】 循环队列类定义 #include template class Queue i ∥循环队列的类定义 Queue( int10 ) -Oueue delete [0; void EnQueue(Type item ) Type DeQueue ( Type GetFront ( void Make Empty (tfront=rear =tag=0;) 置空队列 int Is Empry() const{ return front==rear&&lag==0;}∥判队列空否 int sFull() const{ return front==rea&&lag==1;}∥判队列满否 int rear, front, tag: 队尾指针、队头指针和队满标志 Type Q ∥放队列元素的数组 队列最大可容纳元素个数 构造函数 Queue<Type: Queue( int s=): rear(O), front(O), tag(O), m(s=)t ∥建立一个最大具有m个元素的空队列 ∥创建队列空间 assert(Q=0); 断言:动态存储分配成功与否 插入函数 ){ sert(! IsFull(): ∥判队列是否不满,满则出错处理 rear=( rear+1)% m 队尾位置进1,队尾指针指示实际队尾位置 ∥进队列 ∥标志改1,表示队列不空

} 读取队头元素值函数 template Type Queue :: GetFront ( ) { assert ( ! IsEmpty ( ) ); return elements[(rear-length+1+maxSize) % maxSize]; //返回队头元素值 } 4-10 假设以数组 Q[m]存放循环队列中的元素, 同时设置一个标志 tag，以 tag == 0 和 tag == 1 来区别在队 头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和 删除(dlqueue)算法。 【解答】 循环队列类定义 #include template class Queue { //循环队列的类定义 public: Queue ( int=10 ); ~Queue ( ) { delete [ ] Q; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) { front = rear = tag = 0; } //置空队列 int IsEmpty ( ) const { return front == rear && tag == 0; } //判队列空否 int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否 private: int rear, front, tag; //队尾指针、队头指针和队满标志 Type *Q; //存放队列元素的数组 int m; //队列最大可容纳元素个数 } 构造函数 template Queue:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) { //建立一个最大具有 m 个元素的空队列。 Q = new Type[m]; //创建队列空间 assert ( Q != 0 ); //断言: 动态存储分配成功与否 } 插入函数 template void Queue :: EnQueue ( Type &item ) { assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理 rear = ( rear + 1 ) % m; //队尾位置进 1, 队尾指针指示实际队尾位置 Q[rear] = item; //进队列 tag = 1; //标志改 1，表示队列不空 }

删除函数 emplate Type Queue: DeQueue (i ( IsEmpry () ∥判断队列是否不空,空则出错处理 front=(front +1)% /队头位置进1,队头指针指示实际队头的前一位置 ∥标志改0,表示栈不满 return @fron; ∥返回原队头元素的值 读取队头元素函数 template Type Queue: GetFront (i assert(! IsEmpty()); ∥判断队列是否不空,空则出错处理 return o[front+ 1)% m]: ∥返回队头元素的值 4-11若使用循环链表来表示队列,p是链表中的一个指针。试基于此结构给出队列的插λ( enqueue)和删除 ( dequeue)算法,并给出p为何值时队列空。 【解答】 链式队列的类定义 template class queue ∥链式队列类的前视定义 late class QueueNode i ∥链式队列结点类定义 class Queue Type data; ∥数据域 QueueNode class Queue i ∥链式队列类定义 publie Queue(:P(NULL )0 ∥构造函数 -Queue (i ∥析构函数 void EnQueue const Type item ) 将iem加入到队列中 Type DeQueue ( 删除并返回队头元素 Type GetFront ( M查看队头元素的值 void Make Empty o: ∥置空队列,实现与~ Queue()相同 int IsEmpty()const( return P== NULL; j ∥判队列空否 vate: QueueNode *p; /队尾指针(在循环链表中) 队列的析构函数 template Queue: -Queue (i 队列的析构函数

删除函数 template Type Queue :: DeQueue ( ) { assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 front = ( front + 1 ) % m; //队头位置进 1, 队头指针指示实际队头的前一位置 tag = 0; //标志改 0, 表示栈不满 return Q[front]; //返回原队头元素的值 } 读取队头元素函数 template Type Queue :: GetFront ( ) { assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理 return Q[(front + 1) % m]; //返回队头元素的值 } 4-11 若使用循环链表来表示队列，p 是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除 (dequeue)算法，并给出 p 为何值时队列空。 【解答】 链式队列的类定义 template class Queue; //链式队列类的前视定义 template class QueueNode { //链式队列结点类定义 friend class Queue; private: Type data; //数据域 QueueNode *link; //链域 public: QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } //构造函数 }; template class Queue { //链式队列类定义 public: Queue ( ) : p ( NULL ) { } //构造函数 ~Queue ( ); //析构函数 void EnQueue ( const Type & item ); //将 item 加入到队列中 Type DeQueue ( ); //删除并返回队头元素 Type GetFront ( ); //查看队头元素的值 void MakeEmpty ( ); //置空队列，实现与~Queue ( ) 相同 int IsEmpty ( ) const { return p == NULL; } //判队列空否 private: QueueNode *p; //队尾指针（在循环链表中） }; 队列的析构函数 template Queue::~Queue ( ) { //队列的析构函数

while(pl=NULL){s=p;p=p->lmk; delete s;}m逐个删除队列中的结点 队列的插入函数 template void Queue: EnQueue const Type item)i if(P== NULL)( 队列空,新结点成为第一个结点 p= new QueueNode( item, NULL); P->link =p; QueueNode *s=new QueueNode( item, NULL); s->lnk=p->lnk;p=p->lnk=s;w结点p指向新的队尾 队列的删除函数 emplate Type queue: DeQueue (i if(p==NULL){coutdata: delete s; ∥保存原队头结点中的值,释放原队头结点 return revalue ∥返回数据存放地址 队空条件p==NUL。 4-12若将一个双端队列顺序表示在一维数组Ⅵm中,两个端点设为endl和end2,并组织成一个循环队列 试写出双端队列所用指针endl和end2的初始化条件及队空与队满条件,并编写基于此结构的相应的插入 ( enqueue)新元素和删除( dEqueue)算法。 【解答】 初始化条件endl=end2=0; 队空条件endl=end2 队满条件(endl+1)%m=enn2;∥设endl端顺时针进栈,end端逆时针进栈 循环队列类定义 #include template class Doublequeue i ∥循环队列的类定义 Doublequeue ( delete [V; void EnQueue( Type& item, const int end ); Type DeQueue(const int end); Type GetFront (const int end ) void Make Empty (endl end =0; 置空队列 ∥判两队列空否 int IsFull(() const{ return(endl1+1)%m==endn2;}∥判两队列满否 int endl. end2 /队列两端的指针

QueueNode *s; while ( p != NULL ) { s = p; p = p->link; delete s; } //逐个删除队列中的结点 } 队列的插入函数 template void Queue::EnQueue ( const Type & item ) { if ( p == NULL ) { //队列空, 新结点成为第一个结点 p = new QueueNode ( item, NULL ); p->link = p; } else { //队列不空, 新结点链入 p 之后 QueueNode *s = new QueueNode ( item, NULL ); s->link = p->link; p = p->link = s; //结点 p 指向新的队尾 } } 队列的删除函数 template Type Queue::DeQueue ( ) { if ( p == NULL ) { cout *s = p; //队头结点为 p 后一个结点 p->link = s->link; //重新链接, 将结点 s 从链中摘下 Type retvalue = s->data; delete s; //保存原队头结点中的值, 释放原队头结点 return retvalue; //返回数据存放地址 } 队空条件 p == NULL。 4-12 若将一个双端队列顺序表示在一维数组 V[m]中，两个端点设为 end1 和 end2，并组织成一个循环队列。 试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入 (enqueue)新元素和删除(dlqueue)算法。 【解答】 初始化条件 end1 = end2 = 0; 队空条件 end1 = end2; 队满条件 ( end1 + 1 ) % m = end2; //设 end1 端顺时针进栈，end2 端逆时针进栈 循环队列类定义 #include template class DoubleQueue { //循环队列的类定义 public: DoubleQueue ( int=10 ); ~DoubleQueue ( ) { delete [ ] V; } void EnQueue ( Type & item, const int end ); Type DeQueue (const int end ); Type GetFront (const int end ); void MakeEmpty ( ) { end1 = end2 = 0; } //置空队列 int IsEmpty ( ) const { return end1 == end2; } //判两队列空否 int IsFull ( ) const { return (end1+1) % m == end2; } //判两队列满否 private: int end1, end2; //队列两端的指针 end1 end2

∥放队列元素的数组 /队列最大可容纳元素个数 构造函数 Doublequeue: Double Queue(int s=): endl(O), end2(0), m(s=)i ∥建立一个最大具有m个元素的空队列 V= new Type] ∥创建队列空间 assert(V=0); /言:动态存储分配成功与否 插入函数 EnQueue( Type const int end)i assert (!sFull(; endl =(endl +1)% m; end1端指针先进1,再按指针进栈 Mendl=item: end1指向实际队头位置 Fendel =item; ∥en端先进队列,指针再进1 ∥en指向实际队头的下一位置 删除函数 emplate Type DoubleQueue: DeQueue( const int end)t assert(IlsEmpy ()i Type& temp if end==1)i temp=Mendl ∥先保存原队头元素的值,enll端指针退1 endl=(endl m-1)% m else i end2 =(end2+ 1)%m; ∥en端指针先退1。再保存原队头元素的值 return temp 读取队头元素的值 template GetFront( const int end)i assert(!lsEmpry (); Type& temp; if( end== 1)return Mendi]: ∥返回队头元素的值

Type *V; //存放队列元素的数组 int m; //队列最大可容纳元素个数 } 构造函数 template DoubleQueue:: DoubleQueue ( int sz ) : end1 (0), end2 (0), m (sz) { //建立一个最大具有 m 个元素的空队列。 V = new Type[m]; //创建队列空间 assert ( V != 0 ); //断言: 动态存储分配成功与否 } 插入函数 template void DoubleQueue :: EnQueue ( Type &item, const int end ) { assert ( !IsFull ( ) ); if ( end == 1 ) { end1 = ( end1 + 1 ) % m; //end1 端指针先进 1, 再按指针进栈 V[end1] = item; //end1 指向实际队头位置 } else { V[end2] = item; //end2 端先进队列, 指针再进 1 end2 = ( end2 - 1 + m ) % m; //end2 指向实际队头的下一位置 } } 删除函数 template Type DoubleQueue :: DeQueue ( const int end ) { assert ( !IsEmpty ( ) ); Type& temp; if ( end == 1 ) { temp = V[end1]; //先保存原队头元素的值, end1 端指针退 1 end1 = ( end1 + m - 1 ) % m; } else { end2 = ( end2 + 1 ) % m; temp = V[end2]; //end2 端指针先退 1。再保存原队头元素的值 } return temp; } 读取队头元素的值 template Type DoubleQueue :: GetFront ( const int end ) { assert ( !IsEmpty ( ) ); Type& temp; if ( end == 1 ) return V[end1]; //返回队头元素的值

else return M(end2+1)%m]: 4-13设用链表表示一个双端队列,要求可在表的两端插入,但限制只能在表的一端删除。试编写基于此结 构的队列的插入( enqueue)和删除( dequeue)算法,并给出队列空和队列满的条件 解答】 链式双端队列的类定义 template class Doublequeuenode ∥链式双端队列结点类定义 friend class Double queue link ∥链域 Doublequeuenode( Type d=0, DoubleQueueNode=NULL):da(d,lmk(D{}∥构造函数 }; template class Doublequeue 式双端队列类定义 ∥构造函数 ∥析构函数 void EnDoubleQueuel const Type& item ) ∥从队列end1端插入 con ; ∥从队列end2端插入 Type DeDouble queue ( 删除并返回队头end1元素 Type GetFront ( 查看队头endl元素的值 void Make Empty(; ∥置空队列 int Is Emp() const( return endl==endl->lmnk;}/判队列空否 private: Oueuenode*endl,·end2; MendI在链头,可插可删;en在链尾,可插不可删 }; 队列的构造函数 template doublequeue doubleQueue (i ∥构造函数 ∥创建循环链表的表头结点 assert(lendl lend ) end1->link 队列的析构函数 template Queue : :-Queue (i /队列的析构函数 QueueNode *p /逐个删除队列中的结点,包括表头结点 while( endl I=NULL )P= endl; endl endl->ink; delete P;1 队列的插入函数 template ∥从队列endl端插入

else return V[(end2+1) % m]; } 4-13 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结 构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。 【解答】 链式双端队列的类定义 template class DoubleQueue; //链式双端队列类的前视定义 template class DoubleQueueNode { //链式双端队列结点类定义 friend class DoubleQueue; private: Type data; //数据域 DoubleQueueNode *link; //链域 public: DoubleQueueNode (Type d = 0, DoubleQueueNode *l = NULL) : data (d), link (l) { } //构造函数 }; template class DoubleQueue { //链式双端队列类定义 public: DoubleQueue ( ); //构造函数 ~DoubleQueue ( ); //析构函数 void EnDoubleQueue1 ( const Type& item ); //从队列 end1 端插入 void EnDoubleQueue2 ( const Type& item ); //从队列 end2 端插入 Type DeDoubleQueue ( ); //删除并返回队头 end1 元素 Type GetFront ( ); //查看队头 end1 元素的值 void MakeEmpty ( ); //置空队列 int IsEmpty ( ) const { return end1 == end1->link; } //判队列空否 private: QueueNode *end1, *end2; //end1 在链头, 可插可删; end2 在链尾, 可插不可删 }; 队列的构造函数 template doubleQueue :: doubleQueue ( ) { //构造函数 end1 = end2 = new DoubleQueueNode( ); //创建循环链表的表头结点 assert ( !end1 || !end2 ); end1->link = end1; } 队列的析构函数 template Queue :: ~Queue ( ) { //队列的析构函数 QueueNode *p; //逐个删除队列中的结点, 包括表头结点 while ( end1 != NULL ) { p = end1; end1 = end1->link; delete p; } } 队列的插入函数 template //从队列 end1 端插入

void DoubleQueue: EnDoublequeuel const Type& item)& 队列空,新结点成为第一个结点 new Double QueueNode( item, end1 ) 队列不空,新结点链入endl之后 endl-link new DoubleQueueNode( item, end1-> ink ) template : EnDoubleQueue2 const Type& item )t nd2 =end2->link = new Double QueueNode( item, end1 ) 队列的删除函数 Type Doublequeue DeDouble queue (t if( TeMpt()) return{cout 'p=endl->link ∥被删除结点 end1->ink =p->link ∥重新链接 Type revalue = p->data: delete p: /删除end后的结点p if( Is Empty()end2 =endl; return revalue: 读取队列endl端元素的内容 template Type Doublequeue: GetFront()i assert(!sEmpry(; return endl->link->data; 置空队列 template void queues ke Empry(i 逐个删除队列中的结点,包括表头结点 while endl I=endl->ink )p=endl; endl endl->ink; delete p: j 4-14试建立一个继承结构,以栈、队列和优先级队列为派生类,建立它们的抽象基类一一Bqg类。写出各 个类的声明。统一命名各派生类的插入操作为Add,删除操作为 Remove,存取操作为Get和Pa,初始化 操作为 MakeEmpry,判空操作为Empy,判满操作为Fl,计数操作为 Length 【解答】 Bag类的定义 template class Bag t Bag( int s== DefauliSie ) 构造函数 ∥析构函数 virtual void Add( const Type& item ) 插入函数 virtual Type Remove (: ∥删除函数 virtual int Is Empty(i return top==-1: ∥判空函数

void DoubleQueue :: EnDoubleQueue1 ( const Type& item ) { if ( end1 == end1->link ) //队列空, 新结点成为第一个结点 end2 = end1->link = new DoubleQueueNode ( item, end1 ); else //队列不空, 新结点链入 end1 之后 end1->link = new DoubleQueueNode ( item, end1->link ); } template //从队列 end2 端插入 void DoubleQueue :: EnDoubleQueue2 ( const Type& item ) { end2 = end2->link = new DoubleQueueNode ( item, end1 ); } 队列的删除函数 template Type DoubleQueue :: DeDoubleQueue ( ) { if ( IsEmpty ( ) ) return { cout *p = end1->link ; //被删除结点 end1->link = p->link; //重新链接 Type retvalue = p->data; delete p; //删除 end1 后的结点 p if ( IsEmpty ( ) ) end2 = end1; return retvalue; } 读取队列 end1 端元素的内容 template Type DoubleQueue :: GetFront ( ) { assert ( !IsEmpty ( ) ); return end1->link->data; } 置空队列 template void Queue:: MakeEmpty ( ) { QueueNode *p; //逐个删除队列中的结点, 包括表头结点 while ( end1 != end1->link ) { p = end1; end1 = end1->link; delete p; } } 4-14 试建立一个继承结构，以栈、队列和优先级队列为派生类，建立它们的抽象基类——Bag 类。写出各 个类的声明。统一命名各派生类的插入操作为 Add，删除操作为 Remove，存取操作为 Get 和 Put，初始化 操作为 MakeEmpty，判空操作为 Empty，判满操作为 Full，计数操作为 Length。 【解答】 Bag 类的定义 template class Bag { public: Bag ( int sz = DefaultSize ); //构造函数 virtual ~Bag ( ); //析构函数 virtual void Add ( const Type& item ); //插入函数 virtual Type *Remove ( ); //删除函数 virtual int IsEmpty ( ) { return top == -1; } //判空函数

virtual int IsFull(i return top== maxsie-1; ∥判满函数 virtual void Empty()i cout Bag :: Bag( int MaxBag Size ) MaxSie( MarBag Size )i elements new Type MaxIe Bag类的析构函数 template Bag: :-Bag (i delete elements Bag类的插入函数 template void Bag: Add( const Type item )4 if( Is Full()Full (; else elements [++top]=item; Bag类的删除函数 template Type*Bag: Remove(& if( lsEmpry()) Empry ( return NULL; Type& x=elements ∥保存被删除元素的值 for int i=0; i class Stack: public Bag i public: Stack( int s== DefaulISie ) ∥构造函数 -Stack(; 析构函数 Type Remore (; ∥删除函数 栈的构造函数 template Stack : Stack( int s=): Bag(s:)0 栈的构造函数Sack将调用Bag的构造函数 栈的析构函数 template Stack: -Stack(3 ∥栈的析构函数将自动调用Bag的析构函数,以确保数组 elements的释放

virtual int IsFull ( ) { return top == maxSize - 1; } //判满函数 private: virtual void Empty ( ) { cout Bag :: Bag ( int MaxBagSize ) : MaxSize ( MaxBagSize ) { elements = new Type [ MaxSize ]; top = -1; } Bag 类的析构函数 template Bag :: ~Bag ( ) { delete [ ] elements; } Bag 类的插入函数 template void Bag :: Add ( const Type & item ) { if ( IsFull ( ) ) Full ( ); else elements [ ++top ] = item; } Bag 类的删除函数 template Type *Bag :: Remove ( ) { if ( IsEmpty ( ) ) { Empty ( ); return NULL; } Type & x = elements [0]; //保存被删除元素的值 for ( int i = 0; i class Stack : public Bag { public: Stack ( int sz = DefaultSize ); //构造函数 ~Stack ( ); //析构函数 Type *Remove ( ); //删除函数 }; 栈的构造函数 template Stack :: Stack ( int sz ) : Bag ( sz ) { } //栈的构造函数 Stack 将调用 Bag 的构造函数 栈的析构函数 template Stack :: ~Stack ( ) { } //栈的析构函数将自动调用 Bag 的析构函数, 以确保数组 elements 的释放