Блок-схемы алгоритмов и алгоритмы по шагам

СОДЕРЖАНИЕ

Введение

Условие задачи

3. Входные и выходные данные

4. Блок схемы алгоритмов и алгоритмы по шагам

5. Код программы

6. Результаты работы программы

Заключение

Литература

 

Введение

Язык программирования Си отличается максимализмом функций. Авторы языка хотели, чтобы программы на нём легко компилировались с помощью однопроходного компилятора. Однопроходный компилятор компилирует программу, не возвращаясь назад, к уже откомпилированному тексту. Поэтому использованию функции должно предшествовать её объявление. Код на Си можно легко писать на низком уровне абстракции. Си часто называют языком среднего уровня или даже низкого уровня, учитывая то, как близко он работает к реальным устройствам.

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

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

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

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

--систему типов, предохраняющую от бессмысленных операций;

--использование препроцессора для, например, определения макросов и включения файлов с исходным кодом;

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

--минимальное число ключевых слов;

--передачу параметров в функцию по значению, а не по ссылке (при этом передача по ссылке выполняется с помощью указателей);

--указатели на функции и статические переменные

--области действия имён;

--записи — определяемые пользователем собирательные типы данных (структуры), которыми можно манипулировать как одним целым;

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

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

Условие задачи

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

Структура входных/выходных данных

Входные данные:

Бинарные файлы hostel.dat и line.dat

Кольцо этажей общежития structRING с полями

 

Rrr - подструктура R

RING *l, *r - указатели на левый и правый элементы кольца

 

 

Подструктура элемента кольца structR с полями

 

int room - кол-во комнат

int bed - кол-во кроватей

int f_bed - кол-во свободных кроватей

char pl[15][30] - массив для ФИО студентов

int number - номер этажа

 

Очередь студентов на подселениеstructLINE с полями

 

Lll - подструктура L

LINE *next - указатель на следующий элемент очереди LINE

 

 

Подструктура элемента очереди structLINE с полями

 

charfio[30] - фио студента

 

 

Выходные данные:

Изменённые бинарные файлы hostel.dat и line.dat

Блок-схемы алгоритмов и алгоритмы по шагам

 

Блок-схема функции занесения информации из файла в кольцо from_file_ring: (передаётся указатель на элемент кольца s)

 

 

 

Алгоритм по шагам функции удаления студента из очереди del_stud: (передаётся указатели на голову очередиh и хвост t)

 

1. Объявление переменных:

 

LINE **h – указатель на голову очереди;

LINE **t – указатель на хвост очереди;

LINE *f – текущий указатель;

LINE *pr – предыдущий указатель;

char *st – введённое ФИО студента.

 

1. Если в очереди только один элемент (hравно t), то пункт 3, иначе 6.
2. Освободить память от h.
3. Указатели на хвост tи головуh равны нулю.
4. Выход из функции.
5. Предыдущий prи текущий fэлементы равны головеh.
6. Начало цикла по очереди pr.
7. Если найден элемент со строкой st то пункт 9, иначе 18.
8. Если pr равен головеh то пункт 10, иначе 14.
9. Голова hравна следующему элементу pr->next.
10. Удаляем элемент pr из очереди.
11. Предыдущий prи текущий f равны головеh.
12. Выход из функции.
13. Обходим элемент pr (f->next=pr->next).
14. Удаляем элемент pr из очереди.
15. Выбор следующего элемента очереди pr=f->next.
16. Выход из функции.
17. Переход к следующему элементpr=pr->next.
18. Конец цикла по очередиpr.
19. Конец функции.

Блок-схема функции занесения информации из файла в очередь from_file_line:(передаётся указатели на голову очередиh и хвост t)

 

 

 

 

Алгоритм по шагам функции добавления студента в очередь на заселение add_stud:(передаётся указатели на голову очередиh и хвост t)

 

1. Объявление переменных:

 

LINE *cur – структурная переменная указатель на очередь

 

1. Выделение памяти дляcur.
2. Ввод ФИО студента в поле fioэлемента очереди cur.
3. Если создаётся первый элемент очереди (hраен нулю), то пункт 5, иначе 6.
4. cur равен головеочередиh и хвоcту t.
5. Выбор следующего элемента очереди cur (t->next=cur).
6. сur равен хвосту t.
7. Конец функции.

Код программы

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

#include<locale.h>

#include<io.h>

 

struct R

{

int room; // кол-во комнат

int bed; // кол-во кроватей

int f_bed; // кол-во свободных кроватей

char pl[15][30]; // массив для ФИО студентов

int number; // номерэтажа

};

 

