吃顿外卖的时间带你解决单链表问题

来源：cnblogs　　作者：小杜加油　　时间：2022/1/17 11:10:22　　对本文有异议

一.链表的定义

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的,相当于一个一个的结点链接在一起就构成了链表.如下图所示.

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

二.链表的实现

1,无头+单向+非循环链表增删查改实现

其具体思路如下图所示

这样具体的思路就有了,然后是具体的程序代码

先是头文件

 1 #include<stdio.h>
 2 #include <stdlib.h>
 3 #include<malloc.h>
 4 #include<assert.h>
 5 
 6 typedef int SLTDataType;
 7 
 8 typedef struct SListNode
 9 {
10     SLTDataType data;
11     struct SListNode* next;
12 }SLTNode;
13 
14 // 单向+不带头+不循环
15 void SListPrint(SLTNode* plist); //打印链表 
16 SLTNode* BuySLTNode(SLTDataType x);//创建节点 
17 void SListPushBack(SLTNode** pplist, SLTDataType x); //尾插 
18 void SListPushFront(SLTNode** pplist, SLTDataType x);// 头插 
19 
20 void SListPopBack(SLTNode** pplist); //尾删 
21 void SListPopFront(SLTNode** pplist);//头删 
22 
23 SLTNode* SListFind(SLTNode* plist, SLTDataType x);//查找 
24 void  SListInsertAfter(SLTNode* pos,SLTDataType x);//pos后插入 
25 void  SListInsertBefore(SLTNode**pplist,SLTNode* pos,SLTDataType x);//pos前插入 
26 void SListEraseAfter(SLTNode* pos);//删除指定数据

函数的具体实现

  1 #include"SList.h"
  2 void SListPrint(SLTNode* plist)
  3 {
  4     SLTNode* cur=plist;
  5     while(cur!=NULL)
  6     {
  7         printf("%d->",cur->data);
  8         cur=cur->next;
  9     }
 10     printf("NULL\n");    
 11 } 
 12 SLTNode* BuySLTNode(SLTDataType x)
 13 {
 14     SLTNode *node=(SLTNode*)malloc(sizeof(SLTNode));
 15     node->data=x;
 16     node->next=NULL;
 17     return node;
 18 }
 19 void SListPushBack(SLTNode** pplist, SLTDataType x) //尾插
 20 {
 21     SLTNode* newnode = BuySLTNode(x);
 22     if(*pplist==NULL)
 23     {
 24     *pplist=newnode ;
 25     } 
 26     else 
 27     {
 28       SLTNode*tail=*pplist;
 29       while(tail->next!=NULL)
 30       {
 31           tail=tail->next;
 32       }
 33         tail->next=newnode;
 34     } 
 35 } 
 36 void SListPushFront(SLTNode** pplist, SLTDataType x) //头插 
 37 {
 38         SLTNode* newnode = BuySLTNode(x);
 39         newnode->next=*pplist;
 40         *pplist=newnode;        
 41 }
 42 void SListPopBack(SLTNode** pplist)//尾删
 43 {
 44     if(*pplist==NULL)
 45     {
 46         return ;
 47     }
 48     else if((*pplist)->next==NULL)
 49     {
 50         free(*pplist);
 51         *pplist=NULL; 
 52     }
 53     else 
 54     {
 55          SLTNode* prev=NULL;
 56          SLTNode*tail=*pplist;
 57          while(tail->next!=NULL)
 58          {
 59              prev=tail;
 60              tail=tail->next;
 61          }
 62         free(tail);
 63         tail->next=NULL;
 64         prev->next=NULL;
 65     }
 66 } 
 67 void SListPopFront(SLTNode** pplist)//头删 
 68 {
 69      if(*pplist==NULL)
 70      {
 71        return ;
 72      }
 73      else 
 74      {
 75          SLTNode* node = *pplist; 
 76         *pplist = node->next;
 77          free(node);
 78      }
 79 } 
 80 SLTNode* SListFind(SLTNode* plist, SLTDataType x)// 查找节点 
 81 {
 82     SLTNode* cur = plist;
 83     while(cur)
 84     {
 85         if(cur->data==x)
 86         {
 87             return cur;
 88         }
 89         cur=cur->next;
 90     }
 91     return NULL;
 92 }
 93 void  SListInsertAfter(SLTNode* pos,SLTDataType x) //插入节点到指定位置的后面 
 94 {
 95     assert(pos);
 96     SLTNode* newnode = BuySLTNode(x);
 97    newnode->next=pos->next;
 98    pos->next=newnode;
 99 }
100 void  SListInsertBefore(SLTNode**pplist,SLTNode* pos,SLTDataType x)
101 {
102     assert(pos);
103     SLTNode* newnode = BuySLTNode(x);
104     if(pos==*pplist)//认为是头插 
105     {
106         newnode->next=pos;
107          *pplist=newnode;
108     }
109     else
110     {
111      SLTNode* prev = NULL;
112      SLTNode* cur = *pplist;
113      while(cur!=pos)
114      {
115          prev=cur;
116          cur=cur->next;
117      }    
118      prev->next=newnode;
119      newnode->next=pos;
120     }
121 } 
122 void SListEraseAfter(SLTNode* pos)//指定某一节点后续位置 
123 {
124     assert(pos);
125     if(pos->next==NULL)
126     {
127         return ;
128     } 
129     else 
130     {
131         SLTNode*next=pos->next;
132         pos->next=next->next;
133         free(next);    
134     }
135 }

主函数调用

#include"SList.h"
void Test()
{
    SLTNode* plist=NULL;
    SListPushBack(&plist,2);
    SListPushBack(&plist,3);
    SListPushBack(&plist,4);
    SListPushBack(&plist,5);
    SListPushFront(&plist,6);
    SListPrint(plist);
    SListPopBack(&plist);
    SListPrint(plist);
    SListPopFront(&plist);
    SLTNode* pos = SListFind(plist, 3);
    SListInsertAfter(pos,40);
    SListPrint(plist);
    SListInsertBefore(&plist,pos,300);
    SListPrint(plist);
    SListEraseAfter(pos); 
    SListPrint(plist);
}
int main()
{
    Test();
    return 0;
}