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

链表的设计_首先定义一个节点类,包含数据域和指针域,然后定义链表类,链表中包含一个头节点,该

作者：Li_阴宅 | 2024-07-01 18:29:08

赞

踩

首先定义一个节点类,包含数据域和指针域,然后定义链表类,链表中包含一个头节点,该

定义

        链表是一种常见的基础数据结构，利用结构体指针来实现一个链表。链表可以动态的进行存储分配，也就是说，链表可以理解为是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。

        链表都有一个头指针，一般以head来表示，存放的是一个地址。链表的每一个元素叫做节点，每个节点包含数据域和指针域；链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。总而言之，在链表中head指向第一个元素：第一个元素又指向第二个元素；直到最后一个元素，该元素的指针域不再指向其它元素，它的指针域部分放一个“NULL”（表示“空地址”），链表到此结束。总而言之，链表的头结点没有前驱，有一个后继，末尾节点没有后继，只有唯一的前驱，其余每一个节点只有唯一的一个前驱和后继。对于循环链表，即是将其尾结点的指针域指向头结点，这样就构成了一个闭环，即为单向循环链表。

 

       对链表的操作有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

对于链表，常见的一般是单向链表，其定义方式如下：

  1. typedef struct student{

  2. int ID;

  3. struct student *next;

  4. } LinkList；

 此处定义了一个学生结构体，并将其重命名为LinkList,对于每一个学生节点，其内部包含了他的ID信息和下一个学生节点的地址，存储这样一系列的节点的结构就被称之为链表。

实例

下面以一个实例对单向链表进行讲解 ：

  1. #ifndef _LINKLIST_H
  2. #define _LINKLIST_H
  3.  
  4. typedef int linklist_data_t;
  5.  
  6. typedef struct linklist{
  7.     linklist_data_t data;
  8.     struct linklist* next;
  9. }lkl_node, *lkl_pnode;
  10.  
  11. //创建头节点
  12. lkl_pnode create_linklist();
  13.  
  14. //插入
  15. int insert_linklist(lkl_pnode H, int pos, linklist_data_t data);
  16.  
  17. //打印
  18. int show_linklist(lkl_pnode H);
  19.  
  20. //判空
  21. int empty_linklist(lkl_pnode H);
  22.  
  23. //获取链表长度
  24. int getlen_linklist(lkl_pnode H);
  25.  
  26. //删除
  27. int delete_linklist(lkl_pnode H, linklist_data_t data); //按值删除
  28.  
  29. int delete1_linklist(lkl_pnode H, int pos);//按位置删除
  30. //查询
  31. linklist_data_t search_linklist(lkl_pnode H, int pos); //按位置查询值
  32. int search1_linklist(lkl_pnode H, linklist_data_t data);//按值查位置
  33. //修改
  34. int change_linklist(lkl_pnode H, int pos, linklist_data_t data);  //按位置修改值
  35. int change1_linklist(lkl_pnode H, linklist_data_t old_data, linklist_data_t new_data);
  36. //清空
  37. int clean_linklist(lkl_pnode H);
  38. //销毁
  39. int destroy_linklist(lkl_pnode *H);
  40. //链表的逆序
  41. int  linklist_reverse(lkl_pnode H);
  42. //链表的排序
  43. int linklist_sort(lkl_pnode H);
  44.  
  45. #endif

         在上述头文件中，我们定义了一个存储int型数据的节点结构体 ，使用typedef int linklist_data_t;的原因是如果直接在结构体内部声明data的数据类型为int,若后期需要存储其他类型的数据如char、double、float等，就需要去结构体内部更改，代码的复用性就大大降低了。而使用上面这种方式，只需要将typedef int linklist_data_t;改为typedef char linklist_data_t;就可以实现从存储int型转换为存储char型或则其他类型。

        同时，在头文件中我们声明了对链表实现某些操作的功能函数，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

接下来是这些功能函数的实现方法：

1、链表的创建

  1. //创建头节点
  2. lkl_pnode create_linklist()
  3. {
  4.     //创建堆区空间
  5.     lkl_pnode H = (lkl_pnode)malloc(sizeof(lkl_node));
  6.     if (NULL == H)
  7.     {
  8.         printf("malloc is default\n");
  9.         return NULL;
  10.     }
  11.     H->next = NULL;  //一开始是没有其他节点的，所以头节点指向NULL
  12.     H->data = -1;//对于头结点的数据域，不使用，初始化为-1，以便用户识别
  13.     return H;
  14. }

