定义链表应该加什么头文件

C的话，标准的stdio.h和stdlib.h就可以。

C++用#include。

<iostream>以及命名空间using。

namespace。

typedef structSingleNode

ElemType data

structSingleNode *next

SingleLinkedList,*Linklist

//定义单链表结点的结构体

void ListInitialize(SingleLinkedList **head)

if((*head=(SingleLikedList *)malloc(sizeof(SingleLikedList)))==NULL) exit(1)    //取数据元素

//单链表初始化

int ListLength(SingleLikedList *head)

while(p->next!=NULL)

p=p->next

链接存储方法

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）。

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）。

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

问题的描述

1.1基本功能

1、创建二叉树（10’）

可以使用先序遍历输入，无节点的可以使用#表示。

例如下图可以输入6423####51##7##。这里前面2个#表示节点3左右孩子节点都为空，第3个#表示节点2右孩子为空，第4个#表示节点4右孩子为空，1和7后面的2个#分别代表节点1和7的左右孩子节点都为空。

也可以自己选择其他方式输入，但要在readme文件和实验报告说清楚。

2、遍历二叉树（先序、中序、后序、层序遍历）(20’)

前序遍历：6423517

中序遍历：3246157

后序遍历：3241756

层序遍历：6452173

3、二叉树的计算（二叉树的结点数、叶子数、高度、宽度等）(20’)

结点数：7

叶子数：3

高度：4

宽度：3

4、 二叉树的处理（复制、销毁）(20’)

复制要创建一个新的二叉树，对于原二叉树和复制的二叉树之间销毁 *** 作不能互相影响。

1.2健壮性

对于创建的二叉树为空的情况，要能程序要能正常运行并识别。（5分）

对于空树，其他功能要可以识别、输出相应信息，并且程序不能异常终止。（5分）

1.3 规范性

代码注释

程序模块化

人机交互友好

2.算法的描述

2.1数据结构的描述

程序中应用到的主要数据结构是二叉树（二叉链表）。

主要变量说明：

变量

类型

说明

Node、BiTNode

结构体

二叉树结点的结构体

*BiTree

二叉树结点指针

二叉树结点的指针

data

可变（由宏定义TElemType确定，示例中为char）

二叉树结点中的数据域

*lchild

二叉树结点指针

结点的左孩子

*rchild

二叉树结点指针

结点的右孩子

TElemType

宏定义

二叉树节点数据域的类型

2.2程序结构的描述

程序主要包含Noah_BiTree.h头文件和main.cpp主文件，其中Noah_BiTree.h是二叉链表数据结构的实现代码头文件，N，main.cpp中主要实现菜单和功能界面的交互以及头文件中函数的调用。其具体结构如下图所示。

3.调试分析

调试功能一：Create a binary tree and show the tree structure

创建二叉树并显示树的结构

测试数据选择:

6423####51##7##

124##5##36##7##

#

1234######

问题及解决方法：

无

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

创建一个二叉树，显示前序、中序后序和层次遍历。

测试数据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无

调试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

创建一个二叉树，计算节点的数量，叶，高度和宽度

测试数据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

创建一个二叉树，复制它，销毁原来的树，并显示新的树

测试数据选择:

6423####51##7##

124##5##36##7##

1234######

问题及解决方法：

无

4.算法的时空分析

(1) CreateBiTree_withhint(BiTree &T)

时间复杂度：O(n)

空间复杂度：O(n)

