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"

 

using namespace std;

// Пример для лекции

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 sortHnr (int a[],int l, int r)

{tdp * beg=0;

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);

}

}