对于链表的创建，只需要创建一个头结点即可，后续的其他操作均是在头结点后面进行。对于创建函数，返回链表的头结点。

2、链表的判空

  1. //判空
  2. int empty_linklist(lkl_pnode H)
  3. {
  4.     if (H->next == NULL)
  5.         return 0;
  6.     else
  7.         return -1;
  8. }

 因为头结点的指针域存储的是下一个节点的地址，故若头结点指针域为空，则代表该链表为空。

3、获取链表对的长度

  1. int getlen_linklist(lkl_pnode H)
  2. {
  3.     int count = 0;
  4.     while (H->next)
  5.     {
  6.         H = H->next;
  7.         count++;
  8.     }
  9.  
  10.     return count;
  11. }

 在获取链表的长度时需要注意的是，头结点并不算做是有效节点；故应该从H->next即第一个节点开始计数。

4、插入

  1. //插入
  2. int insert_linklist(lkl_pnode H, int pos, linklist_data_t data)
  3. {
  4.     //判断插入位置是否合法
  5.     if (pos < 0 || pos > getlen_linklist(H))
  6.     {
  7.         printf("pos is default\n");
  8.         return -1;
  9.     }
  10.  
  11.     //找到插入位置的前一个节点的位置
  12.     while (pos--)
  13.     {
  14.         H = H->next;
  15.     }
  16.     //插入，头插
  17.     lkl_pnode new = create_linklist();
  18.     new->data = data;
  19.  
  20.     new->next = H->next;
  21.     H->next = new;
  22.  
  23.     return 0;
  24. }

此处实现的是按位置插入，核心点是使用while循环找到要插入的位置的前驱节点，然后使用头插的方式将该节点插入。

5、打印 

  1. //打印
  2. int show_linklist(lkl_pnode H)
  3. {
  4.     if (0 == empty_linklist(H))
  5.     {
  6.         printf("H is empty\n");
  7.         return -1;
  8.     }
  9.  
  10.     //遍历
  11.     while (H->next)
  12.     {
  13.         H = H->next;
  14.         printf("dat=%d ", H->data);
  15.     }
  16.     printf("\n");
  17. }

打印的思想比较简单，即遍历一遍链表，挨个打印即可

6、删除 

删除有两种方式，即按位置删除和安置删除

首先是按值删除

  1. int delete_linklist(lkl_pnode H, linklist_data_t data) //按值删除
  2. {
  3.     if (0 == empty_linklist(H))
  4.     {
  5.         printf("H is empty\n");
  6.         return -1;
  7.     }
  8.     
  9.     lkl_pnode p = H;
  10.     lkl_pnode q = H->next;
  11.     while (q)
  12.     {
  13.         if (q->data == data)
  14.         {
  15.             p->next = q->next;
  16.             free(q);
  17.             q = p->next;
  18.             continue;
  19.         }
  20.         p = q;
  21.         q = q->next;
  22.     }
  23. }

安值删除需要借助两个辅助指针一前一后，若后一个指针的数据域与要删除的值相等，则前一个指针的指针域直接指向后一个指针的指针域（ p->next = q->next;）；即断开了要删除的节点，然后释放掉该节点即完成删除。

按位置删除

  1. int delete1_linklist(lkl_pnode H, int pos)//按位置删除
  2. {
  3.     if (0 == empty_linklist(H))
  4.     {
  5.         printf("H is empty\n");
  6.         return -1;
  7.     }
  8.  
  9.     if (pos < 0 || pos >= getlen_linklist(H))
  10.     {
  11.         printf("pos is default\n");
  12.         return -1;
  13.     }
  14.     //找到要删除的前一个节点位置
  15.     while (pos--)
  16.     {
  17.         H = H->next;
  18.     }
  19.     //保存要删除的节点的位置
  20.     lkl_pnode p = H->next;
  21.     //连线
  22.     H->next = p->next;
  23.     //释放空间
  24.     free(p);
  25.     p = NULL;
  26.  
  27.     return 0;
  28. }

按位置删除比较简单，找到该位置的前驱节点，断开连接，释放空间即可。

