本文所讲的链表是单链表，链表采用无头链表
科普下：一般链表可以分为有头节点的链表与无头节点的链表
- 有头节点的链表：每个节点存储这个一个或者一组数据，但是有头节点的链表的第一个节点是头节点，头节点只是一个节点，但不存储数据，头节点的主要作用是方便插入操作
- 无头节点的链表：每个节点都是有效节点，都存储有效的数据
至于为什么用无头节点，是因为刚实习的时候被领导说了使用有头节点的链表是浪费内存，好吧！！
（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;
}
