数据结构第四次上机代码

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 6k 阅读时长 ≈ 5 分钟
二叉树 图的一点点
报告

二叉树

丰富了许多

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
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
#define ERROR -1
typedef char DataType;
typedef struct TreeNode
{
	DataType elem;
	struct TreeNode* rchild;
	struct TreeNode* lchild;
}TreeNode, *PTREE;
//先序创建
void CreatTree(PTREE *Root) {
	char val = 0;//用于下面存放数据
	val = getchar();//输入数据值
					//如果输入'*'，则指向为空
	if (val == '*' || val == '#' || val == '.')
		(*Root) = NULL;
	//如果输入非'*'，则给数据域赋值
	else {
		(*Root) = (PTREE)malloc(sizeof(TreeNode));//申请内存空间
		if ((*Root) == NULL) {
			printf("创建结点失败，无法分配可用内存...");
			exit(-1);
		}
		else {
			(*Root)->elem = val;//给结点数据域赋值
			CreatTree(&(*Root)->lchild);
			CreatTree(&(*Root)->rchild);
		}
	}
}
//前序遍历
void PreOrderTraverse (PTREE Root) 
{
	if (Root == NULL)
		return;
	else {
		putchar(Root->elem);
		PreOrderTraverse(Root->lchild);
		PreOrderTraverse(Root->rchild);
	}
}
//中序
void InOrderTraverse(PTREE Root) {
	if (Root != NULL) {
		InOrderTraverse(Root->lchild);
		putchar(Root->elem);
		InOrderTraverse(Root->rchild);
	}
}
//后序
void PostOrderTraverse(PTREE Root) {
	if (Root != NULL) {
		PostOrderTraverse(Root->lchild);
		PostOrderTraverse(Root->rchild);
		putchar(Root->elem);
	}
}
//深度
int Depth(PTREE Root) {
	if (Root == NULL) {
		return 0;
	}
	else {
		return (Depth(Root->lchild)>Depth(Root->rchild) ? Depth(Root->lchild) : Depth(Root->rchild )) + 1;
	}
} 
//结点个数01*49**8**25**6** ABD***CE**FG*** 01*49**8**25**6*37***
int GetNodeNum(PTREE Tree)
{
	if (NULL == Tree)
	{
		return 0;
	}
	else
	{
		return GetNodeNum(Tree->lchild) + GetNodeNum(Tree->rchild) + 1;
	}
}
//叶子结点个数
int GetLeafNum(PTREE Tree)
{
	if (Tree == NULL)
		return 0;
	if (Tree->lchild == NULL&&Tree->rchild == NULL)
		return 1;
	return GetLeafNum(Tree->lchild) + GetLeafNum(Tree->rchild);
}
//度为1结点个数
int GetNodde1Num(PTREE Tree)
{
	if (Tree == NULL)

		return 0;

	if (Tree->lchild == NULL&&Tree->rchild != NULL || Tree->rchild == NULL&&Tree->lchild != NULL)

		return 1 + GetNodde1Num(Tree->lchild) + GetNodde1Num(Tree->rchild);
	return GetNodde1Num(Tree->lchild) + GetNodde1Num(Tree->rchild);
}
//度为2结点个数
int GetNodde2Num(PTREE Tree)
{
	if (Tree == NULL)
		return 0;
	if (Tree->lchild != NULL&&Tree->rchild != NULL)
		return 1 + GetNodde2Num(Tree->lchild) + GetNodde2Num(Tree->rchild);
	return GetNodde2Num(Tree->lchild) + GetNodde2Num(Tree->rchild);
}
void myprintf(char* c,int n)
{
	std::cout <<c<< "求得结果为\t" << n << std::endl;
}
int main(void)
{
	PTREE root=NULL;
	char ch = NULL;
	printf("菜单：\n"
		"0 先序建表\n"
		"1 前序遍历\n"
		"2 中序遍历\n"
		"3 后序遍历\n"
		"4 树的深度\n"
		"5 递归所有结点\n"
		"6 等式求所有结点\n"
		"7 递归求所有叶子结点\n"
		"8 性质求所有叶子结点\n"
		"9 递归求所有度为1的结点\n"
		"a 等式求所有度为1的结点\n"
		"b 递归求所有度为2的结点\n"
		"c 性质求所有度为2的结点\n");
	while (true)
	{
		std::cin >> ch;
		switch (ch)
		{
		case '0':getchar();/*过滤回车符*/ CreatTree(&root); break;
		case '1':printf("1 前序遍历结果： "); PreOrderTraverse(root); printf("\n"); break;//前序遍历
		case '2':printf("2 中序遍历结果： "); InOrderTraverse(root);  printf("\n"); break;
		case '3':printf("3 后序遍历结果： "); PostOrderTraverse(root); printf("\n"); break;
		case '4':myprintf("4 树的深度 ",Depth(root)); break;//深度
		case '5':myprintf("5 递归所有结点 ",GetNodeNum(root)); break;
		case '6':myprintf("6 等式求所有结点 ",GetLeafNum(root) + GetNodde2Num(root) + GetNodde1Num(root)); break;
		case '7':myprintf("7 递归求所有叶子结点 ",GetLeafNum(root)); break;
		case '8':myprintf("8 性质求所有叶子结点 ",GetNodde2Num(root) + 1); break;
		case '9':myprintf("9 递归求所有度为1的结点 ",GetNodde1Num(root)); break;
		case 'a':myprintf("a 等式求所有度为1的结点 ",GetNodeNum(root) - GetLeafNum(root) - GetNodde2Num(root)); break;
		case 'b':myprintf("b 递归求所有度为2的结点 ",GetNodde2Num(root)); break;
		case 'c':myprintf("c 性质求所有度为2的结点 ",GetLeafNum(root) - 1); break;
		case '\n':case '\t':break;
		default:system("pause");return 0;break;
		}
	}
}

