Создание и обработка динамического списка

Создание и обработка динамического списка

Пензенский технологический институт (завод-втуз)

Факультет ФСВТ

Кафедра Вмис

Пояснительная записка

к курсовой работе по дисциплине:

«Алгоритмические языки и программирование»

на тему

«Создание и обработка динамического списка»

Выполнил: студент группы 02В2

Новокшонов М.С.

Руководитель: Данилина Н.П.

Проект защищен с оценкой ________

Пенза 2003

[pic]

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

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

программу, которая выполняет следующие действия:

o Создание однонаправленного динамического списка содержащего сведения о

книгах

o Вывод данных однонаправленного динамического списка на экран

o Удаление первого элемента однонаправленного динамического списка.

o Перемена мест элементов однонаправленного динамического списка, которые

заданы ключами.

Программу построить по процедурному принципу, пользовательский элемент

оформить в виде меню.

3

2. Разработка метода решения задачи и его формализация

1) В данной программе будут использоваться следующие глобальные переменные:

n – массив 30 переменных типа char. Несет информацию о названии газеты.

s – массив 30 переменных типа char. Несет информацию о названии статьи

st – переменная типа int. Несет информацию о номере страницы.

Все эти переменные являются элементами структуры gaseta:

struct games {

char n[30];

char s[30];

int st;};

g – переменная типа gaseta. Несет полную информацию о газете.

n – указатель на структуру news.

Все эти переменные являются элементами структуры news:

struct news{

gaseta g;

news *n;};

un – указатель на структуру news. Несет информацию об адресе первого

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

p – указатель на структуру news. Несет информацию об адресе текущего

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

q – указатель на структуру news. Несет информацию об адресе последнего

созданного элемента однонаправленного динамического списка.

news *un,*p,*q;

i – переменная типа int. Несет информацию о количестве элементов

однонаправленного динамического списка.

int i;

4

2) Локальные переменные процедуры ввода данных:

j – переменная типа int. Эта переменная является параметром всех циклов

используемых в данной процедуре.

int j;

3) Локальные переменные процедуры вывода данных:

j – переменная типа int. Эта переменная является параметром всех циклов

используемых в данной процедуре.

int j;

4) Локальные переменные процедуры удаления первого элемента списка:

У данной процедуры нет локальных переменных.

5) Локальные переменные процедуры перемены мест элементов, которые заданы

по названию:

j – переменная типа int. Эта переменная является одним параметром всех

циклов используемых в данной процедуре.

int j;

k1 – переменная типа char. Несет информацию о названии первой газеты,

место которой будем менять.

k1 – переменная типа cnar. Несет информацию о названии второй газеты,

место которой будем менять.

char k1[30],k2[30];

p2 – указатель на структуру news. Несет информацию об адресе второго

текущего элемента однонаправленного динамического списка.

news *p2;

c - переменная типа gaseta. Несет полную информацию об игре.

gaseta c;

5

6) Локальные переменные основной части программы:

a – переменная типа int. Несет информацию о текущей процедуре и является

параметром цикла и оператора множественного выбора.

int a;

6

3. Разработка состава и структуры исходных данных и результата

Исходные данные и результат представляют собой однонаправленный

динамический список. Элементом списка будет являться структура, состоящая

из внутренней структуры и указателя на следующий элемент списка. Внутренняя

структура состоит из полей:

1) название газеты (тип char)

2) название статьи (тип char)

3) номера страниц (тип int)

[pic]

На экране исходные данные будут представлены:

Введите данные о 1 статье

Название: Комсомольская правда

Статья: О вреде курения

Страница: 12

………………………………

Результат будет представлен в виде таблицы:

+---------------+--------------+--------------+

| газета | статья

| страница |

|Комсомольская правда | О вреде курения |

12 |

7

4. Разработка алгоритма

4.1 Основная часть программы.

0. Начало

1 Очищаем экран

2 Присваиваем переменной а, которая является параметром последующего цикла

и оператора множественного выбора значение равное единицы

3 Открываем цикл с предусловием (условие: переменная а не равна 5); в цикле

будут выполняться шаги с 4 по 11

4 Вводим переменную а

5 Выполняем оператор множественного выбора с параметром а; оператор

включает шаги с 6 по 10

6 Если а=1, вызываем процедуру ввода данных

7 Если а=2, вызываем процедуру вывода данных

