阅读量:0
数据结构第三讲：单链表的实现
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; } 