数据结构——双链表和循环链表

摘要:由于太久没有复习数据结构了,导致该忘的都忘了,所以在这里记录重新学习数据结构的笔记,以备以后查看。

双链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

存储结构

1
2
3
4
5
typedef struct DLNode{
ElemType data;
struct DLNode *prior; //指向前驱的指针
struct DLNode *next; //指向后继的指针
}DLNode;

与单链表的区别就是定义了一个指向前驱的指针。

初始化结点

1
2
3
4
5
6
7
8
DLNode *create_node(ElemType data)
{
DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
ret->data = data;
ret->prior = NULL;
ret->next = NULL;
return ret;
}

尾插法创建双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
DLNode *s,*r;
int i;
L = create_node(NULL);
r = L;
for(i = 0;i < n ; i++){
s = create_node(data[i]);
s->prior = r;
r->next = s;
r = r->next;
}
r->next = NULL;
return L;
}

查找结点某个位置的指针

1
2
3
4
5
6
7
8
9
10
11
12
//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
int i,count = 0;
DLNode *ret = L->next;
if(p<0 || p > link_length(L))
return 0;
for(i = 1;i< p ; i++){
ret = ret->next;
}
return ret; //这样写如果未找到也会返回NULL
}

在某个结点后面插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
DLNode *s,*p;
if(index < 0|| index>link_length(L))
return 0;
p = find_elem_node(L,index);
s = create_node(data);
if(index != link_length(L)){
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
}
else{
p->next = s;
s->prior=p;
}
return 1;
}

此处记得判断是否是最后一个结点插入。

删除结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
DLNode *ret;
if(index < 0|| index>link_length(L))
return 0;
ret = find_elem_node(L,index);
if(index != link_length(L)){
ret->next->prior = ret->prior;
ret->prior->next = ret->next;
}
else{
ret->prior->next = NULL;
}
return ret;
}

获取链表长度

1
2
3
4
5
6
7
8
9
int link_length(DLNode *L)
{
int count = 0;
while(L->next){
count++;
L = L ->next;
}
return count;
}

打印双链表

1
2
3
4
5
6
7
8
int printf_link(DLNode *L)
{
while(L->next){
L = L ->next;
printf("%3d",L->data);
}
printf("\n\n");
}

完整函数(包含测试)

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//定义双链表的节点类型
typedef struct DLNode{
ElemType data;
struct DLNode *prior; //指向前驱的指针
struct DLNode *next; //指向后继的指针
}DLNode;

DLNode *create_node(ElemType data)
{
DLNode *ret = (DLNode*)malloc(sizeof(DLNode));
ret->data = data;
ret->prior = NULL;
ret->next = NULL;
return ret;
}
//尾插法
DLNode *create_link_tail(DLNode *L,ElemType data[],int n)
{
DLNode *s,*r;
int i;
L = create_node(NULL);
r = L;
for(i = 0;i < n ; i++){
s = create_node(data[i]);
s->prior = r;
r->next = s;
r = r->next;
}
r->next = NULL;
return L;
}

//查找某个位置的结点的指针
DLNode *find_elem_node(DLNode *L,int p)
{
int i,count = 0;
DLNode *ret = L->next;
if(p<0 || p > link_length(L))
return 0;
for(i = 1;i< p ; i++){
ret = ret->next;
}
return ret; //这样写如果未找到也会返回NULL
}

//在某个结点后面插入结点
int insert_elem(DLNode *L,ElemType data,int index)
{
DLNode *s,*p;
if(index < 0|| index>link_length(L))
return 0;
p = find_elem_node(L,index);
s = create_node(data);
if(index != link_length(L)){
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
}
else{
p->next = s;
s->prior=p;
}
return 1;
}
//删除某个结点并返回
DLNode *delete_node(DLNode *L,int index)
{
DLNode *ret;
if(index < 0|| index>link_length(L))
return 0;
ret = find_elem_node(L,index);
if(index != link_length(L)){
ret->next->prior = ret->prior;
ret->prior->next = ret->next;
}
else{
ret->prior->next = NULL;
}
return ret;
}
//双链表长度
int link_length(DLNode *L)
{
int count = 0;
while(L->next){
count++;
L = L ->next;
}
return count;
}
//打印双链表
int printf_link(DLNode *L)
{
while(L->next){
L = L ->next;
printf("%3d",L->data);
}
printf("\n\n");
}

int main()
{
DLNode *A;
DLNode *local;
int i;
ElemType data1[] = {1,2,3,4,5};
//尾插法
A = create_link_tail(A,data1,5);
printf_link(A);
//长度
printf("A链表长度为:%d.\n\n",link_length(A));
//查找结点
local = find_elem_node(A,2);
printf("查找到第2位结点为:%d.\n\n",local->data);
//指定结点后插入元素
insert_elem(A,6,5);
printf_link(A);
//删除某个结点
local = delete_node(A,6);
printf("删除的结点为:%d\n\n",local->data);
printf_link(A);

return 0;
}

循环链表

循环单链表和循环双链表是由对应的单链表和双链表改造而来,只需要在终点结点和头结点间建立联系即可。循环单链表终端结点的next结点指针指向头结点。循环双链表终端结点的next指针指向表头结点,头节点的prior指针指向表尾节点即可。

tips:

如果P指针沿着循环链表行走,则判断p走到尾节点的条件是p->next == head。循环链表的操作均与非循环链表类似。

------- 本文结束  感谢您的阅读 -------