数据结构之链栈基本操作的实现详解（C语言描述）

布满荆棘的人生 2022-03-21 13:18 378阅读 0赞

1.链栈：就是栈的链式存储结构，简称链栈。  
2.首先我们要考虑的就是链栈的存储结构，由于栈只是在栈顶进行插入和删除操作，而且单链表也存在头指针，栈也存在栈顶指针，那么我们能不能想办法让这二者合为一体呢，答案是肯定的。我们直接将栈顶放在单链表的头部，因此单链表中常用的头指针自然也就失去了意义，**通常对链栈来讲是不需要头结点的**。对于链栈来讲基本很少出现栈满的情况（除非内存已经被沾满 ），如果这种事情真的发生，那么此时的计算机操作系统也将会面临死机崩溃的情况，那就不单单是这个链栈是否溢出的问题了。对于链表来说，链表为空的表示是头结点指向空，那么对于链栈来讲，链栈为空就是栈顶指针指向空（top = NULL）。  
3.链栈的结构定义  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
在这里我们假设elementype为int类型，读者可根据需要自行修改。  
4.链栈的进栈操作算法（类似于链表的插入）：***先对数据域进行赋值，然后让新结点指向栈顶指针，最后将栈顶指针交给新节点***。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
5.链栈的出栈操作算法（类似于链表的删除操作）：***现将要删除的元素的值交给临时变量，将栈顶指针交给临时节点（栈只在栈顶进行操作，不用担心其他问题），将栈顶指针下移，最后释放临时节点（即完成删除）。***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
6.对于访问来讲，这里我采用了最基本的打印元素的方式来进行访问（即遍历栈，对每个位置上的元素进行打印）。  
![在这里插入图片描述][20190201213651440.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]  
7.返回栈的大小就是检测元素个数，只需要查看计数器的值即可。  
8.获得栈顶元素的值，直接调用栈，然后打印栈顶元素即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]  
*全部代码及测试结果如下*：在进行栈中元素分配的时候，小编采用了直接用for循环+入栈的操作对栈内元素进行了录入。

//等于说，链表的头就是栈顶，因此在退栈的时候直接让指针后继就可以
    //在进行新元素插入的时候让新建立的节点的指针后继指向栈顶指针就可以
    #include<stdio.h>
    #include<stdbool.h>
    #include<malloc.h>
    
    typedef int elementype;
    
    typedef struct node{
    	elementype data;
    	struct node *next;
    }stacknode, *linkstackptr;
    
    typedef struct stack{
    	linkstackptr top;		//栈顶指针 
    	int count;				//计数器 
    }Linkstack;
    
    /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
    int stackempty(Linkstack S)
    { 
            if (S.count == 0)
                    return 1;
            else
                    return 0;
    }
    
    bool push(Linkstack *S, elementype e)		//入栈操作 
    {
    	linkstackptr s = (linkstackptr)malloc(sizeof(stacknode));
    	s -> data = e;
    	s -> next = S -> top;		//把当前的栈顶赋值给新的元素的后继(指针的指向)
    	S -> top = s;		//新的节点赋值给栈顶指针（即让新元素成为栈顶元素）
    	S -> count++;
    	return true; 
    }
    
    int pop(Linkstack *s, elementype *e)		//出栈操作
    {
    	linkstackptr p;		//临时节点
    	if(stackempty(*s))
    		return 0;
    	else
    	{
    		*e = s -> top -> data;
    		p = s -> top;		//将栈顶指针交给p 
    		s -> top = s -> top -> next;	//使得栈顶指针下移一位
    		free(p);		//因为节点被删除，所以要释放临时节点		
    		s -> count--;			//计数器减一个 
    		return 1;
    	}	
    }
    
    void visit(elementype p)
    {
    	printf("%d ", p);
    }
    
    bool traversestack(Linkstack s)
    {
    	linkstackptr p;
    	p = s.top;
    	while(p)
    	{
    		visit(p -> data);
    		p = p -> next;
    	}
    	printf("\n");
    	return true;
    }
    
    /*  构造一个空栈S */
    bool InitStack(Linkstack *S)
    { 
            S -> top = (linkstackptr)malloc(sizeof(stacknode));
            if(!S -> top)
                    return false;
            S -> top = NULL;
            S -> count = 0;
            return true;
    }
    
    /* 把S置为空栈 */
    bool ClearStack(Linkstack *S)
    { 
            linkstackptr p,q;
            p = S -> top;
            while(p)
            {  
                    q = p;
                    p = p -> next;
                    free(q);		//对每一个节点进行释放 
            } 
            S -> count = 0;
            return true;
    }
    
    /* 返回S的元素个数，即栈的长度 */
    int StackLength(Linkstack S)
    { 
            return S.count;
    }
    
    /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
    int GetTop(Linkstack S,elementype *e)
    {
            if (S.top == NULL)
                    return 0;
            else
                    *e = S.top -> data;
            return 1;
    }
    
    int main()
    {
            int j;
            Linkstack s;
            int e;
            if(InitStack(&s) == true)
                    for(j = 1;j <= 10;j++)
                            push(&s,j);
            printf("栈中元素依次为：");
            traversestack(s);
            pop(&s,&e);
            printf("弹出的栈顶元素 e=%d\n",e);
            printf("栈空否：%d(1:空 0:否)\n",stackempty(s));
            GetTop(s,&e);
            printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
            ClearStack(&s);
            printf("清空栈后，栈空否：%d(1:空 0:否)\n",stackempty(s));
            
            return 0;
    }

![在这里插入图片描述][20190201214156980.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220321/ee228cb04c03480a9387b19c682601fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220321/f7c4d212931741fb90f895a30c2c5263.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20220321/dbff966f18c1423f9ba8982ea2bdfb16.png
[20190201213651440.png]: /images/20220321/076b22af33ea499381b0564c824e74a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]: /images/20220321/6fcf621d1bbb4ca3bfea29db599cc75b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]: /images/20220321/23e8e5faafca4eeeaf710a0ed7a2ec81.png
[20190201214156980.png]: /images/20220321/f9a8494201c9457d83747ab81584cd42.png