数据结构 - 链栈的基本操作(C语言)

喜欢ヅ旅行 2022-06-04 09:56 223阅读 0赞

**栈的特点**：先进后出。

**链栈**：

(1)：栈底即链表的最后一个结点，而栈顶总是链表的第一个结点。因此：新入栈元素即为链表新的第一个结点。

(2)：一个链栈可由栈顶指针top唯一确定。如下图给出了链栈中元素与top的关系。

(3)：采用带头节点的单链表实现栈。因为：链栈的插入和删除仅在表头位置进行，所以表头指针top就作为栈顶指针。

![Center][]

链栈的C语言定义为：

typedef int ElemType;
     
     typedef struct Stacknode
     {
     	ElemType data;
     	struct Stacknode *next;
     }LinkStackNode, *LinkStack;

入栈，出栈的思想就不叙述了。代码如下：

#include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    
     typedef int ElemType;
     
     typedef struct Stacknode
     {
     	ElemType data;
     	struct Stacknode *next;
     }LinkStackNode, *LinkStack;
     
     LinkStack Create_LinkStack();		/*头插法创建链栈.*/
     
     int Push_LinkStack(LinkStack top,ElemType x);		/*入栈*/
     
     ElemType Pop_Linkstack(LinkStack top);	/*出栈.*/
     
     void Print_LinkStack(LinkStack top);	/*打印栈内元素.*/
     
     int main()
     {
     	LinkStack top;
    	ElemType x;
    	/*----------------创建链栈并打印----------------*/ 
    	top=Create_LinkStack();
    	Print_LinkStack(top);
    	
    	/*--------------入栈并打印栈内元素--------------*/ 
    	printf("\n请输入入栈元素: ");
    	scanf("%d",&x);
    	Push_LinkStack(top,x);
    	printf("\n入栈后栈内元素如下：");
    	Print_LinkStack(top);
    	
    	/*--------------出栈并打印栈内元素--------------*/ 
    	x = Pop_Linkstack(top);
    	printf("\n出栈后栈内元素如下："); 
    	Print_LinkStack(top);
    	printf("\n");
    	
     	return 0;
     }
     
     LinkStack Create_LinkStack()		/*头插法创建链栈.*/
     {
     	printf("请输入链栈元素,按-1结束："); 
    	LinkStack top=(LinkStack)malloc(sizeof(LinkStackNode));
    	top->next=NULL;
    	LinkStackNode *s;
    	int x;
    	scanf("%d",&x);
    	while(x!=-1){
    		s=(LinkStack)malloc(sizeof(LinkStackNode));
    		s->data=x;			/*头插法创建的栈顺序刚好和输入顺序相反*/ 
    		s->next=top->next;
    		top->next=s;
    		scanf("%d",&x);
    	}
    	return top;
     }
     
     int Push_LinkStack(LinkStack top,ElemType x)		/*入栈*/
     {
     	LinkStack p=(LinkStack)malloc(sizeof(LinkStackNode));
    	if(p==NULL) return FALSE;
    	p->data=x;					/*头插法入栈,保证新入栈元素在栈顶位置.*/ 
    	p->next=top->next;
    	top->next=p;
    	return TRUE; 
     }
     
     ElemType Pop_Linkstack(LinkStack top)	/*出栈.*/
     {
     	LinkStack p;
     	ElemType x;		/*存放出栈元素*/ 
     	if(top->next == NULL) return NULL;		/*空栈*/
    	 p = top->next;
    	 top->next = p->next;
    	 x = p->data;
    	 free(p);
    	 return x;
     }
     
    void Print_LinkStack(LinkStack top)
    {
    	LinkStack p=top->next;
    	while(p!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }

运行结果如下：

![20171211110355405][]

小结：一点一滴，记录向前。

[Center]: /images/20220604/99720575dfed4041896813c289214448.png
[20171211110355405]: /images/20220604/112d4f59348945f4ac0e9579fbba449e.png