Data Structure and Algorithms Using C++ E-Book

Sachi Nandan Mohanty

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch
• Veröffentlichungsjahr: 2021

Seitenzahl: 253

Beschreibung

Everyone knows that programming plays a vital role as a solution to automate and execute a task in a proper manner. Irrespective of mathematical problems, the skills of programming are necessary to solve any type of problems that may be correlated to solve real life problems efficiently and effectively. This book is intended to flow from the basic concepts of C++ to technicalities of the programming language, its approach and debugging. The chapters of the book flow with the formulation of the problem, it's designing, finding the step-by-step solution procedure along with its compilation, debugging and execution with the output. Keeping in mind the learner's sentiments and requirements, the exemplary programs are narrated with a simple approach so that it can lead to creation of good programs that not only executes properly to give the output, but also enables the learners to incorporate programming skills in them. The style of writing a program using a programming language is also emphasized by introducing the inclusion of comments wherever necessary to encourage writing more readable and well commented programs. As practice makes perfect, each chapter is also enriched with practice exercise questions so as to build the confidence of writing the programs for learners. The book is a complete and all-inclusive handbook of C++ that covers all that a learner as a beginner would expect, as well as complete enough to go ahead with advanced programming. This book will provide a fundamental idea about the concepts of data structures and associated algorithms. By going through the book, the reader will be able to understand about the different types of algorithms and at which situation and what type of algorithms will be applicable.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

Preface

1 Introduction to Data Structure

1.1 Definition and Use of Data Structure

1.2 Types of Data Structure

1.3 Algorithm

1.4 Complexity of an Algorithm

1.5 Efficiency of an Algorithm

1.6 Asymptotic Notations

1.7 How to Determine Complexities

1.8 Questions

2 Review of Concepts of ‘C++’

2.1 Array

2.2 Function

2.3 Pointer

2.4 Structure

2.5 Questions

3 Sparse Matrix

3.1 What is Sparse Matrix

3.2 Sparse Matrix Representations

3.3 Algorithm to Represent the Sparse Matrix

3.4 Programs Related to Sparse Matrix

3.5 Why to Use Sparse Matrix Instead of Simple Matrix?

3.6 Drawbacks of Sparse Matrix

3.7 Sparse Matrix and Machine Learning

3.8 Questions

4 Concepts of Class

4.1 Introduction to CLASS

4.2 Access Specifiers in C++

4.3 Declaration of Class

4.4 Some Manipulator Used In C++

4.5 Defining the Member Functions Outside of the Class

4.6 Array of Objects

4.7 Pointer to Object

4.8 Inline Member Function

4.9 Friend Function

4.10 Static Data Member and Member Functions

4.11 Constructor and Destructor

4.12 Dynamic Memory Allocation

4.13 This Pointer

4.14 Class Within Class

4.15 Questions

5 Stack

5.1 STACK

5.2 Operations Performed With STACK

5.3 ALGORITHMS

5.4 Applications of STACK

5.5 Programming Implementations of STACK

5.6 Questions

6 Queue

6.1 Queue

6.2 Types of Queue

6.3 Linear Queue

6.4 Circular Queue

6.5 Double Ended Queue

6.6 Priority Queue

6.7 Programs

6.8 Questions

7 Linked List

7.1 Why Use Linked List?

7.2 Types of Link List

7.3 Single Link List

7.4 Programs Related to Single Linked List

7.5 Double Link List

7.6 Programs on Double Linked List

7.7 Header Linked List

7.8 Circular Linked List

7.9 Application of Linked List

7.10 Garbage Collection and Compaction

7.11 Questions

8 TREE

8.1 Tree Terminologies

8.2 Binary Tree

8.3 Representation of Binary Tree

8.4 Operations Performed With the Binary Tree

8.5 Traversing With Tree

8.6 Conversion of a Tree From Inorder and Preorder

8.7 Types of Binary Tree

8.8 Expression Tree

8.9 Binary Search Tree

8.10 Height Balanced Tree (AVL Tree)

8.11 Threaded Binary Tree

8.12 Heap Tree

8.13 Huffman Tree

8.14 Decision Tree

8.15 B-Tree

8.16 B + Tree

8.17 General Tree

8.18 Red–Black Tree

