Else
Else
Рис 3. Структура кольцевого двухсвязного списка
Рисунок 2. Структура двусвязного списка
Рисунок 1. Структура односвязного списка
Линейные списки
Тяговые подстанции
Участке с автоблокировкой
Нитей на двухпутном
1-дроссель
2-изолирующий стык
3-стыковое соединение
4-междупутное соединение
эффективность различных видов тяги
- электрическая тяга
КПД 
%
% 
%
- тепловозная тяга
КПД 
%
- газотурбинная тяга
КПД 
%
- паровозная тяга
КПД 
%
Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент ссылался на следующий. Такую динамическую структуру называют однонаправленным (односвязным) линейным списком.
На рисунке 1 приведена структура односвязного списка. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка.
Однако, обработка односвязного списка не всегда удобна, так как существует возможность перемещения по списку лишь в одну сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двусвязного списка приведена на рисунке 2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать NULL, как и показано на рисунке.
Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.
Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двусвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двусвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рисунке 3.
При работе с такими списками несколько упрощаются некоторые процедуры, выполняемые над списком. Однако, при просмотре такого списка следует принять меры предосторожности, чтобы не попасть в бесконечный цикл.
Создадим однонаправленный список студентов и их оценок. Каждый элемент списка будет иметь следующий вид:
struct student
{
char *fio;
int mark;
student *next;
}
Для формирования списка требуется иметь, по крайней мере, один указатель – на начало списка (голова списка).
student * begin=NULL;
и один вспомогательный указатель student *adr;.
Опишем процедуру создания списка
void vvod ()
{
int n;
cout<< “Введите количество студентов ”;
cin>>n;
const int dlin=20;
char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента
for (int i=1;i<=n; i++)
{
if (begin==NULL) // выделение памяти под первый элемент списка
{
begin=new (student);
adr=begin;
}
else // выделение памяти под очередной элемент списка
{
adr->next=new(student);
adr=adr->next;
}
//заполнение элементов списка
cout<< “Введите фамилию ”;
cin.getline(f,dlin);
adr->fio=new (char [strlen(f)+1]);
strcpy(adr->fio,.f);
cout<< “Введите оценку ”;
cin>>(adr->mark);
adr->next=NULL;
}
}
В данном случае мы создали список студентов как очередь. Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (firs in – first out, первым пришел – первым вышел). В нашем примере указатель begin указывает на начало списка, и не изменяется во время выполнения программы. Добавление элементов происходит в конец списка. Очевидно, что обработка элементов для списка, сформированного таким образом, может происходить только с первого введенного.
Другим частным случаем однонаправленного списка является стек, добавление в который и выборка из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел). Создадим список студентов как стек, постоянно передвигая указатель begin и последний созданный элемент делая головой списка.
void vvod1 ()
{
int n;
cout<< “Введите количество студентов ”;
cin>>n;
const int dlin=20;
char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента
for (int i=1;i<=n; i++)
{
adr=new(student);
cout<< “Введите фамилию ”;
cin.getline(f,dlin);
adr->fio=new (char [strlen(f)+1]);
strcpy(adr->fio,f);
cout<< “Введите оценку ”;
cin>>(adr->mark);
adr->next=begin;
begin=adr;
}
}
Чтобы вывести на экран элементы списка, созданного любым из предложных способов, можно использовать следующую процедуру
void vivod()
{
adr=begin;
while (adr!=NULL)
{
cout<<"\n "<<(adr->fio)<<" "<<adr->mark;
adr=adr->next;
}
}
Кроме процедур создания и вывода на экран для списка обычно определяют следующие процедуры:
- добавления элемента в конец (начало) списка;
- поиска заданного элемента;
- вставка элемента до или после заданного элемента;
- сортировка списка;
- удаления заданного элемента (одного или всех);
- удаление списка.
Рассмотрим их подробно
Процедура добавления элемента в конец списка пишется по-разному в зависимости от того, как создавался список: как стек или как очередь.
Например, если список создан как стек, процедура добавления записывается следующим образом:
void add()
{
student *adr;
char f[dlin];
adr=begin;
begin=new(student);
cout<<"\nEnter fio ";
gets(f);
begin->fio=new (char [strlen(f)+1]);
strcpy(begin->fio,f);
cout<<"\nEnter mark ";
cin>> begin->mark;
begin->next=adr;
}
Если список создан как очередь, процедура добавления записывается следующим образом:
void add1()
{
student *adr;
char f[dlin];
if (begin==NULL)
{
begin=new (student);
adr=begin;
}
else
{
adr=begin;
while (adr) adr=adr->next;
adr->next=new(student);
adr=adr->next;
}
cout<< “Введите фамилию ”;
cin.getline(f,dlin);
adr->fio=new (char [strlen(f)+1]);
strcpy(adr->fio,f);
cout<< “Введите оценку ”;
cin>>(adr->mark);
adr->next=NULL;
}
Часто выделяют создание головного элемента очереди и элемента, отличного от головного в две разные процедуры.
Очевидно, что процедура создания списка на практике представляет собой многократный вызов процедуры добавления элементов.
Процедура поиска заданного элемента очень проста.Просматриваются все элементы с первого до последнего и каждый элемент проверяется на соответствие условию.Например, найти всех студентов с заданной оценкой.
viod poisk (int k)
{
student * adr=begin;
int m=0;
while (adr)
{
if(adr->mark==k) {cout<<adr->fio<< “ ”; m++;}
adr=adr->next;
}
if (m) cout<< “Найдено ”<<m<< “студентов”;
else cout<< “Не найдено студентов с оценкой”<<k;
}
При добавлении элемента в список до заданного необходимо сначала отдельно проверить первый элемент списка. Если он совпадает с заданным, то необходимо вставить элемент как голову. Если же нет, то необходимо просматривать элементы, начиная с второго и до последнего. Причем просмотр необходимо осуществлять, фиксирую каждый раз вспомогательный указатель adr на предыдущем элементе (то есть просматривать элемент adr->next).
Процедура добавления нового студента до студента с заданной фамилией:
void add2(char * f)
{
student *adr;
if (strcmp (begin->fio, f)==0) add();
else
{
adr=begin;
while (adr->next && strcmp (adr->next->fio, f)) adr=adr->next;
if (adr->next)
{
student * adr1=adr->next;
adr->next=new(student);
cout<< “Введите фамилию ”;
cin.getline(f1,dlin);
adr->next->fio=new (char [strlen(f1)+1]);
strcpy(adr->next->fio,f1);
cout<< “Введите оценку ”;
cin>>(adr->next->mark);
adr->next->next=adr1;
}
else cout<< “Нет студента с фамилией”<<f;
}
При удалении заданного элемента из списканеобходимо сначала отдельно проверить первый элемент списка. Пока он совпадает с заданным, необходимо голову передвигать на следующий элемент, а текущий элемент удалять. Далее нужно установить текущий указатель adr на голову и просматривать элемент adr->next, пока он не равен нулевому указателю. Если просматриваемый элемент совпадает с заданным, текущий указатель сохраняется как указатель a, перемещается на следующий элемент, а из- поз указателя а освобождается память. В противном случае текущий указатель просто перемещается на следующий.
Рассмотри функцию удаления всех студентов с заданной оценкой
void udol (int k) //
{
if (begin)
{
student *adr;
while (k==begin->mark)
{
cout<<begin->fio<<" udal \n";
adr = begin;
begin=begin->next;
delete adr;
}
student *a;
adr=begin;
while (adr->next!=NULL)
{
if (k==adr->next->mark)
{
cout<<adr->next->fio<<" udal \n";
a=adr->next;
adr->next=adr->next->next;
delete a;
}
else adr=adr->next;
}
}
else cout<<"NO spisok";
}
Процедура удаления всего списка очень проста. Текущий указатель устанавливается на голову. Голова перемещается на следующий элемент списка. Память из-под текущего указателя освобождается. Эти действия производятся до тех пор, пока голова не станет равна нулевому указателю. Рассмотрим процедуру удаления списка студентов.
void del()
{
student *adr;
while (begin)
{
adr=begin;
begin=begin->next;
delete adr;
}
cout<<"\nspisok udalen";
}
При сортировке списка элементы не перемещаются в памяти – меняются лишь указатели.Рассмотрим сортировку списка студентов по оценке методом пузырька.
void sort () //
{
if (begin)
{
student *a,*b, *adr;;
bool f;
do
{
f=false;
if (begin->next && begin->mark > begin->next->mark )
{
a=begin->next;
begin->next=begin->next->next;
a->next=begin;
begin=a;
f=true;
}
adr=begin;
while (adr->next && adr->next->next)
{
a=adr->next;
b=adr->next->next;
if (a->mark>b->mark)
{
adr->next=b;
a->next=b->next;
b->next=a;
f=true;
}
adr=adr->next;
}
} while (f);
cout<<"Spisok sorted\n";
}
else cout<<"NO spisok";
}
Контрольные вопросы:
1. За счет чего на языке С реализуются динамические структуры?
2. В чем плюсы динамических структур?
3. В чем минусы динамических структур?
4. Какие динамические структуры вы знаете?
5. Что такое односвязный список?
6. Что такое двусвязный список?
7. Что такое кольцевой список?
8. Что такое очередь?
9. Что такое стек?
10. Можно ли для стека реализовать функцию добавления элемента в конец?
11. Можно ли для очереди написать функцию добавления элемента в конец?
12. Можно ли для стека реализовать функцию удаления элемента равного заданному?
13. Для каких типов списков нельзя реализовать функцию сортировки?
14. Зачем хранить указатель на начало списка?
15. В каких случаях используют динамические структуры?
puts("Файл сохранен!"); //Удачная запись файла
free(array);//Освобождение выделенной динамической памяти
return 0; //Выход
}
/* ------------ Функция загрузки файла --------------------
Параметры: name - имя файла
arr - указатель на массив (по ссылке)
num - число элементов в массиве (по ссылке)
Возвращаемое значение: 0 - успешное завершение
1 - ошибка открытия файла
2 - ошибка выделения памяти
-------------------------------------------------------- */
int LoadFile(const char*name, int **arr, int *num)
{
FILE *file = fopen(name,"rb");//Открытие файла для чтения
if(!file) return 1; //Если открыть не удалось, то выход
//Установка файлового указателя в конец файла
fseek(file,0,SEEK_END);
//Определение числа элементов в файле
int n = ftell(file)/sizeof(int);
//Установка файлового указателя в начало файла
fseek(file,0,SEEK_SET);
//Выделение динамической памяти
int *ptr = (int *)calloc(n,sizeof(int));
//Если память не выделилась, то закрываем файл и выход
if(!ptr) {fclose(file); return 2;}
//Считываем файл в динамически созданный массив
fread(ptr,sizeof(int),n,file);
fclose(file); //Закрываем файл
//Записываем значения размера массива и указателя на
//массив в парамеры, переданные по ссылке
*num = n; *arr = ptr;
return 0; //Выход
}
/* --------------- Функция записи файла ------------------
Параметры: name - имя файла,
arr - указатель на массив,
num - количество элементов
Возвращаемое значение: 0 - успешное завершение
1 - ошибка записи в файл
------------------------------------------------------- */
int SaveFile(const char*name, int *arr, int num)
{
//Открытие файла для записи
FILE *file = fopen(name,"wb");
//Если файл открыть не удалось, то выход
if(!file) return 1;
fwrite(arr,sizeof(int),num,file); //Запись данных в файл
fclose(file); //Зыкрываем файл
return 0; //Выход
}
/* -------- Функции сравнения двух элементов --------------
Параметры: два элемента следующие по порядку
Возвращаемое значение: 1 - необходима перестановка
0 - перестановка не нужна
-------------------------------------------------------- */
int CmpInc(int a,int b) //По возрастанию
{
if(a>b) return 1;
return 0;
}
int CmpDec(int a,int b) //По убыванию
{
if(a<b) return 1;
return 0;
}
/* --------------- Функция сортировки ---------------------
Параметры: arr - указатель на массив элементов,
num - число элементов в массиве,
cmp - указатель на функцию сравнения.
Реализован алгоритм сортировки пузырьком с оптимизацией
-------------------------------------------------------- */
void Sort(int *arr,int num, int (*cmp)(int,int))
{
int last = num;
while(last>0){
int pos = 0;
for(int i=0;i<last-1;i++)
if(cmp(arr[i],arr[i+1])){
int tmp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=tmp;
pos = i+1;
}
last = pos;
}
}
Задача 8.2: Дан бинарный файл, содержащий вещественные числа (тип double). Переписать файл, упорядочив хранящиеся в нем значения. Имя файла и направление сортировки передаются в параметрах командной строки. Направление сортировки передается в формате: dir:inc (по возрастанию) или dir:dec (по убыванию). Алгоритм сортировки реализовать так, чтобы минимизировать объем данных из файла в оперативной памяти.
Программа для задачи
#include <stdio.h>//Библиотека функций ввода и вывода
#include <string.h>//Библиотека функций обработки строк
#include <stdlib.h>//Библиотека стандартных функций
/* -------------- Главная функция main ----------------- */
int main(int argc, char *argv[])
{ //Если параметров меньше трех, то выход из программы
if(argc < 3) {puts("Мало параметров!"); return0;}
char name[50] = ""; //Имя исходного файла
int dir = -1; //Направление сортировки
//Цикл обработки параметров командной строки
for(inti=1;i<argc;i++){
//Преобразование символов строки к нижнему регистру
_strlwr(argv[i]);
//Если это параметр направления сортировки по
//возрастанию, то переменной dir присваиваем - ноль
if(strcmp(argv[i],"dir:inc")==0) dir = 0;
//Если это параметр направления сортировки по
//убыванию, то переменной dir присваиваем - единица
else if(strcmp(argv[i],"dir:dec")==0) dir = 1;
//В противном случае: это имя файла, которое
//копируем в переменную name
elsestrcpy(name,argv[i]);
}
//Если имя файла не найдено в параметрах, то вывод
//сообщения и выход из программы
if(strcmp(name,"")==0)
{puts("Имя файла не указано!"); return 0;}
//Если направление сортировки не найдено, то вывод
//сообщения и выход из программы
if(dir == -1)
{puts("Направление сортировки не указано!"); return 0;}
//Открытие файла для чтения и записи
FILE *file = fopen(name,"rb+");
//Если файл открыть не удалось, то вывод сообщения и
//выход из программы
if(!file) {puts("Невозможно открыть файл!"); return 0;}
//Файловый указатель устанавливаем в конец файла
fseek(file,0,SEEK_END);
//Определяем количество элементов в файле
int size = ftell(file)/sizeof(double);
/* ------------------------------------------------------
Реализован алгоритм поиска максимального или минимального
элемента (в зависимости от направления сортировки)
------------------------------------------------------ */
//Цикл: пока есть не упорядоченные элементы в файле
while(size>0){
//Устанавливаем файловый указатель на начало файла
fseek(file,0,SEEK_SET);
//Индекс ind и значение value найденного максимума
int ind = 0; //(минимума) в файле
double value = 0.0;
//Считываем первое значение в файле
fread(&value,sizeof(double),1,file);
//Цикл по всем не упорядоченным элементам в файле
for(int i=1;i<size;i++){
double cur; //Объявляем локальную переменную
//и считываем в нее следующее значение из файла
fread(&cur,sizeof(double),1,file);
//Если сортировка по возрастанию и найден новый
if(((dir==0)&&(cur>value))|| //максимум
//Если сортировка по убыванию и найден новый
((dir==1)&&(cur<value))){ //минимум
//Сохраняем значение в переменной value и
value = cur; ind = i;//позицию в переменной ind
}
}
//Если найденный максимум (или минимум) находится не
//в конце файла, то осуществляем его перестановку с
if(ind != size-1){//последним рассматриваемым элементом
double tmp; //Локальная переменная
//Установка файлового указателя на последний элемент
fseek(file,(size-1)*sizeof(double),SEEK_SET);
//Считываем значение последнего элемента в tmp
fread(&tmp,sizeof(double),1,file);
//Установка файлового указателя на последний элемент
fseek(file,(size-1)*sizeof(double),SEEK_SET);
//Записываем значение максимума (или минимума)
fwrite(&value,sizeof(double),1,file);
//Установка файлового указателя на позицию максимума
fseek(file,ind*sizeof(double),SEEK_SET); //(минимума)
//Записываем значение из tmp на позицию максимума
fwrite(&tmp,sizeof(double),1,file); //(минимума)
}
size--; //Уменьшаем число рассматриваемых элементов
}
fclose(file); //Закрываем файл
return 0; //Выход
}
Задача 8.3: В текстовом файле содержатся записи с информацией о студентах: фамилия, имя, отчество (строки, максимум 15 символов), номер зачетной книжки (целое шестизначное число), средний балл (целое число от 1 до 10). Каждая запись содержится в отдельной строке, поля разделяются одним или несколькими пробелами. Упорядочить файл по значению одного из полей. Имя файла, поле и направление сортировки указываются в параметрах командной строки. Поле сортировки: SURNAME (фамилия), NAME (имя), PATRONYMIC (отчество), NUMBER (номер зачетной книжки), RATE (средний балл). Направления сортировки: INC - по возрастанию, DEC - по убыванию.
Программа для задачи
#include <stdio.h> //Библиотека функций ввода и вывода
#include <string.h> //Библиотека функций обработки строк
#include <stdlib.h> //Библиотека стандартных функций
typedef struct{ //Объявление структуры
char fio[3][16]; //Поля: фамилия, имя, отчество
int number,rate; //Поля: номер книжки и средний балл
} STUDENT;
//Функция загрузки списка из файла
int LoadList(const char*,STUDENT **,int*);
//Функция записи списка в файл
int SaveList(const char*,STUDENT *,int);
//Функция сортировки
void Sort(STUDENT*,int,int,int);
/* ------------- Главная функция main ------------------ */
intmain(int argc, char *argv[])
{ //Если параметров менее четырех, то вывод сообщения и
if(argc < 4) {puts("Мало параметров!"); return 0;}//выход
char name[50] = ""; //Название файла
int dir = -1, field = -1; //Направление и поле сортировки
//Разбор параметров командной строки
for(int i=1;i<argc;i++){
_strlwr(argv[i]); //Преобразование к нижнему регистру
//Сравнение со всеми ключами и установка значений
if(strcmp(argv[i],"inc")==0) dir = 0;
else if(strcmp(argv[i],"dec")==0) dir = 1;
else if(strcmp(argv[i],"surname") == 0) field = 0;
else if(strcmp(argv[i],"name") == 0) field = 1;
else if(strcmp(argv[i],"patronymic") == 0)
field = 2;
else if(strcmp(argv[i],"number") == 0)
field = 3;
else if(strcmp(argv[i],"rate") == 0)
field = 4;
else strcpy(name,argv[i]);//Имя файла
}
//Если имя файла не указано - вывод сообщения и выход
if(strcmp(name,"")==0)
{puts("Имя файла не указано!"); return 0;}
//Если направление не указано - вывод сообщения и выход
if(dir == -1)
{puts("Направление сортировки не указано!"); return 0;}
//Если поле не указано - вывод сообщения и выход
if(field == -1)
{puts("Поле сортировки не указано!"); return 0;}
STUDENT *list = NULL; //Указатель на список
int num = 0; //Число элементов в списке
//Вызов функции чтения списка из файла
switch(LoadList(name,&list,&num)){
//Если файл не существует или его имя указано неверно
case 1: {puts("Can\'t open file!"); return 0;}
//Если недостаточно динамической памяти для обработки
case 2: {puts("Few memory!"); return 0;}
}
Sort(list,num,field,dir); //Сортировка списка
//Вызов функции записи списка в файл и вывод сообщения
if(SaveList(name,list,num))
puts("Список записать не удалось!");
puts("Список был записан в файл!");
free(list); //Освобождение памяти
return 0; //Выход
}
/* --------- Функция добавления записи в список ----------
Параметры: list - указатель на список (по ссылке)
num - количество записей в списке (по ссылке)
value - значение, добавляемое к списку.
Возвраащемое значение: 1 - успешное завершение
0 - нехватка памяти
------------------------------------------------------- */
int Add(STUDENT **list,int *num, STUDENT value)
{
STUDENT *tmp = //Перевыделение памяти под список
(STUDENT*)realloc(*list,(*num+1)*sizeof(STUDENT));
if(!tmp) return 0; //Если не удалось выделить - выход
tmp[*num] = value; //Записываем новый элемент в список
(*num)++; //Увеличиываем число элементов
*list = tmp; //Сохраняем новое значение указателя
return 1; //Выход
}
/* --------- Функция загрузки списка из файла ------------
Параметры: name - имя файла,
list - указатель на список (по ссылке),
num - число записей в списке (по ссылке)
Возвращаемое значение: 0 - успешное завершение,
1 - файл не найден
2 - не хватает динамической памяти
-------------------------------------------------------- */
int LoadList(const char*name, STUDENT **list, int *num)
{
FILE *file = fopen(name,"r");//Открытие файла для чтения
if(!file) return 1; //Если открыть не удалось, то выход
while(!feof(file)){ //Цикл: пока не конец файла
STUDENT val; //Локальная переменная
int res = 1;
//Считываем строку и заносим в список
if(fscanf(file,"%s %s %s %d %d", //Формат
&val.fio[0],&val.fio[1],&val.fio[2],//ФИО
&val.number, //Номер книжки
&val.rate //Средний балл
)==5) res = Add(list,num,val);
//Если добавить запись в список не удалось, то
if(!res) {fclose(file); return 2;} //выход
}
fclose(file); //Закрытие файла
return 0; //Выход
}
/* --------- Функция записи списка в файл ---------------
Параметры: name - имя файла
list - указатель на список
num - количество записей в списке
Возвращаемое значение: 0 - успешное завершение
1 - ошибка создания файла
------------------------------------------------------ */
int SaveList(const char*name, STUDENT *list, int num)
{
FILE *file = fopen(name,"w"); //Открытие файла для записи
if(!file) return 1; //Если открыть не удалось, то выход
for(int i=0;i<num;i++) //Цикл: запись списка в файл
fprintf(file,"%-15s %-15s %-15s %6d %2d\n",
list[i].fio[0],list[i].fio[1],list[i].fio[2],
list[i].number,list[i].rate);
fclose(file); //Закрытие файла
return 0; //Выход
}
/* ---------- Функция сравнения двух элементов -----------
Параметры: st1, st2 - два элемента для сравнения
field - номер поля, по которому сравниваются
dir - направление сравнения
Вовзращаемое значение: > 0 - больше,
< 0 - меньше,
= 0 - равно
----------------------------------------------------- */
int Cmp(STUDENT st1,STUDENT st2, int field, int dir)
{
if(!dir){ //Если сравнение по возрастанию
//Возвращаем значение в соответствии с номером поля
switch(field){
case 0: return strcmp(st1.fio[0],st2.fio[0]);
case 1: return strcmp(st1.fio[1],st2.fio[1]);
case 2: return strcmp(st1.fio[2],st2.fio[2]);
case 3: return st1.number - st2.number;
case 4: return st1.rate - st2.rate;
}
}else{ //Если сравнение по убыванию
//Возвращаем значение в соответствии с номером поля
switch(field){
case 0: return strcmp(st2.fio[0],st1.fio[0]);
case 1: return strcmp(st2.fio[1],st1.fio[1]);
case 2: return strcmp(st2.fio[2],st1.fio[2]);
case 3: return st2.number - st1.number;
case 4: return st2.rate - st1.rate;
}
}
return 0; //Выход
}
/* ---------- Функция сортировки (внутренняя) ------------
Алгоритм сортировки: быстрый алгоритм Хоара
Параметры: list - указатель на список
iLo, iHi - нижний и верхний индексы
field - номер поля, по которому сравниваются
dir - направление сравнения
-------------------------------------------------------- */
void QuickSort(STUDENT *list, int iLo, int iHi,
int field, int dir)
{
int Lo = iLo, Hi = iHi;
STUDENT mid = list[(Lo+Hi)/2];
do{
while(Cmp(list[Lo],mid,field,dir)<0) Lo++;
while(Cmp(list[Hi],mid,field,dir)>0) Hi--;
if(Lo <= Hi){
STUDENT tmp = list[Lo];
list[Lo] = list[Hi];
list[Hi] = tmp;
Lo++; Hi--;
}
}while(Lo <= Hi);
if(Hi > iLo) QuickSort(list,iLo,Hi,field,dir);
if(Lo < iHi) QuickSort(list,Lo,iHi,field,dir);
}
/* ---------- Функция сортировки (интерфейсная) -----------
Алгоритм сортировки: быстрый алгоритм Хоара
Параметры: list - указатель на список
num - размер списка
field - номер поля, по которому сравниваются
dir - направление сравнения
-------------------------------------------------------- */
void Sort(STUDENT *list,int num, int field, int dir)
{
QuickSort(list,0,num-1,field,dir);
}
Задача 8.4: Дан бинарный файл, содержащий записи об абонентах оператора мобильной связи: фамилия, имя и отчество абонента (строки по 15 символов), номер телефона (целое положительное семизначное число), дата подключения (дд.мм.гггг). Программа должна по запросу пользователя найти всех абонентов подключившихся за определенный период (вводится как две даты). Все найденные записи выводятся на экран, а затем, по требованию пользователя, сохраняются в файл (имя файла вводит пользователь). Записи выводятся в хронологическом порядке. Имя исходного файла передается в параметрах командной строки.
Программа для задачи
#include <stdio.h>//Библиотека функций ввода и вывода
#include <string.h>//Библиотека функций обработки строк
#include <stdlib.h>//Библиотека стандартных функций
typedef struct{//Описание структуры для хранения даты
unsigned dd:5,mm:4,yy:14;//с использованием битовых полей
} DATE;
typedef struct{ //Описание структуры для хранения
char fio[3][16]; //информации об абоненте
int number;
DATE date;
} ABONENT;
//Функция загрузки списка из файла
int LoadList(const char*,ABONENT **,int*);
void Sort(ABONENT*,int); //Функция сортировки
void Search(ABONENT *,int,DATE,DATE);//Функция поиска
int InputDate(DATE *); //Функция ввода даты
int CmpDate(DATE,DATE); //Функция сранения дат
/* ---------- Главная функция программы main ----------- */
int main(int argc, char *argv[])
{
//Если имя исходного файла не указано, то выход
if(argc < 2) {puts("Не указано имя файла!"); return 0;}
ABONENT *list = NULL; //Указатель на список записей
int num = 0; //Количество записей в списке
//Вызов функции загрузки списка и анализ ее результата
switch(LoadList(argv[1],&list,&num)){
case 1: {puts("Невозможно открыть файл!"); return 0;}
case 2: {puts("Недостаточно памяти!"); return 0;}
}
Sort(list,num); //Сортировка списка по дате
DATE date_from, date_to; //Переменные для хранения дат
do{ //Ввод дат с которой и по какую осуществлять поиск
do //Ввод даты с которой осуществляется поиск
printf("Начальная дата: ");//с проверкой корректного
while(InputDate(&date_from)); //ввода
do //Ввод даты по которую осуществляется поиск
printf("Конечная дата: ");//с проверкой корректного
while(InputDate(&date_to)); //ввода
//Если даты введены в хронологическом порядке, то выход
if(CmpDate(date_from,date_to) <= 0) break; //из цикла
puts("Даты введены некорректно!");//Сообщение об ошибке
}while(1);
Search(list,num,date_from,date_to); //Поиск в списке
free(list); //Удаление списка
return 0; //Выход
}
/* ------------ Функция загрузки списка -------------------
Параметры: name - имя файла,
list - указатель на список (по ссылке),
num - количество записей в списке (по ссылке)
Возвращаемое значение: 0 - успешное завершение,
1 - некорректное имя файла
2 - нехватка динамической памяти
-------------------------------------------------------- */
int LoadList(const char*name, ABONENT **list, int *num)
{
FILE *file = fopen(name,"rb"); //Открытие файла
if(!file) return 1; //Если открыть не удалось, то выход
fseek(file,0,SEEK_END); //Переход в конец файла
//Определение количества записей в файле
int cnt = ftell(file)/sizeof(ABONENT);
fseek(file,0,SEEK_SET); //Переход в начало файла
//Выделение динамической памяти под список
ABONENT *tmp = (ABONENT *)calloc(cnt,sizeof(ABONENT));
//Если память не выделилась, то выход
if(!tmp) {fclose(file); return 2;}
fread(tmp,sizeof(ABONENT),cnt,file); //Считывание даных
fclose(file); //Закрытие файла
*list = tmp; *num = cnt; //Установка переменных по ссылке
return 0; //Выход
}
/* --------- Функция поиска одной записи в списке ---------
Параметры: list - указатель на список,
num - количество записей в списке,
start - номер записи, с которой начинать поиск,
date_from - левая граница временного промежутка,
date_to - правая граница временного промежутка
Возвращаемое значение: -1 - запись не найдена,
≥0 - номер записи в списке.
Реализован алгоритм линейного поиска.
-------------------------------------------------------- */
int Find(ABONENT *list, int num, int start,
DATE date_from, DATE date_to)
{
for(int i=start;i<num;i++)
if((CmpDate(list[i].date,date_from)>=0)&&
(CmpDate(list[i].date,date_to)<=0)) return i;
return -1;
}
/* --------- Функция поиска всех записей в списке ---------
Параметры: list - указатель на список,
num - количество записей в списке,
start - номер записи, с которой начинать поиск,
date_from - левая граница временного промежутка,
date_to - правая граница временного промежутка
-------------------------------------------------------- */
void Search(ABONENT *list, int num, DATE date_from,
DATE date_to)
{
char fname[50] = ""; //Имя файла для отчета
for(int i=0;i<2;i++){//Цикл на две итерации
FILE *file = stdout; //Установка на стандартный вывод
//Если это вторая итерация, то вывод в файл
if(i == 1) file=fopen(fname,"w");
//Если открыть файл не удалось, то выход
if(!file) {puts("Невозможно создать файл!"); return;}
int ind = -1; //Индекс найденной записи
//Поиск записей в цикле, выход - если запись не найдена
while((ind=Find(list,num,ind+1,date_from,date_to))!=-1)
//Вывод найденной записи
fprintf(file,"%-15s %-15s %-15s %7u %2u.%2u.%4u\n",
list[ind].fio[0], list[ind].fio[1],
list[ind].fio[2], list[ind].number,
list[ind].date.dd, list[ind].date.mm,
list[ind].date.yy
);
char ch = 'n'; //Символ для диалога с пользователем
while(i==0){//Если это первая итерация
//Вопрос пользователю
printf("Сохранить файл? (y/n): ");
//Очистка буфера ввода и ввод символа
fflush(stdin); scanf("%c",&ch);
//Если ответ положительный
if((ch == 'y')||(ch == 'Y')){
printf("Имя файла: ");//Приглашение к вводу
scanf("%s",fname); //и ввод имени файла
break; //Выход из вложенного цикла
}
//Если ответ отрицательный, то выход
if((ch == 'n')||(ch == 'N')) return;
}
}
}
/* ---- Функция ввода даты и проверки ее корректности -----
Параметр: date - структура дата, в которую осуществляется
ввод (по ссылке)
Возвращаемое значение: 0 - дата введена корректно
1 - дата введена не корректно
-------------------------------------------------------- */
int InputDate(DATE *date)
{
unsignedday,mon,year; //Локальные переменные
//Ввод значения в формате дд.мм.гггг.
//Если ввод некорректный, то выход со значением 1
if(scanf("%u.%u.%u",&day,&mon,&year) != 3) return 1;
//Проверка корректности введенных значений
if((day<1)||(day>31)||(mon<1)||(mon>12)||(year<1))
return 1;
//Проверка корректности ввода числа для месяцев, в
//которых 30 дней и для февраля с учетом високосного года
switch(mon){
case 4: case 6: case 9: case 11:
if(day>30) return 1; else break;
case 2: if(( (year%4)&&(day>28))||
(!(year%4)&&(day>29))) return 1;
}
//Запись значений в структуру
date->dd = day; date->mm = mon; date->yy = year;
return 0; //Выход
}
/* ------------- Функция сравнения двух дат ---------------
Параметр: dt1 - первая дата,
dt2 - вторая дата
Возвращаемое значение: 0 - даты равны,
1 - первая дата «больше»,
-1 - вторая дата «больше»
-------------------------------------------------------- */
int CmpDate(DATE dt1, DATE dt2)
{
if(dt1.yy > dt2.yy) return 1;
else if(dt1.yy < dt2.yy) return -1;
if(dt1.mm > dt2.mm) return 1;
else if(dt1.mm < dt2.mm) return -1;
if(dt1.dd > dt2.dd) return 1;
else if(dt1.dd < dt2.dd) return -1;
return 0;
}
/* ------- Функция сортировки списка (внутренняя) ---------
Параметр: list - указатель на список,
iLo - нижний индекс,
iHi - верхний индекс.
Реализует алгоритм Хоара
-------------------------------------------------------- */
void QuickSort(ABONENT *list, int iLo, int iHi)
{
int Lo = iLo, Hi = iHi;
ABONENT mid = list[(Lo+Hi)/2];
do{
while(CmpDate(list[Lo].date,mid.date)<0) Lo++;
while(CmpDate(list[Hi].date,mid.date)>0) Hi--;
if(Lo <= Hi){
ABONENT tmp = list[Lo];
list[Lo] = list[Hi];
list[Hi] = tmp;
Lo++; Hi--;
}
}while(Lo <= Hi);
if(Hi > iLo) QuickSort(list,iLo,Hi);
if(Lo < iHi) QuickSort(list,Lo,iHi);
}
/* -------- Функция сортировки списка (внешняя) -----------
Параметр: list - указатель на список,
num - количество элементов в списке
-------------------------------------------------------- */
void Sort(ABONENT *list,int num)
{
QuickSort(list,0,num-1);
}
Задача 8.5: Дан бинарный файл, содержащий записи об абонентах оператора мобильной связи: фамилия, имя и отчество абонента (строки по 15 символов), номер телефона (целое положительное семизначное число), дата подключения (дд.мм.гггг). Программа должна по запросу пользователя (водит номер телефона) найти абонента с этим номером и вывести его ФИО и дату подключения. Программа должна работать в интерактивном режиме: после вывода найденной информации переходить к новому запросу. Выход из программы - ввод слова exit. При реализации программы использовать библиотечные функции сортировки и поиска. Имя исходного файла передается в параметрах командной строки.
Программа для задачи
#include <stdio.h>//Библиотека функций ввода и вывода
#include <string.h> //Библиотека функций обработки строк
#include <stdlib.h> //Библиотека стандартных функций
typedef struct{//Описание структуры для хранения даты
unsigned dd:5,mm:4,yy:14;//с использованием битовых полей
} DATE;
typedef struct{//Описание структуры для хранения
char fio[3][16]; //информации об абоненте
int number;
DATE date;
} ABONENT;
//Функция загрузки списка из бинарного файла
int LoadList(const char*,ABONENT **,int*);
//Функция сравнения двух записей
int Cmp(const void*,const void*);
/* -------- Главная функция программы main ------------- */
int main(int argc, char *argv[])
{
//Если имя исходного файла не указано, то выход
if(argc < 2) {puts("Имя файла не указано!"); return 0;}
ABONENT *list = NULL; //Указатель на список записей
int num = 0; //Количесвто записей в списке
//Вызов функции загрузки списка и разбор ее значения
switch(LoadList(argv[1],&list,&num)){
case 1: {puts("Невозможно открыть файл!"); return0;}
case 2: {puts("Недостаточно памяти!"); return 0;}
}
qsort(list,num,sizeof(ABONENT),Cmp);//Сортировка списка
while(1){ //Цикл интерактивного режима работы
char str[100]; //Буфер ввода
printf(">:"); //Приглашение к вводу
gets(str); //Ввод строки
//Если введено слово «exit», то выход из цикла
if(strncmp(str,"exit",4) == 0) break;
ABONENT key = {{"","",""},0,{0,0,0}};//Ключ для поиска
//Преобразование запрашиваемого номера из
key.number = atoi(str); //введенной строки
//Проверка корректности ввода телефонного номера
if((key.number < 1000000)||(key.number > 9999999)){
puts("Телефонный номер введен неправильно!");
continue; //Переход к следующей итерации
}
//Поиск записи в списке по введенному номеру
ABONENT *ptr =
(ABONENT *)bsearch(&key,list,num,sizeof(ABONENT),Cmp);
//Если запись не найдена, то выводим сообщение
if(!ptr) puts("Не найдено!");
//Иначе: выводим на экран найденную запись
else printf("%-15s %-15s %-15s %7u %2u.%2u.%4u\n",
ptr->fio[0], ptr->fio[1], ptr->fio[2],
ptr->number,
ptr->date.dd, ptr->date.mm, ptr->date.yy);
}
free(list); //Удаление списка
return 0; //Выход
}
/* ------------ Функция загрузки списка -------------------
Описание и комментарии в предыдущем примере
-------------------------------------------------------- */
int LoadList(const char*name, ABONENT **list,int*num)
{
FILE *file = fopen(name,"rb");
if(!file) return 1;
fseek(file,0,SEEK_END);
int cnt = ftell(file)/sizeof(ABONENT);
fseek(file,0,SEEK_SET);
ABONENT *tmp = (ABONENT *)calloc(cnt,sizeof(ABONENT));
if(!tmp) {fclose(file); return 2;}
fread(tmp,sizeof(ABONENT),cnt,file);
fclose(file);
*list = tmp; *num = cnt;
return 0;
}
/* ----------- Функция сравнения двух записей -------------
Параметр: el1 - указатель на первую запись,
el2 - указатель на вторую запись
Возвращаемое значение:
0 - телефонные номера равны,
1 - телефонный номер перой записи «больше»,
-1 - телефонный номер второй записи «больше»,
-------------------------------------------------------- */
int Cmp(const void*el1, const void*el2)
{
ABONENT *ptr1 = (ABONENT *)el1, *ptr2 = (ABONENT *)el2;
if(ptr1->number > ptr2->number) return 1;
else if(ptr1->number < ptr2->number) return -1;
return 0;
}
//
#include "franca.h"
#include "Func_header.h"
athlete Sal, Sally;
void mainprog()
{
JmpJack(Sal, Sally);
JmpJack(Sal, Sally);
}
Т. ч. перед тим, як компілятор почне|зачинатиме| транслювати вашу програму на машинну мову|язик|, копія запрошуваної програми з'явиться|появлятиметься| там, де знаходиться|перебуває| директива #include. Файл, який необхідно|треба| включити в програму, повинен знаходитися|перебувати| в тому ж каталозі, що і ваша програма. Якщо це не так, треба вказати повний|цілковитий| шлях|дорогу| до файлу:
#include "c:\franca\franca.h"
Якщо необхідно|треба| включити файли, що знаходяться|перебувають| в каталогах компілятора потрібне|необхідне| ім'я файлу укласти в кутові дужки.
Наприклад:
#include <math.h>;
#include <iostream. h>;
Зона видимості
Зона видимості дозволяє вводити|запроваджувати| різні об'єкти з|із| однаковими іменами за умови, що|при умові , що| вони знаходяться|перебувають| в різних зонах видимості.
1. Глобальний об'єкт - це об'єкт визначений поза|зовні| усіма функціями і доступний для усіх функцій, визначених після нього|т.
