[数据结构与算法]数据结构：有头单向不循环链表的16种操作，代码详细

一、概念

逻辑结构：线性结构

存储结构：链式存储

链表又分为有头节点的和无头节点的，区别就是头结点是否存储数据。

又分为单向链表和双向链表，还有循环链表。

有头单向不循环链表的示意图

?

二、 链表相关操作

1. 创建链表?

2. 清空链表?

3. 销毁链表?

4. 头插法?

5. 尾插法?

6. 任意位置插入法?

7. 头删法?

8. 尾删法?

9. 任意位置删除法?

10. 查询链表中是否有想要的数据(在链表中获取指定位置的数据)?

11. 按照位置修改链表中的数据?

12. 按照值修改链表中的数据?

13. 两个链表合并?

14. 链表的排序

15. 链表的翻转

16. 遍历链表的节点----学习阶段看现象用的?

二、代码实现?

2.1 link_list.h

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct __Node{
    int data;
    struct __Node *next;
}node_t;

//1.创建新节点的函数
int create_node(node_t **p, int in_data);
//2.头插法
int insert_data_by_head(node_t *phead, int in_data);
//3.遍历链表
int print_link_list(node_t *phead);
//4.尾插法插入数据
int insert_data_by_tail(node_t *phead, int in_data);
//5.任意位置插入法
int insert_data_by_pos(node_t *phead, int in_data, int pos);
//6.头删法
int del_from_list_by_head(node_t *phead);
//7.尾删法
int del_from_list_by_tail(node_t *phead);
//8.任意位置删除法
int del_from_list_by_pos(node_t *phead, int pos);
//9.根据位置从链表中获取数据
int get_data_from_list(node_t *phead, int pos, int *num);
//10.根据位置修改链表中的数据
int update_list_by_pos(node_t *phead, int pos, int new_data);
//11.根据值修改链表中的数据
int update_list_by_value(node_t *phead, int old_value, int new_value);
//12.清空链表--释放所有数据节点 保留头结点
int clean_list(node_t *phead);
//13.销毁链表
int destroy_list(node_t **p);
//14.两个链表合并
int merge_two_list(node_t *phead1, node_t **phead2);
//15.链表的翻转
int overturn_list(node_t *phead);
//16.链表的排序 -- 以升序为例
int sort_list(node_t *phead);

#endif

2.2 link_stack.c

#include "link_list.h"

