As we know, programs consist of two parts — algorithms and data structures. In a good program these components effectively complement each other. The choice and implementation of a data structure are just as important as the procedures for processing the data. The way information is organized and accessed is usually determined by the nature of the task being programmed. Thus it is important for a programmer to have at hand techniques suited to different situations.

The degree to which a data type is tied to its machine representation is inversely related to its level of abstraction. In other words, the more abstract data types become, the more the conceptual view of how that data is stored differs from the actual, physical way it is stored in computer memory. Simple types, such as char or int, are closely tied to their machine representation. For example, the machine representation of an integer value closely approximates the corresponding programming concept. As data types grow more complex, they become conceptually less similar to their machine equivalents. Thus, real floating-point numbers are more abstract than integers. The actual representation of the float type in the machine corresponds only roughly to the average programmer's notion of a real number. Even more abstract is a structure belonging to composite data types.

At the next level of abstraction, the purely physical aspects of the data recede into the background as a result of introducing an access mechanism(data engine) for the data, that is, a mechanism for storing and retrieving information. In essence, the physical data is linked to an access mechanism that manages the handling of the data from the program. It is precisely the mechanisms for accessing data to which this chapter is devoted.

There are four access mechanisms:

• Queue (queue)
• Stack (stack)
• Linked list (linked list)
• Binary tree (binary tree)

Each of these methods makes it possible to solve problems of a certain class. These methods are essentially mechanisms that perform certain operations of storing and retrieving the information passed to them, based on the requests they receive. They all store and retrieve an element, where an element is understood to be a unit of information. This chapter shows how to build such access mechanisms in the C language. Along the way, it illustrates some common C programming techniques, including dynamic memory allocation and the use of pointers.

• Queues
• Circular queue
• Stacks
• Linked lists
• Singly linked lists
• Doubly linked lists
• Mailing list example
• Binary trees

Other names: magazine, stack memory, pushdown memory, pushdown-type memory, pushdown-type storage device, stack storage device.

Other names: chained list, list using pointers, list with links, pointer-based list.

Other names: binary search tree.

Queues

A queue — is a linear list of information handled on the principle of "first in — first out" (first-in, first-out); this principle (and the queue as a data structure) is also sometimes called FIFO . This means that the first element placed into the queue will be the first one retrieved from it; the second element placed will be the second one extracted, and so on. This is the only way to work with a queue; random access to individual elements is not allowed.

Queues are very common in real life, for example, at banks or fast-food restaurants. To imagine how a queue works, let’s introduce two functions: qstore() and qretrieve() (from "store"— to store, "retrieve" — to fetch). The functionqstore() places an element at the end of the queue, while the function qretrieve() removes an element from the front of the queue and returns its value. Table 22.1 shows the effect of a sequence of such operations.

Table 22.1. Operation of a queue

Action	Contents of the queue
qstore(A)	A
qstore(B)	A B
qstore(C)	A B C
qretrieve() returns A	B C
qstore(D)	B C D
qretrieve() returns B	C D
qretrieve() returns C	D

Keep in mind that the retrieval operation removes an element from the queue and destroys it, unless it is stored somewhere else. Therefore, after all elements have been retrieved, the queue will be empty.

In programming, queues are used to solve many kinds of problems. One of the most popular types of such problems — simulation. Queues are also used in operating system task schedulers and in input/output buffering.

To illustrate how a queue works, we will write a simple appointment-scheduling program. This program lets you store information about a certain number of appointments; later, as each appointment passes, it is removed from the list. For simplicity, the appointment description is limited to 255 characters, and the number of appointments — to an arbitrary figure of 100.

When developing this simple scheduling program, the first thing to do is implement the functions described here, qstore() andqretrieve(). They will store pointers to strings containing the descriptions of the appointments.

#define MAX 100

char *p[MAX];
int spos = 0;
int rpos = 0;

/* Store an appointment. */
void qstore(char *q)
{
  if(spos==MAX) {
    printf("List is full\n");
    return;
  }
  p[spos] = q;
  spos++;
}

/* Retrieve an appointment. */
char *qretrieve()
{
  if(rpos==spos) {
    printf("No more appointments.\n");
    return '\0';
  }
  rpos++;
  return p[rpos-1];
}

Notice that these two functions require two global variables: spos, which holds the index of the next free slot in the list, and rpos, which holds the index of the next element to be fetched. Using these functions, you can organize a queue of data of another type simply by changing the base type of the array they process.

The function qstore() places the descriptions of new appointments at the end of the list and checks whether the list is full. The function qretrieve()extracts appointments from the queue, if any are present. As appointments are scheduled, the value of the variable spos increases, and as they pass, the value of the variable rpos increases. In effect, rpos "catches up with" spos in the queue. Fig. 22.1 shows what may happen in memory during program execution. If rpos and spos are equal, there are no scheduled events pending. Even though the function qretrieve() does not physically destroy the information stored in the queue; however, this information can be considered destroyed, since it is no longer possible to access it again.

Fig. 22.1. The retrieval index "catches up" with the insertion index

Initial state of the queue ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos qstore('A') ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | A | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos qstore('B') ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | A | B | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos qretrive() ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | | B | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos qretrive() ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos qstore('A') ↓spos +---+---+---+---+---+---+---+---+---+---+---+ | | | C | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+ ↑rpos

The complete source code of the simple appointment scheduler program is given below. You can improve upon this program as you see fit.

/* Mini appointment scheduler */

#include 
#include 
#include 
#include 

#define MAX 100

char *p[MAX], *qretrieve(void);
int spos = 0;
int rpos = 0;
void enter(void), qstore(char *q), review(void), delete_ap(void);

int main(void)
{
  char s[80];
  register int t;

  for(t=0; t < MAX; ++t) p[t] = NULL; /* initialize the array
                                         with null pointers */

  for(;;) {
    printf("Enter (E), List (L), Remove (R), Quit (Q): ");
    gets(s);
    *s = toupper(*s);

    switch(*s) {
      case 'E':
        enter();
        break;
      case 'L':
        review();
        break;
      case 'R':
        delete_ap();
        break;
      case 'Q':
        exit(0);
    }
  }
  return 0;
}

/* Insert a new appointment into the queue. */
void enter(void)
{
  char s[256], *p;

  do {
    printf("Enter appointment %d: ", spos+1);
    gets(s);
    if(*s==0) break; /* no entry was made */
    p = (char *) malloc(strlen(s)+1);
    if(!p) {
      printf("Out of memory.\n");
      return;
    }
    strcpy(p, s);
    if(*s) qstore(p);
  } while(*s);
}

/* Display the contents of the queue. */
void review(void)
{
  register int t;

  for(t=rpos; t < spos; ++t)
    printf("%d. %s\n", t+1, p[t]);
}

/* Remove an appointment from the queue. */
void delete_ap(void)
{
  char *p;

  if((p=qretrieve())==NULL) return;
  printf("%s\n", p);
}

/* Insert an appointment. */
void qstore(char *q)
{
  if(spos==MAX) {
    printf("List Full\n");
    return;
  }
  p[spos] = q;
  spos++;
}

/* Retrieve an appointment. */
char *qretrieve(void)
{
  if(rpos==spos) {
    printf("No more appointments.\n");
    return NULL;
  }
  rpos++;
  return p[rpos-1];
}

This principle also goes by other names: "first in, first served," "in order of arrival," "first in, first out," "reverse-stack type."

Circular Queue

When studying the previous appointment scheduler example, you probably thought of the following way to improve it: instead of stopping the program when the end of the array holding the queue is reached, the insertion (spos) and retrieval (rpos) indices can be set to point to the beginning of the array. This makes it possible to place any number of elements into the queue, provided they are retrieved in a timely manner. This implementation of the queue is called a circular queue, because the array is used as though it were not a linear list but a ring.

To implement a circular queue in the scheduler program, the functions qstore() and qretrieve() needs to be rewritten as follows:

void qstore(char *q)
{
  /* The queue overflows when spos is one
     less than rpos, or when spos points
     to the end of the array and rpos points to the beginning.
  */
  if(spos+1==rpos || (spos+1==MAX && !rpos)) {
    printf("List is full\n");
    return;
  }

  p[spos] = q;
  spos++;
  if(spos==MAX) spos = 0; /* set to the beginning */
}

char *qretrieve(void)
{
  if(rpos==MAX) rpos = 0; /* set to the beginning */
  if(rpos==spos) {
    printf("No more events.\n");
    return NULL;
  }
  rpos++;
  return p[rpos-1];
}

In this version of the program, the queue overflows when the store index is immediately in front of the retrieve index; otherwise, there is still room to insert an event. The queue is empty when rpos equals spos.

Circular queues are probably most often used in operating systems to hold information being tracked and written to disk files or to the console. Circular queues are also used in real-time processing programs that must continue processing information while buffering input/output requests. Many word processors use this technique while reformatting a paragraph or justifying a line. The text being entered is not displayed on the screen until the process is finished. To do this, the application program must check for a keypress while another task is executing. If a key has been pressed, the character entered is quickly placed in the queue, and the process continues. After it finishes, the characters are retrieved from the queue.

To experience this application of circular queues firsthand, let's look at a simple program consisting of two processes. The first process in the program displays the numbers from 1 to 32,000 on the screen. The second process places characters into the queue as they are entered, without displaying them on the screen, until the user presses . The characters entered are not displayed because the first process has priority for screen output. Afterward, the characters are retrieved from the queue and printed.

For the program to work as described above, it must use two functions that are not defined in standard C:_kbhit() and _getch(). The _kbhit() function returns TRUE if a key has been pressed on the keyboard; otherwise it returns FALSE. The _getch() function reads the character entered but does not echo it to the screen. The C standard does not provide functions for checking the state of the keyboard or reading characters without displaying them on the screen, because these functions are operating-system dependent. Nevertheless, most compiler libraries have functions that perform these tasks. The short program given here compiles with the Microsoft compiler.

/* Example of a circular queue used as a keyboard buffer. */
#include 
#include 
#include 

#define MAX 80

char buf[MAX+1];
int spos = 0;
int rpos = 0;

void qstore(char q);
char qretrieve(void);

