数据结构——链表

本文所讲的链表是单链表，链表采用无头链表

科普下：一般链表可以分为有头节点的链表与无头节点的链表

• 有头节点的链表：每个节点存储这个一个或者一组数据，但是有头节点的链表的第一个节点是头节点，头节点只是一个节点，但不存储数据，头节点的主要作用是方便插入操作
• 无头节点的链表：每个节点都是有效节点，都存储有效的数据

至于为什么用无头节点，是因为刚实习的时候被领导说了使用有头节点的链表是浪费内存，好吧！！

（1）定义链表结构

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

typedef struct {
    char key[15];
    char name[20];
    int age;
} DATA;

typedef struct Node {
    DATA data;
    struct Node *next;
} ChainListType;

（2）定义链表操作

ChainListType *ChainListAddEnd(ChainListType *head, DATA data); //添加节点到链表末尾
ChainListType *ChainListAddFirst(ChainListType *head, DATA data); //添加节点到链表首部
ChainListType *ChainListFind(ChainListType *head, char *key); //按关键字在链表中查找内容
ChainListType *ChainListInsert(ChainListType *head, char *findkey, DATA data); //插入节点到指定位置
int ChainListDelete(ChainListType *head, char *key); //删除指定关键字的节点
int ChainListLength(ChainListType *head); //获取链表节点数量

（3）链表操作

/*
 * 添加节点到链表末尾
 * */
ChainListType *ChainListAddEnd(ChainListType *head, DATA data)
{
    ChainListType *node, *h;
    if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))) {
        printf("为保存节点数据申请内存失败!\n");
        return NULL;
    }

    node->data = data;
    node->next = NULL;

    if (head == NULL) {
        head = node;
        return head;
    }

    h = head;

    while (h->next != NULL) {
        h = h->next;
    }

    h->next = node;
    return head;
}

/*
 * 添加节点到链表首部
 * */
ChainListType *ChainListAddFirst(ChainListType *head, DATA data)
{
    ChainListType *node;
    if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))) {
        printf("为保存节点数据申请内存失败!\n");
        return NULL;
    }

    node->data = data;
    node->next = head;
    head = node;

    return head;
}

/*
 * 按关键字在链表中查找内容
 * */
ChainListType *ChainListFind(ChainListType *head, char *key)
{
    ChainListType *h;

    h = head;
    while (h) {
        if (strcmp(h->data.key, key) == 0)
            return h;
        h = h->next;
    }
    return NULL;
}

/*
 * 插入节点到指定位置
 * */
ChainListType *ChainListInsert(ChainListType *head, char *findkey, DATA data)
{
    ChainListType *node, *node1;
    if (!(node = (ChainListType *)malloc(sizeof(ChainListType)))) {
        printf("为保存节点数据申请内存失败!\n");
        return NULL;
    }

    node->data= data;
    node1 = ChainListFind(head, findkey);
    if (node1) {
        node->next = node1->next;
        node1->next = node;
    } else {
        printf("未找到插入节点!\n");
        free(node);
    }

    return head;
}

/*
 * 删除指定关键字的节点
 * */
int ChainListDelete(ChainListType *head, char *key)
{
    ChainListType *node, *h;

    h=head;
    while (h) {
        if (strcmp(h->data.key, key) == 0) {
            node = h->next; //无头节点的删除，将要删除的节点下个节点数据拷贝给删除节点，然后删除下一个节点
            h->data = node->data;  
            h->next = node->next;
            free(node);
            return 1;
        } else {
            h = h->next;
        }
    }
}

/*
 * 获取链表节点数量
 * */
int ChainListLength(ChainListType *head)
{
    ChainListType *h;
    int i = 0;

    while (h) {
        i++;
        h = h->next;
    }

    return i;
}

/*
 * 遍历链表
 * */
void ChainListAll(ChainListType *head)
{
    ChainListType *h;
    DATA data;
    h = head;
    printf("链表所有数据如下:\n");

    while (h) {
        data = h->data;
        printf("(%s,%s,%d)\n", data.key, data.name, data.age);
        h = h->next;
    }
    return;
}