Data Structures : A Pseudocode Approach with C

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

• ISBN13: 9780534951238
• ISBN10: 0534951236
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-03-01
• Publisher: Course Technology Ptr

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.

Table of Contents

Preface	xiii
1 Introduction	1	(26)
1-1 Pseudocode	2	(5)
Algorithm Header	2	(1)
Purpose, Conditions, and Return	3	(1)
Statement Numbers	4	(1)
Variables	4	(1)
Algorithm Analysis	5	(1)
Statement Constructs	5	(1)
Sequence	5	(1)
Selection	6	(1)
Loop	6	(1)
Pseudocode Example	6	(1)
1-2 The Abstract Data Type	7	(4)
Atomic and Composite Data	8	(1)
Data Structure	9	(1)
Abstract Data Type	9	(2)
1-3 A Model For An Abstract Data Type	11	(1)
ADT Operations	12	(1)
ADT Data Structure	12	(1)
1-4 Algorithm Efficiency	12	(10)
Linear Loops	14	(1)
Logarithmic Loops	14	(1)
Nested Loops	15	(2)
Linear Logarithmic	15	(1)
Dependent Quadratic	16	(1)
Quadratic	16	(1)
Big-O Notation	17	(1)
Standard Measures of Efficiency	18	(1)
Big-O Analysis Examples	19	(3)
Add Matrices	19	(1)
Multiply Matrices	20	(2)
1-5 Summary	22	(1)
1-6 Practice Sets	23	(1)
Exercises	23	(2)
Problems	25	(1)
Projects	25	(2)
2 Searching	27	(38)
2-1 Linear List Searches	28	(12)
Sequential Search	28	(3)
Sequential Search Algorithm	28	(3)
Variations on Sequential Searches	31	(3)
Sentinel Search	31	(1)
Probability Search	32	(1)
Ordered List Search	33	(1)
Binary Search	34	(4)
Target Found	34	(1)
Target Not Found	35	(2)
Binary Search Algorithm	37	(1)
Analyzing Linear Search Algorithms	38	(2)
Sequential Search	38	(1)
Binary Search	39	(1)
2-2 Linear Search C Algorithms	40	(2)
Sequential Search In C	40	(1)
Binary Search In C	41	(1)
2-3 Hashed List Searches	42	(9)
Basic Concepts	43	(1)
Hashing Methods	44	(6)
Direct Methods	44	(6)
Subtraction Method	46	(1)
Modulo-Division Method	46	(1)
Digit-Extraction Method	47	(1)
Midsquare Method	47	(1)
Folding Methods	48	(1)
Rotation Method	48	(2)
Pseudorandom Method	50	(1)
Hashing Algorithm	50	(1)
2-4 Collision Resolution	51	(9)
Open Addressing	53	(3)
Linear Probe	54	(1)
Quadratic Probe	55	(1)
Pseudorandom Collision Resolution	55	(1)
Key Offset	56	(1)
Linked List Resolution	57	(1)
Bucket Hashing	58	(1)
Combination Approaches	59	(1)
2-5 Summary	60	(1)
2-6 Practice Sets	61	(1)
Exercises	61	(1)
Problems	62	(1)
Projects	63	(2)
3 Linear Lists	65	(84)
3-1 Linear List Concepts	66	(3)
Insertion	67	(1)
Deletion	67	(1)
Retrieval	68	(1)
Traversal	68	(1)
3-2 Linked Lists	69	(3)
Nodes	69	(1)
Linked List Data Structure	70	(2)
Head Node Structure	71	(1)
Data Node Structure	71	(1)
Pointers to Linked Lists	72	(1)
3-3 Linked List Algorithms	72	(19)
Create List	74	(2)
Insert Node	76	(3)
Insert Into Empty List	76	(1)
Insert at Beginning	77	(1)
Insert in Middle	77	(1)
Insert at End	79	(1)
Insert Node Algorithm	79	(1)
Delete Node	79	(5)
Delete First Node	81	(1)
General Delete Case	82	(1)
Delete Node Algorithm	83	(1)
Search List	84	(3)
Retrieve Node	87	(1)
Empty List	87	(1)
Full List	88	(1)
List Count	88	(1)
Traverse List	89	(2)
Destroy List	91	(1)
3-4 Processing A Linked List	91	(6)
Add Node	93	(1)
Remove Node	94	(1)
Print List	95	(2)
Testing Insert and Delete Logic	96	(1)
3-5 Linear List Applications	97	(5)
Append Linked Lists	97	(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)
Search	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