C Programming: Data Structures and Algorithms

1 C programming : data Structures and Algorithms An introduction to elementary programming concepts in C Jack Straub, Instructor Version DRAFT C programming : data Structures and Algorithms , Version DRAFT ii 08/12/08 C programming : data Structures and Algorithms Version DRAFT Copyright 1996 through 2006 by Jack Straub C programming : data Structures and Algorithms , Version DRAFT iii 08/12/08 Table of Contents COURSE OVERVIEW.

2 IX 1. 13 Objectives .. 13 Typedef .. 13 Typedef and Portability .. 13 Typedef and Structures .. 14 Typedef and Functions .. 14 Pointers and Arrays .. 16 Dynamic Memory Allocation .. 17 The Core Module .. 17 The Private Header File .. 18 The Principal Source File .. 18 The Public Header File .. 19 Activity .. 21 2. DOUBLY LINKED LISTS .. 23 Objectives .. 23 Overview .. 23 Definitions .. 24 Enqueuable Item .. 25 Anchor .. 26 Doubly Linked List .. 26 Methods .. 26 ENQ_create_list: Create a New Doubly linked List .. 27 ENQ_create_item: Create a New Enqueuable Item .. 28 ENQ_is_item_enqed: Test Whether an Item is Enqueued .. 29 ENQ_is_list_empty: Test Whether a List is Empty.

3 29 ENQ_add_head: Add an Item to the Head of a List .. 29 ENQ_add_tail: Add an Item to the Tail of a List .. 30 ENQ_add_after: Add an Item After a Previously Enqueued Item .. 30 ENQ_add_before: Add an Item Before a Previously Enqueued Item .. 30 ENQ_deq_item: Dequeue an Item from a List .. 31 ENQ_deq_head: Dequeue the Item at the Head of a List .. 31 ENQ_deq_tail: Dequeue the Item at the Tail of a List .. 32 ENQ_GET_HEAD: Get the Address of the Item at the Head of a List .. 32 ENQ_GET_TAIL: Get the Address of the Item at the Tail of a List .. 32 ENQ_GET_NEXT: Get the Address of the Item After a Given Item .. 33 ENQ_GET_PREV: Get the Address of the Item Before a Given Item .. 33 ENQ_GET_LIST_NAME: Get the Name of a List.

4 33 ENQ_GET_ITEM_NAME: Get the Name of an Item .. 34 ENQ_destroy_item: Destroy an Item .. 34 C programming : data Structures and Algorithms , Version DRAFT iv 08/12/08 ENQ_empty_list: Empty a 35 ENQ_destroy_list: Destroy a List .. 35 Case Study .. 35 Activity .. 39 3. SORTING .. 41 Objectives .. 41 Overview .. 41 Bubble Sort .. 41 Select Sort .. 42 Mergesort .. 42 A Mergesort Implementation in C .. 43 The Mergesort Function s Footprint .. 43 The Pointer Arithmetic Problem.

5 43 The Assignment Problem .. 44 The Comparison Problem .. 45 The Temporary Array .. 46 4. MODULES .. 47 Objectives .. 47 Overview .. 47 C Source Module Components .. 47 Public data .. 47 Private data .. 48 Local data .. 49 Review: Scope .. 49 A Bit about Header Files .. 49 Module Conventions .. 49 5. ABSTRACT data TYPES .. 51 Objectives .. 51 Overview .. 51 Exception Handling .. 52 Classes of ADTs .. 54 The Complex Number ADT .. 54 C programming : data Structures and Algorithms , Version DRAFT v 08/12/08 The List ADT.

6 55 Implementation Choices .. 60 6. STACKS .. 69 Objectives .. 69 Overview .. 69 Stacks And Recursion .. 72 A Minimal Stack Module .. 76 STK Module Public Declarations .. 76 STK_create_stack: Create a Stack .. 76 STK_push_item: Push an Item onto a Stack .. 77 STK_pop_item: Pop an Item off a Stack .. 77 STK_peek_item: Get the Top Item of a Stack .. 77 STK_is_stack_empty: Determine If a Stack is Empty .. 78 STK_is_stack_full: Determine If a Stack is Full .. 78 STK_clear_stack .. 78 STK_destroy_stack: Destroy a Stack .. 79 Simple Stack Example .. 79 Implementation Details .. 80 A More Robust Stack Module .. 82 Stack Marks .. 82 Segmented Stacks .. 84 7. PRIORITY QUEUES.

7 87 Objectives .. 87 Overview .. 87 Queues .. 88 QUE_create_queue .. 90 QUE_create_item .. 91 QUE_clear_queue .. 91 Other QUE Module Methods .. 92 QUE Module Sample Program .. 93 Simple Priority Queues .. 93 PRQ_create_priority_queue .. 95 PRQ_create_item .. 96 PRQ_is_queue_empty .. 96 PRQ_add_item .. 97 PRQ_remove_item .. 97 PRQ_GET_DATA .. 97 PRQ_GET_PRIORITY .. 97 PRQ_destroy_item .. 98 PRQ_empty_queue .. 98 PRQ_destroy_queue .. 98 Priority Queue Example .. 99 Simple Priority Queue Module Implementation ..102 C programming : data Structures and Algorithms , Version DRAFT vi 08/12/08 A More Robust Priority Queue Implementation.

8 104 8. THE SYSTEM LIFE CYCLE .. 107 Objectives ..107 Overview ..107 Specification Phase ..107 Design Phase ..108 Implementation Phase ..108 Acceptance Testing Phase ..108 Maintenance ..109 Testing ..109 Testing at the System Specification Testing at the Design Level ..109 Testing at the Implementation Level ..110 Testing at the Acceptance Testing Level ..111 Testing at the Maintenance Level ..111 9. BINARY TREES .. 113 Objectives ..113 Overview ..113 Binary Tree Representation ..115 Contiguous Array Representation ..115 Dynamically Linked Representation ..116 A Minimal Binary Tree Implementation ..116 Public Declarations ..117 Private Declarations ..117 BTREE_create_tree.

9 118 BTREE_add_root ..118 BTREE_add_left ..119 BTREE_add_right ..120 BTREE_get_root ..120 BTREE_get_data, BTREE_get_left, BTREE_get_right ..120 BTREE_is_empty ..121 BTREE_is_leaf ..121 BTREE_traverse_tree ..122 BTREE_destroy_tree, BTREE_destroy_subtree ..122 Using a Binary Tree as an Index ..124 Using a Binary Tree as an Index Traversing a Binary Tree ..130 Inorder Traversal ..131 Preorder Traversal ..131 Postorder Traversal ..132 C programming : data Structures and Algorithms , Version DRAFT vii 08/12/08 10.

10 N-ARY TREES .. 135 Objectives ..135 Overview ..135 A Small N-ary Tree Implementation ..136 Public data Types ..137 Private Declarations ..137 NTREE_create_tree ..137 NTREE_add_root ..137 NTREE_add_child ..138 NTREE_add_sib: Add a Sibling to a Node ..138 NTREE_get_root ..139 NTREE_has_child ..139 NTREE_has_sib ..139 NTREE_get_data, NTREE_get_child, NTREE_get_sib ..140 NTREE_destroy_tree ..140 Directories ..140 A Simple Directory Module ..143 Public data Types ..143 CDIR_create_dir ..143 CDIR_add_child ..143 CDIR_add_property ..144 CDIR_get_node ..144 CDIR_get_property ..145 CDIR_destroy_dir ..145 Implementation structure ..146 CDIR_create_dir Implementation.