struct RING

{

R rr;

 

RING *l, *r;

};

 

struct L

{

char fio[30]; // ФИОстудента

};

 

struct LINE

{

L ll;

 

LINE *next;

};

 

RING* from_file_ring(RING *); //записьинформацииизфайлавоперативнуюпамять

LINE* from_file_line(LINE **, LINE **); //запись информации из файла в оперативную память

void add_stud(LINE **, LINE **); //добавление студента в очередь на подселение

void del_stud(LINE **, LINE **, char *); //удаление студента с очереди на подселение

int kill(RING *); //выселить студента с общежития

void out(RING *); //вывод всех этажей

void out_floor(RING *); //вывод указанного этажа

void to_file(RING *, LINE *); //запись информации из оперативной памяти в файл

void free_mem(RING **); //освобождение памяти

RING* add_floor(RING *); //добавление этажа

RING* del_floor(RING *); //удалениеэтажа

int into(RING *, int); //заселениестудента

 

void main()

{

RING *s = NULL, *cur;

LINE *h = NULL, *t = NULL;

LINE *temp = NULL;

int k = 1; //флаг окончания ввода студентов

int kk = 0; //флаг поиска этажа (равен 0, если нет этажа)

int buf; //буффер для ввода этажа

char in[30]; //буфер для ввода ФИО студента

int i; //счётчик мест на этаже

int ex; //флаг для выхода из циклов

 

setlocale(LC_ALL,".ACP");

 

s=from_file_ring(s); //запись информации из файла в оперативную память

h=from_file_line(&h,&t); //запись информации из файла в оперативную память

 

while(1)

{

puts("\nНажмите:");

puts("'1' - просмотреть очередь студентов на подселение");

puts("'2' - добавить студента в очередь на подселение");

puts("'3' - убрать студента из очереди на подселение");

puts("'4' - выселить студента с общежития");

puts("'5' - просмотреть информацию о всех этажах");

puts("'6' - просмотреть информацию о выбранном этаже");

puts("'x' - добавить этаж");

puts("'y' - заселить студента");

puts("'z' - удалить этаж");

puts("'q' - выход");

fflush(stdin);

 

switch(getch())

{

case'1':

 

puts("\n\n*************** Просмотр очереди студентов на подселение *****************\n");

 

if(!h)

{

puts("\nНет очереди");

getch();

break;

}

 

i=1;

temp=h;

printf(" ______________________________________________________________________________ ");

printf("| | |");

printf("| МЕСТО | ФИОСТУДЕНТОВ |");

printf("|_______|______________________________________________________________________|");

do

{

 

printf("| | |");

printf("| %3d | %20s |",i,temp->ll.fio);

printf("|_______|______________________________________________________________________|");

temp=temp->next;

i++;

}

while(temp);

 

break;

 

case'2':

 

puts("\n\n************ Добавление студента в очередь на подселение ************");

add_stud(&h,&t);

 

cur=s;

ex = 0; //для выхода из цикла просмотра стоянок

do //просмотркольцаэтажей

{

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

if(!cur->rr.pl[i][0]) //если есть свободные места

{

strcpy(cur->rr.pl[i],h->ll.fio);

temp=h;

h=h->next;

free(temp);

 

cur->rr.f_bed = cur->rr.f_bed - 1; //свободныеместа

ex = 1;

break;

}

 

cur=cur->l;

 

if(ex == 1)

break;

}

while(cur!= s);

 

break;

 

case'3':

 

puts("\n\n*********** Удаление студента с очереди на подселение *************");

if(h)

{

fflush(stdin);

printf("\nВведите ФИО студента --> ");

gets(in);

del_stud(&h,&t,in);

}

else

{

puts("\nНеточереди");

getch();

}

break;

 

case'4':

 

puts("\n\n*********** Выселение студента с общежития ************");

printf("\nВведите номер этажа --> ");

scanf("%d",&buf);

 

cur=s;

kk=0; //этаж не найден

k=0;

 

do //просмотр кольца этажей

{

if(cur->rr.number == buf)

{

kk=1; //этажнайден

break;

}

 

cur=cur->l;

}

while(cur!= s);

 

printf("\n");

 

if(kk == 1) //если этаж найден

{

i=kill(cur); //возращаем номер места

 

if(h->ll.fio) //если есть очередь

{

strcpy(cur->rr.pl[i],h->ll.fio); //то заселяем первого студента из очереди

temp=h;

h=h->next;

free(temp);

 

cur->rr.f_bed = cur->rr.f_bed - 1; //свободныеместа

}

}

else

{

puts("\nТакого этажа нет");

getch();

break;

}

 

break;

 

case'5':

 

if(!s)

{

puts("\nНетэтажей!");

getch();

break;

}

 

puts("\n\n *********** Просмотр информации о общежитии *************");

out(s);

printf("\n для продолжения нажмите любую кнопку...");

getch();

break;

 

case'6':

 

if(!s)

{

puts("\nНетэтажей!");

getch();

break;

}

 

puts("\n\n********** Просмотр информации о выбранном этаже ************");

printf("Введите номер этажа --> ");

scanf("%d",&buf);

 

cur=s;

kk=0; //этаж не найден

 

do //просмотр кольца этажей

{

if(cur->rr.number == buf)

{

kk=1; //этаж найден

break;

}

 

cur=cur->l;

}

while(cur!= s);

 

if(kk == 1) //еслиэтажнайден

out_floor(cur);

else

{

puts("\nТакогоэтажанет");

getch();

break;

}

 

printf("\n для продолжения нажмите любую кнопку...");

getch();

break;

 

 

case'x':

 

puts("\n\n*************** Добавлениеэтажа ***************");

s=add_floor(s);

break;

 

case'y':

 

puts("\n\n*********** Заселить студента в общежитие ************");

printf("\nВведите номер этажа --> ");

scanf("%d",&buf);

 

cur=s;

kk=0; //этаж не найден

k=0;

 

do //просмотр кольца этажей

{

if(cur->rr.number == buf)

{

kk=1; //этажнайден

break;

}

 

cur=cur->l;

}

while(cur!= s);

 

printf("\n");

 

if(kk == 1) //если этаж найден

while(k!= -1)

k=into(cur,k);

 

else

{

puts("\nТакого этажа нет");

getch();

break;

}

break;

 

case'z':

 

if(!s)

{

puts("\nНетстоянок!");

getch();

break;

}

 

puts("\n\n******************** Удаление этажа ********************");

s=del_floor(s);

break;

 

case'q':

 

to_file(s,h);

free_mem(&s);

return;

}

}

 

setlocale(LC_ALL,".OCP");

}

 

 

