Лабораторной работе № 1

ОТЧЕТ ПО

Дисциплина: « Структуры и алгоритмы обработки данных »

Тема: «Программирование с использованием динамических структур: списки»

Вариант 11

ВЫПОЛНИЛ студент группы 14-ИТ-2

Кунцевич Н.А.

ПРОВЕРИЛА ст. преподаватель кафедры ТП

Деканова М.В.

Полоцк 2015 г.

Анализ задания: В задании необходимо разработать программу, в которой выполняется ввод списка записей определённого типа. Записи вводятся построчно в определённом формате, признак завершения ввода – ввод пустой строки. Список – двунаправленный.

11 вариант, тип СТУДЕНТ, сортировка по № зачетной книжки.

СТУДЕНТ:

· фамилия, имя, отчество (строки по 15 символов);

· номер зачётной книжки (целое семизначное число);

· дата рождения (в формате дд.мм.гггг).

Листинг программы:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <locale.h>

typedef struct //Объявление структуры, в которой содержится информация о студентах

{ char surname[15]; //фамилия

char Name[15];// имя

char middleName[15];// отчество

int day, month, year,// день, месяц, год

number;//номер зачетки

}Student; //имя типа структуры

//Структура описывающая элемент списка

typedef struct NODE{

Student st; //Поле данных элемента списка

struct NODE *next, *prev; // Указатели на следущий и предыдущий эле-мент списка

}NODE;

//Объявляем тип переменной - двухсвязный список

typedef struct

{

NODE *head, *curr; //Указатели на текущий и начальный элемент списка

}LIST; //имя двухсвязного списка

LIST* list; //Объевление двухсвязного списка

char str[300];// Вспомогательная строка

void Create(void);//Функция создания списка

void Menu(void);//Функция вызова меню

Student enter(void);//Функция заполнения полей информации о студенте

int Add(LIST*, Student);//Функция добавления элемента в список

int Ins(Student);// Функция вставки элемента перед текущим

int Del(void);// Функция удаления текущего элемента списка

void Sort(void); //Функция сортировки элементов в списке по номеру за-четки

void swap(void); //Функция смены позиции соседних элементов

void Print(void);//Функция вывода списка на экран

int checkStr(char*); //Функции проверки на ввод для текстовых полей структуры

int checkDate(int,int, int);// Функция проверки даты

void Destroy(void); // Функция удаления списка из памяти

int checkNum(int bnum); //проверка на совпадение номеров зачеток

//-------------------------------------------------------------------------------

int main(void) //основная функция

{

setlocale(LC_ALL,"ru"); //локализация

Create(); //Выделение памяти

Menu(); //Вызов меню

return 0; //выход из программы

}

void Create(void){ //функция создания списка

list = (LIST*)malloc(sizeof(LIST)); //выделение памяти под список

list->head = NULL; //указатель на начало списка равен нулю

list->curr = NULL; //указатель на текущий элемент списка равен нулю

}

void Menu(void)

{

while (1) //цикл выполняется пока не будет выполнено условие

{

int menu = 0; //Объявим переменну значение выбора и прировняем её к 0

//Описание пунктов меню

printf("-- Выберите пункт --\n\n");

printf("1. Добавить элемент в конец списка\n");

printf("2. Вставить элемент перед текущим элементом списка\n");

printf("3. Удалить элемент из списка\n");

printf("4. Вывести список\n");

printf("5. Сортировка списка\n");

printf("0. Выход\n\n");

while (1){ //пока условие не выполнено, цикл выполняется

//fflush(stdin); //очистка буфера ввода

if (scanf("%d", &menu) == 1){ //если введен номер пункта в меню

break; //завершаем цикл

}

else{ //иначе выводим сообщение об ошибке

printf("Неверный ввод. Попробуйте снова...\n");

}

}

switch (menu){ //Организация выбора действия

case 1:{ //если выбран первый пункт меню

system("cls"); //очистка экрана

while(1) //пока не выполнено условие, выполняется цикл

{

Student data = enter(); //заполнение информации об студенте

fflush(stdin);//очистка буфера ввода

if (Add(list, data) == 1) //добавление информации об студенте в список

printf("Выполнено!\n"); //сообщение о выполнение

printf("Завершить ввод? \n"); //проверка на заверше-ние

gets(str); //ввод строки

if(strlen(str)==0)//если строка пуста, завершаем ввод

break;//выход из цикла

else

system("cls"); //очищаем экран

}

system("pause"); //ожидание нажатия клавиши

system("cls"); //очищаем экран

break; //завершение действия пункта меню

}

case 2:{ //если выбран второй пункт меню

system("cls"); //очищаем экран

Student data = enter(); //заполнение информации об студенте

if(Ins(data) == 1) //вставка элемента списка перед текущим элементом

{

printf("Выполнено!\n"); //сообщение о выполнении

}

system("pause"); //ожидание нажатия клавиши

system("cls"); //очищаем экран

break; //завершение действия пункта меню

}

case 3:{ //если выбран третий пункт меню

system("cls"); //очищаем экран

if(Del() == 1) //удаление текущего элемента

printf("Выполнено!\n");//сообщение о выполнении

system("pause");//ожидание нажатия клавиши

system("cls");// очищаем экран

break;// завершение выполнения пункта меню

}

case 4:{

system("cls"); //очищаем экран

Print();//вывод списка на экран

system("pause");// ожидание нажатия клавиши

system("cls");// очищаем экран

break; // завершение выполнения пункта меню

}

case 5:{

system("cls");//очищаем экран

Sort();//сортировка списка по номеру зачетки

printf("Done!\n");//сообщение о выполнении

system("pause");//ожидание нажатия клавиши

system("cls");//очищаем экран

break; // завершение выполнения пункта меню

}

case 0:{

system("cls");//очищаем экран

exit(0); //выход из программы

break; // завершение выполнения пункта меню

}

default:{

system("cls");//очищаем экран

printf("Неверный ввод. Попробуйте снова...\n"); //сообщение об ошибке

break; // завершение выполнения пункта меню

}

}

}

}

//-------------------------------------------------------------------------

Student enter(void)//Функция заполнения информации об студенте

{

int Shtetchik = 0;//устанавливаем флаг в ноль

Student st; //объявление структуры, содержащей информацию о студенте

char bname[50];//фамилия

char blastName[50];//имя

char bsurName[50];//отчество

int bday;//день

int bmonth;//месяц

int byear;//год

int bnum;//номер зачетки

printf("Введите данные в формате:\n Фамилия Имя Отчество № зачетной книжки дата рождения(в формате дд.мм.гггг)\n");//вывод формата ввода

while(Shtetchik!= 1)//пока флаг не установлен в единицу, выполняем цикл

{

fflush(stdin);//очистка буфера ввода

gets(str);//ввод строки

sscanf(str,"%s %s %s %d %d.%d.%d",blastName,bname,bsurName,&bnum,&bday,&bmonth,&byear);//считывания Фио номера зачетки и даты из строки

if(checkStr(bname)==0){//проверка на соответсвие фамилии

printf("Ошибка ввода. Повторите попытку ещё раз.\n\n");//сообщение об ошибке

continue;}//выполняем цикл сначала

if(checkStr(blastName)==0){//проверка на соответствие имени

printf("Ошибка ввода. Повторите попытку ещё раз.\n\n");//сообщение об ошибке

continue;}//выполняем цикл сначала

if(checkStr(bsurName)==0){//проверка на соответствие отчества

printf("Ошибка ввода. Повторите попытку ещё раз.\n\n");//сообщение об ошибке

continue;}//выполняем цикл сначала

if(checkDate(bday,bmonth,byear)==0){//проверка даты

printf("Ошибка ввода. Повторите попытку ещё раз.\n\n");//сообщение об ошибке

continue;}//выполняем цикл сначала

if(bnum > 9999999 || (checkNum(bnum) == 0)){//проверка номера зачетки

printf("Ошибка ввода. Повторите попытку ещё раз.\n\n");//сообщение об ошибке

continue;}//выполняем цикл сначала

strcpy(st.surname,bname);//копируем содержимое строки с фамилией в поле структуры

strcpy(st.Name,blastName); //копируем содержимое строки с именем в поле структуры

strcpy(st.middleName,bsurName); //копируем содержимое строки с отчеством в поле структуры

st.number=bnum;//поле структуры – номер зачетки равно значению в числе номер зачетки

st.day=bday; //поле структуры – день равно значению в числе день

st.month=bmonth; //поле структуры – месяц равно значению в числе месяц

st.year=byear; //поле структуры – год равно значению в числе год

Shtetchik = 1;//устанавливаем флаг в 1

}

return st; //возвращаем структуру

}

int checkDate(int day, int mounth, int year){//функция проверки даты

if(day > 31 || day <= 0) //проверка дня

return 0;//возвращаем код ошибки

else if(mounth > 12 || mounth <= 0)// проверка месяца

return 0;//возвращаем код ошибки

else if(1970 > year || year > 1998)// проверка года

return 0;//возвращаем код ошибки

return 1;//возвращаем код выполнения

}

int checkStr(char* str){ //Функция проверки содержимого и размера строки

for(int i = 0; i < strlen(str); i++) //проверка на содержание сим-волов

if(str[i] >= '0' && str[i] <= '9') //если строка содержит числа

return 0;//возвращаем код ошибки

if(strlen(str) > 15) //проверка на длинну строки, если больше 15

return 0;//возвращаем код ошибки

if(str[0] == ' ') //проверка на первый символ - пробел

return 0;//возвращаем код ошибки

return 1;//возвращаем код выполнения

}

int checkNum(int bnum)//Функция проверки номера зачетки

{

NODE* tmp = list->head; //устанавливаем tmp в начало списка

while(tmp!= NULL)//пока список не пуст

{

if (bnum == tmp->st.number)//если номер зачетки совпадает с полем структуры

return 0; //возвращаем код ошибки

tmp = tmp->next; //смещаем начало списка на следущий элемент

}

return 1;//возвращаем код выполнения

}

//-----------------------------------------------------------------

int Add(LIST* list, Student St){

NODE* tmp = (NODE *)malloc(sizeof(NODE)); //выделение памяти под но-вый элемент списка

if(!tmp) //проверка на выделение памяти

return 0;//возвращаем код ошибки

if(!list->head){ //если список пуст

list->head = tmp; //начальный элемент списка - tmp

list->head->prev = NULL;// предыдущего элемента не существует

list->head->next=NULL; //следующего элемента не существует

}

else{//иначе

if(!list->curr)//если текущего нет

list->curr = list->head;// первый элемент - текущий

while(list->curr->next)//пока существует следующий после текущего существует

list->curr = list->curr->next;//текущим становится следующий после текущего

list->curr->next = tmp;//следующий после текущего - tmp

tmp->prev = list->curr; //Указатель предыдущего указывает на текущий элемент

}

tmp->st = St; //получение информации об студенте

tmp->next = NULL; //установка указателя на следующий элемент обнуля-ется

list->curr = tmp; //текущий элемент равен новому

return 1; //возвращаем код выолнения

}

void Print(void)//Функция вывода списка на экран

{

int i = 0;//номер записи

NODE* tmp = list->head;//Объявление временного элемента списка равного начальному

while(tmp!= NULL){//пока существует начальный элемент списка

i++;//повышаем номер записи на единицу

printf("#%d: %s %s %s\n\tНомер зачетки [%d]\n\tДата рождения %02d.%02d.%04d\n\n", i,

tmp->st.Name, tmp->st.surname, tmp->st.middleName,

tmp->st.number, tmp->st.day, tmp->st.month, tmp->st.year

);//выводим первый элемент списка

tmp = tmp->next;//первым элементом становится следующий

}

}

