C++11 数据结构6 栈的链式存储，实现，测试

  • 开发
  • 31

栈顶放在链表的头部

栈顶放在链表的头部还是尾部呢？

需要栈 是特殊的线性表，那么我们回忆一下 线性表的链式存储的插入和删除的写法，就应该能理清线性表的头部做为栈顶 合适  还是 线性表的尾部 作为栈顶合适

插入算法 核心代码

	//正式插入数据，
	int i = 0;
	LinkListNode *curSeqListNode = &(tempseqlist->head);//让curSeqListNode 指向 链表的头部
	for (int i = 0; i < pos; ++i) {
		curSeqListNode = curSeqListNode->next;
	}
	node->next = curSeqListNode->next;
	curSeqListNode->next = node;
	tempseqlist->length++;
	return ret;

删除算法 核心代码

	//辅助指针变量curSeqListNode，指向的位置是链表的头部
	LinkListNode *curSeqListNode = &(tempseqlist->head);//让curSeqListNode 指向 链表的头部
	
    int i = 0;
	for (i = 0; i < pos; ++i) {
		curSeqListNode = curSeqListNode->next;
	}
	retSeqListNode = curSeqListNode->next;	//先将要删除的节点缓存出来
	curSeqListNode->next = retSeqListNode->next;// 删除的节点的next中保存着 “要删除元素的下一个元素”，让curseqlistnode->next 指向
	tempseqlist->length--;
	return retSeqListNode;

从这两个算法都能看出，如果要在pos 位置插入元素 或者 删除元素，那么先要遍历到pos 位置，因此我们在 线性表的头部 做为 栈顶 比较合理。因此不管是插入元素，或者是删除元素，都是对线性表的头部的第一个元素进行处理。

相关代码：

#ifndef __006LINKSTACK_H__
#define __006LINKSTACK_H__

typedef void LinkStack; //链表的返回值，需要使用void *

typedef struct LinkStackNode {  //链表节点
	struct LinkStackNode *next;
}LinkStackNode;

// 初始化，建立一个空的链表 
//返回值不为NULL，表示创建成功。
//返回值为NULL，表示创建失败。
LinkStack* LinkStack_Create();

//销毁该线性表
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Destory(LinkStack *list);

//清空seqlist
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Clear(LinkStack *list);

// 返回线性表List存在的元素个数
//返回值 >=0 表示：该list存在的元素个数
//<0 表示error
int LinkStack_Length(LinkStack *list);



//从LinkStack 中获取栈顶位置的数据，实际上是 栈的第一个链表的数据
//返回值：为存储在该位置的元素
//返回NULL 表示有问题
LinkStackNode* LinkStack_Get(LinkStack *list);


//给LinkStack中指定位置插入数据，
//参数LinkStackNode为要插入的数据
//参数 pos 为要插入的位置
//成功返回1
//失败 返回<0

int LinkStack_Insert(LinkStack *list, LinkStackNode *node);


//从LinkStack 中删除栈顶位置的元素，实际上删除的链表的除了头结点的第一个元素
//参数 pos
//返回值为 删除的元素
//返回NULL 表示出现了error
LinkStackNode* LinkStack_Delete(LinkStack *list);

//判断当前linkstack 是否为null，如果为null，则返回1
//如果不为NULL，则返回-1；
int isEmptyLinkStack(LinkStack *list);
#endif

#include "006linkstack.h"
#include "stdlib.h"
#include "stdio.h"
#include "string.h"

typedef struct LinkStack {
	LinkStackNode head;
	int length;// 该链表的大小
}TLinkStack;

// 初始化，建立一个空的链表 
//返回值不为NULL，表示创建成功。
//返回值为NULL，表示创建失败。
LinkStack* LinkStack_Create() {
	TLinkStack * ts = (TLinkStack *)malloc(sizeof(TLinkStack));
	if (ts == NULL) {
		printf("LinkStack_Create error list==NULL\n");
		return NULL;
	}
	memset(ts, 0, sizeof(TLinkStack));
	ts->head.next = NULL;
	ts->length = 0;

	return ts;
}

