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

单向循环链表——插入、删除、实现约瑟夫环、排序

作者：从前慢现在也慢 | 2024-02-08 09:42:05

赞

踩

单向循环链表——插入、删除、实现约瑟夫环、排序

2024年2月3日
1.请编程实现单向循环链表的头插，头删、尾插、尾删

自定义头文件：

  1. #ifndef __head_h__
  2. #define __head_h__
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6. typedef int datatype;
  7. typedef struct Node
  8. {
  9. 	datatype data;
  10. 	struct Node *next;
  11. }*Linklist;
  12. Linklist create();
  13. Linklist insert_head(Linklist head,datatype element);
  14. Linklist insert_rear(Linklist head,datatype element);
  15. void output(Linklist head);
  16. Linklist delete_head(Linklist head);
  17. Linklist delete_rear(Linklist head);
  18.  
  19. #endif

主函数：

  1. #include"head.h"
  2. int main(int argc, const char *argv[])
  3. {
  4. 	datatype element;
  5. 	int num;
  6. 	Linklist head=NULL;
  7. 	printf("please enter num:");
  8. 	scanf("%d",&num);
  9. 	for(int i=0;i<num;i++)
  10. 	{
  11. 		printf("please enter %d element:",i+1);
  12. 		scanf("%d",&element);
  13. 		//head=insert_head(head,element);
  14. 		head=insert_rear(head,element);
  15. 	}
  16. 	output(head);
  17. 	puts("");
  18. 	head=delete_head(head);
  19. 	output(head);
  20. 	puts("");
  21. 	head=delete_rear(head);
  22. 	output(head);
  23. 	return 0;
  24. }

自定义函数:

  1. #include"head.h"
  2. /*
  3.  * function:    创建新节点
  4.  * @param [ in] 
  5.  * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
  6.  * @return      
  7.  */
  8. Linklist create()
  9. {
  10. 	Linklist s=(Linklist)malloc(sizeof(struct Node));
  11. 	if(s==NULL)
  12. 		return NULL;
  13. 	s->data=0;
  14. 	s->next=s;
  15. 	return s;
  16. }
  17. /*
  18.  * function:   头插
  19.  * @param [ in] 头　插入的值
  20.  * @param [out] 头
  21.  * @return      
  22.  */
  23. Linklist insert_head(Linklist head,datatype element)
  24. {
  25. 	Linklist s=create();
  26. 	s->data=element;
  27. 	if(head==NULL)
  28. 	{
  29. 		head=s;
  30. 	}
  31. 	else
  32. 	{
  33. 		Linklist p=head;
  34. 		while(p->next!=head)
  35. 			p=p->next;
  36. 		s->next=head;
  37. 		head=s;
  38. 		p->next=head;
  39. 	}
  40. 	return head;
  41. }
  42. /*
  43.  * function:    尾插　
  44.  * @param [ in] 头　插入值
  45.  * @param [out] 头
  46.  * @return      
  47.  */
  48. Linklist insert_rear(Linklist head,datatype element)
  49. {
  50. 	Linklist s=create();
  51. 	s->data=element;
  52. 	if(head==NULL)
  53. 	{
  54. 		head=s;
  55. 		return head;
  56. 	}
  57. 	Linklist p=head;
  58. 	while(p->next!=head)
  59. 	{
  60. 		p=p->next;
  61. 	}
  62. 	p->next=s;
  63. 	s->next=head;
  64. 	return head;
  65. }
  66. /*
  67.  * function:    遍历输出
  68.  * @param [ in] 头
  69.  * @param [out] 
  70.  * @return      
  71.  */
  72. void output(Linklist head)
  73. {
  74. 	if(head==NULL)
  75. 	{
  76. 		puts("empty");
  77. 		return;
  78. 	}
  79. 	Linklist p=head;
  80. 	do
  81. 	{
  82. 		printf("%-5d",p->data);
  83. 		p=p->next;
  84. 	}while(p!=head);
  85. }
  86. /*
  87.  * function:    头删
  88.  * @param [ in] 头
  89.  * @param [out] 头
  90.  * @return      
  91.  */
  92. Linklist delete_head(Linklist head)
  93. {
  94. 	if(head==NULL)
  95. 		return head;
  96. 	Linklist del=head;
  97. 	Linklist p=head;
  98. 	while(p->next!=head)
  99. 		p=p->next;
  100. 	p->next=head->next;
  101. 	head=head->next;
  102. 	free(del);
  103. 	return head;
  104. }
  105. /*
  106.  * function:    尾删
  107.  * @param [ in] 头
  108.  * @param [out] 头
  109.  * @return      
  110.  */
  111. Linklist delete_rear(Linklist head)
  112. {
  113. 	if(head==NULL)
  114. 		return NULL;
  115. 	if(head->next==head)
  116. 	{
  117. 		free(head);
  118. 		head=NULL;
  119. 		return head;
  120. 	}
  121. 	Linklist p=head;
  122. 	while(p->next->next!=head)
  123. 	{
  124. 		p=p->next;
  125. 	}
  126. 	Linklist del=p->next;
  127. 	free(del);
  128. 	del=NULL;
  129. 	p->next=head;
  130. 	return head;
  131. }