void Destroy(void)//Очистка всего списка

{

while(list->head) //пока существует первый элемент списка

{

list->curr = list->head; // текущий - начальный

list->head = list->head->next; //начальный - следующий

free(list->curr);// освобождаем память из-под текущего

}

list->head = list->curr = NULL; //обнуление указателей

}

int Ins(Student st){//Функция вставки элемента

if(!list->head ||!list->curr) //если не существует элементов в списке

return Add(list, st);// выполняем добавление элемента в конец списка

NODE *tmp = (NODE *)malloc(sizeof(NODE)); //выделение памяти под временный элемент списка

if(!tmp) //проверка на выделение памяти

return 0;//Возвращаем код ошибки

tmp->next = list->curr; //следующий элемент равен текущему

tmp->prev = list->curr->prev;// предыдущий равен предыдущему для текущего

if(tmp -> prev) //если существует предыдущий элемент для временного элемента

tmp->prev->next = tmp; //то следующий после предыдущего для временного – временный

list->curr->prev = tmp; //и предыдущий элемент для текущего является временным

if(list->curr == list->head)//если текущий элемент является начальным

list->head = tmp;// начальный элемент - временный

tmp->st = st; //элемент получает информацию о студенте

list->curr = tmp; // текущий элемент - временный

return 1; //Возвращаем код выполнения

}

void Sort(void){//Функция сортировка

if(!list->head)// //Если список пуст

return;//сортировка не выполняется

int Flag = 1;//установка флага в единицу

while(Flag)//пока флаг установлен в еденицу

{

Flag = 0;//устанавливаем флаг в ноль

//Устанавливаем указатель текущего элемента, на начальный

list->curr = list->head;

//Пока существует следущий элемент после текущего

while(list->curr->next){

if(list->curr->st.number > list->curr->next->st.number)

//если номер зачетки текущего элемента больше номера зачетки следующего

{

swap();//меняем элементы местами

Flag = 1;//устанавливаем флаг в единицу

}

else //иначе

list->curr = list->curr->next;

//текущий становится следующим

}

}

}

void swap(void){//Функция обмена местами

NODE* tmp = list->curr->next; //Устанавливаем временный указа-тель на следущий элемент после текущего

list->curr->next = tmp->next; //указатель следущего после текущего элемента, устанавливаем на следующий после времменого

tmp->prev = list->curr->prev; //указатель на предыдущий элемент перед временным, устанавливаем на предыдущий перед текущим

if(list->curr->next!= NULL) //Если следующий после текущего элемента существует

list->curr->next->prev = list->curr;//то предыдущий следующего после текущего указывает на текущий

if(tmp->prev!= NULL) //Если предыдущий указатель для временного су-ществует

tmp->prev->next = tmp;// то следущий после предущего для временного указывает на временный

tmp->next = list->curr; //устанавливаем указатель на следующий после временного, на текущий элемент

list->curr->prev = tmp; //указатель на предыдущий для текущего элемента устанавливаем на временный

if(list->curr == list->head) //если укатель на текущий элемент указывает на начальный

{

list->head = tmp; //то начальный элемент равен временному

}

}

int Del(void) //Функция удаление элемента

{

if(list->curr==NULL) //Если текущий элемент не существует

return 0; //Возвращаем код ошибки

NODE *tmp=list->curr->prev; //Объявляем временный элемент списка указывающий на предудыщий для текущего элемента списка

if(!tmp){ //Если он не существует

list->head=list->head->next; // то следующий после начального элемента, становится начальным элементом

list->head->prev=NULL; //обнуляем указатель на предыдущий

}else{//иначе

tmp->next=list->curr->next; // следующий после временного эле-мента становится следующим после текущего

if(list->curr->next) // если следующий после текущего существует

list->curr->next->prev = tmp; //то предыдущий следующего после текущего равен временному

}

free(list->curr);//освобождаем память из-под текущего элемента

list->curr=tmp; //текущий элемент получает значение временного

return 1; //Возвращаем код выполнения

}