数据结构练习题解答（四）

数据结构练习题解答（四）

第四章 栈和队列

4-1、改写顺序栈的进栈成员函数Push (x )，要求当栈满时执行一个stackFull ( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。

【解答】templatevoid stack :: push ( const Type & item ) {

template void stack :: stackFull ( ) {

Type * temp = new Type [ 2 * maxSize ]; for ( int i = 0; i <= top; i++ )

temp[i] = elements[i];

}

delete [ ] elements; maxSize *= 2; elements = temp;

//创建体积大一倍的数组 //传送原数组的数据

//删去原数组

//数组最大体积增长一倍 //新数组成为栈的数组空间

}

if ( isFull ( ) ) stackFull ( ); elements [ ++top ] = item;

//栈满，做溢出处理 //进栈

4-2、铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：

(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。 【解答】

(1) 可能的不同出栈序列有

?1/(6?1)??C12?1326种。

(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须

一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。

3 2 1

2 1

1

5 4 1

1

6 4 1

4 1

1

4

3 32 32 325 325 3256 32564 325641

1

3 2

5 4 2

4 2

2

6

1 1 13 135 1354 13542 13542 135426

4-3、试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某

1

一种排列)，则在输出序列中不可能出现以下情况，即存在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出栈。此时具有最小值的排在最前面pi位置，具有中间值

的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出现pj < pk < pi的情形；

? i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值

的排在pj位置，具有中间值的排在最后pk位置，有pi < pk < pi , 不可能出现pj, pk < pi的情形；

? i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值

的排在其后pj位置，有pj < pi < pk, 不可能出现pj < pk < pi的情形；

? i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi 位置，具有最大

值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出现pj < pk < pi的情形；

? i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi 位置，具有中间

值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出现pj < pk < pi的情形；

4-5、写出下列中缀表达式的后缀形式：

4-7、设表达式的中缀表示为a * x - b / x↑2，试利用栈将它改为后缀表示ax * bx2↑/ -。写出转换过程中栈的变化。 【解答】

步序 0 1 2 3 4 5 6 7 8 9

扫描项 a * x - b / x ↑ 2

项类型 操作数 操作符 操作数 操作符 操作数 操作符 操作数 操作符 操作数

动 作 ? '#' 进栈, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' # ' ) < icp ( ' * ' ), 进栈, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' * ' ) > icp ( ' - ' ), 退栈输出 ? isp ( ' # ' ) < icp ( ' - ' ), 进栈, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号 ? 直接输出, 读下一符号

栈的变化 # # # * # * # # - # - # -/ # -/ # -/↑ # -/↑

输 出 a a a x a x * a x * a x * b a x * b a x * b x a x * b x a x * b x 2

(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 < C)||(C > D) ) )||(C < E) (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 > ! ||

(6) A B C < C D > || ! && ! C E < ||

【解答】

2

10

#

操作符

? isp ( '↑' ) > icp ( ' # ' ), 退栈输出 ? isp ( ' / ' ) > icp ( ' # ' ), 退栈输出 ? isp ( ' - ' ) > icp ( ' # ' ), 退栈输出 ? 结束

# -/ # - #

a x * b x 2↑ a x * b x 2↑/ a x * b x 2↑/ -

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 ( ) );

//判断队列是否不空，空则出错处理

3

length--; //队列长度减1

//返回原队头元素值

return elements[(rear-length+maxSize) % maxSize];

}

读取队头元素值函数

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; Q[rear] = item; tag = 1;

//判队列是否不满，满则出错处理

//队尾位置进1, 队尾指针指示实际队尾位置 //进队列

//标志改1，表示栈不空

4

}

删除函数

template

Type Queue :: DeQueue ( ) {

assert ( ! IsEmpty ( ) ); front = ( front + 1 ) % m; tag = 0;

//判断队列是否不空，空则出错处理

//队头位置进1, 队头指针指示实际队头的前一位置 //标志改0, 表示栈不满 //返回原队头元素的值

return Q[front];

}

读取队头元素函数

template

Type Queue :: GetFront ( ) {

assert ( ! IsEmpty ( ) );

//判断队列是否不空，空则出错处理 //返回队头元素的值

return Q[(front + 1) % m];

}

4-11 若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。 【解答】

template class Queue { public:

Queue ( ) : p ( NULL ) { } ~Queue ( );

//构造函数 //析构函数

//将item加入到队列中 //删除并返回队头元素 //查看队头元素的值

//置空队列，实现与~Queue ( ) 相同 //判队列空否

//链式队列类定义

链式队列的类定义

template class QueueNode { friend class Queue; private: Type data;

//数据域 //链域

//构造函数

QueueNode *link;

//链式队列结点类定义

template class Queue;

//链式队列类的前视定义

QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } };

void EnQueue ( const Type & item ); Type DeQueue ( ); Type GetFront ( );

void MakeEmpty ( );

int IsEmpty ( ) const { return p == NULL; } private:

QueueNode *p; };

template Queue::~Queue ( ) { QueueNode *s;

//队尾指针（在循环链表中）

队列的析构函数

//队列的析构函数

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构练习题解答（四）在线全文阅读。