数据结构单链表1（C语言）

媒介：

        前面说到了顺序表，顺序表的特点是存储是按顺序存储，只要能找到顺序表中的任意一个元素，其他元素就可以顺遂找到。
        当然顺序表也是有一定的缺陷，使用顺序表存储数据，开发空间的大小不好掌控，一样平常取每次开上一次的二倍比力合理一点，但是仍有空间浪费的情况。其次在顺序表中举行头插，头删都需要挪动数据，时间复杂度为O(n);
        在此引出了链表，链表可以补充顺序表的缺陷，但是自身也是有缺陷，接下来进入链表的解说说明。
链表：

   概念：
  链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接序次实现的 。
  链表的分类：

   
1、带头大概不带头
  

  
  2、双向大概单向
  

  
  3、循环大概非循环
  

  常见的链表：

   1、无头非循环单向链表
  
  2、带头非循环单向链表
  
  3、无头循环单向链表
  
  4、带头双向循环链表 
  无头非循环单向链表的组成：

           1、自己的值，int（char,long,short,...）val;
          2、结构体指针（连接下一个结构体），struct ListNode*next;
  针对这两部分可以通过画图来说明一下他们的作用。
   一个结构体中有这两部分组成：
  

    多个结构体就是如许：
  
  注意：
  1、前一个结构体中需要存放下一个结构体的地址，便于查找下一个结构体。
  2、最末尾的结构体中需要存放一个空指针（不能忘记）
  
  

 
  无头非循环单向链表的实现：

注：我们还是接纳三文件的方式完成链表。
界说结构体：

界说结构体需要在SList.h的头文件中完成。

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<assert.h>
5. #define SLNDataType int
6. typedef struct SListNode
7. {
8.         SLNDataType val;
9.         struct SListNode* next;
10. }SListNode;

复制代码

        注：由于不确定结构体中存储的值的类型，这里将接纳#define界说的方式，假如类型不同，可以直接通过修改SLNDataType int来举行全局的修改。
 动态申请一个节点：

        写一个函数SListNode* BuySListNode(SLTDateType x)，每次需要申请空间，可以直接调用该函数。（在SList.c中界说函数）

1. #include"SList.h"
2. SListNode* BuySListNode(SLNDataType x)
3. {
4.         SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
5.         if (tmp == NULL)
6.         {
7.                 perror("BuySlListNode malloc::");
8.                 exit(-1);
9.         }
10.         tmp->next = NULL;
11.         tmp->val = x;
12.     return tmp;
13. }

复制代码

   单链表的打印：

        写一个函数void SListPrint(SListNode* plist)实现链表的打印。
   方法：
  1、需要注意一个无头循环单链表的末尾是指向NULL的指针。
  2、如何让指针往后走，那就要抓住*next，也就是让head = head->next。

1. void SListPrint(SListNode* plist)
2. {
3.         while (plist)
4.         {
5.                 printf("%d->", plist->val);
6.                 plist = plist->next;
7.         }
8.         printf("NULL");
9.         printf("\n");
10. }

复制代码

单链表的尾插：

        写一个函数void SListPushBack(SListNode** pplist, SLNDataType x)，可以实现单链表的尾插。
      注意：
  在找尾的时间需要注意不要用原来的指针找，要让头指针保持不动！

1. void SListPushBack(SListNode** pplist, SLNDataType x)
2. {
3.         SListNode* cur = BuySListNode(x);
4.         SListNode* tmp = *pplist;
5.         if (*pplist == NULL)
6.         {
7.                 *pplist = cur;
8.         }
9.         else
10.         {
11.                 //找尾
12.                 while (tmp->next)
13.                 {
14.                         tmp = tmp->next;
15.                 }
16.                 tmp->next = cur;
17.         }
18. }

复制代码

大家可以先想一想，
   这里为什么要用二级指针？
  而且为什么要用 if 分情况讨论？
  
解答第一个标题我们可以从主函数出发：
要实现尾插，有两种传参方式，我们可以看看
第一种：界说一个函数体指针，然后将函数体指针的值直接传进去。

1. void test1()
2. {
3.         SListNode* head = NULL;
4.         SListPushBack(head,3);
5. }

复制代码

第二种：界说一个函数体指针，然后将函数体指针的地址传进进去。

1. void test1()
2. {
3.         SListNode* head = NULL;
4.         SListPushBack(&head,3);
5. }

复制代码

这两种有什么区别：
第一种：

        此时假如我改phead的指向，head的指向是不会改变的，此时phead内里的地址，只不过是head的一份暂时拷贝。
第二种：

        此时假如我首先解引用*phead，就相当于找到了head，然后再举行指向的修改，就相当于修改head的指向。

   当然，假如有人问，我就是搞不懂，也不行传二级指针，这时间就需要接触到带头非循环单链表。
  也就是带哨兵位的，大概样子就是如许。
  

          相当于第一个头内里不存有效值，只存储第二个结构体的地址。也就是说头节点自己的地址不可能为NULL，他一定会存放第二个结点的地址，也就是不论如何头节点一定在。
          这时间，假如我传参的时间，传入的就是头结点的地址，这个标题就可以用一级指针办理：
代码如下：

1. void test1()
2. {
3.         SListNode* head = (SListNode*)malloc(sizeof(SListNode));//开辟头节点
4.         head->next = NULL;
5.         SListPushBack(head,3);
6. }

复制代码

        当然假如选择如许去做，那么所有的函数需要改变一下，也就是第一个有效节点就会变为
phead->next !!!
单链表的头插：

        写一个函数void SListPushFront(SListNode** pplist, SLTDateType x)，实现单链表的头插。
需要注意也有两种情况：
第一种情况：

第二种情况：

1. void SListPushFront(SListNode** pplist, SLNDataType x)
2. {
3.         SListNode* cur = BuySListNode(x);
4.         if (*pplist == NULL)
5.         {
6.                 *pplist = cur;
7.         }
8.         else
9.         {
10.                 SListNode* tmp = (*pplist)->next;
11.                 *pplist = cur;
12.                 cur->next = tmp;
13.         }
14. }

复制代码

单链表的尾删：

        写一个函数void SListPopBack(SListNode** pplist)，实现链表的尾删。
   注意：
1、假如是一个空链表就不需要删除！
  2、需要找到尾的前一个

1. void SListPopBack(SListNode** pplist)
2. {
3.         assert(pplist);
4.         assert(*pplist);
5.         SListNode* cur = *pplist;
6.         //找尾的前一个
7.         while (cur->next->next)
8.         {
9.                 cur = cur->next;
10.         }
11.         free(cur->next);
12.         cur->next = NULL;
13. }

复制代码

单链表头删

        写一个函数void SListPopFront(SListNode** pplist)，实现单链表的头删。
注意：
在free之前一定要先生存一份(*pplist)->next。

1. void SListPopFront(SListNode** pplist)
2. {
3.         assert(pplist);
4.         assert(*pplist);
5.         SListNode* tmp = (*pplist)->next;
6.         free(*pplist);
7.         (*pplist) = tmp;
8. }

复制代码

单链表查找

        写一个函数SListNode* SListFind(SListNode* plist, SLTDateType x)，实现单链表的查找。

1. SListNode* SListFind(SListNode* plist, SLNDataType x)
2. {
3.         assert(plist);
4.         while (plist)
5.         {
6.                 if (plist->val == x)
7.                 {
8.                         return plist;
9.                 }
10.                 plist = plist->next;
11.         }
12.         return NULL;
13. }

复制代码

单链表的任意位置插入：

        写函数void SListInsertAfter(SListNode* pos, SLTDateType x)，实现在任意位置插入。
   注：
  1、SListInsertAfter函数只能在选定位置的背面插入。
  2、SListInsertAfter函数需要配合链表的查找功能一起使用

1. void SListInsertAfter(SListNode* pos, SLNDataType x)
2. {
3.         assert(pos);
4.         SListNode* tmp = pos->next;
5.         SListNode* cur = BuySListNode(x);
6.         pos->next = cur;
7.         cur->next = tmp;
8. }

复制代码

        写作实属不易，可否点赞再走

 
如有哪里理解有误，希望大家多多指点！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。