数据结构 = 数据的存储 + 数据的操作 (遍历，查找，删除) 数据的存储 = 个体的存储 + 个体之间的关系 算法 = 对存储数据的操作

复习知识

数组指针

  • 用指针实现数组的创建，追加，插入，删除，排序，倒置，打印，以及判断空满状态。
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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>

struct Arr {
    int* pBase; //数组的首地址
    int len; //数组的规定长度
    int cnt; //数组的实际长度
};

void init_arr(struct Arr* parr, int length);
bool append_arr(struct Arr* parr, int val);
bool is_empty(struct Arr* parr);
bool is_full(struct Arr* parr);
void show_arr(struct Arr* parr);
bool insert_arr(struct Arr* parr, int pos, int val);
bool delay_arr(struct Arr* parr, int pos, int* val);
//bool get();
void sort_arr(struct Arr* parr);
void inversion_arr(struct Arr* parr);


void init_arr(struct Arr* parr, int length) {
    parr->pBase = (int*)malloc(sizeof(int) * length);  // 修正类型转换
    if (parr->pBase == NULL) {
        printf("动态内存分配失败\n");
        exit(-1);
    }
    else {
        parr->len = length;
        parr->cnt = 0;
    }
}

bool append_arr(struct Arr* parr, int val) {
    if (is_full(parr)) {
        printf("数组已满\n");
        return false;
    }
    else {
        parr->pBase[parr->cnt] = val;
        parr->cnt++;
        return true;
    }
}

bool is_empty(struct Arr* parr) {
    return parr->cnt == 0;
}

bool is_full(struct Arr* parr) {
    return parr->cnt == parr->len;
}

void show_arr(struct Arr* parr) {
    if (is_empty(parr)) {
        printf("数组为空\n");
    }
    else {
        for (int i = 0; i < parr->cnt; i++) {  // 修正 for 循环
            printf("%d ", parr->pBase[i]);
        }
        printf("\n");
    }
}


bool insert_arr(struct Arr* parr, int pos, int val) {
    if ((is_full(parr))) {
        return false;
    }
    else {
        if (pos < 0 || pos > parr->len-1 || pos > parr->cnt-1) {
            return false;
        }
        else {
            //printf("%d", parr->cnt);
            for (int i = (parr->cnt - 1); i >= pos; i--) {
                parr->pBase[i + 1] = parr->pBase[i];
            }
            parr->pBase[pos] = val;
            parr->cnt++;
            return true;
        }
    }
}


bool delay_arr(struct Arr* parr, int pos, int* val) {
    if ((is_empty(parr))) {
        return false;
    }
    else {
        if (pos < 0 || pos >= parr->len - 1 || pos > parr->cnt-1) {
            return false;
        }
        else {
            *val = parr->pBase[pos];
            for (int i = pos; i < parr->cnt-1; i++) {
                parr->pBase[i] = parr->pBase[i + 1];
            }
            parr->cnt --;
            return true;
        }
    }

}


void inversion_arr(struct Arr* parr) {
    int i = 0;
    int j = parr->cnt - 1;
    int temp;
    while (i < j) {
        temp = parr->pBase[i];
        parr->pBase[i] = parr->pBase[j];
        parr->pBase[j] = temp;
        i++;
        j--;
    }
}


void sort_arr(struct Arr* parr) {
    int i=0, j=0;
    int temp;
    for (i = 0; i < parr->cnt; i++) {
        for (j = i + 1; j < parr->cnt; j++) {
            if (parr->pBase[i] > parr->pBase[j]) {
                temp = parr->pBase[i];
                parr->pBase[i] = parr->pBase[j];
                parr->pBase[j] = temp;
            }
        }
    }

}


int main() {
    int num=0;
    struct Arr arr;
    init_arr(&arr, 10);
    append_arr(&arr, -8);
    append_arr(&arr, 2);
    append_arr(&arr, 6);
    append_arr(&arr, 4);
    append_arr(&arr, 88);
    append_arr(&arr, 1);
    insert_arr(&arr, 0, 0);
    insert_arr(&arr, 6, 7);
    insert_arr(&arr, 5, 60);
    show_arr(&arr);
    if (delay_arr(&arr, 5, &num)) {
        printf("删除的元素是%d\n", num);
    }
    else {
        printf("删除失败\n");
    }
    show_arr(&arr);  
    inversion_arr(&arr);
    show_arr(&arr);
    sort_arr(&arr);
    show_arr(&arr);
    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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


struct student {
	int sid;
	char name[100];
	char sex[4];
};

typedef struct teacher {
	int sid;
	char name[100];
	char sex[4];
}* pter; // ter 为 struct teacher* 类型

typedef struct worker {
	int sid;
	char name[100];
	char sex[4];
}*pwer, wer; // pwer 为 struct worker* 类型, wer为 struct worker 类型

typedef struct student stu;

int main() {
	stu a = { 100, "张三", "男" };
	printf("%d\n", a.sid);
	printf("%s\n", a.name);
	printf("%s\n", a.sex);
	struct teacher b = { 20084, "李四", "男" };
	pter pb = &b;
	printf("%d\n", pb->sid);
	printf("%s\n", pb->name);
	printf("%s\n", pb->sex);
	wer c = { 18419, "李雪", "女" };
	printf("%d\n", c.sid);
	printf("%s\n", c.name);
	printf("%s\n", c.sex);
	pwer pc = &c;
	printf("%d\n", pc->sid);
	printf("%s\n", pc->name);
	printf("%s\n", pc->sex);
	return 0;
}

链表

链表相关知识

  1. 定义：n 个节点离散分布，彼此通过指针相连，每个节点只有前向节点一个后向节点，首节点没有前向节点，尾节点只有一个前向节点。

    专业术语：

    • 首节点：第一个有效节点
    • 尾节点：最优一个有效节点
    • 头节点：首节点之前的一个节点，把 0 占掉，方便后续操作
    • 头指针：指向头节点的指针变量
    • 尾指针：指向尾节点的指针变量

  2. 分类：

    • 单链表
    • 双链表：每一个节点有两个指针，一个指针指向前一个节点，一个指针指向后一个节点
    • 循环链表：能通过一个节点找到其他的所有节点
    • 非循环链表

  3. 算法

    • 遍历
    • 查找
    • 清空
    • 销毁
    • 求长度
    • 排序
    • 删除节点 image.png
    • 插入节点 image.png

  4. 链表的优缺点 优点：

    • 没有空间限制
    • 插入删除很快 缺点：
    • 存取速度慢

链表的创建与遍历

image.png 

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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


typedef struct Node
{
	int data;
	struct Node* pnext;
}NODE, *PNODE;

PNODE creat_list(void);
void traverse_list(PNODE phead);


PNODE creat_list() {
	int len;
	int i;
	int temp;
	printf("请输入需要链表节点的个数：");
	scanf_s("%d", &len);

	PNODE phead = (PNODE)malloc(sizeof(NODE));
	PNODE ptail = phead;
	if (phead == NULL) {
		printf("phead内存分配失败,程序终止");
		exit(-1);
	}

	for (i = 0; i < len; i++) {
		printf("请输入第%d节点的值：", i+1);
		scanf_s("%d", &temp);
		PNODE pnew = (PNODE)malloc(sizeof(NODE));
		if (pnew == NULL) {
			printf("pnew内存分配失败,程序终止");
			exit(-1);
		}
		pnew->data = temp;
		pnew->pnext = NULL;
		ptail->pnext = pnew;
		ptail = pnew;
	}
	return phead;
}


void traverse_list(PNODE phead) {
	PNODE p_temp = phead->pnext;;
	while (p_temp != NULL) {
		printf("%d ", p_temp->data);
		p_temp = p_temp->pnext;
	}
}


int main() {
	PNODE phead = NULL;
	phead = creat_list(); //创建一个非循环单链表
	traverse_list(phead);
	return 0;
}

链表是否为空

1
2
3
4
5
bool list_is_empty(PNODE phead);

bool list_is_empty(PNODE phead) {
	return phead->pnext == NULL;
}

链表的长度

1
2
3
4
5
6
7
8
9
10
11
int length_list(PNODE phead);

int length_list(PNODE phead) {
	int len=0;
	PNODE p_temp = phead->pnext;
	while (p_temp != NULL) {
		len += 1;
		p_temp = p_temp->pnext;
	}
	return len;
}

链表插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool insert_list(PNODE phead, int pos, int val);

bool insert_list(PNODE phead, int pos, int val) {
	int i = 0;
	PNODE p = phead;
	while (p != NULL && i < pos - 1) { // 在 pos 大于 0 的情况下，找到 pos 前一个节点 或者最后一个节点
		p = p->pnext;
		i = i + 1;
	}
	if (i > pos - 1 || p == NULL) { // 去除一些非法的 pos
		return false;
	}
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew内存分配失败,程序终止");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = p->pnext;
	p->pnext = pnew;
	return true;
}

链表删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool delete_list(PNODE phead, int pos, int* val) {
	int i = 0;
	PNODE p = phead;
	while (p->pnext != NULL && i < pos - 1) { // 只有一个数的链表不能移除，找到 pos 前一个节点
		p = p->pnext;
		i = i + 1;
	}
	if (i > pos - 1 || p->pnext == NULL) { // 
		return false;
	}
	PNODE prm;
	prm = p->pnext;
	*val = prm->data;
	p->pnext = p->pnext->pnext;
	free(prm);
	prm = NULL;
	return true;
}

链表追加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void append_list(PNODE phead, int val) {
	PNODE p_temp = phead;
	while (p_temp->pnext != NULL) {
		p_temp = p_temp->pnext;
	}
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew内存分配失败,程序终止");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = NULL;
	p_temp->pnext = pnew;
	return;
}

链表排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sort_list(PNODE phead, int len) {
	PNODE p1_temp, p2_temp;
	int i, j;
	int temp;
	for (i = 0, p1_temp = phead->pnext; i < len-1; i++, p1_temp = p1_temp->pnext) {
		for (j = i+1, p2_temp = p1_temp->pnext; j < len; j++, p2_temp = p2_temp->pnext) {
			if (p1_temp->data > p2_temp->data) {
				temp = p1_temp->data;
				p1_temp->data = p2_temp->data;
				p2_temp->data = temp;
			}
		}
	}
	return;
}

链表查找

1
2
3
4
5
6
7
8
9
10
11
12
bool find_list(PNODE phead, int val, PNODE pos) {
	PNODE p_temp = phead->pnext;
	int p = 1;
	while (p_temp != NULL) {
		if (p_temp->data == val) {
			append_list(pos, p);
		}
		p_temp = p_temp->pnext;
		p += 1;
	}
	return p != 1;
}

链表替换

1
2
3
4
5
6
7
8
9
10
11
12
bool replace_list(PNODE phead, int org_num, int re_num) {
	PNODE p_temp = phead->pnext;
	int p = 1;
	while (p_temp != NULL) {
		if (p_temp->data == org_num) {
			p_temp->data = re_num;
		}
		p_temp = p_temp->pnext;
		p += 1;
	}
	return p!=1;
}

完整代码

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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


typedef struct Node
{
	int data;
	struct Node* pnext;
}NODE, *PNODE;


PNODE creat_list(void);
void traverse_list(PNODE phead);
bool list_is_empty(PNODE phead);
int length_list(PNODE phead);
bool insert_list(PNODE phead, int pos, int val);
bool delete_list(PNODE phead, int pos, int* val);
void append_list(PNODE phead, int val);
void sort_list(PNODE phead, int len);
bool find_list(PNODE phead, int val, PNODE pos);
bool replace_list(PNODE phead, int org_num, int re_num);


PNODE creat_list() {
	int len;
	int i;
	int temp;
	printf("请输入需要链表节点的个数：");
	scanf_s("%d", &len);

	PNODE phead = (PNODE)malloc(sizeof(NODE));
	PNODE ptail = phead;
	if (phead == NULL) {
		printf("phead内存分配失败,程序终止");
		exit(-1);
	}
	phead->pnext = NULL;
	for (i = 0; i < len; i++) {
		printf("请输入第%d节点的值：", i+1);
		scanf_s("%d", &temp);
		PNODE pnew = (PNODE)malloc(sizeof(NODE));
		if (pnew == NULL) {
			printf("pnew内存分配失败,程序终止");
			exit(-1);
		}
		pnew->data = temp;
		pnew->pnext = NULL;
		ptail->pnext = pnew;
		ptail = pnew;
	}
	return phead;
}


PNODE creat_list_v2(void) {
	PNODE phead = (PNODE)malloc(sizeof(NODE));
	if (phead == NULL) {
		printf("phead内存分配失败,程序终止");
		exit(-1);
	}
	phead->pnext = NULL;
	
	return phead;
}


void traverse_list(PNODE phead) {
	PNODE p_temp = phead->pnext;
	while (p_temp != NULL) {
		printf("%d ", p_temp->data);
		p_temp = p_temp->pnext;
	}
	printf("\n");
	return;
}


bool list_is_empty(PNODE phead) {
	return phead->pnext == NULL;
}


int length_list(PNODE phead) {
	int len=0;
	PNODE p_temp = phead->pnext;
	while (p_temp != NULL) {
		len += 1;
		p_temp = p_temp->pnext;
	}
	return len;
}


void sort_list(PNODE phead, int len) {
	PNODE p1_temp, p2_temp;
	int i, j;
	int temp;
	for (i = 0, p1_temp = phead->pnext; i < len-1; i++, p1_temp = p1_temp->pnext) {
		for (j = i+1, p2_temp = p1_temp->pnext; j < len; j++, p2_temp = p2_temp->pnext) {
			if (p1_temp->data > p2_temp->data) {
				temp = p1_temp->data;
				p1_temp->data = p2_temp->data;
				p2_temp->data = temp;
			}
		}
	}
	return;
}


bool insert_list(PNODE phead, int pos, int val) {
	int i = 0;
	PNODE p = phead;
	while (p != NULL && i < pos - 1) { // 在 pos 大于 0 的情况下，找到 pos 前一个节点 或者最后一个节点
		p = p->pnext;
		i = i + 1;
	}
	if (i > pos - 1 || p == NULL) { // 去除一些非法的 pos
		return false;
	}
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew内存分配失败,程序终止");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = p->pnext;
	p->pnext = pnew;
	return true;
}


bool delete_list(PNODE phead, int pos, int* val) {
	int i = 0;
	PNODE p = phead;
	while (p->pnext != NULL && i < pos - 1) { // 只有一个数的链表不能移除，找到 pos 前一个节点
		p = p->pnext;
		i = i + 1;
	}
	if (i > pos - 1 || p->pnext == NULL) { // 
		return false;
	}
	PNODE prm;
	prm = p->pnext;
	*val = prm->data;
	p->pnext = p->pnext->pnext;
	free(prm);
	prm = NULL;
	return true;
}


void append_list(PNODE phead, int val) {
	PNODE p_temp = phead;
	while (p_temp->pnext != NULL) {
		p_temp = p_temp->pnext;
	}
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew内存分配失败,程序终止");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = NULL;
	p_temp->pnext = pnew;
	return;
}


bool find_list(PNODE phead, int val, PNODE pos) {
	PNODE p_temp = phead->pnext;
	int p = 1;
	while (p_temp != NULL) {
		if (p_temp->data == val) {
			append_list(pos, p);
		}
		p_temp = p_temp->pnext;
		p += 1;
	}
	return p != 1;
}


bool replace_list(PNODE phead, int org_num, int re_num) {
	PNODE p_temp = phead->pnext;
	int p = 1;
	while (p_temp != NULL) {
		if (p_temp->data == org_num) {
			p_temp->data = re_num;
		}
		p_temp = p_temp->pnext;
		p += 1;
	}
	return p!=1;
}


//int main() {
//	PNODE phead = NULL;
//	PNODE pos = NULL;
//	int len;
//	int rm_num;
//	int find_num = 5;
//	phead = creat_list(); //创建一个非循环单链表
//	pos = creat_list_v2();
//
//	if (list_is_empty(phead)) {
//		printf("链表为空\n");
//	}
//	else {
//		printf("链表非空\n");
//	}
//	traverse_list(phead);
//	
//	len = length_list(phead);  //求链表的长度
//	printf("链表长度是%d\n", len);
	
	//insert_list(phead, len, 99); //在链表任意位置插入 val 
	//traverse_list(phead);

	//sort_list(phead, len); //在链表排序
	//printf("链表排序后的顺序是\n");
	//traverse_list(phead);
	//
	//delete_list(phead, 2, &rm_num); //删除指定位置的链表
	//printf("移除的数字是%d\n", rm_num);
	//traverse_list(phead);
	
	//append_list(phead, 100); //在链表末尾追加 val
	//traverse_list(phead);

//	if (find_list(phead, find_num, pos)) {
//		printf("链表中找到的 %d 的位置是：",  find_num);
//		traverse_list(pos);
//		free(pos);
//		replace_list(phead, find_num, -1);
//		traverse_list(phead);
//	}
//	else {
//		printf("链表中不存在 %d \n", find_num);
//	}
//	return 0;
//}

栈

栈相关知识

  1. 定义：一种先进后出的存储结构
  2. 分类：
    • 静态栈，以数组的存储方法
    • 动态栈，以数链表的存储方法
  3. 算法
    • 初始化 image.png|275
    • 出栈
    • 入栈 image.png|275
  4. 应用
    • 函数调用
    • 中断
    • 表达式求值
    • 内存分配
    • 缓冲处理
    • 迷宫

栈初始化

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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


typedef struct Node
{
	int data;
	struct Node* pnext;
}NODE, * PNODE;


typedef struct stack
{
	PNODE ptop;
	PNODE pbottom;
}STACK, *PSTACK;

void init_stack(PSTACK pstack);

void init_stack(PSTACK pstack) {
	PNODE phead = (PNODE)malloc(sizeof(NODE));
	if (phead == NULL) {
		printf("phead 内存分配失败");
		exit(-1);
	}
	pstack->pbottom = phead;
	pstack->ptop = phead;
	pstack->ptop->pnext = NULL;
}

堆栈

1
2
3
4
5
6
7
8
9
10
11
12
13
void push_stack(PSTACK pstack, int val);


void push_stack(PSTACK pstack, int val) {
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew 内存分配失败");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = pstack->ptop;
	pstack->ptop = pnew;
}

出栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool pop_stack(PSTACK pstack, int* val);


bool pop_stack(PSTACK pstack, int* val) {
	PNODE ptemp= pstack->ptop;
	if (is_empty_stack(pstack)) {
		return false;
	}
	else {
		pstack->ptop = pstack->ptop->pnext;
		*val = ptemp->data;
		free(ptemp);
		return true;
	}
}

栈是否为空

1
2
3
4
5
6
bool is_empty_stack(PSTACK pstack);


bool is_empty_stack(PSTACK pstack) {
	return pstack->ptop == pstack->pbottom;
}

栈的遍历

1
2
3
4
5
6
7
8
9
10
void traverse_stack(PSTACK pstack);

void traverse_stack(PSTACK pstack) {
	PNODE ptop = pstack->ptop;
	while (ptop != pstack->pbottom) {
		printf("%d ", ptop->data);
		ptop = ptop->pnext;
	}
	printf("\n");
}

栈的清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void clear_stack(PSTACK pstack);

void clear_stack(PSTACK pstack) {
	PNODE ptop = pstack->ptop;
	PNODE ptemp = NULL;
	if (is_empty_stack(pstack)) {
		return;
	}
	else {
		while (ptop != pstack->pbottom) {
			ptemp = ptop;
			ptop = ptop->pnext;
			free(ptemp);
		}
		pstack->ptop = pstack->pbottom;
	}
}

完整代码

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>  // 用于 malloc 和 free
#include <stdbool.h>


typedef struct Node
{
	int data;
	struct Node* pnext;
}NODE, * PNODE;


typedef struct stack
{
	PNODE ptop;
	PNODE pbottom;
}STACK, *PSTACK;


void init_stack(PSTACK pstack);
void push_stack(PSTACK pstack, int val);
bool pop_stack(PSTACK pstack, int* val);
bool is_empty_stack(PSTACK pstack);
void traverse_stack(PSTACK pstack);
void clear_stack(PSTACK pstack);


void init_stack(PSTACK pstack) {
	PNODE phead = (PNODE)malloc(sizeof(NODE));
	if (phead == NULL) {
		printf("phead 内存分配失败");
		exit(-1);
	}
	pstack->pbottom = phead;
	pstack->ptop = phead;
	pstack->ptop->pnext = NULL;
}


bool is_empty_stack(PSTACK pstack) {
	return pstack->ptop == pstack->pbottom;
}


void push_stack(PSTACK pstack, int val) {
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	if (pnew == NULL) {
		printf("pnew 内存分配失败");
		exit(-1);
	}
	pnew->data = val;
	pnew->pnext = pstack->ptop;
	pstack->ptop = pnew;
}


bool pop_stack(PSTACK pstack, int* val) {
	PNODE ptemp= pstack->ptop;
	if (is_empty_stack(pstack)) {
		return false;
	}
	else {
		pstack->ptop = pstack->ptop->pnext;
		*val = ptemp->data;
		free(ptemp);
		return true;
	}
}


void traverse_stack(PSTACK pstack) {
	PNODE ptop = pstack->ptop;
	while (ptop != pstack->pbottom) {
		printf("%d ", ptop->data);
		ptop = ptop->pnext;
	}
	printf("\n");
}


void clear_stack(PSTACK pstack) {
	PNODE ptop = pstack->ptop;
	PNODE ptemp = NULL;
	if (is_empty_stack(pstack)) {
		return;
	}
	else {
		while (ptop != pstack->pbottom) {
			ptemp = ptop;
			ptop = ptop->pnext;
			free(ptemp);
		}
		pstack->ptop = pstack->pbottom;
	}
}


int main(void) {
	STACK S;
	int val;
	init_stack(&S);
	push_stack(&S, 1);
	push_stack(&S, 2);
	push_stack(&S, 3);
	push_stack(&S, 4);
	push_stack(&S, 5);
	push_stack(&S, 6);
	traverse_stack(&S);
	if (pop_stack(&S, &val)) {
		printf("%d 出栈成功\n", val);
	} 
	else {
		printf("出栈失败\n");
	}
	traverse_stack(&S);

	clear_stack(&S);
	if (pop_stack(&S, &val)) {
		printf("%d 出栈成功\n", val);
	}
	else {
		printf("出栈失败\n");
	}
	traverse_stack(&S);
	return 0;
}

队列

队列相关知识

  1. 定义：一种前进先出的存储结构
  2. 分类
    • 链式队列
    • 静态（数组）队列，通常都必须是循环队列
      • 静态队列为什么必须是循环队列？
        • 答：静态队列的长度是固定的，插入元素 front 增加与删除元素 rear 增加，只能增加会导致内存浪费，以及溢出。
      • 循环队列需要几个参数来确定，以及这些参数的含义？
        • 答：2 个参数，front， rear；初始化 front=rear=0；队列非空 front 表示队列第一个有效的元素，rear 表示队列最后一个有效的元素；队列为空 front=rear；
      • 入队
      • 出队
      • 判断队列是否为空
      • 判断队列是否为满 image.png 在循环队列中 rear 与 front 无大小关系，rear 可能比 front 也可能比 front 小
  3. 算法
    • 队列初始化
    • 入队
    • 出队
    • 队列的遍历
  4. 队列的应用
    • 所有和时间有关的操作

队列初始化

1
2
3
4
5
6
7
void init_queue(QUEUE* pq);

void init_queue(QUEUE* pq) {
	pq->pbase = (int*)malloc(sizeof(int) * len_queue);
	pq->front = 0;
	pq->rear = 0;
}

队列是否为空

1
2
3
4
5
bool is_empty_queue(QUEUE* pq);

bool is_empty_queue(QUEUE* pq) {
	return pq->rear == pq->front;
}

队列是否为满

1
2
3
4
5
bool is_full_queue(QUEUE* pq);

bool is_full_queue(QUEUE* pq) {
	return ((pq->rear + 1)% len_queue) == pq->front;
}

入队

1
2
3
4
5
6
7
8
9
10
11
12
bool en_queue(QUEUE* pq, int val);

bool en_queue(QUEUE* pq, int val) {
	if (!is_full_queue(pq)) {
		pq->pbase[pq->rear] = val;
		pq->rear = (pq->rear + 1) % len_queue;
		return true;
	}
	else {
		return false;
	}
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
bool out_queue(QUEUE* pq, int* val);

bool out_queue(QUEUE* pq, int* val){
	if (!is_empty_queue(pq)) {
		*val = pq->pbase[pq->front];
		pq->front = (pq->front + 1) % len_queue;
		return true;
	}
	else {
		return false;
	}
}

队列的遍历

1
2
3
4
5
6
7
8
void traverse_queue(QUEUE* pq) {
	int n = pq->front;
	while (n != pq->rear) {
		printf("%d ", pq->pbase[n]);
		n = (n + 1) % len_queue;
	}
	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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


typedef struct Queue {
	int* pbase;
	int front;
	int rear;
}QUEUE;

int len_queue = 6;

void init_queue(QUEUE* pq);
bool is_empty_queue(QUEUE* pq);
bool is_full_queue(QUEUE* pq);
bool en_queue(QUEUE* pq, int val);
bool out_queue(QUEUE* pq, int* val);
void traverse_queue(QUEUE* pq);


bool is_empty_queue(QUEUE* pq) {
	return pq->rear == pq->front;
}


void init_queue(QUEUE* pq) {
	pq->pbase = (int*)malloc(sizeof(int) * len_queue);
	pq->front = 0;
	pq->rear = 0;
}


bool is_full_queue(QUEUE* pq) {
	return ((pq->rear + 1)% len_queue) == pq->front;
}


bool en_queue(QUEUE* pq, int val) {
	if (!is_full_queue(pq)) {
		pq->pbase[pq->rear] = val;
		pq->rear = (pq->rear + 1) % len_queue;
		return true;
	}
	else {
		return false;
	}
}


bool out_queue(QUEUE* pq, int* val){
	if (!is_empty_queue(pq)) {
		*val = pq->pbase[pq->front];
		pq->front = (pq->front + 1) % len_queue;
		return true;
	}
	else {
		return false;
	}
}

void traverse_queue(QUEUE* pq) {
	int n = pq->front;
	while (n != pq->rear) {
		printf("%d ", pq->pbase[n]);
		n = (n + 1) % len_queue;
	}
	printf("\n");
}


//int main(void) {
//	QUEUE Q;
//	int val;
//	init_queue(&Q);
//	en_queue(&Q, 1);
//	en_queue(&Q, 2);
//	en_queue(&Q, 3);
//	en_queue(&Q, 4);
//	en_queue(&Q, 5);
//	en_queue(&Q, 6);
//	en_queue(&Q, 7);
//	traverse_queue(&Q);
//	if(out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	if (out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	if (out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	if (out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	if (out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	if (out_queue(&Q, &val)) printf("%d 出队\n", val);
//	else printf("出队失败\n");
//	traverse_queue(&Q);
//	return 0;
//}

递归

递归相关知识

  1. 定义：函数直接或者间接调用自己，递归的思想是把一个问题不断分割为子问题，当子问题规模很小不需要继续分割时，可以反过来求出原来问题的答案。
  2. 例子
    • 求阶乘
    • 汉诺塔
    • 走迷宫
  3. 递归必须满足的三个条件
    • 递归必须得有一个明确的终止条件
    • 该函数所处理的数据规模必须在递减
    • 这个转化必须是可解的
  4. 递归与循环的优缺点
    • 递归：易于理解，速度慢，所需存储空间大
    • 循环：不易理解，速度快，所需存储空间小

汉诺塔代码

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
#include <stdio.h>
#include <stdlib.h>  // 用于 malloc 和 free
#include <stdbool.h>


void hannota(int n, char a, char b, char c) {
	/*
	1. 把 a 柱子上的 n-1 个盘子 通过 c 柱子 移动到 b 柱子
	2. a 柱子上的盘子移动到 c 柱子
	3. 把 b 柱子上 n-1 个盘子 通过 a 柱子 移动到 c 柱子
	// 这里的 n 既是 剩余盘子的个数又是最下面一个盘子的编号
	递归的终止并不意味着整个递归过程结束，而是意味着当前的递归层级结束。首先要理解递归的执行过程：
	每次出现 --------end-------- 出现意味着当前递归的结束，但外层的递归还没结束，只有最外层的的递归 n == 1，整个程序才终止
	*/

	
	if (n == 1) {
		printf("-end-");
		printf("把编号为 %d 的盘子从 %c 柱子移动到 % c 柱子\n", n, a, c);
	}
	else {
		hannota(n - 1, a, c, b);
		printf("把编号为 %d 的盘子从 %c 柱子移动到 % c 柱子\n", n, a, c);
		hannota(n - 1, b, a, c);
	}
}

int main(void) {
	hannota(5, 'A', 'B', 'C');
	return 0;
}