数据结构 C语言前篇

发表于 阅读次数：
本文字数： 13k 阅读时长 ≈ 12 分钟

图书馆

数据结构

初始数据结构

基础理论

数据结构-第一章

图片地址

https://cdn.jsdelivr.net/gh/codexiaobo/image@main/数据结构/考研数据结构-第一章.7lhc0556ays0.jpg

PDF文档地址

https://urlify.cn/uyEZnq

线性表 和 链表

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
# include <stdio.h>
# define MAXSIZE 20
typedef int ElemType;

// 线性表的存储结构
typedef struct {
	ElemType data[MAXSIZE];
	int length;
}sqList;


// 获取一个元素并赋值给别的
int getElem(sqList L, int i, ElemType* e) {

	//校验
	if (L.length == 0 || i < 1 || i > L.length) {
		return 0;
	}

	*e = L.data[i - 1];

	return 1;
}

// 插入元素
int listInsert(sqList L, int i, ElemType e) {

	if (L.length == MAXSIZE) {
		return 0;
	}

	if (i < 1 || i > L.length) {
		return 0;
	}

	if (i <= L.length) {
		for (int k = L.length; k >= i - 1; k--) {
			L.data[k + 1] = L.data[k];
		}
	}

	L.data[i - 1] = e;

	L.length++;
	
	return 1;
}



int main() {

	sqList sqList;

	printf("%d",listInsert(sqList, 3, 2));

	return 0;
}

单链表

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
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
# include <stdio.h>
# include <stdlib.h>
#include <stdbool.h>


typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;


// 带头结点的按照位插入
bool ListInsert1(LinkList L, int i, ElemType e) {

	//检验、判断 i 插入的位置是否符合题意
	if (i < 1) {
		return false;
	}

	LNode* p;// 当前的结点
	int j = 0;// 当前指向的结点
	p = L;// L指向头节点

	// 循环遍历找到位置数据和下标
	while (p->next != NULL && j < i - 1){

		//下一结点
		p = p->next;
		//下标+1
		j++;
	}

	//校验
	if (p == NULL) {
		return false;
	}

	//动态生成结点
	LNode* s = (LNode *)malloc(sizeof(LNode));

	//将数据存到动态生成的结点中
	s->data = e;
	//将要插入节点的前一节点的下一节点连接到新节点的下一节点
	s->next = p->next;
	//将动态生成的节点连接到要插入节点的前一节点的下一节
	p->next = s;

	return true;

}



//不带头结点的
bool ListInsert2(LinkList L, int i, ElemType e) {

	//检验、判断 i 插入的位置是否符合题意
	if (i < 1) {
		return false;
	}
	
	if (i == 1) {
		LNode* s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = NULL;
		L = s;
		return true;
	}


	LNode* p;// 当前的结点
	int j = 1;// 当前指向的结点
	p = L;// L指向头节点

	// 循环遍历找到位置数据和下标
	while (p->next != NULL && j < i - 1) {

		//下一结点
		p = p->next;
		//下标+1
		j++;
	}

	//校验
	if (p == NULL) {
		return false;
	}

	//动态生成结点
	LNode* s = (LNode*)malloc(sizeof(LNode));

	//将数据存到动态生成的结点中
	s->data = e;
	//将要插入节点的前一节点的下一节点连接到新节点的下一节点
	s->next = p->next;
	//将动态生成的节点连接到要插入节点的前一节点的下一节
	p->next = s;

	return true;

}


//后插操作
bool ListlaterInsert(LNode* p, ElemType e) {

	//校验链表
	if (p == NULL) {
		return false;
	}

	//动态分配一个结点
	LNode* s = (LNode*)malloc(sizeof(LNode));
	
	//检验
	if (s == NULL) {
		return false;
	}
	//将数据存到动态生成的结点中
	s->data = e;
	//将要插入节点的前一节点的下一节点连接到新节点的下一节点
	s->next = p->next;
	//将动态生成的节点连接到要插入节点的前一节点的下一节
	p->next = s;
	
	return true;
}

//前插操作
bool ListBeforeInsert(LNode* p, ElemType e) {

	//动态分配内存空间
	LNode* s = (LNode*)malloc(sizeof(LNode));

	//检验
	if (s == NULL || p == NULL) {
		return false;
	}

	//将新节点连上
	s->next = p->next;
	p->next = s;

	//将插入的节点利用中间量与前一节点交换数据、这就相当于是在前面差点了一个结点
	ElemType temp = p->data;

	p->data = s->data;
	s->data = temp;
	return true;
}


//带头结点的删除
bool ListDelete(LinkList L, int i, ElemType e) {
	
	//检验
	if (i < 1) {
		return false;
	}

	//定义循环到的节点
	LNode* p;
	//定义指向的下标
	int j = 0;
	//将L指向头节点
	p = L;

	//循环遍历、找到要操作节点的上一结点
	while (p == NULL && j < i - 1) {
		p = p->next;
		j++;
	}

	//检验
	if (p == NULL || p->next == NULL) {
		return false;
	}

	//定义要做操作的节点
	LNode* q = p->next;
	//将要操作的结点的数据给e
	e = q->data;
	//删除结点
	p->next = q->next;
	//释放内存空间
	free(q);

	return true;
}

//指定结点删除
bool LinkListDelete(LNode* p) {

	if (p == NULL) {
		return false;
	}

	//定义p的下一节点
	LNode* q = p->next;
	//将p的下一节点的数据给p
	p->data = q->data;
	//将p节点指向q的下一结点、进行删除q
	p->next = q->next;
	//释放内存空间
	free(q);

	return true;
}


//按位查找
LNode* GetElem(LinkList L, int i) {

	//检验
	if (i < 0) {
		return NULL;
	}

	//定义循环到的节点
	LNode* p;
	//定义指向的下标
	int j = 0;
	//将L指向头节点
	p = L;

	//检验
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}

	return p;
}

//按值查找
LNode* LocateElem(LinkList L, ElemType e) {

	LNode* p = L->next;

	while (p != NULL && p->data != e) {
		p = p->next;
	}

	return p;
}

//求表的长度
int Length(LinkList L) {
	//设置初始值
	int len = 0;
	//初始
	LNode* p = L;
	//循环遍历
	while (p->next != NULL) {
		p = p->next;
		len++;
	}

	return len;
}

//创建单链表
bool initList(LinkList L) {
	//动态分配内存空间
	L = (LNode*)malloc(sizeof(LNode));
	//检验
	if (L == NULL) {
		return false;
	}
	//头节点下一节点为空
	L->next = NULL;

	return true;
}

//尾插法
LinkList List_TailInsert(LinkList L) {
	//定义变量、插入的值
	int x;
	
	//动态生成结点
	L = (LinkList)malloc(sizeof(LinkList));

	//记录一个r结点和s结点
	LNode* s,* r = L;

	//输入
	scanf_s("%d", &x);

	//输入9999结束
	while (x != 9999) {

		//动态生成内存空间
		s = (LNode*)malloc(sizeof(LNode));
		
		//将输入的值赋值给插入结点的数据
		s->data = x;
		
		//将插入的节点连到r结点
		r->next = s;

		//将r结点指向s结点、使r结点为最后一个结点
		r = s;
		//输入插入的值
		scanf_s("%d", &x);
	}

	//因为是尾部、所以r的下一结点为空	
	r->next = NULL;

	return L;
}


//头插发创建链表  链表顺序是和插入数据相反
LinkList list_HeadInsert(LinkList L) {
	
	//定义一个指针
	LNode* s;
	//定义输入值
	int x;
	//动态生成链表
	L = (LinkList*)malloc(sizeof(LinkList));

	//输入数据
	scanf_s("%d", &x);

	while (x != 9999) {

		s = (LNode *)malloc(sizeof(LNode));

		//数据赋值
		s->data = x;
		//将下一结点接到插入节点的下一结点
		s->next = L->next;
		//将插入节点接到L结点
		L->next = s;
		//输入值
		scanf_s("%d", &x);
	}

	return L;
}

双链表

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

typedef int ElemType;


//定义一个双链表的结构体、数据  前结点和后结点
typedef struct DNode {
	ElemType data;
	struct DNode* prior, * next;
}DNode,*DLinkList;

bool initDLinkList(DLinkList L) {

	//动态获取内存
	L = (DNode*)malloc(sizeof(DNode));

	//校验
	if (L == NULL) {
		return false;
	}

	//头结点的前结点为空
	L->prior = NULL;

	//头结点的后结点为空
	L->next = NULL;

	return false;
}

//判断链表是否为空
bool Empty(DLinkList L) {

	//如果为空true 反之 false
	if (L->next == NULL) {
		return true;
	}
	else {
		return false;
	}

}

//双链表带头结点的插入
bool InsertNextDNode(DNode* p, DNode* s) {

	//检验
	if (p == NULL || s == NULL) {
		return false;
	}

	//s的下一结点指向p一开始的下一结点
	s->next = p->next;

	//判断p是不是最后一个结点
	if (p->next != NULL) {
		//将p一开始的节点的前结点指向s结点
		p->next->prior = s;
	}

	//将s的前一结点指向p
	s->prior = p;

	//p的下一结点指向s
	p->next = s;

	return true;
}

