Создание базы данных, хранящей информацию о студентах учебного заведения

Размещено на http://www.allbest.ru/

Федеральное агентство связи

Сибирский государственный университет телекоммуникаций и информатики

Кафедра прикладной математики и кибернетики

КУРСОВАЯ РАБОТА

"Информационные технологии"

ВАРИАНТ 2

Выполнил: Голубев Антон

Проверил: Ракитский Антон Андреевич

Новосибирск 2014

Содержание

1. Задание к курсовой

2. Теория к курсовой работе

A) Сортировка методом прямого слияния

B) Односвязные списки

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

4. Работа функций

5. Вывод

1. Задание к курсовой

Необходимо создать файл со списком студентов в следующем формате:

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

В последующих Nстроках представлена информация о студентах. Каждая строка содержит: фамилию студента, имя, номер группы, дата рождения в формате день/месяц/год (dd/mm/yyyy), оценка за первый контрольный срок и оценка за второй контрольный срок. Все данные отделены друг от друга ровно одним пробелом, не содержат пробелов внутри и следуют строго в описанном порядке.

Необходимо написать программу для работы с представленной выше «базой данных». Программа должна иметь меню, в котором будут следующие пункты:

· Добавить студента

· Удалить студента

· Редактировать информацию о студенте

· Сохранить информацию о студентах в файл

· Загрузить информацию о студентах из файла

· Упорядочить студентов и вывести список на экран

· Найти студента

· Выйти из программы

Вся информация о студентах должна храниться в виде динамического списка. Для упорядочивания студентов использоватьбыструю сортировку(QuickSort).

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

Для поиска студента необходимо вводить фамилию, имя и номер группы. Чтобы упростить выполнение работы, будем считать, что не существует двух таких студентов, у которых все три параметра совпадают.

база данные информация

2. Теория к курсовой работе

A) Метод быстройсортировки

Метод Хоара или метод быстрой сортировки заключается в следующем. Возьмем произвольный элемент массива x. Просматривая массив слева, найдем элемент ai ? x. Просматривая массив справа, найдем aj? x. Поменяем местами aiи aj. Будем продолжать процесс просмотра и обмена, до тех пор пока i не станет больше j. Тогда массив можно разбить на две части: в левой части все элементы не больше x, в правой части массива не меньше x. Затем к каждой части массива применяем тот же алгоритм.

Трудоемкость метода существенно зависит от выбора элемента x, который влияет на разделение массива. Максимальные значения M и Cдля метода быстрой сортировки достигаются при сортировке упорядоченных массивов (в прямом и обратном порядке). Тогда в этом случае в одной части остается только один элемент (минимальный или максимальный), а во второй - все остальные элементы. Выражения для M и С имеют следующий вид

M=3(n-1),C=(n2+5n+4)/2

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

Элемент am называется медианой для элементов aL…aR, если количество элементов меньших am равно количеству элементов больших amс точностью до одного элемента (если количество элементов нечетно).

Минимальная трудоемкость метода Хоара достигается в случае, когда на каждом шаге алгоритма в качестве ведущего элемента выбирается медиана массива. Количество сравнений в этом случае C = (n+1)log(n+1)-(n+1). Количество пересылок зависит от положения элементов, но не может быть больше одного обмена на два сравнения. Поэтому количество пересылок - величина того же порядка, что и число сравнений. Асимптотические оценки для средних значений M и Cимеют следующий вид.

С=О(nlogn), М=О(nlogn) при n > ?.

Метод Хоара неустойчив.

B) Динамический список

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

Structst { char data[20];

structst *next; }; // Указательнаструктуруst

Здесь при описании указателя используем ещё не описанный объект structst *next , который будет служить ссылкой на соседний элемент списка. В зависимости от метода доступа к элементам линейного списка различают разновидности линейных списков. Наиболее известны списки, называемые стеком и очередью.Стек можно представить как стопку книг на столе, где добавление или взятие новой книги возможно только сверху. Таким образом, операции добавления и удаления элемента, а также доступа к элементу выполняются только в конце списка. Очередь - это список, где элементы удаляются из начала списка, а добавляются в конец списка (как обыкновенная очередь в магазине).

Пример создания и просмотра стека. Пусть требуется ввести некоторую последовательность символов, заканчивающуюся точкой, и напечатать ее в обратном порядке.

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

typedefstructst

{ charch;

structst *next;

} stack;

main()

{ stack *p,*q;

char a;

p=NULL;

system (“CLS”);

// заполнениестека

do

{ a=getchar();

q=(stack *)malloc(sizeof(stack));

q->next=p;

p=q;

q->ch=a;

} while(a!='.');

// печать стека c освобождением памяти

do

{ p=q->next;

free(q);

q=p;

printf("%c",p->ch);

} while(p->next!=NULL);

getch();

return 0;

}

Пример создания и просмотра односвязного списка. Пусть требуется поместить в список фамилии и вывести их в порядке очерёдности. В данном примере используем операторы new и delete.

#include<stdio.h>

#include <conio.h>

#include <stdlib.h>

typedefstructst

{ char data[20];

structst *next;} spis;

spis * create(void); //функциясозданиясписка

voidlist(spis *head); // функция просмотра списка

voidfree_spis(spis *head); //функцияосвобожденияпамяти

main()

{ system ("CLS");

spis *head; // адресголовысписка

head= create();

list (head);

free_spis (head);

getch();

}

spis * create(void)

{ spis *p, *pred, *h;

// pred - указатель на предыдущую структуру

// h- указатель на первую структуру

h=pred=newspis; //выделение памяти для первой структуры

printf(" fam: "); scanf("%s", pred->data);

do { p=new spis;

printf("\n fam: "); scanf("%s", p->data);

pred->next=p; //ссылка из предыдущей на текущую

pred=p; // сохранение адреса текущей

printf(" закончить? y/n ");

} while (getch()='y');

p->next=NULL;

return h;

}

void list(spis *head)

{ spis *p;

p=head;

while (p!=NULL) // пока не конец списка

{ printf("\n fio: %s",p->data);

p=p->next; // продвижение по списку

}

}

voidfree_spis(spis *head)

{ spis *p,*q;

q=p=head;

while (p!=NULL)

{

p=q->next;

delete q;

q=p;

}

head=NULL;

}

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

#include <locale.h>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

#include<iostream>

usingnamespacestd;

int N;

intindex[1000];

int i = 0;

typedefstruct S

{

struct S *next, *head;

charfam[20];

char name[20];

char group[8];

char d[11];

int KS1;

int KS2;

} spis;

voidAdd(spis **p, intflag){ // процедура для добавления студента в список

spis *temp = newspis;

if(flag==1)

cout<< "Введите нового студента:" <<endl<< "[Фамилия] [Имя] [№ группы] [Д.рождения] [1ый КС] [2ой КС]" <<endl;

elseif(flag==2)

cout<< "Введите измененного студента: [Фамилия] [Имя] [№ группы] [Д.рождения] [1ый КС] [2ой КС]" <<endl;

cin>> temp->fam>> temp->name >> temp->group >> temp->d >> temp->KS1 >> temp->KS2;

index[i] = (int)*(&temp);

temp->next = (*p)->head;

(*p)->head = temp;

if(flag==1)

cout<< "Студент успешно добавлен!" <<endl;

elseif(flag==2)

cout<< "Студент успешно изменен!" <<endl;

getch();

}

voidlist(spis *p){ // вывод списка на экран

spis *temp = p->head;

int j=0;

while(temp != NULL){

if(((spis*)index[j])->fam[0]!='\0')

cout<< ((spis*)index[j])->fam<< " " << ((spis*)index[j])->name << " " << ((spis*)index[j])->group << " " << ((spis*)index[j])->d << " " << ((spis*)index[j])->KS1 << " " << ((spis*)index[j])->KS2 <<endl;

temp = temp->next;

j++;

}

}

void Del(spis **p, int flag){

char k[20];

if(flag==1)

cout<< "Введите фамилию для удаления студента:" <<endl;

elseif(flag==2)

cout<< "Введите фамилию для изменения студента:" <<endl;

cin>> k;

cout<< k<<endl;

spis *temp = (*p)->head;

int j = 0;

while(temp != NULL){

if(strcmp(temp->fam,k)==0){ memset(temp->fam,0,sizeof(char)); index[j]=0;}

j++;

temp = temp->next;

}

if(flag==1)

cout<< "Студент успешно удален!" <<endl;

elseif(flag==2)

cout<< "Студент готов к изменению!" <<endl;

getch();

}

voidOutFile(spis **p){

FILE *out;

out = fopen("database","w");

int n = 0;

spis *temp = (*p)->head;

while(temp != NULL){

if(temp->fam[0]!='\0')

n++;

temp = temp->next;

}

fprintf(out,"%d\n",n);

temp = (*p)->head;

while(temp != NULL){

if(temp->fam[0]!='\0')

fprintf(out,"%s %s %s %s %d %d\n",temp->fam,temp->name,temp->group,temp->d,temp->KS1,temp->KS2);

temp = temp->next;

}

cout<< "Данные о студентах удачно сохранены в файл!" <<endl;

getch();

fclose(out);

}

