Динамическое распределение памяти, создание списка

Цель работы – овладение навыками использования динамического распределения памяти, создания списков с размещением их в динамической памяти.

 

Задания для самостоятельной подготовки:

1. Изучить:

- возможности языка программирования для динамического распределения памяти;

- принципы создания списков и размещение их в динамической памяти.

2. Разработать алгоритм решения в соответствии с заданием.

3. Составить программу решения задачи.

4. Подготовить тестовый вариант исходных данных. Выполнить на ЭВМ программу с тестовым вариантом.

 

Задание к работе:

Задание А.

Разместить в динамической памяти список элементами которого являются структуры, состоящие из полей в соответствии с вариантом задания из таблицы 16. Вывести информацию из ДП на экран.

 

Задание Б.

Модернизировать программу размещения в ДП списка, таким образом, чтобы список размещался с одновременным упорядочиванием по полю в соответствии с вариантом задания из таблицы 16. Организовать возможность удаления элементов списка по вводимому с клавиатуры значению поля, по которому производилось упорядочивание.

Таблица 16

 

Вариант задания	Условия задачи
	Задание А. - ФИО преподавателя; - предмет; - курс. Задание Б. Упорядочивание по возрастанию курса.
	Задание А. - код товара; - наименование; - стоимость. Задание Б. Упорядочивание по убыванию стоимости.
	Задание А. - артикул; - наименование; - количество. Задание Б. Упорядочивание по наименованию в алфавитном порядке.
	Задание А. - ФИО студента; - группа; - средний балл. Задание Б. Упорядочивание по возрастанию среднего балла.

 

Продолжение таблицы 16

 

Вариант задания	Условия задачи
	Задание А. - ФИО; - год рождения; - должность. Задание Б. Упорядочивание по убыванию года рождения.
	Задание А. - ФИО; - диагноз; - возраст. Задание Б. Упорядочивание по ФИО в обратном алфавитному порядке.
	Задание А. - номер квартиры; - площадь; - ФИО нанимателя. Задание Б. Упорядочивание по возрастанию номера квартиры.
	Задание А. - название книги; - шифр; - количество. Задание Б. Упорядочивание по убыванию количества.
	Задание А. - название города; - численность населения; - площадь. Задание Б. Упорядочивание по убыванию площади.
	Задание А. - тема реферата; - дата сдачи; - количество листов. Задание Б. Упорядочивание по возрастанию количества листов.
	Задание А. - ФИО студента; - тема дипломного проекта; - дата защиты. Задание Б. Упорядочивание по ФИО в алфавитном порядке.
	Задание А. - табельный номер; - ФИО; - номер отдела. Задание Б. Упорядочивание по убыванию табельного номера.

 

 

Продолжение таблицы 16

	Задание А - ФИО; - должность; - возраст. Задание Б. Упорядочивание по ФИО в обратном алфавитному порядке.
	Задание А. - название дика; - шифр; - количество. Задание Б. Упорядочивание по убыванию количества.
	Задание А. - название улицы; - количество домов; - количество квартир. Задание Б. Упорядочивание по убыванию домов

 

Пример выполнения работы

Задание А.

Разместить в динамической памяти список элементами которого являются структуры, состоящие из полей:

- название книги;

- автор;

- год выпуска.

Вывести информацию из ДП на экран.

 

Программа решения задачи имеет вид:

 

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<alloc.h>

#include<string.h>

 

void main()

{

char b,q[20]; // b – для считывания символа, нажатого на клавиатуре,

//q – вспомогательная строка

struct sv { char a[20]; int year; char naz[20]; struct sv* p; }

*nov, *pred; //указатели на структуру sv, состоящую из полей a – автор,

//year – год издания, naz – название книги, p – адрес предыдущего элемента списка

clrscr();

pred=NULL; //адрес предыдущего элемента списка

for(;;)

{

if((nov= (sv*) malloc(sizeof(sv))) ==NULL) //выделение динамической памяти

{

printf("Empety memory!"); //не хватает памяти

return;

}

//Ввод

printf("Название книги:");

gets(nov->naz);

printf("Автор:");

gets(nov->a);

printf("Год выпуска:");

gets(q);

nov->year=atoi(q);

nov->p=pred; //адрес предыдущего элемента списка

pred=nov; //запоминание адреса предыдущего элемента списка

printf("Продолжить? (y/n):");

b=getc(stdin); //считывание символа

if(b=='n' || b=='N')

break; //выход из цикла for

b=getc(stdin); //считывание символа

}

//Вывод

clrscr();

printf("Список из DS:\n");

pred=nov; //встать в начало списка

do

{

printf("***Книга: %-15s ***Автор: %-15s ***Год: %d\n",pred->naz,pred->a,pred->year);

pred=pred->p;

}

while(pred!=NULL); //пока не достигли конца списка

getch();

return; //завершение программы

}

 