//1.创建新节点的函数
int create_node(node_t **phead, int in_data){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    *phead = (node_t *)malloc(sizeof(node_t));
    if(*phead == NULL){
        printf("内存分配失败\n");
        exit(-1);
    }
    (*phead)->data = in_data;
    (*phead)->next = NULL;
    return 0;
}
//2.头插法
int insert_data_by_head(node_t *phead, int in_data){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //创建新节点
    node_t *pnew = NULL;
    create_node(&pnew, in_data);
    //执行头插操作
    pnew->next = phead->next;
    phead->next = pnew;
}
//3.遍历链表
int print_link_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    node_t *ptemp = phead;
    while(ptemp->next != NULL){ 
        ptemp = ptemp->next;
        printf("%d  ", ptemp->data);    
    }
    printf("\n");
    return 0;
}
//4.尾插法插入数据
int insert_data_by_tail(node_t *phead, int in_data){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //创建新节点
    node_t *pnew =  NULL;
    create_node(&pnew,in_data);
    //执行尾插操作
    node_t *ptemp = phead;
    //遍历链表找到链表的尾节点
    while(ptemp->next != NULL){
        ptemp = ptemp->next;
    }
    //让尾节点的指针域指向新节点
    ptemp->next = pnew;
    return 0;
}
//5.任意位置插入法
int insert_data_by_pos(node_t *phead, int in_data, int pos){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(pos <= 0){
        printf("插入位置不合理，请检查\n");
        return -1;
    }
    //找到待插入位置的前一节点
    node_t *ptemp = phead;
    int i = 0;
    for (i = 0; i < pos-1; i++){
        ptemp = ptemp->next;
        if(NULL == ptemp->next){
            break;
        }
    }
    //如果是由于break导致的循环结束 说明位置不合理
    if(i < pos-1){
        printf("插入位置不合理，请检查\n");
        return -1;
    }
    //位置合理 创建新节点
    node_t *pnew = phead;
    create_node(&pnew, in_data);
    //将新节点插入
    pnew->next = ptemp->next;
    ptemp->next = pnew;
    return 0;
}
//6.头删法
int del_from_list_by_head(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //判断是否有数据用来删除
    if(NULL == phead->next){
        printf("链表中没有数据 头删失败\n");
        return -1;
    }
    //定义一个指针 pdel 保存 第一个数据节点的地址
    node_t *pdel = phead->next;
    phead->next = pdel->next;
    free(pdel);
    pdel = NULL;
    return 0;
}
//7.尾删法
int del_from_list_by_tail(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //判断是否有数据用来删除
    if(NULL == phead->next){
        printf("链表中没有数据 头删失败\n");
        return -1;
    }
    //找到最后一个节点的前一节点
    node_t *ptemp = phead;
    while(ptemp->next->next != NULL){
        ptemp = ptemp->next;
    }
    free(ptemp->next);
    ptemp->next = NULL; 
    return 0;
}
//8.任意位置删除法
int del_from_list_by_pos(node_t *phead, int pos){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(pos <= 0){
        printf("删除位置不合理，请检查\n");
        return -1; 
    }
    node_t *ptemp = phead;
    int i = 0;
    //找到待删除位置的前一节点
    for(i = 0; i < pos-1; i++){
        ptemp = ptemp->next;
        if(NULL == ptemp->next){
            break;
        }
    } 
    if(i < pos-1){
        printf("删除位置不合理，请检查\n");
        return -1; 
    }  
    //执行删除操作
    node_t *pdel = ptemp->next;
    ptemp->next = pdel->next;
    free(pdel);
    pdel = NULL;
    return 0;
}
//9.根据位置从链表中获取数据
int get_data_from_list(node_t *phead, int pos, int *num){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(pos <= 0){
        printf("删除位置不合理，请检查\n");
        return -1; 
    }
    node_t *ptemp = phead;
    int i = 0;
    //找到要获取数据的节点  并做位置合理性的检查
    for(i = 0; i < pos; i++){
        ptemp = ptemp->next;
        if(NULL == ptemp){
            printf("获取数据的位置不合理，请检查\n");
            return -1;
        }
    } 
    //如果运行到这儿了 说明位置合理
    *num = ptemp->data;
    printf("该位置查找的数据为：%d\n", *num);
    return 0;
}
//10.根据位置修改链表中的数据
int update_list_by_pos(node_t *phead, int pos, int new_data){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(pos <= 0){
        printf("删除位置不合理，请检查\n");
        return -1; 
    }
    node_t *ptemp = phead;
    int i = 0;
    //找到要修改数据的节点  并做位置合理性的检查
    for(int i = 0; i < pos; i++){
        ptemp = ptemp->next;
        if(NULL == ptemp){
            printf("修改数据的位置不合理，请检查\n");
            return -1; 
        }
    } 
    //如果运行到这儿了 说明位置合理
    ptemp->data = new_data;
    return 0;
}
//11.根据值修改链表中的数据
int update_list_by_value(node_t *phead, int old_value, int new_value){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //遍历链表
    node_t *ptemp = phead->next;
    while(ptemp->data != old_value){
        ptemp = ptemp->next;
        if(NULL == ptemp){
            printf("链表中不存在该值，请检查\n");
            return -1;  
        }
    }
    ptemp->data = new_value;
    return 0;
}
//12.清空链表--释放所有数据节点 保留头结点
int clean_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //循环头删所有数据节点
    node_t *pdel = NULL;
    while(phead->next != NULL){
        pdel = phead->next;
        phead->next = pdel->next;             
        free(pdel);
    }
    pdel == NULL;
    return 0;
}
//13.销毁链表
int destroy_list(node_t **phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //防止先调用销毁没调用清空导致的内存泄漏
    //可以在释放头结点之前  先调用一下清空的函数
    clean_list(*phead);
    free(*phead);
    *phead = NULL;
    return 0;
}
//14.两个链表合并
int merge_two_list(node_t *phead1, node_t **phead2){
    if(NULL == phead1 || NULL == phead2 || NULL == *phead2){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    //先找到第一个链表的最后一个节点
    node_t *ptemp = phead1;
    while(ptemp->next != NULL){
        ptemp = ptemp->next;
    }
    //让第一个链表的最后一个节点的指针域指向第二个链表的第一个数据节点
    ptemp->next = (*phead2)->next;
    //释放第二个链表的 头结点
    free(*phead2);
    *phead2 = NULL;
    return 0;
}
//15.链表的翻转
int overturn_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(phead->next == NULL){
        printf("链表为空，无需翻转\n");
        return -1;
    }
    if(phead->next->next == NULL){
        printf("链表只有一个数据节点 无需翻转\n");
        return -1;
    }
    node_t *p = phead->next;
    node_t *q = p->next;
    p->next = NULL;
    while(q != NULL){
        p = q->next;
        q->next = phead->next;
        phead->next = q;
        q = p;
    }
    printf("翻转完成\n");
    return 0;
}