voidClear(spis *p){ // процедура очистки списка

while(p->head != NULL){

spis *temp = p->head->next;

delete p->head;

p->head = temp;

}

}

voidInFile(spis **p){ // процедура загрузки списка из файла

Clear(*p);

FILE *in;

in = fopen("database","r");

int n;

fscanf(in,"%d",&n);

N=n;

cout<< n<<endl;

while(n>0){

spis *temp = newspis;

fscanf(in,"%s %s %s %s %d %d\n",temp->fam,temp->name,temp->group,temp->d,&temp->KS1,&temp->KS2);

index[i] = (int)*(&temp);

temp->next = (*p)->head;

(*p)->head = temp;

n--; i++;

}

cout<< "Данные успешно считаны!" <<endl;

getch();

}

voidSearch(spis **p){ // процедура поиска студента по фамилии, имени и номеру группы

cout<< "Поиск по фамилии, имени и номеру группы: " <<endl;

chartF[20],tN[20],tG[8];

cin>>tF>>tN>>tG;

int s = 0;

spis *temp = (*p)->head;

while(temp != NULL){

if(temp->fam[0]!='\0' &&strcmp(temp->fam,tF)==0 &&strcmp(temp->name,tN)==0 &&strcmp(temp->group,tG)==0){

cout<< temp->fam<< " " << temp->name << " " << temp->group << " " << temp->d << " " << temp->KS1 << " " << temp->KS2 <<endl;

s=1;

break;

}

temp = temp->next;

}

if(s==0) cout<< "Поиск не дал результатов" <<endl;

getch();

}

int Less(int p, int q){

if(strcmp(((spis*)p)->group,((spis*)q)->group)<0)return 1;

else if(strcmp(((spis*)p)->group,((spis*)q)->group)>0) return 0;

else if(strcmp(((spis*)p)->fam,((spis*)q)->fam)>0) return 0;

else if(strcmp(((spis*)p)->fam,((spis*)q)->fam)<0) return 1;

else if(strcmp(((spis*)p)->name,((spis*)q)->name)>0) return 0;

else if(strcmp(((spis*)p)->name,((spis*)q)->name)<0) return 1;

return 0;

}

voidQuickSort(int L, int R){

int x = index[L];

int i = L;

int j = R;

while(i <= j){

while(Less(index[i],x)) i++;

while(Less(x,index[j])) j--;

if(i<= j){ int t = index[i];

index[i] = index[j];

index[j] = t;

i++;j--;

}

}

if(L < j) QuickSort(L,j);

if(i< R) QuickSort(i,R);

}

intmain(){

setlocale(LC_ALL, "Russian");

N = 0;

spis *head = newspis;

head->head = NULL;

while(1){

system("CLS");

cout<<endl<<endl<<endl;

puts("1. Добавить");

puts("2. Удалить");

puts("3. Редактировать ");

puts("4. Сохранить в файл");

puts("5. Загрузить из файла");

puts("6. Упорядочить и вывести");

puts("7. Найти ");

puts("8. Выйти");

char m = getch();

switch(m){

case '1': Add(&head,1); break;

case '2': Del(&head,1); break;

case '3': Del(&head,2); Add(&head,2); break;

case '4': OutFile(&head); break;

case '5': InFile(&head); break;

case '6': QuickSort(0,N-1); list(head); system("PAUSE"); break;

case '7': Search(&head); break;

case 'q': case 'й': list(head); system("PAUSE"); break;

case '8': exit(0); break;

default: exit(0); break;

}

}

Clear(head);

return 0;

}

4. Работа функций

Добавление студента.

Удаление студента.

Редактирование студента.

Сохранение в файл

Загрузка из файла

Вывод

Поиск



5. Вывод

В ходе написания курсовой работы был создан файл со списком студентов в заданном формате. Так же реализована программы для работы с «базой данных» студентов.

Программа может:

1) Добавить студента

2) Удалить студента

3) Редактировать информацию о студенте

4) Сохранять информацию о студентах в файл

5) Загружать информацию о студентах из файла

6) Упорядочивать студентов методом прямого слияния

7) Поиск по студенту

Вся информация из файла помещается в динамический список.

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

Поиск производиться по фамилии, имени и номеру группы одновременно.

Размещено на Allbest.ru