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

Проблема распределения памяти.

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

2 св-ва: время жизни и видимость.

Видимость в основном определяет права доступа к данным из той или иной ф-ии программы.

Время жизни – сколько времени под данные должна распределена память.

На быстроту доступа влияют 2 фактора:

- Хорошо спроектированная логическая модель.

- Грамотная реализация логической модели для выбранной логической.

Существующие способы распределения памяти.

3 способа распределения памяти:

- статический – память под данные выделяется на всё время работы программы. Она освобождается только по окончании работы программы (в С++ это глобальные данные).

-автоматические-память под данные распределяется автоматически в процессе работы программы (С++ локальные данные. Данные внутри отдельных функций).

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

Статическое распределение памяти. Преимущества и недостатки.

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

Автоматическое распределение памяти. Преимущества и недостатки.

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

Динамическое распределение памяти. Особенности динамического распределения памяти. Преимущества и недостатки.

. При динамическом распределении, выделением и освобождением памяти управляет сама программа в процессе своей работы. Время жизни динамически распределенных данных определяется самой программой в процессе ее выполнения. В отличии от заранее определенных данных количество динамических данных жестко не фиксировано. Если программе потребуется динамическое распределение данные она может получить и распределить память под него.Они имеют особенности: 1)эти данные в отличии заранее определены, не имеют имен и доступ осуществляется с помощью указателей 2)память выделяется не во время компиляции, а во время работы.

 

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

Структура односвязного списка: Каждый элемент списка состоит из 2-ух элементов:

-поле данных

-указатель на следующий элемент.

В последнем элементе списка, указатель на следующий элемент = 0.

Для работы необходим указатель на 1-ый элемент списка.

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

Удаление элемента из односвязного списка в программе на языке Си.

Рассмотрим на примере:

Есть 3 элемента списка:

Э1, Э2,Э3

Необходимо удалить Э2.

Запоминаем указатель на след элем, который храниться в Э2.

Удаляем Э2. Переходим в Э1,устанавливаем связь между Э1 и Э3.

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

Если нужно удалить последний элемент, то ук на слде эл в предпоследней элементе присваиваем ноль, и удаляем последний элемент.