Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Введение
Курсовая работа предназначена для отработки навыков программирования задач средней сложности у студентов дневного и заочного отделения специальностей "" в рамках дисциплины "Программирование".
Целью курсовой работы является закрепление и углубление знаний, полученных студентами в курсе "Программирование", развитие навыков при выборе представления исходных данных при написании программ на языке C/С++, тестировании и отладки программы, оформлении документации на программную разработку.
Порядок выполнения курсовой работы
Курсовая работа по курсу "Программирование" выполняется индивидуально каждым студентом в соответствии с выданным преподавателем вариантом. Курсовая работа выполняется в среде MS Visual C++6.0.
В процессе работы автор должен:
Все этапы работы должны быть отражены в пояснительной записке.
|
№ |
Этап курсовой работы |
Неделя семестра |
|
1 |
Анализ предметной области, декомпозиция системы на компоненты (структуры, модули). |
1-3 |
|
2 |
Разработка пользовательских структур. |
4-5 |
|
3 |
Разработка алгоритмов, используемых при решении задачи. |
6-8 |
|
4 |
Разработка интерфейса. |
9 |
|
5 |
Отладка и тестирование программы. |
10-12 |
|
6 |
Оформление пояснительной записки. |
13 |
|
7 |
Защита курсовой работы. |
14-15 |
Теоретические сведения
Список — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле. Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Линейный связный список
Односвязный список. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента невозможно.
Двусвязный список. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, т.к. всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.
Стек — структура данных с методом доступа к элементам «последним пришел — первым вышел». Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно взять верхнюю.
Добавление элемента, называемое также проталкиванием (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;
осуществляет второй этап вставки. Следующий рисунок иллюстрирует этапы вставки.
Из примеров видно, что длина цепочки (количество звеньев в ней) может динамически изменяться, т.е. изменяться в процессе выполнения программы. Подобно цепочкам можно сконструировать и более сложные структуры, в которых объекты связаны между собой с помощью указателей. Такого рода структуры данных называются динамическими.
Некоторые операции со списками
Приведём описание нескольких функций для работы со списками.
Создание списка
Функция create(s) создает и возвращает в качестве результата список из символов параметра-строки s.
list create (char *s)
{
int i;
link cur; /* указатель на текущее звено списка */
list res; /* возвращаемый список */
if ( *s == '\0' )
return NULL; /* если строка пуста, то возвращаем
пустой список
иначе строим непустой список */
res = cur = (link ) malloc ( sizeof (node)); /* создаем первое звено списка */
cur->elem = *s++; /* заполняем поле elem и переходим к
следующему элементу строки */
while ( *s != '\0' ) /* пока не конец строки */
{
cur = cur->next = (list) malloc( sizeof (node)); /* присоединяем в конец
списка новое звено */
cur->elem = *s++ ; /* помещаем в новое звено очередной элемент
и переходим к следующему элементу
строки */
}
cur->next = NULL; /* последнее звено должно иметь
нулевой указатель */
return res; /* возвращаем список
(указатель на первое звено) */
}
Условие *s != '\0' можно заменить на *s, а *s == '\0' заменить на !*s .
Печать элементов списка
/* print: печатает в стандартный выходной поток элементы списка */
void print (list p)
{
while (p != NULL ) /* пока не конец списка,*/
{
putchar (p->elem ); /* печатаем очередной элемент */
p = p->next; /* и переходим к следующему звену */
}
putchar ('\n');
}
Заголовок while-цикла можно было записать как while ( p ). Однако, выражение p != NULL более информативно — по нему можно догадаться, что p скорее всего является указателем, даже не видя его описания.
Опишем функцию печати, используя цикл for.
/* print: печать в стандартный выходной поток элементов списка версия с циклом for */
void print(list p)
{
for ( ;p;p=p->next) /* пока не конец списка, т.е. p!=NULL */
putchar ( p->elem ); /* печатаем очередной элемент и переходим к следующему звену */
putchar('\n') ;
}
Здесь мы использовалиp в качестве условия продолжения цикла, а не p!=NULL, так как рядом стоящее p ->next (в третьем выражении заголовка for), говорит о том, что p — указатель.
Вычисление свойств и характеристик списков
/* isempty: возвращает 1, если список пуст, иначе — 0 */
int isempty ( list ls)
{
return ls == NULL;
}
/* count: подсчитывает число вхождений элемента elem в список ls */
int count (list ls, elemtype elem)
{
int c = 0; /* счетчик вхождений */
for ( ; ls ; ls = ls->next)
if ( ls->elem == elem )
c++;
return c;
}
Можно обойтись без условного оператора в теле цикла for, записав вместо него оператор-выражение:
c += ( ls->elem == elem);
/* length: вычисляет длину списка ls */
int length (list ls)
{
int c;
for ( c = 0; lst; lst = lst->next, c++);
return c;
}
Теперь опишем рекурсивную версию функции length(). Для этого список удобно представлять себе как рекурсивную структуру данных: он либо пуст, либо состоит из «головы» (первый элемент) и «хвоста» (все, кроме первого). Хвост, в свою очередь, также является списком.
/* length: рекурсивно вычисляет длину списка ls;
длина пустого списка равна нулю,длина непустого списка на единицу больше длины его хвоста */
int length ( list ls)
{
return (ls)?length(ls->next)+1: 0;
}
Вставка элемента
/* insfront: вставляет элемент elem в начало списка,
переданного через указатель lp */
void insfront( elemtype elem, list * lp)
{
list cur = ( list ) malloc ( sizeof ( list ) );
cur->elem = elem; cur->next = *lp;
*lp = cur;
}
Удаление списка
После того, как список в программе стал не нужен, следует удалить его, освободив память, занимаемую звеньями.
/* destruct: удаляет список, освобождая занимаемую им память */
void destruct ( list ls )
{
link q;
while ( ls !=NULL )
{
q = ls ;
ls = ls->next;
free (q);
}
}
Задания
Вариант 1
Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе включают:
Программа должна обеспечивать:
Вариант 2
Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах включают:
Программа должна обеспечивать:
Вариант 3
Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка включает:
Программа должна обеспечивать:
Вариант 4
Составить программу, которая содержит текущую информацию о заявках на авиабилеты. Каждая заявка включает:
Программа должна обеспечивать:
Вариант 5
Составить программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах включают:
Программа должна обеспечивать:
Вариант 6
Составить программу, которая содержит динамическую информацию о наличии автобусов в автобусном парке. Сведения о каждом автобусе включают:
Программа должна обеспечивать:
Вариант 7
Создать программу, отыскивающую проход по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.
Вариант 8
Гаражная стоянка имеет одну стояночную полосу, причем единственный въезд и единственный выезд находятся в одном конце полосы. Если владелец автомашины приходит забрать свой автомобиль, который не является ближайшим к выходу, то все автомашины, загораживающие проезд, удаляются, машина данного владельца выводится со стоянки, а другие машины возвращаются на стоянку в исходном порядке.
Написать программу, которая моделирует процесс прибытия и отъезда машин. Прибытие или отъезд автомашины задается командной строкой, которая содержит признак прибытия или отъезда и номер машины. Программа должна выводить сообщение при прибытии или выезде любой машины. При выезде автомашины со стоянки сообщение должно содержать число случаев, когда машина удалялась со стоянки для обеспечения выезда других автомобилей.
Вариант 9
Написать программу, моделирующую заполнение гибкого магнитного диска. Общий объем памяти на диске 360 Кбайт. Файлы имеют произвольную длину от 18 байт до 32 Кбайт. В процессе работы файлы либо записываются на диск, либо удаляются с него.
В начале работы файлы записываются подряд друг за другом. После удаления файла на диске образуется свободный участок памяти, и вновь записываемый файл либо размещается на свободном участке, либо, если файл не помещается в свободный участок, размещается после последнего записанного файла.
В случае, когда файл превосходит длину самого большого свободного участка, выдается аварийное сообщение. Требование на запись или удаление файла задается в командной строке, которая содержит имя файла, его длину в байтах, признак записи или удаления. Программа должна выдавать по запросу сведения о занятых и свободных участках памяти на диске.
Указание: следует создать список занятых участков и список свободных участков памяти на диске.
Вариант 10
В файловой системе каталог файлов организован в виде линейного списка. Для каждого файла в каталоге содержатся следующие сведения:
Написать программу, которая обеспечивает:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 11
Предметный указатель организован в виде линейного списка. Каждая компонента указателя содержит слово и номера страниц, на которых это слово встречается. Количество номеров страниц, относящихся к одному слову, лежит в диапазоне от одного до десяти. Написать программу, которая обеспечивает:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 12
Текст помощи для некоторой программы организован в виде линейного списка. Каждая компонента текста помощи содержит термин (слово) и текст, содержащий пояснения к этому термину. Количество строк текста, относящихся к одному термину, составляет от одной до пяти. Написать программу, которая обеспечивает:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 13
Картотека в бюро обмена квартир организована в виде линейного списка. Сведения о каждой квартире включают:
Написать программу, которая обеспечивает:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 14
Англо-русский словарь построен в виде двоичного дерева. Каждая компонента содержит английское слово, соответствующее ему русское слово и счетчик количества обращений к данной компоненте. Первоначально дерево формируется в порядке английского алфавита. В процессе эксплуатации словаря при каждом обращении к компоненте к счетчику обращений добавляется единица. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 15
Анкета для опроса населения содержит две группы вопросов. Первая группа содержит сведения о респонденте:
Вторая группа содержит собственно вопрос анкеты, ответом на который может являться либо ДА, либо НЕТ. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 16
Написать программу, которая содержит текущую информацию о книгах в библиотеке. Сведения о книгах включают:
Программа должна обеспечивать:
Вариант 17
На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована в виде линейного списка. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 18
На междугородной телефонной станции картотека абонентов, содержащая сведения о телефонах и их владельцах, организована в виде двоичного дерева. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 19
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается:
Данные в информационной системе организованы в виде линейного списка. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.
Вариант 20
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования. Для каждого поезда указывается:
Данные в информационной системе организованы в виде двоичного дерева. Написать программу, которая:
Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.