Динамическая память

1. Динамическая память

Лекция 1

2. Размерности

1 байт = 8 бит
1 параграф = 24 байт
1 Кб = 210 байт
1 Мб = 220 байт
1 сегмент = 64 Кб = 216 байт

3. Модель оперативной памяти ПК

адрес = (сегмент, смещение)
Абсолютный адрес =
сегмент *16 + смещение
Пример
240E
Смещение
F10A[0]
Адрес = (F10A, 240E)
Абс. адрес = F10A0 + 240E
+
Сегмент
…
0
F10A0
240E
F34AE

4. Модель карты памяти

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

5. Сравнение статической и динамической памяти

Параметры сравнения
Статические переменные
Динамические
переменные
Способ распределения
памяти
Автоматическое
(во время компиляции)
Управляется программой
Место расположения
Глобальные переменные
– в сегменте кода,
локальные – в сегменте
стека
В динамической памяти
(куче)
Способ доступа
По имени
(идентификатор)
По адресу
(указатель на место
расположения в памяти)

6. Указатель

Указатель – это переменная, значением
которой является адрес области памяти
Указатель
Адрес
Переменная
Значение

7. Описание указателей

На Паскале
var
p : pointer;
t : ^integer;
n: integer;
…
n := t^;
На Си
int *t, n;
…
n = *t; //разыменование
t = &n; //адрес

8. Указатели и массивы

int b[5] = {1, 1};
int *p, i;
for (i = 2; i < 5; i++)
b[i] = b[i-1]+b[i-2];
//----------------for (p = b+2; p != b+5; p++)
*p = *(p-1) + *(p-2);
b
p
1
1
2
3
5
0
1
2
3
4

9. Строки в Си

#include <string.h>
…
char S[100];
int l;
strcpy (S, ”test”);
l = strlen(S);
‘t’ ‘e’ ‘s’ ‘t’
0
S
1
2
l
3
4
4
…
0
5
97
98
99

10. Функции работы с динамической памятью

Функции
Прототипы и краткое описание
malloc
void * malloc ( unsigned s);
Возвращает указатель на начало области динамической памяти
длиной в s байт. При неудачном завершении возвращает значение
NULL.
calloc
void * calloc (unsigned n, unsigned m);
Возвращает указатель на начало области обнуленной динамической
памяти , выделенной для размещения n элементов по m байт каждый.
При неудачном завершении возвращает значение NULL.
realloc
void * realloc (void * bl, unsigned ns);
Изменяет размер блока ранее выделенной памяти до размера ns байт.
bl - адрес начала изменяемого блока. Если bl = NULL (память раньше не
выделялась), то функция выполняется как malloc.
free
void * free (void *bl);
Освобождает ранее выделенный участок динамической памяти, адрес
первого байта которого равен значению bl.

11. Пример работы с динамической памятью

#include <stdio.h>
#include <stdlib.h>
int main() {
float *t;
int i,n;
printf(”\nn=”);
scanf(”%d”,&n);
t= (float *)malloc(n*sizeof(float));
for(i=0;i<n;i++) {
printf (”x[%d]=”, i);
scanf(”%f”,&(t[i]));
}
for(i=0;i<n;i++) {
if (i % 2 == 0) printf (”\n”);
printf(”\tx[%d]=%f”, i, t[i]);
}
free (t);
return 0;
}

12. Пример 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char *s, *s1;
int n;
s = (char *)malloc(100);
scanf(”%s”, s);
for(n=0;s[n]; n++);
s1 = (char *)malloc(n*2 + 1);
strcpy (s1, s);
strcpy (s1 + n, s);
printf(”%s”, s1);
free (s);
free (s1);
return 0;
}

13. Структуры в Си

struct <имя типа> { поля}
struct student {
char * name;
int age;
};
struct student x, y, *z;
…
x.age = 19;
x.name = (char *) malloc (20);
scanf (“%s”, x.name);
z = &x;
printf (“age = %d\n”, (*z).age);
printf (“age = %d\n”, z->age);

14. Списки. Определения.

Список – структура данных, представляющая собой
конечную последовательность элементов.
Элемент списка:
Данные
Связь

15. Односвязные списки

Односвязный список – это список, у элементов которого
существует связь, указывающая на следующий элемент
списка ( односторонняя связь).
Голова
Хвост

16. Описание списка на Си

struct list {
int data;
//информационное поле, данные
struct list *next; // указатель на следующий элемент списка
};
/* Описание переменных: */
struct list *head=NULL; // - указатель на голову списка
struct list *p, *t;

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

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 5;
p->next = NULL;
head = p;
head
p
5
NULL

18. Вставка нового элемента в начало списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 3;
p->next = head;
head = p;
head
p
5
3
NULL

19. Вставка нового элемента в конец списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 10;
p->next = NULL;
t = head;
while (t->next != NULL)
t = t->next;
t->next = p;
head
3
5
NULL
t
p
10
NULL

20. Вставка нового элемента в середину списка

p = (struct list*) malloc( sizeof( struct list ) );
p->data = 4;
t = head;
while (t->next ->data != 5) //вставка перед элементом с заданным свойством
t = t->next;
p->next = t->next;
t->next = p;
head
3
5
t
p
4
10
NULL

21. Удаление элемента из списка

t = head;
while (t->next ->data != 5)
t = t->next;
p = t->next;
t->next = p->next;
free(p);
head
3
5
t
p
4
10
NULL

22. Лабораторная работа

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

23. Циклические списки

Циклический список – это список, в котором связь
последнего элемента указывает на первый или
один из других элементов этого списка.
head
Задача: Для заданного односвязного списка определить,
является ли он циклическим.
Преобразовывать список нельзя.

24. Двусвязные списки

Двусвязные списки – это списки, элементы которых
имеют по две связи, указывающие на предыдущий
и следующий элементы.
NULL
head
typedef struct list {
int data;
struct list *prev;
struct list *next;
} List;
NULL

25. Удаление элемента из двусвязного списка

List *del (List *p) { //возвращает указатель на следующий элемент списка
List *pp,*pn;
if (p == NULL) return NULL;
pp = p->prev;
pn = p->next;
if (pp) pp->next = pn;
if (pn) pn->prev = pp;
free(p);
return pn;
}
pp
p
pn

26. Иерархические списки

Это списки, значениями элементов которых являются
указатели на другие списки (подсписки).
NULL
head