devbox
Guff_9hys
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

线性表的简单实现_线性表怎么创建

作者：Guff_9hys | 2024-08-11 21:41:52

赞

踩

线性表怎么创建

1. 写在前面

作为计算机领域的核心基础理论学科之一——数据结构，其讨论研究的主要相关内容为，数据是如何在内存中进行存储与管理的；我们知道，应用程序（.exe文件）在运行时，会将存储在磁盘中的数据读入到内存中，再进行相应的处理操作；而在这一过程中，数据在内存中的存储组织方式就显得十分的重要啦；在算法中，根据实际业务需求，采用合适的数据组织方式，能极大地发挥出算法的威力，提高算法的性能。而笔者今天的内容，主要是对近期学习线性表这一数据结构知识的总结与梳理，内容如下：

2. 线性表的定义

什么是线性表？（What）

线性表（linear list）： 是n个具有相同特性数据元素的有限序列。

常见的线性表：

  • 顺序表  -  （数组）
  • 链表
  • 栈
  • 队列
  • 字符串

值得注意的是：线性表在逻辑上是连续的，但在物理存储结构上不一定是连续的，如链表。

3. 顺序表

3.1 顺序表的定义

什么是顺序表？（What）

顺序表：用一段物理地址连续的存储单元依次存储数据元素的线性结构

常见顺序表：

  • 静态顺序表：使用定长数组存储元素
  • 动态顺序表：使用动态开辟的元素存储元素

3.2 顺序表的实现

支持动态增长的顺序表实现

代码实现

SeqList.h ：类型与函数的声明

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. #define __DEBUG__ 0
  7.  
  8. // 静态顺序表
  9. #if __DEBUG__
  10. #define N 100  // 定长数组的大小
  11. typedef int SLDdataType;  // 重命名顺序表的数据类型
  12.  
  13. struct SeqList
  14. {
  15. 	SLDdataType a[N]; // 定长数组
  16. 	int size;  // 已存储的数据个数
  17. };
  18. #endif
  19.  
  20. // 动态顺序表
  21. typedef int SLDataType;
  22.  
  23. typedef struct SeqList
  24. {
  25. 	SLDataType* a;  // 指向动态开辟的数组
  26. 	int size;   // 有效的数据个数
  27. 	int capacity;  // 动态数组的容量
  28. }SL;
  29.  
  30. // 功能操作
  31. void SeqListInit(SL* ps); // 初始化
  32. void SeqListPrint(SL* ps); // 打印
  33. void SeqListDestory(SL* ps); // 销毁
  34. void SeqListCheckCapacity(SL* ps); // 检查容量
  35. void SeqListPushBack(SL* ps, SLDataType x); // 尾插
  36. void SeqListPopBack(SL* ps); // 尾删
  37. void SeqListPushFront(SL* ps, SLDataType x); // 头插
  38. void SeqListPopFront(SL* ps); // 头删
  39. void SeqListInsert(SL* ps, int pos, SLDataType x); // 任意位置插入
  40. void SeqListErase(SL* ps, int pos); // 任意位置删除
  41. void SeqListModify(SL* ps, int pos, SLDataType x); // 修改
  42. int SeqListFind(SL* ps, SLDataType x); // 查找

SeqList.c  : 功能实现

  1. #include "SeqList.h"
  2.  
  3. // 初始化
  4. void SeqListInit(SL* ps)
  5. {
  6. 	assert(ps);
  7. 	ps->a = NULL;
  8. 	ps->size = 0;
  9. 	ps->capacity = 0;
  10. }
  11.  
  12. // 销毁
  13. void SeqListDestory(SL* ps)
  14. {
  15. 	if (ps->a)
  16. 	{
  17. 		free(ps->a);
  18. 		ps->a = NULL;
  19. 		ps->capacity = ps->size = 0;
  20. 	}
  21. }
  22.  
  23. // 打印
  24. void SeqListPrint(SL* ps)
  25. {
  26. 	assert(ps);
  27. 	int i = 0;
  28. 	for (i = 0; i < ps->size; i++)
  29. 	{
  30. 		printf("%d ", ps->a[i]);
  31. 	}
  32. 	printf("\n");
  33. }
  34.  
  35. // 扩容
  36. void SeqListCheckCapacity(SL* ps)
  37. {
  38. 	assert(ps);
  39.  
  40. 	if (ps->size == ps->capacity)
  41. 	{
  42. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  43. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
  44. 		if (tmp != NULL)
  45. 		{
  46. 			ps->a = tmp;
  47. 		}
  48. 		else
  49. 		{
  50. 			perror("CheckCapacity::realloc\n");
  51. 			exit(-1);
  52. 		}
  53. 		ps->capacity = newCapacity;
  54. 	}
  55. }
  56.  
  57. // 尾插
  58. void SeqListPushBack(SL* ps, SLDataType x)
  59. {
  60. 	SeqListInsert(ps, ps->size, x);
  61. 	//assert(ps);
  62. 	 检查容量空间
  63. 	//SeqListCheckCapacity(ps);
  64.  
  65. 	//ps->a[ps->size] = x;
  66. 	//ps->size++;
  67. }
  68.  
  69. // 头插
  70. void SeqListPushFront(SL* ps, SLDataType x)
  71. {
  72. 	SeqListInsert(ps, 0, x);
  73. 	//assert(ps);
  74. 	//SeqListCheckCapacity(ps);
  75.  
  76. 	 挪动数据
  77. 	//int end = ps->size - 1;
  78. 	//while (end >= 0)
  79. 	//{
  80. 	//	ps->a[end + 1] = ps->a[end];
  81. 	//	end--;
  82. 	//}
  83. 	//ps->a[0] = x;
  84. 	//ps->size++;
  85. }
  86.  
  87. // 尾删
  88. void SeqListPopBack(SL* ps)
  89. {
  90. 	SeqListErase(ps, ps->size - 1);
  91. 	//assert(ps);
  92.  
  93. 	 暴力检查
  94. 	//assert(ps->size);
  95. 	ps->size--;
  96. 	 避免越界访问越界访问
  97. 	//if (ps->size)
  98. 	//{
  99. 	//	ps->size--;
  100. 	//}
  101. 	//else
  102. 	//{
  103. 	//	printf("SeqList is already empty"); // 温柔检查
  104. 	//	exit(-1);
  105. 	//}
  106. 	
  107. }
  108.  
  109. // 头删
  110. void SeqListPopFront(SL* ps)
  111. {
  112. 	SeqListErase(ps, 0);
  113. 	//assert(ps);
  114.  
  115. 	//assert(ps->size);
  116. 	//int i = 0;
  117. 	//if (ps->size)
  118. 	//{
  119. 	//	for (i = 0; i < ps->size - 1; i++)
  120. 	//	{
  121. 	//		ps->a[i] = ps->a[i + 1];
  122. 	//	}
  123. 	//	ps->size--;
  124. 	//}
  125. 	//else
  126. 	//{
  127. 	//	printf("SeqList is already empty"); // 温柔检查
  128. 	//	exit(-1);
  129. 	//}
  130. }
  131.  
  132. // 任意位置插入
  133. void SeqListInsert(SL* ps, int pos, SLDataType x)
  134. {
  135. 	// 防御式检查
  136. 	assert(ps); 
  137. 	assert(pos >= 0 && pos <= ps->size);
  138. 	SeqListCheckCapacity(ps);
  139. 	int end = ps->size - 1;
  140. 	while (end >= pos)
  141. 	{
  142. 		ps->a[end + 1] = ps->a[end];
  143. 		end--;
  144. 	}
  145. 	ps->a[pos] = x;
  146. 	ps->size++;
  147. }
  148.  
  149. // 任意位置删除
  150. void SeqListErase(SL* ps, int pos)
  151. {
  152. 	assert(ps);
  153. 	assert(pos >= 0 && pos < ps->size);
  154.  
  155. 	int begin = pos;
  156. 	while (begin < ps->size-1) // 边界控制
  157. 	{
  158. 		ps->a[begin] = ps->a[begin + 1];
  159. 		begin++;
  160. 	}
  161. 	ps->size--;
  162. }
  163.  
  164. // 查找
  165. int SeqListFind(SL* ps, SLDataType x)
  166. {
  167. 	assert(ps);
  168.  
  169. 	int i = 0;
  170. 	for (i = 0; i < ps->size; i++)
  171. 	{
  172. 		if (ps->a[i] == x)
  173. 		{
  174. 			return i; // 返回下标
  175. 		}
  176. 	}
  177. 	return -1;
  178. }
  179.  
  180. // 修改
  181. void SeqListModify(SL* ps, int pos, SLDataType x)
  182. {
  183. 	assert(ps);
  184. 	assert(pos >= 0 && pos < ps->size);
  185. 	ps->a[pos] = x;
  186. }

New.c : 功能测试 

  1. #include "SeqList.h"
  2.  
  3. void Test1()
  4. {
  5. 	SL s1;
  6. 	SeqListInit(&s1);
  7. 	SeqListPushBack(&s1, 1);
  8. 	SeqListPushBack(&s1, 2);
  9. 	SeqListPushBack(&s1, 3);
  10. 	SeqListPushBack(&s1, 4);
  11. 	SeqListPrint(&s1);
  12. 	SeqListPushBack(&s1, 5);
  13. 	SeqListPushBack(&s1, 4);
  14. 	SeqListPushBack(&s1, 3);
  15. 	SeqListPushBack(&s1, 2);
  16. 	SeqListPushBack(&s1, 1);
  17. 	SeqListPrint(&s1);
  18. }
  19.  
  20. void Test2()
  21. {
  22. 	SL s1;
  23. 	SL* ps = &s1;
  24. 	SeqListInit(ps);
  25. 	SeqListPushFront(&s1, 5);
  26. 	SeqListPushFront(&s1, 4);
  27. 	SeqListPushFront(&s1, 3);
  28. 	SeqListPushFront(&s1, 2);
  29. 	SeqListPushFront(&s1, 1);
  30. 	SeqListPrint(ps);
  31. 	SeqListPushBack(&s1, 4);
  32. 	SeqListPushBack(&s1, 3);
  33. 	SeqListPushBack(&s1, 2);
  34. 	SeqListPushBack(&s1, 1);
  35. 	SeqListPrint(ps);
  36.  
  37. }
  38.  
  39. void Test3()
  40. {
  41. 	SL s1;
  42. 	SL* ps = &s1;
  43. 	SeqListInit(ps);
  44. 	SeqListPushFront(ps, 5);
  45. 	SeqListPushFront(ps, 4);
  46. 	SeqListPushFront(ps, 3);
  47. 	SeqListPushFront(ps, 2);
  48. 	SeqListPushFront(ps, 1);
  49. 	SeqListPrint(ps);
  50. 	SeqListPopBack(ps);
  51. 	SeqListPopBack(ps);
  52. 	SeqListPopBack(ps);
  53. 	SeqListPopBack(ps);
  54. 	SeqListPopBack(ps);
  55. 	SeqListPopBack(ps);
  56. 	SeqListPopBack(ps);
  57. 	SeqListPushFront(ps, 2);
  58. 	SeqListPushFront(ps, 3);
  59. 	SeqListPushFront(ps, 2);
  60.  
  61. 	SeqListPrint(ps);
  62. 	SeqListDestory(ps);
  63. }
  64.  
  65. void Test4()
  66. {
  67. 	SL s1;
  68. 	SL* ps = &s1;
  69. 	SeqListInit(ps);
  70. 	SeqListPushFront(&s1, 5);
  71. 	SeqListPushFront(&s1, 4);
  72. 	SeqListPushFront(&s1, 3);
  73. 	SeqListPushFront(&s1, 2);
  74. 	SeqListPushFront(&s1, 1);
  75. 	SeqListPrint(ps);
  76. 	SeqListPopFront(ps);
  77. 	SeqListPopFront(ps);
  78. 	SeqListPopFront(ps);
  79. 	SeqListPopFront(ps);
  80. 	SeqListPopFront(ps);
  81. 	SeqListPopFront(ps);
  82. 	SeqListPopFront(ps);
  83. 	SeqListPrint(ps);
  84. }
  85.  
  86. void Test5()
  87. {
  88. 	SL s1;
  89. 	SL* ps = &s1;
  90. 	SeqListInit(ps);
  91. 	SeqListPushFront(&s1, 5);
  92. 	SeqListPushFront(&s1, 4);
  93. 	SeqListPushFront(&s1, 3);
  94. 	SeqListPushFront(&s1, 2);
  95. 	SeqListPushFront(&s1, 1);
  96. 	SeqListPrint(ps);
  97. 	SeqListInsert(ps, 0, 8);
  98. 	SeqListPrint(ps);
  99. }
  100.  
  101. void Test6()
  102. {
  103. 	SL s1;
  104. 	SL* ps = &s1;
  105. 	SeqListInit(ps);
  106. 	SeqListPushFront(&s1, 5);
  107. 	SeqListPushFront(&s1, 4);
  108. 	SeqListPushFront(&s1, 3);
  109. 	SeqListPushFront(&s1, 2);
  110. 	SeqListPushFront(&s1, 1);
  111. 	SeqListPrint(ps);
  112. 	SeqListErase(ps, 2);
  113. 	SeqListPrint(ps);
  114. 	SeqListErase(ps, 0);
  115. 	SeqListPrint(ps);
  116. 	SeqListErase(ps, ps->size-1);
  117. 	SeqListPrint(ps);
  118. 	SeqListPopFront(ps);
  119. 	SeqListPushFront(ps, 6);
  120. 	SeqListPrint(ps);
  121. 	SeqListPopBack(ps);
  122. 	SeqListPrint(ps);
  123.  
  124. }
  125.  
  126. void Test7()
  127. {
  128. 	SL s1;
  129. 	SL* ps = &s1;
  130. 	SeqListInit(ps);
  131. 	SeqListPushFront(&s1, 5);
  132. 	SeqListPushFront(&s1, 4);
  133. 	SeqListPushFront(&s1, 3);
  134. 	SeqListPushFront(&s1, 2);
  135. 	SeqListPushFront(&s1, 1);
  136. 	SeqListPrint(ps);
  137. 	int x = 0;
  138. 	printf("请输入你要删除的值:> ");
  139. 	scanf("%d", &x);
  140. 	int pos = SeqListFind(ps, x);
  141. 	if (pos != -1)
  142. 	{
  143. 		SeqListErase(ps, pos);
  144. 	}
  145. 	else
  146. 	{
  147. 		printf("没有找到\n");
  148. 	}
  149. 	SeqListPrint(ps);
  150.  
  151. }
  152.  
  153. void Test8()
  154. {
  155. 	SL s1;
  156. 	SL* ps = &s1;
  157. 	SeqListInit(ps);
  158. 	SeqListPushFront(&s1, 5);
  159. 	SeqListPushFront(&s1, 4);
  160. 	SeqListPushFront(&s1, 3);
  161. 	SeqListPushFront(&s1, 2);
  162. 	SeqListPushFront(&s1, 1);
  163. 	SeqListPrint(ps);
  164. 	int y = 0;
  165. 	int z = 0;
  166. 	printf("请输入你要修改的值和修改之后的值:> ");
  167. 	scanf("%d %d", &y, &z);
  168. 	int pos = SeqListFind(ps, y);
  169. 	if (pos != -1)
  170. 	{
  171. 		SeqListModify(ps, pos, z);
  172. 	}
  173. 	else
  174. 	{
  175. 		printf("没有找到\n");
  176. 	}
  177. 	SeqListPrint(ps);
  178. }
  179.  
  180. int main()
  181. {
  182. 	//Test1();
  183. 	//Test2();
  184. 	//Test3();
  185. 	//Test4();
  186. 	//Test5();
  187. 	//Test6();
  188. 	//Test7();
  189. 	Test8();
  190. 	return 0;
  191. }

运行结果

4. 链表

4.1 链表的定义

什么是链表？（What）

链表：物理存储非连续，数据存储的逻辑顺序是连续的线性存储结构

常见链表：

  • 无头单向非循环链表
  • 带头双向循环链表

4.2 链表的实现

无头单向非循环链表的实现

代码实现

SList.h ： 功能与类型的声明

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. typedef int SLDataType;
  7.  
  8. typedef struct SListNode
  9. {
  10. 	SLDataType data; // 存储的数据
  11. 	struct SListNode* next; // 指向下一个节点
  12. }SLNode;
  13.  
  14.  
  15. void SListPrint(SLNode* phead);    // 打印  
  16. SLNode* CreateSListNode(SLDataType* x); // 创建新节点
  17. void SListPushBack(SLNode** pphead, SLDataType x);   // 尾插
  18. void SListPushFront(SLNode** pphead, SLDataType x);  // 头插
  19. void SListPopBack(SLNode** pphead);  // 尾删
  20. void SListPopFront(SLNode** pphead);  // 头删
  21. SLNode* SListFind(SLNode* phead, SLDataType x);  // 查找
  22. void SListModify(SLNode* pos, SLDataType x, SLDataType y);   // 修改
  23. void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x); // 在指定位置之前插入
  24. void SListInsertAfter(SLNode* pos, SLDataType x); // 在指定位置之后插入
  25. void SListErase(SLNode** pphead, SLNode* pos);  // 删除指定位置的节点
  26. void SListEraseAfter(SLNode* pos); // 在指定位置之后删除

SList.c :  功能实现

  1. #include"SList.h"
  2.  
  3. // 打印
  4. void SListPrint(SLNode* phead)
  5. {
  6. 	SLNode* cur = phead;
  7. 	while (cur)
  8. 	{
  9. 		printf("%d->", cur->data);
  10. 		cur = cur->next;
  11. 	}
  12. 	printf("NULL\n");
  13. }
  14.  
  15. // 创建新节点
  16. SLNode* CreateSListNode(SLDataType* x)
  17. {
  18. 	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
  19. 	assert(newnode);
  20.  
  21. 	newnode->data = x;
  22. 	newnode->next = NULL;
  23.  
  24. 	return newnode;
  25. }
  26.  
  27. // 尾插  想改变外部的指针（实参），就需要传入指针的地址；想在函数中改变外部变量（实参）的内容，就需要传入该外部变量的地址
  28. // 因为函数的形参只是实参的一份临时拷贝，与实参没有直接联系，只是模拟实参的效果，形参的改变对实参没有直接的影响
  29. void SListPushBack(SLNode** pphead, SLDataType x)
  30. {
  31. 	assert(pphead);
  32. 	// 允许空链表传入
  33. 	SLNode* cur = *pphead;
  34. 	SLNode* newnode = CreateSListNode(x);
  35.  
  36. 	if (*pphead == NULL)
  37. 	{
  38. 		*pphead = newnode;
  39. 	}
  40. 	else
  41. 	{
  42. 		while (cur->next) // 找尾节点
  43. 		{
  44. 			cur = cur->next;
  45. 		}
  46. 		
  47. 		cur->next = newnode;
  48. 	}
  49. 	// 只有当节点不被需要了，才进行free操作
  50. 	// 函数结束，函数中定义的局部变量被销毁，但malloc的内存空间依旧存在有效
  51. }
  52.  
  53. // 头插  使用二级指针，与外部的phead建立直接的联系，头插完成之后，phead要指向新的头节点
  54. void SListPushFront(SLNode** pphead, SLDataType x)
  55. {
  56. 	assert(pphead);
  57. 	// 允许空链表传入
  58. 	/*assert(*pphead);*/
  59. 	SLNode* cur = *pphead;
  60. 	SLNode* newnode = CreateSListNode(x);
  61.  
  62. 	newnode->next = cur;
  63. 	*pphead = newnode;
  64. }
  65.  
  66. // 尾删
  67. void SListPopBack(SLNode** pphead)
  68. {
  69. 	assert(pphead);
  70. 	// 链表本就为空，就不能再进行删除了
  71. 	assert(*pphead);
  72.  
  73. 	// 只有一个节点
  74. 	if ((*pphead)->next == NULL)
  75. 	{
  76. 		free(*pphead);
  77. 		*pphead = NULL;  // 改变了phead指针的值，所以要传二级指针
  78. 	}
  79. 	else  // 多个节点
  80. 	{
  81. 		// 找尾节点的前一个节点
  82. 		SLNode* prev = *pphead;
  83. 		while (prev->next->next)  // 当只有一个节点时，会有越界访问的问题
  84. 		{
  85. 			prev = prev->next;
  86. 		}
  87. 		SLNode* tail = prev->next;
  88. 		free(tail); // 释放掉tail指针指向的结构体空间; 但只有一个节点时，则会发生释放NULL指针的的错误
  89. 		prev->next = NULL; // 将尾节点的前一个节点的next指针，置空
  90. 	}
  91. 	
  92. }
  93.  
  94. // 头删
  95. void SListPopFront(SLNode** pphead)
  96. {
  97. 	assert(pphead);
  98. 	// 链表本就为空，就不能再进行删除了
  99. 	assert(*pphead);
  100. 	SLNode* next = (*pphead)->next;
  101. 	free(*pphead);  // 将结构体节点所占用的空间，进行释放，即销毁
  102. 	*pphead = next; 
  103. }
  104.  
  105. // 查找
  106. SLNode* SListFind(SLNode* phead, SLDataType x)
  107. {
  108. 	
  109. 	// 空链表无法进行查找
  110. 	assert(phead);
  111. 	SLNode* cur = phead;
  112. 	while (cur->next)  //  逻辑有问题，如果查找的是尾节点，则将尾节点的情况直接跳过而没有进行检查
  113. 	{
  114. 		if (cur->data == x)
  115. 		{
  116. 			return cur;
  117. 		}
  118. 		cur = cur->next;
  119. 	}
  120. 	if (cur->data == x) // 检查一下跳过的尾节点
  121. 		return cur;
  122. 	else
  123. 		return NULL;
  124. }
  125.  
  126. // 修改
  127. void SListModify(SLNode* phead, SLDataType x, SLDataType y)
  128. {
  129. 	SLNode* cur = SListFind(phead, x);
  130. 	if (cur)
  131. 	{
  132. 		cur->data = y;
  133. 	}
  134. 	else
  135. 	{
  136. 		printf("%d不存在\n", x);
  137. 	}
  138. }
  139.  
  140. // 在pos节点之前插入
  141. void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x)
  142. {
  143. 	// 以防恶意插入
  144. 	assert(pos);
  145. 	assert(pphead);
  146. 	// 空链表也可以传入
  147. 	SLNode* newnode = CreateSListNode(x);
  148. 	if (*pphead == NULL)
  149. 	{
  150. 		newnode->next = *pphead;
  151. 		*pphead = newnode;
  152. 	}
  153. 	else
  154. 	{
  155. 		// 找到pos节点的前一个节点
  156. 		SLNode* prev = *pphead;
  157. 		while (prev->next != pos)
  158. 		{
  159. 			prev = prev->next;
  160. 		}
  161. 		newnode->next = pos;
  162. 		prev->next = newnode;
  163. 	}
  164. }
  165.  
  166. // 在pos之后进行插入
  167. void SListInsertAfter(SLNode* pos, SLDataType x)
  168. {
  169. 	// 以防恶意插入
  170. 	assert(pos);
  171. 	// 空链表无法进行查找，已在SListFind内进行断言，保证了pos的有效性
  172. 	SLNode* newnode = CreateSListNode(x);
  173. 	
  174. 	newnode->next = pos->next;
  175. 	pos->next = newnode;
  176. }
  177.  
  178. // 删除指定位置的节点
  179. void SListErase(SLNode** pphead, SLNode* pos)
  180. {
  181. 	// 以防恶意删除
  182. 	assert(pos);
  183. 	assert(pphead);
  184. 	// 空链表无法进行删除，已在SListFind内进行断言，保证了*phead和pos的有效性
  185. 	// 找到pos的前一个节点
  186. 	if ((*pphead)->next == NULL)  // 只有一个节点时
  187. 	{
  188. 		free(*pphead);
  189. 		*pphead = NULL;
  190. 	}
  191. 	else if (*pphead == pos)  // 有多个节点时，要删除头节点
  192. 	{
  193. 		*pphead = pos->next;
  194. 		free(pos);
  195. 	}
  196. 	else   // 有多个节点时，删除其它节点
  197. 	{
  198. 		SLNode* prev = *pphead;
  199. 		while (prev->next != pos)
  200. 		{
  201. 			prev = prev->next;
  202. 		}
  203. 		prev->next = pos->next;
  204. 		free(pos);
  205. 	}
  206. }
  207.  
  208. // 在指定位置之后删除
  209. void SListEraseAfter(SLNode* pos)
  210. {
  211. 	// 以防恶意删除
  212. 	assert(pos);
  213. 	// 空链表无法进行删除，已在SListFind内进行断言，pos的有效性
  214. 	if (pos->next == NULL)  // pos已为尾节点
  215. 	{
  216. 		return;
  217. 	}
  218. 	else
  219. 	{
  220. 		SLNode* after = pos->next->next;
  221. 		free(pos->next);
  222. 		pos->next = after;
  223. 	}
  224. }

New.c :  功能测试

  1. #include "SList.h"
  2.  
  3. void Test1()
  4. {
  5. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  6. 	assert(n1);
  7.  
  8. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  9. 	assert(n2);
  10.  
  11. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  12. 	assert(n3);
  13.  
  14. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  15. 	assert(n4);
  16.  
  17. 	n1->data = 1;
  18. 	n2->data = 2;
  19. 	n3->data = 3;
  20. 	n4->data = 4;
  21.  
  22. 	n1->next = n2;
  23. 	n2->next = n3;
  24. 	n3->next = n4;
  25. 	n4->next = NULL;
  26. 	SListPrint(n1);
  27. }
  28.  
  29. void Test2()
  30. {
  31. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  32. 	assert(n1);
  33.  
  34. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  35. 	assert(n2);
  36.  
  37. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  38. 	assert(n3);
  39.  
  40. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  41. 	assert(n4);
  42.  
  43. 	n1->data = 1;
  44. 	n2->data = 2;
  45. 	n3->data = 3;
  46. 	n4->data = 4;
  47.  
  48. 	n1->next = n2;
  49. 	n2->next = n3;
  50. 	n3->next = n4;
  51. 	n4->next = NULL;
  52. 	SListPrint(n1);
  53.  
  54. 	SListPushBack(&n1, 5);
  55. 	SListPrint(&n1);
  56. 	SListPushBack(&n1, 4);
  57. 	SListPushBack(&n1, 3);
  58. 	SListPushBack(&n1, 2);
  59. 	SListPushBack(&n1, 1);
  60. 	SListPrint(n1);
  61.  
  62. }
  63.  
  64. void Test3()
  65. {
  66. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  67. 	assert(n1);
  68.  
  69. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  70. 	assert(n2);
  71.  
  72. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  73. 	assert(n3);
  74.  
  75. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  76. 	assert(n4);
  77.  
  78. 	n1->data = 1;
  79. 	n2->data = 2;
  80. 	n3->data = 3;
  81. 	n4->data = 4;
  82.  
  83. 	n1->next = n2;
  84. 	n2->next = n3;
  85. 	n3->next = n4;
  86. 	n4->next = NULL;
  87. 	SListPrint(n1);
  88. 	SListPushFront(&n1, 0);
  89. 	SListPushFront(&n1, -1);
  90. 	SListPushFront(&n1, -2);
  91. 	SListPushFront(&n1, -3);
  92. 	SListPushFront(&n1, -4);
  93.  
  94. 	SListPrint(n1);
  95.  
  96. }
  97.  
  98. void Test4()
  99. {
  100. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  101. 	assert(n1);
  102.  
  103. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  104. 	assert(n2);
  105.  
  106. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  107. 	assert(n3);
  108.  
  109. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  110. 	assert(n4);
  111.  
  112. 	n1->data = 1;
  113. 	n2->data = 2;
  114. 	n3->data = 3;
  115. 	n4->data = 4;
  116.  
  117. 	n1->next = n2;
  118. 	n2->next = n3;
  119. 	n3->next = n4;
  120. 	n4->next = NULL;
  121. 	SListPrint(n1);
  122. 	SLNode** pphead = &n1;
  123. 	SListPopFront(pphead);
  124. 	SListPopFront(pphead);
  125. 	SListPopFront(pphead);
  126. 	SListPopFront(pphead);
  127. 	SListPopFront(pphead);
  128.  
  129. 	SListPrint(n1);
  130.  
  131. }
  132.  
  133. void Test5()
  134. {
  135. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  136. 	assert(n1);
  137.  
  138. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  139. 	assert(n2);
  140.  
  141. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  142. 	assert(n3);
  143.  
  144. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  145. 	assert(n4);
  146.  
  147. 	n1->data = 1;
  148. 	n2->data = 2;
  149. 	n3->data = 3;
  150. 	n4->data = 4;
  151.  
  152. 	n1->next = n2;
  153. 	n2->next = n3;
  154. 	n3->next = n4;
  155. 	n4->next = NULL;
  156. 	SListPrint(n1);
  157. 	SLNode** pphead = &n1;
  158. 	SListPopBack(pphead);
  159. 	SListPrint(n1);
  160. 	SListPopBack(pphead);
  161. 	SListPrint(n1);
  162. 	SListPopBack(pphead);
  163. 	SListPrint(n1);
  164. 	SListPopBack(pphead);
  165.  
  166. 	SListPrint(n1);
  167. }
  168.  
  169. void Test6()
  170. {
  171. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  172. 	assert(n1);
  173.  
  174. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  175. 	assert(n2);
  176.  
  177. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  178. 	assert(n3);
  179.  
  180. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  181. 	assert(n4);
  182.  
  183. 	n1->data = 1;
  184. 	n2->data = 2;
  185. 	n3->data = 3;
  186. 	n4->data = 4;
  187.  
  188. 	n1->next = n2;
  189. 	n2->next = n3;
  190. 	n3->next = n4;
  191. 	n4->next = NULL;
  192. 	SListPrint(n1);
  193. 	SLNode* phead = n1;
  194. 	int x = 0;
  195. 	int y = 0;
  196. 	printf("请输入要修改的值和修改之后的值:> ");
  197. 	scanf("%d %d", &x, &y);
  198. 	SListModify(phead, x, y);
  199. 	SListPrint(n1);
  200. }
  201. void Test7()
  202. {
  203. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  204. 	assert(n1);
  205.  
  206. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  207. 	assert(n2);
  208.  
  209. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  210. 	assert(n3);
  211.  
  212. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  213. 	assert(n4);
  214.  
  215. 	n1->data = 1;
  216. 	n2->data = 2;
  217. 	n3->data = 3;
  218. 	n4->data = 4;
  219.  
  220. 	n1->next = n2;
  221. 	n2->next = n3;
  222. 	n3->next = n4;
  223. 	n4->next = NULL;
  224. 	SListPrint(n1);
  225. 	SLNode* phead = n1;
  226. 	SLNode** pphead = &n1;
  227. 	int x = 0;
  228. 	int y = 0;
  229. 	printf("输入指定的插入位置与要插入的数字（在该位置之前插入):> ");
  230. 	scanf("%d %d", &x, &y);
  231. 	SLNode* pos = SListFind(phead, x);
  232. 	SListInsert(pphead, pos, y);
  233. 	SListPrint(n1);
  234.  
  235. }
  236.  
  237. void Test8()
  238. {
  239. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  240. 	assert(n1);
  241.  
  242. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  243. 	assert(n2);
  244.  
  245. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  246. 	assert(n3);
  247.  
  248. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  249. 	assert(n4);
  250.  
  251. 	n1->data = 1;
  252. 	n2->data = 2;
  253. 	n3->data = 3;
  254. 	n4->data = 4;
  255.  
  256. 	n1->next = n2;
  257. 	n2->next = n3;
  258. 	n3->next = n4;
  259. 	n4->next = NULL;
  260. 	SListPrint(n1);
  261. 	SLNode* phead = n1;
  262. 	SLNode** pphead = &n1;
  263. 	int x = 0;
  264. 	int y = 0;
  265. 	printf("输入指定的插入位置与要插入的数字（在该位置之后插入):> ");
  266. 	scanf("%d %d", &x, &y);
  267. 	SLNode* pos = SListFind(phead, x);
  268. 	SListInsertAfter(pos, y);
  269. 	SListPrint(n1);
  270.  
  271. }
  272.  
  273. void Test9()
  274. {
  275. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  276. 	assert(n1);
  277.  
  278. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  279. 	assert(n2);
  280.  
  281. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  282. 	assert(n3);
  283.  
  284. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  285. 	assert(n4);
  286.  
  287. 	n1->data = 1;
  288. 	n2->data = 2;
  289. 	n3->data = 3;
  290. 	n4->data = 4;
  291.  
  292. 	n1->next = n2;
  293. 	n2->next = n3;
  294. 	n3->next = n4;
  295. 	n4->next = NULL;
  296. 	SListPrint(n1);
  297. 	SLNode* phead = n1;
  298. 	SLNode** pphead = &n1;
  299. 	int x = 0;
  300. 	printf("输入要删除的数字:> ");
  301. 	scanf("%d", &x);
  302. 	SLNode* pos = SListFind(phead, x);
  303. 	SListErase(pphead, pos);
  304. 	SListPrint(n1);
  305. }
  306.  
  307. void Test10()
  308. {
  309. 	SLNode* n1 = (SLNode*)malloc(sizeof(SLNode));
  310. 	assert(n1);
  311.  
  312. 	SLNode* n2 = (SLNode*)malloc(sizeof(SLNode));
  313. 	assert(n2);
  314.  
  315. 	SLNode* n3 = (SLNode*)malloc(sizeof(SLNode));
  316. 	assert(n3);
  317.  
  318. 	SLNode* n4 = (SLNode*)malloc(sizeof(SLNode));
  319. 	assert(n4);
  320.  
  321. 	n1->data = 1;
  322. 	n2->data = 2;
  323. 	n3->data = 3;
  324. 	n4->data = 4;
  325.  
  326. 	n1->next = n2;
  327. 	n2->next = n3;
  328. 	n3->next = n4;
  329. 	n4->next = NULL;
  330. 	SListPrint(n1);
  331. 	SLNode* phead = n1;
  332. 	SLNode** pphead = &n1;
  333. 	int x = 0;
  334. 	printf("输入所删除数字的前一个数字:> ");
  335. 	scanf("%d", &x);
  336. 	SLNode* pos = SListFind(phead, x);
  337. 	SListEraseAfter(pos);
  338. 	SListPrint(n1);
  339. }
  340.  
  341. int main()
  342. {
  343. 	//Test1();
  344. 	//Test2();
  345. 	//Test3();
  346. 	//Test4();
  347. 	//Test5();
  348. 	//Test6();
  349. 	//Test7();
  350. 	//Test8();
  351. 	//Test9();
  352. 	Test10();
  353. 	return 0;
  354. }

运行结果

带头双向循环链表的实现

代码实现

DList.h ：功能与类型的声明

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5. #include<assert.h>
  6.  
  7.  
  8. typedef int LTDataType;
  9.  
  10. typedef struct ListNode
  11. {
  12. 	struct ListNode* next;  // 后继指针
  13. 	struct ListNode* prev;  // 前驱指针
  14. 	LTDataType data;
  15. }LTNode;
  16.  
  17.  
  18. LTNode* ListInit();  // 初始化
  19. void ListPrint(LTNode* phead);  // 打印
  20. void ListPushBack(LTNode* phead, LTDataType x); // 尾插
  21. void ListPushFront(LTNode* phead, LTDataType x); // 头插
  22. void ListPopBack(LTNode* phead);  // 尾删
  23. void ListPopFront(LTNode* phead); // 头删
  24. bool ListEmpty(LTNode* phead); // 判断链表是否为空
  25. LTNode* ListFind(LTNode* phead, LTDataType x); // 查找
  26. void ListInsert(LTNode* pos, LTDataType x); // 在pos位置之前插入
  27. void ListErase(LTNode* pos); // 删除pos位置的节点
  28. int ListSize(LTNode* phead);  // 统计链表有效节点的个数
  29. void ListDestory(LTNode* phead);  // 销毁链表

DList.c :  功能实现

  1. #include "DList.h"
  2.  
  3. LTNode* CreateListNode(LTDataType x)
  4. {
  5. 	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  6. 	if (node == NULL)
  7. 	{
  8. 		perror("CreateListNode:: malloc");
  9. 		exit(-1);
  10. 	}
  11.  
  12. 	node->data = x;
  13. 	node->next = NULL;
  14. 	node->prev = NULL;
  15. 	return node;
  16. }
  17.  
  18. // 初始化链表
  19. LTNode* ListInit() 
  20. {
  21. 	LTNode* phead = CreateListNode(-1);
  22. 	phead->next = phead;
  23. 	phead->prev = phead;
  24. 	return phead;
  25. }
  26.  
  27. // 打印
  28. void ListPrint(LTNode* phead)
  29. {	
  30. 	assert(phead);
  31. 	LTNode* cur = phead->next;
  32. 	while (cur != phead)
  33. 	{
  34. 		printf("%d ", cur->data);
  35. 		cur = cur->next;
  36. 	}
  37. 	printf("\n");
  38. }
  39.  
  40. // 尾插
  41. void ListPushBack(LTNode* phead, LTDataType x)
  42. {
  43. 	assert(phead);
  44. 	/*LTNode* newnode = CreateListNode(x);
  45. 	LTNode* tail = phead->prev;
  46. 	tail->next = newnode;
  47. 	newnode->prev = tail;
  48. 	phead->prev = newnode;
  49. 	newnode->next = phead;*/
  50.  
  51. 	ListInsert(phead, x);
  52. }
  53.  
  54. // 头插
  55. void ListPushFront(LTNode* phead, LTDataType x)
  56. {
  57. 	assert(phead);
  58. 	/*LTNode* newnode = CreateListNode(x);
  59. 	phead->next->prev = newnode;
  60. 	newnode->next = phead->next;
  61. 	newnode->prev = phead;
  62. 	phead->next = newnode;*/
  63.  
  64. 	ListInsert(phead->next, x);
  65. }
  66.  
  67. // 判断链表是否为空
  68. bool ListEmpty(LTNode* phead)
  69. {
  70. 	assert(phead);
  71.  
  72. 	return phead->next == phead;
  73. }
  74.  
  75. // 尾删
  76. void ListPopBack(LTNode* phead)
  77. {
  78. 	assert(phead);
  79. 	assert(phead->prev != phead);
  80. 	//LTNode* newtail = phead->prev->prev;
  81. 	//LTNode* tail = phead->prev;
  82.  
  83. 	//free(tail);
  84.  
  85. 	//phead->prev = newtail;
  86. 	//newtail->next = phead;
  87. 	ListErase(phead->prev);
  88.  
  89. }
  90.  
  91. // 头删
  92. void ListPopFront(LTNode* phead)
  93. {
  94. 	assert(phead);
  95. 	assert(phead->prev != phead);
  96.  
  97. 	/*LTNode* next = phead->next->next;
  98. 	phead->next = next;
  99. 	next->prev = phead;*/
  100. 	ListErase(phead->next);
  101. }
  102.  
  103. // 查找
  104. LTNode* ListFind(LTNode* phead, LTDataType x)
  105. {
  106. 	assert(phead);
  107. 	LTNode* cur = phead->next;
  108. 	while (cur != phead)
  109. 	{
  110. 		if (cur->data == x)
  111. 			return cur;
  112. 		
  113. 		cur = cur->next;
  114. 	}
  115. 	return NULL;
  116. }
  117.  
  118. // 在pos位置之前插入
  119. void ListInsert(LTNode* pos, LTDataType x)
  120. {
  121. 	LTNode* newnode = CreateListNode(x);
  122. 	LTNode* prev = pos->prev;
  123. 	prev->next = newnode;
  124. 	newnode->prev = prev;
  125.  
  126. 	newnode->next = pos;
  127. 	pos->prev = newnode;
  128. }
  129.  
  130.  
  131. // 删除pos位置的节点
  132. void ListErase(LTNode* pos)
  133. {
  134. 	LTNode* prev = pos->prev;
  135. 	LTNode* next = pos->next;
  136.  
  137. 	prev->next = next;
  138. 	next->prev = prev;
  139.  
  140. 	free(pos);
  141. }
  142.  
  143. // 统计链表有效节点的个数
  144. int ListSize(LTNode* phead)
  145. {
  146. 	assert(phead);
  147. 	LTNode* cur = phead->next;
  148. 	int size = 0;
  149. 	while (cur != phead)
  150. 	{
  151. 		++size;
  152. 		cur = cur->next;
  153. 	}
  154. 	return size;
  155. }
  156.  
  157. // 销毁链表
  158. void ListDestory(LTNode* phead)
  159. {
  160. 	assert(phead);
  161. 	LTNode* cur = phead->next;
  162. 	while (cur != phead)
  163. 	{
  164. 		LTNode* next = cur->next;
  165. 		ListErase(cur);
  166. 		cur = next;
  167. 	}
  168. 	free(phead);
  169. }

New.c : 功能测试

  1. #include "DList.h"
  2. void Test1()
  3. {
  4. 	LTNode* plist = ListInit();
  5. 	ListPushBack(plist, 1);
  6. 	ListPushBack(plist, 2);
  7. 	ListPushBack(plist, 3);
  8. 	ListPushBack(plist, 4);
  9. 	ListPrint(plist);
  10. 	ListPushBack(plist, 5);
  11. 	ListPrint(plist);
  12. }
  13.  
  14. void Test2()
  15. {
  16. 	LTNode* plist = ListInit();
  17. 	ListPushBack(plist, 1);
  18. 	ListPushBack(plist, 2);
  19. 	ListPushBack(plist, 3);
  20. 	ListPushBack(plist, 4);
  21. 	ListPrint(plist);
  22. 	ListPushFront(plist, 0);
  23. 	ListPushFront(plist, -1);
  24. 	ListPushFront(plist, -2);
  25. 	ListPushFront(plist, -3);
  26. 	ListPushFront(plist, -4);
  27. 	ListPrint(plist);
  28. }
  29.  
  30. void Test3()
  31. {
  32. 	LTNode* plist = ListInit();
  33. 	ListPushBack(plist, 1);
  34. 	ListPushBack(plist, 2);
  35. 	ListPushBack(plist, 3);
  36. 	ListPushBack(plist, 4);
  37. 	ListPrint(plist);	
  38. 	ListPushFront(plist, 0);
  39. 	ListPushFront(plist, -1);
  40. 	ListPushFront(plist, -2);
  41. 	ListPushFront(plist, -3);
  42. 	ListPushFront(plist, -4);
  43. 	ListPrint(plist);
  44. 	ListPopBack(plist);
  45. 	ListPopBack(plist);
  46. 	ListPopBack(plist);
  47. 	ListPopBack(plist);
  48. 	ListPrint(plist);
  49.  
  50. }
  51.  
  52. void Test4()
  53. {
  54. 	LTNode* plist = ListInit();
  55. 	ListPushBack(plist, 1);
  56. 	ListPushBack(plist, 2);
  57. 	ListPushBack(plist, 3);
  58. 	ListPushBack(plist, 4);
  59. 	ListPrint(plist);
  60. 	ListPushBack(plist, 3);
  61. 	ListPushBack(plist, 2);
  62. 	ListPushBack(plist, 1);
  63. 	ListPrint(plist);
  64. 	ListPopFront(plist);
  65. 	ListPopFront(plist);
  66. 	ListPopFront(plist);
  67. 	ListPrint(plist);
  68.  
  69. }
  70.  
  71. void Test5()
  72. {
  73. 	LTNode* plist = ListInit();
  74. 	ListPushBack(plist, 1);
  75. 	ListPushBack(plist, 2);
  76. 	ListPushBack(plist, 3);
  77. 	ListPushBack(plist, 4);
  78. 	ListPrint(plist);
  79. 	int x = 0;
  80. 	int y = 0;
  81. 	printf("请输入要插入的位置与要插入的数字（在该节点之前插入):> ");
  82. 	scanf("%d %d", &x, &y);
  83. 	LTNode* pos = ListFind(plist, x);
  84. 	if (pos != NULL)
  85. 	{
  86. 		ListInsert(pos, y);
  87. 	}
  88. 	else
  89. 	{
  90. 		printf("输入不合法\n");
  91. 	}
  92. 	ListPrint(plist);
  93.  
  94. }
  95.  
  96. void Test6()
  97. {
  98. 	LTNode* plist = ListInit();
  99. 	ListPushBack(plist, 1);
  100. 	ListPushBack(plist, 2);
  101. 	ListPushBack(plist, 3);
  102. 	ListPushBack(plist, 4);
  103. 	ListPrint(plist);
  104. 	int x = 0;
  105. 	printf("请输入要插入的位置:> ");
  106. 	scanf("%d", &x);
  107. 	LTNode* pos = ListFind(plist, x);
  108. 	if (pos != NULL)
  109. 	{
  110. 		ListErase(pos);
  111. 	}
  112. 	else
  113. 	{
  114. 		printf("输入不合法\n");
  115. 	}
  116. 	ListPrint(plist);
  117. }
  118.  
  119. void Test7()
  120. {
  121. 	LTNode* plist = ListInit();
  122. 	ListPushFront(plist, 5);
  123. 	ListPushFront(plist, 4);
  124. 	ListPushFront(plist, 3);
  125. 	ListPushFront(plist, 2);
  126. 	ListPushFront(plist, 1);
  127. 	ListPrint(plist);
  128. 	ListPushBack(plist, 4);
  129. 	ListPushBack(plist, 3);
  130. 	ListPushBack(plist, 2);
  131. 	ListPushBack(plist, 1);
  132. 	ListPrint(plist);
  133. 	ListPopBack(plist);
  134. 	ListPrint(plist);
  135. 	ListPopFront(plist);
  136. 	ListPrint(plist);
  137.  
  138. }
  139.  
  140. int main()
  141. {	
  142. 	//Test1();
  143. 	//Test2();
  144. 	//Test3();
  145. 	//Test4();
  146. 	//Test5();
  147. 	//Test6();
  148. 	Test7();
  149. 	return 0;
  150. }

运行结果

5. 栈

5.1 栈的定义

什么是栈？（What）

栈：只允许在固定的一端进行插入删除元素操作的线性结构  （Last  In  Frist  Out）

栈顶：进行数据插入删除操作的一端

常见栈：

  • 数组栈  （更优）
  • 链表栈

5.2 栈的实现

使用支持动态增长循序表实现的栈

代码实现

Stack.h : 功能与类型的声明

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #include<stdbool.h>
  6.  
  7. #define __DEBUG__ 0
  8.  
  9. // 静态栈的定义
  10. #if __DEBUG__
  11. typedef int STDataType;
  12. #define N 10
  13. struct Stack
  14. {
  15. 	STDataType a[N];
  16. 	int top; // 栈顶
  17. };
  18. #endif
  19.  
  20. // 支持动态增长的栈
  21. typedef int STDataType;
  22. typedef struct Stack
  23. {
  24. 	STDataType* a;
  25. 	int top;  // 栈顶
  26. 	int capacity;  // 容量
  27. }Stack;
  28.  
  29. void StackInit(Stack* ps);  // 初始化栈
  30. void StackPush(Stack* ps, STDataType x);  // 入栈
  31. void StackPop(Stack* ps);   // 出栈
  32. STDataType StackTop(Stack* ps);  // 取栈顶的元素
  33. int StackSize(Stack* ps);  // 获取栈中有效元素的个数
  34. bool StackEmpty(Stack* ps);  // 检测栈是否为空
  35. void StackDestory(Stack* ps); // 销毁栈

Stack.c : 功能实现

  1. #include "Stack.h"
  2.  
  3. // 初始化栈
  4. void StackInit(Stack* ps)
  5. {
  6. 	assert(ps);
  7. 	ps->a = NULL;
  8. 	ps->capacity = ps->top = 0; // 栈顶的位置无数据
  9. }
  10.  
  11. // 检测栈是否为空
  12. bool StackEmpty(Stack* ps)
  13. {
  14. 	assert(ps);
  15. 	return ps->top == 0;
  16. }
  17.  
  18. // 入栈
  19. void StackPush(Stack* ps,STDataType x)
  20. {
  21. 	assert(ps);
  22. 	// 检查是否需要扩容
  23. 	if (ps->top == ps->capacity)
  24. 	{
  25. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
  26. 		STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
  27. 		if (new == NULL)
  28. 		{
  29. 			perror("StackPush::realloc\n");
  30. 			exit(-1);
  31. 		}
  32. 		ps->a = new;
  33. 		ps->capacity = newCapacity;
  34. 	}
  35. 	ps->a[ps->top] = x;
  36. 	ps->top++;
  37. }
  38.  
  39. // 出栈
  40. void StackPop(Stack* ps)
  41. {
  42. 	assert(ps);
  43. 	assert(!StackEmpty(ps));
  44. 	ps->top--;
  45. }
  46.  
  47. // 取栈顶的元素
  48. STDataType StackTop(Stack* ps)
  49. {
  50. 	assert(ps);
  51. 	assert(!StackEmpty(ps));
  52.  
  53. 	return ps->a[ps->top - 1];
  54. }
  55.  
  56. // 获取栈中有效元素的个数
  57. int StackSize(Stack* ps)
  58. {
  59. 	assert(ps);
  60.  
  61. 	return ps->top;
  62. }
  63.  
  64. // 销毁栈
  65. void StackDestory(Stack* ps)
  66. {
  67. 	assert(ps);
  68. 	free(ps->a);
  69. 	ps->top = ps->capacity = 0;
  70. }

