数据结构与算法之线性表

发表于 | 分类于 | |

线性表作为一种常用的数据结构，在实际中有着广泛的运用。

线性表基本概念

线性表定义

  • 线性表(List)是零个或多个数据元素的集合
  • 线性表中的数据元素之间是有顺序的
  • 线性表中的数据元素个数是有限的
  • 线性表中的数据元素的类型必须相同

数学定义

线性表是具有相同类型的 n（ ≥ 0）个数据元素的有限序列
（a1, a2,···, an）
ai是表项，n 是表长度

性质

a0为线性表的第一个元素，只有一个后继
an为线性表的最后一个元素，只有一个前驱
除a0和an外的其它元素ai，既有前驱，又有后继
线性表能够逐项访问和顺序存取

线性表的操作

创建线性表
销毁线性表
清空线性表
将元素插入线性表
将元素从线性表中删除
获取线性表中某个位置的元素
获取线性表的长度

线性表在程序中表现为一种特殊的数据类型
线性表的操作在程序中的表现为一组函数

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
#ifndef __LIST_H_
#define __LIST_H_

typedef void List;
typedef void ListNode;

//创建并且返回一个空的线性表
List* LinkList_Create();

//销毁一个线性表list
void List_Destroy(List* list);

//将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
void List_Clear(List* list);

//返回一个线性表list中的所有元素个数
int List_Length(List* list);

//向一个线性表list的pos位置处插入新元素node
int List_Insert(List* list, ListNode* node, int pos);

//获取一个线性表list的pos位置处的元素
ListNode* List_Get(List* list, int pos);

//删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
ListNode* List_Delete(List* list, int pos);

#endif

线性表的顺序存储结构

基本概念

设计与实现

  • 插入元素算法
    判断线性表是否合法
    判断插入位置是否合法
    把最后一个元素到插入位置的元素后移一个位置
    将新元素插入
    线性表长度加1

  • 获取元素操作
    判断线性表是否合法
    判断位置是否合法
    直接通过数组下标的方式获取元素

  • 删除元素算法
    判断线性表是否合法
    判断删除位置是否合法
    将元素取出
    将删除位置后的元素分别向前移动一个位置
    线性表长度减1

(*.h)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef __MY_SEQLIST_H__ 
#define __MY_SEQLIST_H__

typedef void SeqList;
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity);

void SeqList_Destroy(SeqList* list);

void SeqList_Clear(SeqList* list);

int SeqList_Length(SeqList* list);

int SeqList_Capacity(SeqList* list);

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

SeqListNode* SeqList_Get(SeqList* list, int pos);

SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif

(*.c)

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "seqlist.h"

typedef struct _tag_SeqList
{
	int capacity;
	int length;
	unsigned int *node; //unsigned int array[capacity]
}TSeqList;

SeqList* SeqList_Create(int capacity)
{
	TSeqList *ret = NULL;
	if (capacity < 0)
	{
		return NULL;
	}
	ret = (TSeqList *)malloc(sizeof(TSeqList) + sizeof(unsigned int)*capacity);
	if (ret == NULL)
	{
		return NULL;
	}
	memset(ret, 0, sizeof(TSeqList) + sizeof(unsigned int)*capacity);
	ret->node = (unsigned int *)(ret + 1); //ret向后跳sizeof（TSeqList）
	ret->capacity = capacity;
	ret->length = 0;
	return ret;
}

void SeqList_Destroy(SeqList* list)
{
	if (list == NULL)
	{
		return;
	}
	free(list);
	return;
}

//链表清零
void SeqList_Clear(SeqList* list)
{
	TSeqList *tList = NULL;

	if (list == NULL)
	{
		return;
	}
	tList = (TSeqList *)list;
	tList->length = 0;
	return;
}

int SeqList_Length(SeqList* list)
{
	TSeqList *tList = NULL;
	tList = (TSeqList *)list;
	if (list == NULL)
	{
		return -1;
	}

	return tList->length;
}

//线性表的容量和线性表长度是不一样的
int SeqList_Capacity(SeqList* list)
{
	TSeqList *tList = NULL;
	tList = (TSeqList *)list;
	if (list == NULL)
	{
		return -1;
	}

	return tList->capacity;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
	int			i = 0;
	TSeqList	*tList = NULL;

	tList = (TSeqList *)list;

	if (list == NULL || node == NULL)
	{
		return -1;
	}

	//查看是不是满了
	if (tList->length >= tList->capacity)
	{
		return -2;
	}

	//位置错误判断
	if (pos < 0 || pos >= tList->capacity)
	{
		return -3;
	}

	//优化的容错。。。
	if (pos >= tList->length)
	{
		pos = tList->length;
	}

	//插入算法
	//从pos位置处开始，把数组后面的元素依此后移
	for (i = tList->length; i > pos; i--)
	{
		//把前的元素往后移
		tList->node[i] = tList->node[i - 1];
	}
	//循环跳出以后，pos正好是，要出入的位置
	tList->node[pos] = (unsigned int)node;
	tList->length++;
	return 0;
}

SeqListNode* SeqList_Get(SeqList* list, int pos)
{

	SeqListNode		*ret = NULL;
	TSeqList		*tList = NULL;

	tList = (TSeqList *)list;
	if (list == NULL || pos < 0 || pos >= tList->length)
	{
		return NULL;
	}
	ret = (SeqListNode*)tList->node[pos];
	return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
	int				i;
	TSeqList		*tList = NULL;
	SeqListNode		*ret = NULL;

	tList = (TSeqList *)list;

	if (list == NULL || pos < 0 || pos >= tList->length)
	{
		return NULL;
	}

	//赋给之前，要把元素缓存下来
	ret = (SeqListNode *)tList->node[pos];
	//删除算法
	for (i = pos + 1; i < tList->length; i++)
	{
		tList->node[i - 1] = tList->node[i];
	}
	tList->length--;

	return ret;
}

(test)

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "seqlist.h"

typedef struct _Teacher
{
	char name[64];
	int age;
}Teacher;

int main()
{
	int i = 0, len = 0;
	SeqList *list = NULL;

	Teacher t1, t2, t3;
	t1.age = 31;
	t2.age = 32;
	t3.age = 33;

	list = SeqList_Create(10);

	//头插法
	SeqList_Insert(list, (SeqListNode*)&t1, 0);
	SeqList_Insert(list, (SeqListNode*)&t2, 0);
	SeqList_Insert(list, (SeqListNode*)&t3, 0);

	//循环遍历
	for (i = 0; i < SeqList_Length(list); i++)
	{
		Teacher *tmp = (Teacher *)SeqList_Get(list, i);
		if (tmp != NULL)
		{
			printf("age:%d ", tmp->age);
		}
	}

	//循环删除
	len = SeqList_Length(list);
	for (i = 0; i < len; i++)
	{
		SeqList_Delete(list, 0);
	}
	SeqList_Destroy(list);

	system("pause");
}

优点和缺点

  • 优点：
    无需为线性表中的逻辑关系增加额外的空间
    可以快速的获取表中合法位置的元素

  • 缺点：
    插入和删除操作需要移动大量元素
    当线性表长度变化较大时难以确定存储空间的容量

线性表的链式存储

基本概念

为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息

  • 表头结点
    链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
  • 数据结点
    链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
  • 尾结点
    链表中的最后一个数据结点，其下一元素指针为空，表示无后继

设计与实现

在C语言中可以用结构体来定义链表中的指针域
链表中的表头结点也可以用结构体实现

  • 插入元素

    带头结点、位置从0的单链表
    返回链表中第3个位置处，元素的值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    LinkListNode* LinkList_Get(LinkList* list, int pos)
    { 
    	int  i = 0;
    	TLinkList *tList = (TLinkList *)list;
    	LinkListNode *current = NULL;
    	LinkListNode *ret = NULL;

    	if (list==NULL ||pos<0 || pos>=tList->length)
    	{
    		return NULL;
    	}
    	current = (LinkListNode *)tList;
    	for (i=0; i<pos; i++)
    	{
    		current = current->next;
    	}
    	ret = current->next;
    	return ret ;
    }

返回第三个位置的
移动pos次以后，当前指针指向哪里？
答案：指向位置2，所以需要返回 ret = current->next;
备注：循环遍历时，遍历第1次，指向位置0；遍历第2次，指向位置1；遍历第3次，指向位置2；遍历第n次，指向位置n-1;
所以如果想返回位置n的元素的值，ret = current->next;

  • 删除元素

(*.h)

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
#ifndef __MY_LINKLIST_H_
#define __MY_LINKLIST_H_

typedef void LinkList;
/*
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
LinkListNode* next;
};
*/
typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* next;
}LinkListNode;

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif

(*.c)

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
129
130
131
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linklist.h"

typedef struct _tag_LinkList
{
	LinkListNode header;
	int length;
}TLinkList;

LinkList* LinkList_Create()
{
	TLinkList *ret = (TLinkList *)malloc(sizeof(TLinkList));
	if (ret == NULL)
	{
		return NULL;
	}
	//memset(ret, 0, sizeof(TLinkList));
	ret->header.next = NULL;
	ret->length = 0;
	return ret;
}

void LinkList_Destroy(LinkList* list)
{
	if (list == NULL)
	{
		return;
	}
	free(list);
	return;
}

void LinkList_Clear(LinkList* list)
{
	TLinkList *tList = NULL;

	if (list == NULL)
	{
		return;
	}
	tList = (TLinkList *)list;
	tList->length = 0;
	tList->header.next = NULL;
	return;
}

int LinkList_Length(LinkList* list)
{

	TLinkList *tList = (TLinkList *)list;
	if (tList == NULL)
	{
		return -1;
	}

	return tList->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
	int				i = 0;
	TLinkList		*tList = NULL;
	LinkListNode	*current = NULL;

	tList = (TLinkList *)list;
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i = 0; i < pos && (current->next != NULL); i++)
	{
		current = current->next;
	}
	//让node节点链接后续链表
	node->next = current->next;
	//让前边的链表。链接node
	current->next = node;
	tList->length++;
	return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
	int				i = 0;
	TLinkList		*tList = NULL;
	LinkListNode	*current = NULL;
	LinkListNode	*ret = NULL;

	tList = (TLinkList *)list;

	if (list == NULL || pos < 0 || pos >= tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i = 0; i < pos && (current->next != NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;

	return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
	int				i = 0;
	TLinkList		*tList = NULL;
	LinkListNode	*current = NULL;
	LinkListNode	*ret = NULL;

	tList = (TLinkList *)list;

	if (list == NULL || pos < 0 || pos >= tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i = 0; i < pos && (current->next != NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;
	//删除算法
	current->next = ret->next;
	tList->length--;
	return ret;
}

(test)

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linklist.h"

typedef struct Teacher
{
	LinkListNode node;
	char name[64];
	int age;
}Teacher;

int main()
{
	Teacher		t1, t2, t3;
	int			length, i = 0;
	LinkList	*list = NULL;

	t1.age = 31;
	t2.age = 32;
	t3.age = 33;

	list = LinkList_Create();
	length = LinkList_Length(list);

	LinkList_Insert(list, (LinkListNode *)&t1, LinkList_Length(list));
	LinkList_Insert(list, (LinkListNode *)&t2, LinkList_Length(list));
	LinkList_Insert(list, (LinkListNode *)&t3, LinkList_Length(list));

	//遍历链表 
	for (i = 0; i < LinkList_Length(list); i++)
	{
		Teacher *tmp = (Teacher *)LinkList_Get(list, i);
		if (tmp != NULL)
		{
			printf("age:%d ", tmp->age);
		}
	}
	while (LinkList_Length(list) > 0)
	{
		Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
		if (tmp != NULL)
		{
			printf("age:%d ", tmp->age);
		}
	}
	LinkList_Destroy(list);
	system("pause");
	return 0;
}

优点和缺点

  • 优点：
    无需一次性定制链表的容量
    插入和删除操作无需移动数据元素

  • 缺点：
    数据元素必须保存后继元素的位置信息
    获取指定数据的元素操作需要顺序访问之前的元素

循环链表

基本概念

将单链表中最后一个数据元素的next指针指向第一个元素

循环链表拥有单链表的所有操作

  • 创建链表
  • 销毁链表
  • 获取链表长度
  • 清空链表
  • 获取第pos个元素操作
  • 插入元素到位置pos
  • 删除位置pos处的元素
  • 新增功能：游标的定义

在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素

获取当前游标指向的数据元素
将游标重置指向链表中的第一个数据元素
将游标移动指向到链表中的下一个数据元素
直接指定删除链表中的某个数据元素

1
2
3
4
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);
CircleListNode* CircleList_Reset(CircleList* list);
CircleListNode* CircleList_Current(CircleList* list);
CircleListNode* CircleList_Next(CircleList* list);

设计与实现

  • 插入元素的分析
    • 普通位置插入元素
    • 添加第一个元素（第一次插入元素）
    • 最后一个位置插入元素
    • 第一个位置插入元素

(*.h)

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
#ifndef __CIRCLELIST_H_
#define __CIRCLELIST_H_

typedef void CircleList;
/*
typedef struct _tag_CircleListNode CircleListNode;
struct _tag_CircleListNode
{
	CircleListNode* next;
};
*/
typedef struct _tag_CircleListNode
{
	struct _tag_CircleListNode * next;
}CircleListNode;

CircleList* CircleList_Create();

void CircleList_Destroy(CircleList* list);

void CircleList_Clear(CircleList* list);

int CircleList_Length(CircleList* list);

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);

CircleListNode* CircleList_Get(CircleList* list, int pos);

CircleListNode* CircleList_Delete(CircleList* list, int pos);

//add
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

CircleListNode* CircleList_Reset(CircleList* list);

CircleListNode* CircleList_Current(CircleList* list);

CircleListNode* CircleList_Next(CircleList* list);

#endif

(*.c)

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include <stdio.h>
#include <malloc.h>

#include "CircleList.h"

typedef struct _tag_CircleList
{
	CircleListNode header;
	CircleListNode* slider;
	int length;
} TCircleList;

CircleList* CircleList_Create() // O(1)
{
	TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));
	if (ret == NULL)
	{
		return NULL;
	}
	ret->length = 0;
	ret->header.next = NULL;
	ret->slider = NULL;
	return ret;
}

void CircleList_Destroy(CircleList* list) // O(1)
{
	if (list == NULL)
	{
		return;
	}
	free(list);
}

void CircleList_Clear(CircleList* list) // O(1)
{
	TCircleList* sList = (TCircleList*)list;
	if (sList == NULL)
	{
		return;
	}
	sList->length = 0;
	sList->header.next = NULL;
	sList->slider = NULL;
}

int CircleList_Length(CircleList* list) // O(1)
{
	TCircleList* sList = (TCircleList*)list;
	int ret = -1;
	if (list == NULL)
	{
		return ret;
	}
	ret = sList->length;
	return ret;
}

int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) // O(n)
{
	int				ret = 0, i = 0;
	TCircleList*	sList = (TCircleList*)list;
	if (list == NULL || node == NULL || pos < 0)
	{
		return -1;
	}
	CircleListNode* current = (CircleListNode*)sList;
	for (i = 0; (i < pos) && (current->next != NULL); i++)
	{
		current = current->next;
	}
	//current->next 0号节点的地址
	node->next = current->next; //1
	current->next = node; //2

	//若第一次插入节点
	if (sList->length == 0)
	{
		sList->slider = node;
	}
	sList->length++;
	//若头插法
	if (current == (CircleListNode*)sList)
	{
		//获取最后一个元素
		CircleListNode* last = CircleList_Get(sList, sList->length - 1);
		last->next = current->next; //3

	}
	return ret;
}

CircleListNode* CircleList_Get(CircleList* list, int pos) // O(n)
{
	TCircleList*		sList = (TCircleList*)list;
	CircleListNode*		ret = NULL;
	int					i = 0;
	if (list == NULL || pos < 0)
	{
		return NULL;
	}
	//if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )
	{
		CircleListNode* current = (CircleListNode*)sList;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
	}
	return ret;
}

CircleListNode* CircleList_Delete(CircleList* list, int pos) // O(n)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;
	int i = 0;
	if ((sList != NULL) && (pos >= 0) && (sList->length > 0))
	{
		CircleListNode* current = (CircleListNode*)sList;
		CircleListNode* last = NULL;
		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}
		//若删除第一个元素
		if (current == (CircleListNode*)sList)
		{
			last = (CircleListNode*)CircleList_Get(sList, sList->length - 1);
		}
		//求要删除的元素
		ret = current->next;
		current->next = ret->next;
		sList->length--;
		//判断链表是否为空
		if (last != NULL)
		{
			sList->header.next = ret->next;
			last->next = ret->next;
		}
		//若删除的元素为游标所指的元素
		if (sList->slider == ret)
		{
			sList->slider = ret->next;
		}
		//若删除元素后，链表长度为0
		if (sList->length == 0)
		{
			sList->header.next = NULL;
			sList->slider = NULL;
		}
	}
	return ret;
}

CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) // O(n)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;
	int i = 0;
	if (sList != NULL)
	{
		CircleListNode* current = (CircleListNode*)sList;
		//查找node在循环链表中的位置i
		for (i = 0; i < sList->length; i++)
		{
			if (current->next == node)
			{
				ret = current->next;
				break;
			}
			current = current->next;
		}
		//如果ret找到，根据i去删除	
		if (ret != NULL)
		{
			CircleList_Delete(sList, i);
		}
	}
	return ret;
}

CircleListNode* CircleList_Reset(CircleList* list) // O(1)
{
	TCircleList*		sList = (TCircleList*)list;
	CircleListNode*		ret = NULL;
	if (sList != NULL)
	{
		sList->slider = sList->header.next;
		ret = sList->slider;
	}
	return ret;
}

CircleListNode* CircleList_Current(CircleList* list) // O(1)
{
	TCircleList*		sList = (TCircleList*)list;
	CircleListNode*		ret = NULL;
	if (sList != NULL)
	{
		ret = sList->slider;
	}
	return ret;
}

CircleListNode* CircleList_Next(CircleList* list) // O(1)
{
	TCircleList* sList = (TCircleList*)list;
	CircleListNode* ret = NULL;
	if ((sList != NULL) && (sList->slider != NULL))
	{
		ret = sList->slider;
		sList->slider = ret->next;
	}
	return ret;
}

(test)

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
#include <stdio.h>
#include <stdlib.h>

#include "CircleList.h"

struct Value
{
	CircleListNode circlenode;
	int v;
};

int main()
{
	int				i = 0;
	CircleList*		list = CircleList_Create();

	struct Value v1;
	struct Value v2;
	struct Value v3;
	struct Value v4;
	struct Value v5;
	struct Value v6;
	struct Value v7;
	struct Value v8;

	v1.v = 1;
	v2.v = 2;
	v3.v = 3;
	v4.v = 4;
	v5.v = 5;
	v6.v = 6;
	v7.v = 7;
	v8.v = 8;

	CircleList_Insert(list, (CircleListNode*)&v1, 0);
	CircleList_Insert(list, (CircleListNode*)&v2, 0);
	CircleList_Insert(list, (CircleListNode*)&v3, 0);
	CircleList_Insert(list, (CircleListNode*)&v4, 0);

	for (i = 0; i < 2 * CircleList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)CircleList_Get(list, i);
		printf("%d\n", pv->v);
	}

	while (CircleList_Length(list) > 0)
	{
		CircleList_Delete(list, 0);
	}
	printf("\n");

	CircleList_Destroy(list);

	system("pause");
	return 0;
}

优点和缺点

  • 优点：功能强了。
    循环链表只是在单链表的基础上做了一个加强
    循环链表可以完全取代单链表的使用
    循环链表的Next和Current操作可以高效的遍历链表中的所有元素

  • 缺点：
    代码复杂度提高了

约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，···，如此下去，求出列顺序

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
#include <stdio.h>
#include <stdlib.h>

#include "CircleList.h"

struct Value
{
	CircleListNode header;
	int v;
};

void main()
{
	int				i = 0;
	CircleList*		list = CircleList_Create();

	struct Value v1, v2, v3, v4, v5, v6, v7, v8;

	v1.v = 1;	v2.v = 2;	v3.v = 3;	v4.v = 4;
	v5.v = 5;	v6.v = 6;	v7.v = 7;	v8.v = 8;

	CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
	CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));

	for (i = 0; i < CircleList_Length(list); i++)
	{
		struct Value* pv = (struct Value*)CircleList_Next(list);
		printf("%d\n", pv->v);
	}
	printf("\n");

	//重置游标
	CircleList_Reset(list);
	while (CircleList_Length(list) > 0)
	{
		struct Value* pv = NULL;
		for (i = 1; i < 3; i++)
		{
			CircleList_Next(list);
		}
		pv = (struct Value*)CircleList_Current(list);
		printf("%d\n", pv->v);
		CircleList_DeleteNode(list, (CircleListNode*)pv);
	}
	CircleList_Destroy(list);

	system("pause");
}

双向链表

基本概念

单链表的结点都只有一个指向下一个结点的指针
单链表的数据元素无法直接访问其前驱元素
逆序访问单链表中的元素是极其耗时的操作

1
2
3
4
5
6
len = LinkList_Length(list);
for (i=len-1; len>=0; i++) //O(n)
{
LinkListNode *p = LinkList_Get(list, i); //O(n)
//访问数据元素p中的元素
}