RING* from_file_ring(RING *s)

{

FILE *f;

int fd; //дескрипторфайла f

long l; //длина файла f

int kk = 0; //счётчик числа структур f

RING *s1, *s2;

 

if(!(f = fopen("hostel.dat","rb")))

{

puts("\nОшибкаоткрытияфайла!");

getch();

return 0;

}

 

fd=fileno(f); //переход от указателя на файл к дескриптору

if(!(l=filelength(fd))) //еслифайлпустто return

return 0;

 

if(!s)

{

if(!(s=(RING*)calloc(1,sizeof(RING))))

{

printf("No memory!\n");

getch();

}

 

fread(&(s->rr),sizeof(R),1,f); //чтенияблокакольца

 

s->l=s;

s->r=s;

s1=s;

 

kk++;

}

else s1=s->r; //кольцо уже существует

 

if(l <= sizeof(R)) //если больше нет блоков кольца в файле

return s;

 

do

{

if(!(s2=(RING*)calloc(1,sizeof(RING))))

{

printf("No memory!\n");

getch();

}

 

fread(&(s2->rr),sizeof(R),1,f); //чтенияблокакольца

 

s1->l=s2;

s2->r=s1;

s1=s2;

 

kk++;

}

while(l > kk*sizeof(R)); //пока не кончились блоки кольца в файле

 

s2->l=s;

s->r=s2; //кольцозамкнулось

 

fclose(f);

 

return s;

}

 

LINE* from_file_line(LINE **h, LINE **t)

{

FILE *g;

int gd; //дескрипторфайла g

long gl; //длина файла g

int gkk = 0; //счётчик числа структур g

LINE *cur;

 

if(!(g = fopen("line.dat","rb")))

{

puts("\nОшибкаоткрытияфайла!");

getch();

return 0;

}

 

 

gd=fileno(g); //переход от указателя на файл к дескриптору

if(!(gl=filelength(gd))) //еслифайлпуст

return 0;

 

do

{

if(!(cur=(LINE*)calloc(1,sizeof(LINE))))

{

printf("No memory!\n");

getch();

}

 

fread(&(cur->ll),sizeof(L),1,g); //чтенияблокаочереди

 

cur->next = NULL;

 

if(*h == NULL)

*h=*t=cur;

else

{

(*t)->next=cur;

*t=cur;

}

 

gkk++;

}

while(gl > gkk*sizeof(L)); //пока не кончились блоки очереди в файле

 

fclose(g);

 

return *h;

}

 

RING* add_floor(RING *s)

