Домены верхнего уровня

128.29.15.124

193.126.7.29

ЛЕКЦИЯ

Рис 3. Структура кольцевого двухсвязного списка

Рисунок 2. Структура двусвязного списка

Рисунок 1. Структура односвязного списка

Линейные списки

Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент ссылался на следующий. Такую динамическую структуру называют однонаправленным (односвязным) линейным списком.

Однако, обработка односвязного списка не всегда удобна, так как существует возможность перемещения по списку лишь в одну сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двусвязного списка приведена на рисунке 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. В каких случаях используют динамические структуры?

Тема: Глобальная сеть. Адресация и протоколы

План:

1. Аппаратные средства работы в глобальных сетях

2. Структура адресации в сети Интернет

3. Программные средства работы в глобальных сетях

4. Организация работы в Интернете

1. Аппаратные средства работы в глобальных сетях

К аппаратным средствам работы в сетях относятся:

• линии связи (кабели, радиосвязь, спутниковая связь);

• сетевые карты;

• модемы;

• серверы — компьютеры, выделенные для управления сетевыми ресурсами — сервер печати для управления принтером, коммуникационный сервер для связи с модемами, файловый сервер, которому в сети принадлежит центральная роль.

К узлам компьютерной сети подключаются персональные компьютеры пользователей подобно тому, как с телефонны­ми станциями соединяются телефоны абонентов. Причем в роли абонента компьютерной сети может выступать как от­дельный человек через свой ПК, так и целая организация через свою локальную сеть. В последнем случае к узлу под­ключается файл-сервер локальной сети.

Через компьютерную сеть абоненты получают определен­ные информационные услуги. Организация-поставщик таких услуг называется провайдером. Английское слово provider переводится как «поставщик», «снабженец». Пользователь заключает договор с провайдером и в дальнейшем оплачивает ему предоставляемые услуги (подобно тому, как мы оплачи­ваем услуги телефонной сети).

В распоряжении провайдера имеется один или несколько мощных компьютеров, которые находятся в состоянии по­стоянного подключения к сети. Они называются хост-ком­пьютерами (англ. host - хозяин).

Каждый хост-компьютер имеет свой постоянный адрес, который отличает его от всех других компьютеров в Интернете; он называется IP-адресом.

IP-адрес состоит из четырех десятичных чисел, каждое в диапазоне от 0 до 255, которые записываются через точку.

Пример:

Обычно первый и второй байты определяют адрес сети, третий байт определяет адресподсети, а четвертый — адрескомпьютера в подсети.

Такие же IP-адреса получают и компьютеры пользовате­лей Сети, но они называются временными адресами (дейст­вуют лишь во время подключения пользователя к сети и из­меняются в каждом новом сеансе связи), в то время как адреса хост-компьютеров остаются неизменными.

Наряду с цифровыми IP-адресами в Интернете действует система символьных адресов, более удобная и понятная для пользователей. Она называется доменной системой имен (DNS — Domain Name Sistem).

Каждый IP-адрес имеет соответствующее доменное имя.

Домен — самая крупная структурная единица Интернета, группа ресурсов, управляемых из одного центра или узла.

Например, IР-адресу 195.34.32.11 сервера компании «МТУ-Интел» соответствует доменное имяdialup.mtu.ru.Данное имя состоит из трех доменов, разделенных точками. В Интернете действует специальная адресная служба, кото­рая занимается выделением IР-адресов компьютерам, под­ключаемым к Сети, и назначением им доменных имен.

Слово «домен» обозначает участок, зону. Система домен­ных имен построена по иерархическому принципу. Первый справа домен (его еще называют суффиксом) — домен верх­него уровня, следующий за ним — домен второго уровня и так далее. Последний (первый слева) домен — имя компью­тера.

Домены верхнего уровня бывают географическими (двухбуквенными) или административными (трехбуквенны­ми - чаще всего относятся к американской зоне Интернета). Каждый домен верхнего уровня получает имя, которое регистрируется в координирующем органе Интернет-организации ISOC (www.isoc.org) и закрепляется за соответствующей сетью, организацией или страной на постоянной основе (см. табл. 1)

Таблица 1

В свою очередь, каждый домен верхнего уровня может включать в себя домены нижнего уровня (региональные или городские сети), например: spb — Санкт-Петербург, msk — Москва.

2. Структура адресации в сети Интернет

Таким образом, организация доменной адресации компьютеров является иерархической системой и по своей структуре во многом напоминает файловую структуру на дисках ПК. Доменное имя состоит из нескольких частей, расположенных в определенном порядке и разделенных точками. На рис. 1 приведен пример доменного имени.

Рис. 1. Структура доменного имени

Связь доменного имени с IP-адресом осуществляется с помощью специальной службы DNS, которая переводит имена доменов в связанные с ними IP-адреса. DNS поддерживает список доменных имен компьютеров и соответствующих им IP-адресов. Доменные имена применяются только для серверов, предоставляющих услуги или ресурсы и имеющих постоянное подключение к сети Интернет.

Имя сети — это имя, которое организация или физическое лицо выбирает для системы (компьютерная сеть или отдельный компьютер) самостоятельно и регистрирует его в той организации, которая обеспечивает подключение. Это имя обычно созвучно с названием организации и должно быть уникальным в пределах домена верхнего уровня. В примере (см. рис. 1) «nha» — это аббревиатура организации, которая называется «Нефтехимавтоматика».

3. Программные средства

Сеть нуждается в соответствующем программном обеспечении, управляющем потоком данных.

Это ПО функционирует на хост-компьютерах и на персо­нальных компьютерах пользователей.

Прежде всего режимы работы в сети должна поддерживать операционная система. Наиболее распространенные сетевые операционные системы — Microsoft Windows NT, OS/2, Warp Connect, Unix, Solaris, Novell NetWare.

Коммуникационные программы поддерживают сетевые протоколы, то есть соглашения о правилах обмена данными по сетям.

Браузеры (Browser) — программы, обеспечивающие взаимодействие с пользователем посредством графического интерфейса и транслирующие его указания в команды, понятные компьютерам и сетевым протоколам (Navigator — NetScape Communication, Spry Mosaic, Internet Explorer и др.).

Программное обеспечение хост-компьютеров очень разно­образно. Условно его можно разделить на базовое (систем­ное) и прикладное.

Базовое ПО обеспечивает поддержку ра­боты сети по протоколу ТСР/IР — базовому протоколу Интернета, то есть оно решает проблемы рассылки и приема информации.

Прикладное ПО занимается обслуживанием разнообразных информационных услуг Сети, которые при­нято называть службами Интернета. Такие программы на­зываются серверами. Для каждой службы существует своя сервер-программа: для электронной почты, для телеконфе­ренций, для WWW и пр.

Часто под словом «сервер» понимают хост-компьютер.

Хост-компьютер выполняет функцию сервера определен­ной службы Интернета, если на нем работает сервер-про­грамма этой службы. Один и тот же компьютер в разное время может выполнять функции сервера различных услуг; все зависит от того, какая сервер-программа на нем в дан­ный момент выполняется. На ПК пользователей сети об­служиванием различных информационных услуг занима­ются клиент-программы.

Примерами популярных программ являются: Outlook Express — клиент электронной почты, Internet Explorer — клиент службы WWW (браузер). Во время работы пользователя с определенной службой Интернета между его клиент-програм­мой и соответствующей сервер-программой устанавливается связь. Каждая из этих программ выполняет свою часть работы в предоставлении данной информационной услуги. Такой спо­соб работы Сети называется технологией «клиент-сервер».

Огромное количество информационных ресурсов размещено в настоящее время в глобальной сети Интернет. Интернет не является отдельной сетью: на самом деле это объединение многих региональных и локальных сетей. Именно поэтому Интернет часто называют «сетью сетей». Если вы подключены к какой-либо сети, являющейся частью Интернета, то имеете доступ к ресурсам любого из компьютеров, входящих в неё.

Основные средства обмена информацией в глобальных сетях (сетевые услуги):

· электронные доски объявлений (Bulletin Board System, или BBS);

· электронная почта (e-mail);

· телеконференции;

· обмен файлами между компьютерами (протокол обмена файлами называется File Transfer Protocol — FTP);

· параллельные беседы в Интернете (Internet Relay Chat, или IRC);

· поисковые системы «Всемирной паутины» (World Wide Web, или WWW).

4. Организация работы в Интернете

В Интернете используется пакетная технология переда­чи информации. Чтобы в этом лучше разобраться, пред­ставьте себе следующую ситуацию. Вам нужно переслать то­варищу в другой город какой-то многостраничный документ (например, распечатку романа). Полностью в конверт весь роман не помещается, а посылать бандеролью вы не хоти­те — слишком долго будет идти. Тогда вы делите весь доку­мент на части по 4 листа, вкладываете каждую часть в поч­товый конверт, на каждом конверте пишете адрес, и всю эту пачку конвертов кидаете в почтовый ящик. Например, если ваш роман занимает 100 страниц, то вам придется отпра­вить 25 конвертов. Вы даже можете опустить конверты в разные почтовые ящики на разных узлах связи (для интере­са, чтобы узнать, какие дойдут быстрее). Но поскольку на них указан один и тот же адрес, то все конверты должны дойти до вашего товарища. А еще, чтобы товарищу было удобно собрать роман целиком, на конвертах желательно указать порядковые номера.

Аналогично работает пакетная передача информации в Интернете. За ее работу отвечает протокол ТСР/IР, о кото­ром уже говорилось раньше. Пора разобраться, что же обо­значают эти загадочные буквы.

Фактически речь идет о двух протоколах. Первый — ТСР — расшифровывается так: Transfer Control Protocol — протокол управления передачей. Именно согласно этому протоколу, всякое сообщение, которое нужно передать по Сети, разбивается на части. Эти части называются ТСР-пакетами. К каждому пакету прилагается IР-адрес его достав­ки и еще некоторая служебная информация. Таким образом, ТСР-пакет — это аналог конверта с «кусочком» романа и адресом получателя. Каждый такой пакет будет самостоя­тельно перемещаться по сети независимо от других, но все они вместе соберутся у адресата. Далее, согласно протоколу ТСР, происходит обратный процесс: из отдельных пакетов собирается исходное сообщение. Здесь, очевидно, необходи­мы те самые порядковые номера на конвертах; аналогичные номера содержатся и в ТСР-пакетах. Если какой-то из паке­тов не дошел или был испорчен при транспортировке, его передача будет запрошена повторно.

Согласно протоколу ТСР, передаваемое сообщение разби­вается на пакеты на отправляющем сервере и восстанавливается в исходном виде на принимающем сервере.

Назначение IР-протокола (Internet Protocol) — достав­ка каждого отдельного пакета до места назначения.

Пакеты передаются как эстафетные палочки от одного узла к другому. Причем маршруты для разных пакетов из одного и того же сообщения могут оказаться разными. Опи­санный механизм передачи пакетов отображен на рис. 2. Вопрос о маршруте решается отдельно для каждого пакета. Все зависит от того, куда его выгоднее передать в момент обработки. Если на каком-то участке Сети произошел «об­рыв», то передача пакетов пойдет в обход этого участка.

Таким образом, в любой момент времени по любому каналу Сети перемещается «вперемешку» множество пакетов из самых разных сообщений. Использование всякого канала связи стоит денег: междугородние, а тем более, междуна­родные телефонные разговоры достаточно дороги. Если бы, работая в Сети, вы в течение всего сеанса связи монопольно занимали международный канал, то расходы вас быстро бы разорили. Однако, согласно описанной технологии, канал вы делите с сотнями (а может — тысячами) других пользо­вателей, и поэтому на вашу долю приходится лишь неболь­шая часть расходов.

Рис.2. Механизм передачи пакетов

Для работы прикладных программ, таких, как программы электронной почты, требуется не только правильно упаковать информацию в пакеты и отправить их, но и четко договориться о содержимом этих пакетов, а также о процедуре обмена пакетами. Так, например, для получения письма необхрдимо предъявить пароль обладателя почтового ящика, а это уже целая последовательность действий. Таким образом, необходимы и другие протоколы.

ЗНАТЬ

Аппаратные средстваработы в сетях:

• линии связи (кабели, радиосвязь, спутниковая связь);

• сетевые карты;

• модемы;

• серверы — компьютеры, выделенные для управления сетевыми ресурсами.

Программные средстваработы в сетях:

• операционная система, поддерживающая режимы работы в сети;

• коммуникационные программы, поддерживающие сетевые протоколы.

В Интернете используется пакетный принцип передачи и обработки сетевой информации.

Сетевые протоколы— соглашения о правилах обмена данными по сетям.

Назначение протокола ТСР — разбивка сообщения на па­кеты и сборка из пакетов исходного сообщения в конечном пункте передачи.

Назначение протокола IР — передача пакетов по Сети.

Пакетная технология обеспечивает устойчивость инфор­мационных потоков в Сети и относительно низкую стои­мость ее эксплуатации для пользователей.

Браузеры— программы, обеспечивающие взаимодействие с пользователем и транслирующие его указания вкоманды, понятные компьютерам сети и соответствующие сетевым протоколам.

Основные средства обмена информациейв глобальных сетях (сетевые услуги):

• электронные доски объявлений (Bulletin Board System, или BBS);

• электронная почта (e-mail);

• телеконференции, или группы новостей (NewsGroup);

• обмен файлами между компьютерами (протокол FTP);

• параллельные беседы в Интернете (Internet Relay Chat, или IRC);

• поисковые системы «Всемирной паутины» (World Wide Web, или WWW).

Провайдер — это организация-поставщик сетевых инфор­мационных услуг.

Хост-машина — компьютер, постоянно подключенный к сети, предназначенный для реализации информационных услуг.

Основной принцип организации программного обеспече­ния работы служб Интернета реализуется на базе технологии «клиент-сервер». Сервер-программа работает на хост-компь­ютере, клиент-программа — на ПК пользователя. Во время сеанса связи они взаимодействуют между собой.

Контрольные вопросы

1. Что такое домен?

2. Чем отличается хост-компьютер от ПК пользователя сети? Обо­значьте разницу по следующим позициям: назначение, режим работы, программное обеспечение.

3. Что обозначает слово «сервер» в сетевых технологиях?

4. Что такое IР-адрес и доменный адрес?

5. Как проявляется технология «клиент—сервер» в организации работы сети?

6. Объясните, почему пакетный принцип передачи информации способствует повышению надежности работы Сети.

7. В чем разница назначения протоколов ТСР и IР?

8. Объясните, почему международная связь по сети Интернет де­шевле телефонной или телеграфной связи.