int p_lin1(tmas a[], int n, int x)

Р

{

for(int i=0; i < n; i++)

И

if (a[i].key == x) return i;

У

return -1;

}

Г

В данном алгоритме на каждом шаге делается две проверки: проверка на

равенство ключевого поля и искомого

и проверка условия продолжения

Б

лического алгоритма вводится вспомог тельный элемент – барьер, который

ключа

предохраняет от выхода за пред лы массива:

к

int p_lin2(tmas a[], int n, int x)

{

е

a[n+1].key = x;

т

int i = 0;

while (a[i].key != x) i++;

о

if (i == n+1) return -1;

и

else return i;

}

л

Эффект вность такого алгоритма почти в два раза выше предыдущего.

б

и

15.2. Поиск делением пополам

Поиск деления пополам используется, когда данные упорядочены, на-

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

{

int i=0, j=n-1, m;

while(i < j)

{

m=(i + j)/2;

Р

if (x > a[m].key) i = m+1; else j = m;

И

}

if (a[i].key == x) return i;

У

else return -1;

}

Г

Б,

15.3. Интерполяционный поиск

Для массивов с равномерным распределением элементов можно использо-

где i, j − начало и конец интервала; x − ис омое зн чение ключевого поля.

int p_dv(tmas a[], int n, int x)

а

