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

2024.7.19 作业

作者：小舞很执着 | 2024-08-02 12:54:45

赞

踩

2024.7.19 作业

1.链表的排序

  1. int list_sort(NodePtr L)
  2. {
  3. 	    if(NULL==L || L->len<=1)
  4.     	{
  5. 	 	    printf("排序失败");
  6.         	return -1;
  7.     	}
  8.    
  9.     	int len=L->len+1;
  10.     	NodePtr p;
  11.     	int i,j;
  12.     	for( i=1;i<len;i++)
  13.     	{
  14.         	for( j=0,p=L;j<len-i;j++,p=p->next)
  15.         	{
  16.             		if( p->data > p->next->data )
  17.             		{
  18.                 		datatype t=p->data;
  19.                 		p->data=p->next->data;
  20.                 		p->next->data=t;
  21.             		}
  22.         	}
  23.     	}
  24. 	    printf("排序成功\n");
  25. 	    return 0;
  26. }

2.链表的反转（递归实现）

  1. // 递归反转链表  
  2. NodePtr list_fz(NodePtr L) 
  3. {  
  4. 	    // 基础情况：空链表或只有一个节点  
  5.     	if (L == NULL || L->next == NULL) 
  6. 	    {  
  7.         	return L;  
  8.     	}  
  9.  
  10.    	    NodePtr new_L = list_fz(L->next);  
  11.  
  12.    	    L->next->next = L;  
  13.     	L->next = NULL;
  14.  
  15.     	return new_L; 
  16. }

3.链表去重

  1.  
  2. // 去重函数
  3. int list_dr(NodePtr L) 
  4. {
  5. 	 NodePtr current = L;
  6.      NodePtr prev = NULL;
  7.  
  8.    	 while (current != NULL) 
  9. 	 {
  10.         	NodePtr runner = L;
  11.         	prev = NULL;
  12.         	int flag = 0;
  13.  
  14.         	// 查找当前节点的重复项
  15.         	while (runner != current) 
  16. 		    {
  17.             		if (runner->data == current->data) 
  18. 			        {
  19.                 		flag = 1;
  20.                 		break;
  21.             		}
  22.             		prev = runner;
  23.             		runner = runner->next;
  24.         	}
  25.  
  26.         	if (flag) 
  27. 		    {
  28.             		// 如果是重复节点，删除当前节点
  29.             		NodePtr temp = current;
  30.             		if (prev != NULL) 
  31. 			        {
  32.                 		prev->next = current->next;
  33.             		} 
  34. 			        else 
  35. 			        {
  36.                 		L = current->next; // 更新头节点
  37.             
  38. 			        }
  39.             		current = current->next;
  40.             		free(temp);
  41.         	} 	
  42. 		    else 	
  43. 		    {
  44.             		current = current->next;
  45.         	}
  46.     	}
  47. }

linklist.h

  1. #ifndef LINKLIST_H
  2.  
  3. #define LINKLIST_H
  4. #include <myhead.h>
  5.  
  6. typedef int datatype;
  7.  
  8. typedef struct Node
  9. {
  10. 	union
  11. 	{
  12. 		int len;
  13. 		datatype data;
  14. 	};
  15.  
  16. 	struct Node *next;
  17. }Node,*NodePtr;
  18.  
  19. //创建链表
  20. NodePtr list_create();
  21.  
  22. //申请节点封装数据函数
  23. NodePtr apply_node(datatype e);
  24.  
  25. //链表判空
  26. int list_empty(NodePtr L);
  27.  
  28. //头插
  29. int list_insert_head(NodePtr L,datatype e);
  30.  
  31. //链表遍历函数
  32. int list_show(NodePtr L);
  33.  
  34. //通过位置查找节点
  35. NodePtr list_search_pos(NodePtr L,int pos);
  36.  
  37. //任意位置插入
  38. int list_insert_pos(NodePtr L,int pos,datatype e);
  39.  
  40. //链表头删
  41. int list_delete_head(NodePtr L);
  42.  
  43. //任意位置删除
  44. int list_delete_pos(NodePtr L,int pos);
  45.  
  46. //通过值查找返回位置
  47. int list_search_value(NodePtr L,datatype e);
  48.  
  49. //链表按位置进行修改
  50. int list_update_pos(NodePtr L,int pos,datatype e);
  51.  
  52. //链表按值进行修改
  53. int list_update_value(NodePtr L,datatype old_e,datatype new_e);
  54.  
  55. //将链表进行翻转
  56. void list_reverse(NodePtr L);
  57.  
  58. //释放链表
  59. void list_destroy(NodePtr L);
  60.  
  61. //链表排序
  62. int list_sort(NodePtr L);
  63.  
  64. // 去重函数
  65. int list_dr(NodePtr head);
  66.  
  67. // 递归反转链表 
  68. NodePtr list_fz(NodePtr L);
  69.  
  70.  
  71. #endif

