Упорядочивание данных таблицы «Факультет» (Лабораторная работа № 5)

Министерство  Образования и Науки Российской Федерации

Новосибирский Государственный Технический Университет

Кафедра Прикладной Математики

Лабораторная работа №5

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

на тему : “Упорядочивание данных”

Факультет:                      ПМИ

Группа:                                          ПМ-93

Студентка:                      Трубников А.И.

Преподаватель:            Еланцева И.Л.

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

1. Задание

Читая информацию из файла, создать упорядоченную по убыванию <ФИО>  таблицу «Факультет», используя пирамидальную (древесную) сортировку, содержащую в себе следующую информацию: <ФИО>, <номер группы>, <средний балл>.

Создать таблицу  «Отличники» :  <ФИО>, <Номер группы>, включив в неё студентов со средним баллом не ниже 4.

2. Анализ задачи

Дано: А(i)::=<ФИО><номер группы><средний балл>

<ФИО> ::= <последовательность символов>

<номер группы> ::= <последовательность символов>

<средний балл> ::= <число>

i = 1, N, где N – максимальное количество элементов таблицы

 Результат: упорядоченная таблица B(i)::= <ФИО><номер группы>

Метод решения:

Ключ = ФИО,

при i=0, n=0,

записать первый элемент А из файла в таблицу T

n=n+1

повторять

 пока(не конец файла и n≠N)

 повторять

 i=i+1 

              пока (ключ А> ключ Т[i-1] и i>0)

                            повторять

                            T[i]=T[i-1],

                            I=i-1,

 T[i]=A,

              n=n+1 ,

              i=n-1,

Если (не конец файла и n=N), то «Таблица заполнена, не вся информация из файла просмотрена»

Вызываем функцию HeapSort, в которую передаем таблицу T и n.

 i=0, j=0,

k=0,

пока(n≠i-1)

повторять

  i=i+1

  пока(средний балл T[i]≥4)

копируем <ФИО><Номер группы> из T[i] в B[j],

j=j+1, i=i+1,

k=j,

j=0,

повторять

  j=j+1,

  Записываем в файл «Отличники» таблицу B[j]

  пока (k>j)

3. Структура основных входных и выходных данных

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

Внешнее представление данных:

Представлены в файле in.txt,  который содержит не упорядоченные данные:  фамилии, имена, отчества, номера групп, средние баллы разделенные пробелами.

Внутреннее представление данных:

Таблица статическая, упорядоченная, вида:

struct student

 {

char familiya[40]; // фамилия студента

 char name[20]; // имя студента

 char ochestvo[20]; // очество студента

char gruppa [7]; // номер группы

 float srball ; // средний балл

};

struct tabl

{

struct elem [N];  // элементы таблицы 

int n; //фактическое количество элементов в таблице

 } ;

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

Внешнее представление данных:

Представлены в файле out.txt, в котором содержатся уже упорядоченная таблица без среднего балла, т.е. <ФИО> и <Номер группы> разделенные пробелами.

Внутреннее представление данных:

Таблица будет упорядоченной по <ФИО>, статической, вида:

struct otlichnik

{

char fami[40]; // фамилия студента

char nam[20]; // имя студента

char otch[20]; // очество студента

char grup[7]; // номер группы

};

  struct table

  {

        otlichnik el[N]; // элементы таблицы 

        int n; //фактическое количество элементов в таблице

  };

4. Алгоритм решения задачи

5. Текст программы

# include <stdio.h>

# include <string.h>

# include <conio.h>

# define N 10

struct student

{ char familiya[40];

  char name[20];

  char otchestvo[20];

  char gruppa [7];

  float srball;};

  struct otlichnik

{

char fami[40]; // фамилия студента

char nam[20]; // имя студента

char otch[20]; // очество студента

char grup[7]; // номер группы

};

struct table

  {

        otlichnik el[N]; // элементы таблицы 

        int n; //фактическое количество элементов в таблице

  };

struct tabl

{ student elem[N];

  int n;};

  // функция построения пирамиды

void Sift (tabl*T, int L, int R)