Работа с двунаправленным списком

 

Рис. 6 Двунаправленный список

 

Пример 3.

1. Создать двунаправленный список, выполнить удаление элемента с заданным номером, добавление элемента с заданным номером, печать полученных списков.

#include <iostream.h>

struct point//описание структуры

{

       int key;//ключевое поле

       point* pred,*next;//адресные поля

};

point*make_list()

{

       int n;

       cout<<"n-?";cin>>n;

       point *p,*r,*beg;

       p=new (point);//создать первый элемент

       beg=p;//запомнить адрес в переменную beg, в которой хранится начало списка

       cout<<"key-?";cin>>p->key;//заполнить ключевое поле

       p->pred=0;p->next=0;//запомнить адресные поля

       for(int i=1;i<n;i++)//добавить элементы в конец списка

       {

                   r=new(point);//новый элемент

                   cout<<"key-?";cin>>r->key;//адресное поле

                   p->next=r;//связать начало списка с r

                   r->pred=p;//связать r с началом списка

                   r->next=0;//обнулить последнее адресное поле

                   p=r;//передвинуть p на последний элемент списка

       }

       return beg;//вернуть первый элемент списка

}

void print_list(point *beg)

{

       if (beg==0)//если список пустой

       {

cout<<"The list is empty\n";

 return;

 }

       point*p=beg;

       while(p)//пока не конец списка

       {

                   cout<<p->key<<"\t";

                   p=p->next;//перейти на следующий

       }

       cout<<"\n";

}

point* del_point(point*beg, int k)

{

       point *p=beg;

       if(k==0)//удалить первый элемент

       {

                   beg=beg->next;//переставить начало списка на следующий элемент

                   if(beg==0)return 0;//если в списке только один элемент

                   beg->pred=0;//обнулить адрес предыдущего элемента

                   delete p;//удалить первый

                   return beg;//вернуть начало списка

       }

//если удаляется элемент из середины списка

       for(int i=0;i<k-1&&p!=0;i++,p=p->next);//пройти по списку либо до элемента с предыдущим номером, либо до конца списка

       if(p==0||p->next==0)return beg;//если в списке нет элемента с номером k

       point*r=p->next;//встать на удаляемый элемент

       p->next=r->next;//изменить ссылку

       delete r;//удалить r

       r=p->next;//встать на следующий

       if(r!=0)r->pred=p;//если r существует, то связать элементы

       return beg;//вернуть начало списка

}

point* add_point(point *beg,int k)

{

       point *p;

       p=new(point);//создать новый элемент и заполнить ключевое поле

       cout<<"key-?";cin>>p->key;

       if(k==0)//если добавляется первый элемент

       {

                   p->next=beg;//добавить перед beg

                   p->pred=0;//обнулить адрес предыдущего

                   beg->pred=p;//связать список с добавленным элементом

                   beg=p;//запомнить первый элемент в beg

                   return beg;//вернуть начало списка

       }

                   point*r=beg;//встать на начало списка

       for(int i=0;i<k-1&&r->next!=0;i++,r=r->next);//пройти по списку либо до конца списка, либо до элемента с номером k-1

       p->next=r->next;//связать р с концом списка

       if(r->next!=0)r->next->pred=p;//если элемент не последний, то связать конец списка с р

       p->pred=r;//связать р и r

       r->next=p;

       return beg;//вернуть начало списка

}

           

 

void main()

{

       point*beg;

int i,k;

do

{

       cout<<"1.Make list\n";

       cout<<"2.Print list\n";

       cout<<"3.Add point\n";

       cout<<"4.Del point\n";

       cout<<"5.Exit\n";

cin>>i;

       switch(i)

       {

       case 1:

                   {beg=make_list();break;}

       case 2:

                   {print_list(beg);break;}

       case 3:

                   {

                              cout<<"\nk-?";cin>>k;

                              beg=add_point(beg,k);

                              break;

                   }

       case 4:

                   {

                              cout<<"\nk-?";cin>>k;

                              beg=del_point(beg,k);

                              break;

                   }

       }

}

while(i!=5);

}

Ввод-вывод в С

Файл – это именованная область внешней памяти. Файл имеет следующие характерные особенности:

1. имеет имя на диске, что дает возможность программам работать с несколькими файлами;

2. длина файла ограничивается только емкостью диска.

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

Библиотека С поддерживает три уровня ввода-вывода:

- потоковый ввод-вывод;

- ввод-вывод нижнего уровня;

- ввод-вывод для консоли портов (зависит от конкретной ОС).

Рассмотрим потоковый ввод-вывод.

Потоковый ввод-вывод

