使用C语言模拟顺序表和链表_用c语言(1)定义一个存储整数的顺序表和单链表。 (2)编写初始化/创建、插入、查找

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种最基本、最简单、也是最常用的数据结构。
常见的线性表：顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构，即各元素之间是序偶关系。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
下面仅讨论顺序表和链表。

顺序表和链表

1. 顺序表

1.1 顺序表的定义

顺序表使用一段物理地址连续的存储单元依次存储数据元素，常使用数组实现。
顺序表一般可以分为静态顺序表和动态顺序表。
静态顺序表只适用于确定知道需要存多少数据的场景，使用起来有较大的局限性。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小。

1.2 顺序表的实现

根据顺序表的定义可知，顺序表结构体应包含一个指向一段连续内存空间的指针，这个空间的大小是动态开辟的，既然如此，也就还需要一个变量保存空间的容量，一个变量保存已使用的空间大小。
于是定义顺序表结构体如下：

typedef struct SeqList {
	DataType *arr;
	size_t length;
	size_t capacity;
}SeqList;
1
2
3
4
5

顺序表使用前肯定是要初始化的。除此之外，为满足使用的需求，顺序表还应该具有增、删、查、改等功能。
顺序表的相关操作可定义如下：

//初始化
SeqList* SeqListInit() {
	SeqList* sl;
	sl = (SeqList *)malloc(sizeof(SeqList));
	sl->capacity = sl->length = 0;
	return sl;
}

//扩容
void SeqListExtent(SeqList *sl) {
	assert(sl);
	if (sl->capacity == 0) {
		sl->arr = (DataType *)malloc(sizeof(DataType));
		sl->capacity = 1;
	}
	else {
		sl->arr = (DataType *)realloc(sl->arr, 2 * sl->capacity * sizeof(DataType));
		sl->capacity = sl->capacity * 2;
	}
}

//销毁
void SeqListDestory(SeqList* sl) {
	assert(sl);
	free(sl->arr);
	free(sl);
}

//判满
int CapacityIsFull(SeqList* sl) {
	assert(sl);
	return sl->length == sl->capacity;
}

//判空
int IsEmptyList(SeqList *sl) {
	assert(sl);
	return sl->length == 0;
}

//尾插
void SeqListPushBack(SeqList* sl, DataType x) {
	assert(sl);
	if (CapacityIsFull(sl)) {
		SeqListExtent(sl);
	}
	sl->arr[sl->length] = x;
	++sl->length;
}

//尾删
DataType SeqListPopBack(SeqList* sl) {
	assert(sl);
	if (IsEmptyList(sl)) {
		printf("表已空!\n");
		return -1;
	}
	--sl->length;
	return sl->arr[sl->length];
}

void SeqListInsert(SeqList* sl, size_t pos, DataType x);
//头插
void SeqListPushFront(SeqList* sl, DataType x) {
	SeqListInsert(sl, 0, x);
}

void SeqListErase(SeqList* sl, size_t pos);
//头删
void SeqListPopFront(SeqList* sl) {
	SeqListErase(sl, 0);
}

//查找元素
int SeqListFind(SeqList* sl, DataType x) {
	assert(sl);
	size_t cur = 0;
	while (cur < sl->length) {
		if (sl->arr[cur] == x) {
			break;
		}
		++cur;
	}
	if (cur == sl->length) {
		return -1;
	}
	return cur;
}

//指定位置插入元素
void SeqListInsert(SeqList* sl, size_t pos, DataType x) {
	assert(sl);
	if (pos < sl->length) {
		printf("插入位置非法!\n");
		return;
	}
	++sl->length;
	if (CapacityIsFull(sl)) {
		SeqListExtent(sl);
	}
	size_t cur = sl->length - 1;
	while (cur > pos) {
		sl->arr[cur] = sl->arr[cur - 1];
		--cur;
	}
	sl->arr[cur] = x;
}

//删除指定位置元素
void SeqListErase(SeqList* sl, size_t pos) {
	assert(sl);
	if (IsEmptyList(sl)) {
		printf("表已空!\n");
		return;
	}
	if (pos < sl->length) {
		printf("删除位置非法!\n");
		return;
	}
	for (size_t cur = pos; cur < sl->length - 1; ++cur) {
		sl->arr[cur] = sl->arr[cur + 1];
	}
	--sl->length;
}

