Управление таблицами. Создание упорядоченной по фамилии таблицы «Факультет» (Лабораторная работа № 4)

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

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

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

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

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

на тему : “Управление таблицами”

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

Группа: ПМ-71

Студентка: Калашникова О.А.

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

Новосибирск

2008

1. Задание

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

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

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

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

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

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

при i=0, n=0

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

n=n+1

повторять

 | i=i+1

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

 |        повторять

 |          |T[i]=T[i-1]

 |          |T[i-1]=A

 |          |I=i-1

| если i=0 n=n+1, i=n-1

| иначе

| если ключ А = ключ Т[i-1]

| t = strcmp (A,T[i-1])

| если t>0

|           | T[i] = T[i-1]

|           |T[i-1] = A

|           |n=n+1

| иначе Т[i] = A, n=n+1

| иначе если (ключ А < ключ Т[i-1])

| T[i] = A

| n=n+1

Пока не конец файла

3. Алгоритм

// задание таблицы

          struct table

             { type  elem [ N ];

                 int    n;  }

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

  T->elem[i]=A;

  T->n=T->n+1;

While { не пуст файл…}

  i=i+1;

    while (strcmp(ключ А> ключ Т[i-1] )<0 && i>0)

    { T->elem[i]=T->elem[i-1];

      i=i-1; }

    T[i]=T[i-1]

    T[i-1]=A

    I=i-1

while(i<T->n)

{ вывод элемента на экран};

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

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

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

  char name[20]; // имя

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

  int ozenka }; // оценка

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

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

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

# include <stdio.h>

# include <string.h>

# include <conio.h>

# define N 50

struct student

{ char familiya[40];

  char name[20];

  char gruppa [7];

  float ozenka ;};

struct tabl

{  student elem[N];

  int n;};

void main()

{ clrscr();

  FILE *f;

  int i=0;

  int t;

  tabl* T;

  student A;

  T=new tabl;

  T->n=0;

  if((f=fopen("in.txt","r")) == NULL) printf("fail ne naiden");

else

{ float name;

  fscanf(f,"%s %s %s %f",&A.familiya,&A.name,&A.gruppa,&A.ozenka);

  T->elem[i]=A;

  T->n=T->n+1;

while (!feof(f))

  {fscanf(f,"%s %s %s %f",&A.familiya,&A.name,&A.gruppa,&A.ozenka);

  i=i+1;

    while (strcmp(A.familiya,(*T).elem[i-1].familiya)<0 && i>0)

    { T->elem[i]=T->elem[i-1];

      i=i-1;}

      T->elem[i]=A;

      T->n=T->n+1;

        i=T->n-1;}

i=0;

while(i<T->n)

 {printf ("\n%s %s %s %f\n", T->elem[i].familiya, T->elem[i].name, T->elem[i].gruppa, T->elem[i].ozenka);

  i++;}}

getch();

fclose (f);}

6. Тесты

Исходный файл будет содержать следующие данные:

Фамилия, имя	Группа	Балл
Mazepa Lena	43	4
Antonov Leonid	76	3
Ivanov Sergei	71	3
Ivanov Andrei	74	5
Kravez Ira	24	4
Bondarenko Lesha	55	5
Denchenko Ivan	65	2

После упорядочивания на экран будет выведена следующая последовательность:

Фамилия, Имя	Группа	Балл
Antonov Leonid	76	3
Bondarenko Lesha	55	5
Denchenko Ivan	65	2
Ivanov Sergei	71	3
Ivanov Andrei	74	5
Kravez Ira	24	4
Mazepa Lena	43	4

Программа работает верно, что подтверждают проведенные тесты. Однако, программа имеет лишь один недостаток – если в исходном файле будут однофамильцы (при условии, что имена будут различаться), то программа будет их упорядочивать в порядке поступления. Это очевидно на примере «Ivanov Sergei» и  «Ivanov Andrei».