Просмотр и анализ списка одномерных массивов

За один просмотр списка одномерных массивов, созданного в 2.2, выведем его на экран и найдём количество массивов, среднее значение которых меньше величины d.

В этом случае в начале списка нет фиктивного элемента. Поэтому в отличие от 3.1, начинаем алгоритм просмотра так:

Q2=P2;

Заметим, что при работе с матрицей это соответствует заданию начального значения индекса или номера строки, например: i=0;

Цикл можно организовать разными способами, как и в предыдущем случае при работе со списком целых чисел (см. 3.1).

Внутри цикла можно использовать ещё один цикл для вывода одного элемента списка, то есть одномерного массива:

for (int j=0; j<size; j++)

printf (“%7.2f”, Q2->a [j]);

Здесь же можно анализировать один массив.

Но для этих целей эффективнее составить две функции. Первая выводит одномерный вещественный массив:

void FunOut(float *x, unsigned size)

{ cout<<endl;

for (int j=0; j<size; j++)

printf (“%7.2f”, x[j]); }

Вторая логическая функция возвращает true или false в зависимости от того, удовлетворяет ли массив заданному условию

bool FunAnalis (float *x, unsigned size)

{ //Составить самостоятельно …}

Обратим внимание на то, что из описания функций никак не видно, что они используются для работы с полем списка, то есть в них нигде не записывается ни

Q2->a[j], ни Q2->next->a[j].

Это учитывается при их вызове,который записываем в цикле:

FunOut (Q2->a, m);

if (FunAnalis (Q2->a, m)) count2++;

Для перехода на следующий элемент списка, как и в 3.1, необходимо выполнить тот же оператор присваивания

Q=Q->next;

который не зависит от информационной части элемента списка.

Таким образом, с учётом сказанного получаем следующее:

void FunOut(float *x, unsigned size)

{ …}

bool FunAnalis (float *x, unsigned size)

{ //Составить самостоятельно

…}

void LOOK2 (int &count2)

{ count2=0;

Q2=P2; // Переход на первый реальный элемент списка

while (Q2)

{ FunOut (Q2->a, m); // Вывод информационной части

if (FunAnalis (Q2->a, m)) // Анализ информационной части

count2++;

Q2=Q2->next; // Переход на следующий элемент списка

}

}

§4. Удаление элементов из списка (+).

Обычно в литературе рассматривается удаление одного элемента списка с начала, что имеет место в случае со стеком, или с середины списка. Практика показывает, что определённые трудности возникают, если надо соединить просмотр списка с удалением некоторых элементов в зависимости от условия, налагаемого на поле (поля) информационной части. Например, из первого списка целых чисел (см. 2.1) удалим все отрицательные числа.

Q=P;

cout << " Deleted elements: "<< endl;

while (Q->next)

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

{

// Удаление одного элемента из списка

T=Q->next;

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

T->next=NULL;

// Используем удаляемый элемент, например, выводим

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

// Освобождаем память, занятую под удаляемый элемент

delete T;

}

else

Q=Q->next;

};

Такого рода алгоритмы имеют следующие две важные особенности, которые необходимо учитывать в программе.

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

при наличии фиктивного элемента начинать надо вне цикла с присваивания Q=P, и тогда сможем анализировать и удалять по общему алгоритму первый реальный элемент, то есть в списке он будет вторым после фиктивного; При отсутствии фиктивного элемента первый реальный элемент по общему алгоритму удалить невозможно;

вместо цикла while (Q) необходимо записать цикл while (Q->next), так как последний раз должны ссылаться на предпоследний элемент, а проверять “тупиковый” “правый” последний элемент списка;

в отличие от просмотра в цикле анализируем элемент Q->next->num, а не Q->num.

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

Q=Q->next

записываем не в блоке, в котором удаляли, а под else. Если бы перешли на следующий элемент и после удаления, то элемент, находящийся после удалённого, не проверяется и, значит, не будет удалён, если условие требует этого. Такая ошибка в алгоритме проявится в тесте, в котором надо удалять рядом стоящие элементы. В нашем примере при наличии в числовой последовательности двух рядом стоящих отрицательных чисел первое удалим, а второе даже не проверим, а, значит, и не удалим.

Удаление одного, не первого, элемента списка, выполняется так:

с помощью оператора T=Q->next; “цепляем” удаляемый элемент, то есть его адрес сохраняем в T. Если это не сделать, мы потеряем доступ к этому элементу после изменения адресов;

с помощью оператора

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

“обходим” удаляемый элемент, то есть в адресную часть элемента, предшествующего удаляемому, помещаем адрес элемента, следующего после удаляемого;

наконец, оператор T->next=NULL; “разрывает связь” удаляемого элемента со следующими элементами списка.

После этих трёх операторов физически удаляемый элемент ещё находится в памяти, но связь его с предыдущим и последующим элементами списка разорвана. Его адрес находится в T, поэтому можем использовать удаляемый элемент. В нашем примере его информационную часть выводим на экран с помощью оператора: cout << T->num << " "; В этом месте алгоритма в зависимости от условия задачи может быть запись числа T->num в файл, использование его для создания нового списка и другие варианты.

Физически элемент из памяти удаляется с помощью операции delete T; которая по общим её правилам освобождает память, адрес которой находится в T. То есть освобождается память, занятая одним элементом списка. Напомним, что ячейка T, в которой хранится адрес, из памяти не удаляется и её можно использовать для хранения адреса другого элемента списка.

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

Если фиктивного элемента нет, то с помощью рассмотренного выше алгоритма удалить первый, то есть “левый” заглавный элемент списка мы не сможем. Для этого надо записать другую последовательность операторов, а именно:

