A - 数据结构实验之栈与队列一：进制转换
Description
输入一个十进制非负整数，将其转换成对应的 R (2 <= R <= 9) 进制数，并输出。
Input
第一行输入需要转换的十进制非负整数；
第二行输入 R。
Output
输出转换所得的 R 进制数。
Sample
Input?
1279
8
Output?
2377
顺序栈方法
#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef struct
{
int *base;
int *top;
int len;
}stack;
stack initstack()
{
stack s;
s.top=(int *)malloc(N * sizeof(int));
s.base=s.top;
s.len=0;
return s;
}
int pop(stack *s)
{
int e;
e=*(s->top-1);
s->top--;
s->len--;
return e;
}
void push(stack *s,int x)
{
*(s->top)=x;
s->top++;
s->len++;
}
int main()
{
int n,m;
stack s;
scanf("%d %d",&n,&m);
s=initstack();
if(n==0)
{
push(&s,n);
}
while(n)
{
push(&s,n%m);
n/=m;
}
while(s.len)
{
printf("%d",pop(&s));
}
return 0;
}
链栈方法
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
Node *next;
}node;
typedef struct Stack
{
node *top;
node *base;
}stack;
node *creatnode()
{
node *p;
p=(node *)malloc(sizeof(node));
p->next=NULL;
return p;
}
stack *creatstack()
{
stack *p;
p=(stack *)malloc(sizeof(stack));
p->top=creatnode();
p->base=p->top;
return p;
}
int pop(stack *p)
{
int n;
node *t;
n=p->top->next->data;
t=p->top->next;
p->top->next=p->top->next->next;
free(t);
return n;
}
void push(stack *p,int n)
{
node *t;
t=creatnode();
t->data=n;
t->next=p->top->next;
p->top->next=t;
}
void print(stack *p)
{
while(p->top->next)
{
printf("%d",pop(p));
}
}
int main()
{
int n,m;
stack *t;
t =creatstack();
scanf("%d %d",&n,&m);
if(n==0)
{
push(t,n);
}
while(n)
{
push(t,n%m);
n/=m;
}
print(t);
return 0;
}
B - 数据结构实验之栈与队列二：一般算术表达式转换成后缀式
Description
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。
Input
输入一个算术表达式，以‘#’字符作为结束标志。
Output
输出该表达式转换所得到的后缀式。
Sample
Input?
a*b+(c-d/e)*f#
Output?
ab*cde/-f*+
?链栈
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
char data;
Node *next;
}node;
typedef struct Stack
{
node *top;
node *base;
}stack;
node *creatnode()
{
node *p;
p=(node *)malloc(sizeof(node));
p->next=NULL;
return p;
}
stack *creatstack()
{
stack *s;
s=(stack *)malloc(sizeof(stack));
s->top=creatnode();
s->base=s->top;
return s;
}
void pop(stack *p)
{
node *t;
t=p->top->next;
p->top->next=p->top->next->next;
free(t);
}
char top(stack *p)
{
char t;
t=p->top->next->data;
return t;
}
void push(stack *p,char n)
{
node *t;
t=creatnode();
t->data=n;
t->next=p->top->next;
p->top->next=t;
p->base=t;
}
int empty(Stack *t)
{
if(t->top->next==NULL)
{
return 0;
}
return 1;
}
void print(stack *p)
{
while(empty(p))
{
printf("%c",top(p));
pop(p);
}
}
int main()
{
stack *t;
char s[1000];
scanf("%s",s);
t = creatstack();
for(int i=0;s[i]!='#';i++)
{
if(s[i]=='(')
push(t,s[i]);
else if(s[i]==')')
{
while(top(t)!='(')
{
printf("%c",top(t));
pop(t);
}
pop(t);
}
else if(s[i] == '+' || s[i] == '-')
{
if(!empty(t) || top(t) == '(')
{
push(t,s[i]);
}
else
{
printf("%c",top(t));
pop(t);
push(t,s[i]);
}
}
else if(s[i] == '*' || s[i] == '/')
{
if(!empty(t)|| top(t) == '(' || top(t) == '+' || top(t) == '-')
{
push(t,s[i]);
}
else
{
printf("%c",top(t));
pop(t);
}
}
else
{
printf("%c",s[i]);
}
}
print(t);
return 0;
}
顺序栈
#include<stdio.h>
#include<stdlib.h>
typedef struct Stack
{
char *top;
char *base;
char len;
}stack;
stack creatstack()
{
stack s;
s.top=(char *)malloc(100000 * sizeof(char));
s.base=s.top;
s.len=0;
return s;
}
void pop(stack *p)
{
p->top--;
p->len--;
}
char top(stack p)
{
return *(p.top-1);
}
void push(stack *p,char n)
{
*(p->top)=n;
p->top++;
p->len++;
}
int empty(stack t)
{
if(!t.len)
{
return 0;
}
else
{
return 1;
}
}
void print(stack p)
{
while(empty(p))
{
printf("%c",top(p));
pop(&p);
}
}
int main()
{
stack t;
char s[1000];
scanf("%s",s);
t = creatstack();
for(int i=0;s[i]!='#';i++)
{
if(s[i]=='(')
push(&t,s[i]);
else if(s[i]==')')
{
while(top(t)!='(')
{
printf("%c",top(t));
pop(&t);
}
pop(&t);
}
else if(s[i] == '+' || s[i] == '-')
{
if(!empty(t) || top(t) == '(')
{
push(&t,s[i]);
}
else
{
printf("%c",top(t));
pop(&t);
push(&t,s[i]);
}
}
else if(s[i] == '*' || s[i] == '/')
{
if(!empty(t)|| top(t) == '(' || top(t) == '+' || top(t) == '-')
{
push(&t,s[i]);
}
else
{
printf("%c",top(t));
pop(&t);
}
}
else
{
printf("%c",s[i]);
}
}
print(t);
return 0;
}
|