单链表概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1. 函数的声明部分
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLTDateType; typedef struct SingleListNode { SLTDateType data; struct SingleListNode* next; }SLTNode; //打印 void SLTPrint(SLTNode* phead); //头插 void SLTPushFront(SLTNode** pphead, SLTDateType x); //尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x); //头删 void SLTPopFront(SLTNode** pphead); //尾删 void SLTPopBack(SLTNode** pphead); //在pos位置之后插入x void SLTInsertAfter(SLTNode* pos, SLTDateType x); //删除pos位置之后的值 void SLTEraseAfter(SLTNode* pos); //单链表查找 SLTNode* SLTFind(SLTNode** pphead, SLTDateType x);
2. 函数的实现部分
由于头插，尾插等需要开辟一个节点，所以把开辟节点单独作为一个函数，需要开辟节点的时候直接调用；
SLTNode* BuyListNode(SLTDateType x) { //开辟一个节点 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); assert(newnode); //对newnode初始化 newnode->data = x; newnode->next = NULL; return newnode; }
（1）打印链表
//打印 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
（2）头插
头插需要传二级指针，因为在调用函数SLTPushFront的时候，实参plist本来是结构体指针，现在头插需要改变链表的头，即需要传地址去改变plist的头；
如进行以下操作，值传递操作：
假设链表是如下形式：
当头插函数使用一级指针接收实参时，实参和形参同为一级指针，它们是同等类型的，它们在两个不同的栈空间，假如进行以下操作：
实际上phead并不会改变plist的值：
因为它们两个在不同的栈空间，phead只是plist的临时拷贝，只要出了SLTPushFront这个函数，栈帧被销毁，phead也被销毁了，但是phead的改变也没有改变plist的值，所以相当于什么也没有发生；
所以需要传二级指针，存放plist的指针，到函数内部需要解引用找到plist，再去改变plist的值，这样才能达到我们想要的效果；
//头插 void SLTPushFront(SLTNode** pphead, SLTDateType x) { SLTNode* newnode = BuyListNode(x); //将newnode的next更新为原来的头节点 newnode->next = *pphead; //将newnode更新为新的头节点 *pphead = newnode; }
（3）尾插
尾插的时候，当链表为空时，需要改变的是plist这个结构体指针，所以这个时候也是要传二级指针；当链表为非空链表时，需要改变的是结构体，所以不需要用到二级指针；但为了防止链表为空，这里干脆直接传二级指针；
//尾插 void SLTPushBack(SLTNode** pphead, SLTDateType x) { SLTNode* newnode = BuyListNode(x); //空链表 if (*pphead == NULL) { *pphead = newnode; } //非空链表 else { SLTNode* tail = *pphead; while (tail->next) { tail = tail->next; } tail->next = newnode; } }
（3）头删
//头删 void SLTPopFront(SLTNode** pphead) { //没有节点 assert(*pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //多个节点 else { SLTNode* cur = *pphead; *pphead = cur->next; free(cur); cur = NULL; } }
（4）尾删
//尾删 void SLTPopBack(SLTNode** pphead) { //空链表 assert(*pphead); //一个节点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } //多个节点 else { SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
（5）单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
（6）删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* cur = pos; cur->next = cur->next->next; }
（7）在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDateType x) { SLTNode* cur = BuyListNode(x); assert(cur); cur->next = pos->next; pos->next = cur; }
3. 函数的测试部分
#define _CRT_SECURE_NO_WARNINGS 1 #include "Single List.h" int main() { SLTNode* plist = NULL; SLTPushFront(&plist, 2); SLTPushFront(&plist, 1); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); //SLTPopFront(&plist); //SLTPopBack(&plist); //SLTInsertAfter(plist->next->next, 10); SLTEraseAfter(plist); SLTPrint(plist); SLTNode* ret = SLTFind(plist, 5); if (ret != NULL) { printf("%d->", ret->data); } else { printf("NULL\n"); } SListDestroy(&plist); return 0; }