int main(void)
{
  register char ch;
  int t;

  buf[80] = '\0';

  /* Accept input characters until  is pressed. */
  for(ch=' ',t=0; t<32000 && ch!='\r'; ++t) {
    if(_kbhit()) {
      ch = _getch();
      qstore(ch);
    }
    printf("%d ", t);
    if(ch == '\r') {
      /* Display the contents of the keyboard buffer on the screen
         and free the buffer. */
      printf("\n");
      while((ch=qretrieve()) != '\0') printf("%c", ch);
      printf("\n");
    }
  }
  return 0;
}

/* Placing a character into the queue. */
void qstore(char q)
{
  if(spos+1==rpos || (spos+1==MAX && !rpos)) {
    printf("List is full\n");
    return;
  }
  buf[spos] = q;
  spos++;
  if(spos==MAX) spos = 0; /* set to the beginning */
}

/* Retrieving a character from the queue. */
char qretrieve(void)
{
  if(rpos==MAX) rpos = 0; /* set to the beginning */
  if(rpos==spos) return '\0';

  rpos++;
  return buf[rpos-1];
}

Stacks

A stack (stack) is, as it were, the opposite of a queue, since it works on the principle of "last in, first out" (last-in, first-out, LIFO) . To visualize a stack, recall a stack of plates. The first plate placed on the table will be used last, and the last plate placed on top will be used first. Stacks are often used in system software, including compilers and interpreters.

When working with stacks, the operations of adding and retrieving an element are fundamental. These operations are traditionally called "push onto the stack" (push) and "pop from the stack" (pop) . Therefore, to implement a stack you need to write two functions: push(), which "pushes" a value onto the stack, and pop(), which "pops" a value from the stack. You also need to allocate a memory area that will be used as the stack. For this purpose you can set aside an array or dynamically allocate a block of memory using the C language functions provided for dynamic memory allocation. As with a queue, the retrieval function gets an element from the list and removes it, if it is not stored anywhere else. Below is the general form of the push() and pop() functions working with an integer array. Stacks of another data type can be organized by changing the base data type of the array.

int stack[MAX];
int tos=0;   /* top of stack */

/* Push an element onto the stack. */
void push(int i)
{

  if(tos >= MAX) {
    printf("Stack is full\n");
    return;
  }
  stack[tos] = i;
  tos++;
}

/* Get the top element of the stack. */
int pop(void)
{
  tos--;
  if(tos < 0) {
    printf("Stack is empty\n");
    return 0;
  }
  return stack[tos];
}

The variable tos ("top of stack" ) contains the index of the top of the stack. When implementing these functions, you must take into account the cases when the stack is full or empty. In our case, the sign of an empty stack is tos being equal to zero, and the sign of stack overflow is such an increase in tos that its value points somewhere beyond the last cell of the array. An example of the stack's operation is shown in Table 22.2.

Table 22.2. Stack Operation

Action	Stack contents
push(A)	A
push(B)	B A
push(C)	C B A
pop() retrieves C	B A
push(F)	F B A
pop() retrieves F	B A
pop() retrieves B	A
pop() retrieves A	empty

An excellent example of using a stack is a four-function calculator. Most modern calculators accept the standard notation for expressions, called infix notation , whose general form looks like operand-operator-operand. For example, to add 100 and 200, you need to enter 100, press the "plus" ("+") button, then enter 200 and press the "equals" ("=") button. In contrast, many early calculators (and some of those produced today) use postfix notation , in which both operands are entered first, and then the operator. For example, to add 100 and 200 in postfix notation, you need to enter 100, then 200, and then press the "plus" key. In this method, operands are pushed onto the stack as they are entered. When the operator is entered, the operands are retrieved (popped) from the stack, and the result is placed back onto the stack. One of the advantages of postfix form is the ease of entering long, complex expressions.

The following example demonstrates the use of a stack in a program that implements a postfix calculator for integer expressions. First, the push() and pop() functions need to be modified as shown below. Note that the stack will be placed in dynamically allocated memory rather than in a fixed-size array. Although the use of dynamic memory allocation is not required in such a simple example, we will see how to use dynamic memory to store the stack data.

int *p;   /* pointer to the free memory area */
int *tos; /* pointer to the top of the stack */
int *bos; /* pointer to the bottom of the stack */

/* Push an element onto the stack. */
void push(int i)
{
  if(p > bos) {
    printf("Stack is full\n");
    return;
  }
  *p = i;
  p++;
}

/* Get the top element from the stack. */
int pop(void)
{
  p--;
  if(p < tos) {
    printf("Stack is empty\n");
    return 0;
  }
  return *p;
}

Before using these functions, you need to allocate memory from the free memory area using the malloc() function and assign the address of the start of this area to the variable tos, and the address of its end to the variable bos.

The complete text of the postfix calculator program is given below.

/* A simple four-function calculator. */

#include 
#include 

#define MAX 100

int *p;   /* pointer to the free memory area */
int *tos; /* pointer to the top of the stack */
int *bos; /* pointer to the bottom of the stack */

void push(int i);
int pop(void);

