数据结构第三章习题答案

判断回文palindrome:

#include <iostream>

#include <string>

using namespace std;

bool huiwen(string s)

{

int n=s.length();

int i,j;

i= 0;

j=n-1;

while(i<j && s[i]==s[j]){ i++;j--;}

if(i>=j) return true;else return false;

}

int main()

{

string s1;

cin>>s1;

cout<<huiwen(s1);

return 0;

}

=============

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

#include <iostream>

using namespace std;

#define OVERFLOW -2

#define OK 1

#define ERROR 0

typedef int SElemType;

typedef int Status;

typedef struct {

SElemType a[5];

int top;

} SqStack;

Status InitStack(SqStack &S){

S.top=0;

return OK;

}

Status Push(SqStack &S,SElemType e){

if (S.top>4){cout<<"overlow!"<<endl;return ERROR;}

else S.a[S.top++]=e;

return OK;

}

Status Pop(SqStack &S,SElemType &e)

{ if (S.top==0) {cout<<"underflow"<<endl; return ERROR;}

e=S.a[--S.top];

cout<<e<<endl;

return OK;

}

int main()

{ SqStack s;

InitStack(s);

int n,x,e1;

cout<<"n=?"<<endl;

cin>>n;

for(int i=0;i<n;i++)

{ cin>>x;

if(x!=-1 )Push(s,x);else Pop(s,e1); }

return 0;

}

============

（3）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 ①下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

int Judge(char A[])

{

i=0;

countI=countO=0;

while(A[i]!='\0')

{

if(A[i]=='I')countI++;

else{

countO++;

if(countO>countI)return 0;//出栈次数大于入栈次数

}

i++;

}

if(countI!=countO)return 0;

else return 1;

}

＝＝＝＝＝＝＝

（4）已知Ackermann函数定义如下:

① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。

② 写出计算Ack(m,n)的非递归算法。

int Ack(int m,n)

{if (m==0) return(n+1);

else if(m!=0&&n==0) return(Ack(m-1,1));

else return(Ack(m-1,Ack(m,m-1));

}//算法结束

（1）Ack(2,1)的计算过程

Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得

=Ack(1,Ack(1,1)) //因m<>0,n=0而得

=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得

= Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得

=Ack(1,Ack(0,2)) // 因m=0而得

=Ack(1,3) // 因m=0而得

=Ack(0,Ack(1,2)) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得

= Ack(0,Ack(0,Ack(0,2))) //因m=0而得

= Ack(0,Ack(0,3)) //因m=0而得

= Ack(0,4) //因n=0而得

=5 //因n=0而得

（2）int Ackerman( int m, int n)

{int akm[m][n];int i,j;

for(j=0;j<n;j++) akm[0][j];=j+1;

for(i=1;i<m;i++)

{akm[i][0]=akm[i-1][1];

for(j=1;j<n;j++)

akm[i][j]=akm[i-1][akm[i][j-1]];

}

return(akm[m][n]);

}//算法结束

==========

（5）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：

① 求链表中的最大整数；

② 求链表的结点个数；

③ 求所有整数的平均值。

#include <iostream>

using namespace std;

#define ERROR 0

#define OK 1

typedef int Status ;

typedef int ElemType ;

typedef struct LNode{

ElemType data;

struct LNode *next;

}LNode,*LinkList;

void CreateList_L(LinkList &L,int n)

{LinkList p;

L=new LNode;

L->next=NULL;

for(int i=n;i>0;--i)

{p=(LinkList)malloc(sizeof(LNode));

cin>>p->data;

p->next=L->next;L->next=p;}

}

Status ListInsert_L(LinkList &L, int i, ElemType e)

{ LinkList p,S;

int j;

p=L;j=0;

while(p&&j<i-1){p=p->next; ++j;}

if(!p||j>i-1)return ERROR;

S=(LinkList)malloc(sizeof(LNode));

S->data=e;

S->next=p->next;

p->next=S;

return OK;

}

void print_L(LinkList L)

{

LinkList p=L->next ;

while(p)

{cout<<p->data <<","; p=p->next;

}

cout<<endl;

}

Status ListDelete_L(LinkList &L, int i, ElemType &e)

{ LinkList P,Q;

int j;

P=L,j=0;

while(P->next && j<i-1){P=P->next; ++j;}

if(!(P->next)||j>i-1)return ERROR;

Q=P->next;

P->next=Q->next;

e=Q->data;

delete Q;

return OK;

}

int Max ( LinkList L ) {

LinkList f=L->next;

if ( f ->next == NULL ) return f ->data;

int temp = Max ( f );

if ( f->data > temp ) return f ->data;

else return temp;

}

int Num ( LinkList L ) {

if (L->next== NULL ) return 0;

return 1+ Num (L->next);

}

float Avg ( LinkList L , int n ) {

LinkList f=L->next;

if ( f ->next == NULL )

{ n = 1; return ( float ) (f ->data ); }

else {

float Sum = Avg ( f , n-1 )*(n-1); ; return ( f ->data + Sum ) / n; } }

int main(){

LinkList L;

int n;

cout<<"n=?";

cin>>n;

if(n<=0){cout<<"n 无效,程序终止执行！"<<endl;exit(1);}

CreateList_L(L,n);

cout<<Max(L)<<endl;

cout<<Num(L)<<endl;

cout<<Avg(L,n)<<endl;

return 0;

}