部分习题答案

由天下分享时间：2024/12/27 7:39:09 加入收藏我要投稿点赞

3.1 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种? (2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。【解答】

6 (1) 可能的不同出栈序列有 ? 1 /( 6 ? 1 )??C12?132种。 (2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。

3 2 1

3 2

5 4 2

4 2

2 1

5 4 1

6 4 1

4 1

3 32 32 325 325 3256 32564 325641

1 1 13 135 1354 13542 13542 135426

3-15 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。【解答】

0 m-1

bot[0] top[0] top[1] bot[1] 双栈的类定义如下：

~DblStack ( ) { delete [ ] elements; } void DblPush ( const Type& x, int i ); int DblPop ( int i );

//析构函数

//退掉位于栈i栈顶的元素 //把x插入到栈i的栈顶

#include

template class DblStack { private:

int top[2], bot[2]; Type *elements; int m;

//双栈的栈顶指针和栈底指针 //栈数组

//栈最大可容纳元素个数

//初始化双栈, 总体积m的默认值为

//双栈的类定义

public:

DblStack ( int sz =10 );

栈栈

}

template Type * DblStack :: DblGetTop ( int i ) { //若栈不空则函数返回该栈栈顶元素的地址。 if ( IsEmpty ( int i ) ) return NULL; return& elements[ top[i] ]; }

//判栈i空否, 若栈空则函数返回空指针

//返回栈顶元素的值

template int DblStack :: DblPop ( int i ) {

//如果IsEmpty ( i )，则不执行退栈，返回0；否则退掉位于栈i栈顶的元素，返回1 if ( IsEmpty ( i ) ) return 0; if ( i == 0 ) top[0]--; else top[1]++; return 1; }

//判栈空否, 若栈空则函数返回0 //栈0情形：栈顶指针减1 //栈1情形：栈顶指针加1

else elements[--top[1] ] = x;

//栈1情形：栈顶指针先减1, 然后按此地址进

template void DblStack :: DblPush ( const Type& x, int i ) { //如果IsFull ( )，则报错；否则把x插入到栈i的栈顶 assert ( !IsFull ( ) );

//断言: 栈满则出错处理，停止执行

//栈0情形：栈顶指针先加1, 然后按此地址进

if ( i == 0 ) elements[ ++top[0] ] = x;

template DblStack :: DblStack ( int sz ) : m(sz), top[0] (-1), bot[0](-1), top[1](sz), //建立一个最大尺寸为sz的空栈, 若分配不成功则错误处理。 elements = new Type[m]; }

//创建栈的数组空间

//断言: 动态存储分配成功与否

assert ( elements != NULL ); bot[1](sz) {

}

int IsFull ( ) const { return top[0]+1 == top[1]; } void MakeEmpty ( int i );

//判栈满否, 满则返回1, 否则返回0 //清空栈i的内容

Type * DblGetTop ( int i );

//返回栈i栈顶元素的值

//判栈i空否, 空则返回1, 否则返回

int IsEmpty ( int i ) const { return top[i] == bot[i]; }

template void MakeEmpty ( int i ) { if ( i == 0 ) top[0] = bot[0] = -1; else top[1] = bot[1] = m; }

或

S1.base S[1] S[m] S2.base

进栈：S1.top++ S2.top-- 出栈：S1.top-- S2.top++

栈满：S1.top==--S2.top或++S1.top==S2.top 3.28

void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q {

Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue

void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 {

p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x;

p->next=Q->next; //直接把p加在Q的后面 Q->next=p;

Q=p; //修改尾指针 }

Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x {

if(Q==Q->next) return INFEASIBLE; //队列已空 p=Q->next->next; x=p->data;

Q->next->next=p->next; free(p); return OK; }//DeCiQueue 或

typedef struct QNode {

QElemType data; struct QNode *next; }QNode,*QueuePtr;

Status EnQueue(QueuePtr &tail,QElemType e) {

q = (QueuePtr)malloc(sizeof(QNode));//分配空间，构造入队列元素结点 if(!q) return ERROR; //如果分配空间不成功，返回出错信息 q->data = e; //元素赋值 q->next = tail ->next; //入队列 tail ->next = q;

tail = tail ->next; //队尾指针后移 return OK; }

Status DeQueue(QueuePtr & tail,QElemType &e) {

q = tail ->next->next; //q指向带头结点链表的第一个元素 e = q->data; //返回出队列元素 tail ->next->next = tail ->next; //元素出队列 free(q); //释放空间 return OK;

} 3.30

Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法 {

if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue

Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法 {

if(Q.length==0) return INFEASIBLE;

head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释 x=Q.base[head]; Q.length--; }//DeCyQueue