C语言数据结构——单链表

链表存储结构定义

不同于顺序的线性表，链表的存储单元不连续，数据元素可以存在内存任何未被占用的任意位置。因此除了要存储数据元素的信息之外，还要存储它的后继元素的存储地址，因此每个元素Ai与其后继的元素Ai+1是通过一个存储地址来关联的。
对于元素Ai来说，除了本身的数据，还有一个指向Ai+1的数据域，通过这个数据域才能够索引到Ai+1元素，我们把存储数据的域叫做数据域，存储地址部分的域叫做指针域。指针域中存放的信息叫做指针或者链。
这两部分信息组成的叫做结点。n个结点组成一个链表，我们把链表的第一个结点或头结点的存储位置叫做头指针（指向第一个结点的存储位置；如果有头结点，则是指向头结点的存储位置）。为了更方便链表的操作，会在单链表的第一个结点前设置一个节点，称为头结点。头结点的数据域不存储任何信息，头结点的指针域存储指向第一个结点点指针，如图：

头指针与头结点

头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必要的元素

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可以存放链表的长度)
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
• 头结点不一定是链表必须要素

单链表的存储结构

不带头结点的结构：

带头结点的结构：

空链表：

单链表的存储结构

单链表中，我们可以用结构指针来描述。

typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针

结点由存放数据元素的数据域和存放后继结点地址的指针域组成，假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data表示，p->data的值是个数据元素，结点ai的指针域可以用p->next表示，p->next的值是个指针，p->next指向第i+1各元素，即指向ai+1的指针。也就是，如果p->data=ai,那么p->next->data=ai+1

单链表整表的创建(头插法）

单链表整表创建的算法思路：

1. 声明一结点p和计数器变量i
2. 初始化一空链表L
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
4. 循环
   a.生成一新结点赋值给p
   b.随机生成一数字赋值给p的数据域p->data
   c.将p插入到头结点与前一新结点之间

头插法：
每次都把新的结点都放在最前面。

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

typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表L(头插法)
void CreateListHead(LinkList * L,int n)
{
    LinkList p; //声明了一个指向Node的指针p
    srand(time(0)); //初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //为头结点分配内存空间,创建一个头结点，(*L)相当于头结点
    (*L)->next = NULL;  //建立一个空的头结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList) malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}




int main()
{
    LinkList L;
    CreateListHead(&L,5);//随机创建5个元素的单链表
    PrintLinkList(L);   //打印单链表
    return 0;
}

运行结果：

单链表整表的创建(尾插法）

尾插法：
每次都把新结点都插在终端结点的后面。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ERROR 0
#define OK 1
typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表(尾插法)
void CreateListTail(LinkList * L,int n)
{
    LinkList p,r;
    srand(time(0));//初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //创建头结点
    r = (*L);   //r为指向尾部的结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        r->next = p;    //将尾部结点的指针指向新结点
        r = p;  //将r重新指向为尾部新的终端结点
    }
    r->next = NULL; //表明当前链表结束

}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}




int main()
{
    LinkList L;
    CreateListTail(&L,5);
    PrintLinkList(L);   //打印单链表
    return 0;
}

运行结果：

单链表的读取

单链表读取第i个数据的算法：
1. 声明一个结点p指向链表的第一个节点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
3. 若链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，返回结点p的数据

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ERROR 0
#define OK 1
typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表L(头插法)
void CreateListHead(LinkList * L,int n)
{
    LinkList p; //声明了一个指向Node的指针p
    srand(time(0)); //初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //为头结点分配内存空间,创建一个头结点，(*L)相当于头结点
    (*L)->next = NULL;  //建立一个空的头结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList) malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}


void CreateListTail(LinkList * L,int n)
{
    LinkList p,r;
    srand(time(0));//初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //创建头结点
    r = (*L);   //r为指向尾部的结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        r->next = p;    //将尾部结点的指针指向新结点
        r = p;  //将r重新指向为尾部新的终端结点
    }
    r->next = NULL; //表明当前链表结束

}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}


int GetElem(LinkList L,int i,ElemType * e)
{
    int j;
    LinkList p;
    p = L->next;    //p指向第一个节点
    j = 1;  //计数器
    while(p && j < i)   //p不为空或者计数器j还没有等于1，循环继续
    {
        p = p->next;    //p指向下一个结点
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;//第i个元素不存在
    }
    *e = p->data;   //取出第i个元素的数据
    return OK;
}




int main()
{
    LinkList L;
//  CreateListHead(&L,5);//随机创建5个元素的单链表
    CreateListTail(&L,5);
    PrintLinkList(L);   //打印单链表
    ElemType e;
    GetElem(L,5,&e);
    printf("%d\n",e);
    return 0;
}

运行结果：

单链表的插入

单链表的插入：

