Урок 8 — Однонаправленный линейный список. Динамическое выделение памяти в Си

Однонаправленный линейный список - это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NULL, что говорит о том, что он последний.

Однонаправленный кольцевой список - это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список имеет указатель на начало списка.

Динамическое выделение памятинеобходимо для того, чтобы память выделялась только тогда, когда нам надо, и при необходимости освобождалась.

Динамическая память в сивыделяется функцией new.

Освобождение памяти происходит оператором delete.

По сути говоря, работа с динамической памятью связана с тем, чтобы выделять и очищать память корректно. Чтобы список был связанным, необходимо в самой структуре иметь указатель на следующий список. Для доступа к полям списка используется стрелка (->)

Пример файловой системы (их  атрибуты: имя, расширение, дата создания, размер, атрибуты). Список имеет следующий вид:

struct FDat {               //структура данных
    char Name[20];          //имя
    char r[4];              // расширение
    char d[10];             //       дата 
    int size;               // размер
    char attr[4];           //  атрибут
         FDat *Next; //указатель на следующую структуру
};

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

if (posl == NULL){ //если это первый список
posl = new FDat;
begin = posl; //указатель на начало списка
}
else { posl->Next = new FDat;
posl = posl->Next;
}

Пример задачи: Разработать программу, которая выполняет обработку данных об объектах файловой системы (их  атрибуты: имя, расширение, дата создания, размер, атрибуты). Данные хранить в виде однонаправленного списка в динамически распределяемой памяти. Программа должна поддерживать диалоговый интерфейс с пользователем и обеспечивать следующие функции: 
1. добавление объектов в список; 
2. удаление объектов из списка; 
3. поиск и отображение объектов по заданному признаку; 
4. отображение информационных полей  всех элементов списка. 
Выполнить контроль и мониторинг использования динамически распределяемой памяти. Для общения с пользователем использовать простое меню или общаться с помощью команд.

Решение

Для решения данной задачи, необходимо использовать динамическую память. Разбить программу на функции (функции создания, удаления записи и т. д.).

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

Описание функций

Функция Add добавляет элемент списка, память в куче выделяется с помощью функции new. Функция Del удаляет выбранный элемент списка по его номеру (номер элемента на отображается на экране). Память освобождается функциейdelete. Функция Show выводит на экран созданный список. Функция Find находит искомый элемент (поиск возможен по части имени). Функция Freemem осуществляет очистку памяти занятой списком.

В программе пользователю предоставляется выбор конкретных действий после выполнения этих действий осуществляется возвращение в главное меню. Выход из программы осуществляется при нажатии клавиши Esc, после этого осуществляется очистка памяти и проверка, освободилась ли вся память. Если нет, то выводится предупреждение.

Текст программы

1. Head.h

#ifndef TEXT_H 
#define TEXT_H

#include <iostream.h>
#include <string.h>
#include <alloc.h>
#include <conio.h>
#include <stdlib.h>

struct FDat {               //структура данных
char Name[20];          //имя
char r[4];              // расширение
char d[10];             //       дата 
int size;               // размер
char attr[4];           //  атрибут
FDat *Next;
};

FDat *Add(FDat *, FDat *);
FDat *Del(FDat *, int &);
void Show (FDat *);
void Find (FDat *);
void FreeRam (FDat *);

#endif

2 PROGRAM.cpp

#include "head.h"

FDat *Add(FDat *posl)
{
if (posl == NULL){
posl = new FDat;
}
else { posl->Next = new FDat;
posl = posl->Next;
}

cout << "Vvedite - Name, Racsherenie, Daty, Razmer and Attribut: \n";
cin >> posl->Name >> posl->r >> posl->d >> posl->size >> posl->attr;
posl->Next = NULL;
return posl;
}

FDat *Del(FDat *begin, int &identif )
{
FDat *prom, *begin_new, *next;
int x = 0, j =  0, k = 0, y = 0;
char name[20];

cout << "Mi udalaem!!! \n";

cout <<"Vvedite NAME : ";
cin >> name;
begin_new = prom = next = begin;
while ( begin != NULL) {
for (int i = 0; i<strlen(name); i++)
if (name[i] == begin->Name[i]) j++;
if (j == strlen(name)) {
if (prom == begin) {
begin_new = begin->Next;
prom = begin->Next;
delete begin;
x = 1;
y = 1;
begin = prom;
}
else {
while ( k == 0) {
if (next->Next == begin){
if (next->Next->Next == NULL) {
k = 1;
x = 1;
delete begin;
next->Next = NULL;
begin = NULL;
identif = 1;
begin_new = next;
}
else {
prom = begin->Next;
delete begin;
x = 1;
k = 1;
y = 1;
next->Next = begin = prom;
}
}
next = next->Next;
}
}
}
if (y == 1) begin = NULL;
if (begin != NULL)  begin = begin->Next;
j = 0;
}
if (x == 0)
cout << "NAME nety ... ";
getch();
return begin_new;

}

void Show (FDat *begin)
{
cout << "Prosmotr spiska!!! \n";
cout <<"Name, Racsherenie, Data, Razmer and Attribut\n";
while ( begin != NULL) {
cout <<"\n"<< begin->Name <<"."<<begin->r <<" "<<begin->d <<"  "
<< begin->size <<" byte"<<begin->attr <<" \n ";
begin = begin->Next;
}
getch();

}

void Find (FDat *begin)
{
int x = 0, j =  0;
char name[20];
cout << "poisk!!! \n";
cout <<"Vvedite NAME : ";
cin >> name;
while ( begin != NULL) {
for (int i = 0; i<strlen(name); i++)
if (name[i] == begin->Name[i]) j++;

                                 if (j == strlen(name)) {
cout <<"\n"<< begin->Name <<"."<<begin->r <<" "<<begin->d <<"  "
<< begin->size <<" byte"<<begin->attr <<" \n ";
x = 1;
j = 0;
}

begin = begin->Next;
}
if (x == 0)
cout << "NAME nety ... ";
getch();
}

void FreeRam (FDat *begin)
{
FDat *prom;
cout << "ochistka!!! \n";
prom = begin;
while ( prom != NULL) {
begin = begin->Next;
delete prom;
prom = begin;
}
}

////////////////////////////////////////////////////

int main ()
{
long int mem;
FDat *Begin = NULL, *Posl = NULL, *Dopol;
int ch, iden = 0;               //   наж. клавиша

                mem = farcoreleft(); //     Размер своб. памяти
cout <<"Memory - "<<mem<<"\n";
do {
cout<<" <1> - DOBAVIT ZAPIS \n"
<<" <2> - UDALIT ZAPIS \n"
<<" <3> - PROSMOTR SPISKA \n"
<<" <4> - POISK \n"
<<" <5> - EXIT \n";

                  cin>>ch;       //  {реализация меню}

                  switch (ch) {
case 1 :
cout <<"adress = " <<Begin;
cout <<"adress = " <<Posl;
if (Begin == NULL) {
Begin = Add(Posl);
Posl = Begin;
}
else Posl = Add( Posl);
cout <<"adress = " <<Begin;
break;
case 2 :
Dopol = Del(Begin, iden);
if (iden == 0) Begin = Dopol;
else Posl = Dopol;
break;
case 3 :
Show(Begin);
break;
case 4 :
Find(Begin);
break;
}
} while (ch != 5);

cout <<"\n Memory - " <<farcoreleft()<<"\n";

FreeRam(Begin);           //   очистка памяти
getch();

cout <<"\n Memory - " <<farcoreleft()<<"\n";
if (mem == farcoreleft()) cout <<"Pamat' ne poterana ... ";
else cout << "ERROR!!! Potera Memory!!!";

cout<<" Press key..."<<endl;
getch();

return 0;
}

Результат работы программы: