Списки. Операции над односвязными списками.

Списки.

Рассмотрим структуру

typedef int ETYPE;

struct elem { ETYPE data;

elem *next;

};

 

Назовем data - информационным элементом. У нас он - типа int, но может быть любого сложного необходимого нам типа ETYPE.

 

Указатель next указывает на объект типа elem. Объекты типа elem можно упорядочить с помощью указателя next следующим образом (Рис. 1):

Рис. 1: Структура односвязного списка

Такая структура данных называется однонаправленным, или односвязным списком, иногда - цепочкой.

 

Объекты типа elem из этого списка называют элементами списка или звеньями. Каждый элемент цепочки, кроме последнего, содержит указатель на следующий за ним элемент. Признаком того, что элемент является последним в списке, служит то, что член типа elem* этого звена равен NULL.

 

Вместе с каждым списком рассматривается переменная, значением которой является указатель на первый элемент списка. Если список не имеет ни одного элемента, т.е. пуст, значением этой переменной должен быть NULL.

 

Рассмотрим методы работы с такими списками.

 

Пусть переменные p, q имеют тип elem*:

 

elem *p, *q;

 

Построим список из двух элементов, содержащих числа 12 и -8.

 

Значением переменной p всегда будет указатель на первый элемент уже построенной части списка. Переменная q будет использоваться для выделения с помощью new места в памяти под размещение новых элементов списка.

 

Выполнение оператора

 

p = NULL;

 

приводит к созданию пустого списка. После выполнения операторов

 

q = new elem; q->data = -8; q->next = p; p = q;

 

имеем список, состоящий из одного элемента, содержащего число -8 в информационной части. Переменные p, q указывают на этот элемент

 

(рис. 2):

Рис. 2. Создание списка а) из одного элемента (сплошные линии);

б) из двух элементов (пунктир)

Далее, выполнение операторов (рис. 3)

 

q = new elem; q->data = 12; q->next = p; p = q;

 

приводит к тому, что в начало цепочки добавляется новый элемент, одержащий число 12. В результате получится список, изображенный на рис. 3. Значением переменных p и q снова является указатель на первый элемент списка:

Рис. 3. Список из двух элементов

Фактически мы рассмотрели операцию включения нового элемента в начало, или голову списка, а формирование списка состоит в том, что начинают с пустого списка и последовательно добавляют в начало элементы.

 

Пример:

 

Построим список, элементы которого содержат целые числа

1, 2, 3,..., n.

 

p = NULL;

while (n > 0){ q = new elem;

q->data = n; q->next = p; p = q;

n - -;}

 

Заметим, что при включении элемента в голову списка порядок элементов в списке обратен порядку их включения.

 

Основная операция при работе со списком - это проход по списку.

 

Предположим, что с каждым информационным элементом звена нужно выполнить некоторую операцию, которая реализуется функцией void P(ETYPE). Пусть также опять p указывает на начало списка. Тогда проход по списку осуществляется так:

 

q = p;

while (q) {

P (q->data);

q = q->next; }

 

Пример. Во входном файле num.dat находится последовательность, содержащая нечетное количество целых чисел.

 

Напишем программу, в результате выполнения которой выводится число, занимающее в этой последовательности центральную позицию.

#include < fstream.h > // Для работы с файлом ввода.

#include < stdlib.h >

struct elem { int data;

elem *next; };

void main (){

ifstream infile ("num.dat");

/* Создается входной поток с именем infile для чтения данных, разыскивается файл с именем "num.dat"; если такой файл не существует, то конструктор завершает работу аварийно и возвращает для infile нулевое значение.

*/

if (!infile) {

cout << "Ошибка при открытии файла num.dat!\n"; exit (1); }

elem *p = NULL, *q;

int j = 0;

while (infile.peek()!= EOF) {

/* Функция-член peek() класса ifstream возвращает очередной символ из входного потока infile, фактически не извлекая его оттуда. Если встретится конец файла, то будет возвращено значение EOF, т.е. -1.

*/

q = new elem;

infile >> q->data;

q->next = p; p = q;

j ++;

}

for (int i = 1; i <= j/2; i++)

q = q->next;

cout << q->data << "\n";

}