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

单链表应用_c语言 单链表 应用用途

作者：AllinToyou | 2024-04-15 07:51:08

赞

踩

c语言 单链表 应用用途

目录

1.有关数据结构的体系

 2.带头节点的单项不循环链表

        1）创建.h文件进行宏定义

2）为链表动态分配空间

②透过设置参数的方式  

3）判断链表是否为空  

4）插入数据 

5）删除数据 

6）查找数据，并返回数据所对应的下标  

7）按顺序插入数据     

8）按值删除     

9）输出链表中的值       

10）释放空间       

3.一元多项式的合并

1）定义结构体

2) 创建链表

3）输出链表

4）合并链表

4.不带头节点的单项循环链表

1）定义结构体

2）创建循环链表

 3）显示链表

4）删除直到最后一个

1.有关数据结构的体系

 2.带头节点的单项不循环链表

        利用链表实现函数功能

        1）创建.h文件进行宏定义

  1. #ifndef LIST_H__
  2. #define LIST_H__
  3.  
  4. typedef struct node_st
  5. {
  6. 	int data;
  7. 	struct node_st *next;
  8. }LIST;
  9.  
  10. LIST *list_create();
  11. void list_create1(LIST **p);
  12.  
  13. int list_isempty(LIST *);
  14.  
  15. //pos
  16. int list_insert(LIST *,int pos, int *newdata);
  17. int list_delete(LIST *,int pos, int *newdata);
  18.  
  19. //value
  20. int list_insert_value(LIST *,int *newdata);
  21. int list_delete_value(LIST *,int *newdata);
  22.  
  23. int list_find(LIST *,int *data);
  24.  
  25. void list_display(LIST *);
  26.  
  27. void list_destroy(LIST *);
  28.  
  29.  
  30. #endif

2）为链表动态分配空间

①通过返回的方式        

  1. LIST *list_create()
  2. {
  3. 	LIST *p;//定义一个结构体类型的指针
  4.  
  5. 	p = malloc(sizeof(*p));   //分配动态空间
  6. 	if(p == NULL)            //判断是否为空
  7. 		return NULL;
  8.  
  9. 	p->next = NULL;
  10. 	return p;
  11. }

②透过设置参数的方式  

  1. void list_create1(LIST **p)
  2. {
  3. 	*p = malloc(sizeof(**p));    //动态分配空间
  4.     if(*p == NULL)               //判断是否分配成功
  5.         return ;
  6.  
  7.     (*p)->next = NULL;
  8.     return ;
  9. }

3）判断链表是否为空  

  1. int list_isempty(LIST *p)
  2. {
  3. 	if(p->next == NULL)
  4. 		return 1;
  5. 	return 0;
  6. }

4）插入数据 

  1. int list_insert(LIST *ptr,int pos, int *newdata)
  2. {    
  3. 	int i = 0;
  4. 	LIST *p = ptr,*q;
  5. 	while(i < pos && p )    //链表遍历，找到pos位置，并且指针不为空
  6. 	{
  7. 		p = p->next;
  8. 		i++;
  9. 	}
  10. 	if(p)
  11. 	{
  12. 		q = malloc(sizeof(*q));    //给新定义的结构体指针变量分配空间
  13. 		if(q == NULL)                
  14. 			return -1;
  15. 		q->data = *newdata;        //将要插入的值 赋值给变量q的data
  16. 		q->next = p->next;        //将p中next指向的地址 赋值给q的next
  17. 		p->next = q;               //将q的地址给p的next
  18. 		return 0;
  19. 	}
  20. 	else
  21. 		return -2;
  22. }

        插入数据时，需要先动态分配一个空间（q）来保存插入的数据，将插入位置前驱结点（p）中的next赋值给q中的next，前驱结点（q）中的next保存q的地址

5）删除数据 

  1. int list_delete(LIST *ptr,int pos, int *newdata)
  2. {
  3. 	int i = 0;
  4.     LIST *p = ptr,*q;
  5.  
  6. 	if(list_isempty(ptr))    //判断链表是否为空
  7. 		return -2;
  8.  
  9.     while(i < pos && p )    //遍历，找到所要删除的位置前驱结点
  10.     {
  11.         p = p->next;
  12.         i++;
  13.     }
  14.  
  15. 	if(p)    
  16. 	{
  17. 		q = p->next;        //所要删除的位置
  18. 		p->next = q->next;    //将删除位置的next赋值给前驱结点，赋值完成后它的前驱结点指向它的后继结点
  19. 		if(newdata != NULL)
  20. 			*newdata = q->data;
  21. 		free(q);        将所要删除的结点释放
  22. 		q = NULL;
  23. 		return 0;
  24. 	}
  25. 	else 
  26. 		return -1;
  27. }

        删除结点时要先找到它的前驱结点，再让它的前驱结点指向它的后继结点，之后将所要删除位置空间释放

