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

Else

Else

Do

Else

Частотный словарь

Else

Else

{ // найти место вставки

while ((q.next!=null)&&(q.next.inf<=inf))

q = q.next;

MyNode p = new MyNode(inf, q.next);

q.next = p;

}

}

head = new MyNode(inf,null); // список пуст

count++;

}

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

Если слово встречается первый раз, то оно заносится в список. Если такое слово уже есть в списке, то увеличивается счетчик появления этого слова. Поэтому список опишем следующим образом:

Листинг 8.11. Класс MyNodeStr

class MyNodeStr

{

public string inf; // слово

public MyNodeStr next;

public int count; // счетчик слов

// Конструктор

public MyNodeStr(string inf, MyNodeStr next)

{

this.inf = inf;

this.next = next;

this.count = 1;

}

public void AddCount()

// метод увеличения счетчика

{ count++; }

}

Сначала необходимо осуществить поиск слова в списке. Для переменных типа string упорядочение понимается в лексикографическом смысле, то есть роза меньше, чем роса, а роса меньше, чем соловей. В C# нельзя сравнивать строки s1 и s2 операциями отношения <,>. Вместо операций отношения необходимо использовать метод класса string:

int string.CompareOrdinal(s1, s2)

Этот метод возвращает отрицательное значение, если s1<s2, равное 0, если s1=s2, и положительное, если s1>s2.

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

а б

Рис. 8.5.Блок-схемы алгоритмов вставки в упорядоченный список (а) и обработки слова в списке частотного словаря (б)

Программные дополнения учтены в процедуре AddSort, приведенной в листинге 8.12.

Листинг 8.12. Вставка слова в список частотного словаря

public void AddSort(string inf)

{

if (head != null)

{

MyNodeStr q = head;

int k = string.CompareOrdinal(inf, q.inf);

// -1:s1<s2 0:s1=s2 1:s1>s2

if (k<=0)

if (k == 0)

q.AddCount();

else { // вставить перед головой

MyNodeStr p = new MyNodeStr(inf, q);

head = p;

}

{

MyNodeStr r; // поиск: inf >= q.inf

{

r = q;

q = q.next;

if (q != null)

k = string.CompareOrdinal(q.inf, inf);

}

while ((q!=null) && (k<0));

if (q != null)

if (k == 0)

q.AddCount();

{ // вставить между r и q

MyNodeStr p = new MyNodeStr(inf, q);

r.next = p;

}

{ // вставить за r

MyNodeStr p = new MyNodeStr(inf, null);

R .next = p;

}

}

}

else // список пуст

head = new MyNodeStr(inf,null);

count++;

}

Для вызова метода AddSort() в коде Main() вставим строки:

Листинг 8.13. Вызов метода AddSort()

MyListWord myListWord = new MyListWord();

string[] s = {"bbb", "ccc", "aaa", "bbb", "aaa" ,

"ccc", "bbb"};

for (int i = 0; i <= s.Length - 1; i++ )

myListWord.AddSort(s[i]);

myListWord.Printer();

Слияние — это объединение двух (или более) упорядоченных последовательностей в одну при помощи циклического выбора элементов, доступных в данный момент. Слияние двух списковможно осуществить просто перестановкой указателей. Например, пусть есть два списка, показанные на рис.8.6.

Рис. 8.6. Упорядоченные списки

В случае, когда оба списка не пустые, наименьший из двух первых элементов исходных списков будет первым элементом списка-результата. Далее алгоритм слияния заключается в том, что происходит движение по тому из списков, элементы которого не больше, чем фиксированный элемент другого списка. Затем необходимо переставить указатели, то есть перецепить списки. Зафиксировать элемент того из списков, значение которого меньше, и двигаться по другому списку. И так до тех пор, пока один из списков не закончится. Оставшийся список прицепляем к его концу.

На рис.8.7 показан результат слияния списков.

Рис. 8.7. Список, полученный в результате слияния.

Алгоритм слияния списков реализован в виде функции, значение которой — указатель на список-результат. Этот алгоритм, учитывающий и два вырожденных случая: оба списка пустые и один из двух списков пустой, приведен в листинге 8.14.

Примечание. В алгоритме предполагается, что движение по одному из списков осуществляется с помощью указателя r , тогда как q указывает на элемент другого списка, с которым происходит сравнение.

Листинг 8.14. Слияние двух списков

static MyList Merge(MyNode list1, MyNode list2)

{

MyNode r;

MyList result = new MyList();

MyNode p = list1;

MyNode q = list2;

if ((p != null) && (q != null)) {

if (p.inf <= q.inf) {

result.head = p; r = p;

}

else {

result.head = q; r = q; q = p;

}

bool ok = false;

//еще не найдено место перецепления

MyNode s = r;

// s — указатель на предыдущий элемент

bool finish = false;

do {

while ((r != null) && !ok) {

//поиск места перецепления

if (r.inf > q.inf)

ok = true;

else {

s = r; r = r.next;

}

}

if (ok) { // перецепляем списки

s.next = q; s = r;

r = q; q = s; s = r; ok = false;

}

else { // дописываем список

s.next = q;

finish = true;

}

}

while (!finish);

}

Дата добавления: 2014-03-11; просмотров: 472; Нарушение авторских прав

Мы поможем в написании ваших работ!