
typedef struct point
{
   int date;
    struct point*next;
} *Link;
 
Link p=head->next; //工作指针                                  
 
while(p!=NULL)
 
{
 
(操作语句）
 
p=p->next;
 
}

2.求元素个数

第二，求元素个数，其实相比于一差不多，就是在一的基础上加了个计数的。


typedef struct point
{
   int date;
    struct point*next;
} *Link;
int count=0;
 
Link p=head->next; //工作指针                                  
 
while(p!=NULL)
 
{
 
   p=p->next;
 
   count++;
 
}
printf("%d\n",count);

3.查找

第三，查找，也是与前面的差不多。


typedef struct point
{
   int date;
    struct point*next;
} *Link;
 
Link p=head->next; //工作指针                                  
 
while(p!=NULL)
 
{
 
    if(p->date==x)//x为要查找的数
   {
    printf("%d\n",p->date);
    return;
   }
 
    p=p->next;
 
}
printf("false\n");

4.插入

第四，接着就是非常重要的插入操作了。

比方说在ai-1，ai间插入一个数


typedef struct point
{
    int date;
    struct point*next;
}Node, *Link;
 
//假设链表已经创建好了
 
Link p=head->next;
 
int count=0;
 
while(p!=NULL&&count<i-1)
 
{
 
    p=p->next;
 
    count++;
 
}
 
if(p==NULL)
 
{
 
   printf("false\n");
 
   return;
 
}
 
Link node=(Link)malloc(sizeof(Node));//用malloc函数须引用头文件#include<stdlib>
 
node->date=x;//x为要插入的数
 
node->next=p->next;
 
p->next=node;

好了，之前讲过的操作都是建立在链表已经存在了的情况了，那么重点来了，如何创造一个链表呢。

5.创建链表（重要）

法一：头插法

顾名思义就是把待插入节点插在头结点的后面。

下面是将一个数组转换成链表来输出。


#include<stdio.h>
#include<stdlib.h>
typedef struct point
{
    int date;
    struct point *next;
}Node,*Link;
int a[10]={35,12,24,33,42};
int main()
{
   //头插法
   //创建头结点
   Link head=(Link)malloc(sizeof(Node));
   head->next=NULL;
   //创建后续节点
   for(int i=0;i<5;i++)
   {
       Link node=(Link)malloc(sizeof(Node));
       node->next=head->next;
       node->date=a[i];
       head->next=node;//链接
   }
   Link p=head->next;
   while(p!=NULL)
   {
       printf("%d ",p->date);
       p=p->next;
   }
    return 0;
 
}

可以看出头插法中元素的顺序是倒过来的。

法二：尾插法

顾名思义就是将待插入节点插在终端节点的后面

我们继续将一个数组转换成链表来输出


#include<stdio.h>
#include<stdlib.h>
int a[10]={35,12,24,33,42};
typedef struct point
{
      int date;
      struct point *next;
}Node,*Link;
int main()
{
    Link head=(Link)malloc(sizeof(Node));
    head->next=NULL;
    Link rear=head;//rear为尾指针，head为头指针
    for(int i=0;i<5;i++)
    {
        Link node=(Link)malloc(sizeof(Node));
        node->date=a[i];
        node->next=NULL;//建议定义完一个指针后立马初始化，特别是在这里非常重要
        rear->next=node;//连接
        rear=node;
    }
    Link p=head->next;
   while(p!=NULL)
   {
       printf("%d ",p->date);
       p=p->next;
   }
    return 0;
}

可以看出尾插法中元素的顺序是正确的。

6.删除（重要，易错）

第六，删除本身很简单，这里设p指向要删除的节点，q指向p的前驱节点。


q->next=p->next;
 
free(p);

而这里需要注意的是如何将指针移动到合适的位置。

思路：如果发现p所指向的结点date值不是要找的x,则p,q同时后移，保证p,q指针一前一后；一旦找到，则执行删除操作。

比如说我现在删除数组a里的33


#include<stdio.h>
#include<stdlib.h>
int a[10]={35,12,24,33,42};
typedef struct point
{
      int date;
      struct point *next;
}Node,*Link;
int main()
{
    Link head=(Link)malloc(sizeof(Node));
    head->next=NULL;
    Link rear=head;//rear为尾指针，head为头指针
    for(int i=0;i<5;i++)
    {
        Link node=(Link)malloc(sizeof(Node));
        node->date=a[i];
        node->next=NULL;//建议定义完一个指针后立马初始化，特别是在这里非常重要
        rear->next=node;
        rear=node;
    }
    Link p=head->next;
    Link q=head;//p在前,q在后,两者皆为工作指针
    while(p!=NULL)
    {
        if(p->date==33)
        {
            q->next=p->next;
            free(p);
           break;
        }
        else
        {
            q=p;
            p=p->next;
 
        }
    }
    if(p==NULL)
    {
        printf("该元素不存在\n");
    }
    Link l=head->next;
    while(l!=NULL)
    {
        printf("%d ",l->date);
        l=l->next;
    }
    return 0;
}

若为空表，则应满足head==NULL||head->next==NULL;

易错点

如果建立的是单向链表，当被删除的节点是尾结点时，在free之前应该将前驱指针q 赋给尾指针rear（即将尾指针前移），否则之后的插入操作会出错！
如果建的是双向链表，建议同时创建虚拟头结点和虚拟尾结点，这样在移除元素时可以避免处理很多特殊情况（如果只采用虚拟头结点，那么删除尾节点时，也要将尾指针前移，并且如果删的是最后一个元素，还要特判：if(p.next!=null)p.next.prev = p;）。

事实上我也建议创建单向链表的时候同时创建虚拟尾结点（如果有删除操作的话），当然一般用不上，因为在刷题的时候特别是力扣这种核心代码模式时，返回答案之前还需要把虚拟尾结点去掉，可能有点麻烦。如果是ACM模式倒是可以自己控制。

修改如下：


    Link p=head->next;
    Link q=head;//p在前,q在后,两者皆为工作指针
    while(p!=NULL)
    {
        if(p->date==33)
        {
            q->next=p->next;
            if (p->next == NULL)rear = q;//非常容易错！！！
            free(p);
            break;
        }
        else
        {
            q=p;
            p=p->next;
 
        }
    }

7.释放

第七，单链表的释放，即将单链表中所有结点的存储空间释放。这个过程中要特别注意，你需要保证未处理的部分不断开。


Link q=head;
 
head=head->next;
 
free(q);

8.排序

第八，链表的排序，这里是用的选择排序。核心是只交换数据域，不交换节点连接指向。


    Link p=head->next;
    Link q;
    int temp;
    //运用选择排序，只交换数据域，不交换节点连接指向
    while(p!=NULL)
    {
        q=p->next;
        while(q!=NULL)
        {
            if(p->date>q->date)
            {
                temp=p->date;
                p->date=q->date;
                q->date=temp;
            }
            q=q->next;//易漏！！！
        }
        p=p->next;
    }

综上便是全部内容了，这篇博客花费了我许多时间与精力，因为我也是个新手，如果说你看完后觉得有帮助，不妨给我点个赞。如果内容有错误，也烦请在评论区里留言，谢谢。

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