Односпрямований лінійний список - це список, який має покажчик на початок списку, при цьому кожен список має покажчик на наступний список, а останній список приймає покажчик 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;
}
Результат роботи програми:
