《数据结构习题解答》习题3解答

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

18 (1/(6 1)) 132 6 + C12 = 3-1 改写顺序栈的进栈成员函数 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; //新数组成为栈的数组空间 } 3-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (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 3-3 试证明：若借助栈可由输入序列 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位置,具有最大值的排在p位置,有p class DblStack i ∥双栈的类定义 nt top[2], bot2]; ∥双栈的栈顶指针和栈底指针 I ∥栈数组 ∥栈最大可容纳元素个数 DbIStack( int Sz=10 ) ∥初始化双栈,总体积m的默认值为10 ∥析构函数 oid DblPush( const Type& x, int 1); 把x插入到栈i的栈顶 int DblPop( int i ) ∥退掉位于栈i栈顶的元素 Type* DblGetTop( int 1) ∥返回栈i栈顶元素的值 int IsEmpty(inti) consti return top=bo;}∥判栈i空否,空则返回1,否则返回0 sFull ()const( return top[O+l ==top[1];) ∥判栈满否,满则返回1,否则返回0 ∥清空栈i的内容 template DblStack: DblStack int Sz): m(sz), top[o](-1), bot[0J(1),top(1](sz), bot([1](sz)i ∥建立一个最大尺寸为sz的空栈,若分配不成功则错误处理 elements new Type[m]: ∥创建栈的数组空间 assert( elements I= NULL ) 断言:动态存储分配成功与否

