单链表的操作

单链表代码定义

1
2
3
4
5
typedef struct LinkNode
{
int data; //data存放结点的数据域(以int类型为例)
struct LinkNode *next; //结点的指针域
}LinkNode, LinkList;

单链表的操作

初始化单链表

1
2
3
4
5
6
7
8
9
bool initList(LinkList* &L)			//L类型为引用类型的指针
{
L = new LinkNode; //为L分配一个动态内存
if(!L) return false; //若分配失败则返回false

//头结点指针指向空完成初始化,成功创建一个空的单链表并返回true
L->next = NULL;
return true;
}

插入结点

注: L为插入的单链表,node为将要插入的结点

前插法

1
2
3
4
5
6
7
8
bool ListInsert_front(LinkList* &L, LinkNode *node)
{
//合法性检查
if(!L || !node) return false;

node->next = L->next; //把新结点指针指向原来头结点所指向的结点
L->next = node; //把头结点指向新结点
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkNode *last = NULL;
if(!L || !node) return false;

last = L;

//找到尾结点
while(last->next) last = last->next;

//重置指针
node->next = NULL;
last->next = node;

return true;
}

任意位置插入

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
30
31
32
33
34
35
36
//任意位置插入
/*
* 参数: 要插入的单链表, 位置, 取值
*/
bool LinkInsert(LinkList* &L, int i, int &e)
{
if(!L) return false;

int j = 0;
LinkList *p, *s;
p = L;

//让p寻找插入位置
while(p && j<i-1)
{
p = p->next;
j++;
}

//如果插入位置大于链表节点数,最后p为空
//有一种情况为:若i <= 0 ,j<i-1不成立,但此时p为真,所以这里使用 !p || j>i-1
if(!p || j>i-1)
{
return false;
}

//当i = 0时,p为真且 j = i - 1, 此时指向头结点,直接来到下方这一步

s = new LinkNode; //生成新结点
//连接结点
s->data = e; //保存数据
s->next = p->next;
p->next = s;

return true;
}

输出单链表中的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void LinkPrint(LinkList* &L)
{
LNode *p = NULL;
if(!L)
{
cout << "此链表为空\n";
return;
}

p = L->next;

while(p)
{
cout << p->data << "\t";
p = p->next;
}
cout << endl;
}

元素找查

按位置查找

与任意位置插入类似,只不过要注意访问头结点的情况(带头结点的单链表头结点数据域无初始化数据)

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
/*
* 参数: 单链表, 位置, 取值
*/
bool GetLinkListElemAsAddress(LinkList* &L, int i, int &e)
{
if(!L || !L->next) return false;

int j = 0;
LinkList *p;
p = L;

while(p && j < i-1)
{
p = p->next;
j++;
}

if(!p || j >= i - 1) //这里取等号是为了避免访问头结点数据
{
return false;
}

e = p->data;

return true;
}

按值查找

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
/*
* 带头结点的单链表L中找查值为e的元素
* 参数:单链表, 取值, 返回所找元素的位置
*/
bool GetLinkListElemAsValue(LinkList *L, int e, int &index)
{
LinkList *p;
p = L->next;
index = 1;

if(!L || !L->next)
{
index = 0;
return false;
}

while(p && p->data! = e)
{
p = p->next;
index++;
}

if(!p)
{
index = 0;
return false; //查无此值
}
return true;
}

结点的删除

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 LinkListDel(LinkList* &L, int i)
{
LinkList *p, *q;
int index = 0;
p = L;

//合法性检查
if(!L || !L->next)
{
return false;
}

while((p->next) && (index < i-1))
{
p = p->next;
index++;
}

//删除位置不合理
if(!p->next || (index > i - 1))
{
return false;
}
q = p->next; //临时存放被删结点地址
p->next = q->next;//改变删除结点前驱指针域
delete q;
return true;

}

单链表的销毁

分配动态内存后,记得销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LinkDestory(LinkList* &L)
{
//定义临时结点指向头结点
LinkList *p = L;

cout << "销毁链表" << endl;

//遍历并删除结点
while(p)
{
L = L->next;
delete p;
p = L;
}

}
作者

CairBin

发布于

2021-09-12

更新于

2021-09-18

许可协议

评论