Amazon no longer offers textbook rentals. We do!

Data Structures : A Pseudocode Approach with C

by: Gilberg, Richard F.; Forouzan, Behrouz A.

Data Structures : A Pseudocode Approach with C

by: Gilberg, Richard F.; Forouzan, Behrouz A.

ISBN 13:
9780534951238
ISBN 10:
0534951236
Edition: 1st
Format: Hardcover
Copyright: 03/01/1998
Publisher: Course Technology Ptr
Newer Edition

Rent

Sorry, this item is currently unavailable.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Extend or Purchase Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Summary

Gilberg and Forouzan's language-independent data structures text enables students to first design algorithms using Pseudocode, and then build them using the C programming language. Written at a level that makes it easy for students to understand, the book de-emphasizes mathematical rigor and provides a practical approach to data structures.

Preface

xiii

1 Introduction

(26)

1-1 Pseudocode

(5)

Algorithm Header

(1)

Purpose, Conditions, and Return

(1)

Statement Numbers

(1)

Variables

(1)

Algorithm Analysis

(1)

Statement Constructs

(1)

Sequence

(1)

Selection

(1)

Loop

(1)

Pseudocode Example

(1)

1-2 The Abstract Data Type

(4)

Atomic and Composite Data

(1)

Data Structure

(1)

Abstract Data Type

(2)

1-3 A Model For An Abstract Data Type

(1)

ADT Operations

(1)

ADT Data Structure

(1)

1-4 Algorithm Efficiency

(10)

Linear Loops

(1)

Logarithmic Loops

(1)

Nested Loops

(2)

Linear Logarithmic

(1)

Dependent Quadratic

(1)

Quadratic

(1)

Big-O Notation

(1)

Standard Measures of Efficiency

(1)

Big-O Analysis Examples

(3)

Add Matrices

(1)

Multiply Matrices

(2)

1-5 Summary

(1)

1-6 Practice Sets

(1)

Exercises

(2)

Problems

(1)

Projects

(2)

2 Searching

(38)

2-1 Linear List Searches

(12)

Sequential Search

(3)

Sequential Search Algorithm

(3)

Variations on Sequential Searches

(3)

Sentinel Search

(1)

Probability Search

(1)

Ordered List Search

(1)

Binary Search

(4)

Target Found

(1)

Target Not Found

(2)

Binary Search Algorithm

(1)

Analyzing Linear Search Algorithms

(2)

Sequential Search

(1)

Binary Search

(1)

2-2 Linear Search C Algorithms

(2)

Sequential Search In C

(1)

Binary Search In C

(1)

2-3 Hashed List Searches

(9)

Basic Concepts

(1)

Hashing Methods

(6)

Direct Methods

(6)

Subtraction Method

(1)

Modulo-Division Method

(1)

Digit-Extraction Method

(1)

Midsquare Method

(1)

Folding Methods

(1)

Rotation Method

(2)

Pseudorandom Method

(1)

Hashing Algorithm

(1)

2-4 Collision Resolution

(9)

Open Addressing

(3)

Linear Probe

(1)

Quadratic Probe

(1)

Pseudorandom Collision Resolution

(1)

Key Offset

(1)

Linked List Resolution

(1)

Bucket Hashing

(1)

Combination Approaches

(1)

2-5 Summary

(1)

2-6 Practice Sets

(1)

Exercises

(1)

Problems

(1)

Projects

(2)

3 Linear Lists

(84)

3-1 Linear List Concepts

(3)

Insertion

(1)

Deletion

(1)

Retrieval

(1)

Traversal

(1)

3-2 Linked Lists

(3)

Nodes

(1)

Linked List Data Structure

(2)

Head Node Structure

(1)

Data Node Structure

(1)

Pointers to Linked Lists

(1)

3-3 Linked List Algorithms

(19)

Create List

(2)

Insert Node

(3)

Insert Into Empty List

(1)

Insert at Beginning

(1)

Insert in Middle

(1)

Insert at End

(1)

Insert Node Algorithm

(1)

Delete Node

(5)

Delete First Node

(1)

General Delete Case

(1)

Delete Node Algorithm

(1)

Search List

(3)

Retrieve Node

(1)

Empty List

(1)

Full List

(1)

List Count

(1)

Traverse List

(2)

Destroy List

(1)

3-4 Processing A Linked List

(6)

Add Node

(1)

Remove Node

(1)

Print List

(2)

Testing Insert and Delete Logic

(1)

3-5 Linear List Applications

(5)

Append Linked Lists

(3)

Array of Linked Lists

100

(2)

3-6 Complex Linked List Structures

102

(12)

Header Nodes

102

(1)

Circularly-Linked Lists

103

(1)

Doubly-Linked Lists

104

(6)

Doubly-Linked List Insertion

105

(4)

Doubly-Linked List Deletion

109

(1)

Multilinked Lists

110

(4)

Multilinked List Insert

112

(1)

Multilinked List Delete

113

(1)

3-7 Building A Linked List--C Implementation

114

(8)

Data Structure

114

(1)

Application Functions

115

(7)

Main

115

(1)

Instructions

115

(1)

Build List

116

(1)

Compare Data

117

(1)

Process User Requests

118

(1)

Get User's Choice

119

(1)

Print List

120

(1)

Search List

121

(1)

3-8 Linked List Abstract Data Type

122

(15)

List ADT Functions

123

(14)

Create List

124

(1)

Add Node

125

(1)

Insert Node

126

(2)

Remove Node

128

(1)

Delete Node

128

(1)

Search List

129

(1)

Internal Search Function

129

(3)

Retrieve Node

132

(1)

Empty List

133

(1)

Full List

133

(1)

List Count

134

(1)

Traverse

134

(2)

Destroy List

136

(1)

3-9 Summary

137

(1)

3-10 Practice Sets

137

(1)

Exercises

137

(3)

Problems

140

(1)

Projects

141

(8)

4 Stacks

149

(66)

4-1 Basic Stack Operations

150

(3)

Push

150

(1)

Pop

150

(1)

Stack Top

151

(2)

4-2 Stack--Linked-List Implementation

153

(10)

Data Structure

153

(1)

Stack Head

153

(1)

Stack Data Node

153

(1)

Stack Algorithms

153

(4)

Create Stack

157

(1)

Push Stack

158

(1)

Pop Stack

159

(1)

Stack Top

160

(1)

Empty Stack

161

(1)

Full Stack

161

(1)

Stack Count

162

(1)

Destroy Stack

162

(1)

4-3 Stack Applications

163

(18)

Reversing Data

163

(2)

Reverse a List

164

(1)

Convert Decimal to Binary

164

(1)

Parsing

165

(2)

Postponement

167

(8)

Infix To Postfix Transformation

167

(6)

Evaluating Postfix Expressions

173

(2)

Backtracking

175

(6)

Goal Seeking

175

(3)

Eight Queens Problem

178

(3)

4-4 Eight Queens Problem--C Implementation

181

(7)

Mainline Logic

182

(1)

Get Board Size

183

(1)

Fill Board

183

(2)

Guarded

185

(1)

Print Board

186

(2)

4-5 ADT--Linked-List Implementation

188

(8)

Data Structure

188

(1)

Stack ADT Implementation

188

(8)

Stack Structure

188

(2)

Create Stack

190

(1)

Push Stack

190

(2)

Pop Stack

192

(1)

Stack Top

193

(1)

Empty Stack

193

(1)

Full Stack

194

(1)

Stack Count

194

(1)

Destroy Stack

195

(1)

4-6 Array Implementation of Stacks

196

(6)

Data Structures

196

(1)

Array Algorithms

197

(1)

Create Stack

197

(1)

Push Stack

198

(1)

Pop Stack

198

(1)

Stack Top

199

(1)

Empty Stack

200

(1)

Full Stack

200

(1)

Stack Count

201

(1)

Destroy Stack

201

(1)

4-7 ADT--Array Implementation

202

(5)

Create Stack Array

202

(1)

Push Stack Array

203

(1)

Pop Stack Array

204

(1)

Stack Top Array

205

(1)

Empty Stack Array

205

(1)

Full Stack Array

206

(1)

Stack Count Array

206

(1)

Destroy Stack Array

206

(1)

4-8 Summary

207

(1)

4-9 Practice Sets

208

(1)

Exercises

208

(1)

Problems

209

(2)

Projects

211

(4)

5 Queues

215

(54)

5-1 Queue Operations

216

(2)

Enqueue

216

(1)

Dequeue

216

(1)

Queue Front

217

(1)

Queue Rear

217

(1)

Queue Example

218

(1)

5-2 Queue--Linked-List Implementation

218

(11)

Data Structure

218

(2)

Queue Head

218

(2)

Queue Data Node

220

(1)

Queue Algorithms

220

(3)

Create Queue

223

(1)

Enqueue

224

(1)

Dequeue

225

(1)

Retrieving Queue Data

226

(1)

Empty Queue

227

(1)

Full Queue

227

(1)

Queue Count

228

(1)

Destroy Queue

228

(1)

5-3 Queuing Theory

229

(1)

5-4 Queue Applications

230

(10)

Queue Simulation

231

(7)

Events

231

(1)

Data Structures

232

(1)

Output

233

(1)

Simulation Algorithm

233

(5)

Categorizing Data

238

(2)

5-5 Categorizing Data--C Implementation

240

(4)

Mainline Logic

240

(1)

FillQueues

241

(1)

Print Queues

242

(1)

Print One Queue

243

(1)

5-6 Queue--Linked-List Implementation

244

(8)

Queue Structure

244

(1)

Queue ADT Implementation

245

(7)

Create Queue

245

(1)

Enqueue

246

(1)

Dequeue

247

(1)

Queue Front

248

(1)

Queue Rear

249

(1)

Queue Empty

249

(1)

Full Queue

250

(1)

Queue Count

250

(1)

Destroy Queue

251

(1)

5-7 Queues--Array Implementation

252

(8)

Array Queues Implementation

253

(7)

Create Queue Array

255

(1)

Enqueue: Array Implementation

256

(1)

Dequeue: Array Implementation

257

(1)

Queue Front: Array Implementation

258

(1)

Queue Rear: Array Implementation

259

(1)

Full Queue: Array Implementation

259

(1)

Destroy Queue: Array Implementation

260

(1)

5-8 Summary

260

(1)

5-9 Practice Sets

261

(1)

Exercises

261

(2)

Problems

263

(1)

Projects

264

(5)

6 Recursion

269

(28)

6-1 Factorial--A Case Study

270

(3)

Recursion Defined

270

(1)

Iterative Solution

271

(1)

Recursive Solution

271

(2)

6-2 How Recursion Works

273

(2)

6-3 Designing Recursive Algorithms

275

(5)

The Design Methodology

276

(1)

Limitations of Recursion

277

(1)

Design Implementation-Reverse A Linked List

277

(3)

6-4 Another Case Study-Fibonacci Numbers

280

(2)

6-5 The Towers Of Hanoi

282

(6)

Recursive Towers Of Hanoi

284

(4)

6-6 C Implementations of Recursion

288

(3)

Fibonacci Numbers

288

(1)

Towers of Hanoi

289

(2)

6-7 Summary

291

(1)

6-8 Practice Sets

292

(1)

Exercises

292

(2)

Problems

294

(1)

Projects

295

(2)

7 Introduction to Trees

297

(36)

7-1 Basic Tree Concepts

298

(4)

Terminology

298

(2)

Tree Representation

300

(2)

7-2 Binary Trees

302

(4)

Properties

304

(1)

Height of Binary Trees

304

(1)

Balance

304

(1)

Complete Binary Trees

305

(1)

Binary Tree Structure

305

(1)

7-3 Binary Tree Traversals

306

(7)

Depth-First Traversals

306

(6)

Preorder Traversal (NLR)

307

(2)

Inorder Traversal (LNR)

309

(1)

Postorder Traversal (LRN)

310

(2)

Breadth Traversal

312

(1)

7-4 Expression Trees

313

(3)

Infix Traversal

313

(3)

Postfix Traversal

316

(1)

Prefix Traversal

316

(1)

7-5 General Trees

316

(4)

Changing General Tree To Binary Tree

317

(1)

Insertions Into General Trees

318

(1)

FIFO Insertion

318

(1)

LIFO Insertion

318

(1)

Key-Sequenced Insertion

318

(1)

General Tree Deletions

319

(1)

7-6 Summary

320

(1)

7-7 Practice Sets

321

(1)

Exercises

321

(4)

Problems

325

(1)

Projects

325

(8)

8 Search Trees

333

(62)

8-1 Binary Search Trees

334

(14)

Definition

334

(2)

Operations On Binary Search Trees

336

(12)

Binary Search Tree Traversals

336

(1)

Binary Search Tree Search Algorithms

337

(2)

Insert Node

339

(9)

8-2 AVL Trees

348

(18)

AVL Balance Factor

349

(1)

Balancing Trees

350

(4)

Case 1: Left Of Left

352

(1)

Case 2: Right Of Right

353

(1)

Case 3: Right Of Left

354

(1)

Case 4: Left Of Right

354

(1)

AVL Node Structure

354

(1)

AVL Insert

355

(6)

AVL Insert Algorithm

358

(1)

AVL Left Balance Algorithm

359

(1)

Rotate Algorithm

360

(1)

AVL Delete Algorithm

361

(2)

Delete Right Balance

363

(2)

Adjusting The Balance Factors

365

(1)

8-3 AVL Abstract Data Type

366

(21)

AVL Data Structure

368

(1)

AVL Algorithms

369

(13)

Create AVL Tree

369

(1)

AVL Tree Insert

370

(6)

AVL Tree Delete

376

(6)

AVL Tree Data Processing

382

(2)

Retrieve AVL Tree Node

382

(2)

Traverse AVL Tree

384

(1)

AVL Tree Utility Functions

384

(3)

AVL Empty Tree

385

(1)

AVL Full Tree

385

(1)

AVL Count

385

(1)

Destroy AVL Tree

386

(1)

8-4 Summary

387

(1)

8-5 Practice Sets

388

(1)

Exercises

388

(2)

Problems

390

(2)

Projects

392

(3)

9 Heaps

395

(34)

9-1 Heap Definition

396

(1)

9-2 Heap Structure

396

(1)

9-3 Basic Heap Algorithms

397

(4)

ReheapUp

398

(2)

ReheapDown

400

(1)

9-4 Heap Data Structure

401

(2)

9-5 Heap Algorithms

403

(7)

ReheapUp

403

(1)

ReheapDown

404

(1)

Build Heap

405

(1)

Insert Heap

406

(1)

Delete Heap

407

(3)

9-6 Heap Applications

410

(3)

Selection Algorithms

410

(1)

Priority Queues

410

(3)

9-7 A Heap Program

413

(9)

Heap Program Design

413

(6)

Heap Functions

419

(3)

ReheapUp

419

(1)

ReheapDown

420

(1)

Insert Heap

421

(1)

Delete Heap Node

421

(1)

9-8 Summary

422

(1)

9-9 Practice Sets

423

(1)

Exercises

423

(2)

Problems

425

(1)

Projects

425

(4)

10 Multiway Trees

429

(62)

10-1 M-Way Search Trees

430

(1)

10-2 B-Trees

431

(28)

B-Tree Insertion

433

(9)

B-Tree Insert Design

434

(2)

B-Tree Insert Node

436

(2)

Search Node

438

(1)

Split Node

439

(3)

Insert Entry

442

(1)

Insertion Summary

442

(1)

B-Tree Deletion

