Лаб. практикум

81

несортированными. Внутренние таблицы (создаваемые в оперативной памяти) могут храниться в виде вектора или в виде списка.

Пример решения задачи

Задача. Входной файл st.txt содержит сведения о сдаче студентами группы экзаменационной сессии. Каждая запись файла содержит фамилию и инициалы студента (15 символов) и пять оценок (5 символов) и завершается символом ” перевод строки”. Количество записей не более 30. Вывести:

-фамилии всех студентов с указанием среднего балла каждого студента;

-информацию о заданном студенте.

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

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

-------------------------------------------------------

Выберите номер пункта меню: 1 - средние баллы студентов

2 - информация о заданном студенте

3 - выход

-------------------------------------------------------

При выборе пункта 3 выполнение программы завершается.

/* Программа 9.1 на языке С++ */

#include <stdio.h> #include <conio.h> #include <string.h> #define MAX 30

// тип записи файла struct STUDENT

// прототипы функций void PechTab (EL_TAB * tab, int n); void Stud (EL_TAB * tab, int n);

if ((f= fopen("st.txt","r")) == NULL) { puts ("Файл st.txt не найден");

return;

}

// создание таблицы n = 0;

while (fgets((char *)&tz, sizeof(struct STUDENT), f) != NULL)

{for (i=0,s=0; i<5; i++)

{int ocenka = tz.oc[i]-'0'; tab[n].oc[i] = ocenka;

s += ocenka;

}

tz.fio[14]='\0';

strcpy(tab[n].fio,tz.fio); tab[n++].srball = s/5;

}

fclose(f);

char nom; // номер пункта меню do

{clrscr();

puts ("------------------------------------------------------");

nom = getche(); switch (nom)

{case '1': PechTab(tab,n); break; case '2': Stud(tab,n); break; case '3': break;

default: puts ("\nНужно ввести номер от 1 до 3");

}

if (nom != '3')

{puts("\nДля продолжения нажмите любую клавишу"); getch();

}

}

while (nom != '3');

}

void PechTab (EL_TAB * tab, int n)

{int j;

puts ("\nФамилия и.о. Ср.балл");

printf("%s %.1f\n", tab[j].fio, tab[j].srball);

}

}

// заглушка для функции вывода информации о студенте void Stud (EL_TAB * tab, int n)

{

}

Контрольные вопросы и упражнения

1.Что такое таблица?

2.Какая таблица называется линейной или последовательной?

3.Какие операции над таблицами выполняются в программе 9.1?

84

4. Как описать таблицу, содержащую название месяца и количество дней в каждом из 12 месяцев года?

5.Опишите таблицу из n элементов ( n ≤ 50). Каждый элемент состоит из 4-х полей, описывающих анкетные данные спортсмена:

-фамилия, имя и отчество;

-год рождения;

-рост в метрах (например, 1.85);

-вес в кг.

6.Опишите таблицу из n элементов ( n <=100), каждый элемент которой содержит следующие поля:

-№ поезда (целое число);

-пункт назначения (строка из 30 символов);

-время отправления (строка из 6 символов).

Задания

5.Ознакомьтесь с теоретическим материалом и примером решения задачи. Ответьте на контрольные вопросы.

6.Введите и выполните программу 9.1. Создайте файл st.txt для проверки программы и снова запустите программу.

7.Вместо заглушки функции Stud напишите функцию, которая запрашивает фамилию студента, выполняет линейный поиск элемента с заданной фамилией в таблице и выводит значение найденного элемента или сообщение об ошибке, если такой фамилии нет в таблице.

8.Добавьте в программу подпрограмму сортировки таблицы в порядке убывания среднего балла.

9.Добавьте подпрограмму вывода:

а) отличников группы; б) студентов со средним баллом не ниже 4;

в) студентов, имеющих двойки.

85

Л а б о р а т о р н а я р а б о т а N 10

Организация списков с помощью указателей и структур

Таким образом, каждый элемент списка состоит из двух полей - поля информации и поля ссылки (рис. 10.1).

Рис. 10.1. Cписок

На языке С список организуется с помощью указателей и структур или же с помощью параллельных массивов.

Рассмотрим организацию списков с помощью указателей и структур. Допустим, программа создает список идентификаторов. Тогда в программе следует описать тип элемента списка в виде структуры из двух полей и указатель списка. Указатель списка и поле ссылки на следующий элемент описываются как переменные типа указатель на структуру. Например:

/* описание списка идентификаторов */

Обратите внимание: EL_SP - это не переменная, а имя типа структуры, память для элемента списка здесь не выделяется.

Чтобы выделить память для очередного элемента списка, нужно

86

вызвать функцию malloc(). Аргументом этой функции является размер памяти в байтах, а возвращает она адрес выделенного участка памяти (при использовании этой функции нужно включать файл stdlib.h). Например, оператор присваивания

p = (struct EL_SP *)malloc (sizeof(struct EL_SP));

выделяет память для первого элемента списка и устанавливает указатель p. Операция sizeof (srtuct EL_SP) определяет размер памяти в байтах для структуры типа EL_SP. Функция malloc() выделяет требуемый объем памяти и возвращает адрес этого блока памяти, который присваивается

указатель, осуществляется с помощью операции ->. Например, для приведенного выше списка идентификаторов

Пустая ссылка обозначается константой NULL. Например, оператор p = NULL;

означает, что указатель списка ни на что не будет ссылаться, т.е. список становится пустым. Поле ссылки последнего элемента списка должно иметь значение NULL.

87

Пример решения задачи

Задача. Дана последовательность из n идентификаторов. Длина каждого идентификатора не более 8 символов. Напечатать идентификаторы в лексикографическом порядке.

Пример теста:

n=7

Метод решения. Задачу можно решить, сцепляя идентификаторы

всписок в лексикографическом порядке по мере их ввода. В

сформированный из предшествующих идентификаторов. На рис. 10.2 показано, как изменяется список в процессе включения в него очередных идентификаторов.

Еще несколько пояснений к программе. Идентификаторы поочередно вводятся в массив t_id с помощью функции gets(). Сравнение двух идентификаторов производится с помощью функции strcmp(), которая возвращает значение 0, если идентификаторы равны, и разность кодов двух соответствующих несовпавших символов, если идентификаторы не равны. Значит, значение функции будет < 0, если первый идентификатор в лексикографическом порядке должен следовать раньше второго, и значение будет > 0 в противном случае.

. . .

P

Рис. 10.2. Пример процесса формирования списка идентификаторов

Функция strcpy() служит для копирования строк символов, имеет два аргумента: указатель на строку, куда копировать, и указатель на строку, откуда копировать.

/* выделение памяти для нового эл-та списка */ pt = (struct EL_SP *) malloc(sizeof(struct EL_SP)); strcpy(pt->id, t_id);

if (*p==NULL || strcmp(pt->id,(*p)->id) < 0) { /* включение ид-ра в начало списка */

pt->sled=*p; *p=pt;

}

else

{ /* поиск элемента списка, после которого нужно включить идентификатор */

k=*p;

while (k!=NULL && strcmp(pt->id,k->id)>=0) { j=k; k=k->sled;

}

/* включение эл-та *pt после элемента *j */ j->sled=pt; pt->sled=k;

}

{struct EL_SP *i; /* указатель текущего элемента списка */ printf ("\nРезультат:\n");

for ( i=p; i!=NULL; i=i->sled ) puts (i->id);

}