Линейный список в динамической памяти. Структура памяти языка Си

Линейный список в виде одномерного массива

Линейный список
в динамической памяти

Структура памяти языка Си

Статические и динамические переменные

Функции для динамического распределения памяти
void *malloc(size_t size);
void *free(void *p);
char *c;
// Выделить память 10 байт
c=(char *)malloc(10);
// или
c=(char *)malloc(sizeof(char)*10);

Использование функций malloc() и free()

Пример 1. Создание массива
в динамической памяти
int *p, i;
p = (int *) malloc(100 * sizeof(int));
if (p==NULL)
{
printf("Недостаточно памяти\n");
return 0;
}
for (i = 0; i < 100; i++)
*(p+i) = i;
for (i = 0; i < 100; i++)
printf("%d ", p[i] );
free(p);

Общее представление о списке в динамической памяти

Описание типа для построения линейного списка

Создание элементов в динамической памяти
struct element *nach, *pred, *tek;
nach=(struct element *)malloc(sizeof(struct element));

Обращение к полям структуры через указатель (в статической памяти)
struct date {
int day;
char month[10];
int уear; };
struct date this_day, *db;
db = &this_day;
. . .
(*db).day = 25;
db -> day = 25;

Связывание элементов
pred -> link=tek; // обращение к полю link
// структуры через указатель

Переприсваивание указателей
pred=tek; // pred и tek указывают на
// один и тот же элемент

Алгоритм построения списка в прямом порядке

Продолжение. Алгоритм построения списка
в прямом порядке

Глобальные описания
struct element
{
int d;
struct element *link;
};
struct element *nach; // Указатель на
// начало списка

Шаг по связи
tek = tek->link;

Просмотр списка

Пример 2. Функция просмотра списка:
void prosmotr()
{
struct element *tek;
tek = nach; // Встали на начало списка
while(tek != NULL) // Пока не конец списка
{
printf("%d", tek->d);
tek = tek->link; // Шаг по связи
}
}

Добавление элемента в начало списка
1. Создать новый элемент nov.
Ввести информационную часть nov->d.
2. Построить связь:
nov->link=nach;
3. Новый элемент сделать начальным:
nach=nov;

Добавление элемента в середину списка
1. Заполнить связь 2 у элемента nov:
nov->link=tek->link;
2. Соединить tek и nov (связь 1):
tek->link=nov;

Добавление элемента в конец списка
1. pred->link=NULL;
2. free(pos);

Пример 3. Перемещение по списку
Фрагмент программы:
tek=nach;
while(tek->d != 'c')
tek=tek->link;
printf("%s", tek->d);

Пример 4. Перемещение по списку
Что будет выведено на экран в результате выполнения фрагмента программы:
tek=nach;
for(i=1; i<=4; i++)
tek=tek->link;
printf("%s", tek->d);