linklist.c

  1. #include "linklist.h"
  2.  
  3. NodePtr list_create()
  4. {
  5. 	NodePtr L=(NodePtr)malloc(sizeof(Node));
  6. 	if(NULL==L)
  7. 	{
  8. 		printf("创建失败\n");
  9. 		return NULL;
  10. 	}
  11. 	L->len=0;
  12. 	L->next=NULL;
  13. 	printf("链表创建成功\n");
  14. 	return L;
  15. }
  16.  
  17. //申请节点封装数据函数
  18. NodePtr apply_node(datatype e)
  19. {
  20. 	NodePtr p=(NodePtr)malloc(sizeof(Node));
  21. 	if(NULL==p)
  22. 	{
  23. 		printf("申请失败\n");
  24. 		return NULL;
  25. 	}
  26. 	p->data = e;
  27. 	p->next = NULL;
  28. 	return p;
  29. }
  30.  
  31. //链表判空
  32. int list_empty(NodePtr L)
  33. {
  34. 	return L->next ==NULL;
  35. }
  36.  
  37. //头插
  38. int list_insert_head(NodePtr L,datatype e)
  39. {
  40. 	if(NULL==L)
  41. 	{
  42. 		printf("链表不合法\n");
  43. 		return -1;
  44. 	}
  45. 	NodePtr p = apply_node(e);
  46. 	if(NULL==p)
  47. 	{
  48. 		return -1;
  49. 	}
  50. 	p->next=L->next;
  51. 	L->next=p;
  52. 	
  53. 	L->len++;
  54. 	printf("头插成功\n");
  55. 	return 0;
  56.  
  57. }
  58.  
  59. //链表遍历函数
  60. int list_show(NodePtr L)
  61. {
  62. 	if(NULL==L || list_empty(L))
  63. 	{
  64. 		printf("遍历失败\n");
  65. 		return -1;
  66. 	}	
  67.  
  68. 	NodePtr q = L->next;
  69. 	while(q!=NULL)
  70. 	{
  71. 		printf("%d\t",q->data);
  72. 		q=q->next;
  73. 	}
  74. 	putchar(10);
  75. }
  76.  
  77. //通过位置查找节点
  78. NodePtr list_search_pos(NodePtr L,int pos)
  79. {
  80. 	if(NULL==L || list_empty(L) || pos<0 || pos>L->len)
  81. 	{
  82. 		printf("查找失败\n");
  83. 		return NULL;
  84. 	}
  85. 	NodePtr q= L;
  86. 	for(int i=0;i<pos;i++)
  87. 	{
  88. 		q=q->next;
  89. 	}
  90. 	return q;
  91. }
  92.  
  93. //任意位置插入
  94. int list_insert_pos(NodePtr L,int pos,datatype e)
  95. {
  96. 	if(NULL==L || pos<=0 ||pos>L->len+1)
  97. 	{
  98. 		printf("插入失败\n");
  99. 		return -1;
  100. 	}
  101. 	NodePtr p = apply_node(e);
  102. 	if(NULL==p)
  103. 	{
  104. 		return -1;
  105. 	}
  106. 	NodePtr q =list_search_pos(L,pos-1);
  107.  
  108. 	p->next=q->next;
  109. 	q->next=p;
  110. 	
  111. 	L->len++;
  112. 	printf("插入成功\n");
  113. 	return 0;
  114. }
  115.  
  116.  
  117. //链表头删
  118. int list_delete_head(NodePtr L)
  119. {
  120. 	if(NULL==L || list_empty(L))
  121. 	{
  122. 		printf("删除失败\n");
  123. 		return -1;
  124. 	}
  125. 	NodePtr p=L->next;
  126. 	L->next=p->next;
  127. 	free(p);
  128. 	p=NULL;
  129.  
  130. 	L->len--;
  131. 	printf("头删成功\n");
  132. 	return 0;
  133. }
  134.  
  135. //任意位置删除
  136. int list_delete_pos(NodePtr L,int pos)
  137. {
  138. 	if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
  139. 	{
  140. 		printf("删除失败\n");
  141. 		return -1;
  142. 	}
  143. 	NodePtr q=list_search_pos(L,pos-1);
  144. 	NodePtr p=q->next;
  145. 	q->next =p->next;
  146. 	free(p);
  147. 	p=NULL;
  148.  
  149. 	L->len--;
  150. 	printf("删除成功\n");
  151. 	return 0;
  152. }
  153.  
  154. //通过值查找返回位置
  155. int list_search_value(NodePtr L,datatype e)
  156. {
  157. 	if(NULL==L || list_empty(L))
  158. 	{
  159. 		printf("查找失败\n");
  160. 		return -1;
  161. 	}
  162.  
  163. 	NodePtr q=L->next;
  164. 	for(int index=1;index<=L->len;index++)
  165. 	{
  166. 		if(q->data==e)
  167. 		{
  168. 			return index;
  169. 		}
  170. 		q=q->next;
  171. 	}
  172. 	printf("没找到\n");
  173. 	return -1;
  174. }
  175.  
  176. //链表按位置进行修改
  177. int list_update_pos(NodePtr L,int pos,datatype e)
  178. {
  179. 	if(NULL==L || list_empty(L) || pos<1 || pos>L->len )
  180. 	{
  181. 		printf("修改失败\n");
  182. 		return -1;
  183. 	}
  184.  
  185. 	list_search_pos(L,pos)->data = e;
  186. 	printf("修改成功\n");
  187. 	return 0;
  188. }
  189.  
  190. //链表按值进行修改
  191. int list_update_value(NodePtr L,datatype old_e,datatype new_e)
  192. {
  193. 	if(NULL==L || list_empty(L))
  194. 	{
  195. 		printf("修改失败\n");
  196. 		return -1;
  197. 	}
  198. 	int res = list_search_value(L,old_e);
  199. 	if(res == -1)
  200. 	{
  201. 		printf("没有要修改的值\n");
  202. 		return -1;
  203. 	}
  204. 	list_update_pos(L,res,new_e);
  205. 	printf("修改成功\n");
  206. 	return 0;
  207.  
  208. }
  209.  
  210. //将链表进行翻转
  211. void list_reverse(NodePtr L)
  212. {
  213. 	if(NULL==L || L->len<=1)
  214. 	{
  215. 		printf("翻转失败\n");
  216. 		return;
  217. 	}
  218. 	NodePtr H = L->next;
  219. 	L->next = NULL;
  220. 	NodePtr p = NULL;
  221. 	while(H!=NULL)
  222. 	{
  223. 		p=H;
  224. 		H=H->next;
  225. 		p->next =L->next;
  226. 		L->next =p;
  227. 	}
  228. 	printf("翻转成功\n");
  229. 	return;
  230. }
  231.  
  232. //释放链表
  233. void list_destroy(NodePtr L)
  234. {
  235. 	//判断逻辑
  236.     	if(NULL == L)
  237.     	{
  238.         	return;
  239.     	}
  240.  
  241.     	//将所有结点进行释放
  242.     	while(!list_empty(L))
  243.     	{
  244.         	//头删
  245.         	list_delete_head(L);
  246.     	}
  247.  
  248.     	//释放头结点
  249.     	free(L);
  250.     	L = NULL;
  251.  
  252.     	printf("释放成功\n");
  253. }
  254.  
  255.  
  256.  
  257.  
  258. //链表排序
  259. int list_sort(NodePtr L)
  260. {
  261. 	if(NULL==L || L->len<=1)
  262.     	{
  263. 	 	printf("排序失败");
  264.         	return -1;
  265.     	}
  266.    
  267.     	int len=L->len+1;
  268.     	NodePtr p;
  269.     	int i,j;
  270.     	for( i=1;i<len;i++)
  271.     	{
  272.         	for( j=0,p=L;j<len-i;j++,p=p->next)
  273.         	{
  274.             		if( p->data > p->next->data )
  275.             		{
  276.                 		datatype t=p->data;
  277.                 		p->data=p->next->data;
  278.                 		p->next->data=t;
  279.             		}
  280.         	}
  281.     	}
  282. 	printf("排序成功\n");
  283. 	return 0;
  284. }
  285.  
  286.  
  287. // 递归反转链表  
  288. NodePtr list_fz(NodePtr L) 
  289. {  
  290. 	// 基础情况：空链表或只有一个节点  
  291.     	if (L == NULL || L->next == NULL) 
  292. 	{  
  293.         	return L;  
  294.     	}  
  295.  
  296.    	NodePtr new_L = list_fz(L->next);  
  297.  
  298.    	L->next->next = L;  
  299.     	L->next = NULL;
  300.  
  301.     	return new_L; 
  302. } 
  303.  
  304.  
  305.  
  306.  
  307. // 去重函数
  308. int list_dr(NodePtr L) 
  309. {
  310. 	NodePtr current = L;
  311.     	NodePtr prev = NULL;
  312.  
  313.    	 while (current != NULL) 
  314. 	 {
  315.         	NodePtr runner = L;
  316.         	prev = NULL;
  317.         	int flag = 0;
  318.  
  319.         	// 查找当前节点的重复项
  320.         	while (runner != current) 
  321. 		{
  322.             		if (runner->data == current->data) 
  323. 			{
  324.                 		flag = 1;
  325.                 		break;
  326.             		}
  327.             		prev = runner;
  328.             		runner = runner->next;
  329.         	}
  330.  
  331.         	if (flag) 
  332. 		{
  333.             		// 如果是重复节点，删除当前节点
  334.             		NodePtr temp = current;
  335.             		if (prev != NULL) 
  336. 			{
  337.                 		prev->next = current->next;
  338.             		} 
  339. 			else 
  340. 			{
  341.                 		L = current->next; // 更新头节点
  342.             
  343. 			}
  344.             		current = current->next;
  345.             		free(temp);
  346.         	} 	
  347. 		else 	
  348. 		{
  349.             		current = current->next;
  350.         	}
  351.     	}
  352. }