T=P;

/* “Зацепили” первый удаляемый элемент, чтобы можно было потом использовать операцию delete. */

P=P->next; // или P=T->next;

/* “Перешли” на следующий второй элемент списка, который станет первым заглавным. Для этого в P поместили адрес пока ещё второго элемента. */

T->next=NULL;

/* Разорвали связь удаляемого первого элемента со следующим.*/

delete T;

/* Физически из памяти удалили первый заглавный элемент */

§5. Вставка элементов в список (+)

Обычно в литературе рассматривается вставка одного элемента списка в начало, что имеет место в случае со стеком, или в любое другое место списка. Практика показывает, что определённые трудности возникают, как и при удалении, если надо соединить просмотр списка со вставкой. Например, в первый список целых чисел (см. 2.1) после каждого чётного числа вставим это же число, увеличенное в 10 раз.

/* Так как в начале списка размещается фиктивный элемент, то переходим на второй, то есть на первый реальный элемент. В начало списка, то есть после фиктивного элемента, по условию задачи вставлять не надо. */

Q=P->next;

while (Q)

/* Анализируем информационную часть (целое число) элемента, адрес которого в Q. Является ли число чётным? */

if (! (Q->num % 2)) { n++;

// Вставка одного элемента. Пояснение дальше в тексте

T=new tsp;

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

T->next=Q->next;

Q->next=T;

/* “Обходим” элемент, который вставили, чтобы после него ничего никогда не вставлять. */

Q=Q->next->next; }

else Q=Q->next;

// Если не вставляли, перешли на следующий элемент

Алгоритм, в котором соединяется просмотр и вставка, имеет следующие важные особенности, которые необходимо учитывать в программе.

Первая особенность заключается в том, что в отличие от удаления необходимо ссылаться непосредственно на элемент, после которого будем вставлять. Отсюда следует:

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

Q=P->next;.

Тогда сможем анализировать, вставлять ли новый элемент после первого реального, который в списке является вторым после фиктивного. При отсутствии фиктивного элемента начинали бы с оператора Q=P;

вместо цикла while (Q->next) необходимо записать цикл while (Q), так как последний раз должны ссылаться и проверять “тупиковый” “правый” последний элемент списка на предмет, вставлять после него, то есть в правый конец списка, или нет;

в отличие от удаления в цикле проверяем, является ли чётным элемент

Q-> num, а не Q-> next->num.

Вторая особенность алгоритма, в котором соединены операции просмотра и вставки, такая. После вставки элемента его, этот новый элемент надо “обойти”, то есть вставленный элемент анализировать не надо. Поэтому в блоке вставки записываем

Q=Q->next->next;

Что получится, если и после вставки, и если не вставляли, записать одно и то же:

Q=Q-> next;?

В нашем примере после элемента, в информационной части которого число, например, 4, вставим элемент с числом 40, которое тоже чётное. Потом, если это число 40 не обойдём, вставим 400, так как 40 — чётное, затем по этой же причине вставим 4000 и т.д. В результате произоёдёт переполнение, то есть получим целое число, большее максимально допустимого числа. В других задачах вставки может не хватить динамической памяти или возникнут другие проблемы.

Только в случае, если элемент не вставляли, выполняем обычный оператор перехода на следующий элемент. Поэтому оператор

Q=Q->next

записываем не в блоке, в котором вставляли, а в блоке под else.

Вставка одного, не первого, элемента списка выполняется так:

1) С помощью оператора

T=new tsp;

выделяем память для вставляемого элемента и его адрес помещаем в T.

2) Получаем информационную часть вставляемого элемента. Здесь может быть получение её по некоторому более сложному алгоритму, ввод с экрана или с файла и другие варианты. В нашем примере предыдущее число умножаем на 10:

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

3) Теперь надо вставить подготовленный элемент в список. Сначала надо “соединить” его со следующим элементом. Для этого определяем адресную часть нового элемента, в которую помещаем адрес, хранящийся в элементе, после которого вставляем:

T->next=Q->next;

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

4) Наконец, к элементу, после которого вставляем, надо присоединить этот новый элемент. Этим самым мы присоединим начинающуюся с него вторую часть списка. Для этого адрес вставляемого элемента T помещаем в адресную часть Q->next того элемента, после которого будет находиться новый: Q->next=T;

Необходимо обратить внимание, что важен порядок двух последних операторов присваивания. Если в начале выполнить Q->next=T;, то потеряем доступ к той части списка, которая будет находиться после вставляемого элемента.

В некоторых алгоритмах требуется уметь вставлять элемент в начало списка. Если позаботились о фиктивном элементе, то для вставки в начало, а реально после фиктивного элемента, то есть не в самое начало, достаточно рассмотренного выше алгоритма вставки. В противном случае, когда фиктивного элемента нет,вставка элемента в начало списка (“слева”) выполняется так, как было показано при создании стека (см.2.2):

/* Резервируем память для одного элемента списка и его адрес помещаем в T */

T=new tsp;

/* Определяем информационную часть нового элемента, например, вводим её, то есть одно число, с экрана */

cin >> T->num;

/* Присоединяем этот подготовленный элемент “справа” в начало списка. Для этого в его адресную часть (T->next) помещаем адрес начала списка P, то есть адрес первого элемента ещё не изменённого списка.*/

T->next=P;

/* После этого наш изменённый список со вставленным в начало новым элементом начинается с T. Но раньше мы договорились, что адрес начала списка будет храниться в P. Поэтому выполняем следующее присваивание адресов. */

P=T;

/* В результате адрес нового элемента T, а это уже адрес начала изменённого списка, помещаем в P. */