首页 > 其他分享 >【链栈的实现】--------本质为不带头结点的 头插法建立起来的单链表

【链栈的实现】--------本质为不带头结点的 头插法建立起来的单链表

时间：2024-08-26 14:50:57浏览次数：11  
标签：-------- 插法 结点 return LinkStack 栈顶 链栈 指针

1.链栈的基本属性与特征：

链栈是运算受限的单链表，只能在链表头部进行操作
在这里插入图片描述

2.链栈的相关基础操作汇总

  • 初始化操作：操作结果:构造一个空栈 S。
InitStack(LinkStack *s)
  • 判定S是否为空栈：
    初始条件:栈S 已存在
    操作结果:若栈S为空栈，则返回TRUE，否则 FALSE.
StackEmpty(LinkStack s)
  • 求栈的长度
    初始条件:栈S 已存在。
    操作结果:返回S的元素个数，即栈的长度
StackLength(LinkStack s)
  • 栈销毁操作：
    初始条件:栈S 已存在。
    操作结果:将S清为空栈，且不使用该栈顶指针。
DestroyStack(LinkStack* s)
  • 入栈操作（重点）
    初始条件:栈S已存在 （链栈一般不存在栈满的情况）。
    操作结果:插入元素e为新的栈顶元素。
Push(LinkStack *s,SElemType e)
  • 出栈操作（重点）
    初始条件:栈S 已存在且非空:
    操作结果:删除S的栈顶元素a.，并用e返回其值。
Pop(LinkStack* s, SElemType* e)
  • 取栈顶元素
    初始条件:栈S 已存在且非空。
    操作结果:用e返回S的栈顶元素，并销毁该结点空间。
GetTop(LinkStack s, SElemType* e)
  • 从栈顶开始输出整栈
    初始条件:栈S 已存在且非空。
    操作结果:从栈顶输出栈中所有元素。
PrintStack(LinkStack s)

3.链栈的整栈创建（不带头结点，含头指针 即栈顶指针）

3.1链栈的结构定义：

//1.链栈的结构定义：
//实际上就是运算受限的单链表，只能在链表头部进行操作
typedef struct StackNode
{
	SElemType data;
	struct StackNode* next;
}StackNode,*LinkStack;
//StackNode:用来定义单个链栈的结点
//*LinkStack:用来定义整个链栈（即链栈的头指针或者栈顶指针）
  • 在结构定义中，一个链栈结点里包含了，指针域，和存放栈元素数据域这两个部分
  • 而别名StackNode用来定义单个链栈结点
    LinkStack 用来定义链栈的头指针（栈顶指针）

3.2链栈的初始化

注意：传入参数时，需传入二级指针，这样才能修改栈中的数据

bool InitStack(LinkStack *s)
3.2.1算法步骤：

(1)将传入的头指针（栈顶指针）初始化为空，表示空栈

//2.链栈的初始化
bool InitStack(LinkStack *s)
{
	//[1]将传入的头指针初始化为空，表示空栈
	*s = NULL;
	return true;
}

3.3判断链栈是否为空

注意：传入参数时，不需要传入二级指针，因为判空操作只需要访问栈顶指针,并不做修改

bool StackEmpty(LinkStack s)
3.3.1算法步骤：

（1）若传入的头指针（栈顶指针）为空，则返回true，表示空栈；否则栈非空，

//3.判断链栈是否为空
bool StackEmpty(LinkStack s)
{
	//[1]若传入的头指针为空，则返回true，表示空栈
	if (s == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

3.4求链栈的长度

注意：传入参数时，不需要传入二级指针，因为求长度只需要返回计数器的结果，并不修改栈中数据

  • 该操作与求单链表长度的操作完全一致
int StackLength(LinkStack s)
3.4.1算法步骤：

（1）定义一个临时指针p，并让其指向首元结点
（2）初始化计数器为0,因为没有排除空链栈的可能
（3）循环遍历，统计结点数

//4.求链栈的长度
int StackLength(LinkStack s)
{
	//[1]定义一个临时指针p，并让其指向首元结点
	StackNode * p = s;
	//[2]初始化计数器为0,因为没有排除空链栈的可能
	int count = 0;

	//[3]循环遍历，统计结点数
	while (p != NULL)//若为空，直接返回i=0，不会进入循环
	{
		count++;//进入循环，证明存在首元结点，故先叠加
		p = p->next;//当p指向空，计数器已经将表长记录成功
	}

	return count;
}

3.5销毁链栈

注意：传入参数时，需要传入二级指针，因为销毁栈需要将栈顶指针置空

bool DestroyStack(LinkStack* s)
3.5.算法步骤

（1）定义临时指针p，用来链栈中遍历所有结点
（2）定义临时指针temp,temp用来销毁空间
（3）循环销毁每个结点
（4）循环结束后，将头指针置为空，表示空栈(同时避免了悬挂指针问题)

//5.销毁链栈
//注意：这里传入二级指针，因为最终需要将头指针置为空
bool DestroyStack(LinkStack* s) 
{
	//[1]定义临时指针p，用来链栈中遍历所有结点
	StackNode* p = *s;

	//[2]定义临时指针temp,temp用来销毁空间
	StackNode* temp;

	//[3]循环销毁每个结点
	while (p != NULL) 
	{
		temp = p;
		p = p->next;
		free(temp);
	}

	//[4]循环结束后，将头指针置为空，表示空栈(同时避免了悬挂指针问题)
	*s = NULL;
	return true;
}

3.6链栈的入栈（核心1）

注意：传入参数时，需要传入二级指针，因为入栈操作需要 更改栈顶指针以及 添加栈顶元素

  • 本质为单链表的头部插入操作
  • 由于链栈一般不存在栈满的情况，故不需要特殊判断
bool Push(LinkStack *s,SElemType e)
3.6.1算法步骤：

（1）建立新结点，并初始化数据域
（2）入栈操作：
<1>修改新结点的指针域，指向当前栈顶元素
<2>修改栈顶指针，栈顶指针应指向新插入的结点

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

//6.链栈的入栈操作
//本质为单链表的头部插入操作
bool Push(LinkStack *s,SElemType e)
{
	//[1]建立新结点，并初始化数据域
	StackNode* p = (StackNode *)malloc(sizeof(StackNode));

	if (p == NULL)
	{
		printf("内存分配失败！\n");
		return false;
	}

	p->data = e;


	//[2]将新结点插入到链栈的头部
	p->next = (*s);//仅需要修改新结点的指针域即可
	*s = p;//注意修改栈顶指针，栈顶指针应指向新插入的结点
	
	return true;
}

3.7链栈的出栈（核心2）

注意：传入参数时，需要传入二级指针，因为出栈操作需要 更改栈顶指针以及 带出栈顶元素

bool Pop(SqStack* s, SElemType* e)
3.7.1算法步骤：

（1）判断是否栈空（即栈顶指针 是否指向NULL）
（2）出栈操作：
<1>先将当前栈顶指针指向的栈顶元素 赋值给e
<2>再定义并初始化临时指针p指向当前栈顶结点
<3>修改栈顶指针指向出栈后的栈顶结点
<4>销毁临时指针p指向的结点空间

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

//7.链栈的出栈操作
//本质为单链表的头部删除操作
bool Pop(LinkStack* s, SElemType* e)
{
	//[1]判断链栈是否为空，为空则返回false
	if ((*s) == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]保存栈顶结点的数据
	*e = (*s)->data;

	//[3]定义并初始化临时指针p指向当前栈顶结点
	StackNode* p=(*s);

	//[4]修改栈顶指针指向出栈后的栈顶结点
	(*s) = (*s)->next;

	//[5]销毁临时指针p指向的结点空间
	free(p);

	return true;
}

3.8取栈顶元素

注意：传入参数时，不需要传入二级指针，因为只取元素，不修改栈的数据

bool GetTop(LinkStack s, SElemType* e)
3.8.1算法步骤：

（1）判断链栈是否为空，为空则返回false
（2）若链栈不为空，则直接返回栈顶元素
(栈顶元素为链表的首元结点，即链表的头指针指向的结点)

在这里插入图片描述

//8.获取栈顶元素
bool GetTop(LinkStack s, SElemType* e)
{
	//[1]判断链栈是否为空，为空则返回false
	if (s == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]若链栈不为空，则直接返回栈顶元素
	//注意：栈顶元素为链表的首元结点，即链表的头指针指向的结点
	*e = s->data;

	return true;
}

3.9输出链栈中的所有元素(从顺序栈顶开始输出)

bool PrintStack(LinkStack s)
3.9.1算法步骤：

（1）定义临时指针p，用来链栈中遍历所有结点
（2）判断链栈是否为空，为空则返回false
（3）p从栈顶开始，向栈底移动并依次输出栈中的元素

//9.输出链栈中的所有元素(从栈顶开始输出)
bool PrintStack(LinkStack s)
{
	//[1]定义临时指针p，用来链栈中遍历所有结点
	StackNode* p = s;

	//[2]判断链栈是否为空，为空则返回false
	if (p == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]循环输出每个结点
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}

	printf("\n");
	return true;
}

4.所有操作如下

//创建一个不带头结点的链栈（头指针就是栈顶指针）
//本质为限制了插入与删除操作的（头插法建立起来的 单链表）
#include<stdio.h>
#include<stdlib.h>


#define bool char
#define true 1
#define false 0

typedef int SElemType;//栈中数据元素的类型定义     

//1.链栈的结构定义：
//实际上就是运算受限的单链表，只能在链表头部进行操作
typedef struct StackNode
{
	SElemType data;
	struct StackNode* next;
}StackNode,*LinkStack;
//StackNode:用来定义单个链栈的结点
//*LinkStack:用来定义整个链栈（即链栈的头指针或者栈顶指针）



//2.链栈的初始化
bool InitStack(LinkStack *s)
{
	//[1]将传入的头指针初始化为空，表示空栈
	*s = NULL;
	return true;
}


//3.判断链栈是否为空
bool StackEmpty(LinkStack s)
{
	//[1]若传入的头指针为空，则返回true，表示空栈
	if (s == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}



//4.求链栈的长度
int StackLength(LinkStack s)
{
	//[1]定义一个临时指针p，并让其指向首元结点
	StackNode * p = s;
	//[2]初始化计数器为0,因为没有排除空链栈的可能
	int count = 0;

	//[3]循环遍历，统计结点数
	while (p != NULL)//若为空，直接返回i=0，不会进入循环
	{
		count++;//进入循环，证明存在首元结点，故先叠加
		p = p->next;//当p指向空，计数器已经将表长记录成功
	}

	return count;
}

//5.销毁链栈
//注意：这里传入二级指针，因为最终需要将头指针置为空
bool DestroyStack(LinkStack* s) 
{
	//[1]定义临时指针p，用来链栈中遍历所有结点
	StackNode* p = *s;

	//[2]定义临时指针temp,temp用来销毁空间
	StackNode* temp;

	//[3]循环销毁每个结点
	while (p != NULL) 
	{
		temp = p;
		p = p->next;
		free(temp);
	}

	//[4]循环结束后，将头指针置为空，表示空栈(同时避免了悬挂指针问题)
	*s = NULL;
	return true;
}


//6.链栈的入栈操作
//本质为单链表的头部插入操作
bool Push(LinkStack *s,SElemType e)
{
	//[1]建立新结点，并初始化数据域
	StackNode* p = (StackNode *)malloc(sizeof(StackNode));

	if (p == NULL)
	{
		printf("内存分配失败！\n");
		return false;
	}

	p->data = e;


	//[2]将新结点插入到链栈的头部
	p->next = (*s);//仅需要修改新结点的指针域即可
	*s = p;//注意修改栈顶指针，栈顶指针应指向新插入的结点
	
	return true;
}

//7.链栈的出栈操作
//本质为单链表的头部删除操作
bool Pop(LinkStack* s, SElemType* e)
{
	//[1]判断链栈是否为空，为空则返回false
	if ((*s) == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]保存栈顶结点的数据
	*e = (*s)->data;

	//[3]定义并初始化临时指针p指向当前栈顶结点
	StackNode* p=(*s);

	//[4]修改栈顶指针指向出栈后的栈顶结点
	(*s) = (*s)->next;

	//[5]销毁临时指针p指向的结点空间
	free(p);

	return true;
}


//8.获取栈顶元素
bool GetTop(LinkStack s, SElemType* e)
{
	//[1]判断链栈是否为空，为空则返回false
	if (s == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]若链栈不为空，则直接返回栈顶元素
	//注意：栈顶元素为链表的首元结点，即链表的头指针指向的结点
	*e = s->data;

	return true;
}

//9.输出链栈中的所有元素(从栈顶开始输出)
bool PrintStack(LinkStack s)
{
	//[1]定义临时指针p，用来链栈中遍历所有结点
	StackNode* p = s;

	//[2]判断链栈是否为空，为空则返回false
	if (p == NULL)
	{
		printf("空栈！\n");
		return false;
	}

	//[2]循环输出每个结点
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}

	printf("\n");
	return true;
}

int main()
{
	LinkStack s1;
	InitStack(&s1);  // 初始化栈

	// 入栈
	Push(&s1, 10);
	Push(&s1, 20);
	Push(&s1, 30);
	Push(&s1, 31);
	Push(&s1, 32);

	printf("当前栈的长度: %d\n", StackLength(s1));
	printf("\n");

	// 获取栈顶元素
	SElemType ee;
	GetTop(s1, &ee);
	printf("当前栈顶元素为：%d\n", ee);

	printf("\n");
	printf("从当前栈顶元素向下输出：\n");
	
	PrintStack(s1);

	// 出栈
	printf("\n");
	SElemType e[10];
	for (int i = 0; i < 3; i++)
	{
		Pop(&s1, &e[i]);
		printf("出栈元素: %d\n", e[i]);
	}

	printf("\n");
	printf("从当前栈顶元素向下输出：\n");
	PrintStack(s1);

	// 销毁栈
	DestroyStack(&s1);

	printf("栈是否为空: \n");
	if (StackEmpty(s1))
	{
		printf("栈为空！\n");
	}
	return 0;
}

在这里插入图片描述

标签：--------,插法,结点,return,LinkStack,栈顶,链栈,指针
From： https://blog.csdn.net/2401_82676816/article/details/141399404

相关文章

  • 锦绣河山美如画,祖国建设跨骏马这句歌词是哪首歌曲《我为祖国献石油》
    锦绣河山美如画,祖国建设跨骏马这句歌词是哪首歌曲  我来答 分享 举报 2个回答#热议# 网上掀起『练心眼子』风潮，真的能提高情商吗？启雨7272019-05-04 · TA获得超过5195个赞关注 展开全部是刘秉义唱的歌曲《我为祖国献石油》原句是“锦绣河山......
  • [javascript] 使用 puppeteer 包模拟 chrome 自动化
    npmipuppeteerconstpuppeteer=require('puppeteer');functionsleep(ms){returnnewPromise(resolve=>setTimeout(resolve,ms));}asyncfunctionrun(){constbrowser=awaitpuppeteer.launch({headless:false,args:['--st......
  • AlphaGo Zero论文《Mastering the game of Go without human knowledge》阅读笔记
    AlphaGoZero论文阅读笔记原论文：《MasteringthegameofGowithouthumanknowledge》简述：论文提出了一种新的围棋人工智能算法AlphaGoZero，该算法可以在完全无监督的情况下进行训练，并且超越了之前的AlphaGoFan和AlphaGoLee的表现。该算法具有如下特点：在无监督的情况......
  • 南沙区信奥赛陈老师讲题：1237：求排列的逆序数
    【题目描述】在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n1,2,…,n的排列i1，i2，…，ini1，i2，…，in，如果其中存在j,kj,k，满......
  • JS实现对象只复制已存在的属性
    JavaScript实现只复制已存在属性的笔记在JavaScript中，如果需将一个对象的属性复制到另一个对象中，但只复制目标对象中已经存在的属性，可以使用以下几种方法：1.手动遍历属性通过遍历source对象的属性，并判断target对象中是否存在对应属性，决定是否进行复制。constsource=......
  • 22-lenet网络
    importtorchimporttorch.nnasnnfromd2limporttorchasd2lnet=nn.Sequential(nn.Conv2d(1,6,kernel_size=(5,5),padding=2),nn.Sigmoid(),nn.AvgPool2d(kernel_size=(2,2),stride=2),nn.C......
  • 地理：美国各州首府系列
    1.botson文化重镇波士顿2.annapolis3.弗吉尼亚州首府里士满4.罗得岛州的普罗维登斯5.加利福尼亚州的萨克拉门托6.纽约州奥尔巴尼市7.阿拉巴马州蒙哥马利市8.alascap9.arizona10.little阿肯色州首府小石城11.康涅狄格州哈特福德市12.特拉华州多佛市13.印第安纳波利斯1......
  • 终末之诗
    PlayerNameIseetheplayeryoumean.我看到你所指的那个玩家了。?？Yes.Takecare.Ithasreachedahigherlevelnow.Itcanreadourthoughts.是的。注意，他已达到了更高的境界，他知道我们心里所想。Thatdoesn'tmatter.Itthinkswearepartofthegame.......
  • MySQL常用的分组聚合函数
    一、聚合函数（aggregationfunction）---也就是组函数在一个行的集合（一组行）上进行操作，对每个组给一个结果。常用的组函数：AVG([distinct]expr)求平均值COUNT({*|[distinct]}expr)统计行的数量MAX([distinct]expr)求最大值MIN([distinct]exp......
  • 利用kafka和kafka connect插件debezium实现oracle表同步
    1.kafka安装1.1.java安装openjdk下载，建议使用17，至少应该高于版本11#进入家目录，解压下载的java包，配置环境变量tarvxfopenjdk-20.0.1_linux-x64_bin.tar.gz-C/usr/local/vi.bash_profile#注意要把JAVA的目录放到$PATH之前exportJAVA_HOME=/usr/local/jdk-20exportP......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99