单链表第i个数据插入结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，在系统中生成一个空结点s
5. 将数据元素e赋值给s->data
6. 单链表的插入标准语句s->next = p->next;p->next = s;
7. 返回成功

实现代码算法如下：

//单链表的插入
int InsertList(LinkList * L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p = (*L);   //p指向头结点
    j = 1;  //计数器
    while(p && j < i)   //寻找第i个结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;   //第i个元素不存在
    }

    s = (LinkList)malloc(sizeof(Node)); //生成新结点
    s->data = e;
    s->next = p->next;  //将p的后继结点赋值给s的后继
    p->next = s;    //将s赋值给p的后继
    return OK;

}

运行主程序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ERROR 0
#define OK 1
typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表L(头插法)
void CreateListHead(LinkList * L,int n)
{
    LinkList p; //声明了一个指向Node的指针p
    srand(time(0)); //初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //为头结点分配内存空间,创建一个头结点，(*L)相当于头结点
    (*L)->next = NULL;  //建立一个空的头结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList) malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}


void CreateListTail(LinkList * L,int n)
{
    LinkList p,r;
    srand(time(0));//初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //创建头结点
    r = (*L);   //r为指向尾部的结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        r->next = p;    //将尾部结点的指针指向新结点
        r = p;  //将r重新指向为尾部新的终端结点
    }
    r->next = NULL; //表明当前链表结束

}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}


int GetElem(LinkList L,int i,ElemType * e)
{
    int j;
    LinkList p;
    p = L->next;    //p指向第一个节点
    j = 1;  //计数器
    while(p && j < i)   //p不为空或者计数器j还没有等于1，循环继续
    {
        p = p->next;    //p指向下一个结点
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;//第i个元素不存在
    }
    *e = p->data;   //取出第i个元素的数据
    return OK;
}


//单链表的插入
int InsertList(LinkList * L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p = (*L);   //p指向头结点
    j = 1;  //计数器
    while(p && j < i)   //寻找第i个结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;   //第i个元素不存在
    }

    s = (LinkList)malloc(sizeof(Node)); //生成新结点
    s->data = e;
    s->next = p->next;  //将p的后继结点赋值给s的后继
    p->next = s;    //将s赋值给p的后继
    return OK;

}




int main()
{
    LinkList L;
//  CreateListHead(&L,5);//随机创建5个元素的单链表
    CreateListTail(&L,5);
    PrintLinkList(L);   //打印单链表
    InsertList(&L,3,7); //第三个位置插入元素7
    PrintLinkList(L);   //打印单链表
    return 0;
}

运行结果：

单链表的删除

单链表第i个数据删除结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，将欲删除的结点p->next赋值给q
5. 单链表的删除标准语句p->next = q->next
6. 将q结点中的数据赋值给e，作为返回
7. 释放q结点
8. 返回成功

实现代码算法如下：

//删除单链表元素
int DeleteLinkList(LinkList * L,int i,ElemType * e)
{
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p && j<i) //遍历寻找第i个元素
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i)
    {
        return ERROR;   //第i个元素不存在
    }
    q = p->next;
    p->next = q->next;  //将q的后继赋值给p的后继
    *e = q->data;
    free(q);//让系统回收此结点，释放内存
    return OK;
}

运行主程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ERROR 0
#define OK 1
typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表L(头插法)
void CreateListHead(LinkList * L,int n)
{
    LinkList p; //声明了一个指向Node的指针p
    srand(time(0)); //初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //为头结点分配内存空间,创建一个头结点，(*L)相当于头结点
    (*L)->next = NULL;  //建立一个空的头结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList) malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}


void CreateListTail(LinkList * L,int n)
{
    LinkList p,r;
    srand(time(0));//初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //创建头结点
    r = (*L);   //r为指向尾部的结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        r->next = p;    //将尾部结点的指针指向新结点
        r = p;  //将r重新指向为尾部新的终端结点
    }
    r->next = NULL; //表明当前链表结束

}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}


int GetElem(LinkList L,int i,ElemType * e)
{
    int j;
    LinkList p;
    p = L->next;    //p指向第一个节点
    j = 1;  //计数器
    while(p && j < i)   //p不为空或者计数器j还没有等于1，循环继续
    {
        p = p->next;    //p指向下一个结点
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;//第i个元素不存在
    }
    *e = p->data;   //取出第i个元素的数据
    return OK;
}


//单链表的插入
int InsertList(LinkList * L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p = (*L);   //p指向头结点
    j = 1;  //计数器
    while(p && j < i)   //寻找第i个结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;   //第i个元素不存在
    }

    s = (LinkList)malloc(sizeof(Node)); //生成新结点
    s->data = e;
    s->next = p->next;  //将p的后继结点赋值给s的后继
    p->next = s;    //将s赋值给p的后继
    return OK;

}

