【数据结构】 单向链表的实现

单向链表是数据结构中的一种，它由节点组成，每个节点包含两个部分：数据域和指针域。数据域用于存储节点的值，指针域则用于指向下一个节点。单向链表的特点是只能从头节点开始遍历到尾节点，不能反向遍历。

1 单向链表的节点定义

typedef struct node
{
    int data; //数据域 用来存放数据 整型
    struct node * next; //指针域 用来存放下一个节点的首地址
}link_node_t;

2.创建一个空的链表 

//1.创建一个空的链表(本质上只有一个头节点链表,将头节点的首地址返回)
link_node_t* createEmptyLinklist()
{
    //创建一个空的头节点
    link_node_t* p = malloc(sizeof(link_node_t));
    if(p == NULL)
    {
        printf("createEmptyLinklist malloc failed!!\n");
        return NULL;//表达申请失败
    }
    //申请空间,就是为了装东西
    p->next = NULL;//指针域初始化为NULL,数据域不用初始化,因为头节点数据域无效
    //将头节点的首地址返回
    return p;
}

3.遍历有头链表的有效元素

void showLinklist(link_node_t* p)
{
    while(p->next != NULL)
    {
        p = p->next;
        printf("%d ",p->data);
    }
    printf("\n");
}

4.求链表的长度  

int getLengthLinklist(link_node_t* p)
{
    int len = 0;//统计长度
    while(p->next != NULL)
    {
        p = p->next;
        len++;//打印一次,就计数一次
    }
    return len;
}

5.判断链表是否为空,空返回1，未空返回0

//6. 判断链表是否为空 空返回1,未空返回0
int isEmptyLinklist(link_node_t* p)
{
    //p指向头节点
    //p->next代表头节点的指针域,头节点的指针域为空,说明后面什么没有了
    return p->next == NULL ? 1 : 0;
}

6.向链表的指定位置插入数据

int insertIntoLinklist(link_node_t* p, int post, int x)
{
    int i;
    //0.容错判断
    if(post < 1 || post > getLengthLinklist(p)+1)
    {
        printf("insertIntoLinklist failed!!\n");
        return -1;
    }
    //1.创建一个新的节点,保存插入的数据x
    link_node_t* pnew = malloc(sizeof(link_node_t));
    if(pnew == NULL)
    {
        printf("pnew malloc failed!!\n");
        return -1;
    }
    //申请空间,就是为了装东西,立刻装东西
    pnew->data = x;
    pnew->next = NULL;
    //准备开始插入
    //2.将头指针指向(移动)插入位置的前一个位置
    for(i = 0; i < post-1; i++)
        p = p->next;
    //3.将新节点插入链表(先连后面,再连前面)
    pnew->next = p->next;//连后面
    p->next = pnew;//连前面
    return 0;
}

int deleteFromLinklist(link_node_t* p, int post)
{
    //0.容错判断
    if(post < 1 || post > getLengthLinklist(p) || isEmptyLinklist(p))
    {
        printf("deleteFromLinklist failed!!\n");
        return -1;
    }
    //1. 将头指针移动到删除位置的前一个位置
    int i;
    for(i = 0; i < post-1; i++)
        p = p->next;
    //2.定义了指针变量4个字节,指向被删除节点
    link_node_t* pdel = p->next;
    //3.跨过被删除节点
    p->next = pdel->next;
    //4. 释放被删除节点
    free(pdel)
    pdel = NULL;
    return 0;
}

void clearLinklist(link_node_t* p)
{
    //砍头思想:每次删除的是头节点的下一个节点
    while(p->next != NULL)
    //只要链表不为空,就执行删除操作 p->next == NULL循环结束,此时是空的表
    {
        //1. 将头指针移动到删除位置的前一个位置
        //第一步可以省略不写,因为每次删除的是头节点的下一个节点,
        //那么头节点就是每次被删除节点的前一个位置
        //2.定义了指针变量4个字节,指向被删除节点
        link_node_t* pdel = p->next;
        //3.跨过被删除节点
        p->next = pdel->next;
        //4. 释放被删除节点
        free(pdel);
        pdel = NULL;
    }
}

int searchDataLinklist(link_node_t* p, int x)
{
    int post = 0;
    while(p->next != NULL)
    {
        p = p->next;
        post++;//用来记录第几个
        if(p->data == x)
            return post;//返回值是第几个
    }
    return -1;//不存在
}