Data Structures A Pseudocode Approach with C

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

• ISBN13: 9780534390808
• ISBN10: 0534390803
• Edition: 2nd
• Format: Hardcover
• Copyright: 2004-10-11
• Publisher: Course Technology

Summary

This second edition expands upon the solid, practical foundation established in the first edition of the text. A new four-part organizational structure increases the flexibility of the text, and all material is presented in a straightforward manner accompanied by an array of examples and visual diagrams.

Table of Contents

Part I Introduction	1	(76)
Basic Concepts	5	(40)
Pseudocode	5	(5)
Algorithm Header	6	(1)
Purpose, Conditions, and Return	7	(1)
Statement Numbers	7	(1)
Variables	8	(1)
Statement Constructs	8	(1)
Sequence	8	(1)
Selection	9	(1)
Loop	9	(1)
Algorithm Analysis	9	(1)
Pseudocode Example	9	(1)
The Abstract Data Type	10	(4)
Atomic and Composite Data	10	(1)
Data Type	11	(1)
Data Structure	11	(1)
Abstract Data Type	12	(2)
Model for an Abstract Data Type	14	(1)
ADT Operations	14	(1)
ADT Data Structure	15	(1)
ADT Implementations	15	(2)
Array Implementations	15	(1)
Linked List Implementations	15	(2)
Pointers to Linked Lists	17	(1)
Generic Code for ADTs	17	(11)
Pointer to void	18	(5)
Pointer to Function	23	(1)
Defining Pointers to Functions	24	(1)
Using Pointers to Functions	24	(4)
Algorithm Efficiency	28	(10)
Linear Loops	29	(1)
Logarithmic Loops	29	(1)
Nested Loops	30	(1)
Linear Logarithmic	31	(1)
Quadratic	31	(1)
Dependent Quadratic	31	(1)
Big-O Notation	32	(1)
Standard Measures of Efficiency	33	(2)
Big-O Analysis Examples	35	(1)
Add Square Matrices	35	(1)
Multiply Square Matrices	36	(2)
Key Terms	38	(1)
Summary	38	(1)
Practice Sets	39	(6)
Exercises	39	(2)
Problems	41	(1)
Projects	42	(3)
Recursion	45	(32)
Factorial---A Case Study	45	(3)
Recursion Defined	46	(1)
Iterative Solution	47	(1)
Recursive Solution	47	(1)
Designing Recursive Algorithms	48	(4)
The Design Methodology	48	(2)
Limitations of Recursion	50	(1)
Design Implementation---Reverse Keyboard Input	50	(2)
Recursive Examples	52	(19)
Greatest Common Divisor	52	(1)
GCD Design	53	(1)
GCD C Implementation	53	(1)
Fibonacci Numbers	54	(1)
Design	55	(1)
Fibonacci C Implementation	56	(1)
Prefix to Postfix Conversion	57	(1)
Design	58	(3)
Prefix to Postfix C Implementation	61	(4)
The Towers of Hanoi	65	(1)
Recursive Towers of Hanoi Design	65	(4)
Towers of Hanoi C Implementation	69	(2)
Key Terms	71	(1)
Summary	71	(1)
Practice Sets	72	(5)
Exercises	72	(2)
Problems	74	(1)
Projects	75	(2)
Part II Linear Lists	77	(186)
Stacks	79	(68)
Basic Stack Operations	80	(3)
Push	80	(1)
Pop	80	(1)
Stack Top	81	(2)
Stack Linked List Implementation	83	(7)
Data Structure	83	(1)
Stack Head	83	(1)
Stack Data Node	83	(1)
Stack Algorithms	84	(1)
Create Stack	84	(1)
Push Stack	85	(1)
Pop Stack	86	(1)
Stack Top	87	(1)
Empty Stack	88	(1)
Full Stack	89	(1)
Stack Count	89	(1)
Destroy Stack	89	(1)
C Language Implementations	90	(5)
Insert Data	92	(1)
Push Stack	93	(1)
Print Stack	93	(1)
Pop Character	94	(1)
Stack ADT	95	(7)
Data Structure	95	(1)
ADT Implementation	95	(1)
Stack Structure	95	(1)
Create Stack	96	(1)
Push Stack	97	(1)
Pop Stack	98	(1)
Stack Top	99	(1)
Empty Stack	100	(1)
Stack Count	101	(1)
Destroy Stack	101	(1)
Stack Applications	102	(32)
Reversing Data	103	(1)
Reverse a List	103	(3)
Convert Decimal to Binary	106	(1)
Parsing	107	(3)
Postponement	110	(1)
Infix to Postfix Transformation	110	(8)
Evaluating Postfix Expressions	118	(4)
Backtracking	122	(1)
Goal Seeking	122	(3)
Eight Queens Problem	125	(9)
How Recursion Works	134	(4)
Key Terms	138	(1)
Summary	138	(1)
Practice Sets	139	(8)
Exercises	139	(2)
Problems	141	(2)
Projects	143	(4)
Queues	147	(46)
Queue Operations	148	(3)
Enqueue	148	(1)
Dequeue	148	(1)
Queue Front	149	(1)
Queue Rear	150	(1)
Queue Example	150	(1)
Queue Linked List Design	151	(8)
Data Structure	152	(1)
Queue Head	152	(1)
Queue Data Node	153	(1)
Queue Algorithms	153	(1)
Create Queue	154	(1)
Enqueue	154	(1)
Dequeue	155	(1)
Retrieving Queue Data	156	(1)
Empty Queue	157	(1)
Full Queue	157	(1)
Queue Count	158	(1)
Destroy Queue	158	(1)
Queue ADT	159	(7)
Queue Structure	159	(1)
Queue ADT Algorithms	159	(7)
Queuing Theory	166	(2)
Queue Applications	168	(15)
Categorizing Data	168	(1)
Categorizing Data Design	169	(1)
Categorizing Data---C Implementation	170	(5)
Queue Simulation	175	(1)
Events	176	(1)
Data Structures	176	(1)
Output	177	(1)
Simulation Algorithm	178	(5)
Key Terms	183	(1)
Summary	183	(1)
Practice Sets	184	(9)
Exercises	184	(3)
Problems	187	(1)
Projects	188	(5)
General Linear Lists	193	(70)
Basic Operations	193	(2)
Insertion	193	(1)
Deletion	194	(1)
Retrieval	194	(1)
Traversal	194	(1)
Implementation	195	(18)
Data Structure	195	(1)
Head Node	196	(1)
Data Node	196	(1)
Algorithms	197	(1)
Create List	197	(1)
Insert Node	198	(4)
Delete Node	202	(3)
List Search	205	(3)
Retrieve Node	208	(1)
Empty List	208	(1)
Full List	209	(1)
List Count	210	(1)
Traverse List	210	(2)
Destroy List	212	(1)
List ADT	213	(15)
ADT Functions	214	(2)
Create List	216	(1)
Add Node	217	(1)
Internal Insert Function	217	(2)
Remove Node	219	(1)
Internal Delete Function	220	(1)
Search List	221	(1)
Internal Search Function	222	(2)
Retrieve Node	224	(1)
Empty List	225	(1)
Full List	225	(1)
List Count	226	(1)
Traverse	226	(1)
Destroy List	227	(1)
Application	228	(11)
Data Structure	228	(1)
Application Functions	229	(1)
Mainline	229	(1)
Print Instructions	229	(2)
Build List	231	(2)
Process User Requests	233	(1)
Get User Choice	234	(1)
Print List	235	(1)
Search List	236	(1)
Compare Year	237	(1)
Testing Insert and Delete Logic	238	(1)
Testing Insert Logic	238	(1)
Testing Delete Logic	238	(1)
Complex Implementations	239	(9)
Circularly Linked Lists	239	(1)
Doubly Linked Lists	240	(1)
Insertion	241	(2)
Deletion	243	(1)
Multilinked Lists	244	(2)
Insert	246	(1)
Delete	247	(1)
Key Terms	248	(1)
Summary	248	(1)
Practice Sets	249	(14)
Exercises	249	(2)
Problems	251	(2)
Projects	253	(10)
Part III Non-Linear Lists	263	(268)
Introduction to Trees	265	(34)
Basic Tree Concepts	265	(5)
Terminology	266	(2)
User Representation	268	(2)
Binary Trees	270	(17)
Properties	271	(1)
Height of Binary Trees	271	(1)
Balance	272	(1)
Complete and Nearly Complete Binary Trees	273	(1)
Binary Tree Traversals	273	(1)
Depth-first Traversals	274	(4)
Breadth-first Traversals	278	(2)
Expression Trees	280	(1)
Infix Traversal	280	(1)
Postfix Traversal	281	(1)
Prefix Traversal	282	(1)
Huffman Code	282	(5)
General Trees	287	(3)
Insertions into General Trees	287	(1)
FIFO Insertion	287	(1)
LIFO Insertion	287	(1)
Key-sequenced Insertion	287	(1)
General Tree Deletions	288	(1)
Changing a General Tree to a Binary Tree	288	(2)
Key Terms	290	(1)
Summary	290	(2)
Practice Sets	292	(7)
Exercises	292	(3)
Problems	295	(1)
Projects	296	(3)
Binary Search Trees	299	(42)
Basic Concepts	299	(2)
BST Operations	301	(8)
Traversals	301	(1)
Searches	302	(1)
Find the Smallest Node	302	(1)
Find the Largest Node	303	(1)
BST Search	303	(2)
Insertion	305	(2)
Deletion	307	(2)
Binary Search Tree ADT	309	(15)
Data Structure	311	(1)
Head Structure	311	(1)
Node Structure	311	(1)
Algorithms	311	(2)
Create a BST	313	(1)
Insert a BST	313	(1)
Internal Insert Function	314	(1)
Delete a BST	315	(1)
Internal Delete Function	316	(2)
Retrieve a BST	318	(1)
Internal Retrieve Function	319	(1)
Traverse a BST	320	(1)
Internal Traverse Function	321	(1)
Empty a BST	321	(1)
Full BST	322	(1)
BST Count	322	(1)
Destroy a BST	323	(1)
Internal Destroy Function	323	(1)
BST Applications	324	(10)
Integer Application	324	(4)
Student List Application	328	(1)
Program Design	329	(5)
Threaded Trees	334	(2)
Key Terms	336	(1)
Summary	336	(1)
Practice Sets	337	(4)
Exercises	337	(2)
Problems	339	(1)
Projects	339	(2)
AVL Search Trees	341	(48)
AVL Tree Basic Concepts	341	(7)
AVL Tree Balance Factor	342	(1)
Balancing Trees	343	(1)
Case 1: Left of Left	344	(1)
Case 2: Right of Right	345	(1)
Case 3: Right of Left	346	(1)
Case 4: Left of Right	347	(1)
AVL Tree Implementations	348	(8)
Insert into AVL Tree	348	(2)
AVL Tree Insert Algorithm	350	(1)
AVL Tree Left Balance Algorithm	351	(1)
Rotate Algorithms	351	(1)
AVL Tree Delete Algorithm	352	(2)
Delete Right Balance	354	(1)
Adjusting the Balance Factors	355	(1)
AVL Tree Abstract Data Type	356	(20)
AVL Tree Data Structure	357	(1)
Head Structure	357	(1)
Node Structure	357	(1)
AVL Tree Algorithms	357	(2)
Create an AVL Tree	359	(1)
Insert an AVL Tree	360	(5)
Delete an AVL Tree	365	(5)
Retrieve an AVL Tree	370	(2)
Traverse an AVL Tree	372	(1)
Internal Traverse Function	373	(1)
Empty an AVL Tree	373	(1)
Full AVL Tree	374	(1)
AVL Tree Count	374	(1)
Destroy AVL Tree	375	(1)
Internal Destroy Function	375	(1)
Application---Count Words	376	(8)
Data Structure	376	(1)
Program Design	376	(1)
Count Words Program	377	(1)
Build List	378	(2)
Get Word	380	(1)
Compare Words	381	(1)
Print Words	382	(2)
Key Terms	384	(1)
Summary	384	(1)
Practice Sets	384	(5)
Exercises	384	(2)
Problems	386	(1)
Projects	386	(3)
Heaps	389	(34)
Basic Concepts	389	(5)
Definition	389	(2)
Maintenance Operations	391	(1)
Reheap Up	391	(1)
Reheap Down	392	(2)
Heap Implementation	394	(7)
Algorithms	396	(1)
Reheap Up	396	(1)
Reheap Down	396	(1)
Build a Heap	397	(1)
Insert a Node into a Heap	398	(2)
Delete a Node from a Heap	400	(1)
Heap ADT	401	(6)
Heap Structure	401	(1)
Heap Algorithms	402	(1)
Create a Heap	403	(1)
Insert a Heap	404	(1)
Internal Reheap Up Function	405	(1)
Delete a Heap	405	(1)
Internal Reheap Down Function	406	(1)
Heap Applications	407	(10)
Selection Algorithms	408	(1)
Priority Queues	409	(1)
Design	409	(2)
Implementation	411	(6)
Key Terms	417	(1)
Summary	417	(1)
Practice Sets	418	(5)
Exercises	418	(2)
Problems	420	(1)
Projects	420	(3)
Multiway Trees	423	(58)
M-way Search Trees	423	(2)
B-trees	425	(24)
B-tree Implementation	427	(1)
B-tree Insertion	427	(2)
Insert Node	429	(3)
Search Node	432	(1)
Split Node	433	(2)
Insertion Summary	435	(1)
B-tree Deletion	435	(2)
Delete Node	437	(2)
Delete Entry	439	(1)
Delete Mid	439	(1)
Reflow	440	(2)
Balance	442	(2)
Combine	444	(2)
Traverse B-tree	446	(2)
B-tree Search	448	(1)
B-tree ADT	449	(21)
B-tree Data Structure	449	(1)
Head Structure	449	(1)
Node Structure	450	(1)
Header File	451	(2)
Algorithms	453	(1)
B-tree Search	453	(1)
Internal Search Function	454	(1)
B-tree Traverse	455	(1)
Internal Traverse Function	456	(1)
B-tree Insert	457	(2)
Internal Insert Function	459	(1)
Internal Split Node Function	460	(2)
B-tree Delete	462	(1)
Internal Delete Function	463	(2)
Internal Delete Middle Function	465	(1)
Internal Reflow Function	466	(1)
Internal Borrow Left or Right	467	(2)
Internal Combine Nodes Function	469	(1)
Simplified B-trees	470	(1)
2-3 Tree	470	(1)
2-3-4 Tree	470	(1)
B-tree Variations	471	(1)
B*tree	471	(1)
B+tree	471	(1)
Lexical Search Tree	472	(4)
Tries	473	(1)
Trie Structure	474	(1)
Trie Search	474	(2)
Key Terms	476	(1)
Summary	476	(1)
Practice Sets	477	(4)
Exercises	477	(1)
Problems	478	(1)
Projects	479	(2)
Graphs	481	(50)
Basic Concepts	481	(2)
Operations	483	(5)
Insert Vertex	483	(1)
Delete Vertex	484	(1)
Add Edge	484	(1)
Delete Edge	485	(1)
Find Vertex	485	(1)
Traverse Graph	485	(1)
Depth-first Traversal	485	(2)
Breadth-first Traversal	487	(1)
Graph Storage Structures	488	(2)
Adjacency Matrix	488	(1)
Adjacency List	489	(1)
Graph Algorithms	490	(10)
Create Graph	491	(1)
Insert Vertex	492	(1)
Delete Vertex	493	(1)
Insert Arc	493	(2)
Delete Arc	495	(1)
Retrieve Vertex	496	(1)
Depth-first Traversal	496	(2)
Breadth-first Traversal	498	(1)
Destroy Graph	499	(1)
Graph ADT	500	(13)
Data Structure	501	(1)
Head Structure	501	(1)
Vertex Structure	501	(1)
Arc Structure	501	(1)
Algorithms	502	(1)
Graph Insert Vertex	503	(2)
Graph Delete Vertex	505	(1)
Graph Insert Arc	506	(2)
Graph Delete Arc	508	(1)
Graph Depth-first Traversal	509	(2)
Graph Breadth-first Traversal	511	(2)
Networks	513	(10)
Minimum Spanning Tree	514	(1)
Minimum Spanning Tree Example	515	(1)
Minimum Spanning Tree Data Structure	515	(2)
Minimum Spanning Tree Pseudocode	517	(1)
Shortest Path Algorithm	518	(1)
Shortest Path Manual Example	519	(1)
Shortest Path Pseudocode	520	(3)
Key Terms	523	(1)
Summary	523	(1)
Practice Sets	524	(7)
Exercises	524	(2)
Problems	526	(1)
Projects	527	(4)
Part IV Sorting and Searching	531	(112)
Sorting	533	(64)
Sort Concepts	533	(4)
Sort Order	534	(1)
Sort Stability	535	(1)
Sort Efficiency	535	(1)
Passes	535	(1)
Sorts and ADTs	536	(1)
Selection Sorts	537	(10)
Straight Selection Sort	537	(1)
Selection Sort Algorithm	537	(2)
Heap Sort	539	(2)
Heap Sort Algorithm	541	(1)
Selection Sort Efficiency	541	(1)
Straight Selection Sort	541	(1)
Heap Sort	542	(1)
Summary	542	(1)
Selection Sort Implementation	543	(1)
Selection Sort C Code	543	(1)
Heap Sort C Code	544	(3)
Insertion Sorts	547	(11)
Straight Insertion Sort	547	(1)
Straight Insertion Sort Example	547	(1)
Insertion Sort Algorithm	547	(2)
Shell Sort	549	(1)
Shell Sort Algorithm	550	(3)
Selecting the Increment Size	553	(1)
Insertion Sort Efficiency	554	(1)
Straight Insertion Sort	554	(1)
Shell Sort	554	(1)
Summary	555	(1)
Insertion Sort Implementation	556	(1)
Straight Insertion Sort	556	(1)
Shell Sort	557	(1)
Exchange Sorts	558	(15)
Bubble Sort	558	(1)
Bubble Sort Algorithm	559	(1)
Quick Sort	560	(2)
Quick Sort Algorithm	562	(5)
Exchange Sort Efficiency	567	(1)
Bubble Sort	567	(1)
Quick Sort	567	(1)
Summary	568	(1)
Exchange Sort Implementation	569	(1)
Bubble Sort Code	569	(1)
Quick Sort Code	570	(3)
External Sorts	573	(10)
Merging Ordered Files	573	(2)
Merging Unordered Files	575	(1)
The Sorting Process	576	(1)
Natural Merge	577	(1)
Balanced Merge	577	(3)
Polyphase Merge	580	(1)
Sort Phase Revisited	580	(3)
Quick Sort Efficiency	583	(5)
Worst Case	584	(1)
Best Case	584	(2)
Average Case	586	(2)
Key Terms	588	(1)
Summary	588	(2)
Practice Sets	590	(7)
Exercises	590	(2)
Problems	592	(1)
Projects	593	(4)
Searching	597	(46)
List Searches	597	(12)
Sequential Search	597	(2)
Sequential Search Algorithm	599	(1)
Variations on Sequential Searches	600	(1)
Sentinel Search	600	(1)
Probability Search	601	(1)
Ordered List Search	602	(1)
Binary Search	603	(1)
Target Found	603	(2)
Target Not Found	605	(1)
Binary Search Algorithm	606	(1)
Analyzing Search Algorithms	607	(1)
Sequential Search	607	(1)
Binary Search	608	(1)
Search Implementations	609	(2)
Sequential Search in C	609	(1)
Binary Search In C	610	(1)
Hashed List Searches	611	(9)
Basic Concepts	611	(2)
Hashing Methods	613	(1)
Direct Method	613	(2)
Subtraction Method	615	(1)
Modulo-division Method	615	(1)
Digit-extraction Method	616	(1)
Midsquare Method	617	(1)
Folding Methods	617	(1)
Rotation Method	618	(1)
Pseudorandom Hashing	619	(1)
One Hashing Algorithm	619	(1)
Collision Resolution	620	(16)
Open Addressing	623	(1)
Linear Probe	624	(1)
Quadratic Probe	625	(1)
Pseudorandom Collision Resolution	626	(1)
Key Offset	627	(1)
Linked List Collision Resolution	628	(1)
Bucket Hashing	629	(1)
Combination Approaches	630	(1)
Hashed List Example	630	(6)
Key Terms	636	(1)
Summary	636	(2)
Practice Sets	638	(5)
Exercises	638	(1)
Problems	639	(1)
Projects	640	(3)
Appendix A ASCII Tables	643	(6)
ASCII Codes (Long Form)	643	(5)
ASCII Table (Short Form)	648	(1)
Appendix B Structure Charts	649	(8)
Structure Chart Symbols	650	(5)
Modules	650	(1)
Reading Structure Charts	651	(1)
Common Modules	652	(1)
Conditional Calls	652	(1)
Exclusive Or	652	(1)
Loops	653	(1)
Conditional Loops	653	(1)
Recursion	653	(1)
Data Flows and Flags	654	(1)
Structure Chart Rules	655	(2)
Appendix C Integer and Float Libraries	657	(4)
limits.h	657	(1)
float.h	658	(3)
Appendix D Selected C Libraries	661	(14)
Function Index	661	(3)
Type Library	664	(1)
Math Library	664	(4)
Standard I/O Library	668	(3)
General I/O	668	(1)
Formatted I/O	669	(1)
Character I/O	669	(1)
File I/O	670	(1)
String I/O	670	(1)
System File Control	670	(1)
Standard Library	671	(1)
Math Functions	671	(1)
Memory Functions	671	(1)
Program Control	671	(1)
System Communication	672	(1)
Conversion Functions	672	(1)
String Library	672	(1)
Memory Functions	672	(1)
String Functions	673	(1)
Time Library	673	(2)
Appendix E Mathematical Series and Recursive Relations	675	(6)
Arithmetic Series	675	(2)
Geometric Series	677	(1)
Harmonic Series	678	(1)
Recursive Relations	679	(2)
Appendix F Array Implementations of Stacks and Queues	681	(16)
Stack ADT	681	(7)
Array Data Structure	682	(1)
Create Stack	683	(1)
Push Stack	684	(1)
Pop Stack	684	(1)
Stack Top	685	(1)
Empty Stack	686	(1)
Full Stack	686	(1)
Stack Count	686	(1)
Destroy Stack	687	(1)
Queue ADT	688	(9)
Array Queues Implementation	689	(2)
Create Queue	691	(1)
Enqueue	692	(1)
Dequeue	693	(1)
Queue Front	693	(1)
Queue Rear	694	(1)
Full Queue	694	(1)
Empty Queue	694	(1)
Queue Count	695	(1)
Destroy Queue	695	(2)
Glossary	697	(12)
Index	709