6）查找数据，并返回数据所对应的下标  

  1. int list_find(LIST *ptr,int *data)
  2. {
  3. 	int i=0;
  4. 	if(list_isempty(ptr))
  5. 		return 0;
  6. 	LIST *p = ptr->next;
  7. 	while(p->data!=*data)
  8. 	{	
  9. 		i++;
  10. 		p = p -> next;
  11. 		if(p==NULL)
  12. 		{
  13. 			return 0;
  14. 		}
  15. 	}
  16. 		return i;
  17. }

7）按顺序插入数据     

  1. int list_insert_value(LIST *ptr,int *newdata)
  2. {
  3. 	LIST *p = ptr,*q;
  4.  
  5. 	while(p->next && p->next->data < *newdata)    //当p不为NULL并且当插入的数据大于链表中的数据时，p指针向后移
  6. 		p = p->next;
  7.  
  8. 	q = malloc(sizeof(*q));    //给q动态分配一个空间
  9. 	if(q == NULL)
  10. 		return -1;
  11. 	q->data = *newdata;        
  12. 	q->next = p->next;         //将p中的next赋值给q的next
  13. 	p->next = q;        //将q的地址赋值给p的next
  14. 	return 0;
  15. }

8）按值删除     

  1. int list_delete_value(LIST *ptr,int *newdata)
  2. {// ->  -   2 4 6 8   *newdata = 6;
  3. 	
  4. 	LIST *p = ptr,*q;
  5.  
  6. 	if(list_isempty(ptr))
  7. 		return -2;
  8.  
  9. 	while(p->next && p->next->data != *newdata)    //当不p->next不为空并且数据不相等，向后移
  10. 		p = p->next;
  11.  
  12. 	if(p->next == NULL)
  13. 		return -1;
  14. 	else
  15. 	{
  16. 		q = p->next;    //将p的next赋值给q
  17. 		p->next = q->next;    //将q中的next赋值给p的next
  18. 		free(q);    //释放q的空间
  19. 		q = NULL;
  20. 		return 0;
  21. 	}
  22. }

9）输出链表中的值       

  1. void list_display(LIST *ptr)
  2. {
  3. 	LIST *p = ptr->next;
  4. 	
  5. 	if(list_isempty(p))
  6. 		return ;
  7.  
  8. 	while(p)
  9. 	{
  10. 		printf("%d ",p->data);
  11. 		p = p->next;
  12. 	}
  13. 	printf("\n");
  14. }

10）释放空间       

  1. void list_destroy(LIST *ptr)
  2. {
  3. 	LIST *p = ptr->next,*q;
  4.  
  5. 	if(list_isempty(p))
  6.         return ;
  7.  
  8. 	while(p)
  9.     {
  10. 		q = p->next;
  11.         free(p);
  12. 		p = q;
  13.     }
  14. 	free(ptr);
  15. }

3.一元多项式的合并

1）定义结构体

  1. typedef struct num_st
  2. {
  3.     int coef;
  4.     int exp;
  5.     struct num_st  *next;
  6. }NUM;

2) 创建链表

  1. NUM *poly_create(int (*a)[2],int n)
  2. {
  3.     int i;
  4.     NUM *p,*head,*q;
  5.     head=malloc(sizeof(*head));  //动态分配空间
  6.     if(head==NULL)
  7.     {
  8.         return NULL;
  9.     }
  10.     head->next = NULL;
  11.  
  12.     p=head;
  13.     for(i=0;i<n;i++)            
  14.     {
  15.         q = malloc(sizeof(*q));
  16.         if(q == NULL)
  17.             return NULL;
  18.         q->coef = a[i][0];       //将数组中第一列中的数赋值到链表中（方程式中的常数）
  19.         q->exp = a[i][1];        //将数组中第二列中的数赋值到链表中（幂次）
  20.         q->next = NULL;            
  21.  
  22.         p->next= q;            //将q地址保存到p的next中    
  23.         p=q;                  //将q赋值给p    意思是p向后移
  24.     }
  25.     return head;
  26. }