尾插、头删、尾删

头插、头删、尾删

⒉请编程实现单向循环链表约瑟夫环
约瑟夫环:用循环链表编程实现约瑟夫问题
n个人围成一圈，从某人开始报数1,2, .; m，数到m的人出圈，然后从出圈的下一个人(m+1)开始重复此过程，直到全部人出圈，于是得到一个出圈人员的新序列
如当n=8，m=4时，若从第一个位置数起，则所得到的新的序列为4,8,5,2,1,3,7,6。

头文件：

  1. #ifndef __head_h__
  2. #define __head_h__
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6. typedef int datatype;
  7. typedef struct Node
  8. {
  9. 	datatype data;
  10. 	struct Node *next;
  11. }*Linklist;
  12. Linklist create();
  13. Linklist insert_rear(Linklist head,datatype element);
  14. void output(Linklist head);
  15. Linklist joseph(Linklist head,int n,int m);
  16.  
  17. #endif

主函数：

  1. #include"head.h"
  2. int main(int argc, const char *argv[])
  3. {
  4. 	datatype element;
  5. 	int num;
  6. 	Linklist head=NULL;
  7. 	printf("please enter num:");
  8. 	scanf("%d",&num);
  9. 	for(int i=0;i<num;i++)
  10. 	{
  11. 		printf("please enter %d element:",i+1);
  12. 		scanf("%d",&element);
  13. 		head=insert_rear(head,element);
  14. 	}
  15. 	output(head);
  16. 	puts("");
  17. 	int m;
  18. 	printf("please enter m:");
  19. 	scanf("%d",&m);
  20. 	head=joseph(head,num,m);
  21. 	return 0;
  22. }

自定义函数：

  1. /*
  2.  * function:    创建新节点
  3.  * @param [ in] 
  4.  * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
  5.  * @return      
  6.  */
  7. Linklist create()
  8. {
  9. 	Linklist s=(Linklist)malloc(sizeof(struct Node));
  10. 	if(s==NULL)
  11. 		return NULL;
  12. 	s->data=0;
  13. 	s->next=s;
  14. 	return s;
  15. }
  16. /*
  17.  * function:    尾插　
  18.  * @param [ in] 头　插入值
  19.  * @param [out] 头
  20.  * @return      
  21.  */
  22. Linklist insert_rear(Linklist head,datatype element)
  23. {
  24. 	Linklist s=create();
  25. 	s->data=element;
  26. 	if(head==NULL)
  27. 	{
  28. 		head=s;
  29. 		return head;
  30. 	}
  31. 	Linklist p=head;
  32. 	while(p->next!=head)
  33. 	{
  34. 		p=p->next;
  35. 	}
  36. 	p->next=s;
  37. 	s->next=head;
  38. 	return head;
  39. }
  40. /*
  41.  * function:    遍历输出
  42.  * @param [ in] 头
  43.  * @param [out] 
  44.  * @return      
  45.  */
  46. void output(Linklist head)
  47. {
  48. 	if(head==NULL)
  49. 	{
  50. 		puts("empty");
  51. 		return;
  52. 	}
  53. 	Linklist p=head;
  54. 	do
  55. 	{
  56. 		printf("%-5d",p->data);
  57. 		p=p->next;
  58. 	}while(p!=head);
  59. }
  60. Linklist joseph(Linklist head,int n,int m)
  61. {
  62. 	if(NULL==head)
  63. 		return head;
  64. 	Linklist p=head;
  65. 	for(int i=0;i<n;i++)
  66. 	{
  67. 		for(int j=0;j<m-2;j++)
  68. 		{
  69. 			p=p->next;
  70. 		}
  71. 		printf("%-5d",p->next->data);
  72. 		Linklist del=p->next;
  73. 		p->next=del->next;
  74. 		free(del);
  75. 		del=NULL;
  76. 		p=p->next;
  77. 	}
  78. }

