C语言实现数据结构中的链栈

短命女 2022-09-18 08:52 237阅读 0赞

实现方式一  
\# include <stdio.h>  
\# include <stdlib.h>  
typedef char NodeData;  
//链栈  
typedef struct Node  
\{  
 NodeData data;  
 struct Node \*next;  
\}StackNode;  
typedef struct  
\{  
 StackNode \*top;  
\}  
LinkStack;

/\*置栈空\*/  
void initStack(LinkStack \*ls)  
\{  
 ls->top=NULL;  
\}  
/\*判栈空\*/  
int isStackEmpty(LinkStack \*ls)  
\{  
 return ls->top==NULL;  
\}  
/\*进栈\*/  
void pushStack(LinkStack \*ls,NodeData nodedata)  
\{  
 StackNode \*p;  
 p=(StackNode \*)malloc(sizeof(StackNode));  
 p->data=nodedata;  
 p->next=ls->top;  
 ls->top=p;  
\}  
/\*出栈\*/  
NodeData popStack(LinkStack \*ls)  
\{  
 StackNode \*p=ls->top;  
 NodeData popNode=ls->top->data;  
 ls->top=ls->top->next;  
 free(p);  
 return popNode;  
\}

/\*打印栈\*/  
void printStack(LinkStack \*ls)  
\{  
    int i=0;  
 StackNode \*node;  
 node=ls->top;  
 while(node->next!=NULL)  
 \{  
  node=node->next;  
  printf("LinkStack Node %d is %c/n",i,node->data);  
  i++;  
 \}  
\}

void main()  
\{  
 LinkStack \*ls;  
 char inData;  
 ls=(LinkStack \*)malloc(sizeof(LinkStack));  
 initStack(ls);  
 //入栈  
    printf("Please input data/n");  
    while(inData!='/n')  
    \{  
   scanf("%c",&inData);  
   pushStack(ls,inData);  
   printf("push %c to stack/n",inData);  
    \}  
 printf("print linkStack:/n");  
 //打印栈元素  
    printStack(ls);  
 printf("pop stack/n");  
 //出栈  
 popStack(ls);  
 printStack(ls);  
 printf("pop stack/n");  
 //出栈  
 popStack(ls);  
 printStack(ls);  
\}

实现方式二  
只定义了栈节点  
\# include <stdio.h>  
\# include <stdlib.h>  
  
typedef char NodeData; //节点数据  
typedef struct Node  
\{  
 NodeData data;//节点数据  
 struct Node \* next;  //指向下一个节点的指针  
\}StackNode;

/\*置栈空\*/  
StackNode \* initStack(StackNode \*top)  
\{  
 top=NULL;  
 return top;  
\}  
/\*入栈 (这里很容易出错,需要返回头接点的指针否则每次入参都是指向同一个接点的地址而不是头指针的地址)\*/  
StackNode \* pushStack(StackNode \*top,NodeData nodedata)  
\{  
 StackNode \*p;  
 p=(StackNode \*)malloc(sizeof(StackNode));  
 p->data=nodedata;  
 p->next=top;  
 top=p;  
 return top;  
\}

/\*打印栈\*/  
void printStack(StackNode \*top)  
\{  
    int i=0;  
 StackNode \*node;  
 node=top;  
 while(node->next!=NULL)  
 \{  
  node=node->next;  
  printf("LinkStack Node %d is %c/n",i,node->data);  
  i++;  
 \}  
\}

void main()  
\{  
 StackNode \*top;  
 NodeData inData;  
 top=(StackNode \*)malloc(sizeof(StackNode));  
 top=initStack(top);  
 printf("Please input data/n");  
 while(inData!='/n')  
 \{  
  scanf("%c",&inData);  
  top=pushStack(top,inData);  
  printf("push the %c to stack/n",inData);  
 \}  
 printStack(top);  
\}  
  
实现方式一 中LinkStack结构类型的定义是为了方便在函数体中修改top指针本身  
通过修改指向LinkStack的top指针来控制入栈和出栈.

实现方式二 通过每次修改头指针并返回给入参来控制入栈和出栈.

方式一是通过指针参数修改指针所指内容的典型用法.  
方式二是通过函数返回值改变入参内容的典型用法。