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

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

Содержание

Введение

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

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

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

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

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

. Результаты работы программы

Заключение

Список используемых источников

Приложение

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Уясним эту задачу на следующем примере. Пример основан на легенде: “Отряд Иосифа Флавия <#"553069.files/image001.gif">). Используя дерево отрезков <#"553069.files/image002.gif">. Однако попытаемся найти закономерность, выражающую ответ для задачи (N,K) через решение предыдущих задач. С помощью моделирования построим таблицу значений, скажем, приведенную ниже.

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

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

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

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

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

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

printf("\Vvedite chiclo n ");("%d", &n);

("\Vvedite chiclo m ");("%d", &m);

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

for (i=0; i<n; i++)_item(i+1);

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

s->next=first;

first->prev=s;=first;(i=0; i<n; i++){

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

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

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

}("\n");

=first;(n>1)

{=s;(i=1; i<m; i++)=p->next;>next->prev=p->prev;>prev->next=p->next;=p->next;p;-;

}("%d ",s->n);

getch();

}

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

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

#include<stdio.h>

#include<conio.h>

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

struct Titem {n;*next,*prev;

} *first,*s,*p;

 n,m;

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

void add_item(int v){

Titem *p;(s==NULL && first==NULL){=new Titem;>n = v;>next = NULL;>prev = NULL;=s;

}{= new Titem;>n = v;>next=NULL;>prev=s;>next=p;=p;

}

return;

}

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

int main (){

i;

("\Vvedite chiclo n ");("%d", &n);

("\Vvedite chiclo m ");("%d", &m);

(i=0; i<n; i++) //Запускаем функцию "add_item"_item(i+1);>next=first; //Замыкаем список>prev=s;

=first;(i=0; i<n; i++){("%d ",p->n); //Выводим на экран исходный список

p=p->next;

}("\n");

s=first;(n>1){

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

p=s;(i=1; i<m; i++)=p->next;>next->prev=p->prev;

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

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

n--;

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

();

}

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 с.: ил.

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ

Листинг программного кода

#include<stdio.h>

#include<conio.h> //библиотека с функцией getch

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

{n;*next,*prev;

}

*first,*s,*p;n,m;add_item(int v) /*Описываем функцию "add_item" добавляющую в список порядковые номера участников*/

{*p;

(s==NULL && first==NULL){=new Titem;>n = v;>next = NULL;>prev = NULL;=s;

}

{= new Titem;>n = v;>next=NULL;>prev=s;>next=p;=p;

};

{main ()

{i;

("\Vvedite chiclo n ");("%d", &n);

("\Vvedite chiclo m ");("%d", &m);

(i=0; i<n; i++) //Запускаем функцию "add_item"_item(i+1);>next=first; //Замыкаем список>prev=s;

=first;(i=0; i<n; i++){("%d ",p->n); //Выводим на экран исходный список

p=p->next;

}("\n");

s=first;(n>1){

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

p=s;(i=1; i<m; i++)=p->next;>next->prev=p->prev;

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

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

n--;

}

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

();

}