int main(void)
{
  int a, b;
  char s[80];

  p = (int *) malloc(MAX*sizeof(int)); /* get memory for the stack */
  if(!p) {
    printf("Error allocating memory\n");
    exit(1);
  }
  tos = p;
  bos = p + MAX-1;

  printf("Four-function calculator\n");
  printf("Press 'q' to quit\n");

  do {
    printf(": ");
    gets(s);
    switch(*s) {
      case '+':
        a = pop();
        b = pop();
        printf("%d\n", a+b);
        push(a+b);
        break;
      case '-':
        a = pop();
        b = pop();
        printf("%d\n", b-a);
        push(b-a);
        break;
      case '*':
        a = pop();
        b = pop();
        printf("%d\n", b*a);
        push(b*a);
        break;
      case '/':
        a = pop();
        b = pop();
        if(a==0) {
          printf("Division by 0.\n");
          break;
        }
        printf("%d\n", b/a);
        push(b/a);
        break;
      case '.': /* show the contents of the top of the stack */
        a = pop();
        push(a);
        printf("Current value on top of stack: %d\n", a);
        break;
      default:
        push(atoi(s));
    }
  } while(*s != 'q');

  return 0;
}

/* Push an element onto the stack. */
void push(int i)
{
  if(p > bos) {
    printf("Stack is full\n");
    return;
  }
  *p = i;
  p++;
}

/* Get the top element from the stack. */
int pop(void)
{
  p--;
  if(p < tos) {
    printf("Stack is empty\n");
    return 0;
  }
  return *p;
}

In other words, in pushdown (stack) order.

Also: push (onto the stack), place on the stack, put on the stack, set on the stack, lay on the stack, store on the stack.

Also: pop data from the stack, popping from the stack, popping data from the stack, remove from the stack, take from the stack, read from the stack, pull from the stack.

Also called the top.

Other names: infix representation, infix notation.

Other names: postfix notation, reverse Polish notation.

Linked Lists

Queues and stacks have two characteristic features: both data structures have strict rules governing access to the data stored in them, and as a result of retrieval operations the data is, in effect, destroyed. In other words, accessing an element in a stack or queue causes it to be removed, and if that element is not saved somewhere else, it is lost. In addition, both the stack and the queue use a single contiguous area of memory. Unlike a stack or a queue, linked list allows flexible access methods, because each piece of information has a reference to the next data element in the chain. Moreover, the retrieval operation does not remove the data element from the list or destroy it. In principle, a separate special deletion operation must be introduced for this purpose.

Linked lists can be singly linked and doubly linked . A singly linked list contains a reference to the next data element. A doubly linked list contains references to both the following and the preceding elements of the list. The choice of list type depends on the specific task.

Linked lists are often called linked. Singly linked lists are also called singly linked linear lists, one-way lists, as well as one-way chains. Doubly linked lists are also sometimes called doubly linked; in addition, they are called doubly linked linear lists, as well as bidirectional chains.

Singly Linked Lists

In a singly linked list, each information element contains a reference to the next element of the list. Each data element is usually a structure consisting of information fields and a link pointer. Conceptually, a singly linked list looks as shown in Figure 22.2.

Fig. 22.2 Singly linked list

+---------+ +---------+ +---------+ | data | | data | | data | +---------+ +---------+ +---------+ | pointer |--->| pointer |--->| 0 | +---------+ +---------+ +---------+

There are two main ways of building a singly linked list. The first way is to place new elements at the end of the list . The second is to insert elements at specific positions in the list, for example, in ascending order. The algorithm of the element-adding function depends on the way the list is built. Let's start with the simpler way of creating a list by placing elements at the end.

As a rule, the elements of a linked list are structures, since, in addition to the data, they contain a reference to the next element. Therefore, it is necessary to define a structure that will be used in the following examples. Since mailing lists are usually stored in linked lists, a good choice would be a structure describing a mailing address. Its description is shown below:

struct address {
  char name[40];
  char street[40];
  char city[20];
  char state ;
  char zip[11];
  struct address *next; /* reference to the next address */
} info;

The function slstore() shown below creates a singly linked list by placing each successive element at the end of the list. It is passed as parameters a pointer to a structure of type address containing the new entry, and a pointer to the last element of the list. If the list is empty, the pointer to the last element must be equal to zero.

void slstore(struct address *i,
             struct address **last)
{
  if(!*last) *last = i; /* first element in the list */
  else (*last)->next = i;
  i->next = NULL;
  *last = i;
}

Although a list created using the function slstore() can be sorted by a separate operation after it has been created, it is easier to create an ordered list right away by inserting each new element in the correct place in the sequence. Moreover, if the list is already sorted, it makes sense to maintain its order by inserting new elements at the appropriate positions. To insert an element this way, it is necessary to sequentially scan the list until the place for the new element is found, then insert the new entry at the found position and reset the references.

When inserting an element into a singly linked list, one of three situations can arise: the element becomes the first one, the element is inserted between two others, or the element becomes the last one. Fig. 22.3 shows the change in links for each case.

Fig. 22.3. Inserting element new into a singly linked list (where info is the data field)

Inserting at the start of the list +----+ i +----+ |new | s |new | +----+ +----+ | | c .------------| | +----+ o | +----+ n | +----+ +----+ +----+ v | +----+ +----+ +----+ |info| |info| |info| e | |info| |info| |info| \/\/\->+----+ +----+ +----+ r | +----+ +----+ +----+ | |--->| |--->| 0 | t '->| |--->| |--->| 0 | +----+ +----+ +----+ e +----+ +----+ +----+ d Inserting in the middle of the list +----+ i +----+ |new | s |new | +----+ +----+ | | c .---------->| | +----+ o | .--+----+ n | | +----+ +----+ +----+ v | +----+ | +----+ +----+ |info| |info| |info| e | |info| | |info| .->|info| \/\/\->+----+ +----+ +----+ r \/\/\->+----+ | +----+ | +----+ | |--->| |--->| 0 | t '-| | '->| |-' | 0 | +----+ +----+ +----+ e +----+ +----+ +----+ d Inserting at the end of the list +----+ i +----+ |new | s |new |<----------. +----+ +----+ | | | c | 0 | | +----+ o +----+ | n | +----+ +----+ +----+ v +----+ +----+ +----+ | |info| |info| |info| e |info| .->|info| |info| | \/\/\->+----+ +----+ +----+ r \/\/\->+----+ | +----+ +----+ | | |--->| |--->| 0 | t | |-' | |--->| |-' +----+ +----+ +----+ e +----+ +----+ +----+ d

Keep in mind that when inserting an element at the beginning (the first position) of the list, the address of the entry point into the list must also be changed somewhere else in the program. To avoid this complication, a special sentinel element can be kept as the first element of the list. For an ordered list, some special value must be chosen that will always come first in the list, so that the initial element never changes. The drawback of this method is the fairly large amount of memory spent storing the sentinel element, but this is usually not very important.

The following function, sls_store(), inserts structures of type address into a mailing list, keeping it ordered by increasing values in the name field. The function takes pointers to pointers to the first and last elements of the list, plus a pointer to the element being inserted. Because the first or last element of the list may change, the sls_store() function automatically updates the pointers to the beginning and end of the list when necessary. On the first call to this function, the first and last pointers must be equal to zero.

/* Insert into an ordered singly linked list. */
void sls_store(struct address *i, /* new element */
               struct address **start, /* start of the list */
               struct address **last) /* end of the list */
{
  struct address *old, *p;

  p = *start;

  if(!*last) { /* first element in the list */
    i->next = NULL;
    *last = i;
    *start = i;
    return;
  }

  old = NULL;
  while(p) {
    if(strcmp(p->name, i->name)<0) {
      old = p;
      p = p->next;
    }
    else {
      if(old) { /* insert in the middle */
        old->next = i;
        i->next = p;
        return;
      }
      i->next = p; /* insert at the beginning */
      *start = i;
      return;
    }
  }
  (*last)->next = i; /* insert at the end */
  i->next = NULL;
  *last = i;
}

Sequentially traversing the elements of a linked list is very simple: start at the beginning and follow the pointers. Usually the traversal code is so small that it is embedded directly in another routine — for example, a search, delete, or display function. Thus, the function below prints all the names from the mailing list to the screen:

void display(struct address *start)
{
  while(start) {
    printf("%s\n", start->name);
    start = start->next;
  }
}

When calling the display() function, the start parameter must be a pointer to the first structure in the list. The function then moves to the next element, pointed to by the pointer in the next field. The process stops when next is equal to zero.

To retrieve an element from the list, you simply walk the chain of links. Below is an example of a function that searches by the contents of the name field:

struct address *search(struct address *start, char *n)
{
  while(start) {
    if(!strcmp(n, start->name)) return start;
    start = start->next;
  }
  return NULL;  /* no matching element found */
}

Since the search() function returns a pointer to the list element that contains the name being searched for, the return type is declared as a pointer to an address structure. If there is no matching element in the list, zero (NULL) is returned.

Deleting an element from a singly linked list is simple. As with insertion, there are three possible cases: deleting the first element, deleting an element in the middle, deleting the last element. Fig. 22.4 shows all three operations.

Fig. 22.4. Deleting an element from a singly linked list

Deleting the first element of the list +------+ +------+ +------+ |data | |data | |data | \/\/\->+------+ +------+ +------+ | |--->| |--->| 0 | +------+ +------+ +------+ becomes +------+ +------+ +------+ |freed | \/\/\->|data | .->|data | +------+ +------+ | +------+ | 0 | | |-' | 0 | +------+ +------+ +------+ Deleting a middle element of the list +------+ +------+ +------+ |data | |data | |data | \/\/\->+------+ +------+ +------+ | |--->| |--->| 0 | +------+ +------+ +------+ becomes +------+ +------+ +------+ |data | |freed | |data | \/\/\->+------+ +------+ +------+ | | | 0 | .->| 0 | +------+ +------+ | +------+ \______________| Deleting the last element of the list +------+ +------+ +------+ |data | |data | |data | \/\/\->+------+ +------+ +------+ | |--->| |--->| 0 | +------+ +------+ +------+ becomes +------+ +------+ +------+ |data | |data | |freed | \/\/\->+------+ +------+ +------+ | |--->| 0 | | 0 | +------+ +------+ +------+

Below is a function that deletes a given element from a list of address structures.

void sldelete(
     struct address *p, /* previous element */
     struct address *i, /* element to delete */
     struct address **start, /* start of the list */
     struct address **last) /* end of the list */
{
  if(p) p->next = i->next;
  else *start = i->next;

  if(i==*last && p) *last = p;
}

The sldelete() function must be passed pointers to the element being deleted, to the element preceding it, and to the first and last elements. When deleting the first element, the pointer to the preceding element must be equal to zero (NULL). This function automatically updates the start and last pointers if either of them refers to the element being deleted.

