数据结构-005-栈-链栈

╰+哭是因爲堅強的太久メ 2022-11-28 10:35 281阅读 0赞

## 链栈的定义 ##

链式堆栈分为带头结点的链式堆栈和不带头结点的**链式堆栈**。堆栈的链式存储表示称为链式堆栈，简称链栈。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]

**带头节点的链栈**

typedef struct SNode{
        	
    	DataType data;	
    	struct SNode* next;
    }SNode, *LinkStack;

# 1、初始化链栈 #

int InitStack(LinkStack *top){
        
    	*top=(LinkStack)malloc(sizeof(SNode));
    	if(*top==NULL){
        printf("初始化链栈出错！\n");return 0;}
    	(*top)->next=NULL;
    	return 1;
    }

# 2、判断链栈是否为空 #

int StackEmpty(LinkStack top){
        
    	if(top->next==NULL)	return 1;
    	else	return 0;
    }

# 3、入栈 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]

**操作步骤：**

1.  生成新结点。
2.  在栈顶位置插入新结点。

int Push(LinkStack top,DataType e){
        
    	SNode *p;
    	p=(SNode*)malloc(sizeof(SNode));	/*生成新结点*/
    	if(!p){
        printf("入栈操作出错！\n");return 0;
    	}
    	p->data=e;
    	p->next=top->next;/*在栈顶位置插入新结点*/
    	top->next=p;
    	return 1;
    }

# 4、出栈 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 2]

int Pop(LinkStack top,DataType* e){
        
    	SNode *p;
    	if(!top->next){
        
    		printf("栈已空，无法完成出栈操作！\n");	return 0;}
    	p=top->next;
    	top->next=p->next;		/*删除栈顶结点*/
    	*e=p->data;
    	free(p);	/*释放被删结点所占的内存空间*/
    	return 1;
    }

# 5、取栈顶元素 #

int GetTop(LinkStack top,DataType* e){
        
    	SNode *p;
    	if(!top->next){
        
    		printf("栈已空，无法完成取栈顶元素操作！\n");
    		return 0;
    	}
    	p=top->next;	
    	*e=p->data;	
    	return 1;
    }

# 6、销毁链栈 #

int Destroy(LinkStack top){
        
    	SNode *p;
    	while(top) {
         	/*依次删除所有结点*/
    		p=top;
    		top=top->next;
    		free(p);		
    	}
    	return 1;
    }

**例题**：  
例3-6】若有一个不带头结点的链式堆栈，请设计其入栈和出栈算法。  
思路：与带头结点的链栈区别——不带头结点的链栈为空的条件是栈顶指针为空；入栈后，需移动top指针使其指向新的栈顶；出栈后，需移动top指针使其指向新的栈顶。

int Push(LinkStack *top,DataType e){
        
    	SNode *p=(SNode*)malloc(sizeof(SNode));
    	if(!p){
        printf("入栈操作出错！\n");return 0;}
    	p->data=e;
    	p->next=*top;	/*插入*/
    	*top=p;		/*移动栈顶指针*/
    	return 1;}

int Pop(LinkStack top,DataType* e){
        
    	SNode *p;
    	if(!top) {
         			/*堆栈为空*/
    		printf("栈已空，无法完成出栈操作！\n");	return 0;}
    	p=top;		/*p指向栈顶元素*/	
    	*e=p->data;
        top=top->next;	/*移动栈顶指针*/
    	free(p);		/*释放栈顶结点*/
    	return 1;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9962edca12f142109db809f910c40114.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/8153b4d89834429f94b037eb7a627458.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/b9116d627f724542aa6889288d04a3ba.png