8 Если а=3, вызываем процедуру удаления первого элемента

9 Если а=4, вызываем процедуру перемены мест элементов, которые заданы

названиями

10 Если а не равно не одному из указанных раннее значений, то а присваиваем

значение 5

11 Закрываем оператор множественного выбора

12 Закрываем цикл с предусловием

13 Конец

4.2 Процедура ввода данных

0 Начало процедуры

1 Резервируем область оперативной памяти размером равным размеру элемента и

присваиваем указателю на последний элемент q адрес этой области.

2 Последовательно вводим данные внутренней структуры, на которую будит

указывать указатель q.

3 Присваиваем указателю на первый элемент списка un и указателю на текущий

элемент p значение указателя q. Присваиваем переменной i, которая содержит

данные о числе элементов списка и переменной j, которая является параметром

последующих циклов значение равное 1

4 Открываем цикл с предусловием (условие: переменная j равна 1); в цикле

будут выполняться шаги с 5 по 9

8

5 Увеличиваем значение переменной i на единицу

6 Резервируем область оперативной памяти размером равным размеру элемента и

присваиваем указателю q адрес этой области

7 Последовательно вводим данные внутренней структуры, на которую будит

указывать указатель q

8 Устанавливаем указатель введенного ранее элемента n на элемент, введенный

шагом 7, а указателю p значение указателя q

9 Вводим новое значение переменной j

10 Закрываем цикл с предусловием

11 Устанавливаем указатель n текущего элемента на NULL

12 Конец процедуры

4.3 Процедура вывода данных

0 Начало процедуры

1 Устанавливаем указатель p на первый элемент списка, а переменную j,

которая будет параметром следующего цикла, устанавливаем в 1

2 Открываем цикл с предусловием (условие: переменная j меньше или равно i);

в цикле будет выполняться шаги с 3 по 4

3 Последовательно выводим данные внутренней структуры, на которую будит

указывать указатель p

4 Указатель текущего элемента p устанавливаем на следующий элемент, а

значение переменной j увеличиваем на 1

5 Закрываем цикл с предусловием

6 Конец процедуры

4.4 Процедура удаления первого в списке элемента

0 Начало процедуры

1 Указатель текущего элемента p устанавливаем в начало, а указатель первого

элемента в списке un устанавливаем на следующий элемент

2 Освобождаем область памяти, на которую указывает указатель текущего

элемента p

9

3 Значение переменной i, которая содержит данные о числе элементов в

списке, уменьшаем на 1

4 Конец процедуры

4.5 Процедура перемены мест элементов, которые заданы номерами

0 Начало процедуры

1 Вводим переменную k1, которая указывает на название первого элемента в

операции перемены мест

2 Устанавливаем указатель p на первый элемент списка.

3 Открываем цикл с заданным числом повторений (j=0…k1); в цикле будет

выполняться шаг 4

4 Указатель на текущий элемент p устанавливаем на следующий элемент списка

5 Закрываем цикл с заданным числом повторений

6 Вводим переменную k2, которая указывает на название второго элемента в

операции перемены мест

7 Устанавливаем указатель p2 на первый элемент списка.

8 Открываем цикл с заданным числом повторений (j=0…k2); в цикле будет

выполняться шаг 4

9 Указатель на текущий элемент p2 устанавливаем на следующий элемент списка

10 Закрываем цикл с заданным числом повторений

11 Переменной с присваиваем данные внутренней структуры, на которые

указывает указатель текущего элемента p

12 Данные внутренней структуры, на которые указывает указатель текущего

элемента p2, копируем в переменные внутренней структуры, на которые

указывает указатель текущего элемента p.

13 Значение переменной с присваиваем переменным внутренней структуры, на

которые указывает указатель текущего элемента p2.

14 Конец процедуры

10

5. Выбор языка

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

был разработан на основе языка СИ Бьярном Страуструпом. Выбор языка СИ++

для решения данной задачи обусловлен наличием в языке СИ++ средств для

динамического распределения памяти.

Динамическое распределение памяти осуществляется операциями new и

delete. Это 2 особые унарные операции, появившиеся в языке СИ++ (в языке СИ

этих операций не было). Операция new имя_типа или new имя_типа

инициализатор позволяет выделить и сделать доступным свободный участок в

основной памяти, размеры которого соответствуют типу данных, определяемому

именем типа. В выделенный участок заносится значение, определяемое

