04ds_09day

发表于 2023-02-16 更新于 2023-02-08
本文字数： 4.7k 阅读时长 ≈ 4 分钟

============================
2022-8-11
============================

Note

一.温故知新
    内核链表

链表的排序
1.交换链表中数据结点的数据
1
2
3
4
5
6
7
8
9
10
struct llist_node 
{
	int val;
	struct llist_node *next;
};

	p->val > p->next->val
	tmp = p->val;
	p->val = p->next->val;
	p->next->val = tmp;


2.交换链表的结点
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
struct llist_node *pop_sort(struct llist_node *l)
{
	struct llist_node *newl = NULL;//头结点
	struct llist_node *p = NULL;//标记交换之前的结点
	struct llist_node *q = NULL;//标记交换的结点
	struct llist_node *tail = NULL;//标记最值的位置

	newl = malloc(sizeof(struct llist_node));//创建头

	newl->next = l;//把新创建出的头结点拼到无头链表上

	while(newl->next->next != tail)
	{
		p = newl;//标记新的位置
		q = newl->next;//标记新的位置
		while(q->next != tail)
		{
			if(q->val > q->next->val)
			{
				p->next = q->next;
				q->next = q->next->next;
				p->next->next = q;
				q = p->next;
			}
			p = p->next;
			q = q->next;
		}
		tail = q;
	}
	l = newl->next;
	free(newl);//销毁头

	return l;//返回无头链表的新的位置
}

二叉树画图

遍历方法

先序(根左右)遍历
中序(左根右)遍历
后序(左右根)遍历

遍历练习

(1)
    先序遍历:ABDHJKECFGILM
    中序遍历:DJHKBEAFCLIMG

(2)
    中序遍历:DHFBACGE
    后序遍历:HFDBGECA

(3)
    中序遍历:DJGBHEAFIC
    后序遍历:JGDHEBIFCA

(4)
    先序遍历:ABCDEFGHIJ
    中序遍历:CBEDAGHFJI

(5)
    先序遍历:1 2 3 7 6 5 4 9 8
    中序遍历:1 2 3 4 5 6 7 8 9

