Динамические структуры данных. Списки

Список - это набор связанных между собой динамических элементов.

Элемент односвязной динамической структуры данных состоит из двух полей: информационного и указательного и описывается  типом «структура».

Очередь – частный случай линейного односвязного списка, для которого разрешены два действия: добавление элемента строго в конец списка, а извлечение (удаление) - строго из начала (головы) очереди.

Стек -  частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элемент только с одного конца списка, который называется вершиной стека.

Пример. Задать списком строку, заканчивающуюся точкой. Подсчитать число цифр в ней.

 

#include <conio.h>

#include <stdio.h>

typedef struct zv

{

char info;

     struct zv * next;

} Zv;

 

Void main()

{

     Zv * P;

     Zv * t;

     char sym;

     int k;

     clrscr();

     printf("Vvedite stroku i tochku ");

     P=NULL;

     do                 /* заполнение стека */

        {

              sym=getche();

                        t=malloc(sizeof(Zv));

         t->next=P; P=t;

         t->info=sym;

     } 

     while(sym!='.');

 

              k = 0;     t = P;

              while (t!=0)

     {

              if (t->info >= '0' && t-> info <= '9') k = k+1;

              t = t->next;

     }

     printf("\n");

     printf("Цифр в строке - %d",k);

   getch();

}

    

Задание 1 ( программа 14_1 )

1. Используя динамическую структуру список, подсчитать количество русских строчных букв в строке.

2. Используя динамическую структуру список, проверить, является ли он упорядоченным набором чисел.

3. Используя динамическую структуру список, подсчитать количество цифр в заданном наборе символов.

4. В деке задать слово. Определить, является ли оно словом-перевертышем.

5. Сформировать динамический список из элементов целого типа. Удалить из него отрицательные элементы. Распечатать исходный и результирующий списки.

6. Найти сумму четных элементов списка, состоящего не менее чем из двух элементов.

7. Используя динамическую структуру список, подсчитать сумму чисел в нем.

8. В динамическом списке из каждой группы подряд идущих одинаковых элементов оставить один.

9. Используя динамическую структуру список, подсчитать количество четных чисел в заданном наборе символов.

10. Используя динамическую структуру список, подсчитать сумму отрицательных чисел в списке.

11. Сформировать очередь из элементов целого типа. Четные элементы возвести в квадрат. Распечатать исходную и результирующую очереди.

12. Используя динамическую структуру список, подсчитать количество положительных и отрицательных чисел в списке.

13. Задать два динамических списка. Проверить их на равенство.

14. Используя динамическую структуру список для хранения символов, напечатать только русские буквы из текста.

15. Используя динамическую структуру, список для хранения символов, определить, является ли заданная фраза палиндромом.

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

17. Используя динамическую структуру очередь, перевести введенную последовательность чисел в слово, состоящее из кодов ASCII.

18. Удалить из списка все отрицательные элементы.

19. Используя динамическую структуру список, сохранить ряд чисел. Удалить повторяющиеся элементы.

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

21. Используя динамическую структуру список, сохранить ряд чисел. Удалить элемент с заданным номером.

22. Сформировать динамическую структуру «очередь», элементами которой являются цифры. Извлекая элементы из очереди, напечатать их двоичные эквиваленты.

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

24. Используя динамическую структуру стек, распечатать элементы в обратном порядке.

25. Используя динамическую структуру "очередь", зашифровать содержимое текста: каждый символ заменить его кодом+1.

26. Используя динамическую структуру "стек", зашифровать содержимое текстового файла.

27. Используя динамическую структуру список, сохранить ряд чисел. Удалить элементы с заданным ключевым полем.

Задание 2 ( программа 14_2 )

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

Лабораторная работа 15

Графика

Цель работы: знакомство с графическими процедурами и функциями.

Пример: Пусть необходимо построить график циклоиды. Зададим ее математи­ческое описание:

x = a t - b sin t, y = a - b cos t,

при b<a циклоида получается укороченной, при b>a - удлиненной, b = a да­ет обычную циклоиду.

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

Поскольку в графическом режиме работы дисплея верхняя левая точка экрана имеет координаты (0,0), сместим ось 0Х на середину экрана, а ось 0У - на 10 пикселей вправо. Для наглядности увеличим график путем использования масштабных коэффициентов по каждой оси координат. Кроме того, нужно помнить, что координаты точки в графическом режиме могут быть только целого типа.

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

#include <graphics.h>

#include <conio.h>

#include <math.h>

Void main()

{

int a = DETECT, b, k;

float x, y, t;

 initgraph(&a,&b,"C:\\TC\\BGI\0");

setgraphmode(2);

setbkcolor(0);

setcolor(4);

 moveto(0, 240);

 linerel(625, 0);

getch();

setcolor(2);

line(10, 0, 10, 478);

setcolor(5);

   getch();

moveto(10, 240);

t=0.0;          // текущее значение параметра t из задания

for (k =0; k<200; ++k)

{    

      x = 0.4 * t - 0.5*sin(t);

       y = 0.4 - 0.5*cos(t);

       lineto(100*x + 10, 100*y + 240);

       t = t + M_PI/32;

}

   getch();

settextstyle(0, 0, 3);

outtextxy(50, 440, "График циклоиды");

   getch();

    closegraph ();

}

Поскольку вычисляемые в программе координаты являются веществен­ными, то для их преобразования к целым значениям использована функция TRUNC().

При разработке графических программ необходимо следить, чтобы значения координат не выходили за пределы экрана. Для этого рекоменду­ется рассчитывать коэффициенты увеличения или уменьшения, а также па­раметры смещения изображения.

Задание 1 ( программа 15_1 )

Начертить графики функций F1(x) и F2(x) для результатов, получен­ных в программе 3_2.pas. На экран должен выводиться график с надписью выводимой функции.

Задание 2 ( программа 15_2 )

Напишите и отладьте программу для одной следующих задач.

1. Подготовить и отладить программу вычерчивания квадрата, вписанного в окружность. Запрограммировать изменение цветов окружности.

2. Организовать вывод на экран разноцветных цифр поочередно гори­зонтально и вертикально.

3. Отладить программу вычерчивания нескольких окружностей заданного радиуса в произ­вольном месте экрана разными цветами. Предусмотреть их мерцание.

4. Разработать программу изображения точки, движущейся по косинусоиде (y = cos(x)).

5. Отладить программу рисования квадрата с диагоналями, пресекающимися в центре эк­рана. Создать иллюзию его уменьшения.

6. Начертить на экране картинку «круги на воде».

7. Изобразить движущийся на зрителя экран (прямоугольник).

8. Подготовить и отладить программу изображения правильного треугольника, вращающегося вокруг своей (любой) медианы.

9. Разработать программу вывода на экран компьютера пяти квадратов по углам и в середине экрана. Зап­рограммировать поочередный вывод их разными цветами.

10. Разными цветами в различных точках экрана выводить надпись «TurboPascal» с изменением размера шрифта.

11. Изобразить трубу, образованную разноцветными окружностями.

12. Организовать вывод на экран названия континентов разными цве­тами в различных точках экрана готическим и обычным шрифтами.

13. Изобразить спутник (точку), вращающийся вокруг планеты.

14. Изобразить НЛО, приземляющийся в различных точках экрана.

15. Организовать вывод на экран разноцветных русских букв разных размеров поочередно высвечивая или заполняя экран в хаотическом порядке.

16. Отладить программу вычерчивания графиков функций y = sin(x) и y = sin(2x) разными цветами с разными осями координат.

17. Организовать вывод на экран формул химических элементов разными цве­тами в различных точках экрана.

18. Начертить на экране ряд геометрических фигур: квадрат, круг, треугольник, прямоугольник, используя разные цвета.

19. Изобразить схематично на экране движущегося человечка.

20. Изобразить движение объекта по прямоугольной спирали.

ЗАДАНИЕ К РАСЧЕТНО-ГРАФИЧЕСКОЙ РАБОТЕ

Разработать схему алгоритма, написать и отладить программу для расчета и построения графиков двух функций (результаты расчетов должны храниться в виде массивов и распечатываться в виде таблицы) [5] необходимо выделить наибольшее и наименьшее значения для каждой из функций. Добавить в нее решение нелинейного уравнения и вычисления приближенного значения определенного интеграла по заданию преподавателя.

Разработать программу нахождения корней уравнения f(x)=0 на интервале [a,b] с точностью e=0.001 (интервал подобрать или рассчитать самостоятельно). При реализации можно использовать метод половинного деле­ния (бисекции) или метод хорд [9]:

1. x - 2e^-x - = 0.                          2. x² - ln(x+1) + sin x -2 = 0.

3. 5x - e^x -2x  = 0.                      4. 2x lg x - 3 = 0.

5. 2^x - 3x - 2 = 0.                             6. 0,5 + cos x - 2x sin x = 0.        

7. sin x + x - 3 = 0.                          8. x e^x – 2 x² - 1 = 0.         

9. + 2x - 3 = 0.             10. 2 ln(x+1) - x + 1 = 0.    

11. tg x - e^x+1 = 0.                                12. 2 ln(x+1) + arctg x -3 = 0.    

13. x³ - 2x² - 4 = 0.                            14. 5x² - 2x ln x-7 = 0.