双向链表的定义
在单链表的结点中增加一个指向其前驱的pre指针

双向链表拥有单链表的所有操作

  • 创建链表
  • 销毁链表
  • 获取链表长度
  • 清空链表
  • 获取第pos个元素操作
  • 插入元素到位置pos
  • 删除位置pos处的元素

设计与实现

  • 插入操作

  • 删除操作

双向链表的新操作
获取当前游标指向的数据元素
将游标重置指向链表中的第一个数据元素
将游标移动指向到链表中的下一个数据元素
将游标移动指向到链表中的上一个数据元素
直接指定删除链表中的某个数据元素

1
2
3
4
5
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);
DLinkListNode* DLinkList_Reset(DLinkList* list);
DLinkListNode* DLinkList_Current(DLinkList* list);
DLinkListNode* DLinkList_Next(DLinkList* list);
DLinkListNode* DLinkList_Pre(DLinkList* list);

(*.h)

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
#ifndef __MY_DLINKLIST_H_
#define __MY_DLINKLIST_H_

typedef void DLinkList;
/*
typedef struct _tag_DLinkListNode DLinkListNode;
struct _tag_DLinkListNode
{
DLinkListNode* next;
DLinkListNode* pre;
};
*/

typedef struct _tag_DLinkListNode
{
	struct _tag_DLinkListNode* next;
	struct _tag_DLinkListNode * pre;
}DLinkListNode;

DLinkList* DLinkList_Create();

void DLinkList_Destroy(DLinkList* list);

void DLinkList_Clear(DLinkList* list);

int DLinkList_Length(DLinkList* list);

int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

//add
DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

#endif

(*.c)

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
#include <stdio.h>
#include <malloc.h>

#include "DLinkList.h"

typedef struct _tag_DLinkList
{
	DLinkListNode header;
	DLinkListNode* slider;
	int length;
} TDLinkList;

DLinkList* DLinkList_Create()
{
	TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));

	if (ret != NULL)
	{
		ret->length = 0;
		ret->header.next = NULL;
		ret->header.pre = NULL;
		ret->slider = NULL;
	}

	return ret;
}

void DLinkList_Destroy(DLinkList* list)
{
	if (list != NULL)
	{
		free(list);
	}
}

void DLinkList_Clear(DLinkList* list)
{
	TDLinkList* sList = (TDLinkList*)list;

	if (sList != NULL)
	{
		sList->length = 0;
		sList->header.next = NULL;
		sList->header.pre = NULL;
		sList->slider = NULL;
	}
}

int DLinkList_Length(DLinkList* list)
{
	int				ret = -1;
	TDLinkList*		sList = (TDLinkList*)list;

	if (sList != NULL)
	{
		ret = sList->length;
	}

	return ret;
}

//大家一定要注意：教科书不会告诉你 项目上如何用；哪些点是项目的重点
int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos)
{
	int				ret = 0, i = 0;
	TDLinkList*		sList = (TDLinkList*)list;

	if (list == NULL || node == NULL || pos < 0)
	{
		return -1;
	}

	{
		DLinkListNode* current = (DLinkListNode*)sList;
		DLinkListNode* next = NULL; //需要增加next指针

		for (i = 0; (i < pos) && (current->next != NULL); i++)
		{
			current = current->next;
		}

		next = current->next;

		//步骤1-2
		current->next = node;
		node->next = next;

		//步骤3-4 
		if (next != NULL) //当链表插入第一个元素，需要特殊处理
		{
			next->pre = node;
		}
		node->pre = current;

		if (sList->length == 0)
		{
			sList->slider = node; //当链表插入第一个元素处理游标
		}

		//若在0位置插入，需要特殊处理 新来结点next前pre指向null
		if (current == (DLinkListNode*)sList)
		{
			node->pre = NULL;
		}

		sList->length++;
	}

	return ret;
}

DLinkListNode* DLinkList_Get(DLinkList* list, int pos)
{
	int				i = 0;
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if ((sList != NULL) && (0 <= pos) && (pos < sList->length))
	{
		DLinkListNode* current = (DLinkListNode*)sList;

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
	}

	return ret;
}

