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

leetCode 707---单链表的创建及相关方法实现（C语言版）_mylinkedlist* obj = mylinkedlistcreate();obj是什么意思

作者：繁依Fanyi0 | 2024-04-09 23:13:21

赞

踩

mylinkedlist* obj = mylinkedlistcreate();obj是什么意思

题目描述：

使用C语言实现单链表，单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点

思考设计：

首先要确定是否设置头节点，本题使用头节点。我一直对头节点和头指针这两个东西很迷，这几天我再单独写篇文章来和大家交流一下。

  • 节点设计

单链表的节点包括数据域和指针域，代码如下：

  1. /**
  2.  * 构造节点
  3.  */
  4. typedef struct
  5. {
  6.     int val;                   //数据域，存储有我们需要使用的数据
  7.     struct MylinkedList *next; //指针域，存储有指向下一个节点的指针
  8. } MyLinkedList;

  • 方法实现

1、myLinkedListCreate()：构造函数，初始化链表

众所周知，我们使用头结点来代表整个列表。下面的obj就是头节点，可以代替整个链表。

  1. /** 
  2.  * 构造一个有头结点的空链表 
  3.  */
  4. MyLinkedList *myLinkedListCreate()
  5. {
  6.     MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList)); //在内存空间中开辟一块和节点数据结构大小一样的内存空间，构造头节点
  7.     obj->next = NULL;                                                 //头节点的指针域置空
  8.     return obj;
  9. }

2、myLinkedListGet(MyLinkedList *obj, int index)，获取链表中第 index 个节点的值。如果索引无效，则返回-1

链表中第0个节点指的是头节点后面那一个，其他的以此类推。注意index取负数、链表为空、index大于链表节点数的情况

  1. /** 
  2.  * 获取链表中第 index 个节点的值。如果索引无效，则返回-1 
  3.  */
  4. int myLinkedListGet(MyLinkedList *obj, int index)
  5. {
  6.     int counter = 0; //计数器
  7.     int value = 0;
  8.     MyLinkedList *p = obj->next; //定义一个指针，并指向头节点的下一个节点，即第0个节点
  9.     while (p && counter < index)  //当P存在而且没有遍历到第index节点时继续移动指针，直到counter=index时跳出循环；若P为空也会跳出循环，此时counter不一定等于index
  10.     {
  11.         p = p->next;
  12.         counter++;
  13.     }
  14.     if (!p || counter > index) //跳出while循环后counter<=index，若P为空说明查询节点的index大于链表节点数，返回-1；若用户输入的index是一个负数，虽然P不为空，但这种情况应该返回-1
  15.     {
  16.         return -1;
  17.     }
  18.     else
  19.     {
  20.         value = p->val;
  21.         return value;
  22.     }
  23. }

3、myLinkedListAddAtHead(MyLinkedList *obj, int val)：头插法的实现，就是在头节点和第0个节点间插入一个新节点

  1. /** 
  2.  * 头插法的实现
  3.  * 在头节点和第0个节点间插入一个新节点
  4.  */
  5. void myLinkedListAddAtHead(MyLinkedList *obj, int val)
  6. {
  7.     MyLinkedList *p = obj;                                             //将头节点赋值给指针P
  8.     MyLinkedList *head = (MyLinkedList *)malloc(sizeof(MyLinkedList)); //新建一个节点
  9.     head->val = val;                                                   //给新节点数据域赋值
  10.     head->next = p->next;                                              //让新节点指向头节点的下一个节点
  11.     p->next = head;                                                    //让头节点指向新节点完成插入
  12. }

4、myLinkedListAddAtTail(MyLinkedList *obj, int val)： 尾插法的实现，在链表最后的节点后再插入新的节点

  1. /** 
  2.  * 尾插法的实现
  3.  * 在链表最后的节点后再插入新的节点
  4. */
  5. void myLinkedListAddAtTail(MyLinkedList *obj, int val)
  6. {
  7.     MyLinkedList *tail = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  8.     tail->val = val;
  9.     tail->next = NULL; //初始化新节点，指针域需要置空
  10.     MyLinkedList *node = obj;
  11.     while (node->next) //从头节点开始遍历链表，当节点的指针域为空时跳出循环，表明找到链表尾节点
  12.     {
  13.         node = node->next;
  14.     }
  15.     node->next = tail; //新节点成为尾节点
  16. }

