单链表专题（上）

链表的定义与创建

线性表： 1. 物理结构上不一定是线性的

2. 逻辑结构上一定是线性的

链表是一种物理存储结构上非连续，非顺序的存储结构

链表也是线性表的一种，但是在物理结构上不是连续的

链表是由一个一个的节点组成，需要数据的时候只需要申请空间即可

节点包含两个组成部分： 1. 存储的数据

2. 指向下一个节点的指针

//节点的结构演示
struct SListNode   //single list node
{int data;struct SListNode* next;  //指向下一个节点的指针
}

下面我们将详细的进行链表节点的定义：

//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;  //由于数据不止 int 一种类型，所以统一用 SLTDataType 表示 
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;

这里我们将struct SListNode 统一改写成 SLTNode

接下来，我们来学习创建几个节点：

//创建四个节点
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;

由于创建的新节点的内存情况未知，所以使用 malloc 来动态分配内存。realloc 主要用于调整已分配内存块的大小

链表的打印

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next; }printf("NULL\n");
}

但是我们一般不会像那样创建节点，而是给一个空链表去插入数据，所以下面是链表的尾插

链表的尾插

想找到进行尾插，要先找到尾节点，再将尾节点和新节点连接起来

注意：我们在尾插头插等等时，都需要用到malloc创建新的空间，重复的书写会使代码显得冗长，所以我们封装一个函数专门用于开辟空间

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//判断空间是否开辟成功if (newnode == NULL){perror("malloc failed !");exit(1); //用非零的数表示非正常退出}newnode->data = x;newnode->next = NULL;return newnode;
}

有了创建控件函数后，我们开始写尾插代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = SLTBuyNode(x);//先找尾SLTNode* ptail = phead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;
}

请注意，这里的原链表并不知道是否是空链表，若为空，则对空指针解引用是非法的。所以需要对两种情况进行讨论：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{//空链表情况SLTNode* newnode = SLTBuyNode(x);if (phead == NULL){phead = newnode;}else{//非空链表情况//先找尾SLTNode* ptail = phead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;}    
}

这里用个很重大的问题，我们传入实参 plist ，而我们需要形参改变实参，plist虽然也是指针，但他存储着一个结构体的地址，我们现在就是要修改这个地址的相关内容，所以我们需要使用二级指针来传址调用

下面是一些对应关系：

第一个节点	*plist	**pphead
指向第一个节点的指针	plist	*pphead
指向第一个节点的指针的地址	&plist	pphead

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//空链表情况SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//非空链表情况//先找尾SLTNode* ptail = *pphead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;}
}

由于节点的地址的地址不能为空，所以再加入断言，尾插代码就写好了。

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //链表不能为空SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;
}

链表的头插（相对简单）

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

链表的尾删

思路为先找到尾节点，将尾节点释放掉，由于释放了尾节点后，尾节点的上一个节点依然指向尾节点，所以还需将上一个节点置零

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);  //链表不能为空SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;
}

当链表只有一个节点的时候，此时尾节点的上一个节点并不实际存在，所以需要单独讨论

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;}
}