使用二叉链表的方法实现二叉树

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
/*
	使用二叉链表的方法实现二叉树
	树中的结点 = [数据域] + [指向左子树的指针] +
					[指向右子树的指针]
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct stu//定义数据的结构体
{
	int id;
	char name[20];
	int math;
};

struct tree_node//定义树中结点的结构体
{
	struct stu data;//数据域
	struct tree_node *l;//指向左子树的指针
	struct tree_node *r;//指向右子树的指针
};

struct tree_node *tree = NULL;//指向树的根

int tree_insert(struct tree_node **root, struct stu data)
{
	if(*root == NULL)//判断是否为空树
	{
		*root = malloc(sizeof(struct tree_node));
		if(*root == NULL)
			return -1;
		(*root)->data = data;
		(*root)->l = NULL;
		(*root)->r = NULL;
		return 0;
	}
	if((*root)->data.id > data.id)
		tree_insert(&(*root)->l, data);
	else
		tree_insert(&(*root)->r, data);
}

void print(struct stu data)
{
	printf("%d	%s	%d\n", data.id, data.name, data.math);
}

void tree_display(struct tree_node *tree)
{
	if(tree == NULL)//判断是否是空树
		return;
	tree_display(tree->l);
	tree_display(tree->r);
	print(tree->data);
}

void tree_destroy(struct tree_node *tree)
{
	if(tree == NULL)//判断是否是空树
		return ;
	tree_destroy(tree->l);
	tree_destroy(tree->r);
	free(tree);
}

struct stu *tree_find(struct tree_node *root, int find_id)
{
	if(root == NULL)//判断是否是空树
		return NULL;
	if(root->data.id == find_id)
		return &root->data;
	else if(root->data.id > find_id)
		tree_find(root->l, find_id);
	else
		tree_find(root->r, find_id);
}

struct tree_node *find_max(struct tree_node *root)
{
	if(root == NULL)//判断是否是空树
		return NULL;
	if(root->r == NULL)
		return root;
	find_max(root->r);
}

struct tree_node *find_min(struct tree_node *root)
{
	if(root == NULL)//判断是否是空树
		return NULL;
	if(root->l == NULL)
		return root;
	find_min(root->l);
}

int tree_delete(struct tree_node **root, int find_id)
{
	struct tree_node **node = root;
	struct tree_node *cur = NULL;//标记要删除的结点

	while(*node != NULL && (*node)->data.id != find_id)
	{
		if((*node)->data.id > find_id)
			node = &(*node)->l;
		else
			node = &(*node)->r;
	}
	if(*node == NULL)//没有找到要删除的结点
		return -1;
	cur = *node;//标记删除的位置
	if(cur->l == NULL)//判断要删除的结点是否没有左子树
		*node = cur->r;
	else
	{
		*node = cur->l;//让左子树往上顶
		find_max(cur->l)->r = cur->r;
		//把右子树挂到左子树的最大结点的右边
	}
	free(cur);
	return 0;
}

int main(int argc, char *argv[])
{
	int buf[] = {1, 2, 3, 7, 6, 5, 4, 9, 8};
	struct stu data;//存储数据
	struct stu *datap = NULL;//指向找到的数据
	int i = 0;
	int ret = 0;
	int find_id = 15;

	for(i = 0; i < sizeof(buf) / sizeof(*buf); i++)
	{
		data.id = buf[i];
		sprintf(data.name, "stu%d", buf[i]);
		data.math = 100 - buf[i];
		tree_insert(&tree, data);//插入数据结点
	}

	tree_display(tree);//遍历树
	
	printf("------------------------\n");
#if 0
	datap = tree_find(tree, find_id);
	if(datap == NULL)
		printf("Not Find It!\n");
	else
	{
		printf("Find It!\n");
		print(*datap);
	}
#else
	ret = tree_delete(&tree, 7);
	if(ret == -1)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#endif
	printf("------------------------\n");

	tree_display(tree);//遍历树
	
	tree_destroy(tree);//销毁树

	return 0;
}

04ds_06day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 12k 阅读时长 ≈ 10 分钟

==============================
2022-8-8
==============================

note

一.温故知新
线性表
        是n个具有相同类型的数据元素的集合
        线性表是一种使用比较广泛的数据结构
        线性表在逻辑上是线性的结构,也就相当于是一条直线
        但是在物理结构上并不一定是连续的
        线性表在物理存储时,通常以数组或者链表的形式存储
    顺序表
        是用一段连续的存储空间依次存储数据元素的线性结构
        一般情况下使用的就是数组,在数组中做增删改查的操作
        定长的顺序表 : 使用定长的数组
            适用于确定成员个数的场景
        不定长的顺序表 : 使用动态开辟的数组
            可以根据需求灵活开辟空间
    链表
        在逻辑结构上是线性的存储,
        但是在物理结构体并不是连续的存储结构
        链表中数据的顺序根据链表中结点的指针的指向来确定
顺序表的优缺点
    优点 : 使用的是连续的存储空间
            可以使用下标快速定位到某个成员
    缺点 : 定长的顺序表定义之后不能再扩容
            插入新的成员以及删除成员,需要挪动后续所有成员
链表的优缺点
    优点 : 插入新的成员和删除成员方便,不会造成空间的浪费
    缺点 : 访问链表的成员不方便

总结 : 顺序表和链表是相辅相成的,需要在适合的场景下使用
如果写项目工程使用有头双向循环链表合适
如果在笔试面试中碰到链表的题目,一般来说考无头单向链表
===================================
早测
1.移出链表元素
给你一个无头单向不循环链表的首结点l和一个整数 val 
请你删除链表中所有等于 val 的节点，并返回新的首结点 。
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
struct llist_node
{
	int val;
	struct llist_node *next;
};

struct llist_node* remove(struct llist_node* l, int val)
{
	struct llist_node *cur = l;//指向要删除的结点
	struct llist_node *back = NULL;
	//指向要删除的结点的前一个位置

	while(cur != NULL)//判断是否遍历完所有的结点
	{
		if(cur->val == val)//判断是否是要删除的数据
		{
			if(back == NULL)//判断删除的是否是第一个结点
			{
				l = l->next;//改变l的位置
				free(cur);//释放第一个结点
				cur = l;//改变cur的位置
			}
			else
			{
				back->next = cur->next;
				free(cur);
				cur = back->next;
			}
		}
		else
		{
			back = cur;
			cur = cur->next;
		}
	}
	return l; 
}

===================================

线性表
    两种特殊的线性存储结构(受限制的存储形式)
    栈式存储结构
        一定要和内存中的栈区区分开
        stack
        特点 : 先进后出
        可以把栈式存储结构抽象成有底的容器
        把数据存储到栈式存储结构中	入栈|进栈|压栈|push
        从栈式存储结构中取出数据	出栈|退栈|弹栈|pop
        存入数据或者取出数据的一端	栈顶|ind
        另外一端					栈底
    由于栈式存储结构属于线性表中特殊的存储形式
    所以既可以用顺序表来实现,也可以用链表来实现
        入栈时需要判断,栈是否满了
        出栈时需要判断,栈是否空了

    队列式存储结构

=================================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把栈式存储结构(三种方式)再重新实现一遍
3.把早测的功能函数再重新实现一遍
=================================
1
2
3
4
5
6
l
|
V
11->22->11->33->11->44->11->NULL

11

数组栈

main.c

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

int main(void)
{
	int data[] = {11,22,33,44,55,66,77,88,99};//数据
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值
	int save = 0;//用来保存出栈的数据

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(data[i]);//入栈	
		if(ret == -1)//判断是否栈满
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display();//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(&save);//出栈
	if(ret == -1)//判断栈是否为空
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	stack_display();//遍历栈

	stack_push(999);
	stack_display();//遍历栈

	return 0;
}

stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef __STACK_H
#define __STACK_H

#define STACKSIZE 6

int stack_arr[STACKSIZE];//栈
int stack_ind;//栈顶元素

int stack_push(int data);

int stack_pop(int *save);

void stack_display(void);

#endif

stack.c

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

int isfull(void)
{
	return !(stack_ind - STACKSIZE);
}

int isempty(void)
{
	return !(stack_ind);
}

int stack_push(int data)
{
	if(isfull())//判断是否栈满了
		return -1;
	stack_arr[stack_ind++] = data;//入栈
}

int stack_pop(int *save)//出栈
{
	if(isempty())//判断栈是否为空
		return -1;
	*save = stack_arr[--stack_ind];
}

void stack_display(void)
{
	int i = stack_ind;//循环变量

	while(i--)
	{
		printf("	%d\n", stack_arr[i]);
	}
	printf("===================\n");
}

makefile

1
2
3
4
stack : main.o stack.o
	gcc -o $@ $^
clean :
	rm -rf *.o stack

指针栈

main.c

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

int main(void)
{
	STACK *s = NULL;//s指针指向栈
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用于接收返回值的变量
	int save = 0;//用于接收出栈的数据

	s = stack_create();//开辟栈式存储结构的空间
	if(s == NULL)//判断是否开辟空间失败
		return -1;//开辟失败,结束程序,并且返回-1

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(s, data[i]);//入栈
		if(ret == -1)//判断栈是否满了
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display(s);//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(s, &save);
	if(ret == -1)
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	
	stack_display(s);//遍历栈
	
	stack_push(s, 999);
	
	stack_display(s);//遍历栈

	stack_destroy(s);//销毁栈

	return 0;
}

stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef __STACK_H
#define __STACK_H

#define STACKSIZE 6

typedef struct node
{
	int stack_buf[STACKSIZE];
	int stack_ind;
}STACK;

STACK *stack_create();//创建栈

int stack_push(STACK *s, int data);//入栈

int stack_pop(STACK *s, int *save);//出栈

void stack_display(STACK *s);//遍历栈

void stack_destroy(STACK *s);//销毁栈

#endif

stack.c

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

STACK *stack_create()//创建栈
{
	STACK *s = NULL;//s指针指向开辟的空间

	s = malloc(sizeof(STACK));//开辟空间
	if(s == NULL)//判断是否开辟失败
		return NULL;
	s->stack_ind = 0;//把栈顶元素先清零

	return s;
}

int isfull(STACK *s)
{
	return !(s->stack_ind - STACKSIZE);
}

int isempty(STACK *s)
{
	return !(s->stack_ind);
}

int stack_push(STACK *s, int data)//入栈
{
	if(isfull(s))//判断栈是否满了
		return -1;
	s->stack_buf[s->stack_ind++] = data;
}

int stack_pop(STACK *s, int *save)//出栈
{
	if(isempty(s))
		return -1;
	*save = s->stack_buf[--s->stack_ind];
}

void stack_display(STACK *s)//遍历栈
{
	int i = s->stack_ind;

	while(i--)
		printf("	%d\n", s->stack_buf[i]);
	printf("==================\n");
}

void stack_destroy(STACK *s)//销毁栈
{
	free(s);
}

makefile

1
2
3
4
stack : main.o stack.o
	gcc -o $@ $^
clean :
	rm -rf *.o stack

链表栈

main.c

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

int main(void)
{
	STACK *s = NULL;//s指针指向栈
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用于接收返回值的变量
	int save = 0;//用于接收出栈的数据

	s = stack_create();//开辟栈式存储结构的空间
	if(s == NULL)//判断是否开辟空间失败
		return -1;//开辟失败,结束程序,并且返回-1

	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = stack_push(s, data[i]);//入栈
		if(ret == -1)//判断栈是否满了
		{
			printf("Stack Is Full!\n");
			break;
		}
	}

	stack_display(s);//遍历栈

	printf("*******************\n");
	
	ret = stack_pop(s, &save);
	if(ret == -1)
		printf("Stack Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("*******************\n");
	
	stack_display(s);//遍历栈
	
	stack_push(s, 999);
	
	stack_display(s);//遍历栈

	stack_destroy(s);//销毁栈

	return 0;
}

stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef __STACK_H
#define __STACK_H

#include "llist.h"

typedef LLIST STACK;

STACK *stack_create();//创建栈

int stack_push(STACK *s, int data);//入栈

int stack_pop(STACK *s, int *save);//出栈

void stack_display(STACK *s);//遍历栈

void stack_destroy(STACK *s);//销毁栈

#endif

stack.c

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

STACK *stack_create()//创建栈
{
	return llist_create();
}

int isempty(STACK *s)
{
	return llist_empty(s);
}

int stack_push(STACK *s, int data)//入栈
{
	return llist_insert(s, &data, HEADINSERT);
}

int stack_pop(STACK *s, int *save)//出栈
{
	if(isempty(s))
		return -1;
	_fetch(s, save);
}

void stack_display(STACK *s)//遍历栈
{
	llist_display(s);
}

void stack_destroy(STACK *s)//销毁栈
{
	llist_destroy(s);
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0//头插法
#define TAILINSERT 1//尾插法
#define NAMESIZE 20//字符数组的成员个数

typedef struct llist_node//链表中结点的结构体
{
	int id;//数据域
	//char name[NAMESIZE];//数据域
	//int math;//数据域
	struct llist_node *prev;//prev指针指向前一个结点
	struct llist_node *next;//next指针指向后一个结点
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//取出结点

int llist_empty(LLIST *);//判断链表为空链表

int _fetch(LLIST *, void *);//取出第一个数据结点

#endif

llist.c

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

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟空间失败,结束函数,返回NULL
	
	handler->prev = handler->next = handler;
	//让头结点的前后指针都指向自己

	return handler;//返回指向头结点的指针
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//代替handler指针进行移动
	LLIST *newnode = NULL;//指向新创建的数据结点

	newnode = malloc(sizeof(LLIST));//为数据结点开辟空间
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟空间失败,结束函数,并且返回-1
	
	memcpy(newnode, data, sizeof(LLIST));//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break; 
		default : free(newnode); return -2;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur = handler->next;cur!=handler;cur=cur->next)
		printf("	%d\n",cur->id);
	printf("==================\n");
}

void llist_destroy(LLIST *handler)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=handler->next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);//释放数据结点
	}
	free(cur);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=cur->next)
	{
		if(cur->id==*(int *)find_data)
		{
			return cur;
		}
	}
	return NULL;
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;
	
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);

	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;

	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);

	return 0;
}

int llist_empty(LLIST *handler)
{
	return handler == handler->next;
}

int _fetch(LLIST *handler, void *save)//取出第一个数据结点
{
	LLIST *cur = handler->next;

	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur, sizeof(cur->id));
	free(cur);
	return 0;
}

makefile

1
2
3
4
stack : main.o llist.o stack.o
	gcc -o $@ $^
clean :
	rm -rf *.o stack

汉诺塔

main.c

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

#define HANOISIZE 7

struct
{
	int hanoi[HANOISIZE];
	int ind;
}hanoi_arr[3] = {{{7,6,5,4,3,2,1}, 7}, {}, {}};

void draw(void)
{
	int i = 0, j = 0;

	system("clear");
	for(i = 0; i < 3; i++)//铁柱的遍历
	{
		for(j = 0; j < hanoi_arr[i].ind; j++)
			printf("%d", hanoi_arr[i].hanoi[j]);
		for(; j < 10; j++)
			printf("-");
		printf("\n");
	}
	getchar();
}

void move(int src, int dest)
{
	hanoi_arr[src].ind--;
	hanoi_arr[dest].hanoi[hanoi_arr[dest].ind] = hanoi_arr[src].hanoi[hanoi_arr[src].ind];
	hanoi_arr[dest].ind++;
	draw();
}

void play(int src, int dest, int tmp, int num)
{
	if(num == 1)
	{
		move(src, dest);
		return ;
	}
	play(src, tmp, dest, num - 1);
	move(src, dest);
	play(tmp, dest, src, num - 1);
}

int main(int argc, char *argv[])
{
	draw();
	
	play(0, 1, 2, HANOISIZE);

	return 0;
}

04ds_07day

发表于 2023-02-16 更新于 2023-02-03
本文字数： 9.7k 阅读时长 ≈ 9 分钟

============================
2022-8-9
============================

note

一.温故知新
    栈式的存储结构(受限制的存储结构)
    特点 : 先进后出
    线性表中的特殊存储形式
    通过顺序表来实现栈式存储结构
    通过链表来实现栈式存储结构

#define STACKSIZE 6

struct node
{
    int stack_buf[STACKSIZE];
    int stack_ind;
};

    队列式的存储结构(受限制的存储结构)
    特点 : 先进先出
    线性表中的特殊存储形式
    通过顺序表来实现队列式的存储结构
    通过链表来实现队列式的存储结构

#define QUEUESIZE 6

struct node
{
    int queue[QUEUESIZE];
    int front;
    int rear;
};

早测
快慢指针
struct llist_node 
{
    int val;
    struct llist_node *next;
};
1.反转链表
给你一个无头单向不循环链表的首结点l ，请你反转链表，
并返回反转后的链表首结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct llist_node *func(struct llist_node *l)
{
	struct llist_node *cur = l;//指向当前要反转的结点
	struct llist_node *p = NULL;//指向原链表cur之后的位置
	struct llist_node *next = NULL;//指向反转链表之后cur之后的位置

	while(cur != NULL)//遍历所有结点
	{
		p = cur->next;
		cur->next = next;
		next = cur;
		cur = p;
	}
	return next;
}

2.链表的中间结点
给定一个头结点为handler的单向不循环链表,返回链表的中间结点
如果有两个中间结点，则返回第二个中间结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
struct llist_node *fund(struct llist_node *handler)
{
	struct llist_node *s = handler;//慢指针
	struct llist_node *f = handler;//快指针
	
	while(f != NULL && f->next != NULL)//判断只有一个结点
	{
		s = s->next;
		f = f->next->next;
	}

	return s;
}

===================================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把队列式的存储结构的实现方法再写一遍
3.写个链表,把早测的功能函数写程序实现
===================================

库的制作

在Linux环境中,以.a结尾的库文件是静态库文件
在Linux环境中,以.so结尾的库文件是动态库文件

静态库 : 是在程序编译时会被连接到目标代码中,当编译完之后
        程序运行时将不再需要该静态库,
        所以可执行程序的体积比较大
动态库 : 是在程序编译时仅仅简单的引用,当编译完之后
        程序运行时需要该动态库,
        所以可执行程序的体积比较小
查看可执行代码的依赖的共享库：ldd命令 – 打印程序依赖的共享库
注意 : 如果静态库和动态库同时存在的情况下优先使用动态库

静态库的制作方法

1.把.c文件编译成.o目标文件
    gcc -c -o xxxx.o xxxx.c
2.把.o目标文件编译成.a静态库文件
    ar -cr libxxxx.a xxxx.o
3.生成索引
    ranlib libxxxx.a
4.把静态库放到/lib目录中
    mv libxxxx.a /lib
5.把头文件放到/usr/include目录中
    mv xxxx.h /usr/include
6.编译主程序
    gcc main.c -lxxxx
如果没有把libxxxx.a和xxxx.h文件放到指定目录下
    gcc main.c -I[头文件的路径] -L[库文件的路径] -lxxxx
注意 : [头文件的路径] 和 [库文件的路径]只写路径不写文件名
    -I	指定头文件的路径
    -L	指定库文件的路径
    -l	链接库的名字

动态库的制作

1.把.c文件编译成.o目标文件
    gcc -fPIC -c -o xxx.o xxx.c
    -fPIC	使用gcc编译必须与位置无关
2.把.o目标文件编译成动态库文件
    gcc -shared -o libxxx.so xxx.o
3.把动态库文件移动到/lib目录中
    mv libxxx.so /lib
4.把头文件移动到/usr/include目录中
    mv xxx.h /usr/include
5.编译文件
    gcc main.c -lxxx

-------------------------------------
long arr[5] = {11,22,33,44,55};
与位置有关
    比如 : arr 0x1000
    arr[0]		*(long *)(0x1000)
    arr[1]		*(long *)(0x1008)
与位置无关
    比如 : arr 0x2000
    arr[0]		*(long *)(0x2000)
    arr[1]		*((long *)(0x2000) + 1);
-------------------------------------

quueu_arr队列

main.c

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

int main(void)
{
	QUEUE *q = NULL;//q指针指向队列
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值的变量
	int save = 0;//用来保存出队的数据

	q = queue_create();//创建队列
	if(q == NULL)
		return -1;
	
	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = queue_en(q, data[i]);//入队
		if(ret == -1)//判断队列是否满了
		{
			printf("Queue Is Full!\n");
			break;
		}
	}

	queue_display(q);//遍历队列
	
	printf("***********************\n");
	
	ret = queue_de(q, &save);
	if(ret == -1)
		printf("Queue Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("***********************\n");
	
	queue_display(q);//遍历队列
	
	queue_en(q, 999);

	queue_display(q);//遍历队列

	queue_destroy(q);//释放队列

	return 0;
}

queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef __QUEUE_H
#define __QUEUE_H

#define QUEUESIZE 6

typedef struct node
{
	int queue[QUEUESIZE];//队列
	int front;//队头
	int rear;//队尾
}QUEUE;

QUEUE *queue_create();//创建队列

int queue_en(QUEUE *q, int data);//入队

int queue_de(QUEUE *q, int *save);//出队

void queue_display(QUEUE *q);//遍历队列

void queue_destroy(QUEUE *q);//销毁队列

#endif

queue.c

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

QUEUE *queue_create()//创建队列
{
	QUEUE *q = NULL;//将来指向队列

	q = malloc(sizeof(QUEUE));//为队列开辟空间
	if(q == NULL)
		return NULL;
	q->front = q->rear = 0;//把队头和队尾都标记到0的位置
	return q;
}

int queue_en(QUEUE *q, int data)//入队
{
	if((q->rear + 1) % QUEUESIZE == q->front)//判断队满
		return -1;
	q->rear = (q->rear + 1) % QUEUESIZE;//移动队尾的标志
	q->queue[q->rear] = data;//入队数据
}

int queue_de(QUEUE *q, int *save)//出队
{
	if(q->front == q->rear)
		return -1;
	q->front = (q->front + 1) % QUEUESIZE;
	*save = q->queue[q->front];
}

void queue_display(QUEUE *q)//遍历队列
{
	int i = (q->front + 1) % QUEUESIZE;

	if(q->front == q->rear)//判断是否是空队列
		return ;
	printf("------------------------\n");
	while(i != q->rear)
	{
		printf("%d\t", q->queue[i]);
		i = (i + 1) % QUEUESIZE;
	}
	printf("%d\n", q->queue[i]);
	printf("------------------------\n");
}

void queue_destroy(QUEUE *q)//销毁队列
{
	free(q);
}

makefile

1
2
3
4
queue : main.o queue.o
	gcc -o $@ $^
clean :
	rm -rf *.o queue

queue_llist_队列

main.c

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

int main(void)
{
	QUEUE *q = NULL;//q指针指向队列
	int data[] = {11,22,33,44,55,66,77,88,99};
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值的变量
	int save = 0;//用来保存出队的数据

	q = queue_create();//创建队列
	if(q == NULL)
		return -1;
	
	for(i = 0; i < sizeof(data) / sizeof(*data); i++)
	{
		ret = queue_en(q, data[i]);//入队
		if(ret == -1)//判断队列是否满了
		{
			printf("Queue Is Full!\n");
			break;
		}
	}

	queue_display(q);//遍历队列
	
	printf("***********************\n");
	
	ret = queue_de(q, &save);
	if(ret == -1)
		printf("Queue Is Empty!\n");
	else
		printf("Save = %d\n", save);
	
	printf("***********************\n");
	
	queue_display(q);//遍历队列
	
	queue_en(q, 999);

	queue_display(q);//遍历队列

	queue_destroy(q);//释放队列

	return 0;
}

queue.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef __QUEUE_H
#define __QUEUE_H

#include "llist.h"

typedef LLIST QUEUE;

QUEUE *queue_create();//创建队列

int queue_en(QUEUE *q, int data);//入队

int queue_de(QUEUE *q, int *save);//出队

void queue_display(QUEUE *q);//遍历队列

void queue_destroy(QUEUE *q);//销毁队列

#endif

queue.c

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>
#include "queue.h"

QUEUE *queue_create()//创建队列
{
	return llist_create();
}

int queue_en(QUEUE *q, int data)//入队
{
	return llist_insert(q, &data, TAILINSERT);
}

int queue_de(QUEUE *q, int *save)//出队
{
	if(llist_empty(q))
		return -1;
	_fetch(q, save);
}

void queue_display(QUEUE *q)//遍历队列
{
	llist_display(q);
}

void queue_destroy(QUEUE *q)//销毁队列
{
	llist_destroy(q);
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0//头插法
#define TAILINSERT 1//尾插法
#define NAMESIZE 20//字符数组的成员个数

typedef struct llist_node//链表中结点的结构体
{
	int id;//数据域
	//char name[NAMESIZE];//数据域
	//int math;//数据域
	struct llist_node *prev;//prev指针指向前一个结点
	struct llist_node *next;//next指针指向后一个结点
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//取出结点

int llist_empty(LLIST *);//判断链表为空链表

int _fetch(LLIST *, void *);//取出第一个数据结点

#endif

llist.c

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 <string.h>
#include "llist.h"

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟空间失败,结束函数,返回NULL
	
	handler->prev = handler->next = handler;
	//让头结点的前后指针都指向自己

	return handler;//返回指向头结点的指针
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//代替handler指针进行移动
	LLIST *newnode = NULL;//指向新创建的数据结点

	newnode = malloc(sizeof(LLIST));//为数据结点开辟空间
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟空间失败,结束函数,并且返回-1
	
	memcpy(newnode, data, sizeof(LLIST));//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break; 
		default : free(newnode); return -2;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	printf("==================\n");
	for(cur = handler->next;cur!=handler;cur=cur->next)
		printf("%d\t", cur->id);
	printf("\n==================\n");
}

void llist_destroy(LLIST *handler)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=handler->next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);//释放数据结点
	}
	free(cur);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=cur->next)
	{
		if(cur->id==*(int *)find_data)
		{
			return cur;
		}
	}
	return NULL;
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;
	
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);

	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;

	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);

	return 0;
}

int llist_empty(LLIST *handler)
{
	return handler == handler->next;
}

int _fetch(LLIST *handler, void *save)//取出第一个数据结点
{
	LLIST *cur = handler->next;

	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur, sizeof(cur->id));
	free(cur);
	return 0;
}

makefile

1
2
3
4
queue : main.o llist.o queue.o
	gcc -o $@ $^
clean :
	rm -rf *.o queue

04ds_04day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 7.2k 阅读时长 ≈ 7 分钟

============================
2022-8-4
============================

note

1.写出有头单向循环链表的插入功能(头插 尾插)
2.实现冒泡法排序
    void sort(int *arr, int size);
有头单向循环链表的功能

无头单向不循环链表

约瑟夫环(约瑟夫杀人游戏)

--------------------------------------------
作业 :
1.把今天讲过的内容完完整整的复习一遍
2.把之前写过的5种链表都重新写一遍
    1)有头单向不循环链表
    2)有头单向循环链表
    3)无头单向不循环链表
    4)无头单向循环链表
    5)有头双向循环链表
--------------------------------------------

约瑟夫环(约瑟夫杀人游戏)

main.c

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

int main(void)
{
	JOSEPH *j = NULL;//j指针指向第一个有效结点
	int player_num = 0;//保存玩家个数
	int kill_num = 0;//数的数字
	int alive = 0;//保存存活下来的人的ID

	printf("Please Insert Player Number : ");
	scanf("%d", &player_num);
	j = joseph_insert(player_num);//插入数据结点
	if(j == NULL)
		return -1;
	printf("===========================\n");
	joseph_display(j);//遍历链表
	printf("===========================\n");
	printf("Please Insert Kill Number : ");
	scanf("%d", &kill_num);
	printf("***************************\n");
	alive = joseph_play(j, player_num, kill_num);
	printf("\n***************************\n");
	printf("alive = %d\n", alive);

	return 0;
}

joseph.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef __JOSEPH_H
#define __JOSEPH_H

typedef struct llist_node
{
	int id;//编号
	struct llist_node *next;
}JOSEPH;

JOSEPH *joseph_insert(int );

JOSEPH *joseph_display(JOSEPH *);

int joseph_play(JOSEPH *, int , int);

#endif

joseph.c

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

JOSEPH *joseph_insert(int player_num)
{
	JOSEPH *j = NULL;//j指针指向第一个数据结点
	JOSEPH *p = NULL;//p指针代替j指针进行移动
	JOSEPH *newnode = NULL;//指针指向新创建的结点
	int i = 1;//循环变量
	
	j = malloc(sizeof(JOSEPH));
	if(j == NULL)
		return NULL;
	j->id = i;
	j->next = j;
	p = j;

	for(i = 2; i <= player_num; i++)
	{
		newnode = malloc(sizeof(JOSEPH));
		if(newnode == NULL)
			return j;
		newnode->id = i;
		newnode->next = p->next;
		p->next = newnode;
		p = p->next;
	}

	return j;
}

JOSEPH *joseph_display(JOSEPH *j)
{
	JOSEPH *cur = NULL;

	for(cur = j; cur->next != j; cur = cur->next)
		printf("%d ", cur->id);
	printf("%d\n", cur->id);
}

int joseph_play(JOSEPH *j, int player_num, int kill_num)
{
	JOSEPH *back = j;
	JOSEPH *cur = NULL;
	int p_n = player_num;
	int k_n = kill_num;
	int alive = 0;

	while(back->next != j)//为了找第一个结点的前一个位置
		back = back->next;
	
	while(--p_n)
	{
		for(k_n = kill_num - 1; k_n > 0; k_n--)
			back = back->next;
		cur = back->next;
		back->next = cur->next;
		printf("%d ", cur->id);
		free(cur);
	}
	alive = back->id;
	free(back);

	return alive;
}

makefile

joseph : main.o joseph.o
    gcc -o $@ $^
clean :
    rm -rf *.o joseph

有头双向循环链表

/*
    有头双向循环链表
    1.创建头结点					llist_create();
    2.插入数据结点(头插法 尾插法)	llist_insert();
    3.遍历链表						llist_display();
    4.销毁链表						llist_destroy();
*/

