1-4 C单向链表

1.0 基本概念

线性表的顺序存储：用一块连续的内存空间，线性表的链式存储：不连续的内存空间

链表是由一系列的节点组成，每个节点包含两个域，一个是数据域，一个是指针域

程序框架

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>// 链表节点
typedef struct LINKNODE
{// 使用无类型的指针：该指针可以指向任何类型的数据void *data;struct LINKNODE *next;
} LinkNode;// 链表结构体
typedef struct LINKLIST
{LinkNode *head;int size;// 根据需要申请内存，没有容量的概念
} LinkList;// 打印回调函数指针
typedef void (*PRINTLINKNODE)(void *);// 初始化链表
LinkList *Init_LinkList();// 在指定的位置插入
void Insert_LinkList(LinkList *list, int pos, void *data);// 删除指定位置的值
void RemoveByPos_LinkList(LinkList *list, int pos);// 获得链表的长度
int Size_LinkList(LinkList *list);// 查找链表
int Find_LinkList(LinkList *list, void *data);// 打印链表节点
void Print_LinkList(LinkList *list, PRINTLINKNODE print);// 返回第一个节点
void *Front_LinkList(LinkList *list);// 释放链表内存
void FreeSpace_LinkList(LinkList *list);#endif

2.0 初始化链表

开辟链表空间，设置链表的大小为0，设置链表节点，因为链表也是一个节点，初始化的值为NULL返回头节点的地址，头节点不存储数据。

LinkList *Init_LinkList(void)
{LinkList *header = (LinkList *)malloc(sizeof(LinkList));header->size = 0;header->head = (LinkNode *)malloc(sizeof(LinkNode));header->head->next = NULL;header->head->data = NULL;return header;
}

2.0 插入数据

原理：找到要删除节点的前一个节点，然后创建一个新的节点，将插入位置前一个节点指向新创建的链表节点，然后链表节点再指向后面的节点。

注：也就是插入到2这个节点的位置，那么就是找到插入节点的前面一个节点，通过前面
一个节点，可以拿到插入节点的位置，newnode->next =pCurrent->next，pCurernt->next =newnode插入节点。

参考代码：

程序实现：

void Insert_LinkList(LinkList *list, int pos, void *data)
{if (list == NULL){return;}if (data == NULL){return;}if ((pos < 0) || (pos > list->size)){pos = list->size;}LinkNode *newnode = (LinkNode *)malloc(sizeof(LinkNode));newnode->data = (void *)data;newnode->next = NULL;LinkNode *pCurrent = list->head;for (int i = 0; i < pos; i++){pCurrent = pCurrent->next;}newnode->next = pCurrent->next;pCurrent->next = newnode;list->size++;
}

3.0 删除数据

删除节点也就是2号位置的节点，pCurrent->next= pNext->next，free(pNext) 上一个节点指向下一个节点的下一个节点，然后再释放掉节点就将节点的东西删除掉了。

程序参考：

程序实现：

void RemoveByPos_LinkList(LinkList *list, int pos)
{if (list == NULL){return;}if (pos < 0 || pos >= list->size){return;}LinkNode *pCurrent = list->head;for (int i = 0; i < pos; i++){pCurrent = pCurrent->next;}LinkNode *pDel = pCurrent->next;pCurrent->next = pDel->next;free(pDel);list->size--;
}

4.0 获取链长度

// 获得链表的长度
int Size_LinkList(LinkList *list)
{return list->size;// return 0;
};

5.0 查询链表

// 查找链表
int Find_LinkList(LinkList *list, void *data)
{if (list == NULL){return -1;}if (data == NULL){return -1;}// 遍历查找，使用辅助指针变量LinkNode *pCurrent = list->head->next;int i = 0;while (pCurrent != NULL){if (pCurrent->data == data){break;}i++;pCurrent = pCurrent->next;}return i;
};

6.0 返回第一个节点

// 返回第一个节点
void *Front_LinkList(LinkList *list)
{// 返回的第一个节点就是头结点的下一个节点return list->head->next->data;
};

7.0 打印链表节点

// 打印链表节点
void Print_LinkList(LinkList *list, PRINTLINKNODE print)
{if (list == NULL){return;}// 辅助指针变量LinkNode *pCurrent = list->head->next;while (pCurrent != NULL){print(pCurrent->data);pCurrent = pCurrent->next;}
};

8.0 释放内存

// 释放链表内存
void FreeSpace_LinkList(LinkList *list)
{if (list == NULL){return;}// 辅助指针变量LinkNode *pCurrent = list->head;while (pCurrent != NULL){// 缓存下一个节点LinkNode *pNext = pCurrent->next;pCurrent = pNext;}// 释放链表内存list->size = 0;free(list);
};

9.0 链表调用

程序实现：

int main(void)
{void MyPrint(void *data);// 创建链表LinkList *list = Init_LinkList();// 创建数据Person p1 = {"aa", 18, 100};Person p2 = {"hh", 22, 120};Person p3 = {"zz", 23, 150};Person p4 = {"qq", 12, 180};Person p5 = {"ww", 88, 888};// 将数据插入链表Insert_LinkList(list, 0, &p1);Insert_LinkList(list, 0, &p2);Insert_LinkList(list, 0, &p3);Insert_LinkList(list, 0, &p4);Insert_LinkList(list, 0, &p5);// 打印Print_LinkList(list, MyPrint);// 删除3号元素RemoveByPos_LinkList(list, 3);// 打印printf("-----------------------\n");Print_LinkList(list, MyPrint);// 返回第一个节点printf("-----------------------\n");Person *ret = (Person *)Front_LinkList(list);printf("Name = %s Age = %d Score = %d\n", ret->name, ret->age, ret->score);// 销毁链表FreeSpace_LinkList(list);printf("\n");system("pause");return 0;
}

运行以上程序输出如下结果：