Visual C++ 6.0調試功能 圖解教程(3)--實例二
Posted on 2008-08-19 17:30 ∪∩BUG 閱讀(1851) 評論(2) 編輯 收藏 所屬分類: VC++/MFC學習筆記樹和二叉樹
-
實驗目的
1.熟悉二叉樹的二叉鏈表存儲結構;
2.掌握構造二叉樹的方法;
3.加深對二叉樹的遍歷的理解。
二.需求分析
本程序演示用C++編寫,完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結點個數.
輸入值的范圍:建立一棵二叉時,要求結點的的左右孩子為空時輸入0代替.所有輸入值必須為整形.輸入的結點個數:若為單邊二叉樹(全只有左結點或全只有右結點)則為任意個數;若非單邊二叉則要求結點最多的層個數不得超過MAXSIZE的值.
輸出形式:輸出時如果結點的左右指針這空則以" #"代替輸出.
程序所能完成的功能:程序能完成按先序遍歷生成二叉樹,先序遍歷打印輸出二叉樹, 后序遍歷打印輸出二叉樹, 中序遍歷打印輸出二叉樹, 層序遍歷打印輸出二叉樹, 先序遍歷方法交換左右子樹,求樹的高度,求樹的葉子結點個數.操作.
測試數據
A建立二叉樹中輸入1230000 生成一棵樹123####
B交換左右子樹得到一棵二叉樹1#2#3##
C按層序遍歷樹得到一棵二叉樹1#2#3##
D求二叉樹的高度得到高度3
E求葉子結點個數得到個數1
三.設計概要
(1)為了實現上述程序的功能,需要定義二叉樹的抽象數據類型:
ADT BiTree is{
數據對象:D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
數據關系:R={<ai,ai+1>|ai,ai+1 ∈D}
基本操作:
creat()
操作結果:建立一棵二叉樹
preorder()
初始條件:二叉樹已經存在
操作結果:先序遍歷顯示二叉樹
preordertswap()
初始條件: 二叉樹已經存在
操作結果:交換二叉樹的左右子樹
theight()
初始條件: 二叉樹已經存在
操作結果:輸出二叉樹的高度
tleaves()
初始條件:
操作結果:輸出二叉樹的葉子結點個數
levelorder()
初始條件: 二叉樹已經存在
操作結果:層序遍歷顯示二叉樹
}ADT BiTree
(2) 本程序包含兩個類和一個結構體類型
A基類:隊列類SeQueue有5個函數
1.構造函數 SeQueue()
2.析構函數 ~SeQueue()
3.進隊函數 AddQ(NodeType x)
4.出隊函數 DelQ()
5.判斷非空函數 IsEmpty()
B派生類:二叉樹類BiTree有20個函數
1主函數 main()
2. 構造函數 BiTree()
3. 析構函數 ~BiTree()
4. 建立樹函數 creat0()
5. 先序遍歷函數 void preorder()
6. 中序遍歷函數 inorder()
7. 后序遍歷函數 postorder()
8.層序遍歷函數 levelorder()
9. 交換左右子樹函數 preordertswap()
10. 求二叉樹高度函數 theight()
11. 求二叉樹葉子結點個數函數 tleaves()
12. 建立二叉樹遞歸算法函數 *creat()
13. 先序遍歷遞歸算法函數 preorder(NodeType *p)
14. 中序遍歷遞歸算法函數 inorder(NodeType *p)
15. 后序遍歷遞歸算法函數 postorder(NodeType *p)
16. 按層遍歷算法函數 levelorder(NodeType *p)
17. 先序遍歷方法交換左右子樹函數 preorderswap(NodeType *p)
18. 求二叉樹高度遞歸算法函數 height(NodeType *p)
19. 求二叉樹葉子結點個數的遞歸算法函數 leaves(NodeType *p)
20. 刪除二叉樹所有結點函數 destroy(NodeType* &p)
C結構體類型NodeType
(3)本程序的三個文件
1.頭文件BiTree.h
2.源文件 Queue.cpp
BiTree.cpp
(4)函數之間的關系
四.詳細設計

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

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