5、myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)：在第index节点前插入新节点，若index为负数则插入到链表头部，若index超出链表长度则不插入；这里也要注意链表为空，index越界、index为负数的情况。

  1. /** 
  2.  * 在第index节点前插入新节点，若index为负数则插入到链表头部，若index超出链表长度则不插入
  3.  */
  4. void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
  5. {
  6.     MyLinkedList *insertedNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  7.     insertedNode->val = val;
  8.     MyLinkedList *node = obj;
  9.     int counter = 0;
  10.     if (index < counter) // index为负数时插入到链表头部
  11.     {
  12.         insertedNode->next = node->next;
  13.         node->next = insertedNode;
  14.     }
  15.     while (node && counter < index) //counter等于index时，node的下标应该是index -1，这里和myLinkedListGet方法不同。差别在于当counter是0时，本方法node是头节点，但在myLinkedListGet方法中P是第0个节点
  16.     {
  17.         node = node->next;
  18.         counter++;
  19.     }
  20.     if (!node || counter > index)
  21.     {
  22.         return -1;
  23.     }
  24.     insertedNode->next = node->next;
  25.     node->next = insertedNode;
  26. }

6、myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)：若index有效的话则删除第index个节点，注意index为负数、链表为空的情况

  1. /** 
  2.  * 若index有效的话则删除第index个节点
  3.  * 删除不同于插入。插入时，涉及第index、index-1两个节点，若第index-1个节点是尾节点，虽然第index个节点不存在，但是依然能插入；
  4.  * 删除时，涉及第index-1、index、index+1三个节点，如果第index-1个节点为尾节点，则第index+1个节点即下面的temNode->next不存在，不能完成指针的赋值
  5.  * 所以在判断循环时，判断条件是 node->next，这样才能保证第index+1个节点即下面的temNode->next存在（特殊条件就是为NULL）
  6.  */
  7. void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
  8. {
  9.     MyLinkedList *node = obj;
  10.     int counter = 0;
  11.     while (node->next && counter < index) //找到第index-1 个节点，但需要保证第index+1个节点即下面的temNode->next存在（特殊条件就是为NULL）
  12.     {
  13.         node = node->next;
  14.         counter++;
  15.     }
  16.     if (!(node->next) || counter > index)
  17.     {
  18.         return -1;
  19.     }
  20.     else
  21.     {
  22.         MyLinkedList *temNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  23.         temNode = node->next;
  24.         node->next = temNode->next;
  25.         free(temNode);
  26.     }
  27. }

7、myLinkedListFree(MyLinkedList *obj)：整表删除，从头节点开始删除

  1. /**
  2.  * 整表删除
  3.  */
  4. void myLinkedListFree(MyLinkedList *obj)
  5. {
  6.     MyLinkedList *node = obj->next; //这里node指向的是头节点的下一个节点，与前面有所不同。整表删除时要将头节点以外的所有节点删除，保留头节点
  7.     MyLinkedList *temNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  8.     while (node) //判断除当前结点是否为空，不为空时删除此节点
  9.     {
  10.         temNode = node->next; //删除时要保留被删除节点的下一个节点
  11.         free(node);
  12.         node = temNode;
  13.     }
  14.     obj->next = NULL;
  15. }