//销毁该线性表
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Destory(LinkStack *list) {
	int ret = 1;
	if (list ==NULL) {
		ret = -1;
		printf("func LinkStack_Destory error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	free(ts);
	ts = NULL;
	list = NULL;
	return ret;
}

//清空seqlist
//返回值为1，表示成功。
//返回值为-1，表示失败。
int LinkStack_Clear(LinkStack *list) {
	int ret = 1;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Clear error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	ts->head.next = NULL;
	ts->length = 0;
	return ret;
}

// 返回线性表List存在的元素个数
//返回值 >=0 表示：该list存在的元素个数
//<0 表示error
int LinkStack_Length(LinkStack *list) {
	int ret = 0;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Length error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	return ts->length;
}



//从LinkStack 中获取指定位置的数据
//参数pos：LinkStack中的位置
//返回值：为存储在该位置的元素
//返回NULL 表示有问题
LinkStackNode* LinkStack_Get(LinkStack *list) {
	LinkStackNode* ret = NULL;
	if (list == NULL) {
		ret = NULL;
		printf("func LinkStack_Get error bacesue list = NULL return ret = NULL\n");
		return ret;
	}
	TLinkStack * ts = list;
	if (ts->length==0) {
		ret = NULL;
		printf("func LinkStack_Get error bacesue ts->length = 0 return ret = NULL\n");
		return ret;
	}
	return ts->head.next;
}


//给LinkStack中指定位置插入数据，
//参数LinkStackNode为要插入的数据
//参数 pos 为要插入的位置
//成功返回1
//失败 返回<0

int LinkStack_Insert(LinkStack *list, LinkStackNode *node) {
	int ret = 1;
	if (list == NULL) {
		ret = -1;
		printf("func LinkStack_Insert error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	node->next = ts->head.next;
	ts->head.next = node;
	ts->length++;
	return ret;
}


//从LinkList 中删除指定位置的元素
//参数 pos
//返回值为 删除的元素
//返回NULL 表示出现了error
LinkStackNode* LinkStack_Delete(LinkStack *list) {
	LinkStackNode* ret = NULL;
	if (list == NULL) {
		ret = NULL;
		printf("func LinkStack_Delete error bacesue list = NULL return ret = NULL\n");
		return ret;
	}
	TLinkStack * ts = list;
	if (ts->length == 0) {
		ret = NULL;
		printf("func LinkStack_Delete error bacesue ts->length = 0 return ret = NULL\n");
		return ret;
	}
	LinkStackNode * delnode = ts->head.next;
	ts->head.next = delnode->next;
	ts->length--;
	return delnode;

}

//判断当前linkstack 是否为null，如果为null，则返回1
//如果不为NULL，则返回0；
//有error 则返回-1
int isEmptyLinkStack(LinkStack *list) {
	int ret = 0;
	if (list == NULL) {
		ret = -1;
		printf("func isEmptyLinkStack error bacesue list = NULL return ret = -1\n");
		return ret;
	}
	TLinkStack * ts = list;
	int length = ts->length;
	if (length>0) {
		ret = 0;
	}
	else {
		ret = 1;
	}
	return ret;
}



#define _CRT_SECURE_NO_WARNINGS
#define _CRTDBG_MAP_ALLOC
#include "iostream"
#include <stdio.h>
#include <stdlib.h>

extern "C" {
#include "006linkstack.h"
}

typedef struct Teacher {
	LinkStackNode  linkstacknode;
	int age;
	char name[128];
	char *othername;
	char **stuname; //一个老师下面有5个学生
}Teacher;

int main() {
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口

	int ret = 0;
	//初始化队列，要动态的创建SeqStack，根据user设定的大小创建
//int stacksize ，表示user 要创建栈的大小
//创建失败返回NULL
	LinkStack* linkstack = LinkStack_Create();
	if (linkstack == NULL) {
		ret = -1;
		printf("func LinkStack_Create error because linkstack = NULL return ret =-1\n");
		return ret;
	}
	ret = isEmptyLinkStack(linkstack);
	printf("isEmptyLinkStack = ret %d\n", ret);

	ret = LinkStack_Length(linkstack);
	printf("LinkStack_Length = ret %d\n", ret);

	Teacher tea1;
	tea1.age = 20;
	strcpy(tea1.name, (const char*)"tea1");

	tea1.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea1.othername, 0, sizeof(char) * 128);
	strcpy(tea1.othername, (const char*)"tea1othername");

	tea1.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea1.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea1.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea1.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea1.stuname[i], "tea1stuname%d", i + 1);
	}



	Teacher tea2;
	tea2.age = 22;

	strcpy(tea2.name, (const char*)"tea2");

	tea2.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea2.othername, 0, sizeof(char) * 128);
	strcpy(tea2.othername, (const char*)"tea2othername");

	tea2.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea2.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea2.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea2.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea2.stuname[i], "tea2stuname%d", i + 1);
	}



	Teacher tea3;
	tea3.age = 33;
	strcpy(tea3.name, (const char*)"tea3");

	tea3.othername = (char *)malloc(sizeof(char) * 128);
	memset(tea3.othername, 0, sizeof(char) * 128);
	strcpy(tea3.othername, (const char*)"tea3othername");

	tea3.stuname = (char **)malloc(sizeof(char *) * 5);
	memset(tea3.stuname, 0, sizeof(char *) * 5);
	for (size_t i = 0; i < 5; i++)
	{
		tea3.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
		memset(tea3.stuname[i], 0, sizeof(char) * 128);
		sprintf(tea3.stuname[i], "tea3stuname%d", i + 1);
	}

	ret = LinkStack_Insert(linkstack, (LinkStackNode * )&tea1);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea1) func error ret =%d \n", ret);
		return ret;
	}

	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea2);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea2) func error ret =%d \n", ret);
		return ret;
	}

	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea3);
	if (ret < 0) {
		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea3) func error ret =%d \n", ret);
		return ret;
	}

	printf("-after-\n");
	ret = isEmptyLinkStack(linkstack);
	printf("isEmptyLinkStack = ret %d\n", ret);

	ret = LinkStack_Length(linkstack);
	printf("LinkStack_Length = ret %d\n", ret);



	while (LinkStack_Length(linkstack) > 0) {
		Teacher * temptea = (Teacher *)LinkStack_Get(linkstack);
		if (temptea == NULL) {
			printf("can not get find teacher\n");
		}
		printf("temptea->age = %d,temptea->name = %s,temptea->othername=%s\n",
			temptea->age,
			temptea->name,
			temptea->othername);
		for (size_t j = 0; j < 5; j++)
		{
			printf("temptea->stuname[%d] = %s,  ",
				j, temptea->stuname[j]);
		}
		Teacher * deltea = (Teacher *)LinkStack_Delete(linkstack);
		if (deltea == NULL) {
			printf("LinkStack_Delete seqstack error\n");
		}
		if (deltea->othername != NULL) {
			free(deltea->othername);

		}
		if (deltea->stuname != NULL) {
			for (size_t i = 0; i < 5; i++)
			{
				if (deltea->stuname[i] != NULL) {
					free(deltea->stuname[i]);
				}
			}
			free(deltea->stuname);
			deltea->stuname = NULL;
		}

		printf("\n");
	}
	printf("sss\n");

	//销毁栈
	//成功 返回1 表示成功销毁栈 
	//失败 返回-1 表示该函数执行的时候有问题
	ret = LinkStack_Destory(linkstack);


	return 0;





}

相关应用：实现编译器中的符号成对检测

//几乎所有的编译器都具有检测括号是否匹配的能力，
//那么如何实现编译器中的符号成对检测？如下字符串:
//5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(
//算法思路
//
//从第一个字符开始扫描
//当遇见普通字符时忽略，
//当遇见左括号时压入栈中
//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
//匹配成功：继续读入下一个字符
//匹配失败：立即停止，并报错
//结束：
//成功 : 所有字符扫描完毕，且栈为空
//    失败：匹配失败或所有字符扫描完毕但栈非空

//总结：
//当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性

#define _CRT_SECURE_NO_WARNINGS
#define _CRTDBG_MAP_ALLOC
#include "iostream"
#include <stdio.h>
#include <stdlib.h>


//几乎所有的编译器都具有检测括号是否匹配的能力，
//那么如何实现编译器中的符号成对检测？如下字符串:
//5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(
//算法思路
//
//从第一个字符开始扫描
//当遇见普通字符时忽略，
//当遇见左括号时压入栈中
//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
//匹配成功：继续读入下一个字符
//匹配失败：立即停止，并报错
//结束：
//成功 : 所有字符扫描完毕，且栈为空
//	失败：匹配失败或所有字符扫描完毕但栈非空

//总结：
//当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性

char *err1 = (char *)"无法找到对应的右括号的 左括号";
char *err2 = (char *)"该 左括号 没有对应的有括号";