New.c : 功能测试

  1. #include "Stack.h"
  2. void Test1()
  3. {
  4. 	Stack s;
  5. 	Stack* ps = &s;
  6. 	StackInit(ps);
  7. 	StackPush(ps, 1);
  8. 	StackPush(ps, 2);
  9. 	StackPush(ps, 3);
  10. 	StackPush(ps, 4);
  11. 	StackPush(ps, 5);
  12. 	int size = 0;
  13. 	size = StackSize(ps);
  14. 	printf("%d:\n", size);
  15. 	while (!StackEmpty(ps))
  16. 	{
  17. 		int ret = StackTop(ps);
  18. 		printf("%d ", ret);
  19. 		StackPop(ps);
  20. 	}
  21. 	printf("\n");
  22. 	StackDestory(ps);
  23. }
  24.  
  25. int main()
  26. {
  27. 	Test1();
  28. 	return 0;
  29. }

运行结果

6. 队列

6.1 队列的定义

什么是队列？（What）

队列：只允许在一端插入数据，而在另一端删除数据的线性结构  （Frist  In  Frist  Out）

队头：删除数据的一端

队尾：插入数据的一端

常见队列：

  • 数组队列 
  • 链表队列  （更优）

6.2 队列的实现

使用单链表实现的队列

代码实现

Queue.h : 功能与类型的声明

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<stdbool.h>
  5. #include<assert.h>
  6.  
  7. typedef int QDataType;
  8.  
  9. // 使用单链表实现队列 
  10. typedef struct QueueNode
  11. {
  12. 	struct QueueNode* next;
  13. 	QDataType data;
  14. }QNode;
  15.  
  16. typedef struct Queue
  17. {
  18. 	QNode* head; // 队头
  19. 	QNode* tail; // 队尾
  20. }Queue;
  21.  
  22. void QueueInit(Queue* pq);  // 初始化
  23. void QueueDestory(Queue* pq); // 销毁队列
  24. void QueuePush(Queue* pq, QDataType x);  // 入队列
  25. void QueuePop(Queue* pq);  // 出队列
  26. QDataType QueueFront(Queue* pq);  // 取队头的元素
  27. QDataType QueueBack(Queue* pq);  // 取队尾的元素
  28. bool QueueEmpty(Queue* pq);  // 判断队列是否为空
  29. int QueueSize(Queue* pq);  // 计算队列中的有效元素

Queue.c : 功能实现

  1. #include "Queue.h"
  2.  
  3. // 初始化
  4. void QueueInit(Queue* pq)
  5. {
  6. 	assert(pq);
  7. 	pq->head = pq->tail = NULL;
  8. }
  9.  
  10. // 入队列
  11. void QueuePush(Queue* pq, QDataType x)
  12. {
  13. 	assert(pq);
  14. 	QNode* newnode = (QNode*)malloc(sizeof(QNode));
  15. 	if (newnode == NULL)
  16. 	{
  17. 		perror("QueuePush::malloc\n");
  18. 		exit(-1);
  19. 	}
  20. 	newnode->data = x;
  21. 	newnode->next = NULL;
  22.  
  23. 	if (pq->tail == NULL)
  24. 	{
  25. 		pq->head = pq->tail = newnode;
  26. 	}
  27. 	else
  28. 	{
  29. 		pq->tail->next = newnode;
  30. 		pq->tail = newnode;
  31. 	}
  32. }
  33.  
  34. // 出队列
  35. void QueuePop(Queue* pq)
  36. {
  37. 	assert(pq);
  38. 	// 只剩一个节点
  39. 	if (pq->head->next == NULL)
  40. 	{
  41. 		free(pq->head);
  42. 		pq->head = pq->tail = NULL; // 避免tail成为野指针 （指针的指向是不确定的）
  43. 	}
  44. 	else
  45. 	{
  46. 		// 多个节点
  47. 		QNode* next = pq->head->next;
  48. 		free(pq->head);
  49. 		pq->head = next;
  50. 	}
  51. }
  52.  
  53. // 取队头的元素
  54. QDataType QueueFront(Queue* pq)
  55. {
  56. 	assert(pq);
  57. 	assert(!QueueEmpty(pq));
  58.  
  59. 	return pq->head->data;
  60. }
  61.  
  62. // 取队尾的元素
  63. QDataType QueueBack(Queue* pq)
  64. {
  65. 	assert(pq);
  66. 	assert(!QueueEmpty(pq));
  67. 	
  68. 	return pq->tail->data;
  69. }
  70.  
  71. // 判断队列是否为空
  72. bool QueueEmpty(Queue* pq)
  73. {
  74. 	assert(pq);
  75. 	//if (pq->head == NULL)
  76. 	//	return true;
  77.  
  78. 	//return false;
  79. 	return pq->head == NULL;
  80. }
  81.  
  82. // 计算队列中的有效元素
  83. int QueueSize(Queue* pq)
  84. {
  85. 	assert(pq);
  86. 	QNode* cur = pq->head;
  87. 	int size = 0;
  88. 	while (cur)
  89. 	{
  90. 		++size;
  91. 		cur = cur->next;
  92. 	}
  93. 	return size;
  94. }
  95.  
  96. // 销毁队列 - 即将队列都删空
  97. void QueueDestory(Queue* pq)
  98. {
  99. 	assert(pq);
  100. 	QNode* cur = pq->head;
  101. 	while (cur)
  102. 	{
  103. 		QNode* next = cur->next;
  104. 		free(cur);
  105. 		cur = next;
  106. 	}
  107. 	pq->head = pq->tail = NULL;
  108. }

New.c : 功能测试

  1. #include "Queue.h"
  2.  
  3. void Test1()
  4. {
  5. 	Queue q;
  6. 	Queue* pq = &q;
  7. 	QueueInit(pq);
  8. 	QueuePush(pq, 1);
  9. 	QueuePush(pq, 2);
  10. 	QueuePush(pq, 3);
  11. 	QueuePush(pq, 4);
  12. 	QueuePush(pq, 5);
  13. 	int size = 0;
  14. 	size = QueueSize(pq);
  15. 	printf("%d:\n", size);
  16.  
  17. 	while (!QueueEmpty(pq))
  18. 	{
  19. 		int ret = QueueFront(pq);
  20. 		printf("%d ", ret);
  21. 		QueuePop(pq);
  22. 	}
  23. 	printf("\n");
  24. 	QueueDestory(pq);
  25. }
  26.  
  27. int main()
  28. {
  29. 	Test1();
  30. 	return 0;
  31. }

运行结果

 7. 小结

最后，我们来进行总结一下，今天的博客主要介绍了数据结构中的线性结构及它们的实现（C语言），如顺序表、链表、栈、队列；熟练掌握各种数据结构以及它们的实现，我们软件开发者在进阶过程中必须要攀登的一座“大山”！好啦，希望今天的博客能够对你有所帮助，我们山顶见！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/966232
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号