链表Linklist

一、链表概念

链表也是线性表的一种，用于存取逻辑关系为线性的数据，但是和顺序表不同，链表的存储结构是链式存储，在内存中不连续，例如数据在内存中存储可能是下图：

要把链表的节点连接起来就需要通过指针来操作

所以在链表中，每个数据元素可以配有一个指针用于找到下一个元素即节点，这意味着，链表上的每个“元素”都长下图这个样子：

二、链表的特性

逻辑结构：线性结构??

存储结构：链式存储结构

特点：内存中不连续，通过指针链接

解决顺序表中的问题：长度固定和插入删除的麻烦

struct?node
{
????int?data;//数据域
????struct?node?*next;//指针域
}//

• 单向链表

有头链表：存在一个头节点，（只作为链表开头，不存放数据）数据域无效，指针域有效。

无头链表：每一个节点的数据域和指针域都有效

1、遍历无头单向链表:

#include?<stdio.h>

typedef char?datatype;
typedef struct node
{
????datatype?data;     //数据域，用来存放数据。
    struct node *next; //指针域，用来存放下一个节点的地址。
} link_node_t, *link_list_t;
//?link_node_t?A;?等同于?struct?node?A;
//?link_list_t?p;?等同于?struct?node?*p;

int main(int?argc, char const *argv[])
{
    //1.定义4个节点
    link_node_t?A?= {'a', NULL};
    link_node_t?B?= {'b', NULL};
    link_node_t?C?= {'c', NULL};
    link_node_t?D?= {'d', NULL};

    //2.将四个节点连接起来
????A.next?= &B;
????B.next?= &C;
????C.next?= &D;

    //3.定义一个头指针，指向第一个节点。用于遍历链表。
    link_list_t?p?= &A;

    //4.遍历无头链表
    while (p?!= NULL)    //判断p所指是否为空，不为空则说明指向链表节点。
    {
        printf("%c?",?p->data); //打印节点中数据域
????????p?=?p->next;            //让p指向下一个节点
    }
    printf("\n");
    return 0;
}

2、遍历有头单向链表：

#include?<stdio.h>

typedef char?datatype;
typedef struct node
{
????datatype?data;     //数据域，用来存放数据。
    struct node *next; //指针域，用来存放下一个节点的地址。
} link_node_t, *link_list_t;
//?link_node_t?A;?等同于?struct?node?A;
//?link_list_t?p;?等同于?struct?node?*p;

int main(int?argc, char const *argv[])
{
    //1.定义4个节点
    link_node_t?A?= {'a', NULL};
    link_node_t?B?= {'b', NULL};
    link_node_t?C?= {'c', NULL};
    link_node_t?D?= {'d', NULL};

    //2.将四个节点连接起来
????A.next?= &B;
????B.next?= &C;
????C.next?= &D;

    //3.定义一个头节点，数据无效，指针域指向第一个节点。
    link_node_t?h?= {'\0', &A};

    //4.定义一个头指针，指向头节点。
    link_list_t?p?= &h;

    //5.遍历有头单项链表
#if?0
    //方法一：
????p?=?p->next; //跨过头节点，指向第一个节点。
    while (p?!= NULL)
    {
        printf("%c?",?p->data);
????????p?=?p->next;
    }
    printf("\n");
#else
    //方法二：
    while (p->next?!= NULL)
    {
????????p?=?p->next;
        printf("%c?",?p->data);
    }
    printf("\n");
#endif
    return 0;
}

链表尾插法练习：

写一个有头单项链表，用于保存输入的学生成绩，实现一输入学生成绩就创建一个新的节点，将成绩保存起来。再将该节点链接到链表的尾，直到输入-1结束。

要求：每个链表的节点由动态内存分配得到?,?也就是用malloc。

过程：

1. malloc申请空间link_node_t大小作为头节点
2. 将新节点放到链表尾部

先实现输入学生成绩，直到-1结束：

#include?<stdio.h>
typedef struct node_t
{
    int?score;
    struct node_t *next;
}link_node_t,* link_list_t;

int main(int?argc, char const *argv[])
{
    int?score?= -1;
    while (1)
    {
        scanf("%d", &score);
        if (score?== -1)
            break;
        
    }
    //1.malloc申请空间，创建一个新节点用于保存学生成绩。
    //2.将新节点链接到连表的尾部
    return 0;
}

继续实现malloc申请新节点存入学生成绩然后连接到链表尾部：

#include<stdio.h>
#include<stdlib.h>
typedef struct node_t
{
    int?score;
    struct node_t *next;
}link_node_t,*link_list_t;
int main(int?argc, char const *argv[])
{
    int?score?;
    link_list_t?pnew=NULL;//新节点地址指针
    link_list_t?ptail=NULL;//链表尾巴地址指针
    //1.malloc申请空间，创建一个新节点用于保存学生成绩。
    link_list_t?h=(link_list_t)malloc(sizeof(link_node_t)); //创建一个头节点，用头指针h指向头节点
    if(NULL==h)//判断成功开辟空间
    {
        perror("h?malloc?err");
        return -1;
    }
????h->score='\0';//头节点初始化
????h->next=NULL;
????ptail=h;//指向头节点
    //2、循环输入学生成绩，直到-1结束。并且新输入一个成绩创建一个新节点存入，然后把新节点链接到链表尾巴
    while (1)
    {
        scanf("%d",&score);
        getchar();
        if(score==-1)
        { 
           break;
        }
        else
        {
????????????pnew=(link_list_t)malloc(sizeof(link_node_t));//（1）创建一个新的节点用来保存输入学生成绩
????????????pnew->next=NULL;//新节点指针域赋空值
????????????pnew->score=score;//（2）对新节点的数据域和指针域进行赋值
????????????ptail->next=pnew;//（3）将新节点连接到链表尾部
????????????ptail=pnew;  //（4）链表延长一个新节点，需要将尾指针移动到新的节点作为尾巴
        }
    }
    //3.遍历有头链表
    while (h->next!=NULL)//判断p是否指向为空，若不为空则说明指向了下一个节点
    {
????????h=h->next;//将下一个节点地址赋值给p
        printf("%d?",h->score);
    }
    puts("?");
    return 0;
}