Графическая и программная реализация алгоритмов обработки сложных структур данных

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН НАО «АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ»

Факультет «Информационные технологии»

Кафедра «Информационные системы»

ОТЧЁТ по расчётно — графической работе № 2

по дисциплине «Алгоритмы, структуры данных и программирование»

Тема: «Графическая и программная реализация алгоритмов обработки сложных структур данных»

Вариант № 19

Выполнил ст. гр. БИС-12−2

Нечаев Н.И.

Алматы 2013

1. Теоретическая часть

2. Задание А

2.1 Содержательная постановка задачи

2.2 Проектная часть

2.2.1 Словесное описание алгоритма

2.2.2 Блок — схема

2.2.3 Описание и схема пользовательского интерфейса

2.3 Прикладная часть

2.3.1 Программное описание алгоритма с индексами

2.3.2 Результат выполнения программы

3. Задание Б

3.1 Содержательная постановка задачи

3.2 Проектная часть

3.2.1 Словесное описание алгоритма

3.2.2 Блок — схема

3.2.3 Описание и схема пользовательского интерфейса

3.3 Прикладная часть

3.3.1 Программное описание алгоритма

3.3.2 Результат выполнения программы Заключение Приложение, А Приложение Б Список использованной литературы

Введение

Си — стандартизированный процедурный язык программирования, разработанный в начале 1970;х годов сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи. Си был создан для использования в операционной системе UNIX. С тех пор он был перенесён на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность. Он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков.

Язык программирования СИ — это универсальный язык с богатым набором операторов и компактным способом записи выражений. Язык C обеспечивает разнообразие типов данных. Базовыми типами являются целые, вещественные числа и символы (литеры). Язык разрешает модификацию базовых типов данных, а также создание пользовательских типов. В языке используются стандартные типы данных int, char, float, double; применяются массивы, структуры (записи), файлы; имеется возможность конструирования очередей, списков.

В данном отчете будет представлено решение двух типов задач: одномерного массива и матрицы соответственно. Будет представлено подробное описание решения в форме словесного описания, блок-схемы, кода программы, которую реализовали на языке Си. Также будет осуществлена проверка с помощью MS Excel.

1.

1. Теоретическая часть

Цель. Закрепить навыки разработки и программирования на языке Си алгоритмов обработки сложных структур данных: одномерных массивов и матриц. Приобрести навыки программирования с переменными типа указатель.

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

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

Существует 3 вида алгоритмов:

— линейный

— разветвляющийся

— циклический

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

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

Статические — к этой группе относят массивы, множества, записи, таблицы

Полустатические — это стеки, очереди, деки, дерева

Динамические — линейные и разветвленные связные списки, графы, дерева.

Массив представляет собой матрицу из нескольких переменных одного и того же типа.

Можно говорить о массивах целых чисел, массивов символов и.т.д. Мы можем даже определить массив, элементы которого — массивы (массив массивов), определяя, таким образом, многомерные массивы. Любой массив в программе должен быть описан: после имени массива добавляют квадратные скобки [], внутри которых обычно стоит число, показывающее количество элементов массива. Например, запись int x[10]; определяет x как массив из 10 целых чисел. В случае многомерных массивов показывают столько пар скобок, какова размерность массива, а число внутри скобок показывает размер массива по данному измерению. Например, описание двумерного массива выглядит так: int a[2][5]. Такое описание можно трактовать как матрицу из 2 строк и 5 столбцов. Для обрщения к некоторому элементу массива указывают его имя и индекс, заключенный в квадратные скобки (для многомерного массива — несколько индексов, заключенные в отдельные квадратные скобки): a[1][3], x[i] a[0][k+2]. Индексы массива в Си всегда начинаются с 0, а не с 1, т. е. описание int x[5]; порождает элементы x[0], x[1], x[2], x[3], x[4], x[5].

В общем случае объявление массива имеет следующий синтаксис:

тип_данных имя_переменной[<�количество_элементов>] = <�список, элементов, массива>

int arr[100];

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

char ch[] = {'R','u','b','y','D','e','v','.','r','u'};

Динамическим называется массив, размер которого может меняться во время исполнения программы.

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

Указатель — это переменная, значением которой является адрес некоторого объекта (обычно другой переменной) в памяти компьютера. Подобно тому, как переменная типа char имеет в качестве значения символ, а переменная типа int — целочисленное значение, переменная типа указателя имеет в качестве значения адрес ячейки оперативной памяти. Допустимые значения для переменной-указателя — множество адресов оперативной памяти компьютера.

Указатель является одной из наиболее важных концепций языка C.

· указатели являются средством, при помощи которого функции могут изменять значения передаваемых в нее аргументов;

· при помощи указателей выполняется динамическое распределение памяти;

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

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

Так как указатель может ссылаться на переменные разных типов, с указателем в языке Си связывается тип того объекта, на который он ссылается. Для описания указателей используется операция косвенной адресации *.

Общая форма объявления указателя:

тип *имя;

Например:

int *p1;

char *ch2;

float *fl1;

Понятие указателя тесно связано с понятием адреса объекта. В C есть специальная операция, позволяющая получить адрес любой переменной: &p — получение адреса, где p — идентификатор переменной. Результатом операции является адрес переменной p.

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

1. Определение адреса указателя: &p, где p — указатель (&p — адрес ячейки, в которой находится указатель).

2. Присваивание. Указателю можно присвоить адрес переменной p=&q, где p — указатель, q — идентификатор переменной.

3. Определение значения, на которое ссылается указатель: *p (операция косвенной адресации).

4. Увеличение (уменьшение) указателя. Увеличение выполняется как с помощью операции сложения (+), так и с помощью операции инкремента (++). Уменьшение — с помощью операции вычитания (-) либо декремента (—).

Например, пусть p1 — указатель, тогда р1++ перемещает указатель на:

a) 1 байт, если *p1 имеет тип char;

b) 4 байта, если *p1 имеет тип int (в 32 разрядной операционной системе) или 2 байта (в 16 разрядной операционной системе);

c) 4 байта, если *p1 имеет тип float.

5. Разность двух указателей. Пусть р1 и р2 — указатели одного и того же типа. Можно определить разность р1 и р2, чтобы найти, на каком расстоянии друг от друга находятся элементы массива.

Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.

2. Задание А

Составить блок схему и программу обработки одномерного массива. Элементы массива заполнить, используя функцию генератора случайных чисел. Программу написать двумя способами: 1) осуществляя доступ к элементам массива с помощью индексов; 2) осуществляя доступ к элементам массива с помощью указателей.

2.1 Содержательная постановка задачи

Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k — целая часть среднего арифметического значения нечётных элементов массива A[N].

2.2 Проектная часть

2.2.1 Словесное описание алгоритма

1. Начало алгоритма.

2. Задать размерность массива, то есть константе N присвоить заданное значение.

3. Заполнить массив A[N] случайными числами.

4. Вывести элементы массива A[N].

5. Обнулить переменные S и r.

6. Организовать цикл с заданными параметрами от i=1; N; 1.

Внутри цикла:

Проверить: если а[i]%2=0, то суммируем нечётные элементы массива, т. е. S=S+а[i], и число нечётных элементов увеличить на 1, т. е. r=r+1, иначе перейти к следующему шагу цикла.

7. Находим целую часть среднего арифметического значения нечётных элементов массива A[N], т. е. k: k=abs (S/r).

8. Организовать цикл с заданными параметрами от i=1; k; 1.

Внутри цикла:

a. Запомнить последний элемент f=a[N-1].

b. Организовать цикл с заданными параметрами от j=N; 1; -1.

Внутри цикла: последующему элементу присвоить предыдущий, т. е.

a[j]=a[j-1].

c. По окончании цикла по j первому элементу присвоить значение последнего, т. е. a[1]=a[N-1] и перейти к следующему циклу по i.

9. Вывести элементы массива a[i].

10. Конец алгоритма.

2.2.2 Блок — схема

2.2.3 Описание и схема пользовательского интерфейса

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

Она будет состоять из названия данной работы.

Ras4etno-grafi4eska9 rabota #2 zadanie A

=================================

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

Razmernost' massiva A[N]

Vvedite N

N=

Sgenerirovanniy massiv

sdvig elementov massiva a[n] na k poziciy

k-celaya chast srednego arifmeti4eskogo ne4etnyh 4isel

Vichislit' zanovo?

(esli da t=1,esli net t=0)

3. В случае выбора значение 1, программа должна продолжать работу и переходить к пункту 2. Если вы выбираете значение 0, программа завершит работу и перейдёт к пункту 4.

4. В случае завершения работы, программа выведет посередине наименование студента, выполнившего данную работу, и его группы. Чуть ниже, с правой стороны, программа выведет наименование преподавателя проверившего работу.

=================================

****************************************

