Хранение и обработка данных с использованием линейных списков

Содержание Введение

1. Уяснение задачи

2. Выбор алгоритма решения задачи

3. Написание программы на псевдокоде

4. Составление программы на языке программирование высокого уровня

5. Тестирование и отладка программы

6. Результаты работы программы Заключение Список используемых источников Приложение

ВВЕДЕНИЕ

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

Цель курсовой работы — разработать программу, обеспечивающую эффективную обработку и хранение информации с использованием линейных списков.

Для достижения этой цели определены следующие задачи:

· Уяснить и разобрать задачу;

· Выбрать алгоритм решения этой задачи;

· Написать программу на псевдокоде;

· Написать программу на языке программирования высокого уровня;

· Провести тестирование и отладку программы.

1. Уяснение задачи Формулировка задачи «Считалка» звучит так: даны натуральные n, m. Предполагается, что n человек встают в круг и получают номера, считая против часовой стрелки, 1, 2, …, n. Затем, начиная с первого, также против часовой стрелки отсчитывается m-й человек (поскольку люди стоят по кругу, то за n-м человеком стоит первый). Этот человек выходит из круга, после чего, начиная со следующего, снова отсчитывается m-й человек и так до тех пор, пока из всего круга не остается один человек. Определить его номер.

Уясним эту задачу на следующем примере. Пример основан на легенде: «Отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам».

2. Выбор алгоритма решения задачи Существует несколько алгоритмов решения данной задачи.

Способ первый. Будем хранить в массиве имена (то есть номера) всех живых на текущий момент воинов. Причем удобно, чтобы номера людей были записаны в элементах массива с 0 по N — 1 (это свойство будет использоваться для операции взятия остатка). Когда воин будет умирать, будем удалять его из массива, и тех, кто стоял за ним, «сдвигать» на один элемент влево. Заметим, что если мы уже убили L человек, то в живых осталось M = N — L. Пусть мы только что (на L-ом шаге) убили человека, который был записан в нашем массиве в элементе с номером j (и сдвинули людей, которые были записаны в массиве в элементах с j + 1 по M на один элемент влево). Тогда следующим нужно убивать человека, который записан в этом массиве в элементе с номером (j + k — 1) % M. [9]

Способ второй. Заведем массив, где будем помечать мертвых воинов (то есть в i-м элементе хранится, жив воин i, или уже нет). Пусть у нас на текущем шаге M живых людей и на предыдущем шаге умер воин j. Чтобы найти следующего, будем бежать по массиву, отсчитывая живых и пропуская мертвых. Тот человек, на котором мы насчитаем k % M и должен умереть следующим. Через N — 1 шаг останется один человек. 10]

Рекурсивное решение[5][7]. Простейшее моделирование будет работать O (). Используя дерево отрезков, можно произвести моделирование за. Однако попытаемся найти закономерность, выражающую ответ для задачи (N, K) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

И здесь достаточно отчётливо видна следующая закономерность:

joseph (n, k) = (joseph (n-1, k) + k — 1) % n + 1;

joseph (1, k) = 1

(здесь индексация с единицы несколько портит элегантность формулы).

На мой взгляд, самым простым и понятным является первый способ решения. В связи с этим, алгоритм решения моей задачи, основывается именно на этом способе.

3. Написание программы на псевдокоде Выводятся на экран сообщения — Vvedite chiclo n и Vvedite chiclo m (число n — количество людей, стоящих в кругу, а число m — число людей, которое отсчитывается)

printf («Vvedite chiclo n «);

scanf («%d», &n);

printf («Vvedite chiclo m «);

scanf («%d», &m);

После того, как мы ввели числа n и m запускаем, функцию «add_item» [1]. Эта функция производит все вычисления, отсчет людей и нахождение номера последнего человека в кругу.

