23490数据结构习题答案 下载本文

scanf (“%c”,&x);//x是字符型变量。 while(x!=’$’) {switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数 if(x!=’.’) //处理整数

{num=num*10+(ord(x)-ord(‘0’));

scanf(“%c”,&x);}

else //处理小数部分。 {scale=10.0; scanf(“%c”,&x); while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; scanf(“%c”,&x); } }//else

push(OPND,num); num=0.0;//数压入栈,下个数初始化

case x=‘ ’:break; //遇空格,继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while(x!=‘$’)

printf(“后缀表达式的值为%f”,pop(OPND)); }//算法结束。

[算法讨论]假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符,认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数,每读入一个数字字符,前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点,认为数的整数部分已完,要接着处理小数部分。小数部分的数要除以10(或10的幂数)变成十分位,百分位,千分位数等等,与前面部分数相加。在拼数过程中,若遇非数字字符,表示数已拼完,将数压入栈中,并且将变量num恢复为0,准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断,因此在结束处理数字字符的case后,不能加入break语句。

(5)假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。

①下面所示的序列中哪些是合法的?

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。

①A和D是合法序列,B和C 是非法序列。

②设被判定的操作序列已存入一维数组A中。 int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是,返回true,否则返

回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\\n”);exit(0);} }

i++; //不论A[i]是‘I’或‘O’,指针i均后移。}

if(j!=k) {printf(“序列非法\\n”);return(false);} else {printf(“序列合法\\n”);return(true);} }//算法结束。

[算法讨论]在入栈出栈序列(即由‘I’和‘O’组成的字符串)的任一位置,入栈次数(‘I’的个数)都必须大于等于出栈次数(即‘O’的个数),否则视作非法序列,立即给出信息,退出算法。整个序列(即读到字符数组中字符串的结束标记‘\\0’),入栈次数必须等于出栈次数(题目中要求栈的初态和终态都为空),否则视为非法序列。

(6)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意

不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。

算法如下: //先定义链队结构:

typedef struct queuenode{ Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct{ queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

(1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队:就是使头结点成为队尾元素

QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点

while (Q->rear!=Q->rear->next)//当队列非空,将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; free(s); }//回收结点空间 }

(2)判队空

int EmptyQueue( LinkQueue *Q) { //判队空

//当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }

(3)入队

void EnQueue( LinkQueue *Q, Datatype x) { //入队

//也就是在尾结点处插入元素

QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点 }

(4)出队

Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t;

QueueNode *p; if(EmptyQueue( Q ))

Error(\

p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear)

{//当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next;} else

Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; }

(7)假设以数组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; } private:

int rear, front, tag; Type *Q; int m; }

//队尾指针、队头指针和队满标志

//存放队列元素的数组 //队列最大可容纳元素个数

//循环队列的类定义

int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否

构造函数

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,表示队列不空

位置

删除函数

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];

(8)如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义;

② 写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。

(1)#define M 队列可能达到的最大长度 typedef struct

{ elemtp data[M]; int front,rear; } cycqueue;

(2)elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,

否则给出出错信息。

{ if (Q.front==Q.rear) {printf(“队列空”); exit(0);}