C语言-链表

1. 链表结构介绍

在前面章节已经学习了数组的使用，数组的空间是连续空间，数组的大小恒定的，在很多动态数据存储的应用场景下，使用不方便；而这篇文章介绍的链表结构，支持动态增加节点，释放节点，比较适合存储动态数据的应用场景，而且链表的空间是存储在堆上面的，可以动态分配，释放。从效率上来讲，数组的空间是连续的，查询、读取数据数组占优势；链表的优势在于节点可以动态增加、动态删除，删除支持任意位置的节点删除。

特点:

1. 数组的空间是连续的，可以直接通过[]下标访问。

2. 链表的节点是不连续的，需要通过每个节点的指针，来找到上一个节点或者下一个节点的地址。

   链表的每个节点就是一个结构体变量，节点里有一个或者两个指针，可以保存上一个节点和下一个节点的地址，方便遍历链表，删除、插入节点时定位位置。

2. 案例: 单向链表的创建与使用

下面例子采用函数封装的形式编写，每个功能都使用子函数实现。

实现的功能如下:

1. 初始化链表头
2. 插入节点的函数(链表任意位置插入，链表尾插入)
3. 删除节点的函数（链表任意位置删除、链表尾删除）
4. 遍历链表，输出链表里的所有信息

#include <stdio.h>
#include <stdlib.h>

//定义链表节点的结构体
struct app
{
    int a;
    struct app *next; //能保存结构体的地址
};

struct app *list_head=NULL;  //链表的头指针

void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);

int main()
{
    //1. 初始化链表头
    list_head=list_HeadInit(list_head);
    //2. 在链表尾插入数据
    list_add(10,list_head);
    list_add(11,list_head);
    list_add(12,list_head);
    list_add(13,list_head);
    //3. 删除节点
    list_del(11,list_head);
    //4. 输出链接节点里的数据
    list_print(list_head);
    return 0;
}

/*
函数功能: 初始化链表头--给链表头申请空间
*/
struct app *list_HeadInit(struct app *head)
{
    if(head==NULL) //没有空间
    {
        //1. 申请链表头空间
        head=malloc(sizeof(struct app));
        //2. 初始化链表头
        head->next=NULL;
    }
    return head;
}

/*
函数功能: 在链表尾插入数据
int a  插入的数据值
struct app *head  链表头
*/
void list_add(int a,struct app *head)
{
    struct app *new_p=NULL;
    struct app *next_p=head;
    struct app *tmp_p; //保存上一个节点的地址
    //1.申请空间并给空间成员赋值
    new_p=malloc(sizeof(struct app));
    new_p->a=a;
    new_p->next=NULL;

    //2. 找到链表尾
    while(next_p!=NULL)
    {
        tmp_p=next_p;
        next_p=next_p->next; //指针指向下一个节点
    }

    //3. 插入新节点--链接结尾
    tmp_p->next=new_p;
}

/*
函数功能: 遍历输出链接里的所有数据
*/
void list_print(struct app *head)
{
    struct app *next_p=head;
    int cnt=0;
    if(head!=NULL)
    {
        while(next_p->next!=NULL)
        {
            next_p=next_p->next;
            printf("链表节点[%d]:a=%d\n",cnt++,next_p->a);
        }
    }
}

/*
函数功能:链表的删除－－按照指定的数据删除
*/
void list_del(int a,struct app *head)
{
    struct app *next_p=head;
    struct app *tmp_p; //保存上一个节点的地址
    //1. 找到要删除的链表
    if(next_p!=NULL)
    {
        while(next_p->next!=NULL)
        {
            tmp_p=next_p; //保存上一个节点的地址
            next_p=next_p->next; //获取有效节点的地址
            if(next_p->a==a) //判断是否需要删除
            {
                tmp_p->next=next_p->next;
                free(next_p);
            }
        }
    }
}

3. 案例: 单向循环链表

代码直接在上面的案例2例子上改造的，区别就是尾结点指向了头结点而不是NULL。

#include <stdio.h>
#include <stdlib.h>

//定义链表节点的结构体
struct app
{
    int a;
    struct app *next; //能保存结构体的地址
};

struct app *list_head=NULL;  //链表的头指针

void list_print(struct app *head);
struct app *list_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_del(int a,struct app *head);

int main()
{
    //1. 初始化链表头
    list_head=list_HeadInit(list_head);
    //2. 在链表尾插入数据
    list_add(10,list_head);
    list_add(11,list_head);
    list_add(12,list_head);
    list_add(13,list_head);
    //3. 删除节点
    list_del(11,list_head);
    //4. 输出链接节点里的数据
    list_print(list_head);
    return 0;
}

/*
函数功能: 初始化链表头--给链表头申请空间
*/
struct app *list_HeadInit(struct app *head)
{
    if(head==NULL) //没有空间
    {
        //1. 申请链表头空间
        head=malloc(sizeof(struct app));
        //2. 初始化链表头
        head->next=head;
    }
    return head;
}