for (i=0; i

add_item (i+1);

и замыкаем список

s->next=first;

first->prev=s;

p=first;

for (i=0; i

Выводим на экран исходный список, из списка с порядковыми номерами участников удаляем m-ый по счёту столько раз, пока не останется один участник (после удаления участника считать начинаем со следующего после удалённого);

Перед удалением m-ого элемента списка выстраивается связь между предыдущим и следующим элементами списка, и выводим на экран номер оставшегося участника

printf («%d «, p->n);

p=p->next;

}

printf («n»);

s=first;

while (n>1)

{

p=s;

for (i=1; i

p=p->next;

p->next->prev=p->prev;

p->prev->next=p->next;

s=p->next;

delete p;

n—;

}

printf («%d «, s->n);

getch ();

}

4. Составление программы на языке программирования высокого уровня

1. Объявляем директиву include, которая сообщает компилятору о необходимости подключения библиотек stdio. h и conio. h[2][6]

#include

#include

2. Создаем структуру Titem[3]

struct Titem {

int n;

Titem *next,*prev;

} *first,*s,*p;

int n, m;

3. Описываем функцию «add_item», добавляющую в список порядковые номера участников

void add_item (int v){

Titem *p;

if (s==NULL && first==NULL){

s=new Titem;

s->n = v;

s->next = NULL;

s->prev = NULL;

first=s;

}

else{

p = new Titem;

p->n = v;

p->next=NULL;

p->prev=s;

s->next=p;

s=p;

}

return;

}

4. Описываем главную функцию

int main (){

int i;

printf («Vvedite chiclo n «);

scanf («%d», &n);

printf («Vvedite chiclo m «);

scanf («%d», &m);

for (i=0; i

add_item (i+1);

s->next=first; //Замыкаем список

first->prev=s;

p=first;

for (i=0; i

printf («%d «, p->n); //Выводим на экран исходный список

p=p->next;

}

printf («n»);

s=first;

while (n>1){

/*Из списка с порядковыми номерами участников удаляем m-ый по счёту столько раз, пока не останется один участник (после удаления участника считать начинаем со следующего после удалённого)*/

p=s;

for (i=1; i

p=p->next;

p->next->prev=p->prev;

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

p->prev->next=p->next;

s=p->next;

delete p;

n—;

}

printf («%d «, s->n); //Выводим на экран номер оставшегося участника

getch ();

}

5. Тестирование и отладка программы После завершения написания программного кода я запускаю программу (конфигурация решения Debug), на экране появляется окно о подтверждении запуска программы (рисунок 1).

Рисунок 1 — Подтверждение запуска программы На рисунке 1 изображено диалоговое окно с подтверждением построение проекта kurs.

После нажатия кнопки «Да» выходит программная консоль, на которой выводится сообщение — «Vvedite chislo n» (рисунок 2), число n характеризует количество людей, стоящих в кругу.

Рисунок 2 — Ввод количества людей

На рисунке 2 изображена программная консоль с запросом ввода числа n и с введенным числом n. После ввода числа n, запрашивается ввод числа m, характеризующее какой по счету человек выйдет из круга, после отсчета числа m (рисунок 3).

Рисунок 3 — Запрос ввода числа m

На рисунке 3 изображена программная консоль с запросом ввода числа n и с введенным числом n, с запросом ввода числа m и с введенным числом m.

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

линейный список алгоритм информация Рисунок 4 — Результат работы программы На рисунке 4 — изображена программная консоль, на которой показаны сообщения «Vvedite chiclo n» и «Vvedite chiclo m», значения этих чисел, выведен полный список людей и конечное число, т. е. номер человека оставшегося после всех выбываний.

6. Результаты работы программы После запуска программы появляется рабочее окно программы и оно имеет следующий вид Рисунок 5 — Конечный результат На рисунке 5 изображена окончательная работа выполнения программы.

ЗАКЛЮЧЕНИЕ

В ходе выполнения курсовой работы были выполнены следующие задачи:

— уяснена и разобрана задача;

— выбран алгоритм решения этой задачи;

— написана программа на псевдокоде и на языке программирования высокого уровня;

— проведено тестирование и отладка программы.

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. С/C++. Структурное программирование: Практикум /Т.А.Павловская, Ю. А. Щупак. — СПб.: Питер, 2003. — 240 с.: ил.

2. С/C++. Программирование на языке высокого уровня / Т. А. Павловская. — СПб.: Питер, 2003. — 461 с.: ил.

3. C++. Объектно-ориентированное программирование: Практикум. — СПб.: Питер, 2006. — 265 с.: ил.

4. Основы алгоритмизации. Методическое руководство для самостоятельного изучения. / Сост. С. Г. Кузин. Н. Новгород — ННГУ, 1998.

5. Брукшир Дж. Информатика и вычислительная техника. 7-е изд. — СПб.: Питер, 2004. — 620 с.: ил.

6. Березин Б. И., Березин С. Б. Начальный курс С и C++. — М: ДИАЛОГ-МИФИ, 1996.—288 с.

7. Болски М. И. Язык программирования Си. Справочник: Пер. с англ. — М.-Радио и связь, 1988. — 96 с.

8. Ван Тассел Д. Стиль, разработка, эффективность, отладка и испытание программ. — М: Мир, 1981. — 89 с.

10. С# в задачах и примерах. — СПб.: БХВ-Петербург, 2007. — 240 е.: ил. + CD-ROM

ПРИЛОЖЕНИЕ Листинг программного кода

#include

#include //библиотека с функцией getch

struct Titem //Создаём структуру «Titem»

{

int n;

Titem *next,*prev;

}

*first,*s,*p;

int n, m;

void add_item (int v) /*Описываем функцию «add_item» добавляющую в список порядковые номера участников*/

{

Titem *p;

if (s==NULL && first==NULL){

s=new Titem;

s->n = v;

s->next = NULL;

s->prev = NULL;

first=s;

}

else

{

p = new Titem;

p->n = v;

p->next=NULL;

p->prev=s;

s->next=p;

s=p;

}

return;

{

int main ()

{

int i;

printf («Vvedite chiclo n «);

scanf («%d», &n);

printf («Vvedite chiclo m «);

scanf («%d», &m);

for (i=0; i

add_item (i+1);

s->next=first; //Замыкаем список

first->prev=s;

p=first;

for (i=0; i

printf («%d «, p->n); //Выводим на экран исходный список

p=p->next;

}

printf («n»);

s=first;

while (n>1){

/*Из списка с порядковыми номерами участников удаляем m-ый по счету столько раз, пока не останется один участник (после удаления участника считать начинаем со следующего после удалённого)*/

p=s;

for (i=1; i

p=p->next;

p->next->prev=p->prev;

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

p->prev->next=p->next;

s=p->next;

delete p;

n—;

}

printf («%d «, s->n); //Выводим на экран номер оставшегося участника

getch ();

}