main.c

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

int main(void)
{
	LLIST *handler = NULL;//指针指向链表的头结点
	LLIST *find = NULL;//指针指向要查找的结点
	LLIST data;//存储用户的数据
	LLIST save;//保存取出的数据
	int i = 0;//循环变量
	int ret = 0;//接收函数的返回值
	int find_id = 100;//要查找的ID号
	char *find_name = "stu4";//要查找的名字

	handler = llist_create();//创建头结点
	if(handler == NULL)//判断头结点是否创建失败
		return -1;//创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//获取数据
		sprintf(data.name, "stu%d", i);//获取数据
		data.math = 100 - i;//获取数据
		data.prev = data.next = NULL;//prev和next指向NULL
		llist_insert(handler, &data, TAILINSERT);
		//插入数据结点
	}

	llist_display(handler);//遍历链表
	
	printf("====================\n");
/*
	find = llist_find(handler, "stu9");//查找结点
	if(find == NULL)//判断是否没有找到
		printf("Not Find It!\n");
	else
		printf("Find It!	%d	%s	%d\n",find->id, find->name,find->math);
*/
#if 0
	ret = llist_delete(handler, &find_id);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler, find_name, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
		printf("Fetch It!	%d	%s	%d\n",save.id, save.name, save.math);
#endif
	printf("====================\n");

	llist_display(handler);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0//头插法
