Линейный список
Лекция 6.
4. Линейный список – совокупность однотипных элементов, расположенных последовательно друг за другом, количество элементов в списке не фиксируется.
В списке присутствует указатель, он может перемещаться по списку, отмечает текущий элемент при просмотре списка.
в начале текущий в конце
списка элемент списка
Указатель может перемещаться по списку от начала к концу, в этом случае список называется однонаправленный. Если указателю разрешено перемещаться от начала к концу и от конца к началу списка, список называется двунаправленный.
Операции для однонаправленного списка:
- Сделать список пустым.
- Установить указатель в начало списка.
- Передвинуть указатель на одну позицию к концу.
- Добавить элемент за указателем.
- Удалить элемент за указателем, если такой есть.
- Проверить, стоит ли указатель в конце списка.
- Проверить список на пустоту.
- Выбрать элемент за указателем без удаления.
Список можно реализовать также на основе массива, но в этой реализации такие операции, как добавление и удаление элементов, будут требовать много времени, т.к. придется сдвигать часть массива.
Самим придумать операции для двунаправленного списка.
Связанный список.
Пусть x0 , x1 ,x2 ,. . . . .xn-3, xn-2, xn-1 – совокупность значений данных некоторого типа tip, которые необходимо создать и сохранять в процессе выполнения алгоритма.
Можно описать массив указателей и для каждого создать динамическую переменную:
Выбрать нужный размер массива указателей часто не удаётся. Используется такой способ: под динамическую
переменную выделяется память, но в этой памяти кроме переменной хранится ещё указатель на следующую динамическую переменную:
. . . . . .
Последняя переменная в поле указателя хранит NULL. Кроме того, выделяют указатель на первый элемент (указатель на список), пусть это beg. Такая структура называется связанный список.
Наличие beg позволяет добраться до любого элемента списка. Это список односвязанный.
Если вместе с переменной хранится указатель на следующую переменную и указатель на предыдущую переменную, то список становится двунаправленным, он называется двусвязанным.
Если последний элемент списка указывает на его первый элемент, список называется циклическим.
Организация связанного списка.
- Определить тип элемента связанного списка.
Обозначим tip – тип информационной части элемента списка. Например,
typedef int tip;
Структура элемента связанного списка:
struct tel
{tip inf; // информационная часть
tel *next; //указатель на следующий элемент
};
- Описать указатель на связанный список (иногда удобно описать два указателя: на начало и на конец), рабочие указатели.
tel * beg, *p, *q;
- Объявить список пустым: beg = NULL;
- Включить элемент x : tip в пустой список:
beg = new tel;
|
(*beg) . inf=x; beg
|
x
|
NULL
|
(*beg). next=NULL;
5. Включить элемент x : tip в начало списка:
q= new tel;
(*q) . inf=x;
(*q). next=beg;
beg = q;
q
6. Включить элемент x : tip в связанный список после элемента, на который указывает p.
a) q= new tel; б) q = p ->next;
(*q) . inf=x; p ->next= new tel;
(*q). next=p ->next; (p ->next) ->inf = x;
p->next = q; (p ->next) ->next=q;
p
7. Исключить из списка элемент, следующий за
элементом, на который указывает p.
а) плохой вариант:
p -> next = (p -> next) -> next;
p q
мусор
б) q = p ->next;
p->next = q-> next;
delete q;
- Передвинуть указатель p на следующий элемент связанного списка:
p = p-> next;
- Обработать все элементы связанного списка по очереди с помощью функции void W(tip t).
p=beg;
while (p) // while (p!=null)
{W (p->inf);
p=p->next; }
10.Освободить память, занятую под связанный список.
while (beg)
{ q= beg;
beg= beg ->next;
delete q;
}
11.Пример функции, которая вставляет в связанный список beg элемент x : tip на свое место, и создаёт упорядоченный список за несколько обращений к функции с разными элементами.
void ВСТАВКА (tel * & beg, tip x)
{tel *p, *q, *t;
// поиск места вставки x
t = beg; p = NULL;
bool b = true;
while (t && b)
if (t -> inf < x) {p=t; t = t->next;}
else b=false; // найдено место вставки
//создание нового элемента
q= new tel; q->inf = x;
if (p == NULL) // вставка в начало или в пустой список
{q ->next = beg; beg = q;}
else //вставка после элемента, на который указывает p
{q-> next = p->next;
p-> next =q; } //это может быть вставка в конец,если
// (p->next=0), либо в середину
}
Динамические структуры можно создавать на основе связанного списка. В этом случае элементы динамической структуры составляют информационные части элементов списка.
Рассмотрим реализацию стека на основе связанного списка (в виде 3-х файлов).
// stack3f.h
#include <iostream>
#include <fstream>
using namespace std;
struct segment
{int lg,rg;
};
typedef segment tip;
struct tdp
{tip inf;
tdp *next;
};
void clrst(tdp * &);
void push (tdp * &, tip );
void pop (tdp * &);
tip topst (tdp * );
bool emptyst (tdp * );
ofstream & operator <<(ofstream &, tip);
// stack3fR.cpp
#include "stack3f.h"
// Очистка стека
void clrst (tdp * & s)
{s=NULL;}
/*//запись элемента х в стек
tdp * push (tdp* s, tip x)
{tdp *r=new tdp;
(*r).inf=x;
(*r).next=s;
s=r;
return s;
}*/
//запись элемента х в стек
void push(tdp* & s, tip x)
//возвр.указатель на вершину стека через параметр
{tdp *r=new tdp;
(*r).inf=x;
(*r).next=s;
s=r;
}
//выталкивание эл-та из непустого стека
void pop(tdp* & s)
//возвр. ук-ль на вершину стека через параметр
{tdp * p=(*s).next;
delete s;
s=p; //новая вершина стека
}
//проверка стека на пустоту
bool emptyst (tdp* s)
{return (s==0); //NULL;
}
//
tip topst (tdp * s )
{return s->inf;}
ofstream & operator <<(ofstream &f, tip el)
{f<<'['<<el.lg<<" - "<<el.rg<<']';
return f;
}
//NERECHOAR.cpp
#include <iomanip>
#include "stack3f.h"
int const ni=100;
ifstream fin;
ofstream fout;
void readm(ifstream & fin,int& k,int a[]);
void writem(ofstream &fout, int k,int a[]);
void sortHnr(int a [ ], int l, int r);
int main ()
{ int k;
int a[ni];
fout.open("rez.txt");
if(fout.fail()){cout<<"?open rez.txt";return 2;}
fin.open("dan.txt");
if(fin.fail()){cout<<"?open dan.txt";return 2;}
readm(fin,k,a);
writem(fout,k,a);
sortHnr(a,0,k-1);
writem(fout,k,a);
fout.close();fin.close();
return 0;
}
void readm(ifstream & fin,int & k,int a[])
{k=0;
// чтение массива
while (fin>>a[k])k++;
}
void writem(ofstream &fout,int k,int a[])
{for(int i=0;i<k;i++)
{fout<<setw(6)<<a[i];
if((i+1)%10==0)fout<<endl;
fout<<endl; }
_________________________________________
//сортировка Хоара (рекурсивный вариант)
void sortH (int a [ ], int l, int r)
{ int i=l, j=r;
int x=a [(l+r)/2]; // средний элемент
// Цикл разделения
do
{while (a[i] < x) i++;
while (a[j]>x) j --;
if (i<=j)
{int w=a[i]; a[i]=a[j]; a[j]=w;
i++; j-- ;
}
}
while (i<=j);
if (l<j) sortH (a, l, j);
if (i<r) sortH(a, i, r);
}
Пример
23 54 12 45 78 24 36 71 21 35 11 22 44 55 67
[0 – 14]
[0 - 12] [13 - 14] (1)
[0 - 6] [7 - 12] (2)
[0,0] [1 - 6] (3) [7 - 11] [12,12]
[1 - 3] [4 - 6] (4) [7 - 8] [9 - 11] (6)
[1,1] [2 - 3](5) [9,9] [10,11] (7)
11 12 21 22 23 24 35 36 44 45 54 55 67 71 78
//сортировка Хоара
void sortHnr (int a[],int l, int r)
{tdp * beg; clrst(beg);
tip el;
el.lg=l; el.rg=r; push(beg, el);
while (! emptyst (beg))
{ el=topst(beg); pop(beg);
l=el.lg; r=el.rg;
fout<<el<<'\n'; // перегруженная операция
do
{ int i=l, j=r;
int x=a[(l+r)/2]; fout<<x<<'\n';
//цикл разделения
do
{while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{int w=a[i]; a[i]=a[j]; a[j]=w;
i++; j--; }
}
while (i<=j);
//отрезок [l,r] разделён на два [l,j] [i,r]
if (i<r) {el.lg=i; el.rg=r; push(beg, el);}
r=j;
}while(l<r);
}
}
Шаблон связанного списка
Для создания шаблона требуется,
- чтобы объявление операций и реализация этих операций находились в одном файле (3-х файловая программа не работает).
- template <class tip> помешают перед каждой функцией и структурой tel (если в ней есть параметр шаблона).
//shablon.h
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
template <class tip>
struct tel
{tip inf;
tel *next;
};
struct point // структура нужна для перегрузки операции,
{double x,y;}; // как другой тип параметра шаблона
// включить элемент в пустой список
template <class tip>
void vkl (tel<tip> * &p, tel<tip> * &q, tip el) //в списке 2 указателя
{p=new tel<tip>;
p->inf=el;
p->next=0;
q=p;
}
// включить элемент в начало списка
template <class tip> // В списке есть элементы
void vklnach(tel<tip> * &p, tip el)
{tel<tip> *r =new tel <tip>;
r->inf =el;
r->next =p;
p=r;
}
//включить элемент в конец списка
template <class tip> > // В списке есть элементы
void vklkon (tel<tip> * &q, tip el)
{q->next=new tel<tip>;
q =q->next;
q->inf=el;
q->next=0;
}
//выдать все эл-ты из св. списка в файл
template <class tip>
void wrf (ofstream & f, tel<tip> * p)
{tel<tip> *r = p;
while (r)
{f<< r->inf<<" ";
r=r -> next;}
f<<endl;
}
// удаление списка
template <class tip>
void delsp(tel<tip> * &p, tel<tip> * &q)
{tel<tip> *r;
while (p)
{r=p;
p=p->next;
delete r;
}
q=0;
}
//перегрузка операции<<
ofstream & operator << (ofstream & f, point p)
{f<<p.x<<" "<<p.y<<'\n';
return f;
}
#include "shablonsp.h"
int main()
{tel<int> *beg=0, *kon=0;
ifstream fin;
ofstream fout;
fin.open("dan.txt");
if (fin.fail())
{cout<<"error open file dan.txt "<<endl; return 1;}
fout.open("rez.txt");
if (fout.fail())
{cout<<"error open file rez.txt "<<endl; return 1;}
int m;
int z=1;
if (fin>>m) vkl (beg, kon, m);
while (fin>>m)
{if (z>0) vklnach (beg,m);
else vklkon (kon,m);
z=-z;
}
wrf (fout, beg);
delsp (beg, kon);
fin.close();
fout.close();
// работа шаблона для типа point
tel<point>*u=0,*v=0;
fin.clear();
fout.clear();
fin.open("danp.txt");
if (fin.fail())
{cout<<"error open file danp.txt "<<endl; return 1;}
fout.open("rez.txt",ios::app);
if (fout.fail())
{cout<<"error open file rez.txt "<<endl; return 1;}
point b;
z=2;
if (fin>>b.x>>b.y) vkl (u,v,b);
while (fin>> b.x>>b.y)
{if(z>0) vklnach(u,b);
else vklkon (v,b);
z=-z;
}
wrf(fout,u);
delsp(u,v);
fin.close();
fout.close();
return 0;
}
dan.txt
32 5 6 7 8 9 21 33 65
danp.txt
1 2.5
2 3
3 1
4 2
5 9
6 4
7 5
rez.txt
33 9 7 5 32 6 8 21 65
6 4
4 2
2 3
1 2.5
3 1
5 9
7 5
PAGE 22
Линейный список