русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Урок 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;
}

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

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

Просмотров: 21475

Вы можете --> Заказать программу или Задать вопрос на форуме

Вернуться воглавление


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.