C语言栈与链栈
Mi ronin 人气:0一.栈的定义
栈是限定仅在表尾进行插入和删除操作的数据结构(受到限制的线性表)。
我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何元素为空栈。
二.栈的特点
后进先出
比如word,浏览器网页等一系列软件中,都有撤销的操作,就是利用栈的这种方式来实现的,可能不同软件的代码不同,但是他们的原理是一样的均为:后进先出。
三.栈的理解
- 栈是一个线性表,有前驱后继关系,只不过这里的表尾指的是栈顶。
- 栈限制了线性表的插入和删除位置,这也导致栈底是固定的。
- 栈的插入操作,叫做进栈;可以理解为子弹入弹夹。
- 栈的删除操作,叫做出栈;可以理解为子弹出弹夹。
四.链栈引入
既然栈是属于线性表的一种,那么存储结构也就分为顺序存储和链式存储,这里我们着重讲解链式存储结构。
五.链栈定义
栈的链式存储结构,简称链栈。
对于栈来说,只在栈顶做插入和删除操作,由于单链表有头指针,栈顶指针也是必须的,那我们干脆就将头指针和栈顶指针合二为一,将栈顶放在单链表的头部。通常对于链栈是不需要头结点的。
对于链栈来说,一般不会存在栈满的情况,如果这种事情真的发生,那么此时的计算机操作系统也将会面临死机崩溃的情况,那就不单单是这个链栈是否溢出的问题了。对于链表来说,链表为空的表示是头结点指向空,那么对于链栈来讲,链栈为空就是栈顶指针指向空(top = NULL)。
六.链栈的结构体设计
代码如下:
// 链栈的存储结构 typedef struct StackNode { int data; struct StackNode *next; }StackNode,*LinkStack;
七.链栈的基本操作
对于链栈来说作为线性表的一种,操作也就那么几种,这里我们对以下几种操作进行详解:初始化,判断是否为空,入栈,出栈,取栈顶元素等。
7.1链栈的初始化
链栈的初始化可以理解为构造一个空栈,将栈顶指针top所指头结点的指针域置为NULL,因为此时栈中还没有数据元素。
代码如下:
LinkedStack Init_LinkedStack() { LinkedStack top = (LinkedStackNode *)malloc(sizeof(LinkedStackNode)); //栈顶指针变量 if(top != NULL) { top->next = NULL; } return top; }
7.2链栈判空
判断链栈是否为空,只需要判断栈顶的指针域是否指向空,如果指向空则栈空,相反亦然。
bool LinkedStack_Empty(LinkedStack top) { if(top->next == NULL)//如果栈顶的指针域指向空,则栈空 { return True; } else { return False; }
7.3链栈入栈
入栈就是:
- 先对数据域进行赋值;
- 然后让新结点指向栈顶指针;
- 最后将栈顶指针交给新节点。
假设元素值为e的新节点是s,top为栈顶指针:
代码如下:
int Push(LinkedStack *s ,elemtype e) { LinkedStackNode s= (LinkedStackNode )malloc(sizeof(LinkedStackNode)); s->data=e; s->next=s->top;//把当前的栈顶元素赋值给新结点的直接后继. s->top=s;//把新节点s赋值给栈顶指针 s->cout++; return 1; }
7.4链栈出栈
出栈就是:
- 将要删除的元素的值交给临时变量,将栈顶指针交给临时节点;
- 将栈顶指针下移;最后释放临时节点(即完成删除)。
- 假设变量p用来存储要删除的栈顶结点,将栈顶指针向下移一位,最后释放p即可:
代码如下:
int Pop_LinkedStack(LinkedStack *s,elemtype *e) { LinkedStackNode *p; if(stackempty(*s)) return error; *e=s->top->data; p=s->top; //将栈顶结点赋值给p s->top=s->top->next;//使得栈顶结点指针下移一位,指向后一结点 free(p);//释放结点 s->count--; return 1; } }
7.5取栈顶元素
读取栈顶元素,并返回其值,该操作与出栈的区别是栈顶元素并不删除,所以不用修改头结点的指针域即可。
int Get_LinkedStack(LinkedStack top,elemtype *x) { if(top->next == NULL) { return 0; } else { *x = top->next->data; return 1; } }
八.总结
对比顺序栈和链栈,如果栈的使用过程中元素变化不可预料,有时小,有时大,那么最好用链栈;反之,如果他的变化在可控范围之内建议使用顺序栈会更好点。
(小白一位,如有错误欢迎指正)
加载全部内容