{

к

е

int i = 0, j = n-1, m;

while(i < j)

т

{

о

if (a[i].key == a[j].key) // предотвращение деления на нуль

if (a[i].key == x) return i;

иelse return -1;

m=i + (j - i) * (x - a[i]) / (a[j] - a[i]);

л

if (a[m].key == x) return m;

elseб

if (x > a[m].key) i = m+1; else j = m-1;

и

}

Бreturn -1;

Стек (stek) – список с одной точкой входа. Данные добавляются в список

Р

и удаляются из него только с одной стороны последовательности (вершины

И

У

данных:

ук

данных, в описании которого содержится з тельБна аналогичную этому типу

структуру.

е

Чаще всего используется следующаяаконструкция рекурсивного типа

};

т

struct tinf

{

о

// Набор полей с рук уры

и

л

struct tlist

{

б

и

// Информационная часть структуры

Б

tinf s;

tlist *a;

// Адресная часть структуры

} spis;

Для упрощения рассмотрения в дальнейшем будет использоваться струк-

туру следующего типа:

struct tlist

{

int inf;

; // Информационная часть структуры

tlist *a;

// Адресная часть структуры

} sp;

Рис. 16.1

Р

И

Для перемещения по списку необходимо последовательно переходить от

У

одной ячейки к другой. Такая организация списка называется косвенной адре-

сацией. В отличие от адресации по индексу косвенная адресация менее нагляд-

на, однако обладает большей гибкостью.

Г

16.2. Работа со стеками

Добавление элемента в стек

Б

tlist *AddStack(tlist *sp, int inf)

{ tlist *spt = new tlist;

е

а

spt->inf = inf;

spt->a = sp;

т

к

return spt; }

о

Чтение элемента с удалением

и

tlist *ReadStackD(tlist *sp, int &inf)

{ if (sp == NULL) return NULL;

tlist *spt = sp;

б

inf= sp->inf;

и

sp =лsp->a;

delete spt;

return sp; }

Удаление элемента, следующего за текущим

Бvoid DelStackAfter(tlist *sp)

{ if (sp->a == NULL) return ;

tlist *spt = sp->a;

sp->a = sp->a->a;

delete spt;

}

Удаление всего стека

Р

tlist *DelStackAll(tlist *sp)

{ tlist *spt; int inf;

И

while(sp != NULL)

{

У

spt = sp;

Г

inf = sp->inf;

cout << inf << endl;

sp = sp->a;

а

delete spt;

}

Б

return NULL; }

к

Обмен элементов, следующих за те ущим

void RevStackAfter(tlist *sp)

т

{ tlist *spt = sp->a->a;

е

sp->a->a = spt->a;

spt->a = sp->a;

и

sp->a = spt; }

л

Сортировка с обменомадресами методом пузырька

void SortStackAfter(tlist *sp)

{ if (sp->a->a == NULL) return;

и

tlist *spt = NULL, *spm;

doб{

for (spm=sp; spm->a->a != spt; spm=spm->a)

if (spm->a->inf > spm->a->a->inf) RevStackAfter(spm);

Бspt = spm->a;

Поиск в стеке

tlist * PoiskStack(tlist *sp, int x) // Поиск

{

И

if (sp==NULL) return NULL;

У

Р

tlist *spt=sp;

Г

while (spt->inf != x && spt->a != NULL) spt=spt->a;

if (spt->inf == x) return spt;

Б

else return NULL;

}

16.2. Работа с однонапр вленными очередями

е

а

Добавление элемента в оч р дь

void Addoch(tlist **sp,tlist **spk,кint inf)

{

т

о

tlist *spt = new tlist;

spt->inf = inf;

и

spt->a = NULL;

л

if (*spk == NULL) // Если нет элементов

*sp = *spk = spt;

else

и

{

б(*spk)->a = spt;

*spk = spt;

}

Бreturn;

Чтение элемента с удалением

tlist *ReadochD(tlist *sp, int &inf)

{

if (sp == NULL) return NULL;

inf = sp->inf;

tlist *spt = sp;

sp = sp->a;

delete spt;

return sp;

И

}

У

Р

Удаление элемента, следующего за текущим

void DelOchAfter(tlist *sp)

Г

{

if (sp->a == NULL) return;

tlist *spt = sp->a;

а

sp->a = sp->a->a;

Б

delete spt;

к

}

е

{

Удаление всей очереди

т

void DelOchAll(tlist **sp, tlist **spk) // Удаление всей очереди

о

tlist *spt; int inf;

и

while(*sp != NULL)

{

б

spt = *sp;

и

inf л= (*sp)->inf;

Б

cout << inf << endl;

} *sp;

Р

Чтобы избавиться от необходимости написания алгоритмов обработки

крайних элементов, создается каркас двусвязанной структурыИ, состоящий из

двух крайних, не имеющих информационной части, элементов. После этого

У

любые добавляемые в список элементы будут являться внутренними элемента-

ми этого списка (рис. 15.6).

Г

Б

Рис. 15.6

Создание очереди.

а

к

void NewOchd(tlistdbl **sl, tlistdbl **sr)

{

е

т

*sl = new tlistdbl;

*sr = new tlistdbl;

(*sl)->left = NULL;о

(*sl)->right = *sr;

и

(*sr)->left = *sl;

л

(*sr)->right = NULL;

б

и

Б

tlistdbl *spt = new tlistdbl;

spt->inf = inf;

spt->left = sp;

spt->right = sp->right;

sp->right = spt;

spt->right->left = spt;

return;

}

Р

{

Добавление элемента перед заданным

И

void AddochdLeft(tlistdbl *sp, int inf)

У

tlistdbl *spt = new tlistdbl;

Г

spt->inf = inf;

spt->left = sp->left;

spt->right = sp;

а

}

spt->left->right = spt;

Б

sp->left = spt;

к

return;

Чтение и удаление элем

с адр сом sp

int ReadochdD(tlistdbl *sp)е

{

о

и

int inf = sp->inf; нта

sp->left->right = sp->right;

sp->right->left = sp->left;

б

delete sp;

Удаление всего списка

returnлinf;

}

Б{

void DelOchdAll(tlistdbl **sl, tlistdbl **sr)

spt = (*sl)->right;

}

delete *sl;

*sl = NULL;

delete *sr;

*sr = NULL;

return;

}

Сортировка слиянием двусвязанного списка

Р

Разбиение списка на 2 списка

void div2Ochd(tlistdbl *sl, tlistdbl *sr,tlistdbl **slL, tlistdbl **srL,tlistdbl

**slR, tlistdbl **srR)

{

У

NewOchd(slL,srL);

Г

И

NewOchd(slR,srR);

Б

tlistdbl *spt = sl->right;

while(spt != sr)

а

{

к

AddochdLeft(*srL, ReadochdD(spt));

spt = sl->right;

е

if (spt != sr)

{

AddochdLeft(*srR, ReadochdD(spt));

}

о

} spt = sl->right;

т

}

и

л

delete sl;

б

Б{

delete sr;

Сл ян е двух отсортированных списков

иvoid slipOchd(tlistdbl **sl, tlistdbl **sr,tlistdbl *slL, tlistdbl *srL,tlistdbl

}

else

{

Р

AddochdLeft(*sr, ReadochdD(sptR));

И

sptR = slR->right;

}

У

}

while (sptL != srL)

{

Б

AddochdLeft(*sr, ReadochdD(sptL));

Г

sptL = slL->right;

а

}

к

delete slL; delete srL;

while (sptR != srR)

{

т

AddochdLeft(*sr, ReadochdD(sptR));

sptR = slR->right;

е

}

о

и

delete slR; delete srR;

}

л

Сортировка

void SotrSlipOchd(tlistdbl **sl, tlistdbl **sr)

и

{

бtlistdbl *slL, *srL,*slR, *srR;

if ((*sl)->right->right == *sr) return;

div2Ochd(*sl, *sr, &slL, &srL, &slR, &srR);

БSotrSlipOchd(&slL, &srL);

Р

Рис. 16.3

И

Добавление элемента в циклический список

У

tlistdbl *AddochdC(tlistdbl *sp, int inf)

//

{

Б

tlistdbl *spt = new tlistdbl;

Г

spt->inf = inf;

а

if (sp == NULL)

к

}

е

{

spt->left = spt;

т

spt->right = spt;

else

о

{

и

spt->right = sp->right;

spt->left = sp->right ->left;

б

sp->right ->left = spt;

и

sp->rightл= spt;

}

return spt;

}

БПодключение

}

Удаление всего списка

tlistdbl *DelOchdCAll(tlistdbl *sp)

{

tlistdbl *spt;

while(sp->right != sp)

И

{

У

Р

cout << sp->inf << endl;

sp->left->right = sp->right;

Г

sp->right->left = sp->left;

spt = sp;

Б

sp = sp->right;

} delete spt;

е

cout << sp->inf << endl;

а

delete sp;

т

к

return NULL;

о

}

и

л

б

и

Б