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

    栈顶放在链表的头部

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

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

    插入算法 核心代码

    1. 	//正式插入数据，
    2. 	int i = 0;
    3. 	LinkListNode *curSeqListNode = &(tempseqlist->head);//让curSeqListNode 指向 链表的头部
    4. 	for (int i = 0; i < pos; ++i) {
    5. 		curSeqListNode = curSeqListNode->next;
    6. 	}
    7. 	node->next = curSeqListNode->next;
    8. 	curSeqListNode->next = node;
    9. 	tempseqlist->length++;
    10. 	return ret;

    删除算法 核心代码

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

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

    相关代码：

    1. #ifndef __006LINKSTACK_H__
    2. #define __006LINKSTACK_H__
    3.  
    4. typedef void LinkStack; //链表的返回值，需要使用void *
    5.  
    6. typedef struct LinkStackNode {  //链表节点
    7. 	struct LinkStackNode *next;
    8. }LinkStackNode;
    9.  
    10. // 初始化，建立一个空的链表 
    11. //返回值不为NULL，表示创建成功。
    12. //返回值为NULL，表示创建失败。
    13. LinkStack* LinkStack_Create();
    14.  
    15. //销毁该线性表
    16. //返回值为1，表示成功。
    17. //返回值为-1，表示失败。
    18. int LinkStack_Destory(LinkStack *list);
    19.  
    20. //清空seqlist
    21. //返回值为1，表示成功。
    22. //返回值为-1，表示失败。
    23. int LinkStack_Clear(LinkStack *list);
    24.  
    25. // 返回线性表List存在的元素个数
    26. //返回值 >=0 表示：该list存在的元素个数
    27. //<0 表示error
    28. int LinkStack_Length(LinkStack *list);
    29.  
    30.  
    31.  
    32. //从LinkStack 中获取栈顶位置的数据，实际上是 栈的第一个链表的数据
    33. //返回值：为存储在该位置的元素
    34. //返回NULL 表示有问题
    35. LinkStackNode* LinkStack_Get(LinkStack *list);
    36.  
    37.  
    38. //给LinkStack中指定位置插入数据，
    39. //参数LinkStackNode为要插入的数据
    40. //参数 pos 为要插入的位置
    41. //成功返回1
    42. //失败 返回<0
    43.  
    44. int LinkStack_Insert(LinkStack *list, LinkStackNode *node);
    45.  
    46.  
    47. //从LinkStack 中删除栈顶位置的元素，实际上删除的链表的除了头结点的第一个元素
    48. //参数 pos
    49. //返回值为 删除的元素
    50. //返回NULL 表示出现了error
    51. LinkStackNode* LinkStack_Delete(LinkStack *list);
    52.  
    53. //判断当前linkstack 是否为null，如果为null，则返回1
    54. //如果不为NULL，则返回-1；
    55. int isEmptyLinkStack(LinkStack *list);
    56. #endif

    1. #include "006linkstack.h"
    2. #include "stdlib.h"
    3. #include "stdio.h"
    4. #include "string.h"
    5.  
    6. typedef struct LinkStack {
    7. 	LinkStackNode head;
    8. 	int length;// 该链表的大小
    9. }TLinkStack;
    10.  
    11. // 初始化，建立一个空的链表 
    12. //返回值不为NULL，表示创建成功。
    13. //返回值为NULL，表示创建失败。
    14. LinkStack* LinkStack_Create() {
    15. 	TLinkStack * ts = (TLinkStack *)malloc(sizeof(TLinkStack));
    16. 	if (ts == NULL) {
    17. 		printf("LinkStack_Create error list==NULL\n");
    18. 		return NULL;
    19. 	}
    20. 	memset(ts, 0, sizeof(TLinkStack));
    21. 	ts->head.next = NULL;
    22. 	ts->length = 0;
    23.  
    24. 	return ts;
    25. }
    26.  
    27. //销毁该线性表
    28. //返回值为1，表示成功。
    29. //返回值为-1，表示失败。
    30. int LinkStack_Destory(LinkStack *list) {
    31. 	int ret = 1;
    32. 	if (list ==NULL) {
    33. 		ret = -1;
    34. 		printf("func LinkStack_Destory error bacesue list = NULL return ret = -1\n");
    35. 		return ret;
    36. 	}
    37. 	TLinkStack * ts = list;
    38. 	free(ts);
    39. 	ts = NULL;
    40. 	list = NULL;
    41. 	return ret;
    42. }
    43.  
    44. //清空seqlist
    45. //返回值为1，表示成功。
    46. //返回值为-1，表示失败。
    47. int LinkStack_Clear(LinkStack *list) {
    48. 	int ret = 1;
    49. 	if (list == NULL) {
    50. 		ret = -1;
    51. 		printf("func LinkStack_Clear error bacesue list = NULL return ret = -1\n");
    52. 		return ret;
    53. 	}
    54. 	TLinkStack * ts = list;
    55. 	ts->head.next = NULL;
    56. 	ts->length = 0;
    57. 	return ret;
    58. }
    59.  
    60. // 返回线性表List存在的元素个数
    61. //返回值 >=0 表示：该list存在的元素个数
    62. //<0 表示error
    63. int LinkStack_Length(LinkStack *list) {
    64. 	int ret = 0;
    65. 	if (list == NULL) {
    66. 		ret = -1;
    67. 		printf("func LinkStack_Length error bacesue list = NULL return ret = -1\n");
    68. 		return ret;
    69. 	}
    70. 	TLinkStack * ts = list;
    71. 	return ts->length;
    72. }
    73.  
    74.  
    75.  
    76. //从LinkStack 中获取指定位置的数据
    77. //参数pos：LinkStack中的位置
    78. //返回值：为存储在该位置的元素
    79. //返回NULL 表示有问题
    80. LinkStackNode* LinkStack_Get(LinkStack *list) {
    81. 	LinkStackNode* ret = NULL;
    82. 	if (list == NULL) {
    83. 		ret = NULL;
    84. 		printf("func LinkStack_Get error bacesue list = NULL return ret = NULL\n");
    85. 		return ret;
    86. 	}
    87. 	TLinkStack * ts = list;
    88. 	if (ts->length==0) {
    89. 		ret = NULL;
    90. 		printf("func LinkStack_Get error bacesue ts->length = 0 return ret = NULL\n");
    91. 		return ret;
    92. 	}
    93. 	return ts->head.next;
    94. }
    95.  
    96.  
    97. //给LinkStack中指定位置插入数据，
    98. //参数LinkStackNode为要插入的数据
    99. //参数 pos 为要插入的位置
    100. //成功返回1
    101. //失败 返回<0
    102.  
    103. int LinkStack_Insert(LinkStack *list, LinkStackNode *node) {
    104. 	int ret = 1;
    105. 	if (list == NULL) {
    106. 		ret = -1;
    107. 		printf("func LinkStack_Insert error bacesue list = NULL return ret = -1\n");
    108. 		return ret;
    109. 	}
    110. 	TLinkStack * ts = list;
    111. 	node->next = ts->head.next;
    112. 	ts->head.next = node;
    113. 	ts->length++;
    114. 	return ret;
    115. }
    116.  
    117.  
    118. //从LinkList 中删除指定位置的元素
    119. //参数 pos
    120. //返回值为 删除的元素
    121. //返回NULL 表示出现了error
    122. LinkStackNode* LinkStack_Delete(LinkStack *list) {
    123. 	LinkStackNode* ret = NULL;
    124. 	if (list == NULL) {
    125. 		ret = NULL;
    126. 		printf("func LinkStack_Delete error bacesue list = NULL return ret = NULL\n");
    127. 		return ret;
    128. 	}
    129. 	TLinkStack * ts = list;
    130. 	if (ts->length == 0) {
    131. 		ret = NULL;
    132. 		printf("func LinkStack_Delete error bacesue ts->length = 0 return ret = NULL\n");
    133. 		return ret;
    134. 	}
    135. 	LinkStackNode * delnode = ts->head.next;
    136. 	ts->head.next = delnode->next;
    137. 	ts->length--;
    138. 	return delnode;
    139.  
    140. }
    141.  
    142. //判断当前linkstack 是否为null，如果为null，则返回1
    143. //如果不为NULL，则返回0；
    144. //有error 则返回-1
    145. int isEmptyLinkStack(LinkStack *list) {
    146. 	int ret = 0;
    147. 	if (list == NULL) {
    148. 		ret = -1;
    149. 		printf("func isEmptyLinkStack error bacesue list = NULL return ret = -1\n");
    150. 		return ret;
    151. 	}
    152. 	TLinkStack * ts = list;
    153. 	int length = ts->length;
    154. 	if (length>0) {
    155. 		ret = 0;
    156. 	}
    157. 	else {
    158. 		ret = 1;
    159. 	}
    160. 	return ret;
    161. }
    162.  

    1. #define _CRT_SECURE_NO_WARNINGS
    2. #define _CRTDBG_MAP_ALLOC
    3. #include "iostream"
    4. #include <stdio.h>
    5. #include <stdlib.h>
    6.  
    7. extern "C" {
    8. #include "006linkstack.h"
    9. }
    10.  
    11. typedef struct Teacher {
    12. 	LinkStackNode  linkstacknode;
    13. 	int age;
    14. 	char name[128];
    15. 	char *othername;
    16. 	char **stuname; //一个老师下面有5个学生
    17. }Teacher;
    18.  
    19. int main() {
    20. 	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
    21.  
    22. 	int ret = 0;
    23. 	//初始化队列，要动态的创建SeqStack，根据user设定的大小创建
    24. //int stacksize ，表示user 要创建栈的大小
    25. //创建失败返回NULL
    26. 	LinkStack* linkstack = LinkStack_Create();
    27. 	if (linkstack == NULL) {
    28. 		ret = -1;
    29. 		printf("func LinkStack_Create error because linkstack = NULL return ret =-1\n");
    30. 		return ret;
    31. 	}
    32. 	ret = isEmptyLinkStack(linkstack);
    33. 	printf("isEmptyLinkStack = ret %d\n", ret);
    34.  
    35. 	ret = LinkStack_Length(linkstack);
    36. 	printf("LinkStack_Length = ret %d\n", ret);
    37.  
    38. 	Teacher tea1;
    39. 	tea1.age = 20;
    40. 	strcpy(tea1.name, (const char*)"tea1");
    41.  
    42. 	tea1.othername = (char *)malloc(sizeof(char) * 128);
    43. 	memset(tea1.othername, 0, sizeof(char) * 128);
    44. 	strcpy(tea1.othername, (const char*)"tea1othername");
    45.  
    46. 	tea1.stuname = (char **)malloc(sizeof(char *) * 5);
    47. 	memset(tea1.stuname, 0, sizeof(char *) * 5);
    48. 	for (size_t i = 0; i < 5; i++)
    49. 	{
    50. 		tea1.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
    51. 		memset(tea1.stuname[i], 0, sizeof(char) * 128);
    52. 		sprintf(tea1.stuname[i], "tea1stuname%d", i + 1);
    53. 	}
    54.  
    55.  
    56.  
    57. 	Teacher tea2;
    58. 	tea2.age = 22;
    59.  
    60. 	strcpy(tea2.name, (const char*)"tea2");
    61.  
    62. 	tea2.othername = (char *)malloc(sizeof(char) * 128);
    63. 	memset(tea2.othername, 0, sizeof(char) * 128);
    64. 	strcpy(tea2.othername, (const char*)"tea2othername");
    65.  
    66. 	tea2.stuname = (char **)malloc(sizeof(char *) * 5);
    67. 	memset(tea2.stuname, 0, sizeof(char *) * 5);
    68. 	for (size_t i = 0; i < 5; i++)
    69. 	{
    70. 		tea2.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
    71. 		memset(tea2.stuname[i], 0, sizeof(char) * 128);
    72. 		sprintf(tea2.stuname[i], "tea2stuname%d", i + 1);
    73. 	}
    74.  
    75.  
    76.  
    77. 	Teacher tea3;
    78. 	tea3.age = 33;
    79. 	strcpy(tea3.name, (const char*)"tea3");
    80.  
    81. 	tea3.othername = (char *)malloc(sizeof(char) * 128);
    82. 	memset(tea3.othername, 0, sizeof(char) * 128);
    83. 	strcpy(tea3.othername, (const char*)"tea3othername");
    84.  
    85. 	tea3.stuname = (char **)malloc(sizeof(char *) * 5);
    86. 	memset(tea3.stuname, 0, sizeof(char *) * 5);
    87. 	for (size_t i = 0; i < 5; i++)
    88. 	{
    89. 		tea3.stuname[i] = (char *)malloc(sizeof(char) * 128);//每个学生名字也有128个字符
    90. 		memset(tea3.stuname[i], 0, sizeof(char) * 128);
    91. 		sprintf(tea3.stuname[i], "tea3stuname%d", i + 1);
    92. 	}
    93.  
    94. 	ret = LinkStack_Insert(linkstack, (LinkStackNode * )&tea1);
    95. 	if (ret < 0) {
    96. 		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea1) func error ret =%d \n", ret);
    97. 		return ret;
    98. 	}
    99.  
    100. 	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea2);
    101. 	if (ret < 0) {
    102. 		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea2) func error ret =%d \n", ret);
    103. 		return ret;
    104. 	}
    105.  
    106. 	ret = LinkStack_Insert(linkstack, (LinkStackNode *)&tea3);
    107. 	if (ret < 0) {
    108. 		printf("LinkStack_Insert(linkstack, (LinkStackNode * )&tea3) func error ret =%d \n", ret);
    109. 		return ret;
    110. 	}
    111.  
    112. 	printf("-after-\n");
    113. 	ret = isEmptyLinkStack(linkstack);
    114. 	printf("isEmptyLinkStack = ret %d\n", ret);
    115.  
    116. 	ret = LinkStack_Length(linkstack);
    117. 	printf("LinkStack_Length = ret %d\n", ret);
    118.  
    119.  
    120.  
    121. 	while (LinkStack_Length(linkstack) > 0) {
    122. 		Teacher * temptea = (Teacher *)LinkStack_Get(linkstack);
    123. 		if (temptea == NULL) {
    124. 			printf("can not get find teacher\n");
    125. 		}
    126. 		printf("temptea->age = %d,temptea->name = %s,temptea->othername=%s\n",
    127. 			temptea->age,
    128. 			temptea->name,
    129. 			temptea->othername);
    130. 		for (size_t j = 0; j < 5; j++)
    131. 		{
    132. 			printf("temptea->stuname[%d] = %s,  ",
    133. 				j, temptea->stuname[j]);
    134. 		}
    135. 		Teacher * deltea = (Teacher *)LinkStack_Delete(linkstack);
    136. 		if (deltea == NULL) {
    137. 			printf("LinkStack_Delete seqstack error\n");
    138. 		}
    139. 		if (deltea->othername != NULL) {
    140. 			free(deltea->othername);
    141.  
    142. 		}
    143. 		if (deltea->stuname != NULL) {
    144. 			for (size_t i = 0; i < 5; i++)
    145. 			{
    146. 				if (deltea->stuname[i] != NULL) {
    147. 					free(deltea->stuname[i]);
    148. 				}
    149. 			}
    150. 			free(deltea->stuname);
    151. 			deltea->stuname = NULL;
    152. 		}
    153.  
    154. 		printf("\n");
    155. 	}
    156. 	printf("sss\n");
    157.  
    158. 	//销毁栈
    159. 	//成功 返回1 表示成功销毁栈 
    160. 	//失败 返回-1 表示该函数执行的时候有问题
    161. 	ret = LinkStack_Destory(linkstack);
    162.  
    163.  
    164. 	return 0;
    165.  
    166.  
    167.  
    168.  
    169.  
    170. }

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

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

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

    1. #define _CRT_SECURE_NO_WARNINGS
    2. #define _CRTDBG_MAP_ALLOC
    3. #include "iostream"
    4. #include <stdio.h>
    5. #include <stdlib.h>
    6.  
    7.  
    8. //几乎所有的编译器都具有检测括号是否匹配的能力，
    9. //那么如何实现编译器中的符号成对检测？如下字符串:
    10. //5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(
    11. //算法思路
    12. //
    13. //从第一个字符开始扫描
    14. //当遇见普通字符时忽略，
    15. //当遇见左括号时压入栈中
    16. //当遇见右括号时从栈中弹出栈顶符号，并进行匹配
    17. //匹配成功：继续读入下一个字符
    18. //匹配失败：立即停止，并报错
    19. //结束：
    20. //成功 : 所有字符扫描完毕，且栈为空
    21. //	失败：匹配失败或所有字符扫描完毕但栈非空
    22.  
    23. //总结：
    24. //当需要检测成对出现但又互不相邻的事物时可以使用栈“后进先出”的特性
    25.  
    26. char *err1 = (char *)"无法找到对应的右括号的 左括号";
    27. char *err2 = (char *)"该 左括号 没有对应的有括号";
    29. extern "C" {
    30. #include "004seqstack.h"
    31. }
    32.  
    33. int isLeft( char ch) {
    34. 	if ('(' == ch) {
    35. 		return 1;
    36. 	}
    37. 	return 0;
    38. }
    39.  
    40. int isRight(char ch) {
    41. 	if (')' == ch) {
    42. 		return 1;
    43. 	}
    44. 	return 0;
    45. }
    46.  
    47. void printerror(char* err,char *str, char *ptemp) {
    48. 	printf("err start");
    49. 	printf(err);
    50. 	printf("原始字符串如下\n");
    51. 	printf(str);
    52. 	printf("\n");
    53. 	printf("error位置如下\n");
    54.  
    55. 	int num = ptemp - str;
    56. 	while (num > 0 ) {
    57. 		printf(" ");
    58. 		--num;
    59. 	}
    60. 	printf("|\n");
    61. 	printf("err end");
    62. }
    63.  
    64. void testchar(char *str) {
    65. 	SeqStack * seqstack = createSeqStack(1024);
    66. 	if (seqstack ==NULL) {
    67. 		printf("func testchar error because seqstack==NULL\n");
    68. 		return;
    69. 	}
    70.  
    71. 	if (str == NULL) {
    72. 		printf("testchar func error because str==NULL\n");
    73. 		return;
    74. 	}
    75. 	char *ptemp = str;//让辅助指针变量指向传递过来的str
    76. 	while (*(ptemp) != '\0') {
    77. 		if (isLeft(*ptemp)) { 当遇见左括号时压入栈中.判断是否是符号，如果是 左括号 符号，则要进栈，
    78. 			push_SeqStack(seqstack,ptemp);
    79.  
    80. 		}
    81. 		if (isRight(*ptemp)) {//当遇见右括号时从栈中弹出栈顶符号，并进行匹配
    82. 			//如果这时候栈中啥也没有，就有问题，直接break;
    83. 			if (size_SeqStack(seqstack) == 0) {
    84. 				printerror(err1,str,ptemp);
    85. 				break;
    86. 			}
    87. 			pop_SeqStack(seqstack);
    88. 		}
    89. 		ptemp++;
    90. 	}
    91. 	//当将整个字符串都弄完成后，检查栈中是否有元素，如果栈中有元素，说明有左括号没有匹配
    92. 	while (size_SeqStack(seqstack) > 0 ) {
    93. 		printerror(err2, str, (char *)top_SeqStack(seqstack));
    94. 		pop_SeqStack(seqstack);
    95. 	}
    96. }
    97.  
    98. int main() {
    99. 	int ret = 0;
    100. 	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
    101. 	//char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1) - (1 + 3(";
    102. 	char* sourcestr = (char *)"5 + 5 * (6) + 9 / 3 * 1 - (1 + 3(";
    103. 	testchar(sourcestr);
    104.  
    105. 	return ret;
    106. }

  • 相关阅读:
    利用Kali进行DDOS泛洪演练
    Kubernetes 控制平面组件：etcd
    Windows10不常用操作（录屏、开启超级管理员、关闭自动IP配置、Edge崩溃等）
    当资本对于区块链的关注开始减退，一场降温开始在区块链行业上演
    LeCun和Bengio“吵”起来了，人工智能是“潘多拉魔盒”吗？
    如何确认串口波特率
    SpringBoot集成MyBatis
    django DRF增删改查查
    如何才能在人力RPO蓝海项目中实现盈利呢?
    MySQL单表查询进阶
  • 原文地址：https://blog.csdn.net/hunandede/article/details/138039026