2. Исследование операций с элементами связанных списков

1. Добавление нового элемента списка Add().

// функция добавления элементов в список

List* Add(List *cur) // cur - текущий эл-т

{

// выделение памяти для нового элемента списка

List *p=(List*)malloc(sizeof(List)); // p - новый эл-т if(!p) // если выделить память не удалось

{

cout<<" Error !";

return 0;

}

If(!start) // если список пуст

{

start=p; // то новый элемент будет первым

p->next=NULL; // и последним в списке

return p;

}

// если список не пустой, то добавляем элемент

// после текущего и связываем новый элемент с

// последующим

p->next=cur->next;

cur->next=p; // связываем текущий элемент с новым

return p; // возвращаем указатель на новый элемент

}

Динамическое создание новых элементов списка производится с использованием стандартной функции работы с памятью malloc():

List *p=(List*)malloc(sizeof(List));

Рассмотрим подробнее этот оператор. Функция sizeof(List) определяет размер структуры List в байтах. Функция malloc() выделяет блок памяти этого размера. Результат выполнения этой функции преобразуется к типу указатель на структуру List - (List*), то есть возвращает указателю p типа структуры List адрес первого байта выделенной памяти.

2. Удаление элемента из списка Del().

// функция удаления элемента списка

Void Del(List *cur) // cur - указатель удаляемый элемент

{

// создаем указатель для перемещения и

// устанавливаем на начало

List *p=start;

if (cur==start) // если удаляем первый эл-т списка

{

free(start); // освобождаем память

start=start->next;// второй делаем первым

return ;

}

// выполняем, пока не достигли конца списка

// или предшествующего текущему

while (p && p->next!=cur)

p=Next(p); // переходим к следующему

If(!p) // дошли до конца не найдя предшествующего

{

cout << "Не найден элемент";

return ;

}

// связываем предыдущий с последующим

p->next=cur->next;

// освобождаем память текущего

free(cur);

return;

}

3. Переход к следующему элементу списка Next().

// функция перехода к следующему элементу списка

List* Next(List *cur)

{

// возвращаем указатель на следующий элемент списка

return (cur->next);

}

Задание на исследование

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

2. Разработать функцию main(), позволяющую с использованием описанных операций производить работу со связанным списком данных.

Литература

1. Википедия http://ru.wikipedia.org/wiki

2. Павловская Т.А. С/С++. Программирование на языке высокого уровня: Учебник для вузов. - СПб: Питер, 2004.

3. Учебник по C++. Текстовая версия. – myref.ru/preview/74701.html‎

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000.

5. Макоха А.Н Компьютерные науки. Введение в язык программирования Турбо Паскаль: В 3 ч. Ч. I.: Учебное пособие. – Ставрополь: Изд-во СГУ, 1997.

6. Макоха А.Н Компьютерные науки. Введение в язык программирования Турбо Паскаль: В 3 ч. Ч. II.: Учебное пособие. – Ставрополь: Изд-во СГУ, 1997.

7. Макоха А.Н Компьютерные науки. Введение в язык программирования Турбо Паскаль: В 3 ч. Ч. III.: Учебное пособие. – Ставрополь: Изд-во СГУ, 2001.

8. Павловская Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. - СПб: Питер, 2003.

9. Программирование на языке Паскаль: задачник / под ред. Ускоровой О.Ф. – СПб.: Питер, 2003.

10. Учебный практикум по программированию и информатике. / под ред. Ходжаева Г.А. – Ставрополь, 1993.

11. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. / Уч. Пособие - Нолидж. 2002.

12. 9. Turbo Pascal. Практикум 2-е издание / С.А. Немнюгин. – СПб: Питер, 2003.