DATA STRUCTURES: A PSEUDOCODE APPROACH WITH C, …

1 Licensed to: data Structures: A PSEUDOCODE APPROACH with C, Second EditionRichard F. GilbergBehrouz A. ForouzanSenior Product Manager:Alyssa PrattSenior Acquisitions Editor:Amy YarnevichProduction Editor:BobbiJo Frasca Senior Marketing Manager:Karen SeitzAssociate Product Manager:Mirella MisiaszekEditorial Assistant:Amanda PiantedosiSenior Manufacturing Coordinator:Trevor KallopCover Designer:Abby ScholzCOPYRIGHT 2005 Course Technology, a division of Thomson Learning, Inc. Thomson Learning is a trademark used herein under in the United States of America1 2 3 4 5 6 7 8 9 QWT 09 08 07 06 05 For more information, contact Course Technology, 25 Thomson Place, Boston, Massachusetts, find us on the World Wide Web at: RIGHTS RESERVED. No part of this work covered by the copyright hereon may be reproduced or used in any form or by any means graphic, electronic, or mechanical, including photocopying, recording, taping, Web distribution, or information storage and retrieval systems without the written permission of the permission to use material from this text or product, submit a request online at additional questions about permissions can be submitted by email to DisclaimerCourse Technology reserves the right to revise this publication and make changes from time to time in its content without : 978-0-534-39080-8 ISBN-10: 0-534-39080-3 Copyright 2011 Cengage Learning.

2 All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to:1 Part IIntroductionThere are several concepts that are essential to an understanding of thistext. We discuss these concepts in the first two chapters. Chapter 1 BasicConcepts, covers general materials that we use throughout the 2 Recursion, discusses the concept of recursion. Figure I-1shows the organization of Part I. Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

3 Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to:2 Part IIntroductionFIGURE I-1 Part I ContentsChapters CoveredThis part includes two 1: Basic Concepts The first chapter covers concepts that we use throughout the text. You mayfind that some of them are a review of material from your programming major concepts are outlined all of our texts, we use the basic tenet, Design comes before code. Throughout the text, therefore, we separate algorithm design from the codethat implements it in a specific language. Although the underlying languagein this book is C, PSEUDOCODE allows us to separate the algorithm from theimplementation. Abstract data TypeAn abstract data type (ADT) implements a set of algorithms generically sothat they can be applied to any data type or construct.

4 The beauty of an ADTimplementation is that the algorithms can handle any data type whether it isa simple integer or a complex ImplementationsIn general, there are two basic data structures that can be used to implementan abstract data type: arrays and linked lists. We discuss basic linked list con-cepts in Chapter 1 and expand on them as necessary in subsequent CodeImplementationsAbstract data TypePseudocodeAlgorithm EfficiencyRecursive AlgorithmsRecursion versus RepetitionPart IRecursionChapter 2 Basic ConceptsChapter 1 Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to:Part IIntroduction3 Generic Code for ADTsTo implement the ADT concept, we need to use generic code.

5 Each languageprovides a different set of tools to implement generic code. The C languageuses two tools: pointer to void and pointer to EfficiencyWhile many authors argue that today s computers and compilers make algo-rithm efficiency an academic discussion, we believe that an understanding ofalgorithm efficiency provides the framework for writing better we discuss the efficiency of specific algorithms when we developthem, in this chapter we discuss the basic concepts and tools for discussingalgorithm efficiency. Chapter 2: RecursionIn Chapter 2 we discuss recursion, a concept that is often skipped in anintroductory programming course. We need to understand recursion to dis-cuss data structures because many of the abstract data types are recursive bynature and algorithms that handle them can be better understood usingrecursion. We use recursive algorithms extensively, especially in Part III, Non-Linear Lists. Recursion versus RepetitionThe first part of the chapter compares and contrasts recursion and repetitionand when each should be used.

6 Recursive AlgorithmsAlthough recursive algorithms are generally elegant, they can be difficult tounderstand. In the second part of the chapter, we introduce several algo-rithms to make the recursive concept clear and to provide a sense of designfor creating recursive algorithms. Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to: Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.

7 Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to:5 Chapter 1 Basic ConceptsThis text assumes that the student has a solid foundation in structured pro-gramming principles and has written programs of moderate the text uses C for all of its implementation examples, the designand logic of the data structure algorithms are based on PSEUDOCODE . Thisapproach creates a language-independent environment for the this chapter we establish a background for the tools used in the rest ofthe text, most specifically PSEUDOCODE , the abstract data type, algorithm effi-ciency analysis, and the concepts necessary to create generic PseudocodeAlthough several tools are used to define algorithms, one of the most commonis PSEUDOCODE . PSEUDOCODE is an English-like representation of the algorithmlogic. It is part English, part structured code. The English part provides arelaxed syntax that describes what must be done without showing unnecessarydetails such as error messages.

8 The code part consists of an extended version ofthe basic algorithmic constructs sequence, selection, and this text we use PSEUDOCODE to represent both data structures andcode. data items do not need to be declared. The first time we use a dataname in an algorithm, it is automatically declared. Its type is determined bycontext. The following statement declares a numeric data item named countand sets its value to of the most common tools for defining algorithms is PSEUDOCODE , which is part English, partstructured count to 0 Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require to:6 Section structure of the data , on the other hand, must be declared.

9 We use asimple syntactical statement that begins with a structure name and concludeswith the keyword end and the name of the structure . Within the structure welist the structural elements by indenting the data items as shown data definition describes a node in a self-referential list that consistsof a nested structure ( data ) and a pointer to the next node (link). An ele-ment s type is implied by its name and usage in the mentioned, PSEUDOCODE is used to describe an algorithm. To facilitatea discussion of the algorithm statements, we number them using the hierar-chical system shown in Algorithm 1-1. The following sections describe thecomponents of an algorithm. Colored comments provide documentation orclarification when 1-1 Example of PseudocodeAlgorithm HeaderEach algorithm begins with a header that names it, lists its parameters, anddescribes any preconditions and postconditions. This information is impor-tant because it serves to document the algorithm.

10 Therefore, the headerinformation must be complete enough to communicate to the programmereverything he or she must know to write the algorithm. In Algorithm 1-1there is only one parameter, the page number. nodedata link end nodeAlgorithm sample (pageNumber)This algorithm reads a file and prints a pageNumber passed by reference Post Report Printed pageNumber contains number of pages in report Return Number of lines printed 1 loop (not end of file)1 read file 2 if (full page) 1 increment page number2 write page heading 3 end if4 write report line 5 increment line count2 end loop3 return line countend sample Copyright 2011 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.