Каталог файлов на Visual C++

Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) -- на последний.

Стек -- структура данных с методом доступа к элементам "последним пришел -- первым вышел". Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.

Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху), выталкивание (pop) -- также только из вершины стека, при этом второй сверху элемент становится верхним.

Очередь -- структура данных с дисциплиной доступа к элементам "первый пришёл -- первый вышел". Добавление элемента возможно лишь в конец очереди, выборка -- только из начала очереди.

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

Стандартные функции для работы с динамической памятью

Для работы с динамическими объектами в Си есть функции стандартной библиотеки malloc и free. Для их использования нужно включить в программу заголовочный файл <stdlib.h>. В этом файле также вводится обозначение NULL для пустого (нулевого) указателя.

void *malloc (size_t size)

malloc возвращает указатель на место в памяти для объекта размера size. Выделенная память не инициализируется. Если память отвести не удалось, то результат работы функции -- NULL. (Тип size_t -- это беззнаковый целый тип, определяемый в файле <stddef.h>, результат операции sizeof имеет тип size_t). Как правило, обобщенный указатель, возвращаемый этой функцией, явно приводится к указателю на тип данных. Например, создать динамическую переменную типа double и присвоить значение, возвращаемое malloc, переменной dp -- указателю на double, можно с помощью выражения

dp = (double*) malloc (sizeof (double)).

Созданная динамическая переменная существует вплоть до завершения работы программы, или до момента, когда она явно уничтожается с помощью функции free.

void free (void *p)

free освобождает область памяти, на которую указывает p; если p равно NULL, то функция ничего не делает. Значение p должно указывать на область памяти, ранее выделенную с помощью функций malloc или calloc После освобождения памяти результат разыменования указателя p непредсказуем; результат также непредсказуем при попытке повторного обращения к free c этим же указателем. Приведем описание еще одной функции распределения памяти в Си. Ею удобно пользоваться, когда нужно разместить массив в динамической памяти.

void *calloc (size_t nobj, size_t size)

calloc возвращает указатель на место в памяти, отведенное для массива nobj объектов, каждый из которых имеет размер size. Выделенная область памяти побитово обнуляется. (Заметим, что это не всегда равнозначно присваиванию нулевых значений соответствующим элементам массива. В некоторых реализациях в побитовом представлении нулевого указателя или значения 0.0 с плавающей точкой могут быть ненулевые биты). Если память отвести не удалось, то результат работы функции -- NULL. В C++ для выделения участка памяти в динамически распределяемой области используется ключевое слово new. После слова new следует указать тип объекта, который будет размещен в памяти. В качестве результата оператор new возвращает адрес выделенного фрагмента памяти, который должен быть присвоен указателю.

int* set = new int[100];

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

delete [] set;

Представление списков цепочками звеньев

Для хранения отдельного элемента списка создается динамический объект -- структура с двумя членами, называемая звеном. В одном из членов (информационном) располагается сам элемент, а другой член содержит указатель на звено, содержащее следующий элемент списка, или пустой указатель, если следующего элемента нет. С помощью указателей звенья как бы сцеплены в цепочку. Зная указатель на первое звено можно добраться и до остальных звеньев, то есть указатель на первое звено задаёт весь список. Пустой список представляется пустым указателем. Приведём соответствующие описания на языке Си. В качестве типа элемента списка выбран тип char. Списки с элементами других типов описываются аналогично.

#include <stdio.h>

#include <stdlib.h>

typedef struct Node *link;/* указатель на звено */

typedef char elemtype;/* тип элемента списка */

typedef struct Node/* звено состоит из двух полей:*/

{

elemtype elem;/* - элемент списка, */

link next;/* - указатель на следующее звено */

} node;

typedef link list;/* список задается указателем на звено */

list lst;/* переменная типа список */

Переменная 1st представляет в программе список.

Обратите внимание на то, что в описании типа link используется незавершенный тип struct Node. Описание указателей на незавершенный тип допустимо в Си. Тип struct Node становится завершенным при описании типа node. Тип list объявляется синонимом типа link.

В примерах мы будем обозначать обсуждаемые списки в виде кортежей, как это принято в математике. Так, конструкция (`a', `b', `c') означает список из трех элементов. Первый элемент в этом списке -- `a', второй -- `b' третий -- `c'. Пустой список выглядит так .

Пример. Список символов 'a', `b', `c', представленный цепочкой звеньев, изображается следующим образом (в переменной 1st -- указатель на первое звено):

При этом в программе выражение lst означает указатель на первое звено в цепочке; *lst означает само первое звено, (*lst).elem -- первый элемент списка. По-другому первый элемент обозначается с помощью операции доступа к члену структуры через указатель: lst->elem. Выражение lst->next означает указатель на второе звено. Далее,

*lst-->next- само второе звено,

lst-->next-->elem- второй элемент списка,

lst-->next-->next- указатель на третье звено,

*lst-->next-->next- само третье звено,

lst-- >next-->next-->elem- третий элемент списка,

lst-- >next-->next-- >next- пустой указатель (конец списка).

Выражение 1st имеет и другой смысл. Оно обозначает список в программе, поскольку, зная указатель на первое звено, мы имеем доступ ко всем остальным звеньям, т.е. "знаем" весь список. С этой точки зрения выражение lst-->next в нашем примере обозначает список `b', `c', а выражение lst-->next-->next-->next -- пустой список.

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

Пусть из списка'a', `b', `c', представленного в программе переменной lst, требуется удалить второй элемент. Для этого достаточно исключить из цепочки второе звено - "носитель" второго элемента. Изменим указатель в поле next первого звена:

lst->next = lst->next->next.

Теперь после первого звена в цепочке идёт звено, содержащее элемент `c'. Получился список 'a', `c'. Чтобы исключённое звено не занимало места в памяти, его следует уничтожить с помощью функции free(), предварительно запомнив указатель на него во вспомогательной переменной q. Итак, окончательное решение таково:

q = lst->next; lst->next = lst->next->next;

free(q);

Покажем на рисунке происходящие после каждого действия изменения.

Пусть теперь требуется вставить `d' после первого элемента списка 'a', `c'. Решение состоит из двух этапов. Во-первых, необходимо создать "носитель" -- звено для хранения вставляемого элемента, и занести этот элемент в поле elem "носителя". Во-вторых, путём изменения указателей включить созданное звено в цепочку после первого звена. Первый этап реализуется фрагментом

q = (link) malloc(sizeof (node));

q->elem = `d';

где q -- вспомогательная переменная типа link. Фрагмент

q->next = lst->next;

lst->next = q;

осуществляет второй этап вставки. Следующий рисунок иллюстрирует этапы вставки.

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

2. Постановка задачи

В файловой системе каталог файлов организован в виде линейного списка. Для каждого файла в каталоге содержатся следующие сведения:

· имя файла;

· дата создания;

· количество обращений к файлу.

Написать программу, которая обеспечивает:

· начальное формирование каталога файлов;

· вывод каталога файлов;

· удаление файлов, дата создания которых меньше заданной;

· выборку файла с наибольшим количеством обращений.

Программа должна обеспечивать диалог с помощью меню.

3. Блок-схема

4. Инструкция по работе с программой

Запускаем программу, после чего открывается окно, куда требуется ввести количество файлов создаваемой вами файловой системы:

Далее нужно ввести имя файла. Для первого файла имя будет, к примеру "file1":

Теперь необходимо ввести дату создания файла. Дата вводится в формате (дд мм гггг), например:

Следующим шагом будет ввод количества обращений к файлу:

Далее программа повторяет запрос на ввод имени файла, даты создания и количества обращений, вводим данные:

После этого программа выведет созданный нами каталог:

В следующем шаге программа предложит удалить файлы, дата создания которых меньше заданной. Введем дату 01 01 2011:

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

В итоге программа выводит файл с наибольшим количеством обращений:

В конце требуется нажать любую клавишу для закрытия программы.

5. Исходный код

#include "stdafx.h"

#include<iostream>

#include "stdafx.h"

using namespace std;

struct data//структура описывающая дату

{

int day;//день

int mon;//месяц

int year;//год

};

struct file//структура описывающая файл

{

char name[20];//имя

data date;//дата

int kol;//количество обращений

void in()//функция ввода даты

{

cin>>date.day;

cin>>date.mon;

cin>>date.year;

}

void out()// функция вывода даты

{

cout<<date.day<<" ";

cout<<date.mon<<" ";

cout<<date.year<<" ";

}

};

file *a;// массив файлов

int n;//кол-во файлов

int operator <(file a,file b)// оператор "меньше" для дат

{

if(a.date.year<b.date.year

|| ((a.date.year==b.date.year)&&(a.date.mon<b.date.mon))

||((a.date.year==b.date.year)&&(a.date.mon==b.date.mon)||(a.date.day<b.date.day)))return 1;

else return 0;

}

int operator >(file a,file b) // оператор 'больше' для кол-во обращений

{

if(a.kol>b.kol)return 1;else 0;

}

void del(int k) // функция удаления файла

{

file *b=new file[n-1];

int r=0;

for(int i=0;i<(n-1);i++)

{

if(i<k)r=0;else r=1;

b[i]=a[i+r];

}

a=b;

--n;

}

int main(int argc, char* argv[])

{

wcout.imbue(locale(".866"));//установка локализации

wcout<<L"Введите кол-во файлов: ";

cin>>n;

a=new file[n];

for(int i=0;i<n;i++){

wcout<<L"Введите имя файла № "<<i+1<<L": ";

cin>>a[i].name;

wcout<<L"Введите дату создания файла № "<<i+1<<L" (дд мм гггг): ";

a[i].in();

wcout<<L"Введите кол-во обращений к файлу № "<<i+1<<L" : ";

cin>>a[i].kol;

cout<<endl;

}

wcout<<L"Вывод каталога\n";

for(i=0;i<n;i++){

cout<<i+1<<endl<<"\t"<<a[i].name<<endl<<"\t";

a[i].out();

cout<<endl<<"\t"<<a[i].kol<<endl;

}

wcout<<L"Удаление файлов, дата создания которых меньше заданной:\n\t введите дату: ";

file temp;

temp.in();

for(i=0;i<n;i++)

{

if(a[i]<temp)del(i);

}

wcout<<L"Оставшиеся файлы\n";

for(i=0;i<n;i++){

cout<<i+1<<endl<<"\t"<<a[i].name<<endl<<"\t";

a[i].out();

cout<<endl<<"\t"<<a[i].kol<<endl;

}

wcout<<L"Файл с наибольшим количеством обращений\n";

file max=a[0];

for(i=1;i<n;i++)if(a[i]>max)max=a[i];

cout<<"\t"<<max.name<<endl<<"\t";

max.out();

cout<<endl<<"\t"<<max.kol<<endl;

system("pause");

return 0;

}

Заключение

В процессе написания курсовой работы был организован каталог файлов в файловой системе в виде линейного списка. Программа моделирования данного процесса была создана на языке Visual C++. Были изучены способы создания такого приложения с использованием линейных списков.

файловый каталог visual программа

Список используемой литературы

1. Александреску А. Современное проектирование на С++. Серия C++ In-Depth, т.3. -- Москва: Издательский дом "Вильямс", 2002

2. Бадд Т. Объектно-ориентированное программирование в действии/Пер. с англ.- СПб.: Питер, 1997

3. Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++.-- М: Бином, 1998

4. Вандевурд Д., Джосаттис Н. Шаблоны С++: справочник разработчика/Пер. с англ. -- М.: Издательский дом "Вильямс", 2003

5. Голуб А. И. С и С++. Правила программирования. -- М: БИНОМ, 1996

6. Красикова И.Е. Красиков И.В. С++. Просто как дважды два. -- М.: Изд-во Эксмо, 2005

7. Коплиен Дж. Программирование на С++ . -- СПб: ПИТЕР, 2005

8. Страуструп Б. Дизайн и эволюция С++: Пер.с англ.- М.: ДМК Пресс; СПб.: Питер, 2006

9. Штерн В. Основы С++. Методы программной инженерии. -- Москва: Лори, 2003

10. М. Эллис, Б. Строуструп. Справочное руководство по языку C++ с комментариями: Пер. с англ. - Москва: Мир, 1992

11. Стенли Б. Липпман. C++ для начинающих: Пер. с англ. 2тт. - Москва: Унитех; Рязань: Гэлион, 1992

12. К. Джамса. Учимся программировать на языке C++: Пер. с англ. - Москва: Мир, 1997

13. В.А. Скляров. Язык C++ и объектно-ориентированное программирование: Справочное издание. - Минск: Вышэйшая школа, 1997

14. Х. Дейтел, П. Дейтел. Как программировать на C++: Пер. с англ. - Москва: ЗАО "Издательство БИНОМ", 1998

Размещено на Allbest.ru