C语言实现单链表

单链表

 链表是一种数据结构,其逻辑结构为 线性结构 ,物理结构为 链式存储 。单链表是由多个 节点 进行链接而形成的。对于每个节点中不仅需要存储数据元素,还要存储 下一个节点 的指针位置。

 在编写一个单链表时根据是否存在 头节点(第一个节点为空)可以分为两种单链表,带头节点和不带头节点。

 表示一个单链表时,只需要申明一个头指针L,指向单链表的第一个节点即可找到整个链表中的所有内容。

1613314584628

优点:不要求大片的连续空间,改变容量方便

缺点:不可随机存储,要耗费一定存储空间存放指针

定义结构体作为节点

1
2
3
4
struct LNode{	// 定义当链表节点类型
ElemType data; // 每个节点存放的数据类型
struct LNode *next; //指针指向下一个节点
}

 结构体内部虽然不能定义自身数据类型,但是可以定义自身数据类型的指针。

代码示例:

1
2
3
4
struct LNode{
int data;
struct LNode *next;
}

增加节点时向内存中申请一个节点所需的空间,并用指针p指向这个节点

1
2
3
4
#include<stdio.h>
#include<stdlib.h>

struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));

malloc 函数是用来申请一个连续的空间,其参数为开辟空间的字节大小,所以这里也使用了sizeof()函数来判断该结构体的大小并显著的指明其指针类型。

 我们先看 struct LNode *p 这是一个自定义结构体指针类型,在需要使用的时候总是需要添加关键字 struct,所以可以使用typedef来重命名该结构体。

使用typedef定义结构体

typedef 关键字是给数据类型定义一个新的名字,这里的数据类型范围包括基本数据类型和自定义的数据类型,比如我们自定义的 struct结构体。

typedef使用

1
typedef <数据类型> <别名>

typedef 示例:

1
2
typedef int zhengshu;
typedef int *zhengshuzhizhen;
1
2
3
4
5
int x =1;
int *p;
等价
zhengshu x =1;
zhengshuzhizhen p;

使用typedef对自定义的 struct 结构体进行修改

代码如下:

1
2
3
4
5
typedef struct LNode
{
int data;
struct LNode * next;
}LNode,*LinkList;

解析:

将结构体

1
2
3
4
5
struct LNode
{
int data;
struct LNode * next;
}

重命名为:

LNode :LNode表示一个节点

*LinkList: 表示为单链表,这是一个指针类型,表示该结构体的指针类型

问题:

 为什么还要定义一个*LinkList来表示一个单链表呢?难道LNode *p不能表示一个链表吗?

 因为在对单链表操作的时候,有时候需要返回的是一个节点,而不是一个整个单链表,如果typedef之定义名称NLode,在某些操作中,返回的到底是节点还是链表呢。

 单链表的表示方法为申明一个头指针L,指向单链表的第一个节点即可找到整个链表中的所有内容。

 单链表分为 无头节点有头节点 两种情况,带头节点它的第一个节点时不存储数据的,只是为了方便实现某些操作,而无对头节点的第一个节点就是直接存储数据的。下面分别进行讨论。

 位序表示的是真实存储数据的节点。比如说第一个存储数据的节点其位序为1。对于带头节点的单链表,你可以把头节点看作是第0个节点。

 对于不带头节点的单链表,不存在第0个节点,因此对于需要第一个节点的时候需要特殊处理。

无头节点

1613314584628

(1)单链表初始化

1
2
3
4
5
6
7
8
9
10
bool initList(LinkList &L)
{
L = NULL; // 空表,表示无任何节点
return true;
}
void main()
{
LinkList L; // 申明一个指向单链表的指针
initList(L); // 初始化一个空表
}

(2)判断单链表是否为空

1
2
3
4
5
6
7
bool Empty(LinkList L)
{
if(L == NULL)
return true;
else
return false;
}

1
2
3
4
bool Empty(LinkList L)
{
return L==NULL;
}

(3)在指定节点插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool insertNextNode(LNode *p, int e)
{
if (p == NULL)
return false;// 空节点

LNode* newLNode = (LNode*)malloc(sizeof(LNode));// 创建新节点
if (newLNode == NULL)
return false;// 内存不足

newLNode->data = e;
newLNode->next = p->next;
p->next = newLNode;
return true;
}

(4)按位序插入(不带头节点,在第i位置上插入指定元素e)

 由于不带头节点,所以不存在第0个节点,因此当i=1时需要特别处理,创建新的节点并把它的next指向第一个节点,然后在修改头指针L指向新创建的节点。

 对于其他情况,在i(i不等于1)个节点上插入元素,我们找到i-1个节点,在i-1个节点后插入新的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool ListInsert(LinkList &L,int i,int e)
{
if(i<1)
return false;
if(i==1) // 当i=1时需要特别处理
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
L=s; // 头指针指向新节点
return true;
}
LNode *p;
int j=1;
p = L; // p指向第一个节点,无头节点
while(p!=NULL && j<i-1) // 循环找到第i-1个节点
{
p = p->next;
j++;
}
if(p == NULL) // i值不合法
return false;
insertNextNode(p,e); // 调用 (3)在指定节点后插入
}

(5)在指定节点插入(前插操作)

 单链表无法往前查找,只能往后查找,那我们如何才能完成前插操作呢?

 方案一:传入头指针,循环查找指定节点p前驱节点q,最后在前驱节点q后插入新的节点。时间复杂度为O(n)。(由于是无头结点,这时候就应该考虑一种情况,如果第一个结点就是我们需要进行前插的结点,这时候就需要操作头指针了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 在指定节点p进行前插操作,插入元素e
bool insertPriorNode(LinkList L, LNode* p, int e)
{
LNode* q = L;
if (q == p) { // 如果需要在第一个结点前插入,需要操作头指针
LNode* s = (LNode*)malloc(sizeof(LNode));
s->data = e;
s->next = p;
L = s;
return true;
}

while (q != NULL && q->next != p)
{
q = q->next;
}
if (q == NULL)
return false;
return insertNextNode(q, e);
}

 方案二:首先把新节点插入在指定节点之后,作为后继节点,虽然我们节点无法移动,但是节点里的内容可以交换,通过交换以后,实现的效果等同于前插操作。

方案二实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool insertPriorNode(LNode *p,int e)
{
if(p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s == NULL)
return false;
s->next = p->next;
p->next = s; // 将新节点 s 连接到 p 节点之后
s->data = p->data; // 将 p 节点中的元素复制到 s 中
p->data = e; // p 节点中元素覆盖为 e
return true;
}

时间复杂度:O(1)

(6)按位序删除(带头节点)

 无头结点单链表,当i=1时 需要进行特殊操作(需要操作头指针),并且没有第0个结点,所以需要从1开始循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool ListDelete(LinkList& L, int i, int& e)
{
if (i < 1)
return false;
if (i == 1)
{
LNode* s = L;
e = s->data;
L = s->next;
free(s);
}
LNode* p;
int j = 1;
p = L;
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
if (p->next == NULL)
return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}

带头节点

3432412345654

 如图所示, 头节点中是不存数据的,以及最后一个节点其next所指向的地址为NULL

(1)单链表初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool initList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));// 分配一个头节点内存空间
if(L == NULL) // 内存不足
return false;
L -> next == NULL; //头节点之后暂时没有节点
return true;
}

void main()
{
LinkList L; // 申明一个指向单链表的指针
initList(L); // 初始化一个空表
}

 带头节点的单链表初始化的时候,会申请一个节点用作头节点,这个节点的data中是不存任何数据的,其next指向下一个节点为NULL

 对于带头节点的单链表是为了实现某些操作时可以更加方便一下。

(2)判断单链表是否为空

1
2
3
4
5
6
7
bool Empty(LinkList L)
{
if(L->next == NULL)
return true;
else
return false;
}

(3)在指定节点后插入

 插入操作示意图:

1613393529257

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool insertNextNode(LNode *p, int e)
{
if (p == NULL)
return false;// 空节点

LNode* newLNode = (LNode*)malloc(sizeof(LNode));// 创建新节点
if (newLNode == NULL)
return false;// 内存不足

newLNode->data = e;
newLNode->next = p->next;
p->next = newLNode;
return true;
}

 这里的LNode *p表示的为一个节点

(4)按位序插入(带头节点)

 在单链表第i个位置上插入指定元素e。我们需要找到第i-1个节点,将新节点插入其后。如果我们需要在第1个位置上插入元素,那我们就需要找到第0个节点,这时候我们可以把头节点看作是第0个节点。这里就可以体验出带头节点的好处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool ListAfterInsert(LinkList L, int i, int e)
{
if (i < 1)
return false;
LNode* p = L;// p指针指向头节点
int j = 0;
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
return insertNextNode(p, e);// 调用(3)在指定节点后插入
}

 指针p表示当前指向的节点,而我们最终的目的是找到需要插入位序的前一个节点,也就是i-1的节点。

(5)在指定节点插入(前插操作)

 方案一:思路 同无头节点单链表(5)中方案一。由于存在头指针,所以无需关注第一个结点是否为指定结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 在指定节点p进行前插操作,插入元素e
bool insertPriorNode(LinkList &L, LNode* p, int e)
{
LNode* q = L;

while (q != NULL && q->next != p)
{
q = q->next;
}
if (q == NULL)
return false;
return insertNextNode(q, e);
}

 方案二:同无头节点单链表(5)中方案二

1
2
3
4
5
6
7
8
9
10
11
12
13
bool insertPriorNode(LNode *p,int e)
{
if(p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s == NULL)
return false;
s->next = p->next;
p->next = s; // 将新节点 s 连接到 p 节点之后
s->data = p->data; // 将 p 节点中的元素复制到 s 中
p->data = e; // p 节点中元素覆盖为 e
return true;
}

(6)按位序删除(带头节点)

 循环找到第i-1个节点,删除第i个节点,并把i-1的节点指向第i+1节点,最后使用free()函数释放掉以删除的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool ListDelete(LinkList &L,int i,int &e)
{
if(i<1)
return false;
LNode *p;
int j=0;
p=L;
while(p!=NULL && j<i-1)
{
p=p->next;
j++;
}
if(p == NULL)
return false;
if(p->next == NULL)
return false;
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}

单链表查找

实现两种查找方式:

  • 按位查找
  • 按值查找

每种查找方式都分为带头节点和不带头节点两种情况。

不带头节点

(1)按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LNode * getElem(LinkList L,int i)
{
if(i<1)
return NULL;
LNode *p;
int j=1;
p = L;
while(p != NULL && j<i)
{
p = p->next;
j++;
}
return p;
}

思考: 上文的 按位插入按位删除 是不是可以直接调用该方法。答案是肯定的。

(2)按值查找

1
2
3
4
5
6
7
8
LNode * LocateElem(LinkList L,int e)
{
LNode *p = L;
// 从第一个结点开始查找数据域为e的结点
while(p != NULL && p->data != e)
p = p->next;
return p;//找到返回p,否则返回NULL
}

带头节点

(1)按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
LNode * getElem(LinkList L,int i)
{
if(i<0)
return NULL;
LNode *p;
int j=0;
p = L;
while(p != NULL && j<i)
{
p = p->next;
j++;
}
return p;
}

(2)按值查找

1
2
3
4
5
6
7
8
LNode * LocateElem(LinkList L,int e)
{
LNode *p = L ->next;
// 从第一个结点开始查找数据域为e的结点
while(p != NULL && p->data != e)
p = p->next;
return p;//找到返回p,否则返回NULL
}

单链表长度

带头指针

1
2
3
4
5
6
7
8
9
10
11
12
// 获取单链表长度
int getLength(LinkList L)
{
LNode* p = L;
int i = 0;
while (p->next != NULL)
{
p = p->next;
i++;
}
return i;
}

不带头指针

1
2
3
4
5
6
7
8
9
10
11
12
// 获取单链表长度
int getLength(LinkList L)
{
LNode* p = L;
int i = 1;
while (p->next != NULL)
{
p = p->next;
i++;
}
return i;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!