目录
1.链表的概念
编辑 2.链表的雏形
编辑 3.链表的组成
编辑 4.链表代码
4.1创建节点
4.2链表的打印
4.3链表的尾插
4.4链表的头插
4.5链表的尾删
4.6链表的头删
4.7链表的查找
4.8链表在指定位置之前插⼊数据
4.9链表在指定位置之后插⼊数据
4.9-1删除pos节点
4.9-2删除pos之后的节点
4.9-3销毁链表
补充：测试文件：
1.链表的概念
2.链表的雏形
3.链表的组成
4.链表代码
创建准备;
- SListNode.h文件
- SListNode.c文件
- text.c文件
4.1创建节点
数据+指向下一个节点的指针
// 首先定义数据的类型，方便后续更改
typedef int SLTNodeDataType;// 创建节点
typedef struct SListNode
{SLTNodeDataType data; // 存储数据struct SListNode* next;// 指向下一个节点的指针
}SLTNode;4.2链表的打印
头文件声明：
void SLTPrint(SLTNode* phead);执行文件代码实现：
// 链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;// 保证phead指向的位置是收节点，方便后续再次遍历while (pcur)// 等价于 pcur != NULL;{printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}4.3链表的尾插
头文件声明：
void SLTPushBack(SLTNode** pphead, SLTNodeDataType x);// 创建新的节点
SLTNode* SLTBuyNode(SLTNodeDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newnode){perror("SLTBuyNode malloc err!");exit(1);}// 创建节点成功newnode->data = x;newnode->next = NULL;// 返回return newnode;
}执行文件代码实现：
// 链表的尾插
void SLTPushBack(SLTNode** pphead, SLTNodeDataType x)
{// 传参不可为空assert(pphead);// 创建一个新的节点SLTNode* newnode = SLTBuyNode(x);// 空链表和非空链表if (*pphead == NULL){*pphead = newnode;}else{// 找尾巴SLTNode* ptail = *pphead;while (ptail->next) // 等价于ptail->next !=NULL;{ptail = ptail->next;}// 找到尾巴，开始连接ptail->next = newnode;}}4.4链表的头插
头文件声明：
// 链表的头插
void SLTPushFront(SLTNode** pphead, SLTNodeDataType x);执行文件代码实现：
// 链表的头插
void SLTPushFront(SLTNode** pphead, SLTNodeDataType x)
{// 传参不可为空assert(pphead);// 创建一个新的节点SLTNode* newnode = SLTBuyNode(x);// 头插newnode->next = *pphead;*pphead = newnode;
}4.5链表的尾删
头文件声明：
void SLTPopBack(SLTNode** pphead);执行文件代码实现：
// 链表的尾删
void SLTPopBack(SLTNode** pphead)
{// 链表不可以为空，传参不可为空assert(pphead && *pphead);// 链表有一个节点和多个节点// 一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else //多个节点{// 找尾SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail); // 释放空间ptail = NULL;// 防止野指针prev->next = NULL;}}4.6链表的头删
头文件声明：
void SLTPopFront(SLTNode** pphead);执行文件代码实现：
// 链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}4.7链表的查找
头文件声明：
SLTNode* SLTFind(SLTNode* phead, SLTNodeDataType x);执行文件代码实现：
// 链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTNodeDataType x)
{SLTNode* prev = phead;while (prev)// 等价于 prev != NULL;{if (prev->data == x){return prev;}prev = prev->next;}// 遍历完毕没有找到，返回空。return NULL;
}4.8链表在指定位置之前插⼊数据
头文件声明：
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTNodeDataType x);执行文件代码实现：
// 链表在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTNodeDataType x)
{// 不可以传入NULLassert(pphead && *pphead);assert(pos);// 创建一个新的节点SLTNode* newnode = SLTBuyNode(x);// 如果节点只有一个，就是头插if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* pcur = *pphead;// pcur所指向的节点不为pos前一个节点while (pcur->next != pos){pcur = pcur->next;}// pcur所指向的节点为pos前一个节点newnode->next = pos;pcur->next = newnode;}
}4.9链表在指定位置之后插⼊数据
头文件声明：
void SLTInsertAfter(SLTNode* pos, SLTNodeDataType x);执行文件代码实现：
// 链表在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTNodeDataType x)
{assert(pos);// 创建要插入的节点SLTNode* newnode = SLTBuyNode(x);// 开始插入newnode->next = pos->next;pos->next = newnode;
}4.9-1删除pos节点
头文件声明：
void SLTErase(SLTNode** pphead, SLTNode* pos);执行文件代码实现：
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// prev所指向的就是pos前一个节点prev->next = pos->next;free(pos);pos = NULL;}}4.9-2删除pos之后的节点
头文件声明：
void SLTEraseAfter(SLTNode* pos);执行文件代码实现：
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next); // 传过来的参数不可以为空,pos下一个的参数也不可以是NULLSLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}4.9-3销毁链表
文件声明：
void SListDesTroy(SLTNode** pphead);执行文件代码实现：
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}// 全部销毁完后，置为空NULL;*pphead = NULL;
}补充：测试文件：
//void SListNodeText01()
//{
// // 创建节点
// SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
// node1->data = 1;
//
// SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
// node2->data = 2;
//
// SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
// node3->data = 3;
//
// SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
// node4->data = 4;
//
// // 将四个节点连接起来
// node1->next = node2;
// node2->next = node3;
// node3->next = node4;
// node4->next = NULL;
//
// // 打印
// SLTPrint(node1);
//}void SLTNodeText02()
{//SLTNode* plist = NULL;// 测试尾插//SLTPushBack(&plist, 1);//SLTPushBack(&plist, 2);//SLTPushBack(&plist, 3);//SLTPushBack(&plist, 4);/*SLTPrint(plist);*/// 1->2->3->4->NULL;// 测试头插/*SLTPushFront(&plist, 5);SLTPrint(plist);SLTPushFront(&plist, 6);SLTPrint(plist);SLTPushFront(&plist, 7);SLTPrint(plist);SLTPushFront(&plist, 8);SLTPrint(plist);*/// 测试尾删//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);// 测试头删//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);// 报错//SLTPopFront(&plist);//SLTPrint(plist);// 测试查找//SLTNode* find = SLTFind(plist, NULL);//if (find == NULL)//{// printf("没有找到!\n");//}//else//{// printf("找到了!\n");//}// 测试在pos位置之前插⼊数据//SLTNode* find = SLTFind(plist, 1);//SLTInsert(&plist, find, 11);//SLTPrint(plist);// 测试链表在指定位置之后插⼊数据/*SLTNode* find = SLTFind(plist, 4);SLTInsertAfter(find, 11);SLTPrint(plist);*/// 测试删除pos之后的节点/*SLTNode* find = SLTFind(plist, 1);SLTEraseAfter(find);SLTPrint(plist);*/// 测试销毁SListDesTroy(&plist);
}int main()
{//SListNodeText01();SLTNodeText02();return 0;
}