инициализатором, который не является обязательным элементом. В случае

успешного выполнения операции new возвращает адрес начала выделенного

участка памяти. Если участок нужных размеров не может быть выделен (нет

памяти), то операция new возвращает нулевое значение адреса (NULL).

Синтаксис применения операции: указатель=new имя_типа инициализатор.

Продолжительность существования выделенного с помощью операции new

участка памяти – от точки создания до конца программы или до явного его

освобождения.

Для явного освобождения выделенного операцией new участка памяти

используется оператор delete указатель, где указатель адресует

освобождаемый участок памяти, ранее выделенный с помощью операции new.

11

6. Разработка программы

6.1 Основная часть программы.

0 Начало. Описываем глобальные переменные и типы данных

1 Очищаем экран с помощью оператора clrscr()

2 Присваиваем переменной а, которая является параметром последующего цикла

и оператора множественного выбора значение равное единицы: a=1

3 Открываем цикл с предусловием (условие: переменная а не равна 5); в цикле

будут выполняться шаги с 4 по 11: while (a!=5)

4 Вводим переменную а: a=getch()

5 Выполняем оператор множественного выбора с параметром а; оператор

включает шаги с 6 по 10: switch(a)

6 Если а=1, вызываем процедуру ввода данных: case '1':vvod(); break

7 Если а=2, вызываем процедуру вывода данных: case '2':vivod(); break

8 Если а=3, вызываем процедуру удаления первого элемента: case '3':dele();

break;

9 Если а=4, вызываем процедуру перемены мест элементов, которые заданы

номерами: case '4':pomen(); break;

10 Если а не равно не одному из указанных раннее значений, то а присваиваем

значение 5: default: a=5; break;

11 Закрываем оператор множественного выбора: }

12 Закрываем цикл с предусловием: }

13 Конец: }

6.2 Процедура ввода данных

0 Начало процедуры: void vvod(); Описываем локальные переменные

1 Резервируем область оперативной памяти размером равным размеру элемента и

присваиваем указателю на последний элемент q адрес этой области:

q=new(news)

2 Последовательно вводим данные внутренней структуры, на которую будет

указывать указатель q. Ввод будем осуществлять с помощью последовательности

операторов ввода scanf

12

3 Присваиваем указателю на первый элемент списка un и указателю на текущий

элемент p значение указателя q. Присваиваем переменной i, которая содержит

данные о числе элементов списка и переменной j, которая является параметром

последующих циклов значение равное 1: un=q; p=q; j=1; i=1;

4 Открываем цикл с предусловием (условие: переменная j равна 1); в цикле

будут выполняться шаги с 5 по 9: while (j==1)

5 Увеличиваем значение переменной i на единицу: i++

6 Резервируем область оперативной памяти размером равным размеру элемента и

присваиваем указателю q адрес этой области: q=new(news);

7 Последовательно вводим данные внутренней структуры, на которую будет

указывать указатель q. Ввод будем осуществлять с помощью последовательности

операторов ввода scanf

8 Устанавливаем указатель введенного ранее элемента n на элемент, введенный

шагом 7, а указателю p значение указателя q: p->n=q; p=q;

9 Вводим новое значение переменной j. Ввод будем осуществлять с помощью

оператора ввода scanf

10 Закрываем цикл с предусловием: }

11 Устанавливаем указатель n текущего элемента на NULL: p->n=NULL;

12 Конец процедуры: }

6.3 Процедура вывода данных

0 Начало процедуры: void vivod(); Описываем локальные переменные

1 Устанавливаем указатель p на первый элемент списка, а переменную j,

которая будет параметром следующего цикла, устанавливаем в 1: p=un; j=1;

2 Открываем цикл с предусловием (условие: переменная j меньше или равно i);

в цикле будет выполняться шаги с 3 по 4: while (jn; j++;

5 Закрываем цикл с предусловием: }

6 Конец процедуры: }

6.4 Процедура удаления элемента заданного по имени

0 Начало процедуры: void dele(); Описываем локальные переменные

1 Указатель текущего элемента p устанавливаем в начало, а указатель первого

элемента в списке un устанавливаем на следующий элемент: p=un; un=un->n;

2 Освобождаем область памяти, на которую указывает указатель текущего

элемента p: delete p;

3 Значение переменной i, которая содержит данные о числе элементов в