==Vipolnil Nechayev Nikita Igorevi4==

=======Student gryppi BIS-12−2=======

****************************************

***************************************

==Proveril k.t.n. docent==

==_______________Ni A.G.==

=="" __" «____________2013==

***************************************

5. На следующей строчке будет надпись

Dl9 zaverweni9 nagmite klaviwu

2.3 Прикладная часть

2.3.1 Программное описание алгоритма с индексами:

#include

#include

#include

#include

#include

int main ()

{

int k, N, S, r, i, t, f, j;

int a[N];

float b;

puts («tt Ras4etno-grafi4eska9 rabota #2 zadanie A»);

puts («tt ===========================================»);

printf («Razmernost' massiva A[N]»);

m1:printf («n Vvedite NnN=»);

scanf («%d» ,&N);

S=0;

r=0;

for (i=0;i

{

a[i]=rand ()%10−5;

}

printf («n Sgenerirovanniy massivn»);

for (i=0;i

printf («%4d», a[i]);

for (i=0;i

{

b=a[i]%2;

if (b≠0)

{

r=r+1;

S=S+a[i];

}

}

k=abs (S/r);

for (i=0;i

{

f=a[N-1];

for (j=N-1;j>0;j—)

a[j]=a[j-1];

a[0]=f;

}

printf («n n sdvig elementov massiva a[n] na %d poziciy n», k);

for (i=0;i

printf («%4d», a[i]);

puts («n k-celaya chast srednego arifmeti4eskogo ne4etnyh 4isel»);

printf («n Vichislit' zanovo? n (esli da t=1,esli net t=0)nt=»);

scanf («%d» ,&t);

if (t>0)

{printf (««);goto m1;}

if (t<1)

puts («tt ===========================================»);

puts («****************************************»);

puts («==Vipolnil Nechayev Nikita Igorevi4==»);

puts («=======Student gryppi BIS-12−2=======»);

puts («****************************************»);

puts («***************************************»);

puts («==Proveril k.t.n. docent==»);

puts («==_______________Ni A.G.==»);

puts («==»" __" «____________2013==»);

puts («***************************************»);

printf («Dl9 zaverweni9 nagmite klaviwu «);

getch (); /* Zadergka do nagati9 luboi klaviwi */

return 0;

}

С указателями:

#include

#include

#include

#include

#include

int main ()

{

int k, N, S, r, i, t, f, j,*pa,*pb,*p;

int a[N];

float b;

puts («tt Ras4etno-grafi4eska9 rabota #2 zadanie A»);

puts («tt ===========================================»);

printf («Razmernost' massiva A[N]»);

m1:printf («n Vvedite NnN=»);

scanf («%d» ,&N);

S=0;

r=0;

pa=&a[0];

for (i=0;i

{

*pa=rand ()%10−5;

}

pa=&a[0];

printf («n Sgenerirovanniy massivn»);

for (i=0;i

printf («%4d» ,*pa++);

pa=&a[0];

for (i=0;i

{

b=*pa%2;

++pa;

if (b≠0)

{

r=r+1;

S=S+*pa;

}

}

k=abs (S/r);

for (i=0;i

{

pb=&a[9];

p=&a[0];

f=*pb;

for (j=0;j

*pb=*(—pb);

*p=f;

p=&a[0];

pb=&a[9];

}

printf («n n sdvig elementov massiva a[n] na %d poziciy n», k);

for (i=0;i

pb=&a[0];

printf («%4d» ,*pb++);

puts («n k-celaya chast srednego arifmeti4eskogo ne4etnyh 4isel»);

printf («n Vichislit' zanovo? n (esli da t=1,esli net t=0)nt=»);

scanf («%d» ,&t);

if (t>0)

{printf (««);goto m1;}

if (t<1)

puts («tt ===========================================»);

puts («****************************************»);

puts («==Vipolnil Nechayev Nikita Igorevi4==»);

puts («=======Student gryppi BIS-12−2=======»);

puts («****************************************»);

puts («***************************************»);

puts («==Proveril k.t.n. docent==»);

puts («==_______________Ni A.G.==»);

puts («==»" __" «____________2013==»);

puts («***************************************»);

printf («Dl9 zaverweni9 nagmite klaviwu «);

getch (); /* Zadergka do nagati9 luboi klaviwi */

return 0;

2.3.2 Результат выполнения программы:

2.

3. Задание Б

Составить блок схему и программу обработки матрицы. Элементы матрицы заполнить, используя функцию генератора случайных чисел. Программу написать двумя способами: 1) осуществляя доступ к элементам массива с помощью индексов; 2) осуществляя доступ к элементам массива с помощью указателей.

3.1 Содержательная постановка задачи

Дана целочисленная квадратная матрица. Определить:

1) Сумму элементов в тех строках, которые не содержат отрицательных элементов.

2) Минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

3.2 Проектная часть

3.2.1 Словесное описание алгоритма

1. Начало алгоритма.

2. Задать размерность матрицы.

3. Заполнить массив a[n][m] случайными числами.

4. Вывести элементы массива a[n][m].

5. Организовать цикл с заданными параметрами от i=1; m; 1.

Внутри цикла по i:

5.1. Обнулить сумму sum=0.

5.2. Организовать цикл с заданными параметрами от j=1; n; 1.

Внутри цикла по j:

5.2.1. Проверить: если a[i][j]>=0, то суммировать элементы строки, иначе перейти к следующему шагу цикла.

5.3. По окончании цикла проверить: если j=n, то вывести сумму элементов в тех строках, которые не содержат отрицательных элементов.

5.4. Перейти к следующему шагу цикла по i.

6. Минимум сумм диагоналей находим: min=a[0][n-1].

7. Организовать цикл с заданными параметрами от i=1; m; 1.

Внутри цикла по i:

7.1. Сумма элементов диагоналей, параллельных главной диагонали матрицы с левой стороны равно сумме элементов диагоналей, параллельных главной диагонали матрицы с правой стороны и равно 0, т. е. t1=t2=0.

7.2. Организовать цикл с заданными параметрами от j=0; n; 1.

Внутри цикла по j:

7.2.1. Суммировать элементы диагоналей, параллельных главной диагонали матрицы с левой стороны.

7.2.2. Суммировать элементы диагоналей, параллельных главной диагонали матрицы с правой стороны.

7.3. По окончании цикла по j проверить: если t1

7.3.1. Перейти к следующему шагу цикла по i.

8. Вывести минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.

9. Конец алгоритма.

3.2.2

3.2.2 Блок — схема:

3.2.3

3.2.3 Описание и схема пользовательского интерфейса

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

Она будут состоять из названия данной работы.

Ras4etno-grafi4eska9 rabota #2 zadanie B

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

Sgenerirovanna9 matrica

Rezul’tat pervoy 4asti zadani9

Summa elementov stroki

Rezul’tat vtoroy 4asti zadani9

Minimum Summ

Vichislit' zanovo?

(esli da t=1,esli net t=0)

3. В случае выбора значение 1, программа продолжит работу и перейдёт к пункту 2. Если вы выберете значение 0, программа завершит работу и перейдёт к пункту 4.

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

========================================

****************************************

==Vipolnil Nechayev Nikita Igorevi4==

=======Student gryppi BIS-12−2=======

****************************************

***************************************

==Proveril k.t.n. docent==

==_______________Ni A.G.==

=="" __" «____________2013==

***************************************

5. На следующей строчке будет надпись

Dl9 zaverweni9 nagmite klaviwu

3.3 Прикладная часть

3.3.1 Программное описание алгоритма с индексами

#include

#include

#include

#include

#include

#define m 8

#define n 8

int main ()

{

int i, j, t1,t2,sum, min, t;

int a[m][n];

puts («tt Ras4etno-grafi4eska9 rabota #2 zadanie B»);

puts («tt ===========================================»);

m1:for (i=0; i

for (j=0; j

a[i][j]=rand ()%10−1;

printf («n Sgenerirovanna9 matrican»);

for (i=0; i

{

for (j=0; j

printf («%4d», a[i][j]);

printf («n»);

}

printf («n ttt Rezul’tat pervoy 4asti zadani9»);

printf («nn»);

for (i=0; i

{

sum=0;

for (j=0; j

{

if (a[i][j]>=0)

sum+=a[i][j];

else

break;

}

if (j==n)

printf («Summa elementov stroki #%d=%dn», i+1,sum);

}

printf («n ttt Rezul’tat vtoroy 4asti zadani9»);

min=a[0][n-1];

for (i=1; i

{

t1=t2=0;

for (j=0; j

{

t1+=a[i+j][j];

t2+=a[j][i+j];

}

if (t1

min=t1;

if (t2

min=t2;

}

printf («n Minimum Summ= %d», min);

printf («n Vichislit' zanovo? n (esli da t=1,esli net t=0)nt=»);

scanf («%d» ,&t);

if (t>0)

{printf (««);goto m1;}

if (t<1)

puts («tt ===========================================»);

puts («****************************************»);

puts («==Vipolnil Nechayev Nikita Igorevi4==»);

puts («=======Student gryppi BIS-12−2=======»);

puts («****************************************»);

puts («***************************************»);

puts («==Proveril k.t.n. docent==»);

puts («==_______________Ni A.G.==»);

puts («==»" __" «____________2013==»);

puts («***************************************»);

printf («Dl9 zaverweni9 nagmite klaviwu «);

getch (); /* Zadergka do nagati9 luboi klaviwi */

return 0;

}

С указателями

#include

#include

#include

#include

#include

#define m 8

#define n 8

int main ()

{

int i, j, t1,t2,sum, min, t;

int a[m][n];

int *mat;

puts («tt Ras4etno-grafi4eska9 rabota #2 zadanie B»);

puts («tt ===========================================»);

mat=&a[0][0];

m1:for (i=0; i

for (j=0; j

{

*mat=rand ()%10−1;

mat++;

}

mat-=n*m;

printf («n Sgenerirovanna9 matrican»);

for (i=0; i

{

for (j=0; j

{

printf («%4d» ,*mat);

mat++;

}

printf («n»);

}

printf («n ttt Rezul’tat pervoy 4asti zadani9»);

printf («nn»);

mat=&a[0][0];

for (i=0; i

{

sum=0;

for (j=0; j

{

if (*mat>=0)

sum+=*mat;

else

break;

}

if (j==n)

printf («Summa elementov stroki #%d=%dn», i+1,sum);

}

printf («n ttt Rezul’tat vtoroy 4asti zadani9»);

min=a[0][n-1];

for (i=1; i

{

t1=t2=0;

for (j=0; j

{

t1+=*(mat+i*m+j);

t2+=*(mat+j*m+i);

}

if (t1

min=t1;

if (t2

min=t2;

}

printf («n Minimum Summ= %d», min);

printf («n Vichislit' zanovo? n (esli da t=1,esli net t=0)nt=»);

scanf («%d» ,&t);

if (t>0)

{printf (««);goto m1;}

if (t<1)

puts («tt ===========================================»);

puts («****************************************»);

puts («==Vipolnil Nechayev Nikita Igorevi4==»);

puts («=======Student gryppi BIS-12−2=======»);

puts («****************************************»);

puts («***************************************»);

puts («==Proveril k.t.n. docent==»);

puts («==_______________Ni A.G.==»);

puts («==»" __" «____________2013==»);

puts («***************************************»);

printf («Dl9 zaverweni9 nagmite klaviwu «);

getch (); /* Zadergka do nagati9 luboi klaviwi */

return 0;

}

3.3.2

3.3.2 Результат выполнения программы

Заключение

массив матрица алгоритм индекс В данной расчетно-графической работе были представлены примеры алгоритмов обработки сложных структур данных на языке Си (одномерные и двумерные массивы). Также были представлены блок-схемы, словесное и графическое описание. Как мы видим, для языка Си характерны лаконичность, стандартный набор конструкций управления потоком выполнения и обширный набор операций. Это и делает его столь востребованным языком в наши дни.

Приложение А

Использованные библиотеки

— iostream — заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++ (в данном случае мы подключаем также и цвет system («color 1a»); через эту библиотеку).

— (от англ. console input-output — консольный ввод-вывод) — заголовочный файл, используемый для создания текстового интерфейса пользователя (использующая при вводе-выводе и представлении информации исключительно набор буквенно-цифровых символов).

— заголовочный файл стандартной библиотеки языка программирования С, разработанный для выполнения простых математических операций.

— заголовочный файл стандартной библиотеки языка Си, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и известен в нём как cstdlib. Название «stdlib» расшифровывается как «standard library» (стандартная библиотека). В данном случае подключает rand.

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

Приложение Б

Использованные программы

AFCE — составление блок-схем.

Microsoft Visual Studio, Dev C++ - среды разработки данных программ.

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

1. Стефан Р. Дэвис «C++».

2. С. В. Симонович «Информатика: Базовый курс». — СПб.: Питер, 2003.

3. Оверленд Б. «C++».

4. http://ru.wikipedia.org/wiki/Си_(язык_программирования)

5. http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/

6. Керниган Б., Ритчи Д. Язык программирования Си. — 2-е изд. — М.: Вильямс, 2007. — С. 304.