数据结构第三讲：单链表的实现

1.什么是单链表

单链表也是顺序表的一种，它在逻辑结构上是连续的，在物理结构上不一定是连续的

就像是火车一样，有一个火车头、很多节车厢，每相邻的车厢会通过钩子进行链接，单链表中，一节一节的车厢被成为是一个一个的节点，就像这样：

2. 节点

那么每一个节点到底是怎么样来链接的呢？其实每一个节点中只存储两个数据：需要存储的数据和指向下一个节点的指针，这样通过指针就能够找到下一个节点了

3.单链表的实现

3.1节点的结构

节点只需要存储两个内容，所以实现起来也会比较轻松：

typedef int SLTDateType;typedef struct SListNode
{//存储数据SLTDateType date;//存储框架struct SListNode* next;
}SLTNode;

3.2打印单链表

我们先使用节点结构体自行创建一些节点，然后自行将节点链接起来，如下：

	//通过动态内存分配创建节点SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->date = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->date = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->date = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->date = 4;SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));node5->date = 5;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = NULL;

然后我们实现一下链表的打印功能：
打印我们使用一个while循环即可，因为链表最后一个节点指向的空间为NULL，所以我们可以以此为一个突破点，作为循环的终止条件，实现如下：

void SLTPrint(SLTNode* phead)
{//对于打印，使用一个循环即可SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->date);pcur = pcur->next;}printf("NULL\n");
}

3.3申请一个新节点

上述我们自行申请的一个新节点太过于费事费力了，我们应该试着写一个函数，让函数来帮我们申请空间，实现起来也不困难：

//申请一个新节点
SLTNode* SLBuyNode(SLTDateType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc faile!");exit(1);}node->date = x;node->next = NULL;return node;
}

3.4单链表尾部插入

看图：

我们只需要找到链表的末端，将最后一个节点中的地址指向新的节点，然后将新的节点中的指针指向NULL即可：

//单链表尾部插入
//注意：这里要使用二级指针，因为如果链表中没有节点时，我们要改变头指针的值，让它指向第一个节点的地址
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);//对于插入，首先都要先创建一个节点，才能够实现插入SLTNode* newnode = SLBuyNode(x);//插入方法//1.找到最后一个节点if (*pphead == NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}

3.5单链表头部插入

只需要将刚开辟节点中的指针指向原来的头节点地址，并改变头节点的指向即可：

//单链表头部插入
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = SLBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

3.6单链表的尾部删除

只需要将最后一个节点的空间释放掉，然后将释放后的最后一个节点中的指针指向NULL即可，需要注意的是：这里需要找到释放位置前的节点，当只存在一个节点时，最后一个节点前的空间是不能够进行访问的，这里需要单独讨论：

//单链表尾部删除
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//将只有一个节点的情况单独讨论if ((*pphead)->next == NULL)//这里要注意:->的优先级要大于* 所以要将*pphead加上小括号{free(*pphead);*pphead = NULL;}else{//先找到最后一个数据的前一个数据SLTNode* pcur = *pphead;SLTNode* prev = NULL;while (pcur->next){prev = pcur;pcur = pcur->next;}prev->next = NULL;free(pcur);pcur = NULL;}
}

3.7单链表头部删除

头部删除相对简单，只需要释放空间，然后改变头指针的位置即可：

//单链表头部删除
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* prev = (*pphead)->next;free(*pphead);*pphead = prev;
}

3.8查找

查找查找的是数据所在的位置，返回的是节点的地址：

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDateType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->date == x){return pcur;}pcur = pcur->next;}return NULL;
}

3.9在指定位置之前插入数据

在指定位置之前插入数据，需要找到指定位置前的那个节点，这里还需要单独讨论，因为当只存在一个节点时，前面的空间是无法访问的，和上边一样，然后我们只需要改变节点中指针的指向即可

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);//当在第一个节点前进行插入时if (*pphead == pos){SLTPushFront(pphead, x);}else{//先创建一个节点SLTNode* newnode = SLBuyNode(x);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = newnode;newnode->next = pos;}
}

3.10在指定位置之后插入数据

在指定位置之后插入数据，因为已经知道了在哪个位置进行插入，所以我们就能够直接找到下一个节点的地址，直接改变地址指向即可：

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);//先创建一个节点SLTNode* newnode = SLBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

3.11删除pos节点

删除节点，只需要释放空间，改变指针指向即可：

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(*pphead && pphead);if (*pphead == pos){SLTPopFront(pphead);}else{SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

3.12删除pos之后的节点

释放空间，改变指向：

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);pos->next = pos->next->next;free(pos->next);pos->next = NULL;
}

3.13销毁链表

使用循环销毁即可：

//销毁链表
void SListDestory(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* prew = *pphead;while (prew){SLTNode* pcur = prew->next;free(prew);prew = pcur;}*pphead = NULL;
}