前言
这次我来为大家讲解链表,首先我们来理解一下什么是单链表,我们可以将单链表想象成火车
每一节车厢装着货物和连接下一个车厢的链子,单链表也是如此,它是将一个又一个的数据封装到节点上,节点里不仅包含着数据,还又指向下一个节点的指针。
因此单链表的结构体表示如下:
typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SListNode;
所以单链表的特点是:
在物理结构上不一定是线性的
在逻辑结构上是线性的
我们通常会将单链表抽象成如下图所示: 这样会方便我们接下来的思考和代码的实现。
单链表代码实现
打印
我们先来写打印代码,这个代码也方便我们后期的测试。
打印单链表,我们需要遍历单链表的所有数据,这个函数的形参传一级指针就可以了,因为打印并不需要改变头指针。
void SListPrint(SListNode* phead)
{SListNode* ptail = phead;while (ptail){printf("%d->", ptail->data);ptail = ptail->next;}printf("NULL\n");
}
这里定义一个变量ptail,是为了不想改变phead,说不定哪天要在这个函数再次使用phead,所以我定义了一个ptail来进行遍历,以便后面想使用phead的时候,可以快速增加代码
创建新节点
鉴于插入数据都需要创建一个新节点,为了方便后面的头插,尾插等各种插入,于是我们来封装一个函数来创建新节点:
SListNode* CreatNewnode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
尾插
尾插需要在单链表的尾部插入一个新的数据,画图理解一下:
需要我们找到单链表原先的尾节点,将尾节点的next指向newnode,于是我们很快就会写出如下的代码:
void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;
}
由于上面的代码是基于链表不为空这一种情况实现的,这时候我们还要思考,如果链表为空的时候,上面的代码还能实现吗?
我们来走一下代码,如果链表为空,pcur==NULL,pcur->next一定会报错,对空指针是不能解引用的,所以上面的代码无法处理链表为空的情况,我们就需要单独进行处理!!!
这个尾插代码应该是这样的:
void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//如果链表为空if (*pphead == NULL){*pphead = newnode;}else{//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}
所以当链表为空的时候,我们需要改变头指针的指向,所以传二级指针!!!
头插
头插需要我们在单链表的最前面插入一个数据,我们画图来理解一下:
头插很显然要改变头指针,所以形参要影响实参需要传二级指针。
这时候是先newnode指向原先的第一个节点,再改变phead?还是先改变phead再将newnode 指向原先的第一个节点?
在不创建另外一个变量的时候,我们要找到原先第一个节点只能通过phead->next,如果先改变了phead 的话,我们就找不到原先的第一个节点了。
所以需要将新节点的next指向原先的第一个节点,然后我们将头指针改变,指向新节点。
void SListPushFront(SListNode** pphead, SLTDataType x)//头插
{assert(pphead);SListNode* newnode = CreatNewnode(x);newnode->next = *pphead;*pphead = newnode;
}
这个时候,由于上面的代码还是基于链表不为空的条件下进行的,所以我们还要考虑链表为空的情况,走一下代码,*pphead == NULL,newnode->next = NULL,*phead = newnode ,很显然这个代码也能处理好链表为空的情况,于是我们不需要任何的改动。
尾删
尾删指删除单链表最后一个节点。画图理解一下:
这时候我们需要找到尾节点和尾节点的前一个节点,将尾节点释放掉,改变现在的尾节点的next指向,置为NULL。
所以我们需要两个临时变量,一个来遍历链表找到尾节点,一个来保存上一个节点!!!
这时我们来写代码:
void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL,链表也不能为空//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}
这里我们需要断言一下,就是链表不能为空,链表为空,删什么?
上面的代码是基于链表至少又两个节点的情况下,如果链表只有一个节点呢?也就是头指针指向的就是你要尾删的节点,走一下代码:*pphead == NULL,pcur = prev =NULL,此时while(pcur->next),对空指针解引用,直接报错,既然如此,我们就写多一点代码来专门处理只有一个节点的情况。
void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL,链表也不能为空//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}
}
由于可能会出现只有一个节点的情况,删除的话也需要改变头指针,所以传二级指针。
头删
头删指删除第一个节点。画图理解一下:
我们需要改变头指针的指向,所以必须传二级指针!!!
void SListPopFront(SListNode** pphead)//头删
{assert(pphead && *pphead);//不能传NULL,链表也不能为空SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
老规矩,如果链表只有一个节点,走一下代码:SListNode->next = (*pphead) -> next =NULL; 释放掉第一个节点,*pphead = next = NULL,刚好可以处理这种情况,代码不需要修改。
查找
写查找代码也是方便我们后续的指定位置的插入删除作准备。
这个代码和简单,只需要遍历单链表。
SListNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
删除指定节点
我们画图理解一下:
我们需要改变两个个节点,pos前一个节点的next指向改成pos后一个节点。
void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
如果pos节点就是第一个节点(即pphead == pos),我们来走一下代码,在while循环中pcur->next 不会找到pos,因为pcur = *phead = pos,所以循环最后会导致pcur走到NULL,然后发生对空指针的解引用,所以我们需要单独处理这一种情况
void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){//调用头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}
由于pos 就是头指针,所以pos的删除就是头删,我们可以调用我们之前写好的头删函数,无论你要不要调用头删函数,都要对头指针进行修改,所以要传二级指针(头指针的地址)。而pos不需要传二级指针是因为一般情况下我们不会再次使用pos,所以我们不需要改变pos的指向,也就不用传pos 的地址过去。
删除指定位置之前的数据
画图理解:
我们需要找到pos前两个节点,释放pos 前一个节点,改变pos前前节点的next 的指向,变为指向pos这个节点。
void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}
我们要考虑一下如果pos前面只有一个节点的情况下,我们来走一下代码:当prev->next = pos(pphead = pos),释放pcur(也就是释放了pphead)。这时候头指针没了,你找不到后面的数据了!!!
所以我们单独处理一下这种情况。
void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);if ((*pphead)->next == pos){//头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}
}
头删,需要改变头指针的指向,所以要用二级指针来接收头指针的地址。
删除指定位置之后的数据
画图理解:
由于我们可以通过pos 就可以找到pos后面的节点,所以我们直接传pos就可以了。
我们需要找到pos后后一个节点,然后改变pos 的next 指向指向后后一个节点,为了方便书写代码,我们可以定义一个临时变量del来保存要删除的节点。
这里要注意,指定位置之后必须要有一个节点,否则删什么?所以这里断言一下。
void SListPopPosAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
我们来考虑一下,如果要删除的节点刚好是尾节点,我们来走一下代码:pos->next = del->next = NULL;free(del),没有问题,那就不用单独处理。
指定位置前插入
画图理解一下:
我们需要改变前一个节点,为了找到pos 的前一个结点,我们需要传入头指针对链表进行遍历。
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;
}
如果pos就是第一个节点,上面的代码中while循环就无法找到pos前一个节点,所以我们要单独处理一下这种情况,这时可以调用一下我们写过的头插函数。
头插,需要改变头指针,所以传二级指针。
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头插SListPushFront(pphead, x);}else{SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}
指定位置之后插入
画图理解一下:
这个代码我们可以通过pos找到pos后一个节点,所以不需要传入头指针。
void SListPushPosAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* next = pos->next;pos->next = newnode;newnode->next = next;
}
我们来考虑一下pos就是尾节点的情况,能不能走得通,走一下代码,next = pos->next = NULL,pos->next = newnode,newnode->next = next = NULL,可以,没有任何问题,就不需要改代码了。
销毁链表
销毁链表需要一个一个节点依次删除,所以要遍历链表。
void SListDestroy(SListNode** pphead)
{SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
测试
每写完一个函数,我们就需要进行调试测试来看代码有没有问题,这时一个好的习惯,希望各位也能这样做。
一下是我自己的测试代码:我放在了test.c文件里(就是测试文件)
#include "SList.h"void test1()
{SListNode* plist = NULL;//测试尾插//SListPushBack(&plist, 1);//SListPrint(plist);//SListPushBack(&plist, 2);//SListPrint(plist);//SListPushBack(&plist, 3);//SListPrint(plist);//测试头插SListPushFront(&plist, 10);SListPrint(plist);SListPushFront(&plist, 20);SListPrint(plist);SListPushFront(&plist, 30);SListPrint(plist);//测试尾删/* SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);SListPopBack(&plist);SListPrint(plist);*///测试头删//SListPopFront(&plist);//SListPrint(plist);//SListPopFront(&plist);//SListPrint(plist);//SListPopFront(&plist);//SListPrint(plist);//测试查找/* SListNode* find = NULL;find = SListFind(plist, 30);*//* if (find == NULL){printf("找不到\n");}else{printf("找到了!%d\n", find->data);}*///测试删除pos节点/*SListPopPos(&plist, find);SListPrint(plist);*///删除指定位置之前的数据//SListPopPosFront(&plist, find);//SListPrint(plist);//删除指定位置之后的数据/* SListPopPosAfter(find);SListPrint(plist);*///指定位置前插入/* SListPushPosFront(&plist, find, 100);SListPrint(plist);*///指定位置之后插入/* SListPushPosAfter(find, 100);SListPrint(plist);*/SListDestroy(&plist);SListPrint(plist);
}int main()
{test1();return 0;
}
分装函数
SList.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{int data;struct SListNode* next;
}SListNode;//打印
void SListPrint(SListNode* phead);//插入
void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//头插//删除
void SListPopBack(SListNode** pphead);//尾删
void SListPopFront(SListNode** pphead);//头删//查找
SListNode* SListFind(SListNode* phead, SLTDataType x);//删除pos节点
void SListPopPos(SListNode** pphead, SListNode* pos);//删除指定位置之前的数据
void SListPopPosFront(SListNode** pphead, SListNode* pos);//删除指定位置之后的数据
void SListPopPosAfter(SListNode* pos);//指定位置前插入
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x);//指定位置之后插入
void SListPushPosAfter(SListNode* pos, SLTDataType x);//销毁链表
void SListDestroy(SListNode** pphead);
SList.c
#include "SList.h"//创建新节点
SListNode* CreatNewnode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//打印
void SListPrint(SListNode* phead)
{SListNode* ptail = phead;while (ptail){printf("%d->", ptail->data);ptail = ptail->next;}printf("NULL\n");
}//插入
void SListPushBack(SListNode** pphead, SLTDataType x)//尾插
{assert(pphead);SListNode* newnode = CreatNewnode(x);//如果 *pphead==NULLif (*pphead == NULL){*pphead = newnode;}else{//找尾节点SListNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}pcur->next = newnode;}
}void SListPushFront(SListNode** pphead, SLTDataType x)//头插
{assert(pphead);SListNode* newnode = CreatNewnode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopBack(SListNode** pphead)//尾删
{assert(pphead && *pphead);//不能传NULL,链表也不能为空//链表只有一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾节点SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next){prev = pcur;pcur = pcur->next;}free(pcur);pcur = NULL;prev->next = NULL;}
}void SListPopFront(SListNode** pphead)//头删
{assert(pphead && *pphead);//不能传NULL,链表也不能为空SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//删除pos节点
void SListPopPos(SListNode** pphead, SListNode* pos)
{assert(pphead && *pphead);assert(pos);if (pos == *pphead){//调用头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}//删除指定位置之前的数据
void SListPopPosFront(SListNode** pphead, SListNode* pos)
{assert(pphead && pos); assert(pos != *pphead);if ((*pphead)->next == pos){//头删SListPopFront(pphead);}else{SListNode* pcur = *pphead;SListNode* prev = *pphead;while (pcur->next != pos){prev = pcur;pcur = pcur->next;}prev->next = pos;free(pcur);pcur = NULL;}
}//删除指定位置之后的数据
void SListPopPosAfter(SListNode* pos)
{assert(pos && pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//指定位置前插入
void SListPushPosFront(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);if (*pphead == pos){//头插SListPushFront(pphead, x);}else{SListNode* newnode = CreatNewnode(x);SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}//指定位置之后插入
void SListPushPosAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode* newnode = CreatNewnode(x);SListNode* next = pos->next;pos->next = newnode;newnode->next = next;
}//销毁链表
void SListDestroy(SListNode** pphead)
{SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
单链表完结撒花!!!