UNIX C Programming

Chapter 17: Advanced Data Representation

 

Objectives:

This chapter introduces the concept of abstract data types (ADTs) by means of three types: linked lists, queues, and binary trees. The objectives of this chapter are to

  • Clarify the meaning of an abstract data type (ADT)
  • Explain the design of a linked list ADT
  • Explain the design of a queue ADT
  • Explain the design of a binary tree ADT
Concepts:

Designing a data type consists of deciding on two matters: how to store the data and how to manipulate the data. This chapter examines the process that matches algorithms to data representation. It particular it examines a data representation that uses dynamic memory allocation.

An ADT packages methods and data representations together in a way that is problem-oriented rather than language-oriented.

One ADT is a linked list. A linked list is a list in which each item contains information describing where to find the next item in the list. In a linked-list implementation, each link is called a node. Within each node there is a pointer which points to the address of the next node.

An ADT specifies two types of information: a set of properties and a set of operations. With a linked list, the type property is to hold a sequence of items. The set of operations include:

  • Initialize list to empty
  • Determine if list is empty
  • Determine if list is full
  • Determine number of items in list
  • Add item to end of list
  • Traverse list, processing each item in the list.

The three step process in creating an ADT moves from the general to the concrete. The steps are:

  1. Provide an abstract description of the type's properties and of the operations you can perform on the type.
  2. Develop a programming interface that implements the ADT.
  3. Write code to implement the interface.

Building the interface generally involves creating some general type, such as type Item, as in: 

	#define TSIZE 45
	struct film
	{
	char title[TSIZE];
	int rating;
	};
	typedef struct film Item;

This defines Item and allows the programmer to store data of this type.

A queue is a first in, first out (FIFO) data form. With this ADT, the operations include:

  • Initialize queue to empty
  • Determine whether queue is empty
  • Determine whether queue is full
  • Determine number of items in the queue
  • Add item to rear of queue
  • Remove and recover item from front of queue

A primary difference between a linked list Node and a queue Node is as follows: 

	typedef struct node
	{
	Item item;
	struct node * next;
	} NODE;
	typedef struct queue
	{
	Node * front;
	Node * rear;
	int items;
	} Queue;

With a linked list a single pointer points to the next node. With a queue, two pointers are needed to point to the front and rear nodes.

Comparing a linked list to an array leads to the following advantages for a linked list: Size is determined during run time, and inserting and deleting nodes is quick. The disadvantages include lack of direct support by C and no random user access.

With a linked list, a search must be performed sequentially. A binary search ADT avoids this. This type of search begins in the middle of an ordered list and performs a binary search strategy.

Each node in a binary tree ADT contains two pointers to other nodes, called child nodes. The properties of a binary tree ADT are several and include:

  • A tree is either an empty set of nodes or a set of nodes with one node designated as the root.
  • Each node has exactly two trees, called subtrees, descending from it.
  • Each subtree is itself a binary tree, which include the possibility of an empty tree.
  • A binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item and in which the root item precedes all items in the right subtree.

The operations of a binary tree are also several and include:

  • Determine if the tree is empty
  • Determine if the tree is full
  • Determine the number of items in the tree
  • Add an item to the tree
  • Remove an item from the tree
  • Search the tree for an item
  • Visit each item in the tree

A binary tree is efficient only if it is balanced. Trees built as balanced trees are called AVL trees.