15. 2 - 3 sin x = 5.                16. 2x³ - 3x² - 4 = 0.

17. 4x - sin2x -3 = 0.                         18. 2x sin² x-3  = 0.

19. 2 ln(x+1)-3 sin2x = 4.                  20. x³ + 3x + 2 = 0. 

                                                                 

Разработать программу для вы­числения значения определенного интеграла на интервале [a,b] (a, b подобрать самостоятельно) численными методами прямоугольников и трапеций [9] для следующих вариантов:

1.               2.             3.     4.                  5.                            6.

7.               8.                       9.

10.          11.       12.

13.      14.          15.

16.       17.                18.                                       

19.                  20.       

 Интервал интегрирования разбить равномерно на N>50 частей.

 

Библиографический список

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

2. ГОСТ 19.701-90. ЕСПД. Схемы алгоритмов, пpогpамм, данных и систем. – М.: Изд-во стандартов, 1991. – 26 с.

3. Кpячков, А.В. и дp. Пpогpаммиpование на С и С++. Практикум. / А.В. Кpячков и дp. – М.: Радио и связь, 1997. – 344 с.

4. Макогон, В.С. Язык программирования Си для начинающих / В.С. Макогон. – Одесса: НПФ "АСТРОПРИНТ", 1993. – 96 с.

5. Методы проектирования программ: Метод. указания / Сост. О. П. Шафеева. –Омск: Изд-во ОмГТУ, 2004. – 32 с.

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

7. Подбельский, В.В. Программирование на языке Си / В.В. Подбельский, С.С. Фомин. – М.: 2000 – 600 с.

8. Флоренсов, А.Н. Введение в программирование. Семантический подход: учеб. пособие / А.Н. Флоренсов. – Омск: Изд-во ОмГТУ, 1998. – 220 с.  

9. Численные методы: Метод. указания. / Сост.: О. Б. Малков, Е. Т. Гегечкори. – Омск: Изд-во ОмГТУ, 1995. – 28 с.

10. Шафеева, О.П. Технологии программирования. С++: учеб. пособие / О.П. Шафеева. – Омск: Изд-во ОмГТУ, 2007. – 80 с.

11. Шилд, Г. Справочник программиста по С/С++. Учеб. Пособие / Г. Шилд – М.: Издательский дом «Вильямс», 2000. – 448 с.

Приложение А

Г л а в н о е м е н ю

File                  Edit           Search            Run       Compile (Alt+F)         (Alt+E)       (Alt+S)       (Alt+R)         (Alt+C) Файл           Редактор     Поиск     Выполнение    Компиляция
NEW Создать новый   файл OPEN F3 Открыть         файл SAVE F2 Сохранить       файл SAVE as... Сохранить     под именем … SAVE ALL Сохранить           все __________ CHANGE DIR Смена каталога PRINT  Распечатать DOS SHELL          Выход      в DOS DOS QUIT                ALT + X	UNDO Alt + BkSp Удалить изменения REDO Восстановить                            изменения _____________ CUT Shift - Del Убрать фрагмент в буфер COPY Ctrl-Ins Копировать в буфер PASTE Shift-Ins Вставить из буфера CLEAR Ctrl - Del Удалить фрагмент COPY EXAMPLE Копировать пример SHAW CLIPBOARD Открыть окно буфера	FIND Найти фрагмент REPLACE Заменить фрагмент SEARCH AGAIN Повторить поиск Ctrl + F 2 __________ GO TO LINE NUMBER Перейти к        строке с номером   PREVIOUS ERROR Предыдущая ошибка NEXT ERROR Следующая ошибка   LOCATE FUNCTION Разместить функцию	RUN Ctrl-F9 Запуск на выполнение PROGRAM RESET Ctrl - F 2 Перезапуск программы   GO TO CURSOR F4 Выполнение до курсора   TRACE INTO F7 Трассировка с заходом в п/п   STEP OVER F8 Выполнение по строкам без захода в п/п ARGUMENTS Аргументы	COMPILE             Alt - F 9 Компиляция файла из        окна MAKE F9 Условная рекомпиляция LINK Компоновать ____________ BUILD ALL Безусловная рекомпиляция всей программы   INFORMATION Информация   REMOVE MESSAGE Убрать отчет об ошибках

С р е д ы Турбо Cu

Debug         Alt + D Отладка INSPECT  наблюдать ALT + F 4 EVALUATE / MODIFY   Ctrl - F 4 Вычислить/ изменить CALL STACK                        Ctrl - F 3               Oкнo подпрограммы  WATCHES Параметры TOGGLE BREAKPOINT Обозначить точку прерывания Ctrl + F 8   BREAKPOINTS Точки  прерывания

