4.3. Как создать динамическую матрицу?
4.4. Как освобождается память, занятая под динамические структуры?
Лабораторная работа № 12
Динамические структуры данных
1. ЦЕЛЬ РАБОТЫ: изучение ссылочных типов данных, работа со связными списками.
2. ОДНОСВЯЗНЫЕ СПИСКИ
Список – это последовательность структур, каждая из которых содержит ссылку, связывающую её с другой структурой. Для организации списков используются структуры, состоящие из двух смысловых частей – информационной и дополнительной. Информационная часть содержит подлежащую обработке информацию, в дополнительной находятся указатели на последующую или предыдущую структуру списка:
Struct spis { char data[20];
struct spis *next; }; // Указатель на структуру
Здесь при описании указателя используем ещё не описанный объект struct spis *next , который будет служить ссылкой на последующий элемент списка. Самая последняя структура в списке никуда не указывает, т.е. поле next должно иметь значение NULL. Адрес начала (головы) списка хранится в переменной типа указатель *head. На текущую структуру будет указывать *p.
Пример создания и просмотра односвязного списка.
//lab12_1
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct spis
{ char data[20];
struct spis *next;};
struct spis * create(void); //функция создания списка (возвращает адрес его головы)
void list(spis *head); // функция просмотра списка
struct spis *head; // глобальная переменная, адрес головы списка
main()
{ clrscr();
head= create();
list(head);
free(head);}
struct spis * create(void)
{ spis *p, *pred;char c; // pred – указатель на предыдущую структуру
head=pred=p=(spis *)malloc(sizeof(spis)); //выделяем память для первой записи
printf(" fam: "); scanf("%s", p->data);
do { p=(spis *)malloc(sizeof(spis));
printf("\n fam: "); scanf("%s", p->data);
pred->next=p; //ссылка из предыдущей записи на текущую
pred=p; // сохранение адреса текущей записи в поле предыдущей
printf(" Закончить? y/n ");
c=getch();
} while (c!='y');
p->next=NULL;
return head;}
void list(spis *head)
{ spis *p;
p=head;
while (p!=NULL) // пока не конец списка
{ printf("\n fio: %s",p->data);
p=p->next; // продвижение по списку
}
getch();
}
3. ДВУХСВЯЗНЫЕ СПИСКИ
В двухсвязном списке каждая структура содержит две ссылки: на предыдущую и последующую структуры. Таким образом, по списку можно перемещаться от начала к концу и от конца к началу. Для доступа к началу и концу списка должны быть известны их адреса, которые могут сохраняться в глобальных переменных типа указатель.
Пример создания и работы с двухсвязным списком.
//lab12_2
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#include <string.h>
struct spis
{ char data[20];
struct spis *v1; // v1 – указатель на предыдущую структуру
struct spis *v2;}; // v2 – указатель на последующую структуру
void create(void); // создание
void list(spis *); // просмотр
void del(void); // удаление
struct spis *head,*tail; // указатели на начало и конец списка
main()
{
clrscr();
create();
list(head); // просмотр с начала списка
list(tail); // просмотр с конца списка
del();
list(head);
free(head);
}
void create(void)
{ spis *p,*pred;
pred=NULL;
do { p=(spis *)malloc(sizeof(spis));
printf("Фамилия: "); gets(p->data);
p->v1=pred;
if (pred != NULL)
pred->v2=p;
else
head=p;
pred=p;
puts(" Закончить - <esc>");
}
while (getch()!=27);
tail=p;
tail->v2=NULL;
}
void list(spis *p)
{ if (p==head)
while (p != NULL)
{ puts(p->data);
p=p->v2;
}
else if (p==tail)
while ( p!= NULL)
{ puts(p->data);
p=p->v1;
}
else
puts("Неверный адрес ");
getch();
}
void del(void)
{ spis *p,*temp;char f[20]; // f[20] – Строка для удаляемой фамилии
clrscr();
printf("Фамилия: ");gets(f);
p=head;
while (p!=NULL)
{ if (strcmp((p->data),f)==0) // если найдена заданная фамилия
{ if (p==head) // если найденная запись - первая
{ head=p->v2;
head->v1=NULL;
free(p);
p=head;
}
else if (p==tail) // если найденная запись - последняя
{ tail=p->v1;
tail->v2=NULL;
free(p);
p=tail;
}
else // удаление из средины списка
{ p->v2->v1=p->v1;
p->v1->v2=p->v2;
temp=p;
p=p->v2;
free(temp);
}
}
else // если заданная фамилия не найдена – продвигаемся по списку
p=p->v2;
}
}
Чтобы вставить новую структуру в двухсвязный список, также необходимо изменить только значения указателей. Пусть требуется вставить структуру перед найденной по заданному условию ; p – указатель на найденную структуру:
pn=(spis *)malloc(sizeof(spis)); // pn – указатель на новую структуру
gets(pn->data);
// если структура вставляется в средину списка
pn->v1=p->v1;
pn->v2=p;
p->v1->v2=pn;
p->v1=pn;
// если структура вставляется в начало списка
pn->v1=NULL;
pn->v2=p;
p->v1=pn;
head=pn;
// если структура вставляется в конец списка
pn->v1=tail;
pn->v2=NULL;
p->v2=pn;
tail=pn;
4. ВЫПОЛНЕНИЕ РАБОТЫ
4.1. Проанализировать приведенные программы.
4.2. Сформировать
1. Односвязный список
2. Двухсвязный список
и выполнить задание по своему варианту.
Варианты заданий
1. Структура содержит фамилию и 4 оценки. Удалить из списка неуспевающих.
2. Структура содержит фамилию и 4 оценки. Удалить из списка имеющих 2, 3.
3. Структура содержит название книги, автора, год издания. Удалить издания с годом меньше заданного.
4. Структура содержит название книги, автора, год издания. Удалить книги заданного автора.
5. Структура содержит название, цену, количество товара. Удалить из списка заданный товар.
6. Структура содержит название, цену, количество товара. Удалить из списка партии товара, превышающие заданную стоимость.
7. Структура содержит фамилию, год рождения. Добавлять новые записи так, чтобы список был упорядочен по алфавиту.
8. Структура содержит фамилию, год рождения. Добавлять новые записи так, чтобы список был упорядочен по возрасту.
9. Структура содержит название издания, газета или журнал, цена экземпляра. Добавлять новые записи так, чтобы сначала располагались журналы, затем газеты.
10. Структура содержит название издания, газета или журнал, цена экземпляра. Добавлять новые издания так, чтобы названия были упорядочены по алфавиту.
11. Структура содержит фамилию спортсмена, вид спорта, количество очков. Добавлять новые записи так, чтобы информация по каждому виду спорта располагалась последовательно.
12. Структура содержит фамилию спортсмена, вид спорта, количество очков. Добавлять новые записи так, чтобы они были упорядочены по убыванию очков.
5. КОНТРОЛЬНЫЕ ВОПРОСЫ
5.1. Понятие статической и динамической памяти.
5.2. Как создаётся и просматривается односвязный список?
5.3. Как создаётся и просматривается двухсязный список?
5.4. Как удалить структуру из списка?
5.5. Как добавить структуру в список?
СОДЕРЖАНИЕ
Введение …………………………………………………………………………. 3
Лабораторная работа №1. Работа в интегрированной среде BORLAND C
на примере программ линейной структуры……………..……………………….. 3
Лабораторная работа № 3 Программы циклической структуры……….….…. 10
Лабораторная работа № 4 Обработка статических массивов………..………..13
Лабораторная работа № 5 Работа с символьными данными ………..…………15
Лабораторная работа № 6 Структуры…………………………………………...18
Лабораторная работа № 7 Функции..……..………………………….……..…...23
Лабораторная работа № 8 Рекурсии...….…………………………….……..…...26
Лабораторная работа № 9 Программные средства для работы с файлами……28
Лабораторная работа № 10 Обработка бинарных файлов в прямом режиме ..32
Лабораторная работа № 11 Динамические массивы…………………………...37
Лабораторная работа № 12 Динамические структуры данных………………...41