Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РЕСПУБЛИКИ КАЗАХСТАН
НАО «АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ»
Факультет «информационные технологии» Кафедра «информационные системы»
ОТЧЁТ
по расчётно – графической работе № 2
по дисциплине «Алгоритмы, структуры данных и
программирование».
Тема: «Графическая и программная реализация алгоритмов обработки сложных структур данных».
Вариант № 19
Выполнил ст. гр. БИС-12-2
Нечаев Н.И.
Проверил к.т.н., доцент
_______________ Ни А.Г.
“_____” ___________2013
Алматы 2013
Содержание
Введение………...……………………………………………………..………......3
Заключение………………………………………………………….………...….24
Список использованной литературы………..……………………..………..…26
Приложение А………………....………………….………………………….......25
Приложение Б……………………………………………………………...….…25
ВВЕДЕНИЕ
Си — стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи. Си был создан для использования в операционной системе UNIX. С тех пор он был перенесён на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность. Он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков.
Язык программирования СИ – это универсальный язык с богатым набором операторов и компактным способом записи выражений. Язык C обеспечивает разнообразие типов данных. Базовыми типами являются целые, вещественные числа и символы (литеры). Язык разрешает модификацию базовых типов данных, а также создание пользовательских типов. В языке используются стандартные типы данных int, char, float, double; применяются массивы, структуры (записи), файлы; имеется возможность конструирования очередей, списков.
В данном отчете будет представлено решение двух типов задач: одномерного массива и матрицы соответственно. Будет представлено подробное описание решения в форме словесного описания, блок-схемы, кода программы, которую реализовали на языке Си. Также будет осуществлена проверка с помощью MS Excel.
Цель. Закрепить навыки разработки и программирования на языке Си алгоритмов обработки сложных структур данных: одномерных массивов и матриц. Приобрести навыки программирования с переменными типа указатель.
Методические рекомендации. При выполнении задания изучить теоретический материал по теме расчетно-графической работы, разработать алгоритм решения задачи, построить блок-схему и оформить отчет в соответствии с требованиями, указанными в настоящих методических указаниях.
Алгоритм - набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задач за конечное число действий.
Существует 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, чтобы найти, на каком расстоянии друг от друга находятся элементы массива.
Блок-схема – распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями, указывающими направление последовательности.
|
Наименование |
Обозначение |
Функция |
|
Блок начало-конец |
Элемент отображает вход из внешней среды или выход из неё (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие. |
|
|
Блок действия |
Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции. |
|
|
Логический блок (блок условия) |
Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. |
|
|
Предопределённый процесс |
Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы. |
|
|
Данные |
Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). |
|
|
Граница цикла |
Символ состоит из двух частей − соответственно, начало и конец цикла − операции, выполняемые внутри цикла, размещаются между ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости от типа организации цикла. |
|
|
Соединитель |
Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения её в другом месте. |
Составить блок схему и программу обработки одномерного массива. Элементы массива заполнить, используя функцию генератора случайных чисел. Программу написать двумя способами: 1) осуществляя доступ к элементам массива с помощью индексов; 2) осуществляя доступ к элементам массива с помощью указателей.
Дан массив A[N]. Осуществить циклический сдвиг элементов массива вправо на k позиций, где k – целая часть среднего арифметического значения нечётных элементов массива A[N].
значение.
Внутри цикла:
Проверить: если а[i]%2=0, то суммируем нечётные элементы массива,
т.е. S=S+а[i], и число нечётных элементов увеличить на 1, т.е. r=r+1, иначе перейти к следующему шагу цикла.
Внутри цикла:
Внутри цикла: последующему элементу присвоить предыдущий, т.е.
a[j]=a[j-1].
программы.
Она будет состоять из названия данной работы.
Ras4etno-grafi4eska9 rabota #2 zadanie A
=================================
должен выходиться сгенерированный массив, и должны выходить элементы массива уже с циклическим сдвигом и должно выходит предложение о завершении программы или предложение вычислить заново.
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)
переходить к пункту 2. Если вы выбираете значение 0, программа завершит работу и перейдёт к пункту 4.
наименование студента, выполнившего данную работу, и его группы. Чуть ниже, с правой стороны, программа выведет наименование преподавателя проверившего работу.
=================================
****************************************
==Vipolnil Nechayev Nikita Igorevi4==
=======Student gryppi BIS-12-2=======
****************************************
***************************************
==Proveril k.t.n. docent==
==_______________Ni A.G.==
==""__""____________2013==
***************************************
Dl9 zaverweni9 nagmite klaviwu <Enter>
|
Ras4etno-grafi4eska9 rabota #2 zadanie A ================================= 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) ================================= **************************************** ==Vipolnil Nechayev Nikita Igorevi4== =======Student gryppi BIS-12-2======= **************************************** *************************************** ==Proveril k.t.n. docent== ==_______________Ni A.G.== ==""__""____________2013== *************************************** Dl9 zaverweni9 nagmite klaviwu <Enter> |
#include <iostream>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int k,N,S,r,i,t,f,j;
int a[N];
float b;
puts("\t\t Ras4etno-grafi4eska9 rabota #2 zadanie A");
puts("\t\t ===========================================");
printf("Razmernost' massiva A[N]");
m1:printf("\n Vvedite N\nN=");
scanf("%d",&N);
S=0;
r=0;
for(i=0;i<N;i++)
{
a[i]=rand()%10-5;
}
printf("\n Sgenerirovanniy massiv\n");
for(i=0;i<N;i++)
printf("%4d",a[i]);
for(i=0;i<N;i++)
{
b=a[i]%2;
if(b!=0)
{
r=r+1;
S=S+a[i];
}
}
k=abs(S/r);
for(i=0;i<k;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<N;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("\t\t ===========================================");
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 <Enter> ");
getch( ); /* Zadergka do nagati9 luboi klaviwi */
return 0;
}
С указателями:
#include <iostream>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int k,N,S,r,i,t,f,j,*pa,*pb,*p;
int a[N];
float b;
puts("\t\t Ras4etno-grafi4eska9 rabota #2 zadanie A");
puts("\t\t ===========================================");
printf("Razmernost' massiva A[N]");
m1:printf("\n Vvedite N\nN=");
scanf("%d",&N);
S=0;
r=0;
pa=&a[0];
for(i=0;i<N;i++)
{
*pa=rand()%10-5;
}
pa=&a[0];
printf("\n Sgenerirovanniy massiv\n");
for(i=0;i<N;i++)
printf("%4d",*pa++);
pa=&a[0];
for(i=0;i<N;i++)
{
b=*pa%2;
++pa;
if(b!=0)
{
r=r+1;
S=S+*pa;
}
}
k=abs(S/r);
for(i=0;i<k;i++)
{
pb=&a[9];
p=&a[0];
f=*pb;
for(j=0;j<N;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<N;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("\t\t ===========================================");
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 <Enter> ");
getch( ); /* Zadergka do nagati9 luboi klaviwi */
return 0;
Составить блок схему и программу обработки матрицы. Элементы матрицы заполнить, используя функцию генератора случайных чисел. Программу написать двумя способами: 1) осуществляя доступ к элементам массива с помощью индексов; 2) осуществляя доступ к элементам массива с помощью указателей.
Дана целочисленная квадратная матрица. Определить:
отрицательных элементов.
диагонали матрицы.
Внутри цикла по i:
Внутри цикла по j:
Внутри цикла по i:
Внутри цикла по j:
Она будут состоять из названия данной работы.
Ras4etno-grafi4eska9 rabota #2 zadanie B
элементов разных строк матрицы, которые не содержат отрицательных элементов, будет выходить минимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы, и будет выходить предложение о завершении программы или предложение вычислить заново.
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)
перейдёт к пункту 2. Если вы выберете значение 0, программа завершит работу и перейдёт к пункту 4.
наименование группы и студента, выполнившего данную работу. С правой стороны программа выведет наименование преподавателя, проверившего работу.
========================================
****************************************
==Vipolnil Nechayev Nikita Igorevi4==
=======Student gryppi BIS-12-2=======
****************************************
***************************************
==Proveril k.t.n. docent==
==_______________Ni A.G.==
==""__""____________2013==
***************************************
Dl9 zaverweni9 nagmite klaviwu <Enter>
|
Ras4etno-grafi4eska9 rabota #2 zadanie B ================================= 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) ======================================== **************************************** ==Vipolnil Nechayev Nikita Igorevi4== =======Student gryppi BIS-12-2======= **************************************** *************************************** ==Proveril k.t.n. docent== ==_______________Ni A.G.== ==""__""____________2013== *************************************** Dl9 zaverweni9 nagmite klaviwu <Enter> |
#include <iostream>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define m 8
#define n 8
int main()
{
int i,j,t1,t2,sum,min,t;
int a[m][n];
puts("\t\t Ras4etno-grafi4eska9 rabota #2 zadanie B");
puts("\t\t ===========================================");
m1:for(i=0; i<m; i++)
for(j=0; j<n; j++)
a[i][j]=rand()%10-1;
printf("\n Sgenerirovanna9 matrica\n");
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
printf("%4d",a[i][j]);
printf("\n");
}
printf("\n \t\t\t Rezul'tat pervoy 4asti zadani9");
printf("\n\n");
for(i=0; i<m; i++)
{
sum=0;
for(j=0; j<n; j++)
{
if(a[i][j]>=0)
sum+=a[i][j];
else
break;
}
if(j==n)
printf("Summa elementov stroki #%d=%d\n",i+1,sum);
}
printf("\n \t\t\t Rezul'tat vtoroy 4asti zadani9");
min=a[0][n-1];
for(i=1; i<m; i++)
{
t1=t2=0;
for(j=0; j<n-i; j++)
{
t1+=a[i+j][j];
t2+=a[j][i+j];
}
if(t1<min)
min=t1;
if(t2<min)
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("\t\t ===========================================");
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 <Enter> ");
getch( ); /* Zadergka do nagati9 luboi klaviwi */
return 0;
}
С указателями
#include <iostream>
#include <math.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define m 8
#define n 8
int main()
{
int i,j,t1,t2,sum,min,t;
int a[m][n];
int *mat;
puts("\t\t Ras4etno-grafi4eska9 rabota #2 zadanie B");
puts("\t\t ===========================================");
mat=&a[0][0];
m1:for(i=0; i<m; i++)
for(j=0; j<n; j++)
{
*mat=rand()%10-1;
mat++;
}
mat-=n*m;
printf("\n Sgenerirovanna9 matrica\n");
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
printf("%4d",*mat);
mat++;
}
printf("\n");
}
printf("\n \t\t\t Rezul'tat pervoy 4asti zadani9");
printf("\n\n");
mat=&a[0][0];
for(i=0; i<m; i++)
{
sum=0;
for(j=0; j<n; j++)
{
if(*mat>=0)
sum+=*mat;
else
break;
}
if(j==n)
printf("Summa elementov stroki #%d=%d\n",i+1,sum);
}
printf("\n \t\t\t Rezul'tat vtoroy 4asti zadani9");
min=a[0][n-1];
for(i=1; i<m; i++)
{
t1=t2=0;
for(j=0; j<n-i; j++)
{
t1+=*(mat+i*m+j);
t2+=*(mat+j*m+i);
}
if(t1<min)
min=t1;
if(t2<min)
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("\t\t ===========================================");
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 <Enter> ");
getch( ); /* Zadergka do nagati9 luboi klaviwi */
return 0;
}
ЗАКЛЮЧЕНИЕ
В данной расчетно-графической работе были представлены примеры алгоритмов обработки сложных структур данных на языке Си (одномерные и двумерные массивы). Также были представлены блок-схемы, словесное и графическое описание. Как мы видим, для языка Си характерны лаконичность, стандартный набор конструкций управления потоком выполнения и обширный набор операций. Это и делает его столь востребованным языком в наши дни.
Приложение А
Использованные библиотеки
<iostream> — iostream — заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C++ (в данном случае мы подключаем также и цвет system(“color 1a”); через эту библиотеку).
<conio.h> — (от англ. console input-output — консольный ввод-вывод) — заголовочный файл, используемый для создания текстового интерфейса пользователя (использующая при вводе-выводе и представлении информации исключительно набор буквенно-цифровых символов).
<math.h> — заголовочный файл стандартной библиотеки языка программирования С, разработанный для выполнения простых математических операций.
<stdlib.h> — заголовочный файл стандартной библиотеки языка Си, который содержит в себе функции, занимающиеся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и известен в нём как cstdlib. Название «stdlib» расшифровывается как «standard library» (стандартная библиотека). В данном случае подключает rand.
<time.h> — заголовочный файл стандартной библиотеки языка программирования СИ, содержащий типы и функции для работы с датой и временем. В данном случае этот оператор служит для того, чтобы массив каждый раз генерировался по-разному.
Приложение Б
Использованные программы
AFCE – составление блок-схем.
Microsoft Visual Studio, Dev C++ – среды разработки данных программ.
Список использованной литературы
Стефан Р. Дэвис «C++».
С.В. Симонович «Информатика: Базовый курс». – СПб.: Питер, 2003.
Оверленд Б. «C++».
http://ru.wikipedia.org/wiki/Си_(язык_программирования)
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/
Керниган Б., Ритчи Д. Язык программирования Си. — 2-е изд. — М.: Вильямс, 2007. — С. 304.