阅读量:0
目录
概念
单链表是一种在物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接顺序实现的。
链表的每个结点有两个部分，分别是数据和指向下个结点的指针，每个链表的最后一个结点的下一个结点为NULL（不能对NULL解引用）。
放一张bit课件里的图,我觉得很形象：
链表的单个结点
typedef int SLDataType;//重定义一下在链表内存放的数据类型，方便后期对类型进行统一修改 //链表的单个结点 typedef struct SListNode {//Single List Node :链表结点 SLDataType data;//存放的数据 struct SListNode* next;//指向下一个结点的指针 }SLNode;//重定义名字方便后期使用链表的打印操作
//链表的打印操作 void SLPrint(SLNode* phead) { assert(phead);//不能传入空指针 SLNode* pcur = phead; //pointer cursor:指针光标，不让头结点丢失(虽然不会改变头结点的指向) while (pcur) {//等同于pcur!=NULL printf("%d->", pcur->data);//打印此结点的数据 pcur = pcur->next;//使pcur指向下一个结点 } printf("NULL\n"); }新结点的申请
后面会涉及到新结点的插入，申请新结点可以封装成一个函数，避免代码冗余
//新结点的申请 SLNode* SLBuyNode(SLDataType x) { SLNode* node = (SLNode*)malloc(sizeof(SLNode)); if (!node) {//返回值为空,申请失败(一般是空间不足了)，直接退出 perror("malloc fail"); exit(1); } node->data = x;//将数据赋给data node->next = NULL;//将下一个节点置为NULL; return node; }尾部插入
//尾部插入 void SLPushBack(SLNode** pphead, SLDataType x) { //注意在这里我们传参的是二级指针，因为我们需要在函数内部改变头结点的指向 assert(pphead);//不能传NULL //新结点的申请 SLNode* node=SLBuyNode(x); if (*pphead == NULL) { *pphead = node; } else { SLNode* pcur = *pphead; while (pcur->next) {//找到next元素为NULL的结点，也就是为链表尾部 pcur = pcur->next; } pcur->next = node; } }测试运行一下：
头部插入
//头部插入 void SLPushFront(SLNode** pphead, SLDataType x) { assert(pphead); SLNode* node = SLBuyNode(x); //这里需要处理头结点为空的情况吗？不需要，因为没有涉及到解引用其元素 node->next = *pphead; *pphead = node; } 测试运行一下：
尾部删除
//尾部删除 void SLPopBack(SLNode** pphead) { assert(*pphead && pphead);// if (!(*pphead)->next) {//处理只有一个元素的情况 free(*pphead); *pphead = NULL; } else { SLNode* prev = NULL; SLNode* pcur = *pphead; while (pcur->next) {//找到尾结点前一个结点 prev = pcur; pcur = pcur->next; } free(pcur);//将尾结点释放 pcur = NULL; prev->next = NULL;//将尾结点的前一个结点的next元素置为NULL } }测试运行一下：
头部删除
//头部删除 void SLPopFront(SLNode** pphead) { assert(*pphead && pphead); SLNode* next = (*pphead)->next;//保存头结点的下一个结点地址 free(*pphead);//释放头结点 *pphead = next;//使头结点指向下一个结点 }测试运行一下：
查找
在链表中想要对指定位置进行操作不能使用下标，所以我们必须找到指定位置的地址才能对其进行操作。
//查找 SLNode* SLFind(SLNode* phead, SLDataType x) { assert(phead); SLNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }在指定位置之前插入数据
//在指定位置之前插入数据 void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) { assert(pphead && pos && *pphead);//pos和pphead不能为空,以及pphead指向空间不能为空 if (*pphead == pos) {//处理头插的情况 SLPushFront(pphead,x); } else { SLNode* node = SLBuyNode(x); SLNode* pcur = *pphead; while (pcur->next != pos) {//找到pos前一个结点 pcur = pcur->next; } node->next = pcur->next; pcur->next = node; } }测试运行一下：
在任意位置之后插入数据
//在任意位置之后插入数据 void SLInsertAfter(SLNode* pos, SLDataType x) { assert(pos);//pos不能为空 SLNode* node = SLBuyNode(x); node->next = pos->next; pos->next = node; }测试运行一下：
删除pos结点
//删除pos结点 void SLErase(SLNode** pphead, SLNode* pos) { assert(*pphead && pphead && pos); if (*pphead == pos) {//处理头删的情况 SLPopFront(pphead); } else { SLNode* pcur = *pphead; while (pcur->next!= pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); pos = NULL; } }测试运行一下：
删除pos之后结点
//删除pos之后结点 void SLEraseAfter(SLNode* pos) { assert(pos && pos->next);//pos后面的结点也不能为空 SLNode* next = pos->next; pos->next = next->next; free(next); next = NULL; }测试运行一下：
销毁链表
//销毁链表 void SLDestory(SLNode** pphead) { assert(pphead && *pphead); SLNode* pcur = *pphead; while (pcur) { SLNode* nextnode = pcur->next;//使用一个变量接受下一个结点地址 free(pcur); pcur = nextnode; } *pphead = NULL; }