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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

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) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

Таблица
	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	2	1	2	1	2	1	2	1	2	1
3	3	3	2	2	1	1	3	3	2	2
4	4	1	1	2	2	3	2	3	3	4
5	5	3	4	1	2	4	4	1	2	4
6	6	5	1	5	1	4	5	3	5	2
7	7	7	4	2	6	3	5	4	7	5
8	8	1	7	6	3	1	4	4	8	7
9	9	3	1	1	8	7	2	3	8	8
10	10	5	4	5	3	3	9	1	7	8

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

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<n; i++)

add_item(i+1);

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

s->next=first;

first->prev=s;

p=first;

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

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

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

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

p=p->next;

}

printf("\n");

s=first;

while(n>1)

{

p=s;

for(i=1; i<m; 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<stdio.h>

#include<conio.h>

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<n; i++) //Запускаем функцию "add_item"

add_item(i+1);

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

first->prev=s;

p=first;

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

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

p=p->next;

}

printf("\n");

s=first;

while(n>1){

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

p=s;

for(i=1; i<m; 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<stdio.h>

#include<conio.h> //библиотека с функцией 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<n; i++) //Запускаем функцию "add_item"

add_item(i+1);

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

first->prev=s;

p=first;

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

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

p=p->next;

}

printf("\n");

s=first;

while(n>1){

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

p=s;

for(i=1; i<m; 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();

}

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