//删除单链表元素
int DeleteLinkList(LinkList * L,int i,ElemType * e)
{
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p && j<i) //遍历寻找第i个元素
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i)
    {
        return ERROR;   //第i个元素不存在
    }
    q = p->next;
    p->next = q->next;  //将q的后继赋值给p的后继
    *e = q->data;
    free(q);//让系统回收此结点，释放内存
    return OK;
}




int main()
{
    LinkList L;
//  CreateListHead(&L,5);//随机创建5个元素的单链表
    CreateListTail(&L,5);
    PrintLinkList(L);   //打印单链表
    ElemType e;
    //GetElem(L,5,&e);
    //printf("%d\n",e);
    InsertList(&L,3,7); //第三个位置插入元素7
    PrintLinkList(L);   //打印单链表
    DeleteLinkList(&L,3,&e);//删除第三个位置的元素
    PrintLinkList(L);   //打印单链表
    printf("%d\n",e);
    return 0;
}

运行结果：

单链表的整表删除

单链表整表删除的算法思路：

1. 声明一结点p和q
2. 将第一个结点赋值给q
3. 循环
   a.将下一结点赋值给q
   b.释放p
   c.将q赋值给p

实现代码算法如下：

int ClearList(LinkList * L)
{
    LinkList p,q;
    p = (*L)->next; //p指向第一个结点
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;  //头结点指针域为空
    return OK;
}

运行主程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ERROR 0
#define OK 1
typedef int ElemType;   //假定ElemType的类型为int

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node;  //定义Node

typedef struct Node * LinkList; //定义LinkList，指向Node的指针


//随机产生n个元素的值，建立带头结点的单链表L(头插法)
void CreateListHead(LinkList * L,int n)
{
    LinkList p; //声明了一个指向Node的指针p
    srand(time(0)); //初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //为头结点分配内存空间,创建一个头结点，(*L)相当于头结点
    (*L)->next = NULL;  //建立一个空的头结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList) malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表头
    }
}


void CreateListTail(LinkList * L,int n)
{
    LinkList p,r;
    srand(time(0));//初始化随机数种子
    (*L) = (LinkList)malloc(sizeof(Node));  //创建头结点
    r = (*L);   //r为指向尾部的结点
    for(int i=0;i<n;i++)
    {
        p = (LinkList)malloc(sizeof(Node));//生成新结点
        p->data = rand()%10 + 1;    //随机生成10以内的数字
        r->next = p;    //将尾部结点的指针指向新结点
        r = p;  //将r重新指向为尾部新的终端结点
    }
    r->next = NULL; //表明当前链表结束

}

//打印单链表
void PrintLinkList(LinkList L)
{
    LinkList P;
    P = L->next;
    while(P)
    {
        printf("%d ",P->data);
        P = P->next;
    }
    printf("\n");
}


int GetElem(LinkList L,int i,ElemType * e)
{
    int j;
    LinkList p;
    p = L->next;    //p指向第一个节点
    j = 1;  //计数器
    while(p && j < i)   //p不为空或者计数器j还没有等于1，循环继续
    {
        p = p->next;    //p指向下一个结点
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;//第i个元素不存在
    }
    *e = p->data;   //取出第i个元素的数据
    return OK;
}


//单链表的插入
int InsertList(LinkList * L,int i,ElemType e)
{
    int j;
    LinkList p,s;
    p = (*L);   //p指向头结点
    j = 1;  //计数器
    while(p && j < i)   //寻找第i个结点
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)
    {
        return ERROR;   //第i个元素不存在
    }

    s = (LinkList)malloc(sizeof(Node)); //生成新结点
    s->data = e;
    s->next = p->next;  //将p的后继结点赋值给s的后继
    p->next = s;    //将s赋值给p的后继
    return OK;

}

//删除单链表元素
int DeleteLinkList(LinkList * L,int i,ElemType * e)
{
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p && j<i) //遍历寻找第i个元素
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i)
    {
        return ERROR;   //第i个元素不存在
    }
    q = p->next;
    p->next = q->next;  //将q的后继赋值给p的后继
    *e = q->data;
    free(q);//让系统回收此结点，释放内存
    return OK;
}

int ClearList(LinkList * L)
{
    LinkList p,q;
    p = (*L)->next; //p指向第一个结点
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;  //头结点指针域为空
    return OK;
}



int main()
{
    LinkList L;
//  CreateListHead(&L,5);//随机创建5个元素的单链表
    CreateListTail(&L,5);
    PrintLinkList(L);   //打印单链表
//  ElemType e;
    //GetElem(L,5,&e);
    //printf("%d\n",e);
//  InsertList(&L,3,7); //第三个位置插入元素7
//  PrintLinkList(L);   //打印单链表
//  DeleteLinkList(&L,3,&e);//删除第三个位置的元素
    ClearList(&L);//删除整个链表
    PrintLinkList(L);   //打印单链表
    //printf("%d\n",e);
    return 0;
}

运行结果：