栈-链式栈-C语言实现
#include #include #include #include typedef struct node{ //定义节点 int data; struct node *pnext; }NODE,*PNODE; typedef struct Stack{ PNODE pTop; //指向栈顶元素 PNODE pBottom; //指向栈低元素的下一个没有实际意义的元素,类似头结点 }STACK,*PSTACK;//PSTACK 等价于struct STACK * void init(PSTACK); void push(PSTACK,int); void traverse(PSTACK); bool pop(PSTACK,int *); void clear(PSTACK); int main(){ STACK S; //内存中已经有了一个栈但是没有初值所以是垃圾值 int val; init(&S);//创造一个空栈 push(&S,1); push(&S,2); traverse(&S); clear(&S); printf("after clearn"); pop(&S,&val); pop(&S,&val); if(pop(&S,&val)) { //pop(&S,&val);//val保存出栈的元素 printf("出栈成功succes,出栈元素是%dn",val); }else{ printf("出栈失败failern"); } } void init(PSTACK pS){ //造出头结点让top和bottom都指向这个头结点,空栈便是构造成功 //这个头结点中是个垃圾值 pS->pTop = (PNODE)malloc(sizeof(PNODE)); if(NULL == pS->pTop) { printf("动态内存分配失败n"); exit(-1); } else { //top 已经指向了一个节点,空栈top和bottom指向同一个节点 pS->pBottom = pS->pTop; //把节点的指针域置空 pS->pTop->pnext =NULL; //pS->Bottom->pnext =NULL; } } void push(PSTACK pS,int val){ //创造一个新的节点 PNODE pNew =(PNODE)malloc(sizeof(NODE)); pNew->data =val; pNew->pnext =pS->pTop;//新节点指向栈顶节点 pS->pTop = pNew; //top指针指向栈顶节点 return; } //遍历,制造一个节点指向栈顶元素,输出栈顶元素,节点后移 void traverse(PSTACK pS){ PNODE p =pS->pTop; while(p!=pS->pBottom) { printf("%dn",p->data); p= p->pnext; } printf("n"); return; } //判断栈空 bool empty(PSTACK pS){ if(pS->pTop == pS->pBottom) { return true; } else { return false; } } //出栈,把出栈元素存入pVal形参所指向的变量中如果出栈失败,返回false bool pop(PSTACK pS,int *pVal){ //pS本身存放的就是S的地址 if(empty(pS)) { return false; } else {//定义一个节点指向栈顶元素 PNODE r =pS->pTop; *pVal = r->data; //将元素的值赋给形参 pS->pTop=r->pnext;//将栈顶指针指向下一个元素 free(r);//释放栈顶节点 r=NULL; return true; } } //清空 void clear(PSTACK pS){ if(empty(pS)) { return; } else { PNODE p =pS->pTop; PNODE q= NULL; //PNODE q = p->pnext;//q指向p的下一个元素 while(p != pS->pBottom) { q = p->pnext; free(p); p=q; } pS->pTop = pS->pBottom; free(p); pS->pTop = p->pnext; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |