链表的基础操作（c语言）

概述：

        链表的现状背景是指链表在当前的使用环境中的应用和状况。链表在实际开发中有广泛的应用，特别是在需要频繁插入和删除元素的场景中，链表的动态性能够发挥出很大的优势。链表也有多种变种，如双向链表、循环链表等，根据不同的需求选择不同类型的链表。除了常见的单链表之外，还有其他一些特殊的链表结构，如带头结点的链表和虚拟链表。带头结点的链表在链表的第一个节点之前增加一个特殊节点作为头结点，可以简化链表的操作和处理边界情况。虚拟链表是一种特殊的链表，它通过使用虚拟节点来简化链表的实现和操作。
      

一、单链表的概念

               定义：链表是一种数据结构，用于存储数据元素的集合。它由一系列节点组成，每个节点都包含数据和指向下一个节点的引用。每个节点都可以通过这个引用链接到下一个节点，从而形成一个链式结构。链表中的数据元素可以在任意位置进行插入和删除操作，相比于数组，链表具有更灵活的动态性质。

           一个是存储数据元素的数据域

     图1 单向链表

        把链表想象成一辆火车，每个车厢代表链表中的一个节点，车厢中装有货物，就像链表中的数据域一样，而连接车厢的连接处就像链表中的指针一样，指向下一个车厢。        

 链表的构成：

        链表由一个个节点构成，通常用typedef定义一个节点，后面调用起来非常方便。

        列如：定义一个学生的信息结构体，结构体里边包含学生的学号，分数，姓名。

    链表节点分为两个域

  数据域：存放各种实际的数据，如：num、score，score等

链表的操作:

        链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的操作包括插入、删除、查找、反转等。

 双向链表

        每一个结点由一个数据域和两个指针域组成的，数据域是用来存储数据，两个指针域是用来指向上一个结点和下一个结点
头结点没有指向上一个结点也不存储数据
尾结点没有指向一下一个结点但是它指向上一个节点和数据

图4双向链表

链表与数组的对比

链表和数组都是数据结构，用于存储和操作数据。它们在以下几个方面有所不同：

综上所述，数组适合随机访问和已知大小的情况，插入和删除操作较少的情况；链表适合插入和删除操作频繁的情况，对访问元素的顺序要求较低的情况。

二、链表的创建

1. 第一步：创建一个节点
2. 第二步：创建第二个节点，将其放在第一个节点的后面（第一的节点的指针域保存第二个节点的地址）
3. 第三步：再次创建节点，找到原本链表中的最后一个节点，接着讲最后一个节点的指针域保存新节点的地址，以此内推。

   #include <stdio.h>
   #include <stdlib.h>
   
   #include <malloc.h>
   //定义结点结构体
   typedef struct student
   {
       //数据域
       int num;        //学号
       int score;      //分数
       char name[20];  //姓名
       //指针域
       struct student *next;
   }STU;    //每个学生的个人信息，数据域里面还可以写班级，电话等
    
   void link_creat_head(STU **p_head,STU *p_new)     //链表的形成
   {
       STU *p_mov = *p_head;
       if(*p_head == NULL)    //当第一次加入链表为空时，head执行p_new
       {
           *p_head = p_new;
           p_new->next=NULL;
       }
       else //第二次及以后加入链表
       {
           while(p_mov->next!=NULL)
           {
               p_mov=p_mov->next;    //找到原有链表的最后一个节点
           }
           p_mov->next = p_new;    //将新申请的节点加入链表
           p_new->next = NULL;    //尾结点为空
       }
   }
    
   int main()
   {
       STU *head = NULL,*p_new = NULL;
       int num,i;
       printf("请输入链表初始个数:\n");
       scanf("%d",&num);
       for(i = 0; i < num;i++)   
       {
           p_new = (STU*)malloc(sizeof(STU));//申请一个新节点
           printf("请输入学号、分数、名字:\n"); //给新节点赋值
           scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
   
           link_creat_head(&head,p_new);    //将新节点加入链表
       }
   }

三、链表的打印输出

1. 第一步：输出第一个节点的数据域，输出完毕后，让指针保存后一个节点的地址
2.  第二步：输出移动地址对应的节点的数据域，输出完毕后，指针继续后移 
3.  第三步：以此类推，直到节点的指针域为NULL

#include <stdio.h>
#include <stdlib.h>
//定义结点结构体
typedef struct student
{
    //数据域
    int num;		//学号
    int score;      //分数
    char name[20];  //姓名
    //指针域
    struct student *next;
}STU;
 
//链表的遍历
void link_print(STU *head)   //链表的打印输出
{
    STU *p_mov;
    //定义新的指针保存链表的首地址，防止使用head改变原本链表
    p_mov = head;
    //当指针保存最后一个结点的指针域为NULL时，循环结束
    while(p_mov!=NULL)
    {
        //先打印当前指针保存结点的指针域
        printf("num=%d score=%d name:%s\n",p_mov->num,\
               p_mov->score,p_mov->name);
 
        //指针后移，保存下一个结点的地址
        p_mov = p_mov->next;
    }
}
int main()
{
    STU *head = NULL,*p_new = NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);
    for(i = 0; i < num;i++)
    {
        p_new = (STU*)malloc(sizeof(STU));//申请一个新节点
        printf("请输入学号、分数、名字:\n"); //给新节点赋值
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
 
        link_creat_head(&head,p_new);	//将新节点加入链表
        
    }
	link_print(head);
	
}

四、链表的删除

#include <stdio.h>
#include <stdlib.h>
//定义结点结构体
typedef struct student
{
    //数据域
    int num;		//学号
    int score;      //分数
    char name[20];  //姓名
    //指针域
    struct student *next;
}STU;
//链表的释放
 void link_free(STU **p_head)  //链表的删除
 {
   //定义一个指针变量保存头结点的地址
   STU *pb=*p_head;
 
  while(*p_head!=NULL)
  {
   //先保存p_head指向的结点的地址
   pb=*p_head;
   //p_head保存下一个结点地址
   *p_head=(*p_head)->next; 
   //释放结点并防止野指针
   free(pb);
   pb = NULL;
  }
 }
int main()
{
    STU *head = NULL,*p_new = NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);
    for(i = 0; i < num;i++)
    {
        p_new = (STU*)malloc(sizeof(STU));//申请一个新节点
        printf("请输入学号、分数、名字:\n"); //给新节点赋值
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
 
        link_creat_head(&head,p_new);	//将新节点加入链表
        
    }
	link_free(head);
	
}

 五、链表节点的查找

        先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下 一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在

#include <stdio.h>
#include <stdlib.h>
//定义结点结构体
typedef struct student
{
    //数据域
    int num;		//学号
    int score;      //分数
    char name[20];  //姓名
    //指针域
    struct student *next;
}STU;
//链表的查找
//按照学号查找
STU * link_search_num(STU *head,int num)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov=head;
    //当没有到达最后一个结点的指针域时循环继续
    while(p_mov!=NULL)
    {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(p_mov->num == num)//找到了
        {
            return p_mov;
        }
        //如果没有找到，则继续对比下一个结点的指针域
        p_mov=p_mov->next;
    }
 
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}
 
//按照姓名查找
STU * link_search_name(STU *head,char *name)
{
    STU *p_mov;
    p_mov=head;
    while(p_mov!=NULL)
    {
        if(strcmp(p_mov->name,name)==0)//找到了
        {
            return p_mov;
        }
        p_mov=p_mov->next;
    }
    return NULL;//没有找到
}
int main()
{
    STU *head = NULL,*p_new = NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);
    for(i = 0; i < num;i++)
    {
        p_new = (STU*)malloc(sizeof(STU));//申请一个新节点
        printf("请输入学号、分数、名字:\n"); //给新节点赋值
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
 
        link_creat_head(&head,p_new);	//将新节点加入链表
        
    }
	link_print(head);
	printf("成绩为%d,名字为%s",link_search_num(head,1)->score,link_search_name(head,"cpy")->name);
}

六、链表节点的删除

//链表结点的删除
void link_delete_num(STU **p_head,int num)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head == NULL)//链表为空，不用删
    {
        printf("链表为空，没有您要删的节点");\
        return ;
    }
    while(pb->num != num && pb->next !=NULL)//循环找，要删除的节点
    {
        pf=pb;
        pb=pb->next;
    }
    if(pb->num == num)//找到了一个节点的num和num相同
    {
        if(pb == *p_head)//要删除的节点是头节点
        {
            //让保存头结点的指针保存后一个结点的地址
            *p_head = pb->next;
        }
        else
        {
            //前一个结点的指针域保存要删除的后一个结点的地址
            pf->next = pb->next;
        }
 
        //释放空间
        free(pb);
        pb = NULL;
    }
    else//没有找到
    {
        printf("没有您要删除的节点\n");
    }
}

七、链表中插入一个节点

链表中插入一个结点，按照原本链表的顺序插入，找到合适的位置

 情况（按照从小到大）：

      如果链表没有结点，则新插入的就是第一个结点。

      如果新插入的结点的数值最小，则作为头结点。

      如果新插入的结点的数值在中间位置，则找到前一个，然后插入到他们中间。

      如果新插入的结点的数值最大，则插入到最后。

//链表的插入：按照学号的顺序插入
void link_insert_num(STU **p_head,STU *p_new)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head ==NULL)// 链表为空链表
    {
        *p_head = p_new;
        p_new->next=NULL;
        return ;
    }
    while((p_new->num >= pb->num)  && (pb->next !=NULL) )
    {
        pf=pb;
        pb=pb->next;
    }
 
    if(p_new->num < pb->num)//找到一个节点的num比新来的节点num大，插在pb的前面
    {
        if(pb== *p_head)//找到的节点是头节点，插在最前面
        {
            p_new->next= *p_head;
            *p_head =p_new;
        }
        else
        {
            pf->next=p_new;
            p_new->next = pb;
        }
    }
    else//没有找到pb的num比p_new->num大的节点，插在最后
    {
        pb->next =p_new;
        p_new->next =NULL;
    }
}