栈的实现和应用

《栈的实现和应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1栈(基于顺序表)typedefintS_DataType;typedefstructunsignedmax;unsignedtop;S_DataType*ptr;}Stack;voidS_init(Stack*ps){ps->max=8;ps->top=0;ps->ptr=(S_DataType*)malloc(sizeof(S_DataType)*ps->max);}voidS_clear(Stack*ps){ps->max=ps->top=0;if(ps->ptr)free(ps->ptr);ps->p

2、tr=0;}〃测试是否空intS_isEmpty(Stacks){returns.top==0;}voidS_push(Stack*ps,S_DataTypevalue){unsignedi;if(ps->top==ps->max){S_DataType*new_ptr=(S_DataType*)malloc(sizeof(S_DataType):}:ps->max*2);for(i=0;itop;++i)new_ptr[i]=ps->ptr[i];ps->max*=2;free(ps->ptr);

3、ps->ptr=new_ptr;}ps->ptr[ps->top++]=value;intS_pop(Stack*ps){if(ps->top==0)return0;~ps->top;return1;}intS_getTop(Stacks,S_DataType*p_value){if(s.top==0)return0;*p_value=s.ptr[s.top-1J;return1;}2栈的实现(基于链表)typedefintS_DataType;typedefstructN{S_DataTypedata;st

4、ructN*next;}node;node*make_node(S_DataTypedata){node*np=(node*)malloc(sizeof(node));np->next=0;np->data=data;returnnp;}typedefstruct{node*top;[Stack;voidS_init(Stack*ps){ps->top=0;}voidS_clear(Stack*ps)while(ps->top)node*del=ps->top;ps->top=dek>next;free(de

5、l);}}〃测试是否空intS_isEmpty(Stacks){returns.top==0;}voidS_push(Stack*ps,S_DataTypevalue){node*np=make_node(value);np->next=ps->top;ps->top=np;}intS_pop(Stack*ps){node*del=ps->top;if(ps->top==0)return0;ps->top=del->next;free(del);return1;}intS_getTop(Stacks,S_Da

6、taType*p_value){if(s.top==0)return0;*p_value=s.top->data;return1;}3栈的应用：n皇后voidprint(int**arr,intn){inti,j;for(i=0;i

7、

8、k-i+j>=0&&a

9、rr[k][k-i+j]==l

10、

11、i+j-k

12、][j]=O;i二j=0;while(l){for(;j

13、

14、i==n)if(i==n)printf(u第％(1解：",4-4-count);print(arr,n);)・・i；if(i<0)break;S_getTop(s,&j);S_pop(&s);arr[