На уровне потокового ввода-вывода обмен данными производится побайтно, т. е. за одно обращение к устройству (файлу) производится считывание или запись фиксированной порции данных (512 или 1024 байта). При вводе с диска или при считывании из файла данные помещаются в буфер ОС, а затем побайтно или порциями передаются программе пользователя. При выводе в файл данные также накапливаются в буфере, а при заполнении буфера записываются в виде единого блока на диск. Буферы ОС реализуются в виде участков основной памяти. Т.о. поток – это файл вместе с предоставленными средствами буферизации. Функции библиотеки С, поддерживающие обмен данными на уровне потока позволяют обрабатывать данные различных размеров и форматов. При работе с потоком можно:

1. Открывать и закрывать потоки (при этом указатели на поток связываются с конкретными файлами);

2. Вводить и выводить строки, символы, форматированные данные, порции данных произвольной длины;

3. Управлять буферизацией потока и размером буфера;

4. Получать и устанавливать указатель текущей позиции в файле.

Прототипы функций ввода-вывода находятся в заголовочном файле <stdio.h>, который также содержит определения констант, типов и структур, необходимых для обмена с потоком.

Открытие и закрытие потока

Прежде, чем начать работать с потоком, его надо инициировать, т. е. открыть. При этом поток связывается со структурой предопределенного типа FILE, определение которой находится в файле <stdio.h>. В структуре находится указатель на буфер, указатель на текущую позицию и т. п. При открытии потока возвращается указатель на поток, т. е. на объект типа FILE. Указатель на поток должен быть объявлен следующим образом:

#include <stdio.h>

........

FILE*f;//указатель на поток

Указатель на поток приобретает значение в результате выполнения функции открытия потока:

FILE* fopen(const char*filename,const char*mode);

где const char*filename – строка, которая содержит имя файла, связанного с потоком,

const char*mode – строка режимов открытия файла.

Например:

f=fopen(“t.txt”,”r”);

где t.txt – имя файла, r – режим открытия файла.

Файл связанный с потоком можно открыть в одном из 6 режимов

Режим	Описание режима открытия файла
r	Файл открывается для чтения, если файл не существует, то выдается ошибка при исполнении программы.
w	Файл открывается для записи, если файл не существует, то он будет создан, если файл уже существует, то вся информация из него стирается.
a	Файл открывается для добавления, если фай не существует, то он будет создан, если существует, то информация из него не стирается, можно выполнять запись в конец файла
r+	Файл открывается для чтения и записи, изменить размер файла нельзя, если файл не существует, то выдается ошибка при исполнении программы.
w+	Файл открывается для чтения и записи, если файл не существует, то он будет создан, если файл уже существует, то вся информация из него стирается.
a+	Файл открывается для чтения и записи, если фай не существует, то он будет создан, если существует, то информация из него не стирается, можно выполнять запись в конец файла

Поток можно открывать в текстовом (t) или двоичном режиме(b). В текстовом режиме поток рассматривается как совокупность строк, в конце каждой строки находится управляющий символ ‘\n’. В двоичном режиме поток рассматривается как набор двоичной информации. Текстовый режим устанавливается по умолчанию.

В файле stdio.h определена константа EOF, которая сообщает об окончании файла (отрицательное целое число).

При открытии потока могут возникать следующие ошибки:

- файл, связанный с потоком не найден (при чтении из файла);

- диск заполнен (при записи);

- диск защищен от записи (при записи) и т. п.

В этих случаях указатель на поток приобретет значение NULL (0). Указатель на поток, отличный от аварийного не равен 0.

Для вывода об ошибке при открытии потока используется стандартная библиотечная функция из файла <stdio.h>

void perror (const char*s);

Эта функция выводит строку символов, не которую указывает указатель s, за этой строкой размещается двоеточие пробел и сообщение об ошибке. Текст сообщения выбирается на основании номера ошибки. Номер ошибки заносится в переменную int errno(определена в заголовочном файле errno.h).

После того как файл открыт, в него можно записывать информацию или считывать информацию, в зависимости от режима.

Открытые файлы после окончания работы рекомендуется закрыть явно. Для этого используется функция:

int fclose(FILE*f);

Изменить режим работы с файлом можно только после закрытия файла.

Пример:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

void main()

{

FILE *f;

char filename[20];

cout<<”\nEnter the name of file:”; cin>>filename;

if(f=fopen(filename,”rb”)==0)//открываем для чтения в бинарном режиме и проверяем

// возникает ли ошибка при открытии файла

{

perror(strcat“error in file:”,filename);//strcat складывает две строки

exit(0);//выход из программы

}

.....

fclose(f);

}

Для текстового файла:

if(f=fopen(filename,” rt ”)==0)//открываем для чтения и проверяем возникает ли ошибка при //открытии файла

if(f=fopen(filename,” r ”)==0)//открываем для чтения и проверяем возникает ли ошибка при //открытии файла