Примеры программ

Пример . Написать программу выполняющую раскраску графа

#include<stdio.h>

#include<stdlib.h>

void input(int **graf,int n)

{ int i,j;

while(1)

{ printf("\nvvodite pary smegnyh vershin :");

scanf("%d%d",&i,&j);

if(!i || !j) break;

if(i>n || j>n)

{

puts("error");

continue;

}

*(*(graf+i-1)+j-1)=1;

*(*(graf+j-1)+i-1)=1;

}

}

void print(int **graf,int *color,int n)

{ int i,j;

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

printf("\nverhina : %d cvet : %d",i+1,*(color+i));

printf("\n");

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

{

for(j=0; j<n; j++)

printf("%2d",*(*(graf+i)+j));

printf("\n");

}

}

void raskr(int **graf,int *color,int n)

{ int i,ii,j,k,p;

int *vr,*cv;

vr=(int*) calloc(n,sizeof(int));

cv=(int*) calloc(n,sizeof(int));

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

{ k=0;

for(j=0; j<n; j++)

if(*(*(graf+i)+j)) k++;

*(vr+i)=k;

}

for(p=0; p<n; p++)

{

ii=0;

while(ii<n && *(color+ii)!=0) ii++;

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

if(*(color+i)==0 && *(vr+i) > *(vr+ii))

ii=i;

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

*(cv+i)=0;

for(j=0; j<n; j++)

if(*(*(graf+ii)+j)==1 && *(color+j)!=0)

*(cv+*(color+j)-1)=1;

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

if(*(cv+i)==0)

{ *(color+ii)=i+1;

break;

}

}

free(cv);

free(vr);

}

int main()

{ int **graf,*color; // матрица смежности графа и массив цветов

int n; // размерность графа

scanf("%d",&n); // ввод размерности графа

color=(int*) calloc(n,sizeof(int)); // выделение памяти

graf=(int**) calloc(n,sizeof(int*));

for(int i=0; i<n; i++)

*(graf+i)=(int*)calloc(n,sizeof(int));

input(graf,n); // ввод исходного графа

raskr(graf,color,n); // раскраска вершин графа

print(graf,color,n); // вывод результата окраски графа

free(color);

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

free(*(graf+i));

free(graf);

return 0;

}

Литература

1. Керниган Б., Ритчи Д. Язык программирования С. –М.: Финансы и статистика, 1992

2. Керниган Б., Ритчи Д. Язык программирования С. Спб.: Невский диалект, 2004.

4. Романовская Л.М., Русс Т.В., Свитковский С.Г. Программирование в среде С(С++) для ПЭВМ. М.: Финансы и статистика, 1992.

5. Герберт Шилд. Программирование на Borland C++. –Мн.: ООО "Попурри" 1998г. – 800с.

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

7. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский Диалект, 2001.

8. Демидович, Е.М. Основы алгоритмизации и программирования. Язык Си. – БХВ-Петербург, 2006 г.

9. Б. С. Хусаинов. Структуры и алгоритмы обработки данных. Примеры на языке Си – М.: Финансы и статистика, 2004 г.

10. С. Кочан Программирование на языке С. – М: Издательский дом «Вильямс», 2007 г.

Содержание

Введение 3

Блок-схема алгоритма 3

Общие требования к блок-схеме алгоритма 3

Линейные и разветвляющиеся процессы 5

Циклические процессы 8

Итерационные процессы 12

Основные понятия языка С(С++) 14

Комментарии 16

Типы данных 16

Данные целого типа 17

Данные вещественного типа 18

Модификатор const 18

Переменные перечисляемого типа 19

Константы 20

Структура программы на языке С(С++) 22

Описание переменных 23

Локальные переменные 23

Операции и выражения 28

Операция присваивания 30

Арифметические операции 30

Операции поразрядной арифметики 32

Логические операции 33

Операции отношения 34

Инкрементные и декрементные операции 34

Операция sizeof 35

Порядок выполнения операций 35

Приоритет операций 36

Преобразование типов 36

Операция приведения 37

Операция запятая 38

Ввод и вывод информации 38

Директивы препроцессора 43

Директива #include 43

Директива #define 43

Операторы языка С(С++) 45

Понятие пустого и составного операторов 45

Условные операторы 45

Операторы организации цикла 49

Оператор цикла for 49

Оператор цикла while 51

Оператор цикла do … while 51

Вложенные циклы 52

Операторы перехода (break, continue, return, goto) 52

Примеры программ 54

Массивы 57

Одномерные массивы 57

Примеры программ 58

Многомерные массивы (матрицы) 63

Примеры программ 64

Указатели 69

Понятие указателя 69

Описание указателей 70

Операции с указателями 71

Связь между указателями и массивами 71

Массивы указателей 72

Многоуровневые указатели 72

Примеры программ 74

Символьные строки 84

Ввод/вывод строк. 85

Функции работы со строками. 87

Примеры программ 87

Функции 94

Прототип функции. 94

Определение функции. 95

Параметры функции 96

Параметры по умолчанию 98

Передача массива в функцию 99

inline функции 100

Класс памяти 100

Автоматические переменные 100

Статические переменные 100

Регистровые переменные 101

Блочная структура 101

Примеры программ 102

Указатели на функции 110

Примеры программ 111

Рекурсия 113

Примеры программ 113

Аргументы в командной строке 118

Функции с переменным числом параметров 119

Примеры программ 122

Сортировка 125

Пузырьковая сортировка. 125

Шейкер сортировка 125

Сортировка вставкой 126

Сортировка выбором 127

Метод Шелла 127

Метод Хора 128

Структуры 130

Доступ к элементам структуры 132

Инициализация структур 133

Указатели на структуры. 134

Структуры и функции 136

Примеры программ 137

Поля бит 140

Объединения 141

Переменные с изменяемой структурой 142

Примеры программ 144

Организация списков и их обработка 145

Операции со списками при связном хранении 146

Стек 148

Построение обратной польской записи 151

Односвязный линейный список, очередь 154

Двусвязный линейный список 158

Циклический список, кольцо 162

Двусвязный циклический список 162

Примеры программ 166

Деревья 167

Потоки и файлы 175

Файлы 175

Основные сведения о файловой системе 175

Действие 176

Организация посимвольного ввода и вывода 178

Определение конца файла feof() 178

Организация ввода и вывода строк 179

Удаление файлов 179

Дозапись потока 180

Позиционирование в файле 180

Текстовые и двоичные файлы 180

Функции fread() и fwrite() 181

Примеры программ 182

Хеширование 196

Схемы хеширования 198

Метод открытой адресации с линейным опробыванием 198

Метод цепочек 198

Графы 200

Машинное представление графов 201

Примеры программ 203

Литература 205

Св. план , поз.

Учебное издание

Луцик Юрий Александрович

МЕТОДИЧЕСКОЕ ПОСОБИЕ

по курсу

ОСНОВЫ АЛГОРИТМИЗАЦИИ И

ПРОГРАММИРОВАНИЯ

для студентов специальности

” Вычислительные машины системы и сети”

Редактор

Корректор

____________________________________________________________________

Подписано в печать . . . Формат 60х84 1/16.

Бумага Печать офсетная Усл. печ. л.

Уч.-изд. л. Тираж экз. Заказ

____________________________________________________________________

Белорусский государственный университет информатики и радиоэлектроники

Отпечатано в БГУИР. Лицензия ЛП № 156.22027, Минск, П Бровки, 6