醉丶春风的Blog

代码实现

由于手动分配内存太麻烦， 我就写了两个函数模仿其他语言new的用法

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

/**
 * 链表元素
 */ 
typedef struct node {
    int data; // 元素值
    struct node *next; // 指向下个元素
} Node;

/**
 * 链表
 */ 
typedef struct linklist {
    int length; // 链表长度
    Node *head; // 带头节点
    Node *tail; // 尾结点，通过这个节点可以使插入的时间复杂度变为O(1)
} LinkList;

// 打印链表
void printAll(const LinkList *l);
// 插入元素，尾部插入
void insert(LinkList *l, int data);
// 按索引删除元素
int delete(LinkList *l, int index);
// 按值删除匹配的第一个元素
int deleteByValue(LinkList *l, int data);
// 按值删除所有匹配的元素
int deleteAllByValue(LinkList *l, int value);
// 按索引更新元素
int update(LinkList *l, int index, int value);
// 按索引获取元素
int get(const LinkList *l, int index);
// 清空链表， 不会删除带头节点
int clear(LinkList *l);
// 销毁链表， 释放所有内存
void destory(LinkList *l); // 销毁链表
// 分配并创建链表
LinkList *newLinkList(void);
// 分配并创建链表元素
Node *newNode(int data, Node *next);

int main()
{
    LinkList *l = newLinkList();
    // 添加元素
    insert(l, 1);
    insert(l, 2);
    insert(l, 3);
    insert(l, 4);
    insert(l, 4);
    insert(l, 4);
    insert(l, 4);
    insert(l, 5);
    // 元素删除
    delete(l, 1);
    deleteByValue(l, 2);
    deleteAllByValue(l, 4);
    // 更新
    update(l, 2, 6);
    // 打印
    printAll(l);
    // 获取元素
    printf("第2个元素的值为：%d\n", get(l, 2));
    // 清空链表
    clear(l);
    // 清空之后再打印
    printAll(l);
    // 销毁
    destory(l);


    return 0;
}

/**
 * 手动创建一个new 函数来创建链表
 */ 
LinkList *newLinkList(void)
{
    LinkList *l = (LinkList *)malloc(sizeof(LinkList));
    l->length = 0;
    l->head = newNode(0, NULL);
    l->tail = l->head;
    return l;
}

/**
 * 手动创建一个new 函数来创建元素
 */ 
Node *newNode(int data, Node *next)
{
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = data;
    n->next = next;
    return n;
}

/**
 * 插入一个新元素， 尾部插入
 */
void insert(LinkList *l, int data)
{
    // 创建一个新的元素
    Node *latestNode = newNode(data, l->tail->next);
    // 将新元素放在最后一个元素之后
    l->tail->next = latestNode;
    // 将尾结点指向最后一个元素
    l->tail = latestNode;
    // 更新链表长度
    l->length++;
}

/**
 * 打印链表
 */ 
void printAll(const LinkList *l)
{
    printf("\n开始打印链表。。。\n");
    int i = 1;
    if (l->length > 0) {
        // 忽略带头结点r
        Node *temp = l->head->next;

        while (temp != NULL)
        {
            printf("  ->第%d个元素的值为： %d\n", i, temp->data);
            i++;
            temp = temp->next;
        }
    }
    printf("结束打印链表。。。\n\n");
}

/**
 * 根据索引删除元素， 查到到上一个索引， 将上一个索引指向下下个元素即可
 */ 
int delete(LinkList *l, int index)
{
    if (index > l->length || index < 1) {
        return 0;
    }
    int i = 1;
    Node *temp = l->head; // 带头节点， 指向要删除的元素前一个节点
    while (i != index)
    {
        temp = temp->next;
        i++;
    }
    Node *item = temp->next; // 先保存要删除的节点
    temp->next = temp->next->next; // 更新上个节点指向下下个节点
    free(item);
    return 1;
}

/**
 * 按值删除第一个匹配的元素
 */ 
int deleteByValue(LinkList *l, int value)
{
    if (l->length < 1) {
        return 0;
    }
    Node *temp, *item;
    temp = l->head;
    // 查找要删除的第一个元素， 如果查找到最后一个元素(最后一个元素next指向NULL), 说明没有该值
    while (temp->next != NULL && temp->next->data != value)
    {
        temp = temp->next;
    }

    // 查找到了元素
    if (temp->next != NULL) {
        item = temp->next; // 要删除的元素
        temp->next = temp->next->next; // 指向下下个元素
        free(item); // 释放要删除的元素
        l->length--; // 更新链表长度
        return 1;
    }

    return 0;
}

/**
 * 按值删除所有匹配的元素
 */
int deleteAllByValue(LinkList *l, int value)
{
    if (l->length < 1) {
        return 0;
    }

    Node *temp, *item;
    temp = l->head;

    while (temp != NULL && temp->next != NULL)
    {
        if (temp->next->data == value) {
            item = temp->next;
            temp->next = temp->next->next; // 将指针指向下下个元素， 不能移动指针到下下个元素， 如果下下个元素也是要删除的元素，将会出现内存溢出和遗漏
            free(item);
            l->length--;
        } else {
            temp = temp->next;
        }
    }

    return 1;
}

/**
 * 按索引更新元素
 */
int update(LinkList *l, int index, int value)
{
    if (index > l->length || l->length < 1) {
        return 0;
    }
    Node *temp = l->head;
    // 找到要修改的节点
    // 第0次， 指向第一个节点
    // 。。。， 所以index-1个节点就是我们要修改的节点
    for (int i = 0; i < index; i++)
    {
        temp = temp->next;
    }
    temp->data = value;

    return 1;
}

/**
 * 按索引获取元素
 */ 
int get(const LinkList *l, int index)
{
    if (index > l->length || l->length < 1) {
        return -1;
    }

    Node *temp = l->head;

    for (int i = 0; i < index; i++)
    {
        temp = temp->next;
    }

    return temp->data;
}

/**
 * 清空链表元素，仅保留头结点和尾结点
 */ 
int clear(LinkList *l)
{
    if (l->length <= 0) {
        return 0;
    }
    // 从第一个元素开始删除，保留头节点
    Node *temp = l->head->next;

    while (temp != NULL)
    {
        l->tail = temp->next; // 存储下个节点的指针
        free(temp); // 释放当前节点
        temp = l->tail; // 重新指向下个节点

    }

    l->tail = l->head; // 修复尾结点指向头结点
    l->length = 0; // 重置长度
    return 1;
}

/**
 * 销毁链表
 */ 
void destory(LinkList *l)
{
    clear(l); // 先清空元素
    free(l->head); //释放头结点
    free(l);
    l = NULL; // 将链表指向NULL
}

输出结果

 shantong@mac# gcc ./linklist.c && ./a.out

开始打印链表。。。
  ->第1个元素的值为： 3
  ->第2个元素的值为： 6
结束打印链表。。。

第2个元素的值为：6

开始打印链表。。。
结束打印链表。。。