C语言单链表

阅读本书更多章节>>>>

目录

一.链表的概念及结构

1.概念：

2.结构：

二.单链表的接口声明

三.单链表实现接口:

(1).增加节点：

 1.创建新节点：

2.在头部增加节点：

3.在尾部增加节点：

4.在指定位置前面增加：

5.在指定位置后面增加：

(2).删除节点：

1.删除头部节点：

2.删除尾部节点：

3.删除指定位置的节点：

4.删除指定位置后面节点：

---

C语言实现顺序表(增,删,改,查)-CSDN博客https://blog.csdn.net/lh11223326/article/details/137008884?spm=1001.2014.3001.5501

一.链表的概念及结构

1.概念：

链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。如下图:

现实中数据结构中

注意:

从上图可以看出，链表结构在逻辑上是连续的，但是在物理上不一定连续。现实中的节点一般都是从堆上申请出来的。从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

2.结构：

链表分为单链表和双链表，带头或不带头，循环或者非循环，实际中最常用的只有两种结构:

无头单向非循环链表：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。带头双向循环链表：结构最复杂，一般用在单独存储数据，实际使用的链表数据结构，都是带头双向循环链表，另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而更简单了。

二.单链表的接口声明

如下代码是各种接口(只提供功能的实现，而不需要了解其原理)的声明,文件为.h： 

创建链表之前需要一个结构体用来当做链表的节点,如，data代表数据，next代表用来把内容链接起来的指针。代码如下：

typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;}SLTNode;

然后需要添加节点的函数，也就是BuySListNode，创建好的节点需要返回出去，所以函数的类型就是结构体的类型。如下

SLTNode* BuySListNode(SLTDataType x);

总所周知单链表的头插头删的速度是最快的为O(1)，但头插头删的话一般需要找到对应的地址，又因为我们使用的是指针指向的节点，所以参数列表为指针的指针，也就是二级指针所以是**，但是尾节点跟中间增加和删除的速度不是那么理想,中间的效率为O(n)这里的n是链表头距离要插入的位置，尾的效率为O(N)这里n是整个链表的长度。

头部增加节点,一个是指向链表的指针，还有一个是要添加的数据:

void SLTPushBack(SLTNode** pphead, SLTDataType x);//头增加

因为都是增加节点所以参数跟头结点并无区别。

void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾增加

而头部删除和尾部删除，不用数据参数只需要一个指针参数用来找到对应的位置,所以代码如下:

void SLTPopBack(SLTNode** pphead);//头删void SLTPopFront(SLTNode** pphead);//尾删

 在对应位置插入或删除需要一个要插入的位置，这个就是pos，插入比删除多一个数据参数，而在pos之前插入多了一个前后指针。

//在pos之前插入xvoid SLTInsert(SLTNode** pphead,SLTNode*pos, SLTDataType x);//在pos以后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x);//在删除posvoid SLTErase(SLTNode** pphead, SLTNode* pos);//在删除pos以后一个位置void SLTEraseAfter( SLTNode* pos);

声明接口的总代码如下:

#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;}SLTNode;void SLTPrint(SLTNode* phead);//打印SLTNode* BuySListNode(SLTDataType x);//添加节点void SLTPushBack(SLTNode** pphead, SLTDataType x);//头增加void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾增加void SLTPopBack(SLTNode** pphead);//头删void SLTPopFront(SLTNode** pphead);//尾删SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在pos之前插入xvoid SLTInsert(SLTNode** pphead,SLTNode*pos, SLTDataType x);//在pos以后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x);//在删除posvoid SLTErase(SLTNode** pphead, SLTNode* pos);//在删除pos以后一个位置void SLTEraseAfter( SLTNode* pos);

三.单链表实现接口:

也就是遍历整个链表如果它的下一个等于要查找的就返回指针如果一直没找到就返回NULL。查找节点：后续很多操作都需要查找节点比如指定位置插入删除。如要一组 1 2 3 4 5  要找3图如下:

SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur!=NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;}

(1).增加节点：

如下是单链表的结构。

 1.创建新节点：

使用malloc创建一个节点并使用一个指针来连接，此函数的类型为结构体指针，是为了返回创建好的指向节点的指针，如果内容为空则创建失败终止程序，创建成功之后放入数据，数据是传入进来的参数，然后把创建出来的节点里面的指针至为空。

SLTNode* BuySListNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}

2.在头部增加节点：

