Lecture
As you know, programs consist of two parts - algorithms and data structures. In a good program, these components effectively complement each other. The selection and implementation of the data structure is as important as the procedures for processing the data. The method of organizing and accessing information is usually determined by the nature of the programmed task. Thus, it is important for a programmer to have at his disposal techniques suitable for different situations.
The degree of data type binding to its machine representation is inversely related to its abstraction. In other words, the more abstract the data types become, the more the conceptual idea of how this data is stored differs from the actual, actual way they are stored in computer memory. Simple types, for example, char or int , are closely related to their machine representation. For example, the machine representation of an integer value approximates well the corresponding programming concept. As they become more complex, data types become conceptually less similar to their machine equivalents. So, floating point real numbers are more abstract than integers. The actual representation of the type of float in the machine rather approximately corresponds to the representation of the average programmer about the real number. Even more abstract is the structure belonging to composite data types.
At the next level of abstraction, the purely physical aspects of the data fade into the background due to the introduction of the data engine to data, that is, the mechanism for storing and retrieving information. Essentially, the physical data is associated with an access mechanism that manages the handling of data from the program. This chapter is dedicated to data access mechanisms.
There are four access mechanisms:
Each of these methods makes it possible to solve problems of a particular class. These methods are essentially mechanisms that perform certain operations of storing and retrieving information transmitted to them based on the requests they receive. They all save and receive an element; here, an element means an information unit. This chapter shows how to create such access mechanisms in C. This illustrates some common programming techniques in C, including dynamic memory allocation and the use of pointers.
[1] Other names: store, stack memory, store memory, store type memory, store type storage device, stack storage device.
[2] Other names: chain list, list using pointers, list with links, list on pointers.
[3] Other names: binary search tree.
Queues and stacks have two characteristic features: both data structures have strict rules for accessing the data stored in them, and as a result of the extraction operations, the data are essentially destroyed. In other words, access to an item in a stack or queue causes it to be removed, and if that item is not stored anywhere else, it is lost. In addition, one consecutive section of memory is used in the stack and in the queue. Unlike a stack or a queue, a linked list allows flexible access methods, since each piece of information has a link to the next data element in the chain. In addition, the extraction operation does not delete the item from the list and destroy it. In principle, for this purpose it is necessary to introduce an additional special removal operation.
Linked lists can be single-linked and double-linked [1] . A single linked list contains a link to the next data item. A doubly linked list contains references to both the subsequent and previous elements of the list. The choice of the type of list used depends on the specific task.
[1] Linked lists are often called linked . Singly linked lists are also called simply linked linear lists, unidirectional lists , and unidirectional chains . Biconnected lists are sometimes also called double linked ; in addition, they are called doubly-connected linear lists , as well as bidirectional chains .
In a single-linked list, each information item contains a link to the next list item. Each data element is usually a structure that consists of information fields and a link pointer. The conceptually single-linked list looks like the one shown in fig. 22.2.
Fig. 22.2 Singly linked list
+ --------- + + --------- + + --------- + | data | | data | | data | + --------- + + --------- + + --------- + | pointer | ---> | pointer | ---> | 0 | + --------- + + --------- + + --------- + |
There are two main ways to construct a single-linked list. The first way is to place new items at the end of the list [1] . The second is to insert elements into certain positions in the list, for example, in ascending order. The algorithm for the function of adding an element depends on the method of building the list. Let's start with a simpler way to create a list by putting items at the end.
As a rule, the elements of a linked list are structures, because, in addition to data, they contain a link to the next element. Therefore, it is necessary to define the structure that will be used in the following examples. Since mailing lists are usually stored in linked lists, a structure that describes a postal address is a good choice. Its description is shown below:
struct address {
char name [40];
char street [40];
char city [20];
char state [3];
char zip [11];
struct address * next; / * link to the next address * /
} info;
The function below slstore()creates a single-linked list by placing each item at the end of the list. As parameters, it is passed a pointer to the type structure addresscontaining the new record, and a pointer to the last element of the list. If the list is empty, the pointer to the last element must be zero.
void slstore (struct address * i,
struct address ** last)
{
if (! * last) * last = i; / * first item in the list * /
else (* last) -> next = i;
i-> next = NULL;
* last = i;
}
Although the slstore()list created using the function can be sorted by a separate operation after it has been created, it is easier to immediately create an ordered list by inserting each new item at the right place in the sequence. In addition, if the list is already sorted, it makes sense to maintain its orderliness by inserting new items into the appropriate positions. To insert an element in this way, you need to sequentially browse the list until the location of the new element is found, then insert a new entry into the found position and reinstall the links.
When inserting an element into a single-linked list, one of three situations can arise: the element becomes the first, the element is inserted between the other two, the element becomes the last. In fig. 22.3 the scheme of change of links in each case is shown.
Fig. 22.3. Inserting a new element into a single-linked list (in which info is a data field)
Insert at the top of the list
+ ---- + n + ---- +
| new | p | new |
+ ---- + e + ---- +
| | in .------------ | |
+ ---- + p | + ---- +
a |
+ ---- + + ---- + + ---- + u in | + ---- + + ---- + + ---- +
| info | | info | | info | a | | info | | info | | info |
\ / \ / \ -> + ---- + + ---- + + ---- + e | + ---- + + ---- + + ---- +
|| ---> | | ---> | 0 |t '-> | | ---> | | ---> | 0 |
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
Insert in the middle of the list
+ ---- + n + ---- +
| new | p | new |
+ ---- + e + ---- +
| | in .----------> | |
+ ---- + p | .-- + ---- +
a | |
+ ---- + + ---- + + ---- + u in | + ---- + | + ---- + + ---- +
| info | | info | | info | a | | info | || info | .-> | info |
\ / \ / \ -> + ---- + + ---- + + ---- + e \ / \ / \ -> + ---- + | + ---- + | + ---- +
|| ---> | | ---> | 0 | t '- | |'-> | | - '| 0 |
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
Insert at the end of the list
+ ---- + n + ---- +
| new | p | new | <----------.
+ ---- + e + ---- + |
| | in | 0 | |
+ ---- + p + ---- + |
a |
+ ---- + + ---- + + ---- + ni + ---- + + ---- + + ---- + |
| info | | info | | info | and | info | .-> | info | | info | |
\ / \ / \ -> + ---- + + ---- + + ---- + e \ / \ / \ -> + ---- + | + ---- + + ---- + |
|| ---> | | ---> | 0 |t | | - '| | ---> | | - '
+ ---- + + ---- + + ---- + c + ---- + + ---- + + ---- +
I
|
It should be remembered that when inserting an element at the beginning (first position) of the list, it is also necessary to change the address of entry into the list somewhere else in the program. To avoid these difficulties, you can store a service watchdog element as the first element of the list [2] . In the case of an ordered list, you must select some special value that will always be first in the list so that the initial element remains unchanged. The disadvantage of this method is a rather large memory consumption for storing the watchdog, but usually this is not so important.
The following function sls_store(),, inserts type structures addressinto the mailing list, ordering it by ascending values in the field name. The function accepts pointers to pointers to the first and last elements of the list, as well as a pointer to the inserted element. Since the first or last elements of the list may change, the function sls_store()automatically updates pointers to the beginning and end of the list if necessary. When the function is called for the first time, the pointers firstand lastshould be zero.
/ * Insert in an ordered single-linked list. * /
void sls_store (struct address * i, / * new element * /
struct address ** start, / * start of list * /
struct address ** last) / * end of list * /
{
struct address * old, * p;
p = * start;
if (! * last) {/ * first item 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) {/ * insertion 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;
}
Sequential iteration of the elements of a linked list is very simple: start from the beginning and follow the signs. Usually, the search code fragment is so small that it is inserted into another procedure — for example, a search, delete, or display function. So, the following function displays all the names on the mailing list:
void display (struct address * start)
{
while (start) {
printf ("% s \ n", start-> name);
start = start-> next;
}
}
When calling a function, the display()parameter startmust be a pointer to the first structure in the list. After this, the function proceeds to the next element pointed to by the pointer in the field next. The process stops when it nextis zero.
To get an item from the list, you just need to go through the chain of links. Below is an example of the search function by the field contents name:
struct address * search (struct address * start, char * n)
{
while (start) {
if (! strcmp (n, start-> name)) return start;
start = start-> next;
}
return NULL; / * no matching item found * /
}
Since the function search()returns a pointer to a list item containing the name being searched for, the return type is described as a pointer to a structure address. If there are no matching items in the list, zero ( NULL) is returned .
Removing an item from a single-linked list is easy. As in the case of insertion, three cases are possible: deleting the first element, deleting an element in the middle, deleting the last element. In fig. 22.4 all three operations are shown.
Fig. 22.4. Deleting an item from a single-linked list
Delete the first list item
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
|| ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| deleted | \ / \ / \ -> | data | .-> | data |
+ ------ + + ------ + | + ------ +
| 0 | | | - '| 0 |
+ ------ + + ------ + + ------ +
Remove middle list item
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
|| ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| data | | deleted | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | | 0 | .-> | 0 |
+ ------ + + ------ + | + ------ +
\ ______________ |
Delete the last item in the list
+ ------ + + ------ + + ------ +
| data | | data | | data |
\ / \ / \ -> + ------ + + ------ + + ------ +
|| ---> | | ---> | 0 |
+ ------ + + ------ + + ------ +
turns into
+ ------ + + ------ + + ------ +
| data | | data | | deleted |
\ / \ / \ -> + ------ + + ------ + + ------ +
| | ---> | 0 | | 0 |
+ ------ + + ------ + + ------ +
|
Below is a function that removes the specified
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.