{

RING *s1, *s2;

 

if(!s) //кольцоещёнесоздано

{

if(!(s=(RING*)calloc(1,sizeof(RING))))

{

printf("No memory!\n");

getch();

}

 

printf("\nВведитеномерэтажа --> ");

fflush(stdin);

scanf("%d",&(s->rr.number));

 

s->rr.bed = s->rr.f_bed = 12;

s->rr.room = 4;

 

s->l=s;

s->r=s;

s1=s;

}

else s1=s->r; //кольцоужесуществует

 

 

if(!(s2=(RING*)calloc(1,sizeof(RING))))

{

printf("No memory!\n");

getch();

}

 

printf("\nВведитеномерэтажа --> ");

fflush(stdin);

scanf("%d",&(s2->rr.number));

 

s2->rr.bed = s2->rr.f_bed = 12;

s2->rr.room = 4;

 

s1->l=s2;

s2->r=s1;

s1=s2;

 

s2->l=s;

s->r=s2; //кольцозамкнулось

 

return s;

}

 

void add_stud(LINE **h, LINE **t)

{

LINE *cur;

 

if(!(cur=(LINE*)calloc(1,sizeof(LINE))))

{

printf("No memory!\n");

getch();

}

 

printf("\nВведитеФИОстудента --> ");

fflush(stdin);

gets(cur->ll.fio);

 

cur->next = NULL;

 

if(*h == NULL) //если создаётся первый элемент очереди

*h=*t=cur;

else

{

(*t)->next=cur;

*t=cur;

}

}

RING* del_floor(RING *s)

{

RING *cur = s;

int buf;

 

if(!s)

{

puts("\nНетстоянок!");

getch();

return s;

}

 

printf("\nВведитеномерэтажа --> ");

scanf("%d",&buf);

 

do

{

if(cur->rr.number!= buf) //еслиненайденэтаж

cur=cur->r;

else //если найден этаж

{

if(cur->r == cur) //элемент в кольце один

{

free(s);

return 0;

}

 

if(cur == s)

s=s->r;

 

cur->l->r=cur->r; //обход удаляемого элемента

cur->r->l=cur->l;

 

free(cur);

puts("\nЭтажудален");

return s;

}

}

while(cur!= s);

 

puts("\nТакогоэтажанет");

 

return s;

}

void del_stud(LINE **h, LINE **t, char *st)

{

LINE *f,*pr;

 

if (h == t && (!strcmp((*h)->ll.fio,st) || *st=='\0')) // вочередитолькоодинэлемент

{

free(*h);

*h=*t=NULL; // очередь пуста

return;

}

 

f=pr=*h; // далее f предыдущий к pr элемент

 

do

{

if(!strcmp(pr->ll.fio,st)) // найден элемент со строкой st

{

if(pr == *h)

{

*h=pr->next;

free(pr);

f=pr=*h;

return;

}

else

{

f->next=pr->next; // обходимэлемент pr

free(pr); // удаляем элемент pr очереди

pr=f->next; // выбор следующего элемента очереди pr

return;

}

}

else

{

f=pr;

pr=pr->next;

} // переход к следующему элементу

}

while(pr);

}

 

int kill(RING *s)

{

char in[30];

 

printf("Введите ФИО студента для выселения --> ");

fflush(stdin);

gets(in);

 

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

if(!strcmp(s->rr.pl[i],in)) //еслисовпалистроки

{

strcpy(s->rr.pl[i],""); //заносится пустая строка

s->rr.f_bed = s->rr.f_bed + 1; //свободныеместа

return i;

}

}

#include"superhead.h"

 

void out(RING *s)

{

RING *cur=s;

int k; //номерместа

int m;

int n; //номер комнаты

 

do

{

m = cur->rr.bed / cur->rr.room;

n = 0;

k = 1;

 

printf("\n\n\n");

printf(" ______________________________________________________________________________ ");

printf("| |");

printf("| ЭТАЖ № %d |",cur->rr.number);

printf("|______________________________________________________________________________|");

printf("| | |");

printf("| КОЛИЧЕСТВОМЕСТ - %3d | КОЛИЧЕСТВОСВОБОДНЫХМЕСТ - %3d |",cur->rr.bed,cur->rr.f_bed);

printf("|_____________________________________|________________________________________|");

printf("| | | |");

printf("| МЕСТО | КОМНАТА | ФИОСТУДЕНТА |");

printf("|_________|________________|___________________________________________________|");

 

while(cur->rr.pl[k-1][0]!= NULL || k <= cur->rr.bed) //пока есть студенты или не кончились кровати

{

printf("| | | |");

 

if(cur->rr.pl[k-1][0] == NULL)

{

printf("| %3d | %10d | |",k,(cur->rr.number * 100) + n);

printf("|_________|________________|___________________________________________________|");

 

k++;

 

if(k%m == 1)

n++;

 

continue;

}

 

printf("| %3d | %10d | %30s |",k,(cur->rr.number * 100) + n,cur->rr.pl[k-1]);

printf("|_________|________________|___________________________________________________|");

 

k++;

 

if(k%m == 1)

n++;

}

 

cur=cur->l;

}

while(cur!= s);

}