图

储存

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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
typedef char VerTexType;
typedef int ArcType;
#define MAX_VALUE INT_MAX
#define MAX_NUM 100
typedef struct matrix
{
	VerTexType vexs[MAX_NUM];//节点
	ArcType arcs[MAX_NUM][MAX_NUM];//邻接矩阵
	int vexnum, arcnum;//节点数,边数
} Graph;
//寻找索引
int LocateVex(Graph g, char c)
{
	for (int i = 0; i <g.vexnum; i++)
	{
		if (c == g.vexs[i])
		{
			return i;
		}
	}
	return -1;
}
//创建无向图
void g_create(Graph * g)
{
	std::cout <<"输入节点数和边数"<< std::endl;
	std::cin >> g->vexnum >> g->arcnum;
	std::cout <<"输入顶点"<< std::endl;
	for (int i = 0; i < g->vexnum; i++)
	{
		std::cin >> g->vexs[i];
	}
	memset(g->arcs, 0, sizeof(g->arcs));//初始化矩阵
	char v1=NULL, v2 = NULL;
	int k = 0, l = 0;
	std::cout <<"输入边"<< std::endl;
	for (int i = 0; i < g->arcnum; i++)
	{
		std::cin >> v1 >> v2;
		k = LocateVex(*g, v1);
		l = LocateVex(*g, v2);
		g->arcs[k][l] = 1;
		g->arcs[l][k] = g->arcs[k][l];
	}
}
//打印邻接矩阵
void myprintf(Graph g)
{
	std::cout << "邻接矩阵为" << std::endl;
	for (int i = 0; i < g.vexnum; i++)
	{
		for (int j = 0; j < g.vexnum; j++)
		{
			std::cout << g.arcs[i][j] << "\t";
		}
		std::cout << std::endl;
	}
}

int main(void)
{
	Graph g;
	g_create(&g);
	myprintf(g);
	system("pause");
}