списке, уменьшаем на 1: i=i-1;

4 Конец процедуры

6.5 Процедура перемены мест элементов, которые заданы номерами

0 Начало процедуры: void pomen();Описываем локальные переменные

1 Вводим переменную k1, которая указывает на название первого элемента в

операции перемены мест. Ввод будем осуществлять с помощью оператора ввода

scanf

2 Устанавливаем указатель p на первый элемент списка: p=un;

3 Открываем цикл с заданным числом повторений (j=0…k1); в цикле будет

выполняться шаг 4: for(j=1;jn;

5 Закрываем цикл с заданным числом повторений: }

6 Вводим переменную k2, которая указывает на название второго элемента в

операции перемены мест. Ввод будем осуществлять с помощью оператора ввода

scanf

7 Устанавливаем указатель p2 на первый элемент списка: p2=un

8 Открываем цикл с заданным числом повторений (j=0…k2); в цикле будет

выполняться шаг 4: for(j=1;jn;

14

10 Закрываем цикл с заданным числом повторений: }

11 Переменной с присваиваем данные внутренней структуры, на которые

указывает указатель текущего элемента p: с=p->g;

12 Данные внутренней структуры, на которые указывает указатель текущего

элемента p2, копируем в переменные внутренней структуры, на которые

указывает указатель текущего элемента p: p->g=p2->g;

13 Значение переменной g1 присваиваем переменным внутренней структуры, на

которые указывает указатель текущего элемента p2: p2->g=с;

14 Конец процедуры: }

15

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

Суть процесса тестирования и отладки программы заключается в проверке

правильности программы и исправлении найденных ошибок. В ходе процесса

отладки и тестирования возникали следующие ошибки:

Statement missing ; - отсутствие знака конца оператора.

16

Список используемой литературы

1 В. В. Подбельский. Язык СИ++. - М.: Финансы и статистика, 2003.

2 Б. И. Березин, С. Б. Березин. Начальный курс С и С++. – М.: Диалог-МИФИ,

1998.

17

ПРИЛОЖЕНИЕ 1

18

19

20

21

ПРИЛОЖЕНИЕ 2

# include

# include

# include

struct gaseta{

char n[30];

char s[30];

int st;};

struct news{

games g;

play *n;};

play *un,*p,*q;

int i;

void vvod()

{

int j;

q=new(news);

printf("Введите данные о 1 статье\n");

printf("Газета: ");

scanf("%s",&q->g.n);

printf("Статья: ");

scanf("%d",&q->g.s);

printf("Страница: ");

scanf("%d",&q->g.st);

un=q;

p=q;

j=1;

i=1;

while (j==1)

{

i++;

q=new(news);

printf("Введите данные о %d", i );

printf(" игре\n");

printf("Газета: ");

scanf("%s",&q->g.n);

printf("Статья: ");

scanf("%d",&q->g.s);

printf("Страница: ");

scanf("%d",&q->g.st);

p->n=q;

p=q;

printf("Хотите продолжить? 1-да, 2-нет\n");

22

scanf("%d",&j);

}

p->n=NULL;

}

void vivod()

printf("+---------------+--------------+-------------+\n");

void dele()

{

p=un;

un=un->n;

delete p;

i=i-1;

printf("Обработка выполнена\n");

}

void pomen()

{

int j;

char k1[30],k2[30];

gaseta c;

news *p2;

printf("введите первое название газеты\n");

scanf("%s",&k1);

p=un;

while(strcmp(p->g.n,k1)!=0)

p=p->n;

printf("введите второе название газеты\n");

scanf("%s",&k2);

p2=un;

while(strcmp(p2->g.n,k2)!=0)

p2=p2->n;

c=p->g;

p->g=p2->g;

p2->g=c;

printf("Обработка выполнена\n");

}

23

main ()

{

int a;

clrscr();

a=1;

while (a!=5)

{

printf("Нажмите одну из кнопок\n");

printf("Ввод данных - 1\n");

printf("Вывод данных - 2\n");

printf("Удаление первого элемента - 3\n");

printf("перемена мест - 4\n");

printf("Выход - 5\n");

a=getch();

switch(a)

{

case '1':vvod(); break;

case '2':vivod(); break;

case '3':dele(); break;

case '4':pomen(); break;

default: a=5; break;

}

}

return 0;

}

24

ПРИЛОЖЕНИЕ 3

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных- 3