8、主函数: 大家可以自己试一试，看看结果对不对。

  1. int main()
  2. {
  3.     MyLinkedList *obj = myLinkedListCreate();
  4.  
  5.     int param_1 = myLinkedListGet(obj, 0);
  6.     printf("%d\n", param_1); 
  7.  
  8.     myLinkedListAddAtHead(obj, 0);
  9.     int param_2 = myLinkedListGet(obj, 0);
  10.     printf("%d\n", param_2); 
  11.  
  12.     myLinkedListAddAtTail(obj, 1); 
  13.     int param_3 = myLinkedListGet(obj, 0);
  14.     printf("%d\n", param_3); 
  15.  
  16.     myLinkedListAddAtIndex(obj, 1, 2); 
  17.     int param_4 = myLinkedListGet(obj, 1);
  18.     printf("%d\n", param_4); 
  19.  
  20.     myLinkedListDeleteAtIndex(obj, 2); //02
  21.  
  22.     myLinkedListFree(obj);
  23.     int param_5 = myLinkedListGet(obj, 0);
  24.     printf("%d\n", param_5); 
  25. }

  • 所有代码：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /**
  5.  * 构造节点
  6.  */
  7. typedef struct
  8. {
  9.     int val;                   //数据域，存储有我们需要使用的数据
  10.     struct MylinkedList *next; //指针域，存储有指向下一个节点的指针
  11. } MyLinkedList;
  12.  
  13. /** 
  14.  * 构造一个有头结点的空链表 
  15.  */
  16. MyLinkedList *myLinkedListCreate()
  17. {
  18.     MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList)); //在内存空间中开辟一块和节点数据结构大小一样的内存空间，构造头节点
  19.     obj->next = NULL;                                                 //头节点的指针域置空
  20.     return obj;
  21. }
  22.  
  23. /** 
  24.  * 获取链表中第 index 个节点的值。如果索引无效，则返回-1 
  25.  */
  26. int myLinkedListGet(MyLinkedList *obj, int index)
  27. {
  28.     int counter = 0; //计数器
  29.     int value = 0;
  30.     MyLinkedList *p = obj->next; //定义一个指针，并指向头节点的下一个节点，即第0个节点
  31.     while (p && counter < index) //当P存在而且没有遍历到第index节点时继续移动指针，直到counter=index时跳出循环；若P为空也会跳出循环，此时counter不一定等于index
  32.     {
  33.         p = p->next;
  34.         counter++;
  35.     }
  36.     if (!p || counter > index) //跳出while循环后counter<=index，若P为空说明查询节点的index大于链表节点数，返回-1；若用户输入的index是一个负数，虽然P不为空，但这种情况应该返回-1
  37.     {
  38.         return -1;
  39.     }
  40.     else
  41.     {
  42.         value = p->val;
  43.         return value;
  44.     }
  45. }
  46.  
  47. /** 
  48.  * 头插法的实现
  49.  * 在头节点和第0个节点间插入一个新节点
  50.  */
  51. void myLinkedListAddAtHead(MyLinkedList *obj, int val)
  52. {
  53.     MyLinkedList *p = obj;                                             //将头节点赋值给指针P
  54.     MyLinkedList *head = (MyLinkedList *)malloc(sizeof(MyLinkedList)); //新建一个节点
  55.     head->val = val;                                                   //给新节点数据域赋值
  56.     head->next = p->next;                                              //让新节点指向头节点的下一个节点
  57.     p->next = head;                                                    //让头节点指向新节点完成插入
  58. }
  59.  
  60. /** 
  61.  * 尾插法的实现
  62.  * 在链表最后的节点后再插入新的节点
  63. */
  64. void myLinkedListAddAtTail(MyLinkedList *obj, int val)
  65. {
  66.     MyLinkedList *tail = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  67.     tail->val = val;
  68.     tail->next = NULL; //初始化新节点，指针域需要置空
  69.     MyLinkedList *node = obj;
  70.     while (node->next) //从头节点开始遍历链表，当节点的指针域为空时跳出循环，表明找到链表尾节点
  71.     {
  72.         node = node->next;
  73.     }
  74.     node->next = tail; //新节点成为尾节点
  75. }
  76.  
  77. /** 
  78.  * 在第index节点前插入新节点，若index为负数则插入到链表头部，若index超出链表长度则不插入
  79.  */
  80. void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val)
  81. {
  82.     MyLinkedList *insertedNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  83.     insertedNode->val = val;
  84.     MyLinkedList *node = obj;
  85.     int counter = 0;
  86.     if (index < counter) // index为负数时插入到链表头部
  87.     {
  88.         insertedNode->next = node->next;
  89.         node->next = insertedNode;
  90.     }
  91.     while (node && counter < index) //counter等于index时，node的下标应该是index -1，这里和myLinkedListGet方法不同。差别在于当counter是0时，本方法node是头节点，但在myLinkedListGet方法中P是第0个节点
  92.     {
  93.         node = node->next;
  94.         counter++;
  95.     }
  96.     if (!node || counter > index)
  97.     {
  98.         return -1;
  99.     }
  100.     insertedNode->next = node->next;
  101.     node->next = insertedNode;
  102. }
  103.  
  104. /** 
  105.  * 若index有效的话则删除第index个节点
  106.  * 删除不同于插入。插入时，涉及第index、index-1两个节点，若第index-1个节点是尾节点，虽然第index个节点不存在，但是依然能插入；
  107.  * 删除时，涉及第index-1、index、index+1三个节点，如果第index-1个节点为尾节点，则第index+1个节点即下面的temNode->next不存在，不能完成指针的赋值
  108.  * 所以在判断循环时，判断条件是 node->next，这样才能保证第index+1个节点即下面的temNode->next存在（特殊条件就是为NULL）
  109.  */
  110. void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index)
  111. {
  112.     MyLinkedList *node = obj;
  113.     int counter = 0;
  114.     while (node->next && counter < index) //找到第index-1 个节点，但需要保证第index+1个节点即下面的temNode->next存在（特殊条件就是为NULL）
  115.     {
  116.         node = node->next;
  117.         counter++;
  118.     }
  119.     if (!(node->next) || counter > index)
  120.     {
  121.         return -1;
  122.     }
  123.     else
  124.     {
  125.         MyLinkedList *temNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  126.         temNode = node->next;
  127.         node->next = temNode->next;
  128.         free(temNode);
  129.     }
  130. }
  131.  
  132. /**
  133.  * 整表删除
  134.  */
  135. void myLinkedListFree(MyLinkedList *obj)
  136. {
  137.     MyLinkedList *node = obj->next; //这里node指向的是头节点的下一个节点，与前面有所不同。整表删除时要将头节点以外的所有节点删除，保留头节点
  138.     MyLinkedList *temNode = (MyLinkedList *)malloc(sizeof(MyLinkedList));
  139.     while (node) //判断除当前结点是否为空，不为空时删除此节点
  140.     {
  141.         temNode = node->next; //删除时要保留被删除节点的下一个节点
  142.         free(node);
  143.         node = temNode;
  144.     }
  145.     obj->next = NULL;
  146. }
  147.  
  148. /**
  149.  * Your MyLinkedList struct will be instantiated and called as such:
  150.  * MyLinkedList* obj = myLinkedListCreate();
  151.  * int param_1 = myLinkedListGet(obj, index);
  152.  
  153.  * myLinkedListAddAtHead(obj, val);
  154.  
  155.  * myLinkedListAddAtTail(obj, val);
  156.  
  157.  * myLinkedListAddAtIndex(obj, index, val);
  158.  
  159.  * myLinkedListDeleteAtIndex(obj, index);
  160.  
  161.  * myLinkedListFree(obj);
  162. */
  163. int main()
  164. {
  165.     MyLinkedList *obj = myLinkedListCreate();
  166.  
  167.     int param_1 = myLinkedListGet(obj, 0);
  168.     printf("%d\n", param_1); //-1
  169.  
  170.     myLinkedListAddAtHead(obj, 0);
  171.     int param_2 = myLinkedListGet(obj, 0);
  172.     printf("%d\n", param_2); //0
  173.  
  174.     myLinkedListAddAtTail(obj, 1); // 0 1
  175.     int param_3 = myLinkedListGet(obj, 0);
  176.     printf("%d\n", param_3); //0
  177.  
  178.     myLinkedListAddAtIndex(obj, 1, 2); //021
  179.     int param_4 = myLinkedListGet(obj, 1);
  180.     printf("%d\n", param_4); //2
  181.  
  182.     myLinkedListDeleteAtIndex(obj, 2); //02
  183.  
  184.     myLinkedListFree(obj);
  185.     int param_5 = myLinkedListGet(obj, 0);
  186.     printf("%d\n", param_5); //-1
  187. }

 

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

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

  

闽ICP备14008679号