8.19 Questions

9 Graph

9.1 Graph Terminologies

9.2 Representation of Graph

9.3 Traversal of Graph

9.4 Spanning Tree

9.5 Single Source Shortest Path

9.6 All Pair Shortest Path

9.7 Topological Sorting

9.8 Questions

10 Searching and Sorting

10.1 Linear Search

10.2 Binary Search

10.3 Bubble Sort

10.4 Selection Sort

10.5 Insertion Sort

10.6 Merge Sort

10.7 Quick Sort

10.8 Radix Sort

10.9 Heap Sort

10.10 Questions

11 Hashing

11.1 Hash Functions

11.2 Collisions

11.3 Collision Resolution Methods

11.4 Clustering

11.5 Questions

Index

End User License Agreement

Guide

Cover

Table of Contents

Title page

Copyright

Preface

Begin Reading

Index

End User License Agreement

Pages

v

ii

iii

iv

xi

1

2

3

4

5

6

7

8

9

10

11

12

13

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

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

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

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

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

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

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

391

392

393

394

395

397

398

399

400

401

Scrivener Publishing100 Cummings Center, Suite 541JBeverly, MA 01915-6106

Publishers at ScrivenerMartin Scrivener ([email protected])Phillip Carmical ([email protected])

Data Structure and Algorithms Using C++

A Practical Implementation

Edited by

Sachi Nandan Mohanty

ICFAI Foundation For Higher Education, Hyderabad, India

and

Pabitra Kumar Tripathy

Kalam Institute of Technology, Berhampur, India

This edition first published 2021 by John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA and Scrivener Publishing LLC, 100 Cummings Center, Suite 541J, Beverly, MA 01915, USA © 2021 Scrivener Publishing LLC

For more information about Scrivener publications please visit www.scrivenerpublishing.com.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

Wiley Global Headquarters

111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials, or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read.

Library of Congress Cataloging-in-Publication Data

ISBN 978-1-119-75054-3

Cover image: Pixabay.Com

Cover design by Russell Richardson

Set in size of 11pt and Minion Pro by Manila Typesetting Company, Makati, Philippines

Printed in the USA

10 9 8 7 6 5 4 3 2 1

Preface

Welcome to the first edition of Data Structures Using and Algorithms C++. A data structure is the logical or mathematical arrangement of data in memory. To be effective, data has to be organized in a manner that adds to the efficiency of an algorithm and also describe the relationships between these data items and the operations that can be performed on these items. The choice of appropriate data structures and algorithms forms the fundamental step in the design of an efficient program. Thus, a deep understanding of data structure concepts is essential for students who wish to work on the design and implementation of system software written in C++, an object-oriented programming language that has gained popularity in both academia and industry. Therefore, this book was developed to provide comprehensive and logical coverage of data structures like stacks, queues, linked lists, trees and graphs, which makes it an excellent choice for learning data structures. The objective of the book is to introduce the concepts of data structures and apply these concepts in real-life problem solving. Most of the examples presented resulted from student interaction in the classroom. This book utilizes a systematic approach wherein the design of each of the data structures is followed by algorithms of different operations that can be performed on them and the analysis of these algorithms in terms of their running times.

This book was designed to serve as a textbook for undergraduate engineering students across all disciplines and postgraduate level courses in computer applications. Young researchers working on efficient data storage and related applications will also find it to be a helpful reference source to guide them in the newly established techniques of this rapidly growing research field.

Dr. Sachi Nandan Mohanty and Prof. Pabitra Kumar TripathyDecember 2020

2Review of Concepts of ‘C++’

2.1 Array

Whenever we want to store some values then we have to take the help of a variable, and for this we must have to declare it before its use. If we want to store the details of a student so for this purpose we have to declare the variables as

char name [20], add[30] ;int roll, age, regdno ;float total, avg ;    etc……        for a individual student.

If we want to store the details of more than one student than we have to declare a huge amount of variables and which are too much difficult to access it. I.e/ the programs length will increased too faster. So it will be better to declare the variables in a group. I.e/ name variable will be used for more than one student, roll variable will be used for more than one student, etc.

So to declare the variable of same kind in a group is known as the Array and the concept of array is used for this purpose only.

Definition: