40
правок
Изменения
м
В алгоритме <tex> n </tex> итерации, так как на На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций. ==Пример==Для примера возьмем строку "абракадабра". {| class="wikitable"! Буква || д || к || б || р || а|-| Массив 1 || 1 || 1 || 2 || 2 || 5|-| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>|} На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.{| class="wikitable"| Массив 1 || used || used || 2 || 2 || 5|-| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>|} На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).{| class="wikitable"| Массив 1 || used || used || used || used || 5|-| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>|} На третьем шаге два минимальных элемента - это первые две ячейки второго массива.{| class="wikitable"| Массив 1 || used || used || used || used || 5|-| Массив 2 || deleted || deleted || 6 || <tex>\infty</tex> || <tex>\infty</tex>|} На четвертом шаге складываются две оставшиеся ячейки.{| class="wikitable"| Массив 1 || used || used || used || used || used|-| Массив 2 || deleted || deleted || deleted || 11 || <tex>\infty</tex>|}
sum = int[logMAXN][MAXN+1] // массив, в котором считаем суммы, сначала заполнен "бесконечностями"
s1, s2 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
h1, h2 // указатели на первый элемент первой строки и второй строки соответственно
t1, t2 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
chek s1 = 0, s2 = 1 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма h1 = 0, h2 = 0 // указатели на первый элемент первой строки и второй строки соответственно t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах check = 0 // считает на сколько стало меньше элементов class vert{ // ... чтение данныхкласс - лист дерева, которое, по сути, строится в коде хаффмана '''while''' chek < npublic: val // значение кодового символа {0,1} w // сумма в данном поддереве left // самый левый элемент начального массива в данном поддереве, чтобы упростить поиск при спуске '''while''' h1 < t1 check // проходим по массивупроверка на то, является ли данный лист самым нижним в дереве *nextl, выполняющему роль первого*nextr // указатели на левого и правого детей vert(){ check = 1; val = 0; } }; внутри этого цикла мы ищем минимумы и записываем суммы '''if''' h2 sum = vert[logMAXN][MAXN+1] // элементы w каждой ячейки равны "бесконечности" temp =vert // переменная, на которую ссылаются самые нижние листья дерева temp.check = t2-1 make(int str1, int str2, int pos1, int pos2)// функция, которая суммирует, задает указатели и значения переменных val и left sum[s2][t2] .w = sum[s1str1][h1pos1] .w + sum[s1str2][h1+1pos2].w '''if''' t1 - h1 sum[s2][t2].nextl == 1&sum[str1][pos1] sum[s2][t2] .nextr = &sum[str2][pos2] sum[s2][t2] - .left = min(sum[str1][pos1].left,sum[s1str2][h1+1pos2].left) h1 sum[str1][pos1].val = 0 sum[str2][pos2].val = h1 + 21 coding(sum) t2++ '''while''' check < n '''elsewhile'''h1 < t1 // проходим по массиву, выполняющему роль первого; внутри этого цикла мы ищем минимумы и записываем суммы '''if''' sum[s1][h1] .w < sum[s2][h2].w '''if''' sum[s1][h1+1] .w < = sum[s2][h2].w sum[s2][t2] = sum[ make(s1,s1][,h1] + sum[s1][,h1+1] h1 += 2) '''elseif'''(t2 - h1 == 2) sum[s2][t2] .w -= sum[s1][h1+1] + .w sum[s2][h2t2].nextr = &temp; h1++= 2 h2++ t2++ '''else''' '''if''' sum[ make(s1][,s2,h1] < sum[s2][,h2) h1++1] sum[s2][t2] = sum[s2][ h2] + sum[s1][h1] h1++ h2 t2++
'''if''' sum[s2s1][t2h1] = .w < sum[s2][h2+1] .w make(s2,s1,h2,h1) h1++ h2++ sum[ '''else''' make(s2,s2][,h2,h2+1]) h2+=2 t2++ chek check++ // учитываем то, что элементов стало на 1 меньше s1 = s2 // строки меняются ролями, соответственно все их параметры тоже h1 = h2 t1 = t2 s2++ h2 = t2 = 0 return sum[s1][h1] // возвращает вершину дерева, получить код каждого символа можно получить за logn
→Пример
В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива.Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
==Реализация==
Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".
n // количество элементов
'''else'''