Перемена мест - 4

Выход – 5

1

Введите данные о 1 статье

Газета: Комсомольская правда

Статья: о вреде курения

Страница: 12

Введите данные о 2 статье

Газета: Пенза плюс тв

статья: проблемы

Страница: 6

Хотите продолжить? 1-да, 2-нет

1

Газета: Молодой ленинец

Статья: наркомания

Страница: 8

Хотите продолжить? 1-да, 2-нет

1

Газета: СПИД инфо

Статья: беременность

Страница: 20

Хотите продолжить? 1-да, 2-нет

1

Газета: московский комсомолец

Статья: пенсионная реформа

Страница: 9

Хотите продолжить? 1-да, 2-нет

2

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест - 4

Выход – 5

2

Данные о газетах

+---------------+--------------+--------------+

| название | год выпуска |

занимаемый объем |

| Комсомольская правда | о вреде курения|

12|

| Пенза плюс тв | проблемы|

6|

| Молодой ленинец | наркомания |

8|

| СПИД инфо | беременность|

20|

|Московский комсомолец| пенсионная реформа|

9|

25

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест-4

Выход – 5

3

Удаление выполнено

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест - 4

Выход – 5

2

Данные о газетах

+---------------+--------------+--------------+

| название | год выпуска |

занимаемый объем |

| Пенза плюс тв | проблемы|

6|

| Молодой ленинец | наркомания |

8|

| СПИД инфо | беременность|

20|

|Московский комсомолец| пенсионная реформа|

9|

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест - 4

Выход – 5

4

Введите название первой газеты

Пенза плюс тв

Введите название второй газеты

Молодой ленинец

Перемена мест выполнена

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест - 4

Выход – 5

2

Данные о газетах

+---------------+--------------+--------------+

| название | год выпуска |

занимаемый объем |

| Молодой ленинец | наркомания |

8|

| Пенза плюс тв | проблемы|

6|

| СПИД инфо | беременность|

20|

|Московский комсомолец| пенсионная реформа|

9|

26

Нажмите одну из кнопок

Ввод данных - 1

Вывод данных - 2

Удаление данных - 3

Перемена мест - 4

Выход – 5

5

27

-----------------------

a

p->n=q;

p=q;

void vvod ()

q=new(news)

Ввод q->g.n, q->g.s, q->g.st

un=q;

p=q;

j=1;

i=1;

Цикл 1

Пока (j== 1)

i++;

q=new(news);

Ввод q->g.n, q->g.s, q->g.st

Ввод j

Цикл 1

p->n=NULL;

Конец

a

p=un;

j=1;

void vivod ()

Цикл 1

Пока (jg.n, q->g.s, q->g.st

p=p->n;

j++;

Цикл 1

Конец

p=un;

un=un->n

void dele ()

Конец

delete p

i=i-1;

Цикл 1

j=1…k1

p=un;

Ввод k1

Цикл 1

void pomen ()

Цикл 1

p=p->n;

a

a

p2=un;

Ввод k2

Цикл 2

j=1…k2

p2=p2->n;

Конец

c=p->g;

p->g=p2->g;

p2->g=c;

b

c

d

e

e

d

c

b

pomen()

4

a

Конец

Цикл 1

a

vvod()

vivod()

dele()

a

1

2

3

Ввод a

Цикл 1

Пока a!=5

clrscr();

a=1;

Начало

Содержание

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

2 Разработка метода решения задачи и его формализация 4

3 Разработка состава структуры исходных данных и результата 7

4 Разработка алгоритма 8

5 Выбор языка программирования 12

6 Разработка программы 13

7 Отладка и тестирование программы 18

Список используемой литературы 19

Приложение 1: схема программы 20

Приложение 2: листинг программы 25

Приложение 3: результаты выполнения программы 29

Масса

КР-2201-14-03-ПЗ

Лит.

Масштаб

ПТИ

гр.02В2

Изм

Лист

№ докум.

Подпись

Дата

Разраб.

Пров.

Н.-конт.

Утв.

Т.-конт.

Лист 2

Листов 27

Данилина Н.П.

Новокшонов МС

Создание и обработка динамического списка.

Пояснительная записка

Указатель на первый элемент

Внутренняя

структура

Указатель на следующий элемент

Внутренняя

структура

NULL

Внутренняя

структура

Указатель на следующий элемент