#define TAILINSERT 1//尾插法
#define NAMESIZE 20//字符数组的成员个数

typedef struct llist_node//链表中结点的结构体
{
	int id;//数据域
	char name[NAMESIZE];//数据域
	int math;//数据域
	struct llist_node *prev;//prev指针指向前一个结点
	struct llist_node *next;//next指针指向后一个结点
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//取出结点

#endif

llist.c

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

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟空间失败,结束函数,返回NULL
	
	handler->prev = handler->next = handler;
	//让头结点的前后指针都指向自己

	return handler;//返回指向头结点的指针
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//代替handler指针进行移动
	LLIST *newnode = NULL;//指向新创建的数据结点

	newnode = malloc(sizeof(LLIST));//为数据结点开辟空间
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟空间失败,结束函数,并且返回-1
	
	memcpy(newnode, data, sizeof(LLIST));//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break; 
		default : free(newnode); return -2;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur = handler->next;cur!=handler;cur=cur->next)
		printf("%d	%s	%d\n",cur->id,cur->name,cur->math);
}

void llist_destroy(LLIST *handler)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=handler->next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);//释放数据结点
	}
	free(cur);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	for(cur=handler->next;cur!=handler;cur=cur->next)
	{
		if(cur->id==*(int *)find_data || 
			!(strcmp(cur->name, find_data)))
		{
			return cur;
		}
	}
	return NULL;
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;
	
	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	free(cur);

	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;

	cur->prev->next = cur->next;
	cur->next->prev = cur->prev;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist

04ds_05day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 18k 阅读时长 ≈ 17 分钟

==============================
2022-8-5
==============================

note

一.早测
    完成有头双向循环链表的功能
    1.创建头结点
    2.插入数据结点
    3.遍历链表
    4.销毁链表
    5.查找结点
    6.删除结点
    7.拿出结点
只写声明和实现,不用写调用(llist.c 和 llist.h)

=================================
作业
1.把这一周讲过的内容都完完整整的复习一遍
2.把三个版本的通用性强的链表重新实现一遍
3.在纸上写链表的代码
=================================

通用性强的链表

结点图

main.c

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
#include <stdio.h>
#include <string.h>
#include "llist.h"

#define NAMESIZE 20//字符数组的成员个数

struct stu//客户自己创建的数据结构体
{
	int id;
	char name[NAMESIZE];
	int math;
	int age;
	int tel;
};

void print(const void *data)
{
	const struct stu *p = data;
	printf("%d	%s	%d	%d	%d\n",p->id,p->name,p->math,p->age, p->tel);
}

int id_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->id - *k);
}

int name_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const char *k = key;

	return !(strcmp(p->name, k));
}

int tel_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->tel - *k);
}

int main(void)
{
	LLIST *handler = NULL;//handler指针指向头结点
	struct stu data;//存放客户自己的数据
	struct stu save;//存储拿出的数据
	struct stu *find = NULL;//指向找到的数据
	int i = 0;//循环变量
	int ret = 0;//接收返回值
	int find_id = 100;
	int find_tel = 10002;
	char *find_name = "stu4";

	handler = llist_create(sizeof(struct stu));
	//创建头结点
	if(handler == NULL)//判断头结点是否创建失败
		return -1;//创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//存储数据
		sprintf(data.name, "stu%d", i);//存储数据
		data.math = 100 - i;//存储数据
		data.age = 20 + i;//存储数据
		data.tel = 10000 + i;//存储数据
		llist_insert(handler,&data,TAILINSERT);//插入数据
	}

	llist_display(handler, print);//遍历链表

	printf("============================\n");
/*	
	find = llist_find(handler, &find_tel, tel_cmp);//查找
	if(find == NULL)//判断是否没有找到
		printf("Not Find It!\n");
	else
	{
		printf("Find It!\n");
		print(find);
	}
*/
#if 0
	ret = llist_delete(handler, &find_tel, tel_cmp);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler, &find_tel, tel_cmp, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
	{
		printf("Fetch It!\n");
		print(&save);
	}
#endif

	printf("============================\n");

	llist_display(handler, print);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0
#define TAILINSERT 1

typedef void (*llist_op)(const void *);//定义函数指针类型
typedef int (*llist_cmp)(const void *,const void *);

struct llist_node//数据结点的结构体
{
	void *data;//data指针指向数据
	struct llist_node *prev;//prev指针指向前驱
	struct llist_node *next;//next指针指向后继
};

typedef struct llist_head//头结点的结构体
{
	int size;//保存客户创建的结构体的大小
	struct llist_node head;//
}LLIST;

LLIST *llist_create(int );//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *, llist_op);//遍历链表

void llist_destroy(LLIST *);//销毁链表

void *llist_find(LLIST *, const void *, llist_cmp);//查找

int llist_delete(LLIST *, const void *, llist_cmp);//删除

int llist_fetch(LLIST *, const void *, llist_cmp, void *);

#endif

llist.c

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

LLIST *llist_create(int size)
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟失败,结束函数,并且返回NULL
	handler->size = size;//把客户结构体大小存储起来
	handler->head.prev = &handler->head;//前驱指向自己
	handler->head.next = &handler->head;//后继指向自己
	return handler;//把指向头结点的指针返回
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	struct llist_node *p = &handler->head;//保存头结点地址
	struct llist_node *newnode = NULL;//保存新建的数据结点

	newnode = malloc(sizeof(struct llist_node));//数据结点
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟失败,结束函数,并且返回-1
	
	newnode->data=malloc(handler->size);//开辟数据空间
	if(newnode->data == NULL)//判断数据空间是否开辟失败
	{
		free(newnode);//释放数据结点的空间
		return -2;//数据空间开辟失败,结束函数,并且返回-2
	}
	memcpy(newnode->data, data, handler->size);//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break;
		default : free(newnode->data); free(newnode);
					return -3;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler, llist_op op)
{
	struct llist_node *cur = NULL;
	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *handler)
{
	struct llist_node *cur = NULL;
	
	for(cur=handler->head.next;cur!=&handler->head;cur=handler->head.next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur->data);
		free(cur);
	}
	free(handler);
}

struct llist_node *_find(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		if(cmp(cur->data, find_data))
			return cur;
	return NULL;
}

void *llist_find(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return NULL;
	return cur->data;
}

int llist_delete(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return -1;
	///////cur指针已经指向要删除的结点
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	free(cur->data);
	free(cur);
	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, llist_cmp cmp, void *save)
{
	struct llist_node *cur = NULL;

	cur = _find(handler,find_data,cmp);
	if(cur == NULL)
		return -1;
	
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur->data, handler->size);
	free(cur->data);
	free(cur);

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist

可变长的通用性强的链表

=================================

可变长的结构体

        需要把可变长的因子放到结构体定义的最后
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
#include <stdio.h>
#include <stdlib.h>

struct aaa
{
	void *data;
	struct aaa *prev;
	struct aaa *next;
};

struct bbb
{
	struct bbb *prev;
	struct bbb *next;
	char data[0];
};

int main(int argc, char *argv[])
{
	struct bbb *newnode = NULL;

	printf("sizeof(struct aaa) = %ld\n", sizeof(struct aaa));
	printf("sizeof(struct bbb) = %ld\n", sizeof(struct bbb));

	//newnode = malloc(sizeof(struct bbb));//开辟16byte空间
	newnode = malloc(sizeof(struct bbb) + 40);//开辟56byte空间

	return 0;
}


=================================

main.c

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
#include <stdio.h>
#include <string.h>
#include "llist.h"

#define NAMESIZE 20//字符数组的成员个数

struct stu//客户自己创建的数据结构体
{
	int id;
	char name[NAMESIZE];
	int math;
	int age;
	int tel;
};

void print(const void *data)
{
	const struct stu *p = data;
	printf("%d	%s	%d	%d	%d\n",p->id,p->name,p->math,p->age, p->tel);
}

int id_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->id - *k);
}

int name_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const char *k = key;

	return !(strcmp(p->name, k));
}

int tel_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->tel - *k);
}

int main(void)
{
	LLIST *handler = NULL;//handler指针指向头结点
	struct stu data;//存放客户自己的数据
	struct stu save;//存储拿出的数据
	struct stu *find = NULL;//指向找到的数据
	int i = 0;//循环变量
	int ret = 0;//接收返回值
	int find_id = 100;
	int find_tel = 10002;
	char *find_name = "stu4";

	handler = llist_create(sizeof(struct stu));
	//创建头结点
	if(handler == NULL)//判断头结点是否创建失败
		return -1;//创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//存储数据
		sprintf(data.name, "stu%d", i);//存储数据
		data.math = 100 - i;//存储数据
		data.age = 20 + i;//存储数据
		data.tel = 10000 + i;//存储数据
		llist_insert(handler,&data,TAILINSERT);//插入数据
	}

	llist_display(handler, print);//遍历链表

	printf("============================\n");
/*	
	find = llist_find(handler, &find_tel, tel_cmp);//查找
	if(find == NULL)//判断是否没有找到
		printf("Not Find It!\n");
	else
	{
		printf("Find It!\n");
		print(find);
	}
*/
#if 0
	ret = llist_delete(handler, &find_tel, tel_cmp);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler, &find_tel, tel_cmp, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
	{
		printf("Fetch It!\n");
		print(&save);
	}