//插入第一个节点
//删除的是最后一个结点，该是如何处理
DLinkListNode* DLinkList_Delete(DLinkList* list, int pos)
{
	int				i = 0;
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if (sList == NULL || pos < 0)
	{
		return NULL;
	}
	//if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
	{
		DLinkListNode* current = (DLinkListNode*)sList;
		DLinkListNode* next = NULL; //需要增加next指针

		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}

		ret = current->next;
		next = ret->next;

		//步骤1
		current->next = next;

		//步骤2 
		if (next != NULL)//需要特殊处理
		{
			next->pre = current;

			if (current == (DLinkListNode*)sList) //若第0个位置，需要特殊处理
			{
				next->pre = NULL;
			}
		}

		if (sList->slider == ret)
		{
			sList->slider = next;
		}

		sList->length--;
	}

	return ret;
}

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
{
	int				i = 0;
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if (sList != NULL)
	{
		DLinkListNode* current = (DLinkListNode*)sList;

		for (i = 0; i < sList->length; i++)
		{
			if (current->next == node)
			{
				ret = current->next;
				break;
			}

			current = current->next;
		}

		if (ret != NULL)
		{
			DLinkList_Delete(sList, i);
		}
	}

	return ret;
}

DLinkListNode* DLinkList_Reset(DLinkList* list)
{
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if (sList != NULL)
	{
		sList->slider = sList->header.next;
		ret = sList->slider;
	}

	return ret;
}

DLinkListNode* DLinkList_Current(DLinkList* list)
{
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if (sList != NULL)
	{
		ret = sList->slider;
	}

	return ret;
}

DLinkListNode* DLinkList_Next(DLinkList* list)
{
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if ((sList != NULL) && (sList->slider != NULL))
	{
		ret = sList->slider;
		sList->slider = ret->next;
	}

	return ret;
}

DLinkListNode* DLinkList_Pre(DLinkList* list)
{
	TDLinkList*		sList = (TDLinkList*)list;
	DLinkListNode*	ret = NULL;

	if ((sList != NULL) && (sList->slider != NULL))
	{
		ret = sList->slider;
		sList->slider = ret->pre;
	}
	return ret;
}

(test)

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
#include <stdio.h>
#include <stdlib.h>

#include "DLinkList.h"

struct Value
{
	DLinkListNode node;
	int v;
};

int main()
{
	int i = 0;
	DLinkList* list = DLinkList_Create();
	struct Value* pv = NULL;
	struct Value v1, v2, v3, v4, v5;

	v1.v = 1;	v2.v = 2;	v3.v = 3;
	v4.v = 4;	v5.v = 5;

	DLinkList_Insert(list, (DLinkListNode*)&v1, DLinkList_Length(list));
	DLinkList_Insert(list, (DLinkListNode*)&v2, DLinkList_Length(list));
	DLinkList_Insert(list, (DLinkListNode*)&v3, DLinkList_Length(list));
	DLinkList_Insert(list, (DLinkListNode*)&v4, DLinkList_Length(list));
	DLinkList_Insert(list, (DLinkListNode*)&v5, DLinkList_Length(list));

	for(i=0; i<DLinkList_Length(list); i++)
	{
		pv = (struct Value*)DLinkList_Get(list, i);
		printf("%d\n", pv->v);
	}
	printf("\n");

	DLinkList_Delete(list, DLinkList_Length(list)-1);
	DLinkList_Delete(list, 0);
	//DLinkList_Delete(list, 3);

	for(i=0; i<DLinkList_Length(list); i++)
	{
		pv = (struct Value*)DLinkList_Next(list);
		printf("%d\n", pv->v);
	}
	printf("\n");

	DLinkList_Reset(list);
	DLinkList_Next(list);

	pv = (struct Value*)DLinkList_Current(list);
	printf("%d\n", pv->v);

	DLinkList_DeleteNode(list, (DLinkListNode*)pv);

	pv = (struct Value*)DLinkList_Current(list);
	printf("%d\n", pv->v);

	DLinkList_Pre(list);
	pv = (struct Value*)DLinkList_Current(list);
	printf("%d\n", pv->v);

	printf("Length: %d\n", DLinkList_Length(list));

	DLinkList_Destroy(list);

	system("pause");
	return 0;
}

优点和缺点

  • 优点：双向链表在单链表的基础上增加了指向前驱的指针
    功能上双向链表可以完全取代单链表的使用
    循环链表的Next，Pre和Current操作可以高效的遍历链表中的所有元素

  • 缺点：代码复杂

Donate comment here