郝斌数据结构2栈

深藏阁楼爱情的钟 2022-03-02 05:38 238阅读 0赞

一. 连续栈

1.  栈的定义: 一种可以实现“先进后出”的存储结构  
    栈类似于箱子，只允许在一端进行操作
2.  栈分类: 静态栈(连续栈) 动态栈(链式栈)
3.  操作: 入栈 出栈
4.  连续栈程序:

#include <stdio.h>
    #include <stdlib.h>
    #define N 64
    
    typedef int datatype;
    
    typedef struct
    { 
    	datatype data[N];
    	int top; //top是int型的!!
    } sqstack;
    
    sqstack *stack_create();
    void stack_show(sqstack *s);
    int push(sqstack *s,datatype value);
    datatype pop(sqstack *s);
    int stack_full(sqstack *s);
    int stack_empty(sqstack *s);
    datatype stack_top(sqstack *s);
    void stack_clear(sqstack *s);
    void stack_free(sqstack *s);
    
    int main(void)
    { 
    	sqstack *s = NULL;
    	if ((s = stack_create()) == NULL)
    	{ 
    		printf("stack_create failed\n");
    		return -1;
    	}
    
    	push(s,10);
    	push(s,20);
    	push(s,30);
    	push(s,40);
    
    	stack_show(s);
    	printf("返回栈顶元素:%d\n",stack_top(s));
    	printf("出栈的元素:%d\n",pop(s));
    	printf("出栈的元素:%d\n",pop(s));
    	stack_show(s);
    
    	printf("stack_clear后show:\n");
    	stack_clear(s);
    	stack_show(s);
    	printf("出栈的元素:%d\n",pop(s));
    	printf("出栈的元素:%d\n",pop(s));
    
    	stack_free(s);
    
    	return 0;
    }
    
    sqstack *stack_create()
    { //创建的第一个元素不存放数值!!
    	sqstack *s = NULL;
    	if (NULL == (s = malloc(sizeof(sqstack))))
    	{ 
    		printf("malloc failed\n");
    	}
    
    	s->top = -1;
    
    	return s;
    }
    
    int push(sqstack *s, datatype value)
    { 
    	if (stack_full(s))
    	{ 
    		printf("stack is full\n");
    		return -1;
    	}
    
    	s->top++;
    	s->data[s->top] = value;
    	return 0;
    }
    
    datatype pop(sqstack *s)
    { //出站是因为要返回出站的数值以判断正确，所以
    //函数类型是datatype 入站就定义成int就行了
    	if (stack_empty(s))
    	{ 
    		printf("stack is empty\n");
    		return -1;
    	}
    
    	s->top--;
    	return s->data[s->top + 1];
    }
    
    int stack_full(sqstack *s)
    { 
    	return s->top == N - 1;
    	//注意是“= =”，如果相等就证明满了就返回真，否则就返回假
    }
    
    int stack_empty(sqstack *s)
    { 
    	return s->top == -1 ? 1 : 0;
    	//或者直接写成return s->stop == -1;
    }
    
    datatype stack_top(sqstack *s)
    { //返回栈顶元素
    	return s->data[s->top];
    }
    
    void stack_show(sqstack *s)
    { 
    	int i;
    	for(i = 0;i <= s->top;i++)
    	{ 
    		printf("%d ",s->data[i]);
    	}
    	putchar(10);
    }
    
    void stack_clear(sqstack *s)
    { //清空栈，只留第一个不放数值的元素
    	s->top = -1;
    }
    
    void stack_free(sqstack *s)
    { 
    	while (!stack_empty(s))
    	{ 
    		printf("%d ", pop(s));
    	}
    
    	printf("\n");
    	free(s);
    	s = NULL;
    }

运行结果:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
二. 链式栈  
这次把整个程序写在三个文件中，看起来非常清楚(∩\_∩)