#endif

	printf("============================\n");

	llist_display(handler, print);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0
#define TAILINSERT 1

typedef void (*llist_op)(const void *);//定义函数指针类型
typedef int (*llist_cmp)(const void *,const void *);

struct llist_node//数据结点的结构体(可变长的结构体)
{
	struct llist_node *prev;//prev指针指向前驱
	struct llist_node *next;//next指针指向后继
	char data[0];//可变长的因子
};

typedef struct llist_head//头结点的结构体
{
	int size;//保存客户创建的结构体的大小
	struct llist_node head;//
}LLIST;

LLIST *llist_create(int );//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *, llist_op);//遍历链表

void llist_destroy(LLIST *);//销毁链表

void *llist_find(LLIST *, const void *, llist_cmp);//查找

int llist_delete(LLIST *, const void *, llist_cmp);//删除

int llist_fetch(LLIST *, const void *, llist_cmp, void *);

#endif

llist.c

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

LLIST *llist_create(int size)
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟失败,结束函数,并且返回NULL
	handler->size = size;//把客户结构体大小存储起来
	handler->head.prev = &handler->head;//前驱指向自己
	handler->head.next = &handler->head;//后继指向自己
	return handler;//把指向头结点的指针返回
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	struct llist_node *p = &handler->head;//保存头结点地址
	struct llist_node *newnode = NULL;//保存新建的数据结点

	newnode = malloc(sizeof(struct llist_node) + handler->size);//数据结点
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟失败,结束函数,并且返回-1
	
	memcpy(newnode->data, data, handler->size);//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break;
		default : free(newnode); return -3;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *handler, llist_op op)
{
	struct llist_node *cur = NULL;
	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *handler)
{
	struct llist_node *cur = NULL;
	
	for(cur=handler->head.next;cur!=&handler->head;cur=handler->head.next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);
	}
	free(handler);
}

struct llist_node *_find(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		if(cmp(cur->data, find_data))
			return cur;
	return NULL;
}

void *llist_find(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return NULL;
	return cur->data;
}

int llist_delete(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return -1;
	///////cur指针已经指向要删除的结点
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	free(cur);
	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, llist_cmp cmp, void *save)
{
	struct llist_node *cur = NULL;

	cur = _find(handler,find_data,cmp);
	if(cur == NULL)
		return -1;
	
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur->data, handler->size);
	free(cur);

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist


=================================

封装通用性强的链表

main.c

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
#include <stdio.h>
#include <string.h>
#include "llist.h"

#define NAMESIZE 20//字符数组的成员个数

struct stu//客户自己创建的数据结构体
{
	int id;
	char name[NAMESIZE];
	int math;
	int age;
	int tel;
};

void print(const void *data)
{
	const struct stu *p = data;
	printf("%d	%s	%d	%d	%d\n",p->id,p->name,p->math,p->age, p->tel);
}

int id_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->id - *k);
}

int name_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const char *k = key;

	return !(strcmp(p->name, k));
}

int tel_cmp(const void *data, const void *key)
{
	const struct stu *p = data;
	const int *k = key;

	return !(p->tel - *k);
}

int main(void)
{
	LLIST *handler = NULL;//handler指针指向头结点
	struct stu data;//存放客户自己的数据
	struct stu save;//存储拿出的数据
	struct stu *find = NULL;//指向找到的数据
	int i = 0;//循环变量
	int ret = 0;//接收返回值
	int find_id = 100;
	int find_tel = 10002;
	char *find_name = "stu4";

	handler = llist_create(sizeof(struct stu));
	//创建头结点
	if(handler == NULL)//判断头结点是否创建失败
		return -1;//创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//存储数据
		sprintf(data.name, "stu%d", i);//存储数据
		data.math = 100 - i;//存储数据
		data.age = 20 + i;//存储数据
		data.tel = 10000 + i;//存储数据
		llist_insert(handler,&data,TAILINSERT);//插入数据
	}

	llist_display(handler, print);//遍历链表

	printf("============================\n");
/*	
	find = llist_find(handler, &find_tel, tel_cmp);//查找
	if(find == NULL)//判断是否没有找到
		printf("Not Find It!\n");
	else
	{
		printf("Find It!\n");
		print(find);
	}
*/
#if 0
	ret = llist_delete(handler, &find_tel, tel_cmp);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler, &find_tel, tel_cmp, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
	{
		printf("Fetch It!\n");
		print(&save);
	}
#endif

	printf("============================\n");

	llist_display(handler, print);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0
#define TAILINSERT 1

typedef void (*llist_op)(const void *);//定义函数指针类型
typedef int (*llist_cmp)(const void *,const void *);
typedef void LLIST;

LLIST *llist_create(int );//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *, llist_op);//遍历链表

void llist_destroy(LLIST *);//销毁链表

void *llist_find(LLIST *, const void *, llist_cmp);//查找

int llist_delete(LLIST *, const void *, llist_cmp);//删除

int llist_fetch(LLIST *, const void *, llist_cmp, void *);

#endif

llist.c

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

struct llist_node//数据结点的结构体(可变长的结构体)
{
	struct llist_node *prev;//prev指针指向前驱
	struct llist_node *next;//next指针指向后继
	char data[0];//可变长的因子
};

struct llist_head//头结点的结构体
{
	int size;//保存客户创建的结构体的大小
	struct llist_node head;//
};

LLIST *llist_create(int size)
{
	struct llist_head *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断头结点空间是否开辟失败
		return NULL;//开辟失败,结束函数,并且返回NULL
	handler->size = size;//把客户结构体大小存储起来
	handler->head.prev = &handler->head;//前驱指向自己
	handler->head.next = &handler->head;//后继指向自己
	return handler;//把指向头结点的指针返回
}

int llist_insert(LLIST *h,const void *data,int mode)
{
	struct llist_head *handler = h;
	struct llist_node *p = &handler->head;//保存头结点地址
	struct llist_node *newnode = NULL;//保存新建的数据结点

	newnode = malloc(sizeof(struct llist_node) + handler->size);//数据结点
	if(newnode == NULL)//判断数据结点是否开辟失败
		return -1;//开辟失败,结束函数,并且返回-1
	
	memcpy(newnode->data, data, handler->size);//拷贝数据

	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : p = p->prev; break;
		default : free(newnode); return -3;
	}
	newnode->next = p->next;
	newnode->prev = p;
	newnode->next->prev = newnode;
	newnode->prev->next = newnode;
	return 0;
}

void llist_display(LLIST *h, llist_op op)
{
	struct llist_head *handler = h;
	struct llist_node *cur = NULL;
	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *h)
{
	struct llist_head *handler = h;
	struct llist_node *cur = NULL;
	
	for(cur=handler->head.next;cur!=&handler->head;cur=handler->head.next)
	{
		cur->next->prev = cur->prev;
		cur->prev->next = cur->next;
		free(cur);
	}
	free(handler);
}

struct llist_node *_find(LLIST *h, const void *find_data, llist_cmp cmp)
{
	struct llist_head *handler = h;
	struct llist_node *cur = NULL;

	for(cur=handler->head.next;cur!=&handler->head;cur=cur->next)
		if(cmp(cur->data, find_data))
			return cur;
	return NULL;
}

void *llist_find(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return NULL;
	return cur->data;
}

int llist_delete(LLIST *handler, const void *find_data, llist_cmp cmp)
{
	struct llist_node *cur = NULL;

	cur = _find(handler, find_data, cmp);
	if(cur == NULL)
		return -1;
	///////cur指针已经指向要删除的结点
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	free(cur);
	return 0;
}

int llist_fetch(LLIST *h, const void *find_data, llist_cmp cmp, void *save)
{
	struct llist_head *handler = h;
	struct llist_node *cur = NULL;

	cur = _find(handler,find_data,cmp);
	if(cur == NULL)
		return -1;
	
	cur->next->prev = cur->prev;
	cur->prev->next = cur->next;
	memcpy(save, cur->data, handler->size);
	free(cur);

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist

04ds_02day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 5.7k 阅读时长 ≈ 5 分钟

============================
2022-8-2
============================

note

malloc calloc realloc 开辟空间
free 释放空间
malloc(sizeof(int) * 4);

线性存储结构
    顺序表
        数组
            一维数组
            多维数组
    链表
        是一种物理存储单元上非连续\非顺序的存储结构
        链表是由一个一个的结点组成的
        每一个结点是由两部分组成 : 数据域 和 指针域
        数据域 : 是用来存储结点的数据的
        指针域 : 是用来存储下一个结点的地址的

        在操作链表时包括有 : 增 删 改 查一系列的操作

        在描述链表时会用到一些属性
            有头链表/无头链表	有没有头结点的意思
            循环链表/不循环链表	链表是否可以构成环
            单向链表/双向链表	遍历链表方向

        有头单向不循环的链表
--------------------------------------------------------------------------------
    创建一个有头单向不循环的链表
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        先把新创建出的结点挂到链表上,再改变链表之前的结构
        头插法{11,22,33,44,55}
        把数据结点插入到头结点之后的位置
        头结点->NULL
        头结点->11->NULL
        头结点->22->11->NULL
        头结点->33->22->11->NULL
        
        尾插法{11,22,33,44,55}
        把数据结点插入到链表最后的位置
        头结点->NULL
        头结点->11->NULL
        头结点->11->22->NULL
        头结点->11->22->33->NULL
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
        销毁链表或者删除结点时要注意
        单链表再删除时需要一前一后两个指针
    =======================================
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出结点			llist_fetch();

==============================
作业
1.把今天讲过的内容完完整整的复习一遍
2.把有头单向不循环链表再重新的写一遍
3.尝试自己搞定有头单向循环链表
==============================

链表

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

enum MODE {HEADINSERT, TAILINSERT};//头插法和尾插法

#define NAMESIZE 20

typedef struct llist_node
{
	int id;//数据域中的数据
	char name[NAMESIZE];//数据域中的数据
	int math;//数据域中的数据
	struct llist_node *next;//指针域(指向下一个结点的指针)
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *,const void *,int);//插入数据结点

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//取出数据

#endif

llist.c

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

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//为头结点开辟空间
	if(handler == NULL)//判断是否开辟空间失败
		return NULL;//开辟空间失败,函数结束,并且返回NULL
	handler->next = NULL;//让头结点的next指针指向NULL
	return handler;//返回头结点的地址
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//通过指针p代替handler做操作
	LLIST *newnode = NULL;//指向新创建出来的数据结点

	newnode = malloc(sizeof(LLIST));//开辟数据结点的空间
	if(newnode == NULL)//判断开辟空间是否失败
		return -1;//开辟失败,结束函数,并且返回-1
	
	memcpy(newnode, data, sizeof(LLIST));
	//把数据拷贝到数据结点中
	switch(mode)
	{
		case HEADINSERT : newnode->next = p->next; break;
		case TAILINSERT : while(p->next != NULL) p = p->next;
							break;
		default : free(newnode); return -2;
		//模式选择有误,释放空间,结束程序,并且返回-2
	}
	p->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur = handler->next; cur != NULL; cur = cur->next)
		printf("%d	%s	%d\n", cur->id,cur->name,cur->math);
}