//16.链表的排序 -- 以升序为例
int sort_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL, 请检查\n");
        return -1;
    }
    if(phead->next == NULL){
        printf("链表为空，无需排序\n");
        return -1;
    }
    if(phead->next->next == NULL){
        printf("链表只有一个数据节点 无需排序\n");
        return -1;
    }
    int temp = 0;
    node_t *p = phead->next;
    node_t *q = p->next;  
    while(p->next != NULL){
        while(q != NULL){
            if(p->data > q->data){
                //交换数据域
                temp = q->data;
                q->data = p->data;
                p->data = temp;
            }
            q = q->next;
        }
        p = p->next;
        q = p->next;
    }
    printf("升序排序完成\n");
    return 0;
}

2.3? main.c

#include "link_list.h"
                 
int main(int argc, const char *argv[])
{
    node_t *phead = NULL;
    //1.创建头节点
    create_node(&phead,-1);
    //2.头插法
    insert_data_by_head(phead, 20);
    insert_data_by_head(phead, 10);
    insert_data_by_head(phead, 30);
    //4.尾插法插入数据
    insert_data_by_tail(phead, 50);
    //3.遍历链表
    print_link_list(phead);

    //5.任意位置插入法
    insert_data_by_pos(phead, 40, 3);
    insert_data_by_pos(phead, 60, 2);
    //3.遍历链表
    print_link_list(phead);

    //6.头删法
    del_from_list_by_head(phead);
    //3.遍历链表
    print_link_list(phead);

    //7.尾删法
    del_from_list_by_tail(phead);
    //3.遍历链表
    print_link_list(phead);

    //8.任意位置删除法
    del_from_list_by_pos(phead, 2);
    //3.遍历链表
    print_link_list(phead);

    int num = 0;
    //9.根据位置从链表中获取数据
    get_data_from_list(phead, 2, &num);

    //10.根据位置修改链表中的数据
    update_list_by_pos(phead, 1, 70);
    //3.遍历链表
    print_link_list(phead);

    //11.根据值修改链表中的数据
    update_list_by_value(phead, 40, 80);
    //3.遍历链表
    print_link_list(phead);

    node_t *phead2 = NULL;
    //1.创建头节点
    create_node(&phead2,-1);
    //2.头插法
    insert_data_by_head(phead2, 25);
    insert_data_by_head(phead2, 15);
    insert_data_by_head(phead2, 35);
    //3.遍历链表
    print_link_list(phead2);

    //14.两个链表合并
    merge_two_list(phead, &phead2);
    //3.遍历链表
    print_link_list(phead);

    //15.链表的翻转
    overturn_list(phead);
    //3.遍历链表
    print_link_list(phead);

    //16.链表的排序 -- 以升序为例
    sort_list(phead);
    //3.遍历链表
    print_link_list(phead);

    //12.清空链表--释放所有数据节点 保留头结点
    clean_list(phead);
    //13.销毁链表
    destroy_list(&phead);
    return 0;
}

四、代码运行效果?