C# · 12月 20, 2021

栈-链式栈-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;

}

}