void llist_destroy(LLIST *handler)
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = handler->next;//指向第一个数据结点

	while(cur != NULL)
	{
		back->next = cur->next;//把要释放的结点从链表中拆除
		free(cur);//释放数据结点
		cur = back->next;
	}
	free(back);//释放头结点
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;//循环查找的指针

	for(cur = handler->next; cur != NULL; cur = cur->next)
	{
		if(cur->id == *(int *)find_data || 
			!strcmp(cur->name, find_data))
		{
			return cur;//找到要查找的结点,并且返回
		}
	}
	return NULL;//没有找到数据结点,返回NULL
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *back = handler;//指向要删除的结点的前一个位置
	LLIST *cur = NULL;//指向要删除的结点

	cur = llist_find(handler, find_data);//查找结点
	if(cur == NULL)//判断是否没有找到结点
		return -1;

	while(back->next != cur)//找到要删除结点的前一个位置
		back = back->next;

	back->next = cur->next;//把要删除结点从链表中拆除
	free(cur);//释放删除的结点
	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *back = handler;
	LLIST *cur = NULL;

	cur = llist_find(handler, find_data);
	if(cur == NULL)
		return -1;
	
	while(back->next != cur)
		back = back->next;
	
	back->next = cur->next;
	memcpy(save, cur, sizeof(LLIST));
	free(cur);
	return 0;
}

main.c

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

int main(void)
{
	LLIST *handler = NULL;//handler指针指向头结点
	LLIST *find = NULL;//find指针指向将来找到的结点
	LLIST data;//用来存储数据的变量
	LLIST save;//将来保存取出的数据
	int i = 0;//循环变量
	int ret = 0;//用来接收返回值的变量
	int find_id = 100;//要查找的id号
	char *find_name = "stu4";//要查找的名字

	handler = llist_create();//创建头结点
	if(handler == NULL)//判断创建头结点是否失败
		return -1;//创建头结点失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)//循环进行插入数据结点
	{
		data.id = 100 + i;//存储数据
		sprintf(data.name, "stu%d", i);//存储数据
		data.math = 100 - i;//存储数据
		data.next = NULL;//让next指针指向空
		llist_insert(handler, &data, TAILINSERT);
		//插入数据结点
	}
	
	llist_display(handler);//遍历链表

	printf("====================\n");
/*
	find = llist_find(handler, "stu9");//查找结点
	if(find == NULL)//判断是否没有找到结点
		printf("Not Find It!\n");
	else
		printf("Find It!	%d	%s	%d\n", find->id, find->name, find->math);
*/
#if 0
	ret = llist_delete(handler, "stu9");//删除结点
	if(ret != 0)//判断是否删除失败
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler,"stu9",&save);//取出数据
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
		printf("Fetch It!	%d	%s	%d\n",save.id, save.name, save.math);
#endif
	printf("====================\n");

	llist_display(handler);//遍历链表

	llist_destroy(handler);//销毁链表

	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist

04ds_03day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 9.7k 阅读时长 ≈ 9 分钟

===========================
2022-8-3
===========================

note

一.不用写调用,只写声明和实现
    实现有头单向不循环链表的
    遍历和销毁

任务(最基本的要求)
    1.大家可以在纸上写出简单的(有头双向循环链表)增删改查
    2.大家可以在电脑上写出通用性强的链表
    3.大家可以使用内核链表(会用)

自己重新写一遍有头单向循环链表的功能
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        (头插法	尾插法)
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
    -----------------------------------
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出结点			llist_fetch();

==============================
作业
1.把今天讲过的内容完完整整的复习一遍
2.重新写一遍有头单向循环链表的各种功能
3.写一个无头单向不循环的链表
4.完成joseph杀人游戏
==============================
================================================================================

无头单向不循环的链表

/*
    实现 无头单向不循环的链表
        无头 : 代表没有头结点
        在无头的链表中所有的结点都是数据结点
    1.插入数据结点		llist_insert();
        由于没有头结点所以直接把新的数据结点插入到链表最后
    2.遍历链表			llist_display();
    3.销毁链表			llist_destroy();
    ------------------------------------
    4.查找结点			llist_find();
    5.删除结点			llist_delete();
    6.拿出结点			llist_fetch();
*/

main.c

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

int main(void)
{
	LLIST *l = NULL;//l指针指向无头链表的第一个结点
	LLIST *find = NULL;//指向找到的结点
	LLIST save;
	int ret = 0;//保存函数的返回值
	int find_id = 100;
	int num = 0;//客户用来录入结点个数的
	char *find_name = "stu9";

	printf("Please Insert Node Number : ");
	scanf("%d", &num);

	l = llist_insert(num);//创建无头链表
	if(l == NULL)//判断是否创建失败
		return -1;//从创建失败,结束程序,并且返回-1
	
	llist_display(l);//遍历链表

	printf("==================\n");
/*	
	find = llist_find(l, find_name);
	if(find == NULL)
		printf("Not Find It!\n");
	else
		printf("Find It!	%d	%s	%d\n",find->id, find->name, find->math);
*/
#if 0
	ret = llist_delete(&l, find_name);
	if(ret != 0)
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(&l, &find_id, &save);
	if(ret != 0)
		printf("Fetch It Is Failed!\n");
	else
		printf("Fetch It!	%d	%s	%d\n", save.id, save.name,save.math);
#endif
	printf("==================\n");

	llist_display(l);

	llist_destroy(l);//销毁链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define NAMESIZE 20

typedef struct llist_node
{
	int id;
	char name[NAMESIZE];
	int math;
	struct llist_node *next;
}LLIST;

LLIST *llist_insert(int);//插入数据结点

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST **, const void *);//删除结点

int llist_fetch(LLIST **, const void *, void *);//拿出结点

#endif

llist.c

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

LLIST *llist_insert(int num)//插入数据结点
{
	LLIST *l = NULL;//指向无头链表的第一个结点
	LLIST *p = NULL;//辅助l指针
	LLIST *newnode = NULL;//指向新的结点
	LLIST data;//用来存储数据
	int i = 0;//循环变量

	l = malloc(sizeof(LLIST));//为第一个结点开辟空间
	if(l == NULL)//判断是否开辟失败
		return NULL;

	data.id = 100 + i;
	sprintf(data.name, "stu%d", i);
	data.math = 100 - i;
	data.next = NULL;
	memcpy(l, &data, sizeof(LLIST));
	p = l;
	for(i = 1; i < num; i++)
	{
		newnode = malloc(sizeof(LLIST));
		if(newnode == NULL)//判断是否开辟失败
			return l;
		data.id = 100 + i;
		sprintf(data.name, "stu%d", i);
		data.math = 100 - i;
		data.next = NULL;
		memcpy(newnode, &data, sizeof(LLIST));
		p->next = newnode;
		p = p->next;
	}

	return l;//把第一个结点的地址返回
}

void llist_display(LLIST *l)//遍历链表
{
	LLIST *cur = NULL;

	for(cur = l; cur != NULL; cur = cur->next)
		printf("%d	%s	%d\n",cur->id,cur->name,cur->math);
}

void llist_destroy(LLIST *l)//销毁链表
{
	LLIST *back = l;
	LLIST *cur = l->next;

	while(cur != NULL)
	{
		back->next = cur->next;
		free(cur);
		cur = back->next;
	}
	free(back);
}

LLIST *llist_find(LLIST *l, const void *find_data)
{
	LLIST *cur = NULL;
	for(cur = l; cur != NULL; cur = cur->next)
	{
		if(cur->id==*(int*)find_data || 
			!(strcmp(cur->name, find_data)))
			return cur;
	}
	return NULL;
}

int llist_delete(LLIST **l, const void *find_data)
{
	LLIST *back = *l;//指向第一个结点
	LLIST *cur = NULL;//指向要删除的结点

	cur = llist_find(*l, find_data);//查找要删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//没有找到,结束函数,并且返回-1
	
	if(cur == *l)//判断要删除的结点是否是第一个结点
		(*l) = (*l)->next;//把指向改变为下一个结点
	else
	{
		while(back->next != cur)
			back = back->next;
		back->next = cur->next;
	}
	free(cur);
	return 0;
}

int llist_fetch(LLIST **l, const void *find_data, void *save)
{
	LLIST *back = *l;//指向第一个结点
	LLIST *cur = NULL;//指向要删除的结点

	cur = llist_find(*l, find_data);//查找要删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//没有找到,结束函数,并且返回-1
	
	if(cur == *l)//判断要删除的结点是否是第一个结点
		(*l) = (*l)->next;//把指向改变为下一个结点
	else
	{
		while(back->next != cur)
			back = back->next;
		back->next = cur->next;
	}
	memcpy(save, cur, sizeof(LLIST));
	free(cur);
	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist


================================================================================

需要实现有头单向循环链表

/*
    需要实现有头单向循环链表
    1.创建头结点		llist_create();
    2.插入数据结点		llist_insert();
        头插法	尾插法
    3.遍历链表			llist_display();
    4.销毁链表			llist_destroy();
    ===================================
    5.查找结点			llist_find();
    6.删除结点			llist_delete();
    7.拿出数据			llist_fetch();
*/

main.c

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>
#include "llist.h"

int main(void)
{
	LLIST *handler = NULL;//指向头结点的指针
	LLIST *find = NULL;//指向找到的结点
	LLIST data;//用来存储用户的数据
	LLIST save;//保存拿出的数据
	int i = 0;//循环变量
	int ret = 0;//用于接收返回值
	int find_id = 100;//要查找的ID号
	char *find_name = "stu4";//要查找的姓名

	handler = llist_create();//创建头结点
	if(handler == NULL)//判断是否创建头结点失败
		return -1;//头结点创建失败,结束程序,并且返回-1
	
	for(i = 0; i < 5; i++)
	{
		data.id = 100 + i;//赋值数据
		sprintf(data.name, "stu%d", i);//赋值数据
		data.math = 100 - i;//赋值数据
		data.next = NULL;//指针指向NULL
		llist_insert(handler,&data,TAILINSERT);//插入数据
	}
	
	llist_display(handler);//遍历链表

	printf("=========================\n");
/*	
	find = llist_find(handler, "stu9");//查找结点
	if(find == NULL)//判断是否没有找到结点
		printf("Not Find It!\n");
	else
		printf("Find It!	%d	%s	%d\n", find->id, find->name, find->math);
*/
#if 0
	ret = llist_delete(handler, "stu9");//删除结点
	if(ret != 0)//判断是否删除失败
		printf("Delete It Is Failed!\n");
	else
		printf("Delete It!\n");
#else
	ret = llist_fetch(handler,find_name, &save);//拿出数据
	if(ret != 0)//判断是否拿出失败
		printf("Fetch It Is Failed!\n");
	else
		printf("Fetch It!	%d	%s	%d\n",save.id, save.name, save.math);
#endif
	printf("=========================\n");

	llist_display(handler);//遍历链表

	llist_destroy(handler);//释放链表

	return 0;
}

llist.h

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
#ifndef __LLIST_H
#define __LLIST_H

#define HEADINSERT 0//头插法
#define TAILINSERT 1//尾插法
#define NAMESIZE 20//名字成员个数

typedef struct llist_node//定义了每个结点的结构体类型
{
	int id;
	char name[NAMESIZE];
	int math;
	struct llist_node *next;
}LLIST;

LLIST *llist_create();//创建头结点

int llist_insert(LLIST *, const void *, int );//插入数据

void llist_display(LLIST *);//遍历链表

void llist_destroy(LLIST *);//销毁链表

LLIST *llist_find(LLIST *, const void *);//查找结点

int llist_delete(LLIST *, const void *);//删除结点

int llist_fetch(LLIST *, const void *, void *);//拿出数据

#endif

llist.c

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

LLIST *llist_create()
{
	LLIST *handler = NULL;//指向头结点的指针

	handler = malloc(sizeof(LLIST));//开辟头结点的空间
	if(handler == NULL)//判断是否开辟失败
		return NULL;//开辟失败,结束函数,并且返回NULL
	handler->next = handler;//头结点的next指针指向自己

	return handler;//把头结点的地址返回
}

int llist_insert(LLIST *handler,const void *data,int mode)
{
	LLIST *p = handler;//通过指针p代替handler做操作
	LLIST *newnode = NULL;//指向新创建的结点

	newnode = malloc(sizeof(LLIST));//开辟数据结点的空间
	if(newnode == NULL)//判断数据结点的空间是否开辟失败
		return -1;//数据结点的空间开辟失败,函数结束,返回-1
	
	memcpy(newnode, data, sizeof(LLIST));//拷贝数据
	switch(mode)
	{
		case HEADINSERT : break;
		case TAILINSERT : while(p->next != handler)
							p = p->next;
							break;
		default : free(newnode); return -2;
				  //释放空间,结束函数,并且返回-2
	}
	newnode->next = p->next;
	p->next = newnode;
	return 0;
}

void llist_display(LLIST *handler)//遍历链表
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur=handler->next; cur!=handler; cur=cur->next)
		printf("%d	%s	%d\n",cur->id,cur->name,cur->math);
}

void llist_destroy(LLIST *handler)//销毁链表
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = handler->next;//指向数据结点的指针

	while(cur != handler)
	{
		back->next = cur->next;
		free(cur);
		cur = back->next;
	}
	free(cur);
}

LLIST *llist_find(LLIST *handler, const void *find_data)
{
	LLIST *cur = NULL;//指向每一个数据结点

	for(cur=handler->next;cur!=handler;cur=cur->next)
	{
		if(cur->id==*(int*)find_data || 
			!(strcmp(cur->name, find_data)))
			return cur;//找到了结点,并且返回
	}
	return NULL;//没有找到结点,返回NULL
}

int llist_delete(LLIST *handler, const void *find_data)
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = NULL;//指向要删除的结点的指针

	cur = llist_find(handler, find_data);//查找删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//删除失败,函数结束,并且返回-1
	
	while(back->next != cur)//查找要删除结点的前一个位置
		back = back->next;

	back->next = cur->next;//把删除的结点从链表中摘除
	free(cur);//释放要删除的结点
	return 0;
}

int llist_fetch(LLIST *handler, const void *find_data, void *save)
{
	LLIST *back = handler;//指向头结点的指针
	LLIST *cur = NULL;//指向要删除的结点的指针

	cur = llist_find(handler, find_data);//查找删除的结点
	if(cur == NULL)//判断是否没有找到
		return -1;//删除失败,函数结束,并且返回-1
	
	while(back->next != cur)//查找要删除结点的前一个位置
		back = back->next;

	back->next = cur->next;//把删除的结点从链表中摘除
	memcpy(save, cur, sizeof(LLIST));//把数据拿出
	free(cur);//释放要删除的结点
	return 0;
}

makefile

1
2
3
4
llist : main.o llist.o
	gcc -o $@ $^
clean :
	rm -rf *.o llist

04ds_01day

发表于 2023-02-16 更新于 2022-09-02
本文字数： 7.8k 阅读时长 ≈ 7 分钟

===========================
2022-8-1
===========================

一.温故知新

    复合型数据类型
        结构体
        1.先定义结构体类型
            struct tag
            {
                //结构体成语的定义
            };
        2.再使用结构体类型定义结构体类型的变量\指针\数组
            数据类型		变量名	;
            struct tag		s		;
            struct tag *	p		;
            struct tag		arr	[成员个数]	;
        3.结构体类型的变量访问结构体的成员
            变量名 + . + 成员名
        结构体类型的指针访问结构体的成员
            指针名 + -> + 成员名
        4.通过sizeof运算符结算结构体大小
            结构体的大小相当于成员大小的和 + 字节对齐
        共用体
            共用体中的成员会共用同一块儿存储空间
            (使用一块儿存储空间管理不同类型的数据)
            1.先定义共用体类型
            union tag
            {
                共用体成员的定义;
            };
            2.大端格式和小端格式
            大端格式
            高字节的数据存放在低地址上
            低字节的数据存放在高地址上
            小端格式
            高字节的数据存放在高地址上
            低字节的数据存放在低地址上
            3.位域(位段/位字段)
            是编程语言(C语言)提供的操作位的方法
            -----------------------------------
            位带(bitband)

共用体(联合)
union是C语言中的关键字
1.共用体的含义
    共用体的成员共用同一块儿存储空间
    (使用一块儿存储空间管理不同的数据类型)
2.共用体的定义
    union tag				//tag是标签
    {
        共用体成员的定义;
    };						//最后需要加 ; 结尾
3.和结构体不同的地方
    1>结构体中每个成员都会占用独立的存储空间
    共用体中每个成员都会占用相同的存储空间
    2>结构体的大小是每个成员大小的和的基础上加入字节对齐
    共用体的大小以共用体成员中最大的成员大小为准
4.大端格式和小端格式
    在硬件的平台中是分为大端格式和小端格式的
    X86/英特尔架构		小端格式
    高字节的数据存放在高地址上,低字节的数据存放在低地址上
    (高对高,低对低)
    例子 : 在小端格式上存储一个十六进制的数据0x12345678
    地址		数据
    0x1000		0x78
    0x1001		0x56
    0x1002		0x34
    0x1003		0x12
    ARM架构->ARM系列大端格式(现在既支持大端也支持小端)
    高字节的数据存放在低地址上,低字节的数据存放在高地址上
    (高对低,低对高)
    例子 : 在大端格式上存储一个十六进制的数据0x12345678
    地址		数据
    0x1000		0x12
    0x1001		0x34
    0x1002		0x56
    0x1003		0x78
可以使用共用体测试当前的机器是大端格式还是小端格式

=========================
笔试题
1.什么是大端格式?什么是小端格式?
2.设计一个程序测试当前的机器是大端格式还是小端格式
=========================

预处理

预处理
    条件编译
#ifndef	__ADD_H
#define __ADD_H
除了在.h文件中加入,防止头文件被重复包含以外
在.c文件中也可以使用

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
#if 0
	printf("Hello World!\n");
#else
	printf("你好,中国!\n");
#endif
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>

#define SUB

int main(int argc, char *argv[])
{
	int a = 13, b = 7;
	int sum = 0;

#ifndef ADD
	sum = a + b;
#else
	sum = a - b;
#endif
	printf("sum = %d\n", sum);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

#define STM32F103CBT6

int main(int argc, char *argv[])
{
	int PIN = 0;
#if defined (STM32F103RBT6)
	PIN = 64;
#elif defined (STM32F103CBT6)
	PIN = 32;
#endif
	printf("PIN = %d\n", PIN);

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

#define FLAG 2

int main(int argc, char *argv[])
{
	int a = 13, b = 7;
	int sum = 0;

#if FLAG==0
	sum = a + b;
#elif FLAG==1
	sum = a - b;
#elif FLAG==2
	sum = a * b;
#elif FLAG==3
	sum = a / b;
#else
	sum = a % b;
#endif

	printf("sum = %d\n", sum);
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>

#define PAI 3.14

int main(int argc, char *argv[])
{
	printf("PAI = %f\n", PAI);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

#define ARRSIZE 10

int main(int argc, char *argv[])
{
	int arr[ARRSIZE];
	int i = 0;

	for(i = 0; i < ARRSIZE; i++)
	{

	}

	return 0;
}

    面试题
    1.定义一个宏,计算一年(平年)有多少秒
    
    2.定义一个宏,比较两个值的最大值

    3.定义一个宏,完成两个变量值的交换

    注意 : 在写宏函数的时候一定要加小括号,代表是一个整体

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>

#define SEC_OF_YEAR (365*24*60*60)

int main(int argc, char *argv[])
{
	printf("SEC_OF_YEAR = %d\n", SEC_OF_YEAR);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <stdlib.h>

#define MUL(A,B) (A)*(B)
//MUL(A,B)		A*B
//MUL(2+3,3+4)	2+3*3+4 = 15
int mul(int a, int b)
{
	return a * b;
}

int main(int argc, char *argv[])
{
	int a = 13, b = 7;

	printf("MUL = %d\n", MUL(2+3, 3+4));//a+b
	printf("mul = %d\n", mul(2+3, 3+4));//a+b

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>

#define MAX(A,B) A>B?A:B
//a++ > b++ ? a++ : b ++

int max(int a, int b)
{
	return a > b ? a : b;
}

int main(int argc, char *argv[])
{
	int a = 13, b = 7;

	printf("MAX = %d\n", MAX(a++, b++));
	a = 13;
	b = 7;
	printf("max = %d\n", max(a++, b++));

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>

//#define SWAP(A,B) {typeof(A)tmp; tmp=A; A=B; B=tmp;}
//#define SWAP(A,B) {(A)=(A)+(B);(B)=(A)-(B);(A)=(A)-(B);}
#define SWAP(A,B) {(A)^=(B);(B)^=(A);(A)^=(B);}

int main(int argc, char *argv[])
{
	int a = 13, b = 7;

	printf("a = %d b = %d\n", a, b);
	SWAP(a,b);
	printf("a = %d b = %d\n", a, b);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	printf("__DATE__ = %s\n", __DATE__);
	printf("__TIME__ = %s\n", __TIME__);
	printf("__FILE__ = %s\n", __FILE__);
	printf("__LINE__ = %d\n", __LINE__);
	printf("__FUNCTION__ = %s\n", __FUNCTION__);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
	int a = 3, b = 4, c = 5;

	if((a + b > c) && \
		(a + c > b) && \
		(b + c > a))
	{
		printf("可以构成三角形!\n");
	}

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <stdlib.h>

#define PRINT_STR(n) #n

int main(int argc, char *argv[])
{
	printf("PRINT_STR = %s\n", PRINT_STR(12+34));

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>

#define INT_VAR(n) var##n

int main(int argc, char *argv[])
{
	int var1 = 100;
	int var2 = 200;
	int var3 = 300;
	int var4 = 400;
	int var5 = 500;

	printf("VAR = %d\n", INT_VAR(2));//var2
	printf("VAR = %d\n", INT_VAR(5));//var5

	return 0;
}

枚举
enum是C语言的关键字
枚举就是一个被命名的整型常数的集合
enum 枚举名
{
    标识符[=整型常数],
    标识符,
    ...
    标识符
};			//枚举定义之后需要加 ; 结尾
注意:
1.在定义枚举时.标识符与标识符之间要用 , 隔开而不是 ; 
2.在枚举中标识符可以和变量同名,如果同名变量会屏蔽标识符
    (尽量不要同名)
3.在定义枚举时,方括号的内容时缺省值,可以有也可以没有
    如果没有缺省值,标识符会按照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
#include <stdio.h>
#include <stdlib.h>

enum E
{
	a,
	b,
	c,
	d
};

int main(int argc, char *argv[])
{
	printf("a = %d\n", a);
	printf("b = %d\n", b);
	printf("c = %d\n", c);
	printf("d = %d\n", d);
	
	//a = 9527;枚举的标识符不是变量,不能做赋值运算

	printf("a = %d\n", a);

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

enum E
{
	a,
	b,
	c,
	d
};

int main(int argc, char *argv[])
{
	int a = 9527;
	printf("a = %d\n", a);
	printf("b = %d\n", b);
	printf("c = %d\n", c);
	printf("d = %d\n", d);
	
	//a = 9527;枚举的标识符不是变量,不能做赋值运算

	printf("a = %d\n", a);

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

enum E
{
	a,
	b = 100,
	c,
	d
};

int main(int argc, char *argv[])
{
	//int a = 9527;
	printf("a = %d\n", a);
	printf("b = %d\n", b);
	printf("c = %d\n", c);
	printf("d = %d\n", d);
	
	//a = 9527;枚举的标识符不是变量,不能做赋值运算

	printf("a = %d\n", a);

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

enum E
{
	a,
	b = 100,
	c,
	d
};

int main(int argc, char *argv[])
{
	//int a = 9527;
	printf("a = %d\n", a);
	printf("b = %d\n", b);
	printf("c = %d\n", c);
	printf("d = %d\n", d);
	
	//a = 9527;枚举的标识符不是变量,不能做赋值运算

	printf("a = %d\n", a);

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>

enum E{MODE_0, MODE_1, MODE_2, MODE_3};

int main(int argc, char *argv[])
{
	int mode = 0;

	scanf("%d", &mode);

	switch(mode)
	{
		case MODE_0 : printf("菜鸟难度!\n"); break;
		case MODE_1 : printf("普通难度!\n"); break;
		case MODE_2 : printf("地狱难度!\n"); break;
		case MODE_3 : printf("中国男足难度!\n"); break;
	}

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

struct GPIO
{
	unsigned char PA0 : 2;
	unsigned char PA1 : 2;
	unsigned char PA2 : 2;
	unsigned char PA3 : 2;
	unsigned char PA4 : 2;
	unsigned char PA5 : 2;
	unsigned char PA6 : 2;
	unsigned char PA7 : 2;
	unsigned char PA8 : 2;
	unsigned char PA9 : 2;
	unsigned char PA10: 2;
	unsigned char PA11: 2;
	unsigned char PA12: 2;
	unsigned char PA13: 2;
	unsigned char PA14: 2;
	unsigned char PA15: 2;
};

enum mode
{
	INPUT,
	OUTPUT,
	AF,
	AN
};

int main(int argc, char *argv[])
{
	struct GPIO P;

	P.PA0 = OUTPUT;

	P.PA10 = AF;

	return 0;
}

03c_C截图

发表于 2023-02-16 更新于 2022-09-02
本文字数： 101 阅读时长 ≈ 1 分钟

1数据类型

2ASCII_1

2ASCII_2

2ASCII_3

3转义字符

4运算符

5存储类型比较

6标准输出格式字符

7标准输出修饰符

8一维数组元素表示

9二维数组元素表示

10区分定义

11函数的实现

12运算符优先级

03c_point_and_func

发表于 2023-02-16 更新于 2022-09-02
本文字数： 2.7k 阅读时长 ≈ 2 分钟

===========================
2022-8-1
===========================

1.指针

使用指针的用处

        程序员通过指针,可以简化一些 C 语言编程任务的执行,还有一些任务,如动态内存分配
        大家都知道每一个变量都在内存中占用相应的存储空间,
动态内存分配的函数	malloc calloc realloc free
编程人员来讲
1.谁打开,谁关闭	文件IO
2.谁开辟,谁释放	动态内存
3.谁创建,谁销毁	链表
4.谁加锁,谁解锁	线程

        每一个内存位置都可以使用连字号（&）运算符访问的地址,它表示了在内存中的一个地址
    什么是指针
        其实指针从某种意义上来讲是一个变量,其值为另一个变量的地址,即内存位置的直接地址.
        就像普通的变量一样,必须在使用指针之前,对其进行定义.
        指针的定义一般形式为:type *pointer-name;
        无论何种类型的指针在内存中都占用8个字节空间(相对于64bit操作系统而言)
        不同数据类型的指针之间的相同点是都是用来存储地址的.
        不同数据类型的指针之间唯一的不同是,指针所指向的变量的数据类型不同.

如何使用指针？

        使用指针时会频繁进行以下几个操作:
int a;
        定义一个指针变量					int *p;
        把变量地址赋值给指针				p = &a;
        访问指针变量中可用地址的值			printf(“p = %p\n”, p);
        这些操作是需要通过使用运算符 * 来访问的

指向NULL的指针(空指针) int *p = NULL;//NULL ASCII 0 0x0

        在指针初始化的时候,如果没有确切的地址可以赋值,为指针赋一个 NULL 值
        是一个良好的编程习惯.赋为 NULL 值的指针被称为空指针.
        在写C语言程序时不允许访问地址为 NULL 的内存,因为该内存是操作系统保留的
        然而,内存地址 NULL 有特别重要的意义,它表明该指针不指向一个可操作的内存位置.
int a;
int *p = NULL;
p = &a;
*p = 100;
程序编译时不会报错报警告,但是程序执行时会报段错误(编译器不检查段错误)
if(p == NULL)
printf(“p是一个空指针!\n”);

野指针(没有对象)

        野指针指向一个已删除的对象或申请访问受限内存区域的指针.
        与空指针不同,野指针无法通过简单地判断是否为 NULL 避免,
        而只能通过养成良好的编程习惯来尽力减少.
        对野指针进行操作很容易造成程序错误.
        程序编译时不会报错报警告,程序执行时也不会报段错误
        int *p = NULL;
        p = malloc(sizeof(int));
        使用
        free(p);
        p = NULL;//可以先把野指针变成空指针,然后可以避免程序执行时不会报错

万能指针

    可以保存任意类型的地址

2.函数

什么是函数

        函数是一组一起执行一个任务的语句.每个 C 程序都至少有一个函数,
        即主函数 main() 所有简单的程序都可以定义其他额外的函数.
        程序员可以把代码划分到不同的函数中.
        如何划分代码到不同的函数中是程序员自己来决定的,但在逻辑上,
        划分通常是根据每个函数执行一个特定的任务来进行的.
        函数声明告诉编译器函数的名称\返回类型和参数.函数定义提供了函数的实际主体。

函数的声明

        函数声明会告诉编译器函数名称及如何调用函数.
        函数声明包括以下几个部分:
        return_type		function_name	(parameter list)	;//形式参数 形参
        int				max			(int a, int b)		;
int				add				(int a, int b)		;
Void			swap			(int *a, int *b)	;
        在函数声明中,参数的名称并不重要,只有参数的类型是必需的
        int max(int, int);

函数的实现

        return_type		function_name	(parameter list)//形式参数 形参
        {
   			body of the function
        }
int				max			(int a, int b)
{
return a > b ? a : b;
}
int				add				(int a, int b)
{
return a + b;
}




void		swap	(int *a, int * b)
{
int c;
c = *a;
*a = *b;
*b = c;
}

函数的调用

        当实现函数的功能时,会写出函数要做什么,然后通过调用函数来执行已写好的功能.
        当程序调用函数时,程序控制权会转移给被调用的函数.
        被调用的函数执行函数主体的内容,当函数的返回语句被执行时,
        或到达函数的结束括号时,会把程序控制权交还给主程序.
        调用函数时,传递所需参数,如果函数返回一个值,则可以在调用时用变量来存储返回值.
        function_name	(parameter list);//实际参数 实参
max			(13, 7);
add				(13, 7);		
swap			(&a, &b);
    在 C 语言中,函数由一个函数头和一个函数主体组成.下面列出一个函数的所有组成部分:
        返回类型 : 一个函数可以返回一个值.return_type 是函数返回的值的数据类型.
            有些函数执行所需的操作而不返回值,在这种情况下,return_type 是关键字 void.
        
        函数名称 : 这是函数的实际名称.也是函数的入口
    	
        参数 : 参数就像是占位符.当函数被调用时,程序员需要向参数传递一个值,
            这个值被称为实际参数.参数列表包括函数参数的类型\顺序\数量.
            参数是可选的,也就是说,有些功能函数可能不需要参数.
    	
        函数主体 : 函数主体包含一组定义函数执行任务的语句.
    
    函数参数
        如果函数要使用参数,则必须在函数声明时定义参数变量,这些变量称为函数的形式参数.
        形式参数就像函数内的其他局部变量,在进入函数时被创建,退出函数时被销毁.
    
    当调用函数时,有两种向函数传递参数的方式:
        值传递 : 该方法把参数的实际值复制给函数的形式参数,在这种情况下
                修改函数内的形式参数不会影响实际参数。
swap(a, b)
        地址传递 : 通过指针传递方式,形参为指向实参地址的指针,
                当对形参的指向操作时,就相当于对实参本身进行的操作。
swap(&a, &b)
        如果使用值传递来传递参数,这意味着函数内的代码不能改变用于调用函数的实际参数.