在头部增加节点首先需要新节点指向头指针指向的内容，然后再用头指针指向新节点此时就增加成功。如图：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode(x);//开辟一个空间然后传个数据xif (*pphead==NULL) {//改变的结构体的指针，所以要用二级指针*pphead = newnode;}else {SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}//改变的结构体，用结构体的指针即可tail->next = newnode;}}

3.在尾部增加节点：

在尾部增加节点只需要用为指针指向新节点，然后再把新节点的指针置空。

void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode(x);//开辟一个空间然后传个数据xnewnode->next = *pphead;*pphead = newnode;}

4.在指定位置前面增加：

在指定位置前面增加节点需要一个指定位置也就是pos，还需要一个给新节点数据x，首先用assert断言一下传入的pos是否为有效的，然后再开辟新节点，最后一路走一路判断是否是，如果是指针前面是的话就为真就不执行循环了，然后就用新节点指向它最后用此节点变为指向新的节点。如下图：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);if (pos == *pphead) {SLTPushFront(pphead, x);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}

5.在指定位置后面增加：

其方法比上述方法更简便，只需要把要插入位置的指针传进来，先把其节点的指向的地方赋给新节点，然后再用节点指向它。

void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;}

(2).删除节点：

1.删除头部节点：

删除头部节点首先查看头指针指向的是否为空，如果为空那就结束，如果链表只有一个节点只需要直接把那个节点释放掉，然后直接用头指针指向空就可以了。

void SLTPopBack(SLTNode** pphead) {assert(*pphead);//一个节点if ((*pphead)->next==NULL) {free(*pphead);*pphead = NULL;}else {//一个以上节点//SLTNode* tailPerv = NULL;//SLTNode* tail = *pphead;//while (tail->next) {//tailPerv = tail;//tail = tail->next;//}//free(tail);tail = NULL;//tailPerv->next = NULL;SLTNode* tail = *pphead;while (tail->next->next) {tail = tail->next;}free(tail->next);tail->next = NULL;}}

2.删除尾部节点：

找到尾部节点的前一个，然后保存尾部节点指向的内容，然后释放最后在赋值给其。

void SLTPopFront(SLTNode** pphead) {assert(*pphead);SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}

3.删除指定位置的节点：

首先找节点时指针的next就是下一个节点这样就可以在pos前面了，然后再保存一下pos里面指向的下一个最后把pos释放再用现在指针的节点直接指向之前保存的节点就完了。

void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pos);if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}}

4.删除指定位置后面节点：

首先把pos（指定位置）后面那个节点指向的节点保存一下，然后再把其free释放，然后再用pos指向保存的那个节点。

void SLTEraseAfter(SLTNode* pos) {assert(pos);//检查pos是否是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;}

总代码如下:

#include"SList.h"void SLTPrint(SLTNode* phead){SLTNode* cur = phead;//while(cur!=NULL)while (cur) {printf("%d->", cur->data);cur = cur -> next;}printf("NULL\n");}SLTNode* BuySListNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;}void SLTPushBack(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode(x);//开辟一个空间然后传个数据xif (*pphead==NULL) {//改变的结构体的指针，所以要用二级指针*pphead = newnode;}else {SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}//改变的结构体，用结构体的指针即可tail->next = newnode;}}void SLTPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode(x);//开辟一个空间然后传个数据xnewnode->next = *pphead;*pphead = newnode;}void SLTPopBack(SLTNode** pphead) {assert(*pphead);//一个节点if ((*pphead)->next==NULL) {free(*pphead);*pphead = NULL;}else {//一个以上节点//SLTNode* tailPerv = NULL;//SLTNode* tail = *pphead;//while (tail->next) {//tailPerv = tail;//tail = tail->next;//}//free(tail);tail = NULL;//tailPerv->next = NULL;SLTNode* tail = *pphead;while (tail->next->next) {tail = tail->next;}free(tail->next);tail->next = NULL;}}void SLTPopFront(SLTNode** pphead) {assert(*pphead);SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur!=NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pos);if (pos == *pphead) {SLTPushFront(pphead, x);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}//接口//在pos以后插入xvoid SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySListNode(x);pos->next = newnode;newnode->next = pos->next;}//在删除posvoid SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pos);if (pos == *pphead) {SLTPopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}}//在删除pos以后一个位置void SLTEraseAfter(SLTNode* pos) {assert(pos);//检查pos是否是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;}

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/gushi/2024-04-04/154200.html，文章来源：网络cs，作者：康由，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！