//linkstack.h程序
    
    #ifndef LINKSTACK_H_
    #define LINKSTACK_H_
    
    typedef int datatype;
    
    typedef struct node
    { 
    	datatype data;
    	struct node *next;
    }stack;
    
    stack *stack_create();
    int push(stack *s,datatype value);
    datatype pop(stack *s);
    void stack_show(stack *s);
    int stack_empty(stack *s);
    datatype stack_top(stack *s);
    void stack_clear(stack *s);
    void stack_free(stack *s);
    #endif /* LINKSTACK_H_ */
    
    //linkstack.c程序
    #include <stdio.h>
    #include <stdlib.h>
    #include "linkstack.h"
    
    stack *stack_create()
    { //头结点不存放数据，栈空了这个节点也存在!!
    	stack *s = NULL;
    
    	if (NULL == (s = malloc(sizeof(stack))))
    	{ 
    		printf("malloc failed\n");
    		return NULL;
    	}
    
    	s->next = NULL;
    	return s;
    }
    
    int push(stack *s,datatype value)
    { //这个入栈就是链表的在头结点的后面插入!!
    	stack *p = NULL;
    	if(NULL == (p = malloc(sizeof(stack))))
    	{ 
    		printf("malloc node failed\n");
    		return -1;
    	}
    
    	p->data = value;
    	p->next = s->next;
    	s->next = p;
    
    	return 0;
    }
    
    datatype pop(stack *s)
    { //这个出栈就是链表的在删除头节点后面的节点。链表的特点就是先插入的节点
    //离头结点远，头结点后边那个是最近插入的。这个特点正好用在了链式栈上，体现了
    //先进后出的原则
    	stack *p = NULL;//p指向要弹出的数值
    	datatype t;//存放弹出来的数值
    
    	if (stack_empty(s))
    	{ 
    		printf("stack is empty\n");
    		return -1;
    	}
    
    	p = s->next;
    	t = p->data;
    	s->next = p->next;
    	free(p);
    	p = NULL;
    
    	return t;//让我们知道哪个栈顶元素出栈了
    }
    
    int stack_empty(stack *s)
    { //栈空了的含义不是一个节点也没有，是只有一个头节点!
    	return s->next == NULL;
    	//注意这里是“==”!这写法很精练啊!
    }
    
    datatype stack_top(stack *s)
    { //返回栈顶元素 要明白栈顶节点就是离头结点最近的节点，也就是头结点
    //后面的节点，这里注意不要写成s->data!头节点不存放内容!
    	return s->next->data;
    }
    
    void stack_show(stack *s)
    { //同链表的遍历输出是一样的
    	while(s->next != NULL)
    	{ 
    		printf("%d ",s->next->data);
    //注意是s->next->data!
    		s = s->next;
    	}
    
    	putchar('\n');
    }
    
    void stack_clear(stack *s)
    { //就是让栈空了只剩一个头节点
    	while(!stack_empty(s))
    	{ 
    		printf("clear弹出的:%d ",pop(s));
    	}
    
    	puts(""); //这也是一种输出换行符的方法
    }
    
    void stack_free(stack *s)
    { //完全干掉栈，连头结点也干掉了
    	stack_clear(s);
    	free(s);
    	s = NULL;
    }
    
    //main.c程序
    
    #include <stdio.h>
    #include <stdlib.h>
    #include "linkstack.h"
    
    int main(void)
    { 
    	stack *s = NULL;
    
    	if (NULL == (s = stack_create()))
    	{ 
    		printf("stack_create failed\n");
    		return -1;
    	}
    
    	push(s, 10);
    	push(s, 20);
    	push(s, 30);
    	push(s, 40);
    
    	stack_show(s);
    
    	printf("栈顶元素是:%d\n", stack_top(s));
    	printf("出栈元素是:%d\n", pop(s));
    	printf("出栈元素是:%d\n", pop(s));
    	stack_show(s);
    
    	printf("stack_clear后:\n");
    	stack_clear(s);
    	stack_show(s);
    	printf("出栈元素是:%d\n", pop(s));
    
    	stack_free(s);
    
    	return 0;
    }

运行结果:  
![在这里插入图片描述][20190319195906396.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/5e034d5995dc4642b078c61a021b56e1.png
[20190319195906396.png]: /images/20220302/a8f39e7cb59642b5acc05ca1fcdfec42.png