В файловой системе каталог файлов организован в виде линейного списка. Программа должна обеспечивать диалог с помощью меню.
Составить программу моделирования заданного процесса на языке Visual C++ при выполнении следующих требований:
Основные части программы должны быть оформлены в виде подпрограмм и выделены в отдельный модуль.
Предусмотреть ввод входных данных с клавиатуры, а также формирование их с использованием подпрограммы генерации случайных чисел.
Содержание
Введение
.Теоретические сведения
.Постановка задачи
.Блок-схема
.Инструкция по работе с программой
.Исходный код
Заключение
Список используемой литературы
Введение
Целью курсовой работы является закрепление и углубление знаний, полученных в курсе "Программирование", развитие навыков при выборе представления исходных данных при написании программ на языке 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)
освобождает область памяти, на которую указывает 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 возвращает адрес выделенного фрагмента памяти, который должен быть присвоен указателю.
* set = new int[100];
По завершении работы с выделенной областью ее следует освободить. Делается это с помощью оператора delete, после которого записывается имя указателя. Оператор delete освобождает память, на которую указывает указатель.
[] set;
Представление списков цепочками звеньев
Для хранения отдельного элемента списка создается динамический объект - структура с двумя членами, называемая звеном. В одном из членов (информационном) располагается сам элемент, а другой член содержит указатель на звено, содержащее следующий элемент списка, или пустой указатель, если следующего элемента нет. С помощью указателей звенья как бы сцеплены в цепочку. Зная указатель на первое звено можно добраться и до остальных звеньев, то есть указатель на первое звено задаёт весь список. Пустой список представляется пустым указателем. Приведём соответствующие описания на языке Си. В качестве типа элемента списка выбран тип char. Списки с элементами других типов описываются аналогично.
#include <stdio.h>
#include <stdlib.h>struct Node *link;/* указатель на звено */char elemtype;/* тип элемента списка */struct Node/* звено состоит из двух полей:*/
{elem;/* - элемент списка, */next;/* - указатель на следующее звено */
} node;link 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- третий элемент списка,>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));>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"namespace std;data//структура описывающая дату
{day;//деньmon;//месяц
int year;//год
};file//структура описывающая файл
{name[20];//имяdate;//дата
int kol;//количество обращенийin()//функция ввода даты
{>>date.day;>>date.mon;>>date.year;
}out()// функция вывода даты
{<<date.day<<" ";<<date.mon<<" ";<<date.year<<" ";
}
}; *a;// массив файлов
int n;//кол-во файлов
int operator <(file a,file b)// оператор "меньше" для дат
{(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;return 0;
}operator >(file a,file b) // оператор 'больше' для кол-во обращений
{(a.kol>b.kol)return 1;else 0;
}del(int k) // функция удаления файла
{*b=new file[n-1];r=0;(int i=0;i<(n-1);i++)
{(i<k)r=0;else r=1;[i]=a[i+r];
}=b;
-n;
}main(int argc, char* argv[])
{.imbue(locale(".866"));//установка локализации<<L"Введите кол-во файлов: ";
cin>>n;=new file[n];(int i=0;i<n;i++){
wcout<<L"Введите имя файла № "<<i+1<<L": ";>>a[i].name;<<L"Введите дату создания файла № "<<i+1<<L" (дд мм гггг): ";[i].in();<<L"Введите кол-во обращений к файлу № "<<i+1<<L" : ";
cin>>a[i].kol;<<endl;
}<<L"Вывод каталога\n";
for(i=0;i<n;i++){<<i+1<<endl<<"\t"<<a[i].name<<endl<<"\t";[i].out();<<endl<<"\t"<<a[i].kol<<endl;
}<<L"Удаление файлов, дата создания которых меньше заданной:\n\t введите дату: ";
file temp;.in();(i=0;i<n;i++)
{(a[i]<temp)del(i);
}<<L"Оставшиеся файлы\n";
for(i=0;i<n;i++){<<i+1<<endl<<"\t"<<a[i].name<<endl<<"\t";[i].out();<<endl<<"\t"<<a[i].kol<<endl;
}<<L"Файл с наибольшим количеством обращений\n";
file max=a[0];(i=1;i<n;i++)if(a[i]>max)max=a[i];<<"\t"<<max.name<<endl<<"\t";.out();<<endl<<"\t"<<max.kol<<endl;
system("pause");0;
}
Заключение
В процессе написания курсовой работы был организован каталог файлов в файловой системе в виде линейного списка. Программа моделирования данного процесса была создана на языке Visual C++. Были изучены способы создания такого приложения с использованием линейных списков.
файловый каталог visual программа
Список используемой литературы
1.Александреску А. Современное проектирование на С++. Серия C++ In-Depth, т.3. - Москва: Издательский дом "Вильямс", 2002
2.Бадд Т. Объектно-ориентированное программирование в действии/Пер. с англ.- СПб.: Питер, 1997
.Буч Г. Объектно-ориентированный анализ и проектирование с примерами на С++.- М: Бином, 1998
.Вандевурд Д., Джосаттис Н. Шаблоны С++: справочник разработчика/Пер. с англ. - М.: Издательский дом "Вильямс", 2003
.Голуб А. И. С и С++. Правила программирования. - М: БИНОМ, 1996
.Красикова И.Е. Красиков И.В. С++. Просто как дважды два. - М.: Изд-во Эксмо, 2005
.Коплиен Дж. Программирование на С++ . - СПб: ПИТЕР, 2005
.Страуструп Б. Дизайн и эволюция С++: Пер.с англ.- М.: ДМК Пресс; СПб.: Питер, 2006
.Штерн В. Основы С++. Методы программной инженерии. - Москва: Лори, 2003
.М. Эллис, Б. Строуструп. Справочное руководство по языку C++ с комментариями: Пер. с англ. - Москва: Мир, 1992
.Стенли Б. Липпман. C++ для начинающих: Пер. с англ. 2тт. - Москва: Унитех; Рязань: Гэлион, 1992
.К. Джамса. Учимся программировать на языке C++: Пер. с англ. - Москва: Мир, 1997
.В.А. Скляров. Язык C++ и объектно-ориентированное программирование: Справочное издание. - Минск: Вышэйшая школа, 1997
.Х. Дейтел, П. Дейтел. Как программировать на C++: Пер. с англ. - Москва: ЗАО "Издательство БИНОМ", 1998