Fork me on GitHub

数据结构-线性表的链式表示与实现

发表于 | 分类于 |
字数统计: 2,535

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任务的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是非连续的。这就意味着，这些数据元素可以存储在内存未被占用的任意位置。

线性表的顺序存储结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素外，还要存储它的后继元素的存储地址。

为了表示每个数据元素ai与其直接后继元素的ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其后继的信息(即直接后继的存储位置)。我们把存储数据元素的域称为数据域，把存储直接后继位置的域成为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，成为结点(Node)。

n个结点链结成一个链表，即为线性表(a1,a2,…ai，ai+1，…，an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

线性表链式存储结构

1
2
3
4
5
6
7
8
typedef int ElementType;

typedef struct Node {
	ElementType data;
	struct Node* next;
} Node;

typedef struct Node *LinkedList;

data为数据域，next为指针域

线性表链式存储结构的插入

插入操作算法描述

  • p初始指向链表头结点，迭代p,最终使得p指向第i-1个结点
  • 如果p为NULL，表示第i-1个结点不存在，返回FAILURE
  • 创建新结点，令p的后继是新结点，返回SUCCESS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status listInsert(LinkedList linkedList, int i, ElementType e) {
	Node *p = linkedList;
	// j=0表示从头结点开始
	int j = 0;
	// j < i - 1条件表示循环完成后（j == i - 1结束循环），p指向第i-1个结点
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		return FAILURE;
	}
	Node *newNode = (Node*) malloc(sizeof(Node));
	newNode->data = e;
	newNode->next = p->next;
	p->next = newNode;
    linkedList->data++;
	return SUCCESS;
}

线性表链式存储结构的删除

删除操作算法描述

  • p初始指向链表头结点，迭代p,最终使得p指向第i-1个结点
  • 如果p为NULL，则返回FAILURE
  • tmp指向第i个结点，p的后继为第i个结点的后继
  • 释放掉tmp指向的结点所占内存，返回SUCCESS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status listDelete(LinkedList linkedList, int i, ElementType *e) {
	Node *p = linkedList;
	int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		return FAILURE;
	}
	Node *tmp = p->next;
	p->next = tmp->next;
	*e = tmp->data;
	free(tmp);
    linkedList->data--;
	return SUCCESS;
}

线性表链式存储结构的逆转

反转算法描述

设置3个指针，cur指向当前要操作的元素(操作当前元素的指针域)，pre指向前驱元素，next指向后继元素，next用于保存暂存后继元素的位置信息

  • 使得next指向cur的后继元素，因为下一步要修改cur元素的指针域，如果没有这一步，将找不到cur的后继元素
  • 将cur指向的当前元素的指针域修改为指向pre指向的元素
  • 使得pre指向cur指向的元素
  • 令cur与next的指向相同
  • 循环结束后，创建新的头结点（当然用之前的头节点也可以，只要修改指针域令其指向pre指向的结点），令头结点的指针域指向pre指向的结点
  • 释放原来头结点占用的内存空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LinkedList listReverse(LinkedList list) {
	Node *cur = list->next;
	if (!cur || !cur->next) {
		return list;
	}
	Node *pre = NULL;
	Node *next = NULL;

	while (cur) {
		next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	LinkedList reverseList = (LinkedList) malloc(sizeof(Node));
	// 拷贝链表长度数据
	reverseList->data = list->data;
	reverseList->next = pre;
	free(list);
	return reverseList;

}

线性表链式存储结构的查找

算法描述

  • p指向第一个结点，j=1
  • 迭代直到j=i，退出循环
  • 如果p为NULL则返回FAILURE
  • 用e来返回第i个元素的数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status listSearch(LinkedList list, int i, ElementType *e) {
	Node *p = list->next;
	// j=1表示从第1个结点开始
	int j = 1;
	while (p && j < i) {
		p = p->next;
		++j;
	}
	printf("i=%d,j=%d\n", i, j);
	if (!p || j > i) {
		return FAILURE;
	}
	*e = p->data;
	return SUCCESS;
}

线性表链式存储结构查找倒数第k个结点

算法描述

  • 设置两个指针p1,p2初始都指向第1个结点
  • p2向右移动k个位置
  • p1,p2一起向右移动，直至p2移动到末尾
  • 返回p1,即倒数第k个结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Node* listTheBackKthNode(LinkedList list, int k) {
	if (!list->next || k <= 0 || k > list->data) {
		return NULL;
	}
	// 设置两个指针p1,p2初始都指向第1个结点，p2向右移动k个位置,然后p1,p2同时向右移动，直至p2移动到末尾
	Node *p1 = list->next;
	Node *p2 = p1;
	int j = 1;
	while (p2->next && j < k) {
		p2 = p2->next;
		j++;
	}
	while (p2->next) {
		p2 = p2->next;
		p1 = p1->next;
	}
	return p1;
}

线性表链式存储结构查中间结点

算法描述

与上述查找倒数第k个结点的算法一样，只不过倒数第几个，要根据链表长度计算一下而已，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Node* listTheMiddleNode(LinkedList list) {
	if (!list->next) {
		return NULL;
	}
	// 获取链表的长度（头结点数据域存储了链表的长度）
	int len = list->data;
	int mid = len / 2;
	Node *p1 = list->next;
	Node *p2 = p1;
	int j = 1;
	while (p2 && j < mid + 1) {
		p2 = p2->next;
		j++;
	}
	while (p2->next) {
		p2 = p2->next;
		p1 = p1->next;
	}
	return p1;
}

线性表链式存储完整代码

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

#define SUCCESS 1
#define FAILURE 0

typedef int Status;
typedef int ElementType;

typedef struct Node {
	ElementType data;
	struct Node* next;
} Node;

typedef struct Node *LinkedList;

void listInit(LinkedList *list) {
	// 头结点数据域存储链表长度
	(*list)->data = 0;
	(*list)->next = NULL;
	// list的值是linkedList的地址，所以跟&linkedList是一样的
	//printf("init method list's address = %p\n", list);
	// &list是指向linkedList指针的地址
	//printf("init method &list's address = %p\n", &list);
	// 是头结点的地址
	//printf("init method *list's address = %p\n", *list);
	
    // 若在这里初始化n个结点，则参数必须是LinkedList *list,不能是LinkedList list。需要用到指向指针的指针，因为main函数中的linkedList与listInit的形参list指向的内存地址不一样。
    // 以下代码还是注释掉吧，初始化只需要把data值置为0，next指针域置为NULL
	//	Node *p = (*list);
	//	for (int i = 0; i < n; i++) {
	//		p->next = (Node*) malloc(sizeof(Node));
	//		p->next->data = i;
	//		p->next->next = NULL;
	//		p = p->next;
	//	}
}

Status listSearch(LinkedList list, int i, ElementType *e) {
	Node *p = list->next;
	// j=1表示从第1个结点开始
	int j = 1;
	while (p && j < i) {
		p = p->next;
		++j;
	}
	printf("i=%d,j=%d\n", i, j);
	if (!p || j > i) {
		return FAILURE;
	}
	*e = p->data;
	return SUCCESS;
}

Status listInsert(LinkedList linkedList, int i, ElementType e) {
	Node *p = linkedList;
	// j=0表示从头结点开始
	int j = 0;
	// j < i - 1条件表示循环完成后（j == i - 1结束循环），p指向第i-1个结点
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		return FAILURE;
	}
	Node *newNode = (Node*) malloc(sizeof(Node));
	newNode->data = e;
	newNode->next = p->next;
	p->next = newNode;
	linkedList->data++;
	return SUCCESS;
}