442

(13)

B-Tree Delete

445

(1)

Node Delete

445

(2)

Delete Entry

447

(1)

Delete Mid

447

(1)

ReFlow

448

(3)

Balance

451

(2)

Combine

453

(2)

Traverse B-Tree

455

(3)

B-Tree Search

458

(1)

10-3 Simplified B-Trees

459

(2)

2-3 Tree

459

(1)

2-3-4 Tree

460

(1)

10-4 B-tree Variations

461

(1)

B(*)Tree

461

(1)

B+Tree

461

(1)

10-5 Lexical Search Tree

461

(5)

Tries

463

(1)

Trie Structure

464

(1)

Trie Search

464

(2)

10-6 B-Tree Abstract Data Type

466

(20)

Header File

466

(2)

Utility Functions

468

(4)

468

(2)

Traversal

470

(2)

Insert Algorithms

472

(6)

ADT Interface Function

472

(2)

Internal Insert Processing

474

(4)

Delete Algorithms

478

(8)

ADT Delete Interface

478

(1)

Delete Internal Function

479

(2)

Delete Middle

481

(1)

Reflow Function

482

(2)

Borrow Left or Right

484

(1)

Combine

485

(1)

10-7 Summary

486

(1)

10-8 Practice Sets

487

(1)

Exercises

487

(1)

Problems

487

(1)

Projects

488

(3)

11 Advanced Sorting Concepts

491

(58)

11-1 General Sort Concepts

492

(2)

Sort Order

492

(1)

Sort Stability

493

(1)

Sort Efficiency

494

(1)

Passes

494

(1)

11-2 Insertion Sorts

494

(12)

Straight Insertion Sort

494

(3)

Straight Insertion Sort Example

494

(1)

Insertion Sort Algorithm

495

(2)

Shell Sort

497

(4)

Shell Sort Algorithm

497

(4)

Selecting the Increment Size

501

(1)

Insertion Sort Algorithmics

501

(2)

Straight Insertion Sort

501

(1)

Shell Sort

502

(1)

Summary

503

(1)

Insertion Sort Implementation

503

(3)

Straight Insertion Sort

503

(1)

Shell Sort

504

(2)

11-3 Selection Sorts

506

(8)

Straight Selection Sort

506

(2)

Selection Sort Algorithm

506

(2)

Heap Sort

508

(2)

Heap Sort Algorithm

509

(1)

Selection Sort Algorithmics

510

(3)

Straight Selection Sort

510

(1)

Heap Sort

510

(2)

Summary

512

(1)

Selection Sort Implementation

513

(1)

Selection Sort C Code

513

(1)

Heap Sort C Code

513

(1)

11-4 Exchange Sorts

514

(16)

Bubble Sort

515

(2)

Bubble Sort Algorithm

515

(2)

Quick Sort

517

(7)

Quick Sort Algorithm

519

(5)

Exchange Sort Algorithmics

524

(2)

Bubble Sort

524

(1)

Quick Sort

525

(1)

Summary

526

(1)

Exchange Sort Implementation

526

(4)

Bubble Sort Code

526

(1)

Quick Sort Code

527

(3)

11-5 External Sorts

530

(11)

Merging Ordered Files

530

(2)

Merging Unordered Files

532

(1)

The Sorting Process

533

(6)

Natural Merge

535

(1)

Balanced Merge

535

(1)

Polyphase Merge

535

(4)

Sort Phase Revisited

539

(2)

11-6 Summary

541

(1)

11-7 Practice Sets

542

(1)

Exercises

542

(2)

Problems

544

(1)

Projects

545

(4)

12 Graphs

549

(54)

12-1 Terminology

550

(2)

12-2 Operations

552

(5)

Add Vertex

552

(1)

Delete Vertex

552

(1)

Add Edge

553

(1)

Delete Edge

553

(1)

Find Vertex

553

(1)

Traverse Graph

553

(4)

Depth-First Traversal

554

(1)

Breadth-First

555

