数据结构习题集作业代码（第三章）

Description

试写一算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不包含字符“&”，且序列2是序列1的逆序列。例如，“a+b&b+a”是属于该模式的字符序列，而“1+3&3-1”则不是。

Input
输入字符序列

Output
如果序列符合模式则输出1,不符合则输出0

#include
#include
#include
char a[1001];
char b[1001];
void reverse(char *a){
    int len=strlen(a),i;
    char c[1001];
    for(i=0;i
        c[i]=a[len-i-1];
    }
    for(i=0;i
        a[i]=c[i];
    }
}
char c;
int flag=0,cnt=0;
int main(){
    char * now=a;
    while((c=getchar())!='@'){
        if(c=='&'){
            if(flag==1){
                printf("0");
                return 0;
            }
            else{
                flag=1;
                now[cnt]='';
                now=b;
                cnt=0;
            }
        }
        else now[cnt++]=c;
    }
    if(flag==0){
        printf("0");
        return 0;
    }
//    printf("%s %sn",a,b);
    now[cnt++]='';
    reverse(b);
    if(strcmp(a,b)==0){
        printf("1");
    }
    else{
        printf("0");
    }
    return 0;
}

Description

试写一个判别表达式中开,闭括号是否配对出现的算法。

比如:'(a+b(c-d))‘是配对出现的,而’(d-e))'不是配对出现的。

Input
表达式,如:'a+b(c-d)’

Output
表达式中的括号是否配对出现,是则输出1,否则输出0

#include
#include
#include
char s[10000];
int main(){
	while(scanf("%s",s)!=EOF){
		int cnt=0,i,GG=0;
		int len=strlen(s);
		for(i=0;i
			if(s[i]=='(')cnt++;
			if(s[i]==')'){
				if(cnt)cnt--;
				else GG=1;
			}
		}
		if(cnt)GG=1;
		if(GG)printf("0n");
		else printf("1n");
	}
	return 0;
}

Description

假设表达式由单字母变量和双目四则运算符构成.试写一个算法,将一个通常书写形式且书写正确的表达式转换为逆波兰式.

Input
常规运算表达式

Output
逆波兰式

#include
#include
#include
int OPERATE[7][7]={{0, 0, 0, 0, 0, 0, 0},
                   {0, 1, 1,-1,-1,-1, 1},
                   {0, 1, 1,-1,-1,-1, 1},
                   {0, 1, 1, 1, 1,-1, 1},
                   {0, 1, 1, 1, 1,-1, 1},
                   {0,-1,-1,-1,-1,-1, 0},
                   {1, 1, 1, 1, 1, 0, 1}
                  };
int mapping(char c){
    int opt=0;
    switch (c){
        case '+': 
			opt=1; break;
        case '-': 
			opt=2; break;
        case '*': 
			opt=3; break;
        case '/':
			opt=4; break;
        case '(': 
			opt=5; break;
        case ')': 
			opt=6; break;   
	} 
    return opt;
}
typedef struct Stack{
    int s[1000];
    int top;
}Stack, *StackPointer;
typedef StackPointer SP;
SP OPTR,OPND;
SP init(){
    SP ret=malloc(sizeof(Stack));
    memset(ret,0,sizeof(Stack));
    ret->top=-1;
    return ret;
}
int top(SP now){
    return now->s[now->top];
}
void pop(SP now){
    now->top--;
}
void ins(SP now,int x){
    now->s[++now->top]=x;
}
int empty(SP now){
    return (now->top==-1);
}
int i;
char s[10000+10];
void reverse(char *a){
    int len=strlen(a),i;
    char c[1001];
    for(i=0;i
        c[i]=a[len-i-1];
    }
    for(i=0;i
        a[i]=c[i];
    }
}
int main(){
    OPTR=init();
    OPND=init();
    scanf("%s",s);
    int len=strlen(s);
    for(i=0;i
        if((s[i]>='A'&&s[i]<='Z')||(s[i]>='a'&&s[i]<='z')){
            ins(OPND,s[i]);
        }
        else{
            int opt=mapping(s[i]);
//            printf("%dn",opt);
			while(1){
	            if(empty(OPTR)){
	                ins(OPTR,s[i]);
	                break;
	            }
	            else{
	                if(opt==6){
	                    while(mapping(top(OPTR))!=5){
	                        ins(OPND,top(OPTR));
	                        pop(OPTR);
	                    }
	                    pop(OPTR);
	                    break;
	                }
	                int now=mapping(top(OPTR));
	                if(OPERATE[now][opt]==1){
	                    ins(OPND,top(OPTR));
	                    pop(OPTR);
	                }
	                else{
	                    ins(OPTR,s[i]);
	                    break;
	                }
	            }				
			}
        }
    }
    while(!empty(OPTR)){
//    	printf("%cn",top(OPTR));
        ins(OPND,top(OPTR));
        pop(OPTR);
    }
    char ans[1000+10];
    int idx=0;
    while(!empty(OPND)){
        ans[idx++]=top(OPND);
        pop(OPND);
    }
    ans[idx]='';
    reverse(ans);
    printf("%s",ans);
    return 0;
}

Description

试编写如下定义的递归函数的递归算法，并根据算法画出求ｇ(5, 2)时栈的变化过程。

g(m, n) = 0 (m = 0, n>=0) g(m, n) = g(m-1, 2n) + n (m>0, n>=0)

Input
输入ｍ与n的数值，中间以逗号隔开

Output
递归计算后，g(m, n)的值

#include
int G(int m,int n){
	if(m==0)return 0;
	return G(m-1,2*n)+n;
}
int n,m;
int main(){
	scanf("%d,%d",&m,&n);
	printf("%d",G(m,n));
	return 0;
}

Description

试写出求递归函数Ｆ(n)的递归算法，并消除递归:

F(n ) = n + 1 (n = 0)

F(n) = n * F(n / 2) (n > 0)

Input
输入非负整数ｎ

Output
计算出的F(n)函数的值

#include
#include
#include
typedef struct StackNode{
	int n;
	struct StackNode * next;
}StackNode,*top;
struct StackNode * init(int n){
	struct StackNode * top=malloc(sizeof(StackNode));
	memset(top,0,sizeof(StackNode));
	top->n=n;
	top->next=NULL;
	return top;
}
struct StackNode * ins(struct StackNode * top,int n){
	if(top==NULL)return init(n);
	struct StackNode * pre=top;
	struct StackNode * now=malloc(sizeof(StackNode));
	memset(now,0,sizeof(StackNode));
	now->n=n;
	now->next=NULL;
	while(pre->next!=NULL){
		pre=pre->next;
	}
	pre->next=now;
	return top;
}
int empty(struct StackNode * top){
	return top==NULL;
}
int Top(struct StackNode * top){
	return top->n;
}
struct StackNode * Pop(struct StackNode * top){
	if(empty(top))return NULL;
	struct StackNode * ret=top->next;
	free(top);
	return ret;
}
int n;
int main(){
	struct StackNode * top=NULL;
	scanf("%d",&n);
	while(n){
		top=ins(top,n);
		n>>=1;
	}
	int ans=1;
	while(!empty(top)){
		ans=ans*Top(top);
		top=Pop(top);
	}
	printf("%d",ans);
	return 0;
}

Description

假设称正读和反读都相同的字符序列为"回文",例如,'abba’和’abcba’是回文，

而’abcde’和’ababab’则不是回文。

试写一个算法判别读入的一个以’@'为结束符的字符序列是否为回文。

Input
输入字符串，以@结尾

Output
是回文则输出1，否则输出0

#include
#include
#include
void judge(char s[]){
	int len=strlen(s),i;
	for(i=0;i
		if(s[i]!=s[len-1-i]){
			printf("0n");
			return;	
		} 
	}
	printf("1n");
	return;
}
char c;
char s[10000+10];
int main(){
	while((c=getchar())!=EOF){
		int len=0;
		memset(s,0,sizeof(s));
		for(;;c=getchar()){
			if(c=='@'){
				s[len]='';
				c=getchar();
				judge(s);
				break;
			}
			else{
				s[len++]=c;
			}
		}
	}
	return 0;
}