C语言（16）——初识单链表

1.链表的概念及结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

结构图：

补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、节点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

2.单链表的实现

SList.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** phead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** Node);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** phead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
//创建空间
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
//尾删
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;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//->的优先级大于*free(*pphead);*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur)//等价于pcur != NULL{if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur == NULLreturn NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);//若pos == *pphead;说明是头插if (pos == *pphead){SLTPushFront(pphead, x);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posnewnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos -> newnode -> pos->nextnewnode->next = pos->next;pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//pos是头结点/pos不是头结点if (pos == *pphead){//头删SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//pos del del->nextpos->next = del->next;free(del);del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//pcur*pphead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SListTest02()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);//SLTPrint(plist); // 1->2->3->4->NULL//SListDesTroy(&plist);//SLTPrint(plist);//测试查找SLTNode* find = SLTFind(plist, 1);SLTInsert(&plist, find, 11);SLTInsertAfter(find, 11);/*删除pos节点*//*SLTErase(&plist, find);SLTEraseAfter(find);*/SLTPrint(plist);if (find == NULL){printf("没有找到！\n");}else {printf("找到了！\n");}//SLTPushBack(NULL, 5);////测试头插//SLTPushFront(&plist, 6);//SLTPrint(plist);//SLTPushFront(&plist, 7);//SLTPrint(plist);//SLTPushFront(&plist, 8);//SLTPrint(plist);//测试头删//SLTPopFront(&plist);//SLTPrint(plist);// 2->3->4->NULL//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPrint(plist);}int main()
{//SListTest01();SListTest02();return 0;
}