7、查询 

同上，查询也分为按值查询和按位置查询，其实现代码如下：

  1. //查询
  2. linklist_data_t search_linklist(lkl_pnode H, int pos) //按位置查询值
  3. {
  4.  
  5.     if (0 == empty_linklist(H))
  6.     {
  7.         printf("H is empty\n");
  8.         return -1;
  9.     }
  10.  
  11.     if (pos < 0 || pos >= getlen_linklist(H))
  12.     {
  13.         printf("pos is default\n");
  14.         return -1;
  15.     }
  16.  
  17.     while (pos--)
  18.     {
  19.         H = H->next;
  20.     }
  21.     return H->next->data;
  22. }
  23. int  search1_linklist(lkl_pnode H, linklist_data_t data)//按值查位置
  24. {
  25.     if (0 == empty_linklist(H))
  26.     {
  27.         printf("H is empty\n");
  28.         return -1;
  29.     }
  30.     int pos=0;
  31.     H = H->next;
  32.     while (H)
  33.     {
  34.         if (H->data == data) 
  35.             break;    
  36.         pos++;
  37.         H = H->next;
  38.     }
  39.     return pos;
  40. }

 8、修改

修改也有两种方式，按位置修改，安置修改；

  1. //修改
  2. int change_linklist(lkl_pnode H, int pos, linklist_data_t data) //按位置修改值
  3. {
  4.     if (0 == empty_linklist(H))
  5.     {
  6.         printf("H is empty\n");
  7.         return -1;
  8.     }
  9.  
  10.     if (pos < 0 || pos >= getlen_linklist(H))
  11.     {
  12.         printf("pos is default\n");
  13.         return -1;
  14.     }
  15.  
  16.     while (pos--)
  17.     {
  18.         H = H->next;
  19.     }
  20.     H->next->data = data;
  21.  
  22.     return 0;
  23. }
  24.  
  25. int change1_linklist(lkl_pnode H, linklist_data_t old_data, linklist_data_t new_data)//按值修改
  26. {
  27.     if (0 == empty_linklist(H))
  28.     {
  29.         printf("H is empty\n");
  30.         return -1;
  31.     }
  32.     H = H->next;
  33.     while (H)
  34.     {
  35.         if (H->data == old_data)
  36.             H->data = new_data;
  37.         H = H->next;
  38.     }
  39.  
  40. }

 9、清空

  1. //清空
  2. int clean_linklist(lkl_pnode H)
  3. {
  4.     if (0 == empty_linklist(H))
  5.     {
  6.         printf("H is empty\n");
  7.         return -1;
  8.     }
  9.  
  10.     while (empty_linklist(H))
  11.     {
  12.         delete1_linklist(H, 0);
  13.     }
  14.  
  15.     return 0;
  16. }

 这里需要注意两点：一是对链表的清空，即释放除头结点以外的所有节点，故可以调用删除函数来挨个删除元素即可；二是链表清空后，其头结点还在，热然可以对齐进行插入等操作；

10、销毁

  1. //销毁                                            
  2. int destroy_linklist(lkl_pnode* H)
  3. {
  4.     if (0 == empty_linklist(*H))
  5.     {
  6.         free(*H);
  7.         *H = NULL;
  8.     }
  9.     else
  10.     {
  11.         clean_linklist(*H);
  12.         free(*H);
  13.         *H = NULL;
  14.     }
  15.  
  16.     return 0;
  17. }

对于链表的销毁，也有两点需要注意，首先是链表的销毁即释放掉链表的所有节点，包括头结点，故链表销毁后不可以再使用；其次是，对于链表的销毁，该函数需要进行地址传递，才能通过形参来改变实参，即销毁掉实参链表，否则只是对链表进行了清空，链表头结点实际还存在，要想完全释放掉链表，主函数中还需要再free一次并置空。

11、链表的逆序 

链表的逆序主要思想为将头结点与后面的节点断开，分成两个链表，然后一一取出后面节点组成的链表节点对头结点链表做头插，即可完成链表的逆序。

  1. //链表的逆序
  2. int  linklist_reverse(lkl_pnode H)
  3. {
  4.     if (0 == empty_linklist(H))
  5.     {
  6.         printf("H is empty\n");
  7.         return -1;
  8.     }
  9.     lkl_pnode  p, q;
  10.     p = q = H->next;
  11.     H->next = NULL;
  12.     while (q != NULL)
  13.     {
  14.         q = q->next;
  15.         insert_linklist(H, 0, p->data);
  16.         p = q;
  17.        
  18.     }
  19.  
  20. }