//删除一个结点
bool DeleteNextDNode(DNode* p) {

	//检验
	if (p == NULL) {
		return false;
	}
	
	//找到要删除的结点
	DNode* q = p->next;
	
	//检验
	if (q == NULL) {
		return false;
	}
	
	//将p的结点指向要删除的下一结点
	p->next = q->next;

	//检验
	if (q->next != NULL) {
		//将要删除的结点的下一结点的前结点指向p
		q->next->prior = p;
	}

	//释放q要删除结点的内存空间
	free(q);
	return true;
}

//销毁链表
void DestoryList(DLinkList L) {

	while (L->next != NULL)
	{
		DeleteNextDNode(L);
	}
	free(L);

	L = NULL;
}


DNode* selectLinkList(DNode *p) {


	//向后遍历跳过头结点
	while (p->next != NULL) {
		p = p->next;
	}

	//向前遍历跳过头结点
	while (p->prior != NULL) {
		p = p->prior;
	}

	//后结点遍历
	while (p != NULL) {
		p = p->next;
	}

	//前结点遍历
	while (p != NULL) {
		p = p->prior;
	}
}

循环链表

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

typedef int ElemType;

typedef struct DNode {
	ElemType data;
	DNode* prior;
	DNode* next;
}DNode,* LinkList;

//初始化循环双链表	
bool initList(LinkList L) {

	L = (DNode*)malloc(sizeof(DNode));

	if (L == NULL) {
		return false;
	}

	L->next = L;
	L->prior = L;

	return true;
}

数据结构-第二章

图片地址

https://cdn.jsdelivr.net/gh/codexiaobo/image@main/数据结构/考研数据结构-第二章.1oz2o4mj1deo.jpg

PDF文档地址

https://urlify.cn/uyEZnq

栈 和 队列

顺序栈

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

#define maxSize 10 // 定义最大元素个数

typedef int ElemType;// 声明类型

typedef struct {
	ElemType data[maxSize];// 静态数组存放元素内容
	int top; // 栈顶指针
}sqStack;

//初始化栈
bool initStack(sqStack *s) {
	s->top = -1;
}

//判断是否为空栈
bool StackEmpty(sqStack* s) {
	if (s->top == -1) {
		return true;
	}
	else {
		return false;
	}
}

//进栈
bool push(sqStack *s,ElemType x) {
	
	//栈满情况
	if (s->top == maxSize - 1) {
		return false;
	}

	//指针上移
	s->top = s->top + 1;

	//新元素入栈
	s->data[s->top] = x;

	//等价于上边两步
	//s->data[++s->top] = x;
	return true;
}

//出栈
bool pop(sqStack* s, ElemType x) {

	//判断是否为空栈
	if (s->top == -1) {
		return false;
	}

	//出栈
	x = s->data[s->top];

	//栈顶下移
	s->top = s->top - 1;

	//等同于上两步
	//x = s->data[s->top--];

	return true;
}

//读取栈顶元素
bool getTop(sqStack* s, ElemType x) {

	//判断是否为空栈
	if (s->top == NULL) {
		return false;
	}
	//读取栈顶
	x = s->data[s->top];

	return true;
}


//IDE括号原理
bool kuohao(char str[], int length) {

	//声明一个链表
	sqStack *s;
	
	//链表初始化
	initStack(s);

	//遍历
	for (int i = 0; i < length; i++) {
		
		//如果是左括号、入栈
		if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
			push(s,str[i]);
		}
		else {
			//如果栈为空
			if (StackEmpty(s)){
				return false;
			}
			
			//接出栈的值
			int temp;
			//出栈
			pop(s,temp);

			//不匹配失败
			if (str[i] == ')' && temp != '(') {
				return false;
			}
			if (str[i] == ']' && temp != '[') {
				return false; 
			}
			if (str[i] == '}' && temp != '{') {
				return false;
			}

		}

	}

	//最后如果栈为空、匹配成功
	return StackEmpty(s);
}

顺序队列

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

#define maxSize 10

typedef int ElemType;

typedef struct{
	ElemType data[maxSize];
	ElemType front, rear;
}SqQueue;

//typedef struct {
//	ElemType data[maxSize];
//	ElemType front, rear;
//	ElemType size; //队列长度   每次入队size++ 每次出队size-- 并且判断队满是 size == maxSize 队空时为 size == 0
//};

//typedef struct {
//	ElemType data[maxSize];
//	ElemType front, rear;
//	ElemType tag; // 标记 最近的插入或删除操作 插入为tag = 1 删除为 tag = 0 那么只需要记录tag = 1时即为对满 tag = 0 时为对空
//};

//初始化队列
bool InitQueue(SqQueue* q) {

	q->front = q->rear = 0;
	
	return true;
}

bool QueueEmpty(SqQueue* q) {
	if (q->front == q->rear) {
		return true;
	}
	else {
		return false;
	}
}

bool EnQueue(SqQueue* q, int x) {

	//判断循环队列是否已经满了 这里是通过牺牲一个内存空间来做到的预先留出来一个存放rear指针
	if ((q->rear + 1) % maxSize == q->front) {
		return false;
	}

	//插入新元素
	q->data[q->rear] = x;
	
	//队尾指针 + 1 后 取模
	q->rear = (q->rear + 1) % maxSize;

	return true;

}

//出队
bool DeQueue(SqQueue* q,int x) {

	//判断队列是否已经空了
	if (q->front == q->rear) {
		return false;
	}

	//将出队数据给x
	x = q->data[q->front];

	//队头指针向后移动
	q->front = (q->front + 1) % maxSize;

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

typedef int ElemType;

// 链式队列的结点
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;

//链式队列的头指针和尾指针
typedef struct {
	LinkNode * front, * rear;
}LinkQueue;

//初始化带头结点的队列
void InitQueue(LinkQueue* q) {

	//分配内存空间
	q->front = q->rear = (LinkNode*)malloc(sizeof(LinkNode));

	//将头结点设置为空
	q->rear = NULL;

}

// 判断队列是否为空
bool EmptyQueue(LinkQueue* q) {
	if (q->front == q->rear) {
		return true;
	}
	else {
		return false;
	}
}

//不带头结点的初始化
void InitQueue2(LinkQueue* q) {

	q->front = NULL;
	q->rear = NULL;

}

//入队 带头结点
bool EnQueue(LinkQueue* q, int x) {

	//动态生成要插入的结点
	LinkNode* s = (LinkNode *)malloc(sizeof(LinkNode));

	//将x数据存入结点
	s->data = x;
	//新结点的下一结点为空、因为是在最后插入的
	s->next = NULL;

	//将新节点连在rear后面
	q->rear->next = s;

	q->rear = s;
}

//不带头结点的入队
void EnQueue2(LinkQueue *q,ElemType x) {

	//动态生成结点
	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));

	// 将x放入到data中 
	s->data = x;
	//将下一结点设置为空
	s->next = NULL;

	//因为没有头结点、所以要特殊处理一下
	if (q->front == NULL) {
		//头指针指向s
		q->front = s;
		//尾指针指向s
		q->rear = s;
	}
	else {
		//s连在尾指针指向的下一结点
		q->rear->next = s;
		//移动尾指针
		q->rear = s;
	}

}

//带头结点的出队
bool DeQueue(LinkQueue* q, int x) {

	//判断是否为空队
	if (q->front == q->rear) {
		return false;
	}

	//获得q结点尾指针的下一结点
	LinkNode* p = q->front->next;

	//将删除的数据给返回的x
	x = p->data;

	//将p的下一结点连到头结点
	q->front->next = p->next;

	//判断最后出队的是最后结点
	if (q->rear == p) {
		//头指针指向尾指针
		q->rear = q->front;
	}

	//释放内存空间
	free(q);

	return true;
}

// 不带头结点的出队
bool DeQueue2(LinkQueue* q, int x) {

	// 定义头指针 指向p 出队
	LinkNode* p = q->front;

	// 出队数据
	x = p->data;

	// 将头指针指向p的下一节点
	q->front = p->next;

	// 如果出队的是最后一个结点
	if (q->rear == p) {
		//头指针和尾指针都设置为NULL
		q->rear = NULL;
		q->front = NULL;
	}

	//释放内存空间
	free(p);

	return true;

}

数据结构-第三章

图片地址

https://cdn.jsdelivr.net/gh/codexiaobo/image@main/数据结构/考研数据结构-第三章.650lhlnzy9s0.jpg

PDF文档地址

https://urlify.cn/uyEZnq

正确的开始 微小的长进 然后持续 嘿 我是小博 带你一起看我目之所及的世界……

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

本文标题:数据结构 C语言前篇

文章作者:小博

发布时间:2021年11月26日 - 17:17

最后更新:2021年11月26日 - 17:18

原始链接:https://codexiaobo.github.io/posts/3764329825/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。