Сортировка однонаправленных списков

Для ускорения поиска информации в списке, обычно при выводе данных список упорядочивают (сортируют) по ключу.

Проще всего использовать метод сортировки, основанный на перестановке местами двух соседних элементов, если это необходимо. Существует два способа перестановки элементов: обмен адресов и обмен информацией.

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

Функция сортировки для этого случая имеет вид:

void Sort_p(Stack **p) {

Stack *t = NULL, *t1, *r;

if ((*p) -> next -> next == NULL) return;

do {

for (t1=*p; t1-> next-> next! = t; t1=t1-> next)

if (t1-> next-> info > t1-> next-> next-> info){

r = t1-> next-> next;

t1 -> next -> next = r -> next;

r-> next =t1-> next;

t1-> next = r;

}

t= t1-> next;

} while ((*p)-> next -> next! = t);

}

Обращение к этой функции Sort_p(& begin);

2. Второй способ – обмен информации между текущим и следующим элементами. Функция сортировки для этого случая будет иметь вид:

void Sort_info(Stack *p) {

Stack *t = NULL, *t1;

int r;

do {

for (t1=p; t1 -> next! = t; t1 = t1-> next)

if (t1-> info > t1-> next -> info) {

r = t1-> info;

t1-> info = t1-> next -> info;

t1-> next -> info = r;

}

t = t1;

} while (p -> next! = t);

}

3.2. Пример выполнения задания

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

3.2.1. Реализация задания в оконном приложении

Вид формы и полученные результаты представлены на рис. 3.2.

Рис. 3.2

Приведем только тексты функций, соответствующих кнопок:

...

struct Stack { // Декларация структурного типа

int info;

Stack * next;

} *begin, *t;

//------------ Декларации прототипов функций пользователя ----------

Stack* InStack(Stack*, int);

void View(Stack*);

void Del_All(Stack **);

//----------------------------- Текст функции-обработчика кнопки Создать ------------

int i, in, n = StrToInt(Edit1-> Text);

if(begin! = NULL){

ShowMessage(" Освободите память! " );

return;

}

for(i = 1; i < = n; i++){

in = random(20);

begin = InStack(begin, in);

}

Memo1-> Lines-> Add(" Создали " + IntToStr(n) + " -ть." );

//--------------------------- Текст функции-обработчика кнопки Добавить ------------

int i, in, n = StrToInt(Edit1-> Text);

for(i = 1; i < = n; i++){

in = random(20);

begin = InStack(begin, in);

}

Memo1-> Lines-> Add(" Добавили " + IntToStr(n) + " -ть." );

//---------------------------- Текст функции-обработчика кнопки Просмотреть -----

if(! begin){

ShowMessage(" Стек Пуст! " );

return;

}

Memo1-> Lines-> Add(" --- Элементы ---" );

View(begin);

//----------------------------- Текст функции-обработчика кнопки Очистить ---------

if (begin! = NULL) Del_All(& begin);

ShowMessage(" Память освобождена! " );

//---------------------------- Текст функции-обработчика кнопки EXIT -----------------

if(begin! = NULL) Del_All(& begin);

Close();

//--------------- Функция добавления элемента в Стек ------------------------

Stack* InStack(Stack *p, int in) {

Stack *t = new Stack;

t -> info = in;

t -> next = p;

return t;

}

//----------------- Функция просмотра Стека----------------------------------

void View(Stack *p) {

Stack *t = p;

while( t! = NULL) {

Form1-> Memo1-> Lines-> Add(" " + IntToStr( t-> info));

// В консольном приложении будет, например, cout < < " " < < t-> info < < endl;

t = t -> next;

}

//----------------------- Функция освобождения памяти -----------------------

void Del_All(Stack **p) {

while(*p! = NULL) {

t = *p;

*p = (*p) -> next;

delete t;

}

3.2.2. Реализация задания в консольном приложении

Декларацию шаблона структуры, декларации прототипов функций пользователя и их тексты смотрите в предыдущем примере, а листинг основной функции может иметь следующий вид:

…

void main()

{

int i, in, n, kod;

while(true){

cout < < " \n\tCreat - 1.\n\tAdd - 2.\n\tView - 3.\n\tDel - 4.\n\tEXIT – 0.: " ;

cin > > kod;

switch(kod) {

case 1: case 2:

if(kod == 1 & & begin! = NULL){

// Если создаем новый стек, должны освободить память, занятую предыдущим

cout < < " Clear Memory! " < < endl;

break;

}

cout < < " Input kol = "; cin > > n;

for(i = 1; i < = n; i++) {

in = random(20);

begin = InStack(begin, in);

}

if (kod == 1) cout < < " Create " < < n < < endl;

else cout < < " Add " < < n < < endl;

break;

case 3: if(! begin){

cout < < " Stack Pyst! " < < endl;

break;

}

cout < < " --- Stack ---" < < endl;

View(begin);

break;

case 4:

Del_All(& begin);

cout< < " Memory Free! " < < endl;

break;

case 0:

if(begin! = NULL)

Del_All(& begin);

return; // Выход – EXIT

}

Полученные результаты представлены на рисунке

3.3. Индивидуальные задания

Написать программу по созданию, добавлению, просмотру и решению поставленной задачи (в рассмотренных примерах это действие отсутствует) для однонаправленного линейного списка типа СТЕК. Реализовать сортировку стека двумя рассмотренными выше методами.

Решение поставленной задачи описать в виде блок-схемы.

Во всех заданиях создать список из положительных и отрицательных случайных целых чисел.

1. Разделить созданный список на два: в первом – положительные числа, во втором – отрицательные.

2. Удалить из созданного списка элементы с четными числами.

3. Удалить из созданного списка отрицательные элементы.

4. В созданном списке поменять местами крайние элементы.

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

6. В созданном списке поменять местами элементы, содержащие максимальное и минимальное значения.

7. Перенести из созданного списка в новый список все элементы, находящиеся между вершиной и максимальным элементом.

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

9. В созданном списке определить количество и удалить все элементы, находящиеся между минимальным и максимальным элементами.

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

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

12. Созданный список разделить на два: в первый поместить четные, а во второй – нечетные числа.

13. В созданном списке определить максимальное значение и удалить его.

14. Из созданного списка удалить каждый второй элемент.

15. Из созданного списка удалить каждый нечетный элемент.

16. В созданном списке вычислить среднее арифметическое и заменить им все четные значения элементов.

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