当前位置:博客首页>>C/C++ >> 阅读正文

又是一个单链表的实现(头插法和尾插法)

作者: 郑晓 分类: C/C++, 数据结构 发布于: 2017-02-10 10:41 浏览(876) 没有评论


看了不少资料,之前一直糊涂,感觉刚刚弄明白,所以又写了一遍单链表的实现,包括头插和尾插…C语言的指针果然水深啊。

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

//定义链表节点结构
struct LinkedList {
    int data;
    struct LinkedList *next;
};

//定义一个指向struct LinkedList的指针的类型node
typedef struct LinkedList *node;

/**
 * 创建一个新节点
 * @return node
 */

node create_node() {
    node tmp;
    tmp = (node) malloc(sizeof(struct LinkedList));
    tmp->next = NULL;
    return tmp;
}

/**
 * 尾插法 每次插入的数据放到链表结尾
 */

void add_node_to_tail(node head, int data) {
    node tmp, p;
    //创建一个新节点 并保存入数据
    tmp = create_node();
    tmp->data = data;
    //如果是空表 把新节点直接放到头节点之后
    if(head->next == NULL) {
        head->next = tmp;
    } else {
        //不是空表时 开始遍历链表至尾端
        p = head->next;
        while(p->next!= NULL) {
            p = p->next;
        }
        //把新节点放到尾端
        p->next = tmp;
    }
}

/**
 * 头插法 每次插入的数据放到链表开头
 */

void add_node_to_head(node head, int data) {
    node tmp, p;
    //创建一个新节点
    tmp = create_node();
    tmp->data = data;
    //如果是空表 把新节点直接放到头节点之后
    if(head->next == NULL) {
        head->next = tmp;
    } else {
        //不是空表时 把新节点的next指向到原链表第一个元素
        tmp->next = head->next;
        //把头节点指向到新节点
        head->next = tmp;
    }
}

int main(void) {
    node listHead, p;
    //创建一个头节点
    listHead = create_node();
    //头插法 新增数据
    add_node_to_head(listHead, 10);
    add_node_to_head(listHead, 20);
    add_node_to_head(listHead, 30);
    add_node_to_head(listHead, 40);
    //尾插法 新增数据
    add_node_to_tail(listHead, 100);
    add_node_to_tail(listHead, 200);

    //遍历链表并打印元素值
    p = listHead->next;
    while(p) {
        printf("%d\n", p->data);
        p = p->next;
    }

    return 0;
}
       

本文采用知识共享署名-非商业性使用 3.0 中国大陆许可协议进行许可,转载时请注明出处及相应链接。

本文永久链接: https://www.zh30.com/singly-linked-list-head-tail-insert.html