c语言队列栈程序

#define STACK_INIT_SIZE 10 #define STACKIMCREMENT 2 typedef struct { int *base; int *top; int stacksize; }sqstack;

void initstack(sqstack *s)

{s->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));

if(!s->base) exit(0); s->top=s->base;

s->stacksize=STACK_INIT_SIZE; }

void gettop(sqstack s,int *e) {if(s.base==s.top) return; *e=*(s.top-1); }

void push(sqstack *s,int e)

{if(s->base-s->top>=s->stacksize)

{s->base=(int*)realloc(s->base,(s->stacksize+STACKIMCREMENT)*sizeof(int)); if(!s->base) exit(-2);

s->top=s->base+s->stacksize;

s->stacksize+=STACKIMCREMENT; }

*s->top++=e; }

void pop(sqstack *s,int *e) {if(s->base==s->top) return; *e=*--s->top; }

char precede(char t1,char t2){ char f; switch(t2){ case '+': case '-':

if(t1=='('||t1=='#') f='<'; else f='>'; break; case '*': case '/':

if(t1=='*'||t1=='/'||t1==')') f='>'; else f='<'; break; case '(':

if(t1==')'){

printf(\"error1\\n\"); exit(0); }

else f='<'; break; case ')':

switch(t1){

case '(':f='=';break; case

'#':{printf(\"error2\\n\");exit(0);} default:f='>'; }

break; case '#':

switch(t1){ case

'(':{printf(\"error3\\n\");exit(0);} case '#':f='='; default:f='>'; }

break; }

return f; }

int in(char c){ switch(c){ case '+':

case '-': case '*': case '/': case '(': case ')':

case '#':return 1; default:return 0; } }

int operate(int a,char theta,int b){ int c;

switch(theta){

case '+':c=a+b;break; case '-':c=a-b;break; case '*':c=a*b;break; case '/':c=a/b;break; }

return c; }

int evaluateexpression(){ sqstack optr,opnd; int a,b,i=0,x; int d;

char c,theta; char z[6];

c=getchar();

}while(c>='0'&&c<='9'); //z[i]=0; d=atoi(z);

push(&opnd,d); } else{

printf(\"error4\\n\"); exit(0); }

gettop(optr,&x); }

gettop(opnd,&x); return x; }

void main(){

initstack(&optr); push(&optr,'#'); initstack(&opnd);c=getchar(); gettop(optr,&x); while(c!='#'||x!='#'){ if(in(c)){

switch(precede(x,c)){ case '<':

push(&optr,c); c=getchar(); break; case '=':

pop(&optr,&x); c=getchar(); break; case '>':

pop(&optr,&theta); pop(&opnd,&b); pop(&opnd,&a);

push(&opnd,operate(a,theta,b)); break; } }

else if(c>='0'&&c<='9'){ i=0;

do{z[i]=c; i++;

printf(\"input expressions end with '#'\\n\");

printf(\"------------------------------\\n\");

printf(\"reslut=%d\\n\;

printf(\"------------------------------\\n\"); }

2.串的代码

#include typedef struct { char *ch; int length; }hstring;

void init(hstring *t){

(*t).ch=NULL; (*t).length=0; }

void strassign(hstring *t,char *chars){ int i,j; char *c;

if(t->ch) free(t->ch);

for(i=0,c=chars;*c;i++,c++); if(!i){

t->ch=NULL; t->length=0; } else{

t->ch=(char*)malloc(sizeof(char)*i); if(!t->ch)

exit(0); for(j=0;jlength=i; } }

void strcopy(hstring *t,hstring s){ int i;

if(t->ch) free(t->ch);

t->ch=(char*)malloc(sizeof(char)*s.length); for(i=0;ich[i]=s.ch[i]; t->length=s.length; }

int strempty(hstring s){

if(s.ch==NULL&&s.length==0) return 1; else

return 0; }

int strcompare(hstring s,hstring t){ int i;

for(i=0;ireturn s.ch[i]-t.ch[i]; return s.length-t.length; }

int strlength(hstring s){ return s.length; }

void clearstring(hstring *s){ if(s->ch)

{free(s->ch);s->ch=NULL;} s->length=0; }

void concat(hstring *t,hstring s1,hstring s2){

int i; if(t->ch)

free(t->ch);

t->ch=(char*)malloc(sizeof(char)*(s1.length+s2.length)); if(!t->ch) exit(0);

for(i=0;ich[i]=s1.ch[i]; for(i=0;it->ch[i+s1.length]=s2.ch[i]; t->length=s1.length+s2.length; }

void substring(hstring *sub,hstring s,int pos,int len){ int i;

if(sub->ch)

free(sub->ch);

if(pos<1||pos>s.length||len<0||len>s.length-pos+1)

return;

sub->ch=(char*)malloc(sizeof(char)*len); if(!sub->ch) exit(0);

for(i=pos-1;ich[i-pos+1]=s.ch[i]; sub->length=len; }

int index(hstring s,hstring t,int pos){ int m,n,i; hstring sub; init(&sub); if(pos>0){

n=s.length;m=t.length;i=pos; while(i<=n-m+1){

substring(&sub,s,i,m); if(strcompare(sub,t)!=0) i++; else

return i; } }

return 0; }

void strinsert(hstring *s,int pos,hstring t){ int i;

if(pos<1||pos>s->length+1) return; if(t.length){

s->ch=(char*)realloc(s->ch,sizeof(char)*(s->length+t.length)); if(!s->ch) exit(0);

for(i=s->length-1;i>=pos-1;i--) s->ch[t.length+i]=s->ch[i]; for(i=0;is->ch[i+pos-1]=t.ch[i]; s->length+=t.length; } }

void strdelete(hstring *s,int pos ,int len){ int i;

if(pos<1||pos>s->length-len+1) return;

for(i=pos+len-1;ilength;i++) s->ch[i-len]=s->ch[i]; s->length-=len;

s->ch=(char*)realloc(s->ch,sizeof(char)*s->length); } void replace(hstring *s,hstring t,hstring v){ int i=1;

if(strempty(t)) return; do{

i=index(*s,t,i); if(i>0){

strdelete(s,i,t.length); strinsert(s,i,v); i+=v.length; } }while(i); }

void strprint(hstring t){ int i;

for(i=0;imain() { int i;

hstring t,s1,s2,s3,s4,s5; char

c,*a=\"aa\bccaa\";

init(&s1); init(&s2); init(&s3); init(&s4); init(&s5); init(&t);

strassign(&s1,p); printf(\"s1:\"); strprint(s1);

printf(\"s1/length:%d/empty(1 :Yes):%d\\n\",strlength(s1),strempty(s1)); strcopy(&s3,s1);

printf(\"copy/s1->s3:\"); strprint(s3);

strassign(&s2,q); printf(\"s2:\");

strprint(s2);

i=strcompare(s1,s2); if(i<0) c='<';

else if(i==0) c='='; else c='>';

printf(\"s1%cs2\\n\ concat(&t,s1,s2);

printf(\"concat/s1+s2->t:\"); strprint(t);

strassign(&s4,a); printf(\"s4:\"); strprint(s4);

i=index(s2,s4,1);printf(\"index/s2/s4/1:%d\\n\

i=index(s2,s4,3);printf(\"index/s2/s4/3:%d\\n\

strinsert(&s1,2,s4);

printf(\"insert/s1/2/s4:\"); strprint(s1);

strdelete(&s1,2,3);

printf(\"delete/s1/2/3:\"); strprint(s1);

strassign(&s5,b); printf(\"s5:\"); strprint(s5);

replace(&t,s4,s5);

printf(\"replace/s4/s5:\"); strprint(t);

clearstring(&s1); printf(\"clear/s1:\"); strprint(s1);

printf(\"s1/length:%d/empty(1 :Yes):%d\\n\",strlength(s1),strempty(s1)); } 2.

#include

#define MAXSTRLEN 20

typedef char sstring[MAXSTRLEN+1];

void strassign(sstring t,char *chars){ int i;

if(strlen(chars)>MAXSTRLEN) return;

t[0]=strlen(chars); for(i=0;i<=t[0];i++){ t[i+1]=chars[i]; } }

void strcopy(sstring s,sstring t){ int i;

for(i=0;i<=t[0];i++) s[i]=t[i]; }

int strempty(sstring s){ if(s[0]==0) return 1; else return 0; }

int strcompare(sstring s,sstring t){ int i;

for(i=1;i<=s[0]&&i<=t[0];i++){ if(s[i]!=t[i]) return s[i]-t[i]; }

return s[0]-t[0]; }

int strlength(sstring s){ return s[0]; }

void clearstring(sstring s){ s[0]=0; }

int concat(sstring t,sstring s1,sstring s2){ int i;

if(s1[0]+s2[0]<=MAXSTRLEN){ for(i=1;i<=s1[0];i++) t[i]=s1[i];

for(i=1;i<=s2[0];i++) t[s1[0]+i]=s2[i]; t[0]=s1[0]+s2[0]; } else{

for(i=1;i<=s1[0];i++) t[i]=s1[i];

for(i=1;i<=MAXSTRLEN-s1[0];i++)

t[s1[0]+i]=s2[i]; t[0]=MAXSTRLEN; } }

void substring(sstring sub,sstring s,int pos,int len){ int i;

if(pos<1||pos>s[0]||len<0||len>s[0]-pos+1) return;

for(i=1;i<=len;i++) sub[i]=s[pos+i]; sub[0]=len; }

int index(sstring s,sstring t,int pos){ int i,j;

if(pos<0||pos>s[0]) return 0; i=pos; j=1;

while(i<=s[0]&&j<=t[0]){ if(s[i]==t[j]){i++;j++;} else{i=i-j+2;j=1;} }

if(j>t[0])

return i-t[0]; else

return 0; }

int strinsert(sstring s,int pos,sstring t){ int i;

if(pos<1||pos>s[0]+1) return 0;

if(s[0]+t[0]<=MAXSTRLEN){ for(i=s[0];i>=pos;i--) s[i+t[0]]=s[i];

for(i=pos;i<=pos+t[0]-1;i++) s[i]=t[i-pos+1]; s[0]+=t[0]; } else{ for(i=MAXSTRLEN;i>=MAXSTRLEN-t[0];i++)

s[i]=s[i-t[0]];

for(i=pos;i<=pos+t[0]-1;i++) s[i]=t[i-pos+1];

s[0]=MAXSTRLEN; } }

int strdelete(sstring s,int pos, int len){ int i;

if(pos<1||pos>s[0]-len+1) return 0;

for(i=pos+len;i<=s[0];i++) s[i-len]=s[i]; s[0]-=len; }

void replace(sstring s,sstring t,sstring v){ int i=1;

if(strempty(t)) return; do{

i=index(s,t,i); if(i){

strdelete(s,i,t[0]); strinsert(s,i,v); i+=v[0]; } }while(i); }

void strprint(sstring s){ int i;

for(i=1;i<=s[0];i++){ printf(\"%c\ }

printf(\"\\n\"); }

main(){

sstring s1,s2,s3,s4,s5,t; char

c,*a=\"aa\bccaa\";

int i;

strassign(s1,p); printf(\"s1:\"); strprint(s1);

printf(\"s1/length:%d/empty(1 :Yes):%d\\n\",strlength(s1),strempty(s1)); strcopy(s3,s1);

printf(\"copy/s1->s3:\"); strprint(s3); strassign(s2,q); printf(\"s2:\"); strprint(s2);

i=strcompare(s1,s2); if(i<0) c='<';

else if(i==0) c='='; else c='>';

printf(\"s1%cs2\\n\ concat(t,s1,s2);

printf(\"concat/s1+s2->t:\"); strprint(t); strassign(s4,a); printf(\"s4:\"); strprint(s4);

i=index(s2,s4,1);printf(\"index/s2/s4/1:%d\\n\

i=index(s2,s4,3);printf(\"index/s2/s4/3:%d\\n\

strinsert(s1,2,s4);

printf(\"insert/s1/2/s4:\"); strprint(s1); strdelete(s1,2,3);

printf(\"delete/s1/2/3:\"); strprint(s1); strassign(s5,b); printf(\"s5:\"); strprint(s5); replace(t,s4,s5);

printf(\"replace/s4/s5:\"); strprint(t); clearstring(s1); printf(\"clear/s1:\"); strprint(s1);

printf(\"s1/length:%d/empty(1 :Yes):%d\\n\",strlength(s1),strempty(s1)); }

3.队列的代码： #include #include #include

typedef struct qnode{ int data;

struct qnode *next; }qnode,*queueptr;

typedef struct{

queueptr front; queueptr rear; }linkqueue;

void initqueue(linkqueue *q){

q->front=q->rear=(queueptr)malloc(sizeof(qnode));

if(!q->front) exit(-2); q->front->next=NULL; }

void destroyqueue(linkqueue *q){ while(q->front){

q->rear=q->front->next; free(q->front); q->front=q->rear; } }

void clearqueue(linkqueue *q){ queueptr p,r;

q->rear=q->front; p=q->front->next;

q->front->next=NULL;

while(p){ r=p;

p=p->next; free(r);

} }

int queueempty(linkqueue q){ if(q.front==q.rear) return 1; else return 0; }

int queuelength(linkqueue q){ queueptr p; int i=0; p=q.front;

while(p!=q.rear){ i++;

p=p->next; }

return i; }

void gethead(linkqueue q,int *e){ queueptr p;

if(q.front==q.rear) return; p=q.front->next; *e=p->data; }

void enqueue(linkqueue *q,int e){ queueptr p;

p=(queueptr)malloc(sizeof(qnode)); if(!q) exit(-2); p->data=e;

p->next=NULL; q->rear->next=p; q->rear=p; }

void dequeue(linkqueue *q,int *e){ queueptr p;

if(q->front==q->rear) return; p=q->front->next; *e=p->data;

q->front->next=p->next;

if(p==q->rear) q->rear=q->front; free(p); }

void queuetraverse(linkqueue q){ queueptr p;

p=q.front->next; printf(\"----------------------\\n\"); printf(\"data in queue:\"); while(p){

printf(\"%2d\ p=p->next; }

printf(\"\\n\");

printf(\"----------------------\\n\"); }

main(){

linkqueue q; int i,e;

initqueue(&q); printf(\"empty or not?(true:1,false :0)%2d\\n\);

for(i=0;i<7;i++){ enqueue(&q,i); }

queuetraverse(q); printf(\"empty or not?(true:1,false :0)%2d\\n\);

printf(\"insert data e:\"); scanf(\"%d\ enqueue(&q,e); queuetraverse(q); printf(\"length of queue:%2d\\n\ printf(\"after delete data:\"); dequeue(&q,&e);

printf(\"the delete num:%2d\\n\ queuetraverse(q); gethead(q,&e);

printf(\"dataof head qnode :%2d\\n\ printf(\"after clear:\\n\"); clearqueue(&q); printf(\"empty or not?(true:1,false :0)%2d\\n\);

printf(\"lengthofqueue:%2d\\n\(q));

destroyqueue(&q); }