Project                             проектирова ние (ALT + P) OPEN PROJECT Открыть проект CLOSE PROJECT Закрыть проект   ADD ITEM Добавить                пункт   DELETE ITEM Удалить пункт   LOCAL OPTOIN Отдельные опции   INCLUDE FILES Включить в программу файлы

Options                      Alt+O Параметры APPLICATION Приложение COMPILER    Параметры TRANSFER Переместиться в выбранное MAKE Выполнить выбранные действия LINKER Параметры компоновщика LIBRARIAN Библиотечные параметры DEBUGGER Отладчик DIRECTORIES Каталоги ENVIRONMENT  Условия  работы SAVE Сохранение параметров

Window Alt+W        Окна SIZE / MOVE Ctrl + F 5 Перемещение, изменение размеров ZOOM F 5 Раскрыть на экран  CASCADE Окна каскадом TILE Непересека- ющиеся NEXT        F 6 Следующее CLOSE Alt - F 3  Закрыть текущее CLOSE ALL Закрыть все            окна  MESSAGE Окно сообщений OUTPUT Окно результата WATCH Окно отладки USER SCREEN Пользов. экран PROJECT Окно проекта LIST ALL Список всех окон

Help Alt+H        Помощь CONTENTS Содержание INDEX Ключевые     слова Shift+F1 TOPIC SEARCN    Поиск темы Ctrl+F1   PREVIOUS TOPIC Предыдущая тема Alt + F 1 Help on Help Справка о пользователе   ACTIVE FILE Действующий файл помощи ABOUT Версия языка

 

Приложение Б

Операции языка С/С++

Вес	Знак	Наименование операции	Тип операции	Порядок
1	() [] .   ->	вызов функции  выделение элемента массива  выделение элемента структуры или объединения  выделение элемента структуры или объединения (объединения), адресуемой (го) указателем	Выражение	Слева направо
2	! ~ - ++ -- & * (тип) sizeof	логическое отрицание       побитовое отрицание      изменение знака (унарный минус)     увеличение на 1 (инкремент) уменьшение на 1 (декремент)        определение адреса         обращение по адресу    преобразование типа определение размера в байтах	унарные	Справа налево
3	* / %	умножение                     деление           остаток от деления	бинарные арифмети-ческие	Слева направо
4	+ -	сложение вычитание	бинарные арифмети-ческие	Слева направо ®
5	<< >>	сдвиг влево сдвиг вправо	сдвига	Слева направо
6	< <= > >=	меньше чем    меньше или равно                больше чем                      больше или равно	отношения	Слева направо
7	==                                                !=	равно             неравно	отношения	Слева направо
8	&	поразрядная операция "И"	побитовая	®
9	^	«исключающее "ИЛИ"»	побитовая	®
10	|	поразрядная "ИЛИ"	побитовая	®
11	&&	логическая операция "И"	логическая	®
12	||	логическая операция "ИЛИ"	логическая	®
13	?:	условная операция	тернарная
14	=    += -= *= /= %= <<=   >>= &= |=   ^=	простое присваивание          составные присваивания:  сложение с присваиванием вычитание с присваиванием умножение с присваиванием деление с присваиванием    остаток от деления с присваиванием сдвиг двоичного числа влево с присваиванием сдвиг двоичного кода вправо с пр.  побитовая операция "И" с присв.  поразрядная операция "ИЛИ" c присваиванием             исключающее "ИЛИ" с присваив.	присваи-вания бинарные     (для двоичных операндов)	Справа налево
15	,	операция "запятая" (соединения)	тернарная	®

 

Приложение В

Типы данных

№	Обозначение	Размер (байт)	Диапазон	Тип данных
1	char,     signed char	1	-128...127	Символьный со знаком
2	unsigned char	1	0...255	Символный без знака
3	short, short int,                    signed short, signed short int	2	-32768... 32767	Короткое целое со знаком
4	unsigned short,                   unsigned short int	2	0...65535	Короткое целое без знака
5	int, signed,  signed int	1, 2, 4	Зависит от реализации	Целое
6	unsigned,  unsigned int	1, 2, 4	Зависит от реализации	Целое без знака
7	long, signed long, long int	4	-2147483648 …2147483647	Длинное целое со знаком
8	unsigned long	4	0...4294967295	Длинное целое без знака
9	float	8	-3.4e-38... 3.14e+38	Вещественное число с плавающей точкой
10	double	8	-1.7е-308..1.7е308	Вещественное число удвоенной точности
11	long double	10	-3.4e-4932...              .4e4932	Длинное вещественное                  число удвоенной точности

Приложение Г