亲宝软件园·资讯

展开

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链栈出栈

出栈就是:

代码如下:

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;
	}
}

八.总结

对比顺序栈和链栈,如果栈的使用过程中元素变化不可预料,有时小,有时大,那么最好用链栈;反之,如果他的变化在可控范围之内建议使用顺序栈会更好点。

(小白一位,如有错误欢迎指正)

加载全部内容

相关教程
猜你喜欢
用户评论