数据结构(C语言版)课后习题答案

[题目分析]

将字符串前一半入栈,然后,栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较,若相等,则再出栈一个元素与后一个字符比较,??,直至栈空,结论为字符序列是回文。在出栈元素与串中字符比较不等时,结论字符序列不是回文。

[算法描述]

#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct

{DataType data[StackSize]; int top; }SeqStack;

int IsHuiwen( char *t)

{//判断t字符向量是否为回文,若是,返回1,否则返回0 SeqStack s; int i , len; char temp; InitStack( &s);

len=strlen(t); //求向量长度

for ( i=0; i

Push( &s, t[i]); while( !EmptyStack( &s))

{// 每弹出一个字符与相应字符比较 temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; }

return 1 ; // 比较完毕均相等则返回 1 }

(3)设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用栈结构存储输入的整数,当ai≠-1时,将ai进栈;当ai=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。

[算法描述]

#define maxsize 栈空间容量 void InOutS(int s[maxsize])

//s是元素为整数的栈,本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针,定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。

XVII

{cin>>x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。 {if(top==maxsize-1){cout<<“栈满”<

else s[++top]=x; //x入栈。 }

else //读入的整数等于-1时退栈。

{if(top==0){ cout<<“栈空”<

else cout<<“出栈元素是”<< s[top--]<

(4)从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$。

[题目分析]

逆波兰表达式(即后缀表达式)求值规则如下:设立运算数栈OPND,对表达式从左到右扫描(读入),当表达式中扫描到数时,压入OPND栈。当扫描到运算符时,从OPND退出两个数,进行相应运算,结果再压入OPND栈。这个过程一直进行到读出表达式结束符$,这时OPND栈中只有一个数,就是结果。

[算法描述] float expr( )

//从键盘输入逆波兰表达式,以‘$’表示输入结束,本算法求逆波兰式表达式的值。 {float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。 cin>>x;//x是字符型变量。 while(x!=’$’)

{switch

while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+(ord(x)-ord(‘0’)); cin>>x;} else //处理小数部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; cin>>x; } }//else

XVIII

{case‘0’<=x<=’9’:

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

cin>>x;//读入表达式中下一个字符。 }//结束while(x!=‘$’)

cout<<“后缀表达式的值为”<

[算法讨论]假设输入的后缀表达式是正确的,未作错误检查。算法中拼数部分是核心。若遇到大于等于‘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。

XIX

case‘O’: k++; if(k>j){cout<<“序列非法”<

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

if(j!=k) {cout<<“序列非法”<

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

(6)假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。

[题目分析]

置空队就是建立一个头节点,并把头尾指针都指向头节点,头节点是不存放数据的;判队空就是当头指针等于尾指针时,队空;入队时,将新的节点插入到链队列的尾部,同时将尾指针指向这个节点;出队时,删除的是队头节点,要注意队列的长度大于1还是等于1的情况,这个时候要注意尾指针的修改,如果等于1,则要删除尾指针指向的节点。

[算法描述]

//先定义链队结构: 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; delete s; }//回收结点空间

XX

联系客服:779662525#qq.com(#替换为@)