C语言数据结构之单向链表详解

目录

• 链表
• 静态链表
• 动态链表
• 定义链表节点
• 创建链表
• 创建一个空节点
• 尾插法
• 头插法
• 指定位置插入一个结点
• 遍历链表
• 获取链表长度
• 链表搜索
• 链表数据排序
• 反转链表
• 删除节点数据
• 销毁链表
• 测试

链表

链表实现了，内存零碎数据的有效组织。比如，当我们用 malloc 来进行内存申请的时候，当内存足够，但是由于碎片太多，没有连续内存时，只能以申请失败而告终，而用链表这种数据结构来组织数据，就可以解决上类问题。

静态链表

#include <stdio.h>
// 1.定义链表节点
typedef struct node{
    int data;
    struct node *next;
}Node;
int main(int argc, char *argv[]) {
    // 2.创建链表节点
    Node a;
    Node b;
    Node c;

    // 3.初始化节点数据
    a.data = 1;
    b.data = 3;
    c.data = 5;

    // 4.链接节点
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    // 5.创建链表头
    Node *head = &a;

    // 6.使用链表
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;//指向下一个节点
    }

    return 0;
}

动态链表

静态链表的意义不是很大，主要原因，数据存储在栈上，栈的存储空间有限，不能动态分配。所以链表要实现存储的自由，要动态的申请堆里的空间。

有头链表

无头链表

单向链表有有头节点和无头节点两种列表, 有头节点在列表的删除,反转,插入等操作会比无头节点简单,但是不好之处就是多占用些空间,而且在多个链表结合处理的时候有头链表每次都需要过滤头节点,而无头链表直接完美融合 ,而且很多高级语言都是无头链表的便于日后的扩展 ,下面都是依据无头节点进行演示

定义链表节点

// 1.定义链表节点
typedef struct node {
    void *data;
    struct node *next;
} Node;

创建链表

/**
 * 创建链表
 */
Node *createList() {

    // 1.创建头节点
    Node *root = (Node *) malloc(sizeof(Node));
    root->data = NULL;
    root->next = NULL;
    //返回头节点
    return root;
}

创建一个空节点

/**
 * 创建一个空节点
 */
Node *createNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = NULL;
    node->next = NULL;
    return  node;
}

尾插法

/**
 * @brief insertEndNode 尾插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertEndNode(Node *node, void *data) {
    Node *head = node;
    //找到数据为空的节点,没有节点那么就扩展
    while (head->data != NULL) {
        //扩容
        if(head->next == NULL) {
            Node *pNode = createNode();
            head->next = pNode;
            head = pNode;
            break;
        }
        head = head->next;
    }
    //插入数据
    head->data = data;
}

头插法

/**
 * @brief insertHeadNode 头插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertHeadNode(Node **node, void *data) {
    Node *pNode = createNode();
    pNode->data = data;
    pNode->next = *node;
    *node = pNode;
}

指定位置插入一个结点

简单来说就是先找到需要插入的位置,然后将当前位置节点和他前一个节点连接到需要插入的节点就行了

/**
 * @brief insertNOde 将数据节点插入到指定数据位置节点,指定数据节点向后移动,  如果没有找到插入的位置,那么就插入到最后
 * @param insertionPoint 指定的数据节点
 * @param data 需要插入的数据
 */
void insertNode(Node *node ,void *insertionPoint,void *data){
    Node *pNode = node;
    Node *pre = pNode;//父节点
    while (pNode!=NULL){
        if(pNode->data == insertionPoint){
            break;
        }
        pre=pNode; //保留当前节点
        pNode=pNode->next;
    }
    //如果没有找到那么就插入到最后
    if(pNode==NULL){
        insertEndNode(node,data);
        return;
    }
    Node *dataNode = createNode();
    dataNode->data= data;
    pre->next = dataNode;
    dataNode->next = pNode;
}

遍历链表

因为我们值存储是使用无类型的指针,所以需要转换为插入时候的类型才行

/**
 * @brief printNodeListDouble 遍历链表
 * @param node 链表指针头
 */
void printNodeListDouble(Node *node) {
    Node *head = node;
    while (head!=NULL&&head->data!=NULL){
        double *currentData = head->data;
        printf("currentData = %f\n", *currentData);
        head = head->next;
    }
}

获取链表长度

/**
 * @brief listLength 计算链表长度
 * @param head 链表头指针
 * @return 链表长度
 */
int listLength(Node *head){
    int count = 0;
    head = head;
    while(head){
        count++;
        head = head->next;
    }
    return count;
}

链表搜索

/**
 * @brief searchList 查找指定节点
 * @param head 链表头指针
 * @param key 需要查找的值
 * @return
 */
Node *searchList(Node *head, void *key){
    head = head;
    while(head){
        if(head->data == key){
            break;
        }else{
            head = head->next;
        }
    }
    return head;
}

链表数据排序

因为我们存储数据类型是使用无类型的指针,那么在排序的时候需要转换为指定类型才行

/**
 * @brief bubbleSort 对链表值进行排序  小到大
 * @param head 链表头指针
 */
void sortDouble(Node *head){
    // 1.计算链表长度
    int len = listLength(head);
    // 2.定义变量记录前后节点
    Node *cur = head;
    while (cur!=NULL){
        Node *cur1=cur->next;
        while (cur1!=NULL){
            //比较大小 ,然后交换数据
            if(*((double *)cur->data) > *((double *)cur1->data)){
                double *temp = (double *)cur->data;
                cur->data = cur1->data;
                cur1->data = temp;
            }
            cur1 = cur1->next;
        }
        cur= cur->next;
    }
}

反转链表

断开链表头，然后以头插法的方式将原链表的数据添加链表。

/**
 * @brief reverseList 反转链表
 * @param head 链表头指针
 */
void reverseList(Node **root){
    Node *head = *root;
    Node *pre=head, *cur=head->next;
    pre->next = NULL;
    while (cur!=NULL){
        Node *node = cur->next;
        cur->next = pre;
        pre = cur;
        cur=node;
    }
    *root=pre;
}

删除节点数据

先找到需要删除的节点,之后将后一个结点赋值给前一个结点的next,然后将删除位置的结点释放即可

/**
 * @brief delNode 删除指定节点
 */
void delNode(Node **root, void *key){
    Node *head = *root;
    //根节点单独处理
    if(head->data == key&&head->next != NULL){
        *root = head->next;
        free(head->data);
        free(head);
        return;
    }

    Node *head1 = head->next;
    Node *pre = head;//根节点
    while (head1!=NULL){
        if(head1->data == key){
            pre->next = head1->next;
            free(head1->data);
            free(head1);
            break;
        }
        pre = head1;//当前节点
        head1 = head1->next; //下一个节点
    }
}

销毁链表

/**
 * @brief destroyList 销毁链表
 * @param head 链表头指针
 */
void destroyList(Node *head){
    Node *cur = head;
    while(head != NULL){
        cur = head->next;
        free(head->data);//清除当前节点数据内存
        free(head);//清除当前节点内存
        head = cur;
    }
}

测试

int main(int argc, char *argv[]) {


    //创建链表
    Node *head = createList();

    //插入数据
    printf("insert ====================\n");
    double *f = (double *)malloc(sizeof(double));
    *f=2.1;
    insertEndNode(head, f);
    double *f1 = (double *)malloc(sizeof(double));
    *f1=1.1;
    insertEndNode(head, f1);
    double *f2= (double *)malloc(sizeof(double));
    *f2=0.1;
    insertEndNode(head, f2);

    double *f3= (double *)malloc(sizeof(double));
    *f3=3.1;
    insertHeadNode(&head, f3);


    double *se = (double *)malloc(sizeof(double));
    *se=111.1;
    double *f4= (double *)malloc(sizeof(double));
    *f4=7.1;
    insertNode(head,se, f4);
    free(se);
    printNodeListDouble(head);

    //获取长度
    printf("listLength ====================\n");
    int i = listLength(head);
    printf("listLength = %d\n", i);

    //搜索
    printf("searchList ====================\n");
    Node *pNode = searchList(head, f1);
    printf("currentData = %f\n", *((double *)pNode->data));

    //排序
    printf("sortDouble ====================\n");
    sortDouble(head);
    printNodeListDouble(head);

    //反转
    printf("reverseList ====================\n");
    reverseList(&head);
    printNodeListDouble(head);

    //删除节点
    printf("delNode ====================\n");
    delNode(&head, f1);
    printNodeListDouble(head);

    //销毁
    destroyList(head);


    return 0;
}

到此这篇关于C语言数据结构之单向链表详解的文章就介绍到这了,更多相关C语言单向链表内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！