//移除某元素x
void SeqListRemove(SeqList* sl, DataType x) {
	int pos = SeqListFind(sl, x);
	if (pos != -1)
		SeqListErase(sl, pos);
	else {
		printf("找不到该元素.\n");
	}
}

//修改指定位置的元素值
void SeqListModify(SeqList* sl, size_t pos, DataType x) {
	assert(sl);
	if (pos < sl->length) {
		printf("修改位置非法!\n");
		return;
	}
	sl->arr[pos] = x;
}

//打印顺序表
void SeqListPrint(SeqList* sl) {
	assert(sl);
	for (int i = 0; i < sl->length; ++i) {
		printf("%d ", sl->arr[i]);
	}
	printf("\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
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

3. 链表

3.1 链表的定义

链表是一种逻辑上连续，而物理存储结构上非连续、非顺序的存储结构，链表的各节点通过指针链接起来。
链表常见的结构有以下两种：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
   构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

除了这两种之外还有带头单向非循环链表，下面我们主要实现带头单向非循环链表和带头双向循环链表。

3.2 链表的实现

同顺序表的功能类似，链表也应能完成增删查改等功能。
(1) 单链表：
单链表的结构体定义：

typedef int DataType;

typedef struct SingleListNode{
	DataType data;
	struct SingleListNode *next;
}SingleListNode;
//头结点
typedef struct SingleListHead{
	SingleListNode *head;
}SHead;
1
2
3
4
5
6
7
8
9
10

单链表的相关操作可定义如下：

//初始化头结点
void InitSListHead(SHead* pl) {
	assert(pl);
	pl->head = (SingleListNode *)malloc(sizeof(SingleListNode));
	pl->head->data = 0;
	pl->head->next = NULL;
}

//销毁链表
void SListDestory(SHead* pl) {
	assert(pl);
	SingleListNode *cur = pl->head->next;
	while (cur && cur->next) {
		SingleListNode *p = cur->next;
		free(cur);
		cur = p;
	}
	if (cur) {
		free(cur);
	}
}

//创建链表节点
SingleListNode* CreatSListNode(DataType x) {
	SingleListNode *node;
	node = (SingleListNode *)malloc(sizeof(SingleListNode));
	node->data = x;
	node->next = NULL;
	return node;
}

//查找节点
SingleListNode* FindSListNode(SHead* pl, DataType x) {
	assert(pl);
	SingleListNode *cur = pl->head->next;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//查找某节点的前驱
SingleListNode* FindSListBefore(SHead *pl, SingleListNode *pos) {
	assert(pl && pos);
	SingleListNode *pre = pl->head;
	while (pre) {
		if (pre->next == pos) {
			break;
		}
		pre = pre->next;
	}
	return pre;
}

// 在pos的后面进行插入
void SListInsertAfter(SingleListNode *pos, DataType x) {
	assert(pos);
	SingleListNode *node = CreatSListNode(x);
	node->next = pos->next;
	pos->next = node;
}

// 在pos的前面进行插入
int SListInsertPre(SHead *pl, SingleListNode *pos, DataType x) {
	assert(pl && pos);
	SingleListNode *pre = FindSListBefore(pl, pos);
	if (pre == NULL) {
		printf("插入失败!节点不存在.\n");
		return 0;
	}
	SingleListNode *node = CreatSListNode(x);
	node->data = x;
	node->next = pos;
	pre->next = node;
	return 1;
}

//移除pos后面的节点
int SListEraseAfter(SingleListNode* pos) {
	if (pos == NULL) {
		return 0;
	}
	if (pos->next) {
		SingleListNode *del = pos->next;
		pos->next = pos->next->next;
		free(del);
		return 1;
	}
	printf("节点不存在!\n");
	return 0;
}

//头插
void SListPushFront(SHead* pl, DataType x) {
	SListInsertAfter(pl->head, x);
}

//头删
void SListPopFront(SHead* pl) {
	SListEraseAfter(pl->head);
}

//修改某节点
int AlterSList(SingleListNode *pos, DataType x) {
	if (pos == NULL) {
		printf("修改失败! 节点不存在.\n");
		return 0;
	}
	pos->data = x;
	return 1;
}

//删除某节点
int SListRemove(SHead* pl, DataType x) {
	assert(pl);
	SingleListNode *cur = FindSListNode(pl, x);
	if (cur == NULL) {
		printf("删除失败! 节点不存在.\n");
		return 0;
	}
	SingleListNode *pre = FindSListBefore(pl, cur);
	pre->next = cur->next;
	free(cur);
	return 1;
}

//打印链表
void SListPrint(SHead* pl) {
	assert(pl);
	SingleListNode *node = pl->head->next;
	while (node) {
		printf("%d ", node->data);
		node = node->next;
	}
	printf("\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
129
130
131
132
133
134
135
136
137
138
139

(2)双向链表：
双向链表的结构体定义如下：

typedef int DataType;

typedef struct CircularListNode{
	DataType data;
	struct CircularListNode *next;
	struct CircularListNode *pre;
}CListNode;

typedef struct CircularListHead{
	struct CircularListNode *head;
}CListHead;
1
2
3
4
5
6
7
8
9
10
11

双向链表的相关操作如下：

//初始化
void InitCListHead(CListHead* pl) {
	assert(pl);
	pl->head = (CListNode *)malloc(sizeof(CListNode));
	pl->head->data = 0;
	pl->head->next = pl->head;
	pl->head->pre = pl->head;
}

//销毁链表
void CListDestory(CListHead* pl) {
	assert(pl);
	if (pl->head->next == pl->head) {
		printf("链表已空\n");
		return;
	}
	CListNode *cur = pl->head->next;
	CListNode *later = pl->head->pre;
	while (cur != later) {
		cur = cur->next;
		free(cur->pre);
	}
	free(cur);
}

//查找节点
CListNode* CListFind(CListHead *pl, DataType x) {
	assert(pl);
	CListNode *cur = pl->head->next;
	while (cur != pl->head) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	printf("节点不存在!\n");
	return NULL;
}

// 在pos的前面进行插入
void CListInsert(CListNode *pos, DataType x) {
	assert(pos);
	CListNode *node;
	node = (CListNode *)malloc(sizeof(CListNode));
	node->data = x;
	CListNode *pre = pos->pre;
	pos->pre = node;
	node->next = pos;
	node->pre = pre;
	pre->next = node;
}

// 删除pos位置的节点
void CListErase(CListNode *pos) {
	assert(pos);
	if (pos->next == pos) {
		printf("链表已空!\n");
		return;
	}
	pos->next->pre = pos->pre;
	pos->pre->next = pos->next;
	free(pos);
}

//移除某元素x
void CListRemove(CListHead* pl, DataType x) {
	CListNode *cur = CListFind(pl, x);
	if (cur == NULL) {
		printf("删除失败!\n");
		return;
	}
	CListErase(cur);
}

//打印链表
void CListPrint(CListHead* pl) {
	CListNode *cur = pl->head->next;
	while (cur != pl->head) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//尾插
void CListPushBack(CListHead* pl, DataType x) {
	CListInsert(pl->head, x);
}

void CListPopBack(CListHead* pl) {
	CListErase(pl->head->pre);
}

//头插
void CListPushFront(CListHead* pl, DataType x) {
	CListInsert(pl->head->next, x);
}

//头删
void CListPopFront(CListHead* pl) {
	CListErase(pl->head->next);
}
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

注意，在上述操作中，我并没有对链表的头结点进行删除或修改的操作，因为我定义的链表是带头结点的链表，头结点的作用就是作为该链表的一个标志，因此一旦定义并初始化了一个链表，这个链表的头结点就不会被释放直至程序运行结束。
当然，你也可以定义为带头指针的链表，这样就可以对头结点进行操作了，但是同样的，你不能对头指针进行删除或修改的操作。

4. 顺序表和链表的优缺点

(1) 顺序表

优势：
　　地址空间连续，支持随机访问。
　　
不足：

1. 插入删除操作较麻烦；
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗；
3. 增容后可能会存在空间的浪费。

(2) 链表：

优势：
　　插入删除操作灵活，扩容时不会出现空间的浪费，也不用担心连续的内存空间不足导致增容失败。
　　
不足：

1. 不支持随机访问，查找节点较麻烦；
2. 排序操作较复杂。