extern "C" {
#include "004seqstack.h"
}

int isLeft( char ch) {
	if ('(' == ch) {
		return 1;
	}
	return 0;
}

int isRight(char ch) {
	if (')' == ch) {
		return 1;
	}
	return 0;
}

void printerror(char* err,char *str, char *ptemp) {
	printf("err start");
	printf(err);
	printf("原始字符串如下\n");
	printf(str);
	printf("\n");
	printf("error位置如下\n");

	int num = ptemp - str;
	while (num > 0 ) {
		printf(" ");
		--num;
	}
	printf("|\n");
	printf("err end");
}

void testchar(char *str) {
	SeqStack * seqstack = createSeqStack(1024);
	if (seqstack ==NULL) {
		printf("func testchar error because seqstack==NULL\n");
		return;
	}

	if (str == NULL) {
		printf("testchar func error because str==NULL\n");
		return;
	}
	char *ptemp = str;//让辅助指针变量指向传递过来的str
	while (*(ptemp) != '\0') {
		if (isLeft(*ptemp)) { 当遇见左括号时压入栈中.判断是否是符号，如果是 左括号 符号，则要进栈，
			push_SeqStack(seqstack,ptemp);

		}
		if (isRight(*ptemp)) {//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
			//如果这时候栈中啥也没有，就有问题，直接break;
			if (size_SeqStack(seqstack) == 0) {
				printerror(err1,str,ptemp);
				break;
			}
			pop_SeqStack(seqstack);
		}
		ptemp++;
	}
	//当将整个字符串都弄完成后，检查栈中是否有元素，如果栈中有元素，说明有左括号没有匹配
	while (size_SeqStack(seqstack) > 0 ) {
		printerror(err2, str, (char *)top_SeqStack(seqstack));
		pop_SeqStack(seqstack);
	}
}

int main() {
	int ret = 0;
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
	//char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(";
	char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1 - (1 + 3(";
	testchar(sourcestr);

	return ret;
}

阅读全部

相关推荐

  1. C++11 数据结构6 栈的链式存储，实现，测试

    2024-04-25 15:22:01       32 阅读

  7. 数据结构——队列链式存储实现

    2024-04-25 15:22:01       71 阅读

  8. 24/07/11数据结构(6.1215)双链表实现-栈实现

    2024-04-25 15:22:01       27 阅读

  9. 数据结构链栈实现（c语言）

    2024-04-25 15:22:01       45 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-25 15:22:01       98 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-25 15:22:01       106 阅读

  9. 在Django里面运行非项目文件

    2024-04-25 15:22:01       87 阅读

  19. Python语言-面向对象

    2024-04-25 15:22:01       96 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-25 15:22:01       91 阅读

热门阅读

  1. 脚本：监控Oracle中正在运行的SQL

    2024-04-25 15:22:01       37 阅读

  4. 【Leetcode】33- 搜索旋转排序数组

    2024-04-25 15:22:01       34 阅读

  6. Leetcode30-最小展台数量（66）

    2024-04-25 15:22:01       32 阅读

  7. (五)Servlet教程——Servlet是什么

    2024-04-25 15:22:01       36 阅读

  11. 1002 - 编程求解1+2+3+...+n

    2024-04-25 15:22:01       33 阅读

  14. Gradle的安装配置及使用

    2024-04-25 15:22:01       37 阅读

  15. nvm安装

    2024-04-25 15:22:01       38 阅读

  19. 服务端测试与功能测试

    2024-04-25 15:22:01       30 阅读

  20. 【ARMv9 DSU-120 系列 2. -- DSU-120 Cluster 中组件详细介绍】

    2024-04-25 15:22:01       37 阅读

  22. 买卖股票+跳跃游戏 贪心算法

    2024-04-25 15:22:01       29 阅读

  27. 深入React Hooks：从源码剖析到高级实践（Vue 同学必看指南）

    2024-04-25 15:22:01       40 阅读

  29. python小知识：@property、@setter 使用

    2024-04-25 15:22:01       34 阅读