Программная реализация стека на основе массива

Пример 14.1

Файл stack.h

#include < stdio.h>

#include < stdlib.h>

#include < malloc.h>

#include < conio.h>

////////////////////// Stack for char

typedef struct

{char *stack;

int head;

int size;

} STACK;

int Init(STACK* Stack, int nSize);

char Pop(STACK* Stack);

int Push(STACK* Stack, char cElement);

void Clear(STACK* Stack);

int GetSize(STACK* Stack);

void Free(STACK* Stack);

#include " stack.h"

////////////////////// Stack for char

///////////////////////////////////////////////

int Init(STACK* Stack, int nSize)

{Stack-> stack = (char*)malloc(nSize);

if (Stack-> stack == NULL) return -1;

Stack-> size = nSize;

Stack-> head = 0;

return nSize; }

///////////////////////////////////////////////

char Pop(STACK* Stack)

{if (Stack-> head == 0) return 0;

return Stack-> stack[--Stack-> head]; }

///////////////////////////////////////////////

int Push(STACK* Stack, char cElement)

{if (Stack-> head == Stack-> size) return -1;

Stack-> stack[Stack-> head++] = cElement;

return 1; }

///////////////////////////////////////////////

void Clear(STACK* Stack)

{Stack-> head = 0; }

///////////////////////////////////////////////

int GetSize(STACK* Stack)

{ return Stack-> head; }

///////////////////////////////////////////////

void Free(STACK* Stack)

{ free(Stack-> stack); }

void main()

{STACK A;

Init(& A, 8);

Push(& A, 'J');

Push(& A, 'F');

char c = Pop(& A);

 

53.Сортировка методом обмена(пузырька).

Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,..., K'n >, в котором для любого 1< =i< =n элемент K'(i) < = K'(i+1).

При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

Пример 15.2

Функция BubbleSort() реализует алгоритм сортировки методом «пузырька»:

void BubbleSort(int a[], int n)

{

/*функции передается массив и его размерность */

int i, j; /* переменные цикла */

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

for (j=n-1; j> i; j--)

if (a[j-1] > a[j])

/*если элемент " тяжелее" следующего

swap(& a[j-1], & a[j]) /*поменять их местами */

}

Анализ пузырьковой сортировки.

Пузырьковая сортировка обладает несколькими характеристиками:

• после каждой итерации только один элемент данных помещается в свою правильную позицию;

• сравнение и перестановка смежных элементов данных;

• в каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок;

• худший случай — когда элементы данных отсортированы в обратном порядке;

•лучший случай — когда элементы данных уже отсортированы в правильном порядке;

• легкость реализации.

Методом выбора.

Алгоритм:

1 шаг – находится наименьший элемент в массиве;

2 шаг – найденный элемент меняется с первым элементом;

3 шаг – процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее, пока в конце не останется самый большой элемент, который не нуждается в перестановке.

Пример 15.3

void MinSort(int a[], int n)

{ int i, j, k;

for (i=0; i< n-1; i++)

{ for (k=i; j=i+1; j< n; j++) // находим в цикле

if (a[j] < a[k]) // минимальный элемент

{ k = j; // запоминаем его номер в к

swap(& a[k], & a[i]); // меняем местами минимальный и

} // элемент, с которого начинался цикл}}

 

Методом вставки.

Сортировка вставками — очень простой метод сортировки, при котором элементы данных используют­ся как ключи для сравнения. Этот алгоритм сначала упорядочивает А[0] и А[1], вставляя А[1] перед А[0], если А[0] > А[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный список. После k-й итерации элемент A[k] оказывается в своей правильной позиции и элементы от А[0] до A[k] уже отсортированы.

Пример 15.4

Функция InsertSort() реализует алгоритм сортировки методом вставки:

void InsertSort (int a[], int n)

{ int i, j

for (i=1; i< =n-1; i++)

{ j=i;

while (a[j]< a[j-1] & & j> =1)

{ Swap(& a[j], & a[j-1]);

j--; } }}

Анализ сортировки вставками

Сортировка вставками обладает следующими характеристиками:

• после каждой итерации только один элемент помещается в свою правильную позицию;

• при этом методе выполняется меньше перестановок, чем в пузырьковой сортировке;

• наихудший случай - когда все элементы данных отсортированы в обратном порядке;

• наилучший случай - когда элементы почти отсортированы в правильном порядке;

• легкость реализации.

Методом Шелла.

Метод Шелла является обобщением метода вставок и основан на том, что сортировка методом вставок выполняется очень быстро на почти отсортированном массиве данных. Он также известен как сортировка с убывающим шагом. В отличие от сортировки методом вставок при сортировке методом Шелла весь массив не сортируется одновременно: массив разбивается на отдельные сегменты, которые сортируются раздельно с помощью метода вставок.

Основная идея алгоритма состоит в том, что на начальном этапе реализуется сравнение и, если требуется, перемещение далеко отстоящих друг от друга элементов. Интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы, что приводит к перестановке соседних элементов на последних стадиях сортировки (если это необходимо).

Реализуем метод Шелла следующим образом. Начальный шаг сортировки примем равным n/2, т.е. ½ от общей длины массива, и после каждого прохода будем уменьшать его в два раза. Каждый этап сортировки включает в себя проход всего массива и сравнение отстоящих на gap элементов. Проход с тем же шагом повторяется, если элементы переставлялись. Заметим, что после каждого этапа отстоящие на gap элементы отсортированы. Рассмотрим пример.

Пример 15.5

Рассортировать массив чисел: 41, 53, 11, 37, 79, 19, 7, 61. В строке после массива в круглых скобках указаны индексы сравниваемых элементов и указан номер внешнего цикла.

41 53 11 37 79 19 7 61 – исходный массив

42 19 11 37 79 19 7 61 – (0, 4), (1, 5)

1-й цикл

41 19 7 37 79 19 11 61 – (2, 6), (3, 7)

7 19 41 37 11 53 79 61 – (0, 2), (1, 3), (2, 4), (3, 5), (4, 6), (5, 7)

2-й цикл

7 19 11 37 41 53 79 61 –

7 11 19 37 41 53 61 79 – (сравнивались соседние элементы) 3-й цикл

void sort_shell(int *x, int n)

{ int i, j; //две переменные цикла

int gap; //шаг сортировки

int sorted; //флаг окончания этапа сортировки

for(gap=n/2; gap> 0; gap/=2)//начало сортировки

do

{ sorted = 0;

for(i=0, j=gap; j< n; i++, j++)

if(*(x+i)> *(x+j))

{ swap((x+i), (x+j);

sorted = 1; } }

while(sorted); }

Анализ сортировки методом Шелла

Сортировка методом Шелла будет выполняться для многих задач, в которых количество элементов в массиве данных небольшое. Любую возможность даже незначительного ускорения сортировки необходимо использовать.

57.Метод быстрой сортировки(Хоара).

Сортировка методом Хоора (или быстрая сортировка) — это наиболее эффективный алгоритм внутренней сортировки. Его производительность зависит от выбора точки разбиения. При быстрой сортировке используется следующая стратегия:

1. Массив разбивается на меньшие подмассивы.

2. Подмассивы сортируются.

3. Отсортированные подмассивы объединяются.

Быструю сортировку можно реализовать несколькими способами, но цель каждого подхода заключается в выборе элемента данных и помещении его в правильную позицию (этот элемент называется точкой разбиения) таким образом, чтобы все элементы слева от точки разбиения оказались меньше (или предшествовали) точки разбиения, а все элементы справа от точки разбиения оказались больше (или следовали за ней). Выбор точки разбиения и метод, используемый для разбиения массива, оказывают большое влияние на общую производительность реализации.

Рассмотрим один из вариантов реализации сортировки Хоора.

Пример 15.6

В самой процедуре сортировки сначала выберем средний элемент. Потом, используя переменные i и j, пройдемся по массиву, отыскивая в левой части элементы больше среднего, а в правой – меньше среднего. Два найденных элемента переставим местами. Будем действовать так, пока i не станет больше j. Тогда получаем два подмножества, ограниченные с краев индексами l и r, а в середине – j и i. Если эти подмножества существуют (то есть i< r и j> l), то выполним их сортировку.

void Quicksort(int a[], int n, int left, int right)

{ int i=left, j=right; /*Инициализируем переменные левой и

правой границами подмассива*/

int test=a[(left+right)/2]; /*Выбираем в качестве

элемента разбиения средний элемент массива*/

do { while (a[i] < test)

i++;

/*находим элемент, больший элемента разбиения */

while (a[j] > test)

j--;

/*находим элемент, меньший элемента разбиения */

if (i< =j)

{ Swap(& a[i], & a[j);

i++; j--; }

}

while(i < = j); /*рекурсивно вызываем алгоритм для

правого и левого подмассива*/

if (i< right)

QuickSort(a, n, i, right);

if (j> left)

QuickSort(a, n, left, j);

}

Анализ быстрой сортировки

Быструю сортировку следует рассмотреть одной из первых при выборе метода внутренней сортировки. Алгоритм этой сортировки содержит сложную фазу разбиения и простую фазу слияния. В худшем случае выполненная работа эквивалентна работе при сортировке выбором. Производительность быстрой сортировки существенно зависит от выбора точки разбиения.

⇐ Предыдущая123456

Поделиться: