• 数据结构 2 第二章 线性结构 代码实现

    头文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include //malloc函数头文件
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. # include

    一、单链表

    1.单链表

    线性表：1.有限的序列 2.序列中的每一个元素都有唯一的前驱和后继，除了开头和结尾的两个节点。

    顺序表：分配一块连续的内存去存放这些元素，eg、数组

    链表：内存是不连续的，元素会各自被分配一块内存，内存和内存之间用指针进行相连。

    顺序表和链表的区别是内存的连续与否

     data域 | next指针域 ——> data域 | next指针域 ——> data域 | next指针域 ——> NULL

    2.单链表的操作

    1.增加 ：1>头插法 2>尾插法
    1>插入——> data域 | next指针域 ——> data域 | next指针域 ——> data域 | next指针域 ——> NULL
    2>data域 | next指针域 ——> data域 | next指针域 ——> data域 | next指针域 ——> 插入——>NULL
    2.删除：用前一个节点的指针直接指向对应节点的后一个节点的前驱，只操作一个指针。
    为了使操作方便，在操作中添加一个头节点。头节点并不实际存储，只保存链表中的元素个数。

    代码实现

    1.定义一个结构体

    1. typedef struct Node {//定义一个结构体
    2. 	int data;
    3. 	struct Node* next;
    4. }Node;

    2.初始化一个链表 

    1. Node* initList() {//初始化一个链表
    2. 	Node* list = (Node*)malloc(sizeof(Node));
    3. 	list->data = 0;
    4. 	list->next = NULL;
    5. 	return list;
    6. }

     3.头插法

    1. void headInsert(Node* list,int data){//头插法
    2. 	Node* node = (Node*)malloc(sizeof(Node));
    3. 	node->data = data;
    4. 	node->next = list->next;
    5. 	list->next = node;
    6. 	list->data++;//代表当前链表之中插入元素
    7. }

    4.尾插法

    1. void tailInsert(Node* list, int data){//尾插法
    2. 	Node* head = list;
    3. 	Node* node = (Node*)malloc(sizeof(Node));
    4. 	node->data = data;
    5. 	node->next = NULL;
    6. 	list = list->next;
    7. 	while (list->next) {
    8. 		list = list->next;
    9. 	}
    10. 	list->next = node;
    11. 	head->data++;
    12. }

    5.删除操作

    1. void Delete(Node* list, int data){//删除
    2. 	Node* head = list;
    3. 	Node* pre = list;
    4. 	Node* current = list->next;
    5. 	list = list->next;
    6. 	while (current)
    7. 	{
    8. 		if (current->data == data)
    9. 		{
    10. 			pre->next = current->next;
    11. 			free(current);
    12. 			break;
    13. 		}
    14. 		pre = current;
    15. 		current = current->next;
    16. 	}
    17. 	list->data--;
    18. }

     6.遍历打印操作

    1. void printList(Node* list) {//遍历操作
    2. 	list = list->next;
    3. 	while (list)
    4. 	{
    5. 		printf("%d ", list->data);
    6. 		list = list->next;
    7. 	}
    8. 	printf("\n");
    9. }

     7.代码实现

    1. typedef struct Node {//定义一个结构体
    2. 	int data;
    3. 	struct Node* next;
    4. }Node;
    5.  
    6. Node* initList() {//初始化一个链表
    7. 	Node* list = (Node*)malloc(sizeof(Node));
    8. 	list->data = 0;
    9. 	list->next = NULL;
    10. 	return list;
    11. }
    12.  
    13. void headInsert(Node* list,int data){//头插法
    14. 	Node* node = (Node*)malloc(sizeof(Node));
    15. 	node->data = data;
    16. 	node->next = list->next;
    17. 	list->next = node;
    18. 	list->data++;//代表当前链表之中插入元素
    19. }
    20.  
    21. void tailInsert(Node* list, int data){//尾插法
    22. 	Node* head = list;
    23. 	Node* node = (Node*)malloc(sizeof(Node));
    24. 	node->data = data;
    25. 	node->next = NULL;
    26. 	list = list->next;
    27. 	while (list->next) {
    28. 		list = list->next;
    29. 	}
    30. 	list->next = node;
    31. 	head->data++;
    32. }
    33.  
    34. void Delete(Node* list, int data){//删除
    35. 	Node* head = list;
    36. 	Node* pre = list;
    37. 	Node* current = list->next;
    38. 	list = list->next;
    39. 	while (current)
    40. 	{
    41. 		if (current->data == data)
    42. 		{
    43. 			pre->next = current->next;
    44. 			free(current);
    45. 			break;
    46. 		}
    47. 		pre = current;
    48. 		current = current->next;
    49. 	}
    50. 	list->data--;
    51. }
    52.  
    53. void printList(Node* list) {//遍历操作
    54. 	list = list->next;
    55. 	while (list)
    56. 	{
    57. 		printf("%d ", list->data);
    58. 		list = list->next;
    59. 	}
    60. 	printf("\n");
    61. }
    62.  
    63. int main()
    64. {
    65. 	Node* list = initList();
    66. 	headInsert(list, 1);
    67. 	headInsert(list, 2);
    68. 	headInsert(list, 3);
    69. 	headInsert(list, 4);
    70. 	headInsert(list, 5);
    71. 	tailInsert(list, 6);
    72. 	tailInsert(list, 7);
    73. 	tailInsert(list, 8);
    74. 	tailInsert(list, 9);
    75. 	tailInsert(list, 10);
    76. 	printList(list);
    77. 	Delete(list, 5);
    78. 	printList(list);
    79. 	Delete(list, 10);
    80. 	printList(list);
    81. 	Delete(list, 6);
    82. 	printList(list);
    83. 	return 0;
    84. }

    8.结果

    二、单循环链表

    1..单循环链表

    data|next——>data|next——>data|next——>头节点
    1.初始化链表
    2.增加节点（头插法、尾插法）
    3.删除节点
    4.遍历链表

    代码实现

    1.定义一个结构体

    1. typedef struct Node {//定义一个结构体，存放data域和指针域
    2. 	int data;//数据域类型
    3. 	struct Node* next;
    4. }Node;

    2. 初始化链表

    1. Node* initList() {//初始化链表
    2. 	Node* L = (Node*)malloc(sizeof(Node));
    3. 	L->data = 0;
    4. 	L->next = L;
    5. 	return L;
    6. }

    3.头插法

    1. void headInsert(Node* L, int data) {//头插法
    2. 	Node* node = (Node*)malloc(sizeof(Node));
    3. 	node->data = data;
    4. 	node->next = L->next;
    5. 	L->next = node;
    6. }

    4尾插法

    1. void tailInsert(Node* L, int data) {//尾插法
    2. 	Node* n = L;
    3. 	Node* node = (Node*)malloc(sizeof(Node));
    4. 	node->data = data;
    5. 	while (n->next != L) {
    6. 		n = n->next;
    7. 	}
    8. 	node->next = L;
    9. 	n->next = node;
    10. }

    5.删除操作

    1. int Delete(Node* L, int data)//删除
    2. {
    3. 	Node* preNode = L;
    4. 	Node* node = L->next;
    5. 	while (node != L)
    6. 	{
    7. 		if (node->data == data) {
    8. 			preNode->next = node->next;
    9. 			free(node);
    10. 			return TRUE;
    11. 		}
    12. 		preNode = node;
    13. 		node = node->next;
    14. 	}
    15. 	return FALSE;
    16. }

    6.遍历链表打印

    1. void printList(Node* L) {//遍历链表
    2. 	Node* node = L->next;
    3. 	while (node != L) {
    4. 		printf("%d->", node->data);
    5. 		node = node->next;
    6. 	}
    7. 	printf("NULL\n");
    8. }

    7.代码实现

    1. #define TRUE 1
    2. #define FALSE 0
    3.  
    4. typedef struct Node {//定义一个结构体，存放data域和指针域
    5. 	int data;//数据域类型
    6. 	struct Node* next;
    7. }Node;
    8.  
    9. Node* initList() {//初始化链表
    10. 	Node* L = (Node*)malloc(sizeof(Node));
    11. 	L->data = 0;
    12. 	L->next = L;
    13. 	return L;
    14. }
    15.  
    16. void headInsert(Node* L, int data) {//头插法
    17. 	Node* node = (Node*)malloc(sizeof(Node));
    18. 	node->data = data;
    19. 	node->next = L->next;
    20. 	L->next = node;
    21. }
    22.  
    23. void tailInsert(Node* L, int data) {//尾插法
    24. 	Node* n = L;
    25. 	Node* node = (Node*)malloc(sizeof(Node));
    26. 	node->data = data;
    27. 	while (n->next != L) {
    28. 		n = n->next;
    29. 	}
    30. 	node->next = L;
    31. 	n->next = node;
    32. }
    33.  
    34. int Delete(Node* L, int data)//删除
    35. {
    36. 	Node* preNode = L;
    37. 	Node* node = L->next;
    38. 	while (node != L)
    39. 	{
    40. 		if (node->data == data) {
    41. 			preNode->next = node->next;
    42. 			free(node);
    43. 			return TRUE;
    44. 		}
    45. 		preNode = node;
    46. 		node = node->next;
    47. 	}
    48. 	return FALSE;
    49. }
    50.  
    51. void printList(Node* L) {//遍历链表
    52. 	Node* node = L->next;
    53. 	while (node != L) {
    54. 		printf("%d->", node->data);
    55. 		node = node->next;
    56. 	}
    57. 	printf("NULL\n");
    58. }
    59.  
    60. int main()
    61. {
    62. 	Node* L = initList();
    63. 	headInsert(L, 1);
    64. 	headInsert(L, 2);
    65. 	headInsert(L, 3);
    66. 	headInsert(L, 4);
    67. 	headInsert(L, 5);
    68. 	tailInsert(L, 6);
    69. 	tailInsert(L, 7);
    70. 	tailInsert(L, 8);
    71. 	tailInsert(L, 9);
    72. 	tailInsert(L, 10);
    73. 	printList(L);
    74. 	Delete(L, 4);
    75. 	Delete(L, 5);
    76. 	printList(L);
    77. 	return 0;
    78. }

    8.结果

    三、双链表

    1.双链表

    pre指针|data域|next指针<——>pre|data|next<——>pre|data|next
     与单链表相比多一个指针域

    2.双链表的操作：

     1.初始化链表
     2.插入节点（头插法、尾插法）
     3.删除结点
     4.遍历链表

    代码实现

    1.数据结构的定义

    1. typedef struct Node {//数据结构的定义
    2. 	int data;//data域
    3. 	struct Node* pre;//pre指针
    4. 	struct Node* next;//next指针
    5. }Node;

    2. 初始化链表

    1. Node* initList() {//初始化链表
    2. 	Node* L = (Node*)malloc(sizeof(Node));//新建指针变量并开辟空间 返回一个Node*类型指针
    3. 	L->data = 0;//头节点data域初始化为0
    4. 	L->pre = NULL;//头指针为NULL
    5. 	L->next = NULL;//next指针为NULL
    6. 	return

    3. 头插法

    1. void headInsert(Node* L, int data) {//头插法
    2. 	Node* node = (Node*)malloc(sizeof(Node));//新建一个结点并为他开辟空间
    3. 	node->data = data;
    4. 	if (L->data == 0)
    5. 	{
    6. 		node->next = L->next;
    7. 		node->pre = L;
    8. 		L->next = node;
    9. 	}
    10. 	else {
    11. 		node->pre = L;//node指向的pre指向头节点
    12. 		node->next = L->next;
    13. 		L->next->pre = node;
    14. 		L->next = node;
    15. 		L->data++;
    16. 	}
    17. }

    4.尾插法

    1. void tailInsert(Node* L,int data) //尾插法
    2. {
    3. 	Node* node = L;
    4. 	Node* n = (Node*)malloc(sizeof(Node));
    5. 	n->data = data;
    6. 	while (node->next) {
    7. 		node = node->next;
    8. 	}
    9. 	n->next = node->next;
    10. 	node->next = n;
    11. 	n->pre = node;
    12. 	L->data++;
    13. }

     5.删除操作

    1. int Delete(Node* L, int data) //删除
    2. {
    3. 	Node* node = L->next;
    4. 	while (node) 
    5. 	{
    6. 		if (node->data == data)
    7. 		{
    8. 			node->pre->next = node->next;
    9. 			node->next->pre = node->pre;
    10. 			free(node);
    11. 			return TRUE;
    12. 		}
    13. 		node = node->next;
    14. 	}
    15. 	return FALSE;
    16. }

    6.遍历链表打印

    1. void printList(Node* L)//遍历
    2. {
    3. 	Node* node = L->next;
    4. 	while (node) {
    5. 		printf("%d -> ", node->data);
    6. 		node = node->next;
    7. 	}
    8. 	printf("NULL\n");
    9. }

     7.代码实现

    1. #define TRUE 1
    2. #define FALSE 0
    3.  
    4. typedef struct Node {//数据结构的定义
    5. 	int data;//data域
    6. 	struct Node* pre;//pre指针
    7. 	struct Node* next;//next指针
    8. }Node;
    9.  
    10. Node* initList() {//初始化链表
    11. 	Node* L = (Node*)malloc(sizeof(Node));//新建指针变量并开辟空间 返回一个Node*类型指针
    12. 	L->data = 0;//头节点data域初始化为0
    13. 	L->pre = NULL;//头指针为NULL
    14. 	L->next = NULL;//next指针为NULL
    15. 	return L;//返回L
    16. }
    17.  
    18. void headInsert(Node* L, int data) {//头插法
    19. 	Node* node = (Node*)malloc(sizeof(Node));//新建一个结点并为他开辟空间
    20. 	node->data = data;
    21. 	if (L->data == 0)
    22. 	{
    23. 		node->next = L->next;
    24. 		node->pre = L;
    25. 		L->next = node;
    26. 	}
    27. 	else {
    28. 		node->pre = L;//node指向的pre指向头节点
    29. 		node->next = L->next;
    30. 		L->next->pre = node;
    31. 		L->next = node;
    32. 		L->data++;
    33. 	}
    34. }
    35.  
    36. void tailInsert(Node* L,int data) //尾插法
    37. {
    38. 	Node* node = L;
    39. 	Node* n = (Node*)malloc(sizeof(Node));
    40. 	n->data = data;
    41. 	while (node->next) {
    42. 		node = node->next;
    43. 	}
    44. 	n->next = node->next;
    45. 	node->next = n;
    46. 	n->pre = node;
    47. 	L->data++;
    48. }
    49.  
    50. int Delete(Node* L, int data) //删除
    51. {
    52. 	Node* node = L->next;
    53. 	while (node) 
    54. 	{
    55. 		if (node->data == data)
    56. 		{
    57. 			node->pre->next = node->next;
    58. 			node->next->pre = node->pre;
    59. 			free(node);
    60. 			return TRUE;
    61. 		}
    62. 		node = node->next;
    63. 	}
    64. 	return FALSE;
    65. }
    66.  
    67. void printList(Node* L)//遍历
    68. {
    69. 	Node* node = L->next;
    70. 	while (node) {
    71. 		printf("%d -> ", node->data);
    72. 		node = node->next;
    73. 	}
    74. 	printf("NULL\n");
    75. }
    76.  
    77. int main()
    78. {
    79. 	Node* L = initList();
    80. 	headInsert(L, 1);
    81. 	headInsert(L, 2);
    82. 	headInsert(L, 3);
    83. 	headInsert(L, 4);
    84. 	printList(L);
    85. 	//4 -> 3 -> 2 -> 1 -> NULL
    86. 	tailInsert(L, 5);
    87. 	tailInsert(L, 6);
    88. 	tailInsert(L, 7);
    89. 	tailInsert(L, 8);
    90. 	printList(L);
    91. 	//4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8 -> NULL
    92. 	Delete(L, 2);
    93. 	Delete(L, 4);
    94. 	printList(L);
    95. 	//1 -> 5 -> 6 -> 7 -> 8->NULL
    96. }

    8.结果

     

    四、双循环链表

    1.双循环链表

    pre前指针|data域|next后指针<——>pre|data|next<——>pre|data|next
    最后一个节点的next指针和头节点的pre指针相互指向对方，其他节点与双链表相同。
    功能：
     1.初始化链表
     2.插入节点（头插法、尾插法）
     3.删除结点
     4.遍历链表

    代码实现

    1.定义一个结构体链表数据节点

    1. typedef struct Node//定义一个结构体类型
    2. {
    3. 	int data;
    4. 	struct Node* pre;
    5. 	struct Node* next;
    6. }Node;

    2.初始化链表 

    1. Node* initList()//初始化链表
    2. {
    3. 	Node* L = (Node*)malloc(sizeof(Node));
    4. 	L->data = 0;
    5. 	L->next = L;
    6. 	L->pre = L;
    7. 	return L;
    8. }

    3.头插法

    1. void headInsert(Node* L,int data)//头插法
    2. {
    3. 	Node* node = (Node*)malloc(sizeof(Node));
    4. 	node->data = data;
    5. 	if (L->data == 0)
    6. 	{//链表为空
    7. 		node->pre = L;
    8. 		node->next = L->next;
    9. 		L->next = node;
    10. 		L->pre = node;
    11. 		L->data++;
    12. 	}
    13. 	else {
    14. 		//链表不为空
    15. 		node->next = L->next;
    16. 		node->pre = L;
    17. 		L->next->pre = node;
    18. 		L->next = node;
    19. 		L->data++;
    20. 	}
    21. }

    4.尾插法 

    1. void tailInsert(Node* L,int data)//尾插法
    2. {
    3. 	Node* node = L;
    4. 	while (node->next != L)
    5. 	{
    6. 		node = node->next;
    7. 	}
    8. 	Node* n = (Node*)malloc(sizeof(Node));
    9. 	n->data = data;
    10. 	n->pre = node;
    11. 	n->next = L;
    12. 	L->pre = n;
    13. 	node->next = n;
    14. 	L->data++;
    15. }

    5.删除操作

    1. int Delete(Node* L, int data)//删除
    2. {
    3. 	Node* node = L->next;
    4. 	while (node != L)
    5. 	{
    6. 		if (node->data == data)
    7. 		{
    8. 			node->pre->next = node->next;
    9. 			node->next->pre = node->pre;
    10. 			free(node);
    11. 			L->data--;
    12. 			return 1;
    13. 		}
    14. 		node = node->next;
    15. 	}
    16. 	return 0;
    17. }

     6.遍历链表打印

    1. void printList(Node* L)//遍历
    2. {
    3. 	Node* node = L->next;
    4. 	while (node != L) {
    5. 		printf("%d -> ", node->data);
    6. 		node = node->next;
    7. 	}
    8. 	printf("NULL\n");
    9. }

    7.代码实现

    1. typedef struct Node//定义一个结构体类型
    2. {
    3. 	int data;
    4. 	struct Node* pre;
    5. 	struct Node* next;
    6. }Node;
    7.  
    8. Node* initList()//初始化链表
    9. {
    10. 	Node* L = (Node*)malloc(sizeof(Node));
    11. 	L->data = 0;
    12. 	L->next = L;
    13. 	L->pre = L;
    14. 	return L;
    15. }
    16.  
    17. void headInsert(Node* L,int data)//头插法
    18. {
    19. 	Node* node = (Node*)malloc(sizeof(Node));
    20. 	node->data = data;
    21. 	if (L->data == 0)
    22. 	{//链表为空
    23. 		node->pre = L;
    24. 		node->next = L->next;
    25. 		L->next = node;
    26. 		L->pre = node;
    27. 		L->data++;
    28. 	}
    29. 	else {
    30. 		//链表不为空
    31. 		node->next = L->next;
    32. 		node->pre = L;
    33. 		L->next->pre = node;
    34. 		L->next = node;
    35. 		L->data++;
    36. 	}
    37. }
    38.  
    39. void tailInsert(Node* L,int data)//尾插法
    40. {
    41. 	Node* node = L;
    42. 	while (node->next != L)
    43. 	{
    44. 		node = node->next;
    45. 	}
    46. 	Node* n = (Node*)malloc(sizeof(Node));
    47. 	n->data = data;
    48. 	n->pre = node;
    49. 	n->next = L;
    50. 	L->pre = n;
    51. 	node->next = n;
    52. 	L->data++;
    53. }
    54.  
    55. int Delete(Node* L, int data)//删除
    56. {
    57. 	Node* node = L->next;
    58. 	while (node != L)
    59. 	{
    60. 		if (node->data == data)
    61. 		{
    62. 			node->pre->next = node->next;
    63. 			node->next->pre = node->pre;
    64. 			free(node);
    65. 			L->data--;
    66. 			return 1;
    67. 		}
    68. 		node = node->next;
    69. 	}
    70. 	return 0;
    71. }
    72.  
    73. void printList(Node* L)//遍历
    74. {
    75. 	Node* node = L->next;
    76. 	while (node != L) {
    77. 		printf("%d -> ", node->data);
    78. 		node = node->next;
    79. 	}
    80. 	printf("NULL\n");
    81. }
    82.  
    83. int main()
    84. {
    85. 	Node* L = initList();
    86. 	headInsert(L, 1);
    87. 	headInsert(L, 2);
    88. 	headInsert(L, 3);
    89. 	headInsert(L, 4);
    90. 	printList(L);
    91. 	//4 -> 3 -> 2 -> 1 -> NULL
    92. 	tailInsert(L, 5);
    93. 	tailInsert(L, 6);
    94. 	tailInsert(L, 7);
    95. 	tailInsert(L, 8);
    96. 	printList(L);
    97. 	//4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7 -> 8 -> NULL
    98. 	Delete(L, 2);
    99. 	Delete(L, 4);
    100. 	printList(L);
    101. 	//3 -> 1 -> 5 -> 6 -> 7 -> 8 -> NULL
    102. }

     8.运行结果

    五、栈

    1.栈

    存放：1->2->3 取出:3->2->1   先进后出
    应用场景：1.表达式的值 2.解决一些递归问题 3.计算进制转换
    栈是一种特殊的线性表，它只能在一端进行存取操作，所以存取的元素有先进后出的特点。
    栈的总体特点：先进后出

    2.实现的功能：

     初始化栈
     出栈
     入栈
     判断栈空

    代码实现

    1.结构体定义数据结点

    1. typedef struct Node //结构体创建节点
    2. {
    3. 	int data;//data域
    4. 	struct Node* next;//next指针
    5. }Node;

    2.初始化栈

    1. Node* initStack()//初始化栈
    2. {
    3. 	Node* S = (Node*)malloc(sizeof(Node));//新建一个节点
    4. 	S->data = 0;
    5. 	S->next = NULL;
    6. 	return S;//返回S
    7. }

    3.出栈 

    1. int isEmpty(Node* S)//出栈功能前的判断栈空功能
    2. {
    3. 	if (S->data == 0 || S->next == NULL)//栈空
    4. 	{
    5. 		return 1;
    6. 	}
    7. 	else {
    8. 		return 0;
    9. 	}
    10. }
    11.  
    12. int getTop(Node* S)//出栈 传入头指针
    13. {
    14. 	if (isEmpty(S))
    15. 	{
    16. 		return -1;
    17. 	}
    18. 	else
    19. 	{
    20. 		return S->next->data;//不为空的话 S指向第一个节点的data域
    21. 	}
    22. }

    4. 

     

    六、队

    1.队

    一种先进先出的特殊线性表，只允许在一端进行存取，在头出，在尾进

    2.实现的功能：

    1.初始化队
    2.出队
    3.入队 （尾插法）

    代码实现

    1.结构体定义数据节点

    1. typedef struct Node //定义数据节点结构体
    2. {
    3. 	int data;//数据域data
    4. 	struct Node* next;//next指针
    5. }Node;

    2.初始化队列

    1. Node* initQueue() //初始化队列
    2. {
    3. 	Node* Q = (Node*)malloc(sizeof(Node));//新建指针变量
    4. 	Q->data = 0;
    5. 	Q->next = NULL;
    6. 	return Q;
    7. }

    3. 入队操作 尾插法

    1. void enQueue(Node* Q, int data)//入队操作 尾插法
    2. {
    3. 	Node* q = Q;//传入头指针
    4. 	Node* node = (Node*)malloc(sizeof(Node));
    5. 	node->data = data;
    6. 	for (int i = 0; i < Q->data; i++)//循环遍历队列找到最后一个节点
    7. 	{
    8. 		q = q->next;
    9. 	}
    10. 	node->next = q->next;
    11. 	q->next = node;
    12. 	Q->data++;//!!!!
    13. }

     4.出队操作，删除队列中第一个结点

    1. int isEmpty(Node* Q)//判空
    2. {
    3. 	if (Q->data == 0 || Q->next == NULL)
    4. 	{
    5. 		return 1;
    6. 	}
    7. 	else
    8. 	{
    9. 		return 0;
    10. 	}
    11. }
    12.  
    13. int deQueue(Node* Q) //出队操作 删除队列中的第一个节点
    14. {
    15. 	if (isEmpty(Q))//判空操作
    16. 	{
    17. 		return -1;
    18. 	}
    19. 	else
    20. 	{
    21. 		Node* node = Q->next;
    22. 		int data = node->data;
    23. 		Q->next = node->next;
    24. 		free(node);
    25. 		return data;
    26. 	}
    27. }

    5.遍历队列打印

    1. void printQueue(Node* Q)//遍历队列打印
    2. {
    3. 	Node* node = Q->next;//传入第一个节点
    4. 	while (node)
    5. 	{
    6. 		printf("%d -> ", node->data);
    7. 		node = node->next;
    8. 	}
    9. 	printf("NULL\n");
    10. }

    6.代码实现

    1. typedef struct Node //定义数据节点结构体
    2. {
    3. 	int data;//数据域data
    4. 	struct Node* next;//next指针
    5. }Node;
    6.  
    7. Node* initQueue() //初始化队列
    8. {
    9. 	Node* Q = (Node*)malloc(sizeof(Node));//新建指针变量
    10. 	Q->data = 0;
    11. 	Q->next = NULL;
    12. 	return Q;
    13. }
    14.  
    15. void enQueue(Node* Q, int data)//入队操作 尾插法
    16. {
    17. 	Node* q = Q;//传入头指针
    18. 	Node* node = (Node*)malloc(sizeof(Node));
    19. 	node->data = data;
    20. 	for (int i = 0; i < Q->data; i++)//循环遍历队列找到最后一个节点
    21. 	{
    22. 		q = q->next;
    23. 	}
    24. 	node->next = q->next;
    25. 	q->next = node;
    26. 	Q->data++;//!!!!
    27. }
    28.  
    29. int isEmpty(Node* Q)//判空
    30. {
    31. 	if (Q->data == 0 || Q->next == NULL)
    32. 	{
    33. 		return 1;
    34. 	}
    35. 	else
    36. 	{
    37. 		return 0;
    38. 	}
    39. }
    40.  
    41. int deQueue(Node* Q) //出队操作 删除队列中的第一个节点
    42. {
    43. 	if (isEmpty(Q))//判空操作
    44. 	{
    45. 		return -1;
    46. 	}
    47. 	else
    48. 	{
    49. 		Node* node = Q->next;
    50. 		int data = node->data;
    51. 		Q->next = node->next;
    52. 		free(node);
    53. 		return data;
    54. 	}
    55. }
    56.  
    57. void printQueue(Node* Q)//遍历队列打印
    58. {
    59. 	Node* node = Q->next;//传入第一个节点
    60. 	while (node)
    61. 	{
    62. 		printf("%d -> ", node->data);
    63. 		node = node->next;
    64. 	}
    65. 	printf("NULL\n");
    66. }
    67.  
    68. int main()
    69. {
    70. 	Node* Q = initQueue();
    71. 	enQueue(Q, 1);
    72. 	enQueue(Q, 2);
    73. 	enQueue(Q, 3);
    74. 	enQueue(Q, 4);
    75. 	printQueue(Q);//1 -> 2 -> 3 -> 4 -> NULL
    76. 	int data = deQueue(Q);
    77. 	printf("data=%d\n", data);//data=1
    78. 	printQueue(Q);//2 -> 3 -> 4 -> NULL
    79. 	data = deQueue(Q);
    80. 	printQueue(Q);//3 -> 4 -> NULL
    81.  
    82. 	data = deQueue(Q);
    83. 	printQueue(Q);//4 -> NULL
    84.  
    85. 	data = deQueue(Q);
    86. 	printf("data=%d\n", data);//data=4
    87. 	printQueue(Q);//NULL
    88. 	return 0;
    89. }

    7.运行结果

     

    七、循环队列

    队列组成一周 需要两个指针指向队列的队首与队尾 当插入一个元素后，队尾指针后移一项，

    如何判断队列是空/满：
     1.在实际操作中，牺牲掉队列一个空间来判断队列是满/空
     2.判断逻辑如下：
       1>队空的话，头指针等于尾指针：front==rear
         2>队满的话：rear+1%MAXSIZE==front;

    实现的功能：

      1.初始化队列
      2.入队
      3.出队
      4.遍历循环队列

     代码实现

    1.定义队列结构体

    1. #define MAXSIZE 5
    2.  
    3. typedef struct Queue//定义队列结构体
    4. {
    5. 	int front;//front指针
    6. 	int rear;//rear指针
    7. 	int data[MAXSIZE];//data域
    8. }Queue;

    2.初始化队列 

    1. Queue* initQueue()//初始化队列
    2. {
    3. 	Queue* Q = (Queue*)malloc(sizeof(Queue));
    4. 	Q->front = Q->rear = 0;
    5. 	return Q;
    6. }

    3.判满/空操作

    1. int isFull(Queue* Q)//判满操作
    2. {
    3. 	if ((Q->rear + 1) % MAXSIZE == Q->front)
    4. 	{
    5. 		return 1;
    6. 	}
    7. 	else {
    8. 		return 0;
    9. 	}
    10. }
    11.  
    12. int isEmpty(Queue* Q)//判空操作
    13. {
    14. 	if (Q->front == Q->rear)
    15. 	{
    16. 		return 1;
    17. 	}
    18. 	else {
    19. 		return 0;
    20. 	}
    21. }

     4.入队操作

    1. int enQueue(Queue* Q, int data)//插入函数 入队操作
    2. {
    3. 	if (isFull(Q))
    4. 	{
    5. 		return 0;
    6. 	}
    7. 	else {
    8. 		Q->data[Q->rear] = data;
    9. 		Q->rear = (Q->rear + 1) % MAXSIZE;
    10. 		return 1;
    11. 	}
    12. }

     5。出队操作

    1. int deQueue(Queue* Q)//出队操作
    2. {
    3. 	if (isEmpty(Q))
    4. 	{
    5. 		return -1;
    6. 	}
    7. 	else {
    8. 		int data = Q->data[Q->front];
    9. 		Q->front = (Q->front + 1) % MAXSIZE;
    10. 		return data;
    11. 	}
    12. }

    6，遍历队列打印

    1. void printQueue(Queue* Q)//遍历队列打印
    2. {
    3. 	//要知道队列当前有多少个元素
    4. 	int length = (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
    5. 	int index = Q->front;
    6. 	for (int i = 0; i < length; i++)
    7. 	{
    8. 		printf("%d -> ", Q->data[index]);
    9. 		index = (index + 1) % MAXSIZE;
    10. 	}
    11. 	printf("NULL\n");
    12. }

    7.代码实现

    1. #define MAXSIZE 5
    2.  
    3. typedef struct Queue//定义队列结构体
    4. {
    5. 	int front;//front指针
    6. 	int rear;//rear指针
    7. 	int data[MAXSIZE];//data域
    8. }Queue;
    9.  
    10. Queue* initQueue()//初始化队列
    11. {
    12. 	Queue* Q = (Queue*)malloc(sizeof(Queue));
    13. 	Q->front = Q->rear = 0;
    14. 	return Q;
    15. }
    16.  
    17. int isFull(Queue* Q)//判满操作
    18. {
    19. 	if ((Q->rear + 1) % MAXSIZE == Q->front)
    20. 	{
    21. 		return 1;
    22. 	}
    23. 	else {
    24. 		return 0;
    25. 	}
    26. }
    27.  
    28. int isEmpty(Queue* Q)//判空操作
    29. {
    30. 	if (Q->front == Q->rear)
    31. 	{
    32. 		return 1;
    33. 	}
    34. 	else {
    35. 		return 0;
    36. 	}
    37. }
    38.  
    39. int enQueue(Queue* Q, int data)//插入函数 入队操作
    40. {
    41. 	if (isFull(Q))
    42. 	{
    43. 		return 0;
    44. 	}
    45. 	else {
    46. 		Q->data[Q->rear] = data;
    47. 		Q->rear = (Q->rear + 1) % MAXSIZE;
    48. 		return 1;
    49. 	}
    50. }
    51.  
    52. int deQueue(Queue* Q)//出队操作
    53. {
    54. 	if (isEmpty(Q))
    55. 	{
    56. 		return -1;
    57. 	}
    58. 	else {
    59. 		int data = Q->data[Q->front];
    60. 		Q->front = (Q->front + 1) % MAXSIZE;
    61. 		return data;
    62. 	}
    63. }
    64.  
    65. void printQueue(Queue* Q)//遍历队列打印
    66. {
    67. 	//要知道队列当前有多少个元素
    68. 	int length = (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
    69. 	int index = Q->front;
    70. 	for (int i = 0; i < length; i++)
    71. 	{
    72. 		printf("%d -> ", Q->data[index]);
    73. 		index = (index + 1) % MAXSIZE;
    74. 	}
    75. 	printf("NULL\n");
    76. }
    77.  
    78. int main()
    79. {
    80. 	Queue* Q = initQueue();
    81. 	enQueue(Q, 1);
    82. 	enQueue(Q, 2);
    83. 	enQueue(Q, 3);
    84. 	enQueue(Q, 4);
    85. 	printQueue(Q);//1 -> 2 -> 3 -> 4 -> NULL
    86. 	deQueue(Q);
    87. 	printQueue(Q);//2 -> 3 -> 4 -> NULL
    88. 	return 0;
    89. }

    8.运行结果

     

     

     

  • 相关阅读:
    john 探测(爆破)弱口令（包含linux机器，aix小机）亲测可用
    代码随想录算法训练营第23期day10 |232.用栈实现队列、225. 用队列实现栈
    redis——缓存雪崩、缓存穿透、缓存击穿
    git基础操作随记
    C#练习题1和2
    【LeetCode】删除无效的括号 [H]（递归）
    重新认识下JVM级别的本地缓存框架Guava Cache——优秀从何而来
    Oracle主机变量锚定、游标变量
    如何设置从小程序跳转到其它小程序
    SSL、TLS、HTTPS的关系
  • 原文地址：https://blog.csdn.net/m0_73983707/article/details/133874129