(2) preorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(3) inorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(4) postorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(5) levelorder(BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(6) NumofNode (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiHight (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) Numofleaves (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) BiWidth (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) CopyBitree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

(7) DestroyBiTree (BiTree T)

时间复杂度：O(n)

空间复杂度：O(n)

5.测试结果及分析

测试功能一：Create a binary tree and show the tree structure

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

#

√

1234######

√

调试功能二：Create a binary tree and show show the preoeder, inorder, postorder and levelorder

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

测试功能三：Create a binary tree and calculate the number of nodes, leaves, height and width

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

调试功能四：Create a binary tree, copy it, destory the original one and show the new tree

测试用例

结果

分析

6423####51##7##

√

124##5##36##7##

√

1234######

√

6.实验体会和收获

掌握二叉树的递归特性

掌握二叉树的常用存储结构----二叉链表

掌握二叉树的创建、遍历等基本运算

了解递归函数的执行过程，学会编写递归程序

代码

Noah_BiTree.h

1. #ifndef __NOAH_BITREE_H__

2. #define __NOAH_BITREE_H__

3. #include <stdlib.h>

4. #include <iostream>

5. #include <cstring>

6. #include <queue>

7. #include <string>

8. #include <iostream>

9. using namespace std

10. #define TElemType char

11. /*

12. 1. 对于创建的二叉树为空的情况，要能程序要能正常运行并识别。（5分）

13. 2. 对于空树，其他功能要可以识别、输出相应信息，并且程序不能异常终止。（5分）

14. */

15. typedef struct Node

16. {

17. TElemType data

18. struct Node *lchild,*rchild//左右孩子指针

19. }BiTNode,*BiTree

20.

21. void CreateBiTree_Preorder(BiTree &T){

22. //使用先序遍历的输入创建一个二叉树，例如6423####51##7##

23. char x

24. cin>>x

25. if(x==' '||x=='#'){

26. T = NULL

27. }

28. else {

29. T = (BiTree)malloc(sizeof(BiTNode))

30. if(x !='#')

31. T->data = (TElemType)x

32. CreateBiTree_Preorder(T->lchild)

33. CreateBiTree_Preorder(T->rchild)

34. }

35. }

36.

37. void CreateBiTree_withhint(BiTree &T){

38. //向屏幕输出初始化二叉树的提示信息，调用CreateBiTree_Preorder()

39. cout<<"Please input a preorder sequence of a binary tree(example:6423####51##7##):"<<endl

40. CreateBiTree_Preorder(T)

41. if(T==NULL) cout<<"Input is an empty BiTree."<<endl

42. }

43.

44. int isBiTreeEmpty(BiTree T){

45. //判断二叉树是否为空，为空返回1，不为空返回0

46. if((T->data == NULL &&T->lchild &&T->rchild)||T==NULL)

47. return 1

48. else

49. return 0

50. }

51.

52. void preorder(BiTree T){

53. //使用先序遍历输出二叉树

54. if(T){

55. cout<<T->data

56. preorder(T->lchild)

57. preorder(T->rchild)

58. }

59. else

60. return

61. //cout<<"Empty BiTree."<<endl

62. }

63.

64. void inorder(BiTree T){

65. //使用中序遍历输出二叉树

66. if(T){

67. inorder(T->lchild)

68. cout<<T->data

69. inorder(T->rchild)

70. }

71. }

72.

73. void postorder(BiTree T){

74. //使用后序遍历输出二叉树

75. if(T){

76. postorder(T->lchild)

77. postorder(T->rchild)

78. cout<<T->data

79. }

80. }

81.

82. void leverorder(BiTree T){

83. //使用层次遍历输出二叉树

84. if(T){

85. queue<BiTree>q

86. q.push(T)

87. while(!q.empty()){//当队列非空时，还有没有遍历的parent结点

88. BiTree temp = q.front()

89. q.pop()

90. cout<<temp->data

91. if(temp->lchild!=NULL) q.push(temp->lchild)

92. if(temp->rchild!=NULL) q.push(temp->rchild)

93. }

94. }

95. }

96.

97. int NumofNode(BiTree T){

98. //返回二叉树节点数

99. if(!T) return 0

100. else return 1 + NumofNode(T->lchild) + NumofNode(T->rchild)

101. }

102.

103. int Numofleaves(BiTree T){

104. //返回二叉树叶子数

105. int num = 0

106. if(!T) return 0

107. else{

108. if(T->lchild!=NULL) num = num + Numofleaves(T->lchild)

109. if(T->rchild!=NULL) num = num + Numofleaves(T->rchild)

110. if(T->lchild==NULL &&T->rchild==NULL) return 1

111. }

112. return num

113. }

114.

115. int BiHight(BiTree T){

116. //返回二叉树高度

117. if(!T) return 0

118. else{

119. int lefthight = BiHight(T->lchild)

120. int righthight = BiHight(T->rchild)

121. return (lefthight>=righthight)?lefthight+1:righthight+1

122. }

123. }

124.

125. int BiWidth(BiTree T){

126. //返回二叉树宽度

127. if (isBiTreeEmpty(T)) {

128. return 0

129. }

130. queue<BiTree>q

131. int maxWidth = 1

132. q.push(T)

133.

134. while (1) {

135. int len = q.size()

136. if (!len) {

137. break

138. }

139. while (len--) {

140.

141. BiTree temp = q.front()

142. q.pop()

143. if (temp->lchild) {

144. q.push(temp->lchild)

145. }

146. if (temp->rchild) {

147. q.push(temp->rchild)

148. }

149. }

150. maxWidth = max(maxWidth, (int) q.size())

151. }

152. return maxWidth

153. }

154.

155. void CopyBitree(BiTree source,BiTree &target){

156. //将source中的二叉树复制给target，原二叉树和复制的二叉树之间销毁 *** 作不能互相影响

157. if(!source){

158. target = NULL

159. return

160. }

161.

162. else{

163. target = (BiTNode *)malloc(sizeof(BiTNode))

164. target->data = (TElemType)source->data

165. CopyBitree(source->lchild,target->lchild)

166. CopyBitree(source->rchild,target->rchild)

167. }

168. }

169.

170.

171. void DestroyBiTree(BiTree &T){

172. //销毁二叉树并释放内存

173. if(isBiTreeEmpty(T)){

174. cout<<"DestroyBiTree succeed."<<endl

175. return

176. }

177. else{

178. if(T->lchild!=NULL) DestroyBiTree(T->lchild)

179. if(T->rchild!=NULL) DestroyBiTree(T->rchild)

180. free(T)

181. T = NULL

182. }

183. }

184.

185. void DisplayBitree_control(BiTree n, bool left, string const&indent){

186. //DisplayBitree()函数的中间控制函数

187. if (n->rchild)

188. {

189. DisplayBitree_control(n->rchild, false, indent + (left ? "| " : " "))

190. }

191. cout <<indent

192. cout <<(left ? '\\' : '/')

193. cout <<"-----"

194. cout <<n->data <<endl

195. if (n->lchild)

196. {

197. DisplayBitree_control(n->lchild, true, indent + (left ? " " : "| "))

198. }

199. }

200. void DisplayBitree(BiTree root){

201. //以树形结构形式输出二叉树

202. if(!root){

203. cout<<"An empty tree."<<endl

204. return

205. }

206. if (root->rchild)

207. {

208. DisplayBitree_control(root->rchild, false, "")

209. }

210. cout <<root->data <<endl

211. if (root->lchild)

212. {

213. DisplayBitree_control(root->lchild, true, "")

214. }

215. }

216. #endif

登录后复制

main.cpp

1. #include <stdio.h>

2. #include <string.h>

3. #include <stdlib.h>

4. #include <iostream>

5. using namespace std

6. #include "Noah_BiTree.h"

7. void Menue_gui()

8. void func1()

9. void func2()

10. void func3()

11. void func4()

12.

13. int main()

14. {

15. while(1){

16. Menue_gui()

17. int func

18. scanf("%d",&func)

19. switch(func){

20. case 0:

21. exit(0)

22. case 1:

23. func1()break

24. case 2:

25. func2()break

26. case 3:

27. func3()break

28. case 4:

29. func4()break

30. default:

31. printf("Input error! Please try again!")

32. }

33. printf("\n")

34. system("pause")

35. }

36. return 0

37. }

38.

39. //主界面

40. void Menue_gui(){

41. system("cls")

42. printf("**********************************Binary Tree calcuator**************************************\n")

43. printf("*********************************************************************************************\n")

44. printf("Menue:\n")

45. printf("\nExit this program------------------------------------------------------------------0.\n")

46. printf("\nCreate a binary tree and show the tree structure-----------------------------------1.\n")

47. printf("\nCreate a binary tree and show show the preoeder, inorder, postorder and levelorder-2.\n")

48. printf("\nCreate a binary tree and calculate the number of nodes, leaves, height and width---3.\n")

49. printf("\nCreate a binary tree, copy it, destory the original one and show the new tree------4.\n")

50. printf("\n**********************************************************************************************\n")

51. printf("Choose the function you want to use(input number):\n")

52. }

53.

54. void func1(){

55. system("cls")

56. printf("-----ENTER FUNCTION : Create a binary tree and show the tree structure--1.-----\n")

57. BiTree T1

58. CreateBiTree_withhint(T1)

59. DisplayBitree(T1)

60. }

61. void func2(){

62. system("cls")

63. printf("-----ENTER FUNCTION : Create a binary tree and show show the preoeder, inorder, postorder and levelorder--2.-----\n")

64. BiTree T1

65. CreateBiTree_withhint(T1)

66. cout<<endl<<"The tree form of the Binary Tree is:"<<endl

67. DisplayBitree(T1)

68. cout<<endl<<"The preorder of the Binary Tree is:"<<endl

69. preorder(T1)

70. cout<<endl<<"The inorder of the Binary Tree is:"<<endl

71. inorder(T1)

72. cout<<endl<<"The postorder of the Binary Tree is:"<<endl

73. postorder(T1)

74. cout<<endl<<"The levelorder of the Binary Tree is:"<<endl

75. leverorder(T1)

76. }

77. void func3(){

78. system("cls")

79. printf("-----ENTER FUNCTION : Create a binary tree and calculate the number of nodes, leaves, height and width--3.-----\n")

80. BiTree T1

81. CreateBiTree_withhint(T1)

82. cout<<endl<<"The tree form of the Binary Tree is:"<<endl

83. DisplayBitree(T1)

84. cout<<endl<<"The number of nodes is:"<<NumofNode(T1)<<endl

85. cout<<endl<<"The number of leaves is:"<<Numofleaves(T1)<<endl

86. cout<<endl<<"The height is:"<<BiHight(T1)<<endl

87. cout<<endl<<"The width is:"<<BiWidth(T1)<<endl

88. }

89. void func4(){

90. system("cls")

91. printf("-----ENTER FUNCTION : Create a binary tree, copy it, destory the original one and show the new tree--4.-----\n")

92. BiTree T1

93. CreateBiTree_withhint(T1)

94. cout<<endl<<"The tree form of the [ORIGINAL] Binary Tree is:"<<endl

95. DisplayBitree(T1)

96. BiTree T2

97. CopyBitree(T1,T2)//复制T1到T2

98. DestroyBiTree(T1)//销毁T1

99. cout<<endl<<"After destroy, the tree form of the [ORIGINAL] Binary Tree is:"<<endl

100. DisplayBitree(T1)

101. cout<<endl<<"The tree form of the [NEW] Binary Tree is:"<<endl

102. DisplayBitree(T2)

103. }

登录后复制

关注查看全文

数据结构

链表

算法

细跟高跟凉鞋

精选推荐

广告

---