3）输出链表

  1. void display(NUM *head)
  2. {
  3.     NUM *p=head->next;
  4.     while(p)
  5.     {
  6.     printf("(%d,%d)",p->coef,p->exp);
  7.     p=p->next;
  8.     }
  9.     printf("\n");
  10. }

4）合并链表

  1. void poly_add(NUM *ptr1,NUM *ptr2)
  2. {
  3.     NUM *r = ptr1;
  4.     NUM *p = ptr1->next;
  5.     NUM *q = ptr2->next;
  6.  
  7.     while(p && q)                //判断当p和q都不为NULL时，执行循环
  8.     {
  9.         if(p->exp < q->exp)    //判断 当p的exp(幂)值小于q的exp（幂）值
  10.         {
  11.             r->next=p;    //将p赋值给r的next
  12.             r=p;          //r向后移
  13.             p=p->next;    //p向后移
  14.         }
  15.         else                //判断 当p的exp(幂)值大于或等于q的exp（幂）值
  16.         {
  17.             if(p->exp>q->exp)    
  18.             {
  19.                 r->next = q;    //将q赋值给r的next
  20.                 r = q;          //r向后移
  21.                 q=q->next;      //q向后移
  22.             }
  23.             else
  24.             {
  25.                 p->coef += q->coef;//当幂相等时，两个系数相加，保存到p的coef中
  26.                 if(p->coef)    //判断系数是否为0 
  27.                 {
  28.                     r->next=p;  //p赋值到r的next中
  29.                     r=p;        //r向后移
  30.                 }
  31.                 p=p->next;    //p后移
  32.                 q=q->next;    //q后移
  33.             }
  34.         }
  35.     }
  36.     if(p==NULL)    //当p链表为空时，连接q
  37.         r->next=q;
  38.     else             //当q链表为空时，连接p
  39.         r->next=p;
  40. }

4.不带头节点的单项循环链表

约瑟夫环

1）定义结构体

  1. typedef struct node_st
  2. {
  3. 	int data;
  4. 	struct node_st *next;
  5. }JOSEPHU;

2）创建循环链表

  1. JOSEPHU *josephu_create(int n)
  2. {
  3. 	JOSEPHU *l,*p,*q;
  4. 	int i = 1;
  5.  
  6. 	l = malloc(sizeof(*l));
  7. 	if(l == NULL)
  8. 		return NULL;
  9. 	l->data = i;        //给第一个结点赋值
  10. 	l->next = l;        //让第一个结点指向第一个结点
  11.  
  12. 	p = l;
  13. 	i++;
  14.  
  15. 	while(i <= n)
  16. 	{
  17. 		q = malloc(sizeof(*q));
  18. 		if(q == NULL)
  19. 			return NULL;
  20. 		q->data = i;        //给结点赋值
  21. 		i++;
  22. 		q->next = l;       //让最后一个结点指向第一个 
  23. 		p->next = q;      //将p的next指向q 用于链表连接
  24. 		p = q;        //q赋值给p
  25. 	}
  26. 	return l;
  27. }

 3）显示链表

  1. void josephu_show(JOSEPHU *l)
  2. {
  3. 	JOSEPHU *p = l;
  4.  
  5. 	while(p->next != l)
  6. 	{
  7. 		printf("%d ",p->data);
  8. 		p = p->next;
  9. 	}
  10. 	printf("%d\n",p->data);
  11. }

4）删除直到最后一个

  1. void josephu_kill(JOSEPHU **l, int n)
  2. {
  3. 	int i = 1;
  4. 	JOSEPHU *p = *l,*q;
  5.  
  6. 	printf("KILL:");
  7.  
  8. 	while(p->next != p)    //当指向自己的时候循环结束
  9. 	{
  10. 		while(i < n)        //寻找第n个
  11. 		{
  12. 			q = p;
  13. 			p = p->next;
  14. 			i++;
  15. 		}
  16.  
  17. 		q->next = p->next;
  18. 		printf("%d ",p->data);
  19. 		free(p);
  20.  
  21. 		i = 1;
  22. 		p = q->next;
  23. 	}
  24. 	printf("\n");
  25.  
  26. 	*l = p;
  27. }

注：本文是通过听李慧芹老师上课记的笔记，如有理解不到位请多多包涵，也请多多指教

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

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

  

闽ICP备14008679号