YAZONG 我的开源

(数据结构)第二讲-线性结构(2.2.3堆栈的链式存储实现)

  , ,
0 评论0 浏览

image.png

如果在头节点做插入操作和删除操作是可以的,因为头节点知道下一个元素的位置在哪儿,就可以把TOP指向下一个元素。

image.png

但插入也能在链尾操作,可以用当前的这个链表的尾巴指向一个新的结点。

删除不可以,因为这是单向链表,删除之后,找不到前面的一个结点。

/*
堆栈的链式存储实现结构
*/
typedef struct SNode *Stack;
struct SNode{
	ElementType Data;
	struct SNode *Next;
};
/*
1)堆栈初始化(建立空栈)
构建一个堆栈的头结点,返回指针。
这个头结点不代表任何一个元素,只是通过这个头结点可以方便的找到堆栈里面的一些具体的元素。
插入一个结点,实际上就是在头结点插入新的结点。
*/
Stack CreateStack(){
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

image.png上述建立一个空栈,实际上是形成这种一种结构。

/*
2)判断堆栈是否为空
若为空,函数返回整数1,否则返回0。
*/
int IsEmpty(Stack S){
	return (S->Next == NULL);
}

image.png

/*
将元素item压入堆栈S
注意这里在做PUSH操作时不去判断堆栈是否满,
如果是数组实现堆栈的时候,数组大小是固定的,所以数组存在是否满的问题。
如果是链表,是通过不断地申请节点空间往里面插,所以就不需要判断是否满的问题。
*/
void push(ElementType item, Stack S){
	struct SNode *TmpCell;
	TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
	TmpCell->Element = item;
	TmpCell->Next = S->Next;
	S->Next = TmpCell;
}

image.png

/*
将元素item弹出堆栈S
*/
ElementType Pop(Stack S){
	//删除并返回堆栈S的栈顶元素(跟插入操作颠倒过来)
	struct SNode *FirstCell;
	ElementType TopElem;
	if(IsEmpty(S)){
		printf("堆栈空");
		return NULL;
	}else{
		//下述的三个FirstCell是同一个对象
		FirstCell = S->Next;
		//完成结点指针的重新指向
		S->Next = FirstCell->Next;
		TopElem = FirstCell->Element;
		//删掉的结点的空间必须要释放
		free(FirstCell);
		return TopElem;
	}
}

标题:(数据结构)第二讲-线性结构(2.2.3堆栈的链式存储实现)
作者:yazong
地址:https://blog.llyweb.com/articles/2023/08/15/1692030187242.html