(2)

12-3 Graph Storage Structures

557

(2)

Adjacency Matrix

557

(1)

Adjacency List

558

(1)

12-4 Graph Algorithms

559

(15)

Create Graph

563

(1)

Insert Vertex

563

(2)

Delete Vertex

565

(1)

Insert Arc

566

(1)

Delete Arc

567

(2)

Retrieve Vertex

569

(1)

First Arc

569

(1)

Depth-First Traversal

570

(2)

Breadth-First Traversal

572

(2)

12-5 Networks

574

(10)

Minimum Spanning Tree

575

(5)

Minimum Spanning Tree Example

576

(1)

Minimum Spanning Tree Data Structure

577

(1)

Minimum Spanning Tree Pseudocode

578

(2)

Shortest Path Algorithm

580

(4)

Shortest Path -- Manual Example

580

(2)

Shortest Path Data Structure

582

(1)

Shortest Path Pseudocode

583

(1)

12-6 Abstract Data Type

584

(12)

Insert Vertex

586

(1)

Delete Vertex

587

(2)

Insert Arc

589

(1)

Delete Arc

590

(2)

Depth-First Traversal

592

(2)

Breadth-First Traversal

594

(2)

12-7 Summary

596

(1)

12-8 Practice Sets

597

(1)

Exercises

597

(1)

Problems

598

(1)

Projects

599

(4)

Appendix A ASCII Tables

603

(6)

A-1 ASCII Codes (Long Form)

603

(4)

A-2 ASCII Table (Short Form)

607

(2)

Appendix B Structure Charts

609

(8)

B-1 Structure Chart Symbols

610

(5)

Modules

610

(2)

Reading Structure Charts

612

(1)

Common Modules

612

(1)

Conditional Calls

613

(1)

Exclusive Or

613

(1)

Loops

613

(1)

Conditional Loops

614

(1)

Recursion

614

(1)

Data Flows and Flags

615

(1)

B-2 Structure Chart Rules

615

(2)

Appendix C Program Standards and Styles

617

(6)

C-1 Global Area

618

(1)

C-2 Program Main Line

619

(1)

C-3 General Coding Standards

619

(1)

C-4 Variables and Structures

620

(1)

C-5 Function Definition

621

(2)

Appendix D Random Numbers

623

(6)

D-1 Random Numbers In C

624

(1)

Srand

624

(1)

Rand

624

(1)

D-2 Custom Random Number Generator

624

(1)

D-3 Scaling a Random Number

625

(4)

Appendix E Standard C Libraries

629

(2)

E-1 Limits.H

629

(1)

E-2 Float.H

630

(1)

Appendix F C Function Prototypes

631

(8)

F-1 Function Index

632

(1)

F-2 Character Library

633

(1)

F-3 Math Library

633

(1)

F-4 Standard I/O Library

634

(1)

General I/O

634

(1)

Formatted I/O

634

(1)

Character I/O

634

(1)

File I/O

635

(1)

System Communication

635

(1)

String I/O

635

(1)

System File Control

635

(1)

F-5 Standard Library

635

(1)

Math Functions

635

(1)

Memory Functions

635

(1)

Program Control

636

(1)

System Communication

636

(1)

Conversion Functions

636

(1)

F-6 String Library

636

(1)

Copying Data

636

(1)

Comparing Data

636

(1)

String Lengths

636

(1)

F-7 Time

637

(2)

Solutions to Selected Exercises

639

(16)

Glossary

655

(10)

Index

665

Amazon no longer offers textbook rentals. We do!

Data Structures : A Pseudocode Approach with C

Data Structures : A Pseudocode Approach with C

9780534951238

0534951236

Summary

Table of Contents

Supplemental Materials

Write a Review

Amazon no longer offers textbook rentals. We do!

Data Structures : A Pseudocode Approach with C

Data Structures : A Pseudocode Approach with C

9780534951238

0534951236

Summary

Table of Contents

Supplemental Materials

Write a Review

Related Products