单链表基本操作(C语言)
目录一、链表的介绍二、单链表的实现1、定义单链表2、接口函数1)打印函数2)创建结点3)尾插4) 头插5) 尾删6)头删7) 查找8) 修改9) 指定位置前插入10)删除指定位置节点11)指定位置后插入节点12) 删除指定位置后的节点首先我们回顾一下线性表的两种存储方式--顺序存储和链式存储在中已经讲解过了顺序存储的方式,对于顺序表的优缺点总结来说就是,查找方便,增删复杂。而链表...
目录
首先我们回顾一下线性表的两种存储方式--顺序存储和链式存储
在中已经讲解过了顺序存储的方式,对于顺序表的优缺点总结来说就是,查找方便,增删复杂。
而链表的特点恰恰相反,增删方便,查找复杂。顺序表可以直接通过下标访问,而链表必须走O(N)去查找。
一、链表的介绍
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数组元素的逻辑顺序是通过链表中的指针链接次序实现的。
今天实现的是链表中最简单的一种链表--单链表(每个结点中只含有一个指针域)
对于链表我们只知道它每个结点的存储的物理地址是不连续的。但逻辑上还是符号线性表‘”一对一“的特点。因此我们要用”线“(指针)把这些不连续的结点按顺序连接起来。
二、单链表的实现
1、定义单链表
到这里我们可以发现,要想表示链表中的结点,光靠存储结点的数据是不够的,还得有指针。因此,单链表的结构特点如下:
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType date;//数据域
struct SListNode* next;//指针域
}SLTNode;
注意:因为指针是指向每个结点的,也就是指向 SLTNode这个自定义的结构体类型,所以指针的类型是结构体指针。
2、接口函数
void SListPrint(SLTNode* phead); //打印函数
SLTNode* BuySListNode(SLTDateType x); //创建新的节点
void SListPushBack(SLTNode** phead, SLTDateType x); //尾插
void SListPushFront(SLTNode** phead, SLTDateType x); //头插
void SListPopBack(SLTNode** pphead); //尾删
void SListPopFront(SLTNode** pphead); //头删
SLTNode* SListFind(SLTNode* phead, SLTDateType x); //查找
void SListModify(SLTNode* phead, SLTDateType x,SLTDateType va); //修改
void SListInsert(SLTNode** pphead, SLTNode* pos,SLTDateType x); //指定位置前插入元素
void SListErase(SLTNode** pphead, SLTNode* pos); //删除指定位置元素
void SListInsertAfter(SLTNode* pos,SLTDateType x); //指定位置后插入元素
void SListERaseAfter(SLTNode* pos); //删除指定位置后的元素
1)打印函数
打印函数并没有什么难度,只要将头部节点传参过来,该函数就可以向后挨个访问元素。
void SListPrint(SLTNode* phead)
{
assert(phead);
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->date);
cur = cur->next;
}
printf("NULL\n");
}
解读:我们想实现单链表的打印,我们就需要遍历整个链表。首先创建一个结构体指针 cur 来存放 phead ,然后通过 cur 来把整个链表走一遍。只要 cur 不为 NULL,就说明还没有走完,就进入循环,循环体内打印出当前 cur->data 的内容,就实现了打印节点中的内容,随后将 cur 赋值成 cur->next ,使得 cur 指向它后面的节点。当 cur 为 NULL 时说明已经走完了,则跳出循环。最后我们再打印一个 "NULL" 把链表的尾部表示出来(便于调试观看)。
可以自己构造一些链表节点尝试打印
void testSList1()
{
SLTNode* n1 =(SLTNode*) malloc(sizeof(SLTNode));
assert(n1);
SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n2);
SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n3);
SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
assert(n4);
n1->date = 1;
n2->date = 2;
n3->date = 3;
n4->date = 4;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = NULL;
SListPrint(n1);
}
2)创建结点
当我们要插入新的元素时都需要创建新的节点,所以我们可以单独创建一个函数
SLTNode* BuySListNode(SLTDateType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
assert(newnode);
newnode->date = x;
newnode->next = NULL;
return newnode;
}
其中x是你要插入的新元素,next指向的应该是下一个结点,这里是单独创建,没有可以指向的空间,函数返回时需要注意让它指向下一个结点。如果是尾插则不需要。
3)尾插
2种情况:1、正常插入尾部即可
2、如果是空链表,那我们插入的结点就是新的首地址,则改变了原来的首地址
在函数传参种如果想改变实参,则需要传递实参的地址,也就是说,如果要改变首地址,则需要传递首地址的地址,那就需要用二级指针来接收实参。
代码实现:
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
SLTNode* newnode = BuySListNode(x);//创建新的结点
if (*pphead == NULL)//如果为空链表,则头部结点变
{ //成要插入的结点
*pphead=newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)//找尾部
{
tail = tail->next;
}
tail->next = newnode;//找到之后把尾部指向的空间改为插入的空间
}
}
提醒:如果我们要遍历寻找某个位置,需要提前把首结点的地址保存下来,避免你的指针迷路哦~
4) 头插
思路:和尾插类似,头部插入一定是要改变头部指针的,所以需要二级指针。
//头插
void SListPushFront(SLTNode** phead, SLTDateType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *phead;
*phead = newnode;
}
5) 尾删
2种情况:1)正常删除,即找到尾部的前一个结点,把指向尾部的指针置为空,并释放尾部
2)该链表只有一个结点,则直接释放掉,置为空。这里修改了首结点,需要二级指针
//尾删
void SListPopBack(SLTNode** pphead)
{
assert( pphead);
assert(*pphead);
SLTNode* tailPrev = *pphead;
SLTNode* tail = *pphead;
//只有一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (tail->next != NULL)//找尾部
{
tailPrev = tail;//前一个结点
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
6)头删
删除第一个结点依然需要修改头部指针,用二级指针,需要注意删空的情况哦~
/头删
void SListPopFront(SLTNode** pphead)
{
assert(*pphead);//避免删空后继续删除
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
7)查找
分析:查找用不上二级指针,因为不需要修改链表的内容。函数返回结果为 SLTNode*
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->date == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
8)修改
分析:修改只需要在查找的基础上传递直接修改后的值即可,原理也十分简单
这里修改的是malloc开辟的变量,并不是栈种的变量,所以不用二级指针。
//修改
void SListModify(SLTNode* phead, SLTDateType x,SLTDateType va)
{
SLTNode* value = SListFind(phead, x);
value->date = va;
}
9) 指定位置前插入
分析:
Step1:首先创建新节点。分为两种情况,第一种情况是直接头插,第二种情况就是要找 pos 的前面一个结点的位置。我们首先看第一种情况,如果 *ppHead == pos 就直接头插就行了,先让新节点的 next 指向头结点,然后再更新头结点就行。这里你也可以直接调用 SListPushFront,但是头插代码就2行,所以这里就直接写了。
Step2:第二种情况,我们定义一个结构体指针 posPrev 用来找 pos 的前一个位置,如果 prev-> next 还不是 pos 就进入循环,让 prev 往下走,直到 prev->next 为 pos,也就找到 pos 前一个位置了。
Step3:找到 pos 前一个位置后就可以插入了,直接把 newnode 交给 prev->next ,此时 newnode 默认指向 NULL,还要把 pos 交给 newnode->next 。
//在pos前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
assert(pphead);
if (*pphead == pos)
{
SListPushFront(*pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
10)删除指定位置节点
分析:step1:只有一个结点,即删除头部元素
step2: 定义一个prev查找pos的前一个结点,找到后先将pos->next=pos->next,然后就可以将pos free掉了。这里的pos不能为空,不然是无法删除的,free后可置空。
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (*pphead == pos)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
11)指定位置后插入节点
这里是后续补充的,理解就行,原理不难
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
assert(pos);
//SLTNode* newnode = BuySListNode(x);
//newnode->next = pos->next;
//pos->next = newnode;
SLTNode* newnode = BuySListNode(x);
SLTNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}
12) 删除指定位置后的节点
void SListERaseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}
由于作者水平有限,本文有错误和不准确之处在所难免,本人也很想知道这些错误,恳望读者批评指正!
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)