19 ① i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最大值的排在 pk 位置，有 pi template class DblStack { //双栈的类定义 private: int top[2], bot[2]; //双栈的栈顶指针和栈底指针 Type *elements; //栈数组 int m; //栈最大可容纳元素个数 public: DblStack ( int sz =10 ); //初始化双栈, 总体积 m 的默认值为 10 ~DblStack ( ) { delete [ ] elements; } //析构函数 void DblPush ( const Type& x, int i ); //把 x 插入到栈 i 的栈顶 int DblPop ( int i ); //退掉位于栈 i 栈顶的元素 Type * DblGetTop ( int i ); //返回栈 i 栈顶元素的值 int IsEmpty ( int i ) const { return top[i] == bot[i]; } //判栈 i 空否, 空则返回 1, 否则返回 0 int IsFull ( ) const { return top[0]+1 == top[1]; } //判栈满否, 满则返回 1, 否则返回 0 void MakeEmpty ( int i ); //清空栈 i 的内容 } template DblStack :: DblStack ( int sz ) : m(sz), top[0] (-1), bot[0](-1), top[1](sz), bot[1](sz) { //建立一个最大尺寸为 sz 的空栈, 若分配不成功则错误处理。 elements = new Type[m]; //创建栈的数组空间 assert ( elements != NULL ); //断言: 动态存储分配成功与否 } 0 m-1 bot[0] top[0] top[1] bot[1]

template void DblStack DblPush( const Type& x, int i)i 如果 IsFull(),则报错:否则把x插入到栈i的栈顶 assert(!IsFull (; ∥断言:栈满则出错处理,停止执行 o[OT ∥栈0情形:栈顶指针先加1,然后按此地址进栈 else elements[--top[=x; 栈1情形:栈顶指针先减1,然后按此地址进栈 template int DblStack :: DblPop( int 1)t 如果 IsEmpty(i),则不执行退栈,返回0:否则退掉位于栈i栈顶的元素,返回1 if( IsEmpty (i))return 0; ∥判栈空否,若栈空则函数返回0 if(i==0)top[o]-; 0情形:栈顶指针减1 else top[ 1]++; 1情形:栈顶指针加1 template Type*DblStack DblGetTop( int i)i ∥若栈不空则函数返回该栈栈顶元素的地址 if( IsEmpty int i ))return NULL ∥判栈i空否,若栈空则函数返回空指针 return& elements[ top ∥返回栈顶元素的值 template void Make Empty int i)& if (i=0)topo=bot[0=-1; else top[ 1]= bot[ 1]=m; 写出下列中缀表达式的后缀形式: (1)A*B*C (2)-A+B-C+D (4)(A+B)*D+E/(F+A*D)+C (5)A&&B||!(E>F)体注:按C+的优先级* (6)!(A&&!(BD))!C! (6)ABC‖|!&&!CE< 3-6根据课文中给出的优先级,回答以下问题 (1)在函数 postfix中,如果表达式e含有n个运算符和分界符,问栈中最多可存入多少个元素?

20 template void DblStack :: DblPush ( const Type& x, int i ) { //如果 IsFull ( )，则报错；否则把 x 插入到栈 i 的栈顶 assert ( !IsFull ( ) ); //断言: 栈满则出错处理，停止执行 if ( i == 0 ) elements[ ++top[0] ] = x; //栈 0 情形：栈顶指针先加 1, 然后按此地址进栈 else elements[--top[1] ] = x; //栈 1 情形：栈顶指针先减 1, 然后按此地址进栈 } template int DblStack :: DblPop ( int i ) { //如果 IsEmpty ( i )，则不执行退栈，返回 0；否则退掉位于栈 i 栈顶的元素，返回 1 if ( IsEmpty ( i ) ) return 0; //判栈空否, 若栈空则函数返回 0 if ( i == 0 ) top[0]--; //栈 0 情形：栈顶指针减 1 else top[1]++; //栈 1 情形：栈顶指针加 1 return 1; } template Type * DblStack :: DblGetTop ( int i ) { //若栈不空则函数返回该栈栈顶元素的地址。 if ( IsEmpty ( int i ) ) return NULL; //判栈 i 空否, 若栈空则函数返回空指针 return& elements[ top[i] ]; //返回栈顶元素的值 } template void MakeEmpty ( int i ) { if ( i == 0 ) top[0] = bot[0] = -1; else top[1] = bot[1] = m; } 3-5 写出下列中缀表达式的后缀形式： (1) A * B * C (2) - A + B - C + D (3) A* - B + C (4) (A + B) * D + E / (F + A * D) + C (5) A && B|| ! (E > F) /*注：按 C++的优先级*/ (6) !(A && !( (B D) ) )||(C ! || (6) A B C || ! && ! C E < || 3-6 根据课文中给出的优先级，回答以下问题： (1) 在函数 postfix 中，如果表达式 e 含有 n 个运算符和分界符，问栈中最多可存入多少个元素？

(2)如果表达式e含有n个运算符,且括号嵌套的最大深度为6层,问栈中最多可存入多少个元素? 【解答】 (1)在函数 postfix中,如果表达式e含有n个运算符和分界符,则可能的运算对象有n+1个。因此在 利用后缀表达式求值时所用到的运算对象栈中最多可存入n+1个元素。 (2)同上 3-7试利用运算符优先数法,画出对如下中缀算术表达式求值时运算符栈和运算对象栈的变化。 a+b*(c-d)-etf/g 【解答】 设在表达式计算时各运算符的优先规则如上一题所示。因为直接对中缀算术表达式求值时必须使用两 个栈,分别对运算符和运算对象进行处理,假设命名运算符栈为OPTR( operator的缩写),运算对象栈为 OPND(operand的缩写),下面给出对中缀表达式求值的一般规则 (1)建立并初始化OPIR栈和OPND栈,然后在OPTR栈中压入一个“; (2)从头扫描中缀表达式,取一字符送入ch。 (3)当ch不等于“;”时,执行以下工作,否则结束算法。此时在OPND栈的栈顶得到运算结果 ①如果ch是运算对象,进OPND栈,从中缀表达式取下一字符送入ch ②如果ch是运算符,比较ch的优先级 icp( ch)和OPTR栈顶运算符isp(OPTR)的优先级 若icp(ch)> isp(OPTR),则ch进OPTR栈,从中缀表达式取下一字符送入ch; 若 icp(ch)isp(;',进OPIR栈,取下一符号 操作数 b进OPND栈,取下一符号 操作符 ),进OPTR栈,取下一符号 操作符 ()>p(”)进OPR栈,取下一符号ab c进OPND栈,取下 -)>isp((),进OPIR栈,取下一符号 789 操作数d进OPND找,取下一符号 a bc d )操作符|一ip()')<ip(-),退OPND栈d,退OPND|abs 栈‘c,退OPTR栈‘-’,计算c-d→s1,结果进 OPND栈 10同上|同上 ipC))=isp((),退OPTR栈(,对消括号,abs 取下一符号 操作符ip(-”)<ip()退OPND栈's,退 OPND a sz 栈“b’,退OPTR栈‘*”,计算b*s1→s2,结果进 12同上同上 i(-”)<isp(+”),退OPND栈's2,退 OPND s3 ,退OPTR栈

21 (2) 如果表达式 e 含有 n 个运算符，且括号嵌套的最大深度为 6 层，问栈中最多可存入多少个元素？ 【解答】 (1) 在函数 postfix 中，如果表达式 e 含有 n 个运算符和分界符，则可能的运算对象有 n+1 个。因此在 利用后缀表达式求值时所用到的运算对象栈中最多可存入 n+1 个元素。 (2) 同上。 3-7 试利用运算符优先数法，画出对如下中缀算术表达式求值时运算符栈和运算对象栈的变化。 a + b * (c - d) - e↑f / g 【解答】 设在表达式计算时各运算符的优先规则如上一题所示。因为直接对中缀算术表达式求值时必须使用两 个栈，分别对运算符和运算对象进行处理，假设命名运算符栈为 OPTR (operator 的缩写)，运算对象栈为 OPND(operand 的缩写)，下面给出对中缀表达式求值的一般规则： (1) 建立并初始化 OPTR 栈和 OPND 栈，然后在 OPTR 栈中压入一个“;” (2) 从头扫描中缀表达式，取一字符送入 ch。 (3) 当 ch 不等于“;”时，执行以下工作，否则结束算法。此时在 OPND 栈的栈顶得到运算结果。 ① 如果 ch 是运算对象，进 OPND 栈，从中缀表达式取下一字符送入 ch； ② 如果 ch 是运算符，比较 ch 的优先级 icp(ch)和 OPTR 栈顶运算符 isp(OPTR)的优先级：  若 icp(ch) > isp(OPTR)，则 ch 进 OPTR 栈，从中缀表达式取下一字符送入 ch；  若 icp(ch) isp (‘ ; ’ ), 进 OPTR 栈, 取下一符号 a ; + 3 b 操作数  b 进 OPND 栈, 取下一符号 a b ; + 4 * 操作符  icp (‘ * ’ ) > isp (‘ + ’ ), 进 OPTR 栈, 取下一符号 a b ; + * 5 ( 操作符  icp (‘ ( ’ ) > isp (‘ * ’ ), 进 OPTR 栈, 取下一符号 a b ; + * ( 6 c 操作数  c 进 OPND 栈, 取下一符号 a b c ; + * ( 7 - 操作符  icp (‘ - ’ ) > isp (‘ ( ’ ), 进 OPTR 栈, 取下一符号 a b ; + * ( - 8 d 操作数  d 进 OPND 栈, 取下一符号 a b c d ; + * ( - 9 ) 操作符  icp (‘ ) ’ ) < isp (‘ - ’ ), 退 OPND 栈 ‘d’, 退 OPND 栈 ‘c’, 退 OPTR 栈 ‘-’, 计算 c – d → s1, 结果进 OPND 栈 a b s1 ; + * ( 10 同上 同上  icp (‘ ) ’ ) == isp (‘ ( ’ ), 退 OPTR 栈‘(’, 对消括号, 取下一符号 a b s1 ; + * 11 - 操作符  icp (‘ - ’ ) < isp (‘ * ’ ), 退 OPND 栈 ‘s1’, 退 OPND 栈 ‘b’, 退 OPTR 栈 ‘*’, 计算 b * s1 → s2, 结果进 OPND 栈 a s2 ; + 12 同上 同上  icp (‘ - ’ ) < isp (‘ + ’ ), 退 OPND 栈 ‘s2’, 退 OPND 栈 ‘a’, 退 OPTR 栈 ‘+’, 计算 a * s2 → s3, 结果 s3 ;

13同上 进OPIR栈,取下一符号 e进OPND栈,取下一符号 进OPTR栈,取下一符号se 操作数一f进OPND栈,取下一符号 操作符|ip(/) template class Queue ∥循环队列的类定义 Queue( int10 ) Queue(i delete [elements; 3 Type DeQueue ( Type GetFront ( void Make Empty (i length =0; 3 ∥置空队列 int Is Empty (const i return length ==0; 3 ∥判队列空否 int IsFull const i return length 判队列满否 prvate /队尾指针和队列长度 Type’ elements; 存放队列元素的数组 int max Size: /队列最大可容纳元素个数 构造函数 Queue: Queue( int sz ) rear(maxSize-1), length(0), maxSize(sz)t ∥建立一个最大具有 maxSize个元素的空队列。 ∥创建队列空间 assert( elements [=0 断言:动态存储分配成功与否

22 进 OPND 栈 13 同上 同上  icp (‘ - ’ ) > isp (‘ ; ’ ), 进 OPTR 栈, 取下一符号 s3 ; - 14 e 操作数  e 进 OPND 栈, 取下一符号 s3 e ; - 15 ↑ 操作符  icp (‘↑’ ) > isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 e ; -↑ 16 f 操作数  f 进 OPND 栈, 取下一符号 s3 e f ; -↑ 17 / 操作符  icp (‘ / ’ ) isp (‘ - ’ ), 进 OPTR 栈, 取下一符号 s3 s4 ; - / 19 g 操作数  g 进 OPND 栈, 取下一符号 s3 s4 g ; - / 20 ; 操作符  icp (‘ ; ’ ) 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 )i assert(! IsFull (); ∥判队列是否不满,满则出错处理 ∥长度加1 rear=( rear +1)% maxsize; /队尾位置进1 ∥进队列 删除函数 template :: DeQueue ()i assert(! IsEmpty () ∥判断队列是否不空,空则出错处理 队列长度减 return elements[(rear-lengtht maxSize)%maxsize]; ∥返回原队头元素值 读取队头元素值函数 template Type Queue: GetFront()i assert(! IsEmpty ()) return elements[(rear-length+ 1+maxs ize)% maxSize 返回队头元素值 -9假设以数组Qm]存放循环队列中的元素,同时设置一个标志tag,以tag=0和tag=1来区别在队头 指针( front)和队尾指针(rear相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入( enqueue)和删 除( dequeue)算法 【解答】 循环队列类定义 template class Queue ∥循环队列的类定义 Queue(int10 ) -Queue(i delete[Q:) void EnQueue( Type item ) Type DeQueue ( Type GetFront ( void Make Empty front rear =tag =0;1 置空队列 int IsEmpty) const{ return front=rear&&tag=0;}∥判队列空否 int IsFull const i return front=rear&&tg=1;}∥判队列满否 private: int rear, front, tag: 队尾指针、队头指针和队满标志 Type Q; ∥放队列元素的数组 队列最大可容纳元素个数

23 } 插入函数 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 ( ) { assert ( ! IsEmpty ( ) ); return elements[(rear-length+1+maxSize) % maxSize]; //返回队头元素值 } 3-9 假设以数组 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; //队列最大可容纳元素个数 }

构造函数 Queue: Queue( int Sz ) rear(), front(O), tag(O), m(sz)t 建立一个最大具有m个元素的空队列 Q=new Type f创建队列空间 assert(Q=0; ∥断言:动态存储分配成功与否 插入函数 template assert(! IsFull () ∥判队列是否不满,满则出错处理 rear=( rear+ 1)%m; 队尾位置进1,队尾指针指示实际队尾位置 Qrear]=item ∥进队列 ∥标志改1,表示队列不空 删除函数 template Queue∷:De assert(! IsEmpty () ∥判断队列是否不空,空则出错处理 front=( front+1)% /队头位置进1,队头指针指示实际队头的前一位置 标志改0,表示栈不满 return Q front] ∥返回原队头元素的值 读取队头元素函数 emplate Type Queue: Get Front(i assert(! IsEmpty () ∥判断队列是否不空,空则出错处理 return Q((front 1)%m: ∥返回队头元素的值 3-10若使用循环链表来表示队列,p是链表中的一个指针。试基于此结构给出队列的插入( enq ueue)和删除 ( dequeue))算法,并给出p为何值时队列空 【解答】 链式队列的类定义 template class Queue ∥链式队列类的前视定义 QueueNode i ∥链式队列结点类定义 friend class Queue *link; ∥链域 QueueNode( Type d=0, QueueNode *1=NULL ) data(d), link 造函数

24 构造函数 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，表示队列不空 } 删除函数 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]; //返回队头元素的值 } 3-10 若使用循环链表来表示队列，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 ∥链式队列类定义 Queue(: p(NULL)0 ∥构造函数 Type item ) 将item加入到队列中 Type DeQueue ( 删除并返回队头元素 ∥查看队头元素的值 int IsEmpty const i return p= NULL; ∥判队列空否 QueueNode*p; 队尾指针(在循环链表中) }; 队列的析构函数 template Queue: Queue (i 队列的析构函数 while(pl=NULL){s=p;p=p->link; delete s;}∥逐个删除队列中的结点 队列的插入函数 template void Queue: En Queue( const Type item )i if( p== NULL) /队列空,新结点成为第一个结点 p= new QueueNode( item, NULL ) p->link=p; 队列不空,新结点链入p之后 QueueNode *s=new QueueNodelink=p->link;p=p->link=s;W结点p指向新的队尾 队列的删除函数 template Type Queue: DeQueue (i i(p=NULL){cout *s=p: 队头结点为p后一个结点 p->link ∥重新链接,将结点s从链中摘下 Type revalue =s->data; delete s; 保存原队头结点中的值,释放原队头结点 return revalue 返回数据存放地址 队空条件p=NULL 3-11若将一个双端队列顺序表示在一维数组Ⅴ[m中,两个端点设为end和end2,并组织成一个循环队列。 试写出双端队列所用指针endl和end2的初始化条件及队空与队满条件,并编写基于此结构的相应的插入 ( enqueue)新元素和删除( dEqueue)算法 【解答】 end2 初始化条件endl=end2=0; 队空条件endl=end2

25 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 ( ) { //队列的析构函数 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。 3-11 若将一个双端队列顺序表示在一维数组 V[m]中，两个端点设为 end1 和 end2，并组织成一个循环队列。 试写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入 (enqueue)新元素和删除(dlqueue)算法。 【解答】 初始化条件 end1 = end2 = 0; 队空条件 end1 = end2; end1 end2

队满条件(end1+1)%m=end2;∥设endl端顺时针进栈,end2端逆时针进栈 循环队列类定义 template class DoubleQueue i ∥循环队列的类定义 Double Queue( int=10 ) DoubleQueue (i delete [V;) void EnQueue Type item, const int end )i Type DeQueue(const int end ) Type GetFront(const int end ) ∥置空队列 int Is Empty ()const( return endl ==end2 ∥判两队列空否 int IsFull const( return(end1+1)% end2;}∥判两队列满否 private int endl, end2; 队列两端的指针 ∥存放队列元素的数组 队列最大可容纳元素个数 构造函数 template DoubleQueue: DoubleQueue( int Sz ) endl (O), end2(0), m(sz)t ∥建立一个最大具有m个元素的空队列。 V=new Type]: ∥创建队列空间 assert(V=0); 断言:动态存储分配成功与否 插入函数 template void DoubleQueue: EnQueue( Type &item, const int end)i assert (!sFull(; if( end ==1)i end1 =(endl 1)%m; 端指针先进1,再按指针进栈 Lendl= item; 1指向实际队头位置 else i Vlend2]=item ∥end2端先进队列,指针再进1 end2=( end2-1 +m)% end2指向实际队头的下一位置 删除函数 template e Queue:: DeQueue( const int end)( assert(!IsEmpty ())i Type& temp; ){

26 队满条件 ( 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; //队列两端的指针 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 ) {

p= vlend1]: ∥先保存原队头元素的值,endl端指针退1 endl =( end 1 + m else i end2=( end2+1)% m temp Vlend2 ∥end2端指针先退1。再保存原队头元素的值 return temp 读取队头元素的值 template Type DoubleQueue: GetFront( const int end)( assert(IsEmpty () Ty if( end ==1)return Vend1] 历返回队头元素的值 else return V[(end2+1)%m]; 3-12设用链表表示一个双端队列,要求可在表的两端插入,但限制只能在表的一端删除。试编写基于此结 构的队列的插入 enqueue)和删除( dequeue)算法,并给出队列空和队列满的条件。 【解答】 链式双端队列的类定义 template class DoubleQueue; ∥链式双端队列类的前视定义 ∥链式双端队列结点类定义 friend class D ueue "link DoubleQueueNode( Type d=0, DoubleQueueNode "1=NUL):dad,link({}∥构造函数 emplate class DoubleQueue 链式双端队列类定义 publie DoubleQueue ( 构造函数 -DoubleQueue (; ∥析构函数 ueuel const Type& item ) ∥从队列endl端插入 void En DoubleQueue2 const Type& item ) ∥从队列end2端插入 Type DeDoubleQueue ( ∥删除并返回队头endl元素 Type Get Front ( 渣看队头endl元素的值 void Make Empty(片 ∥置空队列 int Is Empty() const{ return end I=endl->link;}∥判队列空否

27 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 V[(end2+1) % m]; } 3-12 设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结 构的队列的插入(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: