Однако, обработка односвязного списка не всегда удобна, так как существует возможность перемещения по списку лишь в одну сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двусвязного списка приведена на рисунке 2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать NULL, как и показано на рисунке.
Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка. Наличие двух указателей в каждом элементе усложняет список и приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых операций над списком.
NULL
NEXT
INF
PREV
NULL
INF
PREV
NEXT
INF
Голова списка
Указатель конца
Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двусвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двусвязном списке в первом и последнем элементах соответствующие указатели переопределяются, как показано на рисунке 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; //Выход
}
/* ------------ Функция загрузки файла --------------------
Задача 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+");
//Если файл открыть не удалось, то вывод сообщения и
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[])
{ //Если параметров менее четырех, то вывод сообщения и
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;//с использованием битовых полей
Задача 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;}
· Интерфейс определяет поведение объекта и содержит описание поддерживаемых членов. Ими могут быть методы, свойства и события.
· Объект, реализующий некоторый интерфейс, может взаимодействовать с любым другим объектом, которому необходим этот интерфейс.
· За реализацию членов интерфейса отвечает класс или структура, в которой этот интерфейс реализован. В классах, как и в структурах, допускается реализация нескольких интерфейсов.
· Класс или структура, реализующая некоторый интерфейс, должна обеспечить реализацию всех членов, объявленных в этом интерфейсе.
· В С# члены интерфейса реализуются двумя способами:
ü реализация члена с именем, сигнатурой и уровнем доступа, идентичными соответствующему члену интерфейса. Такие члены доступны как через реализующий класс, так и через интерфейс;
ü явная реализация члена интерфейса с указанием его полного имени. Такие члены доступны только через интерфейс.
YouTube ([ˈjuːtjuːb] — ю-тьюб) — сервис, предоставляющий услуги хостинга видеоматериалов. Пользователи могут добавлять, просматривать и комментировать те или иные видеозаписи. Благодаря простоте и удобству использования, YouTube стал популярнейшим видеохостингом и третьим сайтом в мире по количеству посетителей[. Ежедневное количество просмотров видео на сайте составляет более 2 миллиардов. На сайте представлены как профессионально снятые фильмы и клипы, так и любительские видеозаписи, включая видеоблоги.
Проект был основан в феврале 2005 года тремя бывшими работниками PayPal в Сан-Бруно, Калифорния. Они использовали технологию Flash Video (flv), позволяющую получить относительно хорошее качество записи при небольшом объёме передаваемых данных. Проект стал хорошим средством развлечения, и, сформировав своё сообщество, по данным статистики аналитической компании Alexa, опередил по популярности социальную сеть MySpace.
В ноябре 2006 года была завершена покупка YouTube компанией Google за 1,65 миллиарда долларов[3]. До покупки YouTube у Google был сервис схожей направленности — Google Video. Представители Google не намереваются закрывать его, а будут использовать его как место поиска видео по всем видеохостинговым сайтам. В настоящее время поиск Google Video включает и YouTube.Самое первое видео — 18-секундный ролик любительской съёмки в зоопарке Сан-Диего — на YouTube было размещено 23 апреля 2005 года[4].