/*
函数功能: 在链表尾插入数据
int a  插入的数据值
struct app *head  链表头
*/
void list_add(int a,struct app *head)
{
    struct app *new_p=NULL;
    struct app *next_p=head;
    struct app *tmp_p; //保存上一个节点的地址
    //1.申请空间并给空间成员赋值
    new_p=malloc(sizeof(struct app));
    new_p->a=a;
    new_p->next=head;

    //2. 找到链表尾
    if(head!=NULL)
    {
        if(next_p->next==head)  //表示第一次插入节点
        {
            next_p->next=new_p;
            //head ----<节点1>---head
        }
        else
        {
            while(next_p->next!=head)
            {
                next_p=next_p->next; //指针指向下一个节点
            }
            //3. 插入新节点--链接结尾
            next_p->next=new_p;
        }   
    } 
}

/*
函数功能: 遍历输出链接里的所有数据
*/
void list_print(struct app *head)
{
    struct app *next_p=head;
    int cnt=0;
    if(head!=NULL)
    {
        printf("头地址: %#x\n",next_p); //头
        printf("第一个节点地址:%#x\n",next_p->next); //下一个节点地址
        printf("第二个节点地址:%#x\n",next_p->next->next); //下下一个节点地址
        printf("第三个节点地址:%#x\n",next_p->next->next->next);
        printf("第四个节点地址:%#x\n",next_p->next->next->next->next);
    
        while(next_p->next!=head)
        {
            next_p=next_p->next;
            printf("链表节点[%d]:a=%d\n",cnt++,next_p->a);
        }
    }
}

/*
函数功能:链表的删除－－按照指定的数据删除
*/
void list_del(int a,struct app *head)
{
    struct app *next_p=head;
    struct app *tmp_p; //保存上一个节点的地址
    //1. 找到要删除的链表
    if(next_p!=NULL)
    {
        while(next_p->next!=head)
        {
            tmp_p=next_p; //保存上一个节点的地址
            next_p=next_p->next; //获取有效节点的地址
            if(next_p->a==a) //判断是否需要删除
            {
                tmp_p->next=next_p->next;
                free(next_p);
            }
        }
    }
}

4. 案例: 创建双向链表循环，实现插入、删除、遍历

双向链表在每个节点里新增加了一个指针，用于保存上一个节点的地址，现在的节点里一个用两个指针，一个保存上一个节点的地址，一个保存下一个节点的地址。

#include <stdio.h>
#include <stdlib.h>

//定义链表节点的结构体
struct app
{
    int a;
    struct app *next; //下一个节点地址
    struct app *prev; //前一个节点地址
};

//全局变量声明区域
struct app *list_head=NULL;  //链表的头指针

//函数声明
struct app *List_HeadInit(struct app *head);
void list_add(int a,struct app *head);
void list_print(struct app *head);
void list_del(int a,struct app *head);

int main()
{
    /*1. 初始化链表*/
    list_head=List_HeadInit(list_head);
    /*2. 添加链表节点*/
    list_add(10,list_head);
    list_add(11,list_head);
    list_add(12,list_head);
    list_add(13,list_head);
    list_add(14,list_head);
    /*3.删除指定节点*/
    list_del(12,list_head);
    /*4. 遍历输出所有节点信息*/
    list_print(list_head);
    return 0;
}

/*
函数功能: 创建链表头
*/
struct app *List_HeadInit(struct app *head)
{
    if(head==NULL)
    {
        head=malloc(sizeof(struct app));
        head->a=0;
        head->next=head;
        head->prev=head;
    }
    return head;
}

/*
函数功能: 添加数据-链表尾添加数据
*/
void list_add(int a,struct app *head)
{
    struct app *next_p=head;
    struct app *new_p=NULL;
    /*1. 申请新的节点*/
    new_p=malloc(sizeof(struct app));
    new_p->a=a;
    new_p->next=head;
    /*2. 完成新节点的添加*/
    //遍历链表
    while(next_p->next!=head)
    {
        next_p=next_p->next;
    }
    //添加新节点
    new_p->prev=next_p;
    next_p->next=new_p;
    //修改链表头的上一个节点地址
    head->prev=new_p;
}

/*
函数功能:　输出链表里的所有数据
*/
void list_print(struct app *head)
{
    struct app *next_p=head;
    int cnt=0;
    /*1. 顺向遍历*/
    while(next_p->next!=head)
    {
        next_p=next_p->next;
        printf("节点[%d]:%d\n",cnt++,next_p->a);
    }
    /*2. 反向遍历*/
    next_p=head;
    while(next_p->prev!=head)
    {
        next_p=next_p->prev;
        printf("节点[%d]:%d\n",cnt--,next_p->a);
    }
}

/*
函数功能:　删除链表里的指定节点
*/
void list_del(int a,struct app *head)
{
    struct app *next_p=head;
    struct app *tmp_p=NULL;
    while(next_p->next!=head)
    {
        tmp_p=next_p; //保存上一个节点的地址
        next_p=next_p->next;
        if(next_p->a==a)
        {
            //方式1
            tmp_p->next=tmp_p->next->next;
            tmp_p->next->prev=tmp_p;

            //方式2
            //tmp_p->next=next_p->next;
            //next_p->next->prev=tmp_p;
            
            //printf("%d\n",tmp_p->a); //11
            //printf("%d\n",tmp_p->next->a); //13
            //printf("%d\n",next_p->next->prev->a); //11
            free(next_p);
            break;
        }
    }
}