Singly linked lists have one big drawback: a singly linked list cannot be read in the reverse direction. For this reason, doubly linked lists are commonly used instead.

Remember that, like a rope, a singly linked list has two ends: a beginning and an end.

Also often called a sentinel marker.

Doubly linked lists

A doubly linked list consists of data elements, each of which holds links to both the next and the previous elements. Fig. 22.5 shows the link organization in a doubly linked list.

Fig. 22.5. Doubly linked lists

+-------+ +-------+ +-------+ |data | .->|data | .->|data | +---+---+ | +---+---+ | +---+---+ | 0 | |-' | | |-' | | 0 | | | |<---| | |<---| | | +---+---+ +---+---+ +---+---+

Having two links instead of one provides several advantages. Probably the most important is that the list can be traversed in either direction. This simplifies working with the list, in particular insertion and deletion. In addition, the user can browse the list in either direction. Another advantage matters only in the case of certain failures. Since the entire list can be traversed not only via the forward links but also via the backward links, if one of the links becomes invalid, the integrity of the list can be restored using the other link.

When inserting a new element into a doubly linked list, there are three possible cases: the element is inserted at the beginning, in the middle, or at the end of the list. These operations are shown in Fig. 22.6.

Fig. 22.6. Operations on doubly linked lists (here new is the element being inserted, and info is the data field)

Inserting an element at the start of the list +-----+ +-----+ | new | \/\/\->| new | +--+--+ t +--+--+ | | | u .----------->|0 | | | | | r | | | | +--+--+ n | +--+|-+ s | _____| | | +-----+ +-----+ +-----+ i | +-----+ | +-----+ +-----+ |info | |info | |info | n \/\/\->|info |<-' |info | |info | \/\/\->+--+--+ +--+--+ +--+--+ t | +--+--+ +--+--+ +--+--+ |0 | |--->| | |--->| |0 | o | | | |--->| | |--->| |0 | | | |<---| | |<---| | | '-| | |<---| | |<---| | | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ Inserting an element in the middle of the list +-----+ +-----+ | new | | new | +--+--+ t +--+--+ | | | u .---------| | | | | | r | .--->| | | +--+--+ n | | +--+A|+ s | | _____|| | | | | +-----+ +-----+ +-----+ i +--V--+ | | +--+-V+ +-----+ |info | |info | |info | n \/\/\->|info | | | |info | |info | \/\/\->+--+--+ +--+--+ +--+--+ t +--+--+ | | +--+--+ +--+--+ |0 | |--->| | |--->| |0 | o |0 | |-' '-| | |--->| |0 | | | |<---| | |<---| | | | | | | | |<---| | | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ Inserting an element at the end of the list +-----+ +-----+ | new | | new | +--+--+ t +--+--+ | | | u | |0 | | | | r | | |<-----------. +--+--+ n +|-+--+ | s |____________ | | | +-----+ +-----+ +-----+ i +-----+ +-----+ +--V--+ | |info | |info | |info | n \/\/\->|info | |info | |info | | \/\/\->+--+--+ +--+--+ +--+--+ t +--+--+ +--+--+ +--+--+ | |0 | |--->| | |--->| |0 | o |0 | |--->| | |--->| | |-' | | |<---| | |<---| | | | | |<---| | |<---| | | +--+--+ +--+--+ +--+--+ +--+--+ +--+--+ +--+--+

Building a doubly linked list is done similarly to building a singly linked list, except that two links must be set. Therefore the data structure must declare two link pointers. Returning to the mailing-list example, for a doubly linked list the address structure can be modified as follows:

struct address {
  char name[40];
  char street[40] ;
  char city[20];
  char state ;
  char zip[11];
  struct address *next;
  struct address *prior;
} info;

The following function, dlstore(), builds a doubly linked list, using the address structure as the base data type:

void dlstore(struct address *i, struct address **last)
{

  if(!*last) *last = i; /* insert the first element */
  else (*last)->next = i;
  i->next = NULL;
  i->prior = *last;
  *last = i;
}

The dlstore() function places new records at the end of the list. As parameters it must be passed a pointer to the data being stored, as well as a pointer to the end of the list, which must be zero (NULL) on the first call.

Like singly linked lists, doubly linked lists can be built using a function that places elements at specific positions, not just at the end of the list. The function dls_store() shown below builds the list, keeping it ordered by increasing names:

/* Building an ordered doubly linked list. */
void dls_store(
  struct address *i,   /* new element */
  struct address **start, /* first element in the list */
  struct address **last /* last element in the list */
)
{
  struct address *old, *p;

  if(*last==NULL) { /* first element in the list */
    i->next = NULL;
    i->prior = NULL;
    *last = i;
    *start = i;
    return;
   }

  p = *start; /* start from the beginning of the list */

  old = NULL;
  while(p) {
    if(strcmp(p->name, i->name)<0){
      old = p;
      p = p->next;
    }
    else {
      if(p->prior) {
        p->prior->next = i;
        i->next = p;
        i->prior = p->prior;
        p->prior = i;
        return;
      }
      i->next = p; /* new first element */
      i->prior = NULL;
      p->prior = i;
      *start = i;
      return;
    }
  }
  old->next = i; /* insert at the end */
  i->next = NULL;
  i->prior = old;
  *last = i;
}