五.心得:
這次實驗不僅能鞏固理解遞歸的方法,另一方面很能考驗運用指針的能力,還有就是數據類型要使用得當.從levelorder(NodeType *p)函數來看,首先, DelQ()的返回類型要與BiTree二叉樹結點指針的類型一至.其次,在遞歸過程中,傳入AddQ(NodeType x)是整個結點的內容而不是一個指針.值得討論的是,在定義存儲隊列的數組時如何節省存儲空間?因為輸入的結點個數:若為單邊二叉樹(全只有左結點或全只有右結點)則為任意個數(實驗上這時只需要兩個存儲空間);若非單邊二叉則要求結點最多的層個數不得超過MAXSIZE的值.后者時MAXSIZE的值(由性質2得)應該為2(h-1) (h為樹的高度).這一點如何實現呢?BiTree類是SeQueue類的子類,height()函數是BiTree類的函數,如果能把高度傳入SeQueue類的構造函數就可以通過一個for()語句來求得一個合適的值用以初始化MAXSIZE.那么就大大的節省了內存空間,并且還能實現輸入節點的個數為任意的.但把高度傳入SeQueue類的構造函數如何實現?還有其他要考慮的問題,我在今后的學習中深入了解.
六.使用說明
程序名為No4.exe運行環境為DOS,執行后顯示:
在" 請輸入您的選擇(0,1,2,3,4,5,6):"后輸入數字選擇執行的功能.
測試結果:
1)選擇1.后輸入1240003500600.(如右圖的一棵二叉樹)
2)選擇4得
3)選擇5得
4)選擇2得
5)選擇3得
6)選擇6或輸入非"0,1,2,3,4,5,6"的數字
七.調試過程
本程序主要對按層序遍歷操作功能進行調試.用Visual Studio 2008演示.首先把BiTree.h中的" #define MAXSIZE 30"改成" #define MAXSIZE 4",目的是從Visual Studio 2008的監視(Watch)窗口中得到更好的觀察效果.
- 將光標移置BiTree.cpp文件的void BiTree::levelorder(NodeType *p)和第一條語句處Ctrl+F10開始調試
- 選擇1.后輸入1240003500600.(如右圖的一棵二叉樹)
再選擇3.
-
這時Debugger仍停留在void BiTree::levelorder(NodeType *p)的第一條語句上.可以從自動監視窗口中看到已經建立了一棵二叉樹,指針P指向二叉樹的根結點.
-
在監視窗口1中輸入變量名:q,t進行觀察,F10單步調試,這時Debugger停留在 SeQueue q; 語句處
可以在監視1窗口中看到對象q的指針t都未合法初始化.
-
斷續F10單步調試兩步,這時Debugger停留在if(p)語句處,如圖:
在監視1窗口輸入!p進行觀察,這時!p值為0,即if(p)判斷語句值為真.
可以進入f(p)執行,F10斷續,當Debugger停留在q.AddQ(*p)語句時可以從調用堆棧窗口中看到現在調用的函數為F11步入SeQueue類的AddQ(*p)函數.
-
這進Debugger停留在AddQ(*p)函數的第一條語句上.同可以從調用堆棧窗口中看到現在調用的函數為AddQ(*p)
在監視2窗口中輸入rear, elem[rear]進行觀察.同時在自動窗口中可以看到變量X已經指向二叉樹的根結點.
-
斷續F10真到AddQ(NodeType x)結束語句處,可以從監視2窗口看到根結點已經入隊
-
F10后可以看到調用堆棧窗口中當前調用的是levelorder(NodeType *p)函數,同時在監視1窗口中輸入!q.IsEmpty()觀察到值為true,即可以進入while()控制語句執行.
F10單步至 t = &(q.DelQ())處,并F11步入q.DelQ(),這時Debugger停留在DelQ()的第一條語句上,可以從調用堆棧窗口中看到當前調用的是DelQ()函數.
-
在監視3窗口中輸入q進行觀察.斷續F10到Debugger停留在DelQ()函數的return q語句時可以從監視窗口3中看到根結點已經出隊
同時在自動窗口中可以看到從DelQ()函數返回了出隊結點并賦給了指針t
-
F10單步調試直到Debugger停留在levelorder(NodeType *p)函數的cout << t->data語句上,這時可以在調用堆棧窗口中看到當前調用的是levelorder(NodeType *p)函數,在監視窗口1中輸入t->date進行觀察,已經取得根結點數據域的值
-
F10單步調試一步可以在DOS窗口中看到已經輸出根結點
- Shift+F5退出調試,完成調試演示.