3.请编程实现单向循环链表的排序

头文件：

  1. #ifndef __head_h__
  2. #define __head_h__
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6. typedef int datatype;
  7. typedef struct Node
  8. {
  9. 	datatype data;
  10. 	struct Node *next;
  11. }*Linklist;
  12. Linklist create();
  13. Linklist insert_rear(Linklist head,datatype element);
  14. void output(Linklist head);
  15. void bubble(Linklist head,int num);
  16. void simple(Linklist head);
  17.  
  18. #endif

主函数：

  1. #include"head.h"
  2. int main(int argc, const char *argv[])
  3. {
  4. 	datatype element;
  5. 	int num;
  6. 	Linklist head=NULL;
  7. 	printf("please enter num:");
  8. 	scanf("%d",&num);
  9. 	for(int i=0;i<num;i++)
  10. 	{
  11. 		printf("please enter %d element:",i+1);
  12. 		scanf("%d",&element);
  13. 		head=insert_rear(head,element);
  14. 	}
  15. 	output(head);
  16. 	puts("");
  17. 	//bubble(head,num);
  18. 	simple(head);
  19. 	output(head);
  20. 	return 0;
  21. }

自定义函数：

  1. #include"head.h"
  2. /*
  3.  * function:    创建新节点
  4.  * @param [ in] 
  5.  * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
  6.  * @return      
  7.  */
  8. Linklist create()
  9. {
  10. 	Linklist s=(Linklist)malloc(sizeof(struct Node));
  11. 	if(s==NULL)
  12. 		return NULL;
  13. 	s->data=0;
  14. 	s->next=s;
  15. 	return s;
  16. }
  17. /*
  18.  * function:    尾插　
  19.  * @param [ in] 头　插入值
  20.  * @param [out] 头
  21.  * @return      
  22.  */
  23. Linklist insert_rear(Linklist head,datatype element)
  24. {
  25. 	Linklist s=create();
  26. 	s->data=element;
  27. 	if(head==NULL)
  28. 	{
  29. 		head=s;
  30. 		return head;
  31. 	}
  32. 	Linklist p=head;
  33. 	while(p->next!=head)
  34. 	{
  35. 		p=p->next;
  36. 	}
  37. 	p->next=s;
  38. 	s->next=head;
  39. 	return head;
  40. }
  41. /*
  42.  * function:    遍历输出
  43.  * @param [ in] 头
  44.  * @param [out] 
  45.  * @return      
  46.  */
  47. void output(Linklist head)
  48. {
  49. 	if(head==NULL)
  50. 	{
  51. 		puts("empty");
  52. 		return;
  53. 	}
  54. 	Linklist p=head;
  55. 	do
  56. 	{
  57. 		printf("%-5d",p->data);
  58. 		p=p->next;
  59. 	}while(p!=head);
  60. }
  61. void bubble(Linklist head,int num)
  62. {
  63. 	if(NULL==head)
  64. 		return;	
  65. 	for(int i=1;i<num;i++)
  66. 	{
  67. 		Linklist p=head;
  68. 		for(int j=0;j<num-i;j++)
  69. 		{
  70. 			if(p->data>p->next->data)
  71. 			{
  72. 				datatype t=p->data;
  73. 				p->data=p->next->data;
  74. 				p->next->data=t;
  75. 			}
  76. 			p=p->next;
  77. 		}
  78. 	}
  79. }
  80. /*
  81.  * function:    简单选择排序
  82.  * @param [ in] 头
  83.  * @param [out] 
  84.  * @return      
  85.  */
  86. void simple(Linklist head)
  87. {
  88. 	if(NULL==head)
  89. 		return;
  90. 	for(Linklist i=head;i->next!=head;i=i->next)
  91. 	{
  92. 		Linklist min=i;
  93. 		for(Linklist j=i->next;j!=head;j=j->next)
  94. 		{
  95. 			if(min->data>j->data)
  96. 				min=j;
  97. 		}
  98. 		if(min!=i)
  99. 		{
  100. 			datatype t=i->data;
  101. 			i->data=min->data;
  102. 			min->data=t;
  103. 		}
  104. 	}
  105. }

冒泡排序：

简单选择排序：

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

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

  

闽ICP备14008679号