У меня уже есть итерационный алгоритм сортировки слиянием версий для сортировки связанного списка.
Следующая версия хорошо работает в общем случае.
Грубо опишите мой алгоритм:
Я использую кнопку вверх, сначала итерирую, я объединяю 2 узла и 2 узла в 4 узла, которые сортируются и т. Д. ...
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Linked list of elements */
int size;
} queue_t;
void q_sort(queue_t *q)
{
if (!q || !q->head || q->size == 1)
return;
int block_size = 1, n = q->size, i, alen, blen;
list_ele_t virtual_head;
list_ele_t *last = NULL, *it = NULL, *l1 = NULL, *l2 = NULL, *tmp = NULL;
// list_ele_t *l1head = NULL, *l1tail = NULL, *l2tail = NULL;
virtual_head.next = q->head;
while (block_size < n) {
int iter = 0;
last = &virtual_head;
it = virtual_head.next;
while (iter < n) {
// decide each iterate time's block size a and b
alen = min(n - iter, block_size);
// avoid odd block
blen = min(n - iter - alen, block_size);
l1 = it;
l1head = l1;
// if left block is odd, just skip
if (blen != 0) {
// seperate one list in to l1 and l2
for (i = 0; i < alen - 1; ++i)
it = it->next;
l1tail = it;
l2 = it->next;
it->next = NULL;
it = l2;
for (i = 0; i < blen - 1; ++i)
it = it->next;
l2tail = it;
tmp = it->next;
it->next = NULL;
it = tmp;
}
while (l1 || l2) {
if (l2 == NULL ||
(l1 != NULL && strcmp(l1->value, l2->value) < 0)) {
// if l2 doesn't contain any node, just append l1 to
// merge list or if value of l1 is smaller
last->next = l1;
last = last->next;
l1 = l1->next;
} else {
// if l1 doesn't contain any node, just append l2 to
// merge list or if value of l2 is smaller
last->next = l2;
last = last->next;
l2 = l2->next;
}
}
last->next = NULL;
iter += alen + blen;
}
block_size <<= 1;
}
q->head = virtual_head.next;
list_ele_t *nd = q->head;
while (nd->next) {
nd = nd->next;
}
q->tail = nd;
}
Когда этот алгоритм встречается, очень длинный связанный список будет очень медленный, но этот тип тестового стенда имеет определенный формат c, например, имеет несколько повторяющихся разделов. например, AAAAABBBBBBB
В результате я добавляю некоторый код в исходную версию. Я проверяю, совпадают ли члены списка 1 (l1) и списка 2 (l2). Если это так, я пропускаю шаг слияния, просто добавляю l2 к l1
Ниже приводится новая версия:
void q_sort(queue_t *q)
{
long long cnt = 0;
if (!q || !q->head || q->size == 1)
return;
int block_size = 1, n = q->size, i, alen, blen;
list_ele_t virtual_head;
list_ele_t *last = NULL, *it = NULL, *l1 = NULL, *l2 = NULL, *tmp = NULL;
list_ele_t *l1head = NULL, *l1tail = NULL, *l2tail = NULL;
virtual_head.next = q->head;
while (block_size < n) {
int iter = 0;
last = &virtual_head;
it = virtual_head.next;
while (iter < n) {
// decide each iterate time's block size a and b
alen = min(n - iter, block_size);
// avoid odd block
blen = min(n - iter - alen, block_size);
// printf("%d %d block size: %d\n",alen,blen,block_size);
l1 = it;
l1head = l1;
// if left block is odd, just skip
if (blen != 0) {
// seperate one list in to l1 and l2
for (i = 0; i < alen - 1; ++i)
it = it->next;
l1tail = it;
l2 = it->next;
it->next = NULL;
it = l2;
for (i = 0; i < blen - 1; ++i)
it = it->next;
l2tail = it;
tmp = it->next;
it->next = NULL;
it = tmp;
}
if (l1head && l2tail && strcmp(l1head->value, l2tail->value) == 0
&& (l1tail && l2 && strcmp(l1tail->value,l2->value) == 0)) {
iter += alen + blen;
last->next = l1;
l1tail->next = l2;
last = l2tail;
l2tail->next = NULL;
} else {
while (l1 || l2) {
if (l2 == NULL ||
(l1 != NULL && strcmp(l1->value, l2->value) < 0)) {
// if l2 doesn't contain any node, just append l1 to
// merge list or if value of l1 is smaller
last->next = l1;
last = last->next;
l1 = l1->next;
} else {
// if l1 doesn't contain any node, just append l2 to
// merge list or if value of l2 is smaller
last->next = l2;
last = last->next;
l2 = l2->next;
}
}
last->next = NULL;
iter += alen + blen;
}
}
block_size <<= 1;
}
q->head = virtual_head.next;
list_ele_t *nd = q->head;
while (nd->next) {
nd = nd->next;
}
q->tail = nd;
}
Концепция проста, но мое добавление кажется неправильным. Сообщение об ошибке говорит мне, может быть, существует бесконечное число l oop.
Во-первых, мне интересно, есть ли какая-либо ошибка, которую я допускаю, когда добавляю этот раздел? как это исправить?
if (l1head && l2tail && strcmp(l1head->value, l2tail->value) == 0
&& (l1tail && l2 && strcmp(l1tail->value,l2->value) == 0)) {
iter += alen + blen;
last->next = l1;
l1tail->next = l2;
last = l2tail;
l2tail->next = NULL;
}
Во-вторых, есть ли лучший способ ускорить этот специфический c связанный список формата? (например C->C->C->C->B->B.....B)
Спасибо всем вашим советам!