【数据结构】09 线性表的链式存储实现

定义

线性表的链式存储不需要用连续的存储单元来实现，不需要逻辑上相邻的两个数据元素在物理上也相邻，它是通过链建立其数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素，只需要修改连。

为了访问链表，必须找到链表的第一个数据单元，因此实际应用中常用一个称为“表头(Header)”的指针指向链表的第一个单元，并用它表示一个具体的链表。

结点的结构定义

typedef int ElementType;
typedef struct LNode* PtrToLNode;
typedef PtrToLNode Position;
typedef PtrToLNode List;

struct LNode {
	ElementType Data;
	PtrToLNode Next;
};

1
2
3
4
5
6
7
8
9
10

相关操作

初始化

List MakeEmpty(List L) {
	L = (LNode*)malloc(sizeof(LNode));
	L->Next = NULL;
	return L;
}
1
2
3
4
5

插入

bool Insert(List L, ElementType X, int i) {
	int cnt = 0;
	List p = L;
	//printf("p: %d\n", p->Data);
	while (p != NULL && cnt != i-1) {
		p = p->Next;
		cnt++;
	}
	//printf("cnt: %d\n", cnt);
	if (p == NULL || cnt != i - 1) {
		printf("insert error!\n");
		return false;
	}
	else {
		List temp = (LNode*)malloc(sizeof(LNode) * 1);
		temp->Data = X;
		
		temp->Next = p->Next;
		p->Next = temp;
	}
	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

求表长

int ListLength(List L) {
	int length = 0;
	List p = L->Next;
	while (p != NULL) {
		p = p->Next;
		length++;
	}
	return length;

}
1
2
3
4
5
6
7
8
9
10

查找

按序号查找

ElementType Findkth(List L, int K) {
	//找到第i个结点的值
	List p = L->Next;
	int i = 1;
	while (p != NULL && i != K) {
		p = p->Next;
		i++;
	}

	if (p == NULL || i != K) {
		printf("can't find!\n");
		return -1;
	}
	else {
		return p->Data;
	}
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

按值查找

Position Find(List L, ElementType X) {
	//由数值返回其结点位置
	List p = L->Next;
	while (p != NULL && p->Data !=X) {
	
		p = p->Next;
	}

	if (p->Data == X) {
		return p;
	}
	else{
		return NULL;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除

bool Deletei(List L, int i) {
	//删除第i个结点
	List p=L, q = L;
	int cnt = 0;
	while (p != NULL && cnt!=i) {
		cnt++;
		q = p;
		p = p->Next;
	}
	if (p == NULL || cnt != i) {
		return false;
	}
	q->Next = p->Next;
	free(p);
	return true;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

完整代码

# include <stdio.h>
# include <stdlib.h>

typedef int ElementType;
typedef struct LNode* PtrToLNode;
typedef PtrToLNode Position;
typedef PtrToLNode List;

struct LNode {
	ElementType Data;
	PtrToLNode Next;
};

List MakeEmpty(List L) {
	L = (LNode*)malloc(sizeof(LNode));
	L->Next = NULL;
	return L;
}

bool Insert(List L, ElementType X, int i) {
	int cnt = 0;
	List p = L;
	//printf("p: %d\n", p->Data);
	while (p != NULL && cnt != i-1) {
		p = p->Next;
		cnt++;
	}
	//printf("cnt: %d\n", cnt);
	if (p == NULL || cnt != i - 1) {
		printf("insert error!\n");
		return false;
	}
	else {
		List temp = (LNode*)malloc(sizeof(LNode) * 1);
		temp->Data = X;
		
		temp->Next = p->Next;
		p->Next = temp;
	}
	return true;

}
void print_link(List L) {
	List p = L->Next;
	while (p != NULL) {
		printf("Node : %d\n", p->Data);
		p = p->Next;
		
	}
	
}

int ListLength(List L) {
	int length = 0;
	List p = L->Next;
	while (p != NULL) {
		p = p->Next;
		length++;
	}
	return length;

}

ElementType Findkth(List L, int K) {
	//找到第i个结点的值
	List p = L->Next;
	int i = 1;
	while (p != NULL && i != K) {
		p = p->Next;
		i++;
	}

	if (p == NULL || i != K) {
		printf("can't find!\n");
		return -1;
	}
	else {
		return p->Data;
	}
	
}

Position Find(List L, ElementType X) {
	//由数值返回其结点位置
	List p = L->Next;
	while (p != NULL && p->Data !=X) {
	
		p = p->Next;
	}

	if (p->Data == X) {
		return p;
	}
	else{
		return NULL;
	}

}

bool Deletei(List L, int i) {
	//删除第i个结点
	List p=L, q = L;
	int cnt = 0;
	while (p != NULL && cnt!=i) {
		cnt++;
		q = p;
		p = p->Next;
	}
	if (p == NULL || cnt != i) {
		return false;
	}
	q->Next = p->Next;
	free(p);
	return true;

}


int main() {
	List L = NULL;
	L  = MakeEmpty(L);
	printf("Finish init!\n");
	ElementType X;
	int N;
	scanf_s("%d", &N);
	while (N--) {
		scanf_s("%d", &X);
		if (Insert(L, X, 1) == false) {
			printf("insert error!\n");
		}
		
	}
	print_link(L);
	int length = ListLength(L);
	printf("the list's length: %d\n", length);

	/*int x = Findkth(L, 2);
	printf("find: %d\n", x);

	List p = Find(L, 5);
	printf("findp: p->data: %d\n", p->Data);*/

	if (bool(Deletei(L, 2))) {
		printf("Delete Sucessfully!\n");
	}


	print_link(L);
	length = ListLength(L);
	printf("the list's length: %d\n", length);
	
}
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