Since the first and last elements of the list may change, the dls_store() function automatically updates the pointers to the beginning and end of the list through the start and last parameters. When calling the function, you must pass a pointer to the data being stored and pointers to pointers to the first and last elements of the list. The first time, the start and last parameters must be equal to zero (NULL).

As with singly linked lists, to retrieve a data element of a doubly linked list you must follow the links until the desired element is found.

When deleting an element of a doubly linked list, three cases can arise: deleting the first element, deleting an element from the middle, and deleting the last element. Fig. 22.7 shows how the links change in each case. The function dldelete() shown below deletes an element of a doubly linked list:

void dldelete(
  struct address *i, /* element to delete */
  struct address **start,  /* first element */
  struct address **last) /* last element */
{
  if(i->prior) i->prior->next = i->next;
  else { /* new first item */
    *start = i->next;
    if(start) start->prior = NULL;
  }

  if(i->next) i->next->prior = i->prior;
  else   /* deleting the last element */
    *last = i->prior;
}

Since the first or last element of the list may be deleted, the dldelete() function automatically updates the pointers to the beginning and end of the list through the start and last parameters. When called, it is passed a pointer to the element being deleted and pointers to pointers to the beginning and end of the list.

Fig. 22.7. Removing an element from a doubly linked list

Removing the first element of the list +-------+ +-------+ +-------+ \/\/\->|data | |data | |data | +---+---+ +---+---+ +---+---+ | 0 | |--->| | |--->| | 0 | +---+-A-+ +-|-+-A-+ +-|-+---+ |________| |________| becomes +-------+ +-------+ +-------+ |deleted| \/\/\->|data | |data | +---+---+ +---+---+ +---+---+ | 0 | 0 | | 0 | |--->| | 0 | +---+---+ +---+-A-+ +-|-+---+ |________| Removing an element from the middle of the list +-------+ +-------+ +-------+ \/\/\->|data | |data | |data | +---+---+ +---+---+ +---+---+ | 0 | |--->| | |--->| | 0 | +---+-A-+ +-|-+-A-+ +-|-+---+ |________| |________| becomes ___________________ | | +-------+ | +-------+ +---V---+ \/\/\->|data | | |deleted| |data | +---+---+ | +---+---+ +---+---+ | 0 | |-' | 0 | 0 |--->| | 0 | +---+-A-+ +---+---+ +-|-+---+ |_____________________| Removing the first element of the list +-------+ +-------+ +-------+ \/\/\->|data | |data | |data | +---+---+ +---+---+ +---+---+ | 0 | |--->| | |--->| | 0 | +---+-A-+ +-|-+-A-+ +-|-+---+ |________| |________| becomes +-------+ +-------+ +-------+ \/\/\->|data | |data | |deleted| +---+---+ +---+---+ +---+---+ | 0 | |--->| | 0 |--->| 0 | 0 | +---+-A-+ +-|-+---+ +---+---+ |________| Fig. 22.7. Removing an element from a doubly linked list

Mailing List Example

To conclude the discussion of doubly linked lists, this section presents a simple but complete program for working with a mailing list. While the program is running, the entire list is stored in memory. However, it can be saved to a file and loaded again for further work.

/* A simple program for processing a mailing list
   illustrating the use of doubly linked lists.
*/
#include
#include
#include

struct address {
  char name[30];
  char street[40];
  char city[20];
  char state ;
  char zip[11];
  struct address *next;  /* pointer to the next record */
  struct address *prior;  /* pointer to the previous record */
};

struct address *start;  /* pointer to the first record in the list */
struct address *last;  /* pointer to the last record */
struct address *find(char *);

void enter(void), search(void), save(void);
void load(void), list(void);
void mldelete(struct address **, struct address **);
void dls_store(struct address *i, struct address **start,
               struct address **last);
void inputs(char *, char *, int), display(struct address *);
int menu_select(void);

int main(void)
{
  start = last = NULL;  /* initialize the start and end pointers */

  for(;;) {
    switch(menu_select()) {
      case 1: enter(); /* enter address */
        break;
      case 2: mldelete(&start, &last); /* delete address */
        break;
      case 3: list(); /* display list */
        break;
      case 4: search(); /* search for address */
        break;
      case 5: save();  /* save list to file */
        break;
      case 6: load();  /* load from disk */
        break;
      case 7: exit(0);
    }
  }
  return 0;
}

/* Get the user's menu choice. */
int menu_select(void)
{
  char s[80];
  int c;

  printf("1. Enter name\n");
  printf("2. Delete name\n");
  printf("3. Display list contents\n");
  printf("4. Search\n");
  printf("5. Save to file\n");
  printf("6. Load from file\n");
  printf("7. Exit\n");
  do {
    printf("\nYour choice: ");
    gets(s);
    c = atoi(s);
  } while(c<0 || c>7);
  return c;
}

/* Enter name and addresses. */
void enter(void)
{
  struct address *info;

  for(;;) {
    info = (struct address *)malloc(sizeof(struct address));
    if(!info) {
      printf("\nOut of memory");
      return;
    }

    inputs("Enter name: ", info->name, 30);
    if(!info->name ) break;  /* end input */
    inputs("Enter street: ", info->street, 40);
    inputs("Enter city: ", info->city, 20);
    inputs("Enter state: ", info->state, 3);
    inputs("Enter zip code: ", info->zip, 10);

    dls_store(info, &start, &last);
  } /* input loop */
}

/* The following function reads a string from the keyboard
   no longer than count and prevents string overflow.
   It also displays a prompt on the screen. */
void inputs(char *prompt, char *s, int count)
{
  char p[255];

  do {
    printf(prompt);
    fgets(p, 254, stdin);
    if(strlen(p) > count) printf("\nString too long\n");
  } while(strlen(p) > count);

  p[strlen(p)-1] = 0; /* remove the newline character */
  strcpy(s, p);
}

/* Build an ordered doubly linked list. */
void dls_store(
  struct address *i,   /* new element */
  struct address **start, /* first element of the list */
  struct address **last /* last element of the list */
)
{
  struct address *old, *p;

  if(*last==NULL) {  /* first element of the list */
    i->next = NULL;
    i->prior = NULL;
    *last = i;
    *start = i;
    return;
  }
  p = *start; /* start from the beginning of the list */

  old = NULL;
  while(p) {
    if(strcmp(p->name, i->name)<0){
      old = p;
      p = p->next;
    }
    else {
      if(p->prior) {
        p->prior->next = i;
        i->next = p;
        i->prior = p->prior;
        p->prior = i;
        return;
      }
      i->next = p; /* new first element */
      i->prior = NULL;
      p->prior = i;
      *start = i;
      return;
    }
  }
  old->next = i; /* insert at the end */
  i->next = NULL;
  i->prior = old;
  *last = i;
}

/* Delete an element from the list. */
void mldelete(struct address **start, struct address **last)
{
  struct address *info;
  char s[80];

  inputs("Enter name: ", s, 30);
  info = find(s);
  if(info) {
    if(*start==info) {
      *start=info->next;
      if(*start) (*start)->prior = NULL;
      else *last = NULL;
    }
    else {
      info->prior->next = info->next;
      if(info!=*last)
          info->next->prior = info->prior;
      else
        *last = info->prior;
    }
    free(info);  /* free memory */
  }
}

/* Search for an address. */
struct address *find( char *name)
{
  struct address *info;

  info = start;
  while(info) {
    if(!strcmp(name, info->name)) return info;
    info = info->next;  /* move to the next address */
  }
  printf("Name not found.\n");
  return NULL;  /* no matching element */
}

/* Display the entire list on the screen. */
void list(void)
{
  struct address *info;

  info = start;
  while(info) {
    display(info);
    info = info->next;  /* move to the next address */
  }
  printf("\n\n");
}

/* This function performs the actual screen output
   of all fields in an address record. */
void display(struct address *info)
{
    printf("%s\n", info->name);
    printf("%s\n", info->street);
    printf("%s\n", info->city);
    printf("%s\n", info->state);
    printf("%s\n", info->zip);
    printf("\n\n");
}

/* Search for a name in the list. */
void search(void)
{
  char name[40];
  struct address *info;

  printf("Enter name: ");
  gets(name);
  info = find(name);
  if(!info) printf("Not found\n");
  else display(info);
}

/* Save the list to a disk file. */
void save(void)
{
  struct address *info;

  FILE *fp;

  fp = fopen("mlist", "wb");
  if(!fp) {
    printf("Cannot open file.\n");
    exit(1);
  }
  printf("\nSaving to file\n");

  info = start;
  while(info) {
    fwrite(info, sizeof(struct address), 1, fp);
    info = info->next;  /* move to the next address */
  }
  fclose(fp);
}

/* Load addresses from a file. */
void load()
{
  struct address *info;
  FILE *fp;

  fp = fopen("mlist", "rb");
  if(!fp) {
    printf("Cannot open file.\n");
    exit(1);
  }

  /* free memory if the list already exists in memory */
  while(start) {
    info = start->next;
    free(info);
    start = info;
  }

  /* reset the start and end pointers */
  start = last = NULL;

  printf("\nLoading from file\n");
  while(!feof(fp)) {
    info = (struct address *) malloc(sizeof(struct address));
    if(!info) {
      printf("Out of memory");
      return;
    }
    if(1 != fread(info, sizeof(struct address), 1, fp)) break;
    dls_store(info, &start, &last);
  }
  fclose(fp);
}

Binary Trees

Finally, we will examine a data structure called a binary tree (binary tree). Although there are many different kinds of trees, binary trees play a special role because, once sorted, they allow very fast insertion, deletion, and search. Each element of a binary tree consists of an information part and pointers to the left and right elements. Figure 22.8 shows a small binary tree.

Fig. 22.8. An example of a binary tree with a height of 3

root ↙ +-------+ |data | +---+---+ left | | | right subtree +---+---+ subtree ↘ ↙ ↘ ↙ +-------+ +-------+ |data | |data | +---+---+ +---+---+ | | | | 0 | | +---+---+ +---+---+ ↙ ↘ ↘ +-------+ +-------+ +-------+ |data | |data | |data | +---+---+ +---+---+ +---+---+ | 0 | 0 | | 0 | 0 | | 0 | 0 | +---+---+

продолжение следует...

Продолжение:

Часть 1 Queues, Stacks, Linked Lists, and Trees
Часть 2 - Queues, Stacks, Linked Lists, and Trees