Status listDelete(LinkedList linkedList, int i, ElementType *e) {
	Node *p = linkedList;
	int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		return FAILURE;
	}
	Node *tmp = p->next;
	p->next = tmp->next;
	*e = tmp->data;
	free(tmp);
	linkedList->data--;
	return SUCCESS;
}

LinkedList listReverse(LinkedList list) {
	Node *cur = list->next;
	if (!cur || !cur->next) {
		return list;
	}
	Node *pre = NULL;
	Node *next = NULL;

	while (cur) {
		next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}
	LinkedList reverseList = (LinkedList) malloc(sizeof(Node));
	// 拷贝链表长度数据
	reverseList->data = list->data;
	reverseList->next = pre;
	free(list);
	return reverseList;

}

/**
 * 找倒数第k个结点
 */
Node* listTheBackKthNode(LinkedList list, int k) {
	if (!list->next || k <= 0 || k > list->data) {
		return NULL;
	}
	// 设置两个指针p1,p2初始都指向第1个结点，p2向右移动k个位置,然后p1,p2同时向右移动，直至p2移动到末尾
	Node *p1 = list->next;
	Node *p2 = p1;
	int j = 1;
	while (p2->next && j < k) {
		p2 = p2->next;
		j++;
	}
	while (p2->next) {
		p2 = p2->next;
		p1 = p1->next;
	}
	return p1;
}

/**
 * 找到中间结点
 */
Node* listTheMiddleNode(LinkedList list) {
	if (!list->next) {
		return NULL;
	}
	// 获取链表的长度（头结点数据域存储了链表的长度）
	int len = list->data;
	int mid = len / 2;
	Node *p1 = list->next;
	Node *p2 = p1;
	int j = 1;
	while (p2 && j < mid + 1) {
		p2 = p2->next;
		j++;
	}
	while (p2->next) {
		p2 = p2->next;
		p1 = p1->next;
	}
	return p1;
}

void listPrint(LinkedList list) {
	Node *p = list->next;
	while (p) {
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

int main() {
	// 初始化一个单项链表的头结点
	// LinkedList linkedList = (Node*)malloc(sizeof(Node));
	LinkedList linkedList = (LinkedList) malloc(sizeof(Node));
	// 头结点的地址
	printf("main method linkedList's address = %p\n", linkedList);
	// 指向头结点的指针的地址
	printf("main method &linkedList's address = %p\n", &linkedList);
	listInit(&linkedList);
	for (int i = 1; i <= 10; i++) {
		ElementType data = i;
		listInsert(linkedList, i, data);
	}
	ElementType searchElement = -1;
	Status searchResult = listSearch(linkedList, 3, &searchElement);
	printf("search result:%d,the element is %d\n", searchResult, searchElement);
	printf("insert %d\n", listInsert(linkedList, 10, 33));
	listPrint(linkedList);
	ElementType deletedElement = -1;
	Status deleteResult = listDelete(linkedList, 2, &deletedElement);
	printf("delete result:%d,deleted element:%d\n", deleteResult,
			deletedElement);
	listPrint(linkedList);
	LinkedList reverseList = listReverse(linkedList);
	listPrint(reverseList);
	int k = 2;
	Node *theBackKthNode = listTheBackKthNode(reverseList, k);
	printf("the back %dth node is %d\n", k,
			theBackKthNode ? theBackKthNode->data : -1);

	Node *theMiddleNode = listTheMiddleNode(reverseList);
	printf("the middle node is %d\n", theMiddleNode->data);
	return 0;
}
分享到： 微信 新浪微博 Twitter Facebook 复制网址 邮件 收藏夹 一键分享 更多