#include"superhead.h"

 

void out_floor(RING *cur)

{

int k = 1; //номерместа

int m =cur->rr.bed / cur->rr.room;

int n = 0; //номеркомнаты

 

printf("\n\n\n");

printf(" ______________________________________________________________________________ ");

printf("| |");

printf("| ЭТАЖ № %d |",cur->rr.number);

printf("|______________________________________________________________________________|");

printf("| | |");

printf("| КОЛИЧЕСТВОМЕСТ - %3d | КОЛИЧЕСТВОСВОБОДНЫХМЕСТ - %3d |",cur->rr.bed,cur->rr.f_bed);

printf("|_____________________________________|________________________________________|");

printf("| | | |");

printf("| МЕСТО | КОМНАТА | ФИОСТУДЕНТА |");

printf("|_________|________________|___________________________________________________|");

 

while(cur->rr.pl[k-1][0]!= NULL || k <= cur->rr.bed) //пока есть студенты или не кончились места

{

printf("| | | |");

 

if(cur->rr.pl[k-1][0] == NULL) //если нет студентов

{

printf("| %3d | %10d | |",k,(cur->rr.number * 100) + n);

printf("|_________|________________|___________________________________________________|");

k++;

 

if(k%m == 1) //соблюдаем кол-во студентов в одной комнате

n++;

 

continue;

}

 

printf("| %3d | %10d | %30s |",k,(cur->rr.number * 100) + n,cur->rr.pl[k-1]);

printf("|_________|________________|___________________________________________________|");

 

if(k%m == 1) //соблюдаем кол-во студентов в одной комнате

n++;

 

k++;

}

}

 

int into(RING *s, int k)

{

char in[30];

 

printf("ВведитеФИОстудента --> ");

fflush(stdin);

gets(in);

 

if(in[0] == '\0') //если нужно прекратить ввод

return -1;

 

while(s->rr.pl[k][0]!= 0) //проход до пустой строки

k++;

 

strcpy(s->rr.pl[k],in);

 

if(s->rr.f_bed!= 0)

s->rr.f_bed = s->rr.f_bed - 1; //свободныеместа

 

k++;

 

return k;

}

 

void to_file(RING *s, LINE *h)

{

FILE *f,*g;

RING *cur=s;

LINE *temp=h;

 

if(!(f = fopen("hostel.dat","w+b")))

{

puts("\nОшибкаоткрытияфайла!");

getch();

return;

}

 

if(!s) //если нет этажей то закрыть файл

{

fclose(f);

return;

}

 

do

{

fwrite(&(cur->rr),sizeof(R),1,f); //запись в файл элемента кольца

cur=cur->l;

}

while(cur!= s);

 

fclose(f);

 

 

if(!(g = fopen("line.dat","w+b")))

{

puts("\nОшибкаоткрытияфайла!");

getch();

return;

}

 

if(!h) //если нет очереди то закрыть файл

{

fclose(f);

return;

}

 

while(temp) //проходочереди

{

fwrite(&(temp->ll),sizeof(L),1,g); //запись в файл элемента очереди

temp=temp->next;

}

 

fclose(g);

}

void free_mem(RING **s)

{

RING *cur, *head=*s;

LINE *temp;

 

while(*s)

{

cur=*s;

*s=(*s)->r;

free(cur);

 

if(*s == head)

return;

}

}
6 Результаты работы программы

Заключение

 

Для корректной работы программы нужен компьютер поддерживающий MicrosoftVisualStudio 2005.

Рекомендуемые системныетребования:

-- Windows 98\ Me \XP \ Vista

-- 1.0 GHz CPU

-- 128 MB RAM

Программа создана в режиме, не имеющем графического интерфейса. Язык интерфейса русский.

 

Литература

1. Луцик Ю.А. Конспект лекций по курсу ОАИП

2. Батура М.П., Бусько В.Л. «Основы алгоритмизации и программирования. Язык Си»

3. Демидович Е.М. Основы алгоритмизации и программирования. Язык Си»