12、链表的排序

对链表进行排序的思想与逆序相似，首先也是断开头结点分成两个链表，然后一一取出后面链表的节点与头结点链表的每一个节点进行比较后插入，循环往复实现排序。

本例实现的是从小到大的排序：

  1. //链表的排序
  2. int linklist_sort(lkl_pnode H)
  3. {
  4.     if (0 == empty_linklist(H))
  5.     {
  6.         printf("H is empty\n");
  7.         return -1;
  8.     }
  9.     lkl_pnode p, q,t;
  10.     q = H->next;
  11.     H->next = NULL;
  12.     while (q != NULL)
  13.     {
  14.         p = q;
  15.         q = q->next;
  16.         t = H;
  17.         while (t)
  18.         {
  19.             if (t->next == NULL)
  20.             {
  21.                 p->next = t->next;
  22.                 t->next = p;
  23.                 break;
  24.             }
  25.             if (t->next->data >= p->data)
  26.             {
  27.                 p->next = t->next;
  28.                 t->next = p;
  29.                 break;
  30.             }
  31.             else
  32.             {
  33.                 t = t->next;
  34.             }
  35.         }
  36.     }
  37. }

总结 

以上便是对链表所有操作函数的实现，下面看一下实现效果：

  1. int main()
  2. {
  3.     lkl_pnode H = create_linklist();
  4.  
  5.     puts("-------------------insert 0-9--------------");
  6.     int i;
  7.     for (i = 0; i < 10; i++)
  8.     {
  9.         insert_linklist(H, 0, i);
  10.     }
  11.     show_linklist(H);
  12.     puts("\n");
  13.     puts("-----------------delete pos=2--------------");
  14.     delete1_linklist(H, 2);
  15.     show_linklist(H);
  16.     puts("\n");
  17.     
  18.     puts("-----------------change pos=2  data=666-----");
  19.     change_linklist(H, 2, 666);
  20.     show_linklist(H);
  21.     puts("\n");
  22.     puts("-----------------change pos=3  data=666-----");
  23.     change_linklist(H, 3, 666);
  24.     show_linklist(H);
  25.     puts("\n");
  26.     puts("-----------------change old=0  new=777-----");
  27.     change1_linklist(H, 0, 777);
  28.     show_linklist(H);
  29.     puts("\n");
  30.     puts("----------------- 排序----------------------");
  31.     linklist_sort(H);
  32.     show_linklist(H);
  33.     puts("\n");
  34.     puts("-----------------delete val=777--------------");
  35.     delete_linklist(H, 777);
  36.     show_linklist(H);
  37.     puts("\n");
  38.     puts("-----------------search pos=4 ---------------");
  39.     printf("data=%d\n", search_linklist(H, 4));
  40.     puts("\n");
  41.     puts("-----------------search val=3 ---------------");
  42.     printf("pos=%d\n", search1_linklist(H, 3));
  43.     puts("\n");
  44.     puts("-----------------change pos=2  data=888-----");
  45.     change_linklist(H, 2, 888);
  46.     show_linklist(H);
  47.     puts("\n");
  48.     puts("-----------------change pos=3  data=999-----");
  49.     change_linklist(H, 3, 999);
  50.     show_linklist(H);
  51.     puts("\n");
  52.     puts("-----------------逆序-----------------------");
  53.     linklist_reverse(H);
  54.     show_linklist(H);
  55.     puts("\n");
  56.     puts("----------------- 排序----------------------");
  57.     linklist_sort(H);
  58.     show_linklist(H);
  59.     puts("\n");
  60.     puts("-----------------clean-----------------------");
  61.     clean_linklist(H);
  62.     show_linklist(H);
  63.     puts("-----------------destroy---------------------");
  64.     destroy_linklist(&H);
  65.     printf("H=%p\n", H);
  66. }

上面是主函数的测试程序，包含了所有设计函数的使用，以下是输出结果：

 

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

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

  

闽ICP备14008679号