main.c

  1. #include"linklist.h"
  2.  
  3. int main(int argc, const char *argv[])
  4. {
  5.     
  6. 	//调用函数创建一个链表
  7.     	NodePtr L = list_create();
  8.     	if(NULL == L)
  9.     	{
  10.         	return -1;
  11.     	}
  12.  
  13.     	//调用头插函数
  14.     	list_insert_head(L, 520);
  15.     	list_insert_head(L, 1314);
  16.     	list_insert_head(L, 666);
  17.     	list_insert_head(L, 999);
  18.     
  19.     	//调用遍历函数
  20.     	list_show(L);
  21.  
  22.     	//调用任意位置插入函数
  23.     	list_insert_pos(L, 1, 100);
  24.    	    list_insert_pos(L, 3, 100);
  25.     	list_insert_pos(L, L->len+1, 100);
  26.     	list_show(L);
  27. 	    printf("排序: ");
  28. 	    list_sort(L);
  29. 	    list_show(L);
  30. 	    printf("去重：");
  31. 	    list_dr(L);
  32. 	    list_show(L);
  33. 	    printf("反转：");
  34. 	    L->next=list_fz(L->next);
  35. 	    list_show(L);
  36.     	return 0;
  37. }

思维导图

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

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

  

闽ICP备14008679号