Задание Б.

Модернизировать программу размещения в ДП списка, таким образом, чтобы список размещался с одновременным упорядочиванием по наименованию в обратном алфавитному порядке. Организовать возможность удаления элементов списка по вводимому с клавиатуры значению поля, по которому производилось упорядочивание.

 

Программа решения задачи имеет вид:

 

 

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<alloc.h>

#include<string.h>

 

void main()

{

char b,q[20]; // b – для считывания символа, нажатого на клавиатуре,

//q – вспомогательная строка

struct sv { char a[20]; int year; char naz[20]; struct sv* p; }

*nov, *nac, *tec; //указатели на структуру sv, состоящую из полей a – автор,

//year – год издания, naz – название книги, p – адрес предыдущего элемента списка

clrscr();

if((nac= (sv*) malloc(sizeof(sv))) ==NULL)

{

printf("Empety memory!");

return;

}

//Ввод в первый элемент списка

 

printf("Название книги:");

gets(nac->naz);

printf("Автор:");

gets(nac->a);

printf("Год выпуска:");

gets(q);

printf("\n");

nac->year=atoi(q);

nac->p=NULL;

 

for(;;)

{

 

if((nov=(sv*) malloc(sizeof(sv))) ==NULL) //выделение динамической памяти

{

printf("Empety memory!"); //на хватает памяти

return;

}

//Ввод во все следующие элементы списка

printf("Название книги:");

gets(nov->naz);

printf("Автор:");

gets(nov->a);

printf("Год выпуска:");

gets(q);

nov->year=atoi(q);

//определение места для вставки нового элемента списка согласно упорядочиванию

if(strcmp(nac->naz,nov->naz)<0)

{ //вставка в начало списка

nov->p=nac;

nac=nov;

}

else

{

tec=nac;

while(strcmp(tec->naz,nov->naz)>0 && tec->p!=NULL)

tec=tec->p;

//вставка в середину или конец списка

nov->p=tec->p;

tec->p=nov;

}

printf("Продолжить? (y/n):");

b=getc(stdin); //считывание символа, нажатого на клавиатуре

if(b=='n' || b=='N')

break; //

b=getc(stdin);

}

 

//вывод

clrscr();

printf("Список из DS:\n");

tec=nac; //встать в начало списка

do

{

printf("***Книга:%-15s ***Автор:%-15s ***Год:%-4d\n",tec->naz,tec->a,tec->year);

tec=tec->p;

}

while(tec!=NULL); //пока не конец списка

 

//Удаление

b=getc(stdin);

for(;;)

{

printf("Удалить? (y/n)");

b=getc(stdin);

if(b=='n' || b=='N')

break; // выход из цикла

b=getc(stdin);

printf("Удалить книгу: ");

gets(q); //чтение названия удаляемой книги

tec=nac; //встать в начало списка

if(strcmp(tec->naz,q)==0) //если названия совпадают

{

nac=nac->p; //удаление в начале списка

}

else

{

tec=nac; //встать в начало списка

//поиск

while(tec->p!=NULL && strcmp(tec->p->naz,q)= =0)

tec=tec->p;

tec->p=tec->p->p; //удаление

}

if(!nac) //список пуст

{

clrscr();

printf("Список пуст\n");

break;

}

//вывод

 

clrscr();

printf("Список из DS:\n");

tec=nac; //встать в начало

do

{

printf("***Книга:%-15s ***Автор:%-15s ***Год:%-4d\n",tec->naz,tec->a,tec->year);

tec=tec->p;

}

while(tec!=NULL); //пока не конец списка

}

getch();

return; //завершение программы

}

 

Контрольные вопросы

1. Для чего используется динамическое распределение памяти?
2. Перечислить модели памяти, их отличия.
3. Где выделяется память при динамическом распределении памяти для различных моделей памяти?
4. Перечислить функции динамического распределения памяти в изучаемом языке программирования.
5. Принципы организации связных списков? Каким образом разместить список в динамической памяти?