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

 

sortHnr(a,0,k-1);

writem(fout,k,a);

fout.close();fin.close();

return 0;

}_________________________________________

//сортировка Хоара (рекурсивный вариант)

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

}

}