王道数据结构与算法代码（与书本伪代码统一）有思维导图逐句注解 持续更新_王道数据结构代码

本文以王道23版本数据结构与算法书本伪代码为基础进行编写
内容仅供参考，配有个人编写代码辅助思维导图，有部分地方为个人理解，如果发现理解有偏差或者有误欢迎评论区指正，谢谢大家。

01.typedef的使用

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef struct student
{
	int num;
	char name[30];
	char sex[30];
}stu, * Studefine;

typedef int INT;
int main()
{
	stu s = { 1080,"ssao","nan" };
	Studefine p;
    INT n = 100;
	p = &s;
	printf("%d,p->num=%d", n, p->num);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

02.c++的使用

#include <stdio.h>
#include <malloc.h>

void change(int& s)
{
	s++;

};
void gave(int*& d)
{
	d = (int*)malloc(20);//强制类型转换
	d[0] = 1;
}

int main()
{
	int s = 10;
	change(s);
	printf("%d\n", s);
	int* d = NULL;
	gave(d);
	printf("%d\n", d[0]);
	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

03.顺序表的增删查

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50//这个地方不要加“；”
typedef int Minter;
typedef  struct
{
	Minter data[MaxSize];
	int len;
}Sqlist;

//插入操作
bool Cain(Sqlist& L, int i, Minter e)
{
	if (i < 1 || i > L.len)
		return false;
	if (L.len >= MaxSize)
		return false;
	for (int j = L.len; j >= i; j--)
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;
	L.len++;
	return true;
}
//打印操作
void printf_m(Sqlist& L)
{
	for (int i = 0; i < L.len; i++)
		printf("%3d", L.data[i]);
	printf("\n");
}
//删除操作
bool DelList(Sqlist& L, int i, Minter& e)
{
	if (i < 1 || i > L.len)
		return false;
	if (L.len == 0)
		return false;
	e = L.data[i - 1];
	for (int j = i; j < L.len; j++)
		L.data[j - 1] = L.data[j];
	L.len--;
	return true;


}
//查找操作
int FindList(Sqlist& L, Minter e)
{
	for (int i = 0; i < L.len; i++)
		if (L.data[i] == e)
			return i + 1;
	return 0;
}
int main()
{
	Sqlist L;
	bool res;
	int del = 0;//存储删除元素
	L.data[0] = 1;
	L.data[1] = 2;
	L.data[2] = 3;
	L.len = 3;
	//插入部分调用及反馈
	res = Cain(L, 2, 60);
	if (res)
	{
		printf("插入成功\n");
		printf_m(L);
	}
	else
	{
		printf("插入失败\n");
	}
	//删除部分调用及反馈
	res = DelList(L, 1, del);
	if (res)
	{
		printf("删除成功\n");
		printf_m(L);
	}
	else
	{
		printf("删除失败\n");
	}
	int ele_pos;
	ele_pos = FindList(L, 60);
	if (ele_pos)
	{
		printf("查找成功\n元素位置为 %d\n", ele_pos);
	}
	else
	{
		printf("查找失败");

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

04.线性表的链式表示

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//3 4 5 6 7 9999
typedef int Emoint;
typedef struct Lnote
{
	Emoint data;
	struct Lnote* next;
}Lnote, * Linklist;
//头插法
Linklist Chahead(Linklist& L)
{
	Lnote* s; int x;
	L = (Linklist)malloc(sizeof(Lnote));
	L->next = NULL;
	scanf("%d", &x);
	while (x != 9999)
	{
		s = (Lnote*)malloc(sizeof(Lnote));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}
//尾插法
Linklist Chatail(Linklist& L)
{
	int x;
	L = (Linklist)malloc(sizeof(Lnote));
	Lnote* s, * r = L;
	scanf("%d", &x);
	while (x != 9999)
	{
		s = (Lnote*)malloc(sizeof(Lnote));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}
//打印
void PrintfList(Linklist L)
{
	L = L->next;
	while (L != NULL)
	{
		printf("%3d", L->data);
		L = L->next;
	}
	printf("\n");
}
//按序号查找结点值
Linklist NumFind(Linklist L, int i)
{
	int j = 1;
	Lnote* p = L->next;//让p指向第一个结点
	if (i == 0)
		return L;//i是零就返回头结点
	if (i < 1)
		return NULL;
	while (p && j < i)
	{
		p = p->next;//让p指向下一个结点
		j++;
	}
	return p;
}
//按值查找结点值
Linklist Find(Linklist L, Emoint i)
{
	Linklist p = L->next;
	while (p != NULL && p->data != i)
		p = p->next;
	return p;
}
//新结点处插入操作
bool ChaList(Linklist L, int i, Emoint j)
{
	Linklist p = NumFind(L, i - 1);
	if (p == NULL)
		return false;
	Linklist s = (Linklist)malloc(sizeof(Lnote));
	s->data = j;
	s->next = p->next;
	p->next = s;
	return 0;
}
//删除操作
bool DelList(Linklist L, int  i)
{
	Linklist p = NumFind(L, i - 1);
	if (p == NULL)
		return false;
	Linklist s;
	s = p->next;
	p->next = s->next;
	free(s);
	return true;
}
//主函数
int main()
{
	Linklist L;
	Linklist Cun;
	Chahead(L);//头插法	
	//Chatail(L);//尾插法
	PrintfList(L);//打印
	//按序号查找
	Cun = NumFind(L, 4);
	if (Cun != NULL)
	{
		printf("按序号查找成功\n");
		printf("%d\n", Cun->data);
	}
	//按值查找
	Cun = Find(L, 6);
	if (Cun != NULL)
	{
		printf("按值查找成功\n");
		printf("%d\n", Cun->data);
	}
	//插入节点
	ChaList(L, 2, 99);
	if (true)
	{
		printf("插入成功\n");
		PrintfList(L);
	}
	//删除节点
	DelList(L, 4);
	if (true)
	{
		printf("删除成功\n");
		PrintfList(L);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

05.双向链表

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef int Elemon;
typedef struct NBone
{
	Elemon data;
	struct NBone* prior, * next;
}NB, * NBlist;
//头插法
NBlist ChaHead(NBlist& DL)
{
	NB* p; int x;
	DL = (NBlist)malloc(sizeof(NB));
	DL->next = NULL;
	DL->prior = NULL;
	scanf("%d", &x);
	while (x != 9999)
	{
		p = (NBlist)malloc(sizeof(NB));
		p->data = x;
		p->next = DL->next;
		if (DL->next != NULL)
		{
			DL->next->prior = p;
		}
		p->prior = DL;
		DL->next = p;
		scanf("%d", &x);
	}
	return DL;

}
//打印操作
void PrintfDL(NBlist DL)
{
	DL = DL->next;
	while (DL->next != NULL)
	{
		printf("%3d", DL->data);
		DL = DL->next;
	}
	printf("\n");
}
//尾插法
NBlist ChaTail(NBlist& DL)
{
	int x;
	DL = (NBlist)malloc(sizeof(NB));
	NBlist s, r = DL;
	scanf("%d", &x);
	while (x != 9999)
	{
		s = (NBlist)malloc(sizeof(NB));
		s->data = x;
		r->next = s;
		s->prior = r;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return DL;
}
//按序号查找
NBlist numFind(NBlist& DL, int i)
{
	int j = 1;
	NBlist p = DL->next;
	if (i == 0)
		return DL;
	if (i < 1)
		return NULL;
	while (p && j < i)
	{
		p = p->next;
		j++;
	}
	return p;

}
//插入
bool ChaAom(NBlist DL, int i, Elemon e)
{
	NBlist p = numFind(DL, i - 1);
	if (p == NULL)
		return false;
	NBlist s = (NBlist)malloc(sizeof(NB));
	s->data = e;
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}
//删除
bool DelDL(NBlist DL, int i)
{
	NBlist p = numFind(DL, i - 1);
	if (p == NULL)
		return false;
	NBlist r;
	r = p->next;
	if (r == NULL)
		return false;
	p->next = r->next;
	if (r->next != NULL)
		r->next->prior = p;
	free(r);
	return true;
}
//主函数
int main()
{
	//3 4 5 6 7 9999
	NBlist DL;
	NBlist search;
	//ChaHead(DL);
	ChaTail(DL);
	PrintfDL(DL);
	search = numFind(DL, 3);
	if (search != NULL)
	{
		printf("查找成功结果如下\n");
		printf("%3d\n", search->data);
	}
	ChaAom(DL, 2, 99);
	if (true)
	{

		printf("插入成功结果如下\n");
		PrintfDL(DL);
	}

	DelDL(DL, 2);
	if (true)
	{

		printf("删除成功结果如下\n");
		PrintfDL(DL);
	}


}
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

06.栈

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
typedef int Zlist;
typedef struct
{
	Zlist data[MaxSize];
	Zlist top;
}NBlist;
//初始化
void Tof(NBlist& S)
{
	S.top = -1;
}
//判断是否初始化成功
bool PanList(NBlist& S)
{
	if (S.top == -1)
	{
		return true;

	}
	return false;
}
//入栈
bool PutIn(NBlist& S, Zlist x)
{
	if (S.top == MaxSize - 1)

	{
		return false;
	}
	/*S.top = S.top + 1;
	S.data[S.top]=x;*/
	S.data[++S.top] = x;//S.top=S.top+1 ;S.data[S.top];
	return true;
}
//获取栈顶元素
bool Take(NBlist& S, Zlist& x)
{
	if (S.top == -1)
	{
		return false;
	}

	x = S.data[S.top];
	return true;
}
//出栈操作
bool OutZhan(NBlist& S, Zlist& x)
{
	if (S.top == -1)
	{
		return false;
	}
	x = S.data[S.top];
	S.top = S.top - 1;
	return true;

}
int main()
{
	NBlist S;
	bool flag;
	Zlist m;
	//栈初始化
	Tof(S);
	//判断栈是否为空
	flag = PanList(S);
	if (flag)
	{
		printf("栈是空的\n");
	}
	//入栈操作
	PutIn(S, 3);
	PutIn(S, 4);
	PutIn(S, 5);
	//获取栈顶元素
	flag = Take(S, m);
	if (flag)
	{
		printf("获取栈顶元素为%d\n", m);
	}
	//出栈操作
	flag = OutZhan(S, m);
	if (flag)
	{
		printf("弹出的元素为%d\n", m);
	}
}
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

07.循环队列

#include <stdio.h>;
#include <stdlib.h>;

#define MaxSize 5//这个地方一定不要加分号
typedef int EmlyInt;
typedef struct {
	EmlyInt data[MaxSize];
	EmlyInt front, rear;
}NbList;
//初始化
bool NewList(NbList& S)
{
	S.front = S.rear = 0;
	return true;
}
//判断是否为空
bool KanList(NbList& S)
{
	if (S.front == S.rear)
	{
		return true;
	}
}
//入队
bool Inlist(NbList& S, EmlyInt x)
{
	if ((S.rear + 1) % MaxSize == S.front)
		return false;
	S.data[S.rear] = x;
	S.rear = (S.rear + 1) % MaxSize;
	return true;
}
//出队
bool Outlist(NbList& S, EmlyInt& m)
{
	if (S.front == S.rear)
		return false;
	m = S.data[S.front];
	S.front = (S.front + 1) % MaxSize;
}
int main()
{
	NbList S;
	bool res;
	EmlyInt search;
	NewList(S);
	//判断
	res = KanList(S);
	if (res)
	{
		printf("队列为空\n");
	}
	else
	{
		printf("队列不为空");
	}

	//入队
	Inlist(S, 3);
	Inlist(S, 4);
	Inlist(S, 5);
	res = Inlist(S, 6);
	res = Inlist(S, 7);
	if (res)
	{
		printf("入队成功\n");
	}
	else
	{

		printf("入队失败\n");
	}
	//出队
	res = Outlist(S, search);
	if (res)
	{
		printf("出队成功，元素值为%d\n", search);
	}
	else
	{

		printf("出队失败\n");
	}
	res = Outlist(S, search);
	if (res)
	{
		printf("出队成功，元素值为%d\n", search);
	}
	else
	{

		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

08.队列的链式存储

#include <stdio.h>
#include <stdlib.h>
typedef int Elmpey;
typedef struct NumList
{
	Elmpey data;
	struct NumList* next;
}NumList;

typedef struct
{
	NumList* front;
	NumList* rear;
}LinkQu;
//初始化操作
void NewList(LinkQu& S)
{
	S.front = S.rear = (NumList*)malloc(sizeof(NumList));
	S.front->next = NULL;
}
//入队操作
void InList(LinkQu& S, Elmpey x)
{
	NumList* p = (NumList*)malloc(sizeof(NumList));
	p->data = x; p->next = NULL;
	S.rear->next = p;
	S.rear = p;
}
//出队操作
bool OutList(LinkQu& S, Elmpey& x)
{
	if (S.front == S.rear)
		return false;
	NumList* s = S.front->next;
	x = s->data;
	S.front->next = s->next;
	if (s == S.rear)
		S.front = S.rear;
	free(s);
	return true;
}
int main()
{
	LinkQu S;
	bool res;
	Elmpey ForIn;
	NewList(S);
	InList(S, 3);
	InList(S, 4);
	InList(S, 5);
	InList(S, 6);
	InList(S, 7);
	res = OutList(S, ForIn);
	if (res)
	{
		printf("出队成功，出队元素为%d", ForIn);
	}
	else
	{
		printf("出队失败了");

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

09.斐波那契数列

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int Fib(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);

}
int main()
{
	int num;
	while (scanf("%d", &num) != EOF)
	{
		printf("Fib(%d)=%d\n", num, Fib(num));

	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

10.二叉树的遍历

function.h

#define CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef char BiElemType;
typedef struct BiTNode {
	BiElemType c;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode, * BiTree;

typedef struct tag {
	BiTree p;
	struct tag* pnext;
}tag_t, * ptag_t;

//栈的相关数据结构
#define MaxSize 50
typedef BiTree ElemType;
typedef struct {
	ElemType data[MaxSize];
	int top;
}SqStack;
void InitStack(SqStack& S);
bool StackEmpty(SqStack& S);
bool Push(SqStack& S, ElemType x);
bool Pop(SqStack& S, ElemType& x);
bool GetTop(SqStack& S, ElemType& x);
//队列的相关数据结构
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;
typedef struct {
	LinkNode* front, * rear;
}LinkQueue;
void InitQueue(LinkQueue& Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue& Q, ElemType x);
bool DeQueue(LinkQueue& Q, ElemType& x);

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

queue.cpp

#include "function.h"
//代头结点的队列
void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next=NULL;
}

bool IsEmpty(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return true;
	else
		return false;
}

void EnQueue(LinkQueue &Q,ElemType x)
{
	LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));
	s->data=x;s->next=NULL;
	Q.rear->next=s;
	Q.rear=s;
}

bool DeQueue(LinkQueue &Q,ElemType &x)
{
	if(Q.front==Q.rear) return false;
	LinkNode *p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

stack.cpp

#include "function.h"


void InitStack(SqStack &S)
{
	S.top=-1;
}

bool StackEmpty(SqStack &S)
{
	if(S.top==-1)
		return true;
	else
		return false;
}
//入栈
bool Push(SqStack &S,ElemType x)
{
	if(S.top==MaxSize-1)
	{
		return false;
	}
	S.data[++S.top]=x;
	return true;
}
//出栈
bool Pop(SqStack &S,ElemType &x)
{
	if(-1==S.top)
		return false;
	x=S.data[S.top--];
	return true;
}
//读取栈顶元素
bool GetTop(SqStack &S,ElemType &x)
{
	if(-1==S.top)
		return false;
	x=S.data[S.top];
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

main.cpp

#include "function.h"

//递归实现
//abdhiejcfg
void preOrder(BiTree p)
{
	if(p!=NULL)
	{
		putchar(p->c);//等价于visit函数
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}
//中序遍历  hdibjeafcg
void InOrder(BiTree p)
{
	if(p!=NULL)
	{
		InOrder(p->lchild);
		putchar(p->c);
		InOrder(p->rchild);
	}
}
//hidjebfgca
void PostOrder(BiTree p)
{
	if(p!=NULL)
	{
		PostOrder(p->lchild);
		PostOrder(p->rchild);
		putchar(p->c);
	}
}
void InOrder2(BiTree T)
{
	SqStack S;
	InitStack(S);BiTree p=T;
	while(p||!StackEmpty(S))//逻辑或||
	{
		if(p)
		{
			Push(S,p);
			p=p->lchild;
		}else{
			Pop(S,p);putchar(p->c);
			p=p->rchild;
		}
	}
}
//层次遍历,广度优先遍历
void LevelOrder(BiTree T)
{
	LinkQueue Q;//定义队列
	InitQueue(Q);//初始化带头结点的队列
	BiTree p;//树指针
	EnQueue(Q,T);//树根入队
	while(!IsEmpty(Q))//判断是否为空
	{
		DeQueue(Q,p);
		putchar(p->c);
		if(p->lchild!=NULL)
			EnQueue(Q,p->lchild);
		if(p->rchild!=NULL)
			EnQueue(Q,p->rchild);
	}
}
#include "function.h"


void InitStack(SqStack& S)
{
	S.top = -1;
}

bool StackEmpty(SqStack& S)
{
	if (S.top == -1)
		return true;
	else
		return false;
}
//入栈
bool Push(SqStack& S, ElemType x)
{
	if (S.top == MaxSize - 1)
	{
		return false;
	}
	S.data[++S.top] = x;
	return true;
}
//出栈
bool Pop(SqStack& S, ElemType& x)
{
	if (-1 == S.top)
		return false;
	x = S.data[S.top--];
	return true;
}
//读取栈顶元素
bool GetTop(SqStack& S, ElemType& x)
{
	if (-1 == S.top)
		return false;
	x = S.data[S.top];
	return true;
}
int main()
{
	BiTree pnew;
	int i,j,pos;
	char c;
	BiTree tree=NULL;//树根
	ptag_t phead=NULL,ptail=NULL,listpnew,pcur;
	//abcdefghij

	while(scanf("%c",&c)!=EOF)
	{
		if(c=='\n')
		{
			break;
		}
		pnew=(BiTree)calloc(1,sizeof(BiTNode));
		pnew->c=c;
		listpnew=(ptag_t)calloc(1,sizeof(tag_t));
		listpnew->p=pnew;
		if(NULL==tree)
		{
			tree=pnew;//树的根
			phead=listpnew;//队列头
			ptail=listpnew;//队列尾
			pcur=listpnew;
			continue;
		}else{
			ptail->pnext=listpnew;//新结点放入链表，通过尾插法
			ptail=listpnew;//ptail指向队列尾部
		}//pcur始终指向要插入的结点的位置
		if(NULL==pcur->p->lchild)//如何把新结点放入树
		{
			pcur->p->lchild=pnew;//把新结点放到要插入结点的左边
		}else if(NULL==pcur->p->rchild)
		{
			pcur->p->rchild=pnew;//把新结点放到要插入结点的右边
			pcur=pcur->pnext;//左右都放了结点后，pcur指向队列的下一个
		}
	}
	printf("--------前序遍历----------\n");
	preOrder(tree);
	printf("\n--------中序遍历------------\n");
	InOrder(tree);
	printf("\n--------后序遍历------------\n");
	PostOrder(tree);
	printf("\n--------中序遍历非递归------\n");
	InOrder2(tree); 
	printf("\n--------层次遍历-----------\n");
	LevelOrder(tree);
	printf("\n");
	system("pause");
} 
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

11.二插排序树的创建

#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode
{
	KeyType key;
	struct BSTNode* lchild, * rchild;
}BSTNode, * Bitree;
//辅助函数
int  BST_Insert(Bitree& T, KeyType x)
{
	if (T == NULL)
	{
		T = (Bitree)malloc(sizeof(BSTNode));
		T->key = x;
		T->lchild = T->rchild = NULL;
		return 1;
	}
	else if (T->key == x)
		return 0;
	else if (T->key > x)
	{
		return BST_Insert(T->lchild, x);
	}
	else
	{
		return BST_Insert(T->rchild, x);
	}


}
//创建
void Creat_BST(Bitree& T, KeyType str[], int n)
{
	T = NULL;
	int i = 0;
	while (i < n)
	{
		BST_Insert(T, str[i]);
		i++;
	}

}
//删除操作
void DeleteNode(Bitree& root, KeyType x)
{
	if (root->key == NULL)//树根为空
		return;
	if (root->key > x)
	{
		DeleteNode(root->lchild, x);
	}
	else if (root->key < x)
	{

		DeleteNode(root->rchild, x);
	}
	else
	{
		if (root->lchild == NULL)
		{
			Bitree tempNode = root;
			root = root->rchild;
			free(tempNode);
		}
		else if (root->rchild == NULL)
		{
			Bitree tempNode = root;
			root = root->lchild;
			free(tempNode);
		}
		else
		{
			Bitree tempNode = root->lchild;
			if (tempNode->rchild != NULL)
			{
				tempNode = tempNode->rchild;
			}
			root->key = tempNode->key;
			DeleteNode(root->lchild, tempNode->key);
		}
	}
}
//查找
BSTNode* BST_Search(Bitree T, KeyType k, Bitree& p)
{
	p = NULL;
	while (T != NULL && k != T->key)
	{
		p = T;
		if (k < T->key)
			T = T->lchild;
		else
			T = T->rchild;
	}
	return T;

}
//中序遍历
int InOrder(Bitree& T)
{
	if (T != NULL)
	{
		InOrder(T->lchild);
		printf("%3d", T->key);
		InOrder(T->rchild);

	}
	return 1;
}
//主函数
int main()
{
	//定义
	Bitree T = NULL;
	Bitree parent;
	Bitree search;
	KeyType str[7] = { 54,20,66,40,28,79,58 };
	//创建
	Creat_BST(T, str, 7);
	//中序遍历
	InOrder(T);
	printf("\n");
	//查找
	search = BST_Search(T, 40, parent);
	if (search)
	{
		printf("查找成功，查找到的值=%d\n", search->key);

	}
	else
	{
		printf("查找失败\n");
	}
	//删除
	DeleteNode(T, 66);
	InOrder(T);
	printf("\n");

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

12.顺序查找和折半查找

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
//定义
typedef struct {
	ElemType* elem;
	int TableLen;

}SStable;
//生成随机数
void ST_lnit(SStable& ST, int x)
{
	ST.TableLen = x + 1;
	ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
	int i;
	srand(time(NULL));//随机数生成
	for (i = 0; i < ST.TableLen; i++)
	{
		ST.elem[i] = rand() % 100;
	}
}
//打印
void ST_print(SStable& ST)
{
	for (int i = 0; i < ST.TableLen; i++)
	{
		printf("%3d", ST.elem[i]);
	}
	printf("\n");
}
//查找
int Search_Seq(SStable ST, ElemType key)
{
	ST.elem[0] = key;//哨兵
	int i;
	for (i = ST.TableLen - 1; ST.elem[i] != key; --i);
	return i;
}
//比较规则
int compare(const void* left, const void* right)
{
	return *(ElemType*)left - *(ElemType*)right;
}
//二分查找
int Binary_Search(SStable ST, ElemType key)
{
	int low = 0, high = ST.TableLen - 1, mid;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (ST.elem[mid] == key)
			return mid;
		else if (ST.elem[mid] > key)
			high = mid + 1;
		else
			low = mid + 1;
	}
	return -1;
}
//主函数
int main()
{
	SStable ST;
	ElemType key;
	int pos;
	//生成随机数
	ST_lnit(ST, 10);
	ST_print(ST);
	//查找
	printf("请输入要搜索的key值\n");
	scanf("%d", &key);
	pos = Search_Seq(ST, key);
	if (key)
	{
		printf("查找成功，位置是%d\n", pos);
	}
	else
	{
		printf("查找失败");
	}
	//折半查找
	qsort(ST.elem, ST.TableLen, sizeof(ElemType), compare);
	ST_print(ST);
	printf("二分查找，请输入要搜索的key值\n");
	scanf("%d", &key);
	pos = Binary_Search(ST, key);
	if (pos != -1)
	{
		printf("查找成功，位置是%d\n", pos);
	}
	else
	{
		printf("查找失败\n", pos);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99