04ds_09day

04ds_09day

============================
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

resources/02tree.png

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

resources/03tree.png

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

resources/04tree.png

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

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

resources/05tree.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
 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;
}
© 2020 - 2026 ynhugo