Учреждение образования
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Факультет Заочного обучения

КОНТРОЛЬНАЯ РАБОТА
По курсу «Основы алгоритмизации и программирования»

Выполнил Студент
Ф.И.О. Микша Юлия
гр. № 902302
№ зач. кн. 902302-45

Проверил Кардаш С.Н.

Минск-2010
Содержание

Содержание……………………………………………………………. 2
Введение……………………………………………………………….. 3
1. Теоретическая часть……………………………………..…………. 4
1.1. Кольцевая очередь. Деки…………….……………..…………. 4
1.2 Структура данных «список». ………………………………….. 5
2. Задание на разработку………………………...…………………… 8
Заключение…………………………………………………………….. 15
Список использованных источников………………………………… 16

Введение

Контрольная работа должна состоять из двух частей: пояснительной записки и файлов рабочей программы.
Пояснительная записка будет содержать следующие разделы: содержание, введение, два теоретических вопроса, задание на разработку, заключение, список использованных источников.
Во введении необходимо изложить содержание пунктов пояснительной записки, а также описать структуру контрольной работы в целом.
В пунктах «Кольцевая очередь. Деки» и «Структура данных «список»» пояснительной записки будут подробно освещены одноименные теоретические вопросы (в соответствии с индивидуальным заданием).
Формулировка задания на разработку программы (так же в соответствии с индивидуальным заданием) будет приведена в разделе «Задание на разработку» пояснительной записки. Также здесь будет приведен листинг кода программы с комментариями и пояснениями. Здесь же необходимо продемонстрировать интерфейс работы программы.
В заключении будут описаны результаты выполнения контрольной работы, проведен анализ соответствия данных результатов поставленным задачам, подведен итог выполнения работы.
В последнем разделе пояснительной записки будет приведен список литературных источников, которые использовались при написании данной контрольной работы.
Программная часть контрольной работы будет разрабатываться в среде Microsoft Visual Studio 6.0 на языке Си. Откомпилированные файлы рабочей программы будут предоставлены на компакт-диске.

1. Теоретическая часть
1.1 Деки
Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Операции над деком:
• включение элемента справа;
• включение элемента слева;
• исключение элемента справа;
• исключение элемента слева;
• определение размера;
• очистка.

Рис. 1.1. Состояния дека в процессе изменения.
На рис. 1.1. в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.
Физическая структура дека в статической памяти идентична структуре кольцевой очереди.
Деки в вычислительных системах
Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
Однако, в качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь. Однако, в REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит. В распоряжении программиста имеются операции QUEUE - запись строки в конец буфера и PULL - выборка строки из начала буфера. Дополнительная операция PUSH - запись строки в начало буфера - превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.

1.2 Структура данных «список»

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

Здесь Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка.
Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.
Для объявления списка сделано исключение: указатель на звено списка объявляется раньше, чем само звено. В общем виде объявление выглядит так.
Type U = ^Zveno;
Zveno = Record Inf : BT; Next: U End;
Здесь BT — некоторый базовый тип элементов списка.
Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене установлен не в Nil, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.
Более подробно рассмотрим работу со связанными списками на примере однонаправленного некольцевого списка.
Выделим типовые операции над списками:
• добавление звена в начало списка;
• удаление звена из начала списка;
• добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);
• удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);
• проверка, пуст ли список;
• очистка списка;
• печать списка.
Реализуем выделенный набор операций в виде модуля. Подключив этот модуль, можно решить большинство типовых задач на обработку списка. Пусть список объявлен так, как было описано выше. Первые четыре действия сначала реализуем отдельно, снабдив их иллюстрациями.

1. Добавление звена в начало списка

2. Удаление звена из начала списка

3. Добавление звена в произвольное место списка, отличное от начала (после звена, указатель на которое задан)

4. Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)

2. Задание на разработку

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

Разработать программу «Книг по году цене», которая должна содержать структуру из трех полей (название, год, цена) и четыре функции пользователя:
– функция ввода информации;
– функция вывода информации на экран;
– сортировка;
– запись в файл.
Обязательное условие – это наличие меню, что позволит пользователю самому выбирать те действия, которые он хочет совершить над данными.

Листинг программы
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
int n,k,i,j;
struct pl{ //объявление структуры
int id; //id
char nazvanie[30]; //название книги
char god[7]; //год издания
int cena; //стоимость
};
pl new_pl[100], temp;

void menu(); //меню
void vvod(); //объявление процедуры ввода данных
void sort(); //объявление процедуры сортировки данных (по
//стоимости книг)
void vyvod(); //объявление процедуры вывода данных на экран
void fail(); //объявление процедуры вывода данных в файл
void vyhod(); //объявление процедуры выхода из программы
void main(){
menu(); //вызов меню
}
void menu(){ //меню
printf("\nMENU:\n1. Vvod\n2. Sortirovka\n3. Vyvod na ekran\n4. Vyvod v fail\n5. Vyhod\nVvedite punkt menu 1-5 i nazhmite ENTER\n");
scanf("%d",&n); //ввод номера пункта меню
if (n==1) vvod();
else if (n==2) sort();
else if (n==3) vyvod();
else if (n==4) fail();
else if (n==5) vyhod();
else {
printf("vvedite punkt ot 1 do 5!\n");
menu(); //вызов меню
}
}
void vvod(){ //процедура ввода данных
printf("vvod\nvvedite kol-vo zapisey ");
scanf("%d",&k); //ввод количества записей (k)
for (i=0;i<k;i++)
{ new_pl[i].id=i+1; //присвоение значения id записи
printf("\nvvedite nazvanie %d knigi = ",new_pl[i].id);
fflush(stdin);
gets(new_pl[i].nazvanie);//ввод названия книги для текущей //записи
printf("vvedite god izdaniya %d knigi = ",new_pl[i].id);
fflush(stdin);
gets(new_pl[i].god); //ввод нгода издания для текущей
//записи
printf("vvedite stoimost %d knigi = ",new_pl[i].id);
fflush(stdin);
scanf("%d",&new_pl[i].cena); //ввод стоимости
//книги для текущей записи
}
menu(); //вызов меню
}

void sort(){ //процедура сортировки записей по стоимости
//книг (по возрастанию)
for (i=0; i<k; i++)
for (j=0; j<k; j++)
if (new_pl[i].cena<new_pl[j].cena){
temp=new_pl[i];
new_pl[i]=new_pl[j];
new_pl[j]=temp;
}
printf("sortirovka po stoimosti knig zavershena\n");
vyvod(); //вызов процедуры вывода данных на экран
}
void vyvod(){ //процедура вывода данных на экран
printf("vyvod\n");
printf(" id| nazvanie | god|stoimost\n");
for (i=0; i<k; i++){
printf("%3d %-30s %-7s %3d\n", new_pl[i].id, new_pl[i].nazvanie, new_pl[i].god, new_pl[i].cena);
}
menu(); //вызов меню
}
void fail(){ //процедура записи данных в файл
FILE *f; //объявление указателя f на структуру FILE
printf("fail\n");
if ((f=fopen("save_to_file.txt","w"))==NULL)
//указываем имя файла для записи данных, открываем его //для записи или заново создаем
printf("File could not be opened");
else {
for (i=0; i<k; i++){
fprintf(f,"%d %s %s %d\n", new_pl[i].id, new_pl[i].nazvanie, new_pl[i].god, new_pl[i].cena);
//запись в файл полей структуры
}
fclose(f); //закрываем файл
}
printf("info saved to file 'save_to_file.txt'");
menu(); //вызов меню
}
void vyhod(){ //процедура выхода из программы
printf("the END of program\n");
}

При запуске программы на выполнение на экране появляется пользовательское меню следующего вида:

Если пользователь вводит некорректные данные (не входящие в множество [1;5]) на экран выводится соответствующая просьба и происходит возврат к меню:

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

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

Результат выполнения данной процедуры выглядит следующим образом (выводится сообщение о завершении сортировки данных и производится вывод отсортированных записей на экран, пользователю снова предоставляется меню):

При выборе пользователем пункта меню Вывод в файл, данные будут сохранены в текущий каталог выполняемой программы в файл «save_to_file.txt», о чем пользователь будет извещен соответствующим сообщением. Далее пользователю будет снова предложено меню.

Т.к. запись в файл производится после сортировки, данные записываются в файл уже в отсортированном виде. Если данные необходимо записывать в неотсортированном виде, то пункт меню Вывод в файл нужно выбрать до выполнения сортировки данных.

Содержимое файла «Save_to_file.txt»:

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

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

Заключение

В ходе контрольной работы были тщательно изучены и освещены следующие теоретические вопросы: «Кольцевая очередь. Деки» и «Структура данных «список»».
Также в ходе работы была написана программа в среде Microsoft Visual Studio 6.0 на языке Си. Откомпилированные файлы программы прилагаются к пояснительной записке на компакт-диске. Листинг кода программы представлен в пояснительной записке в разделе «Задание на разработку». Также в этом разделе показан интерфейс работы программы на всех этапах ее выполнения. Программа выполняет все требуемые условием индивидуального задания функции.
В ходе работы студентом были получены практические навыки работы со структурами и файлами в Си, а также получены и закреплены необходимые теоретические знания по соответствующим темам, необходимым для выполнения данной контрольной работы.

Список использованных источников

1) Дейтел Х., Дейтел П. Как программировать на Си.
2) Демидович Е.М. Основы алгоритмизации и программирования. Язык СИ.: Пособие для студентов БГУИР. – Мн.: Бестпринт, 2001. – 440 с.
3) Березин Б.И., Березин С.Б. Начальный курс С и С++. –М.: Диалог - МИФИ, 1999
4) О.Л. Голицин «Основы алгоритмизации и программирования»