Сравнительный анализ списков

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

Информационная часть элемента списка

С чем сравниваем

1) Одно число. 2) Один символ. 3) Одномерный статический массив. Одномерный статический массив. 4) Строка. 5) Вложенная структура или несколько полей.

Одномерный статический или динамический числовой массив. Одномерный статический или динамический символьный массив, то есть строка. Полностью статическая матрица. Количество строк и количеством элементов в каждой строке — константы. Частично динамическая матрица. Количество строк — переменная, а количество элементов в каждой строке — константа. Статический или динамический массив строк. Статический или динамический массив структур.

Отметим для начала, что если в инфомационной части элемента списка находится одно число, то смысла в таком списке практически нет. Это связано с тем, что в отличие от массива в два раза увеличивается память, динамически выделяемая под элементы списка, так как рядом с каждым числом в памяти должен находиться адрес следующего элемента списка. Просмотр и анализ также занимают больше времени, так как числа в отличие от массива располагаются не рядом, а “разбросаны” по всей динамической памяти. Использовались такие списки в этой главе только по той причине, чтобы не увеличивать объём некотрых программ при работе с информационной частью элемента списка, а больше внимания уделить работе с его адресной частью, что является более сложным. Аналогичное замечание можно высказать и для второго случая (см. таблицу).

Сравним список, в информационной части элемента которого одномерный статический массив, со статической матрицей с одинаковым количеством элементов в каждой строке.

Память для элементов списка выделяется на этапе выполнения, то есть динамически, а для матрицы — на этапе компиляции. При необходимости память для элементов списка можем освободить (см удаление). Для статической матрицы это сделать нельзя, память занята на всё время выполнения функции (или блока). В этом преимущество списков независимо от характера задачи.

Плохо, что список занимает больше памяти, чем матрица, так как рядом с каждой строкой матрицы (одномерным массивом) в списке находится адрес её следующей строки. Кроме этого, если в статической матрице все её элементы находятся рядом, то в списке это не так, строки располагаются на определённом расстоянии одна от другой. Во время создания или вставки элементов память выделяется там, где есть непрерывный участок требуемого объёма для размещения всей строки матрицы. Поэтому обычный просмотр и анализ строк матрицы (вывести на экран, переписать строки в файл, найти количество строк с некоторым условием и т. п.) выполняется в списке медленнее, чем в обычной матрице, так как необходимо время, чтобы по адресу найти следующий элемент списка, то есть строку матрицы.

Преимущество списков проявляется, если надо корректировать матрицу, в частности, удалять или вставлять строки. Какие проблемы возникают, например, при удалении строки статической матрицы? Для этого надо физически переместить поэлементно несколько строк “вверх”, на что требуется относительно немалое время (см. 1 семестр). При работе со списком, как было показано выше, достаточно было изменить лишь несколько адресов, а строки матрицы в памяти остаются на своих местах и никуда не перемещаются. Кроме этого, после удаления строки из списка занятую под неё память можно освободить, чего нельзя сделать при работе со статической матрицей.

Аналогичное преимущество при использовании списков имеет место и при вставке строк. Поэтому можно сделать следующее заключение. В задачах, в которых требуется вставлять, удалять или переставлять строки, эффективнее использовать списки. При обычном просмотре и анализе без такого рода корректировки достаточно использовать обычный двумерный массив, если, конечно, позволяет объём памяти.

Упражнения, тесты.

1. Пусть объявлена структура для списка:

struct tsp { int num;

tsp *next; } *P, *Q;

Какие из следующих фрагментов допустимы?

1) P=new tsp; P.num=5;

2) P=new tsp; int x=5; P->num=&x;

3) P=new tsp; cin>>(P->num);

4) P=new tsp; P->num=44; Q=P->next; Q->num=P->num;

1. Пусть объявлена структура для списка(см 1) и создан следующий список:

–10 —> 22 —> -3 —> 44 —> 50.

При этом в P — адрес первого элемента с числом -10. Что будет выведено в каждом из приведенных правильных вариантов? Если есть ошибки, указать, в каких вариантах.

1) cout<<P->next->num;

2) Q=P->next; cout<<Q->num;

3) Q=P->next; Q->num=P; cout<<Q->num;

4) Q=P->num; cout<<Q->num;

5) Q=P; Q=Q->next; cout<<Q->next->num;

6) Q=P; Q->next->num=P->num; cout<<Q->num;

3. Пусть объявлена структура для списка (см. 1) и создан список (см.2). При этом в P — адрес первого элемента с числом -10. Дан также код.

Q=P->next; //1

P->next=NULL; //2

delete(P); //3

P=Q; //4

cout<<P->num<< “ “<<Q->num; //5

Что будет выведено в результате его выполнения? Если есть ошибки, указать, в каких строках.

4. Пусть объявлена структура для списка (см. 1) и создан список (см.2). При этом в P — адрес первого элемента с числом -10. Дан также код:

Q=P; //1

while (Q->next->next) Q=Q->next; //1

T=Q->next; //2

Q->next=T->next; //3

delete(T); //4

Q=P; //5

while (Q) //6

{ cout<<Q->num<<” “; //7

Q=Q->next; } //8

cout<< P->num; //9

Что будет выведено в результате его выполнения? Если есть ошибки, указать, в каких строках.

5. Пусть объявлена структура для списка (см.1) и создан список без фиктивного элемента: –10 —> 22 —> -3 —> -44 —> -50 —>66 —> -70. При этом в P — адрес его первого элемента. Дан также код:

Q=P; while (Q->next)

if (Q->next->num < 0)

{ T=Q->next;

Q->next=Q->next->next;

T->next=NULL;

cout << T->num << " ";

delete T;

}

Q=Q->next;

};

Что будет выведено? Какой список получится после выполнения приведенного кода?

6. Пусть объявлена структура для списка (см.1) и создан список (см. 2). Дан также код:

Q=new tsp; cin>>Q->num;

Q->next=P; P=Q;

while (P!=NULL) { cout<<P->num;

P=P->next;

}

cout<<Q->num;

Что будет выведено в результате его выполнения, если введём число 6?

7. Пусть объявлена структура для списка (см.1) и создан следующий список без фиктивного элемента:

10 —> 22 —> 3 —> 44 —> 50 —> 66 —> 70.

При этом в P — адрес его первого элемента c числом 10. Дан также код:

Q=P->next;

while (Q)

{ if (Q->num%10)

{ n++;

T=new tsp;

T->num=Q->num*10;

T->next=Q->next;

Q->next=T;

Q=Q->next->next; }

Q=Q->next; }

Какой список получится после выполнения приведенного кода (записать последовательность чисел)?

8. Сравним список, информационная часть элемента которого содержит одномерный статический массив фиксированной размерности, со статической матрицей, количество строк и столбцов которой — константы, и в каждой строке которой одинаковое количество элементов. Выберите правильные утверждения:

1) Память для элементов списка выделяется на этапе компиляции.

2) Память для элементов статической матрицы, количество строк и столбцов которой — константы, выделяется на этапе выполнения.

3) При необходимости память для элементов списка можно освободить.

4) Для статической матрицы освободить память нельзя, она занята на всё время выполнения функции (или блока).

5) Список занимает меньше памяти, чем матрица.

6) В списке все его элементы находятся рядом.

7) В задачах, в которых требуется вставлять, удалять или переставлять строки матрицы, эффективнее использовать списки.

8) При обычном просмотре и анализе строк матрицы без их вставки, удаления или перестановки эффективнее использовать обычный двумерный массив, если, конечно, позволяет объём памяти.