Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: сортировка связного списка
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему > Программирование
Sneg_87
Структура TMyRect хратит координаты прямоугольников и их площади. Указатель на структуру представляется в виде связного списка. В *R0 записываются координаты прямоугольников прочитанных из файла. *X0 по размеру одинаков с *R0, но пустой - в него и нужно записать отсортированный список *R0. Сколько не пытался - ну никак не получается.
Отсортировать нужно по параметру S(площадь).

Код
struct TMyRect {
int x1,y1,x2,y2;
int S;
TMyRect *point; //point=next
};
TMyRect *R0 = NULL, *Rnew, *Rold, *tmp;//несортированный список
TMyRect *X0 = NULL, *Xnew, *Xold;//сортированный список

void sortirovka () {
//сортировка
Rnew=R0;
Xnew=X0;

while (Rnew!=NULL) {
for (Xnew=X0;Xnew->point!=0;Xnew=Xnew->point) {
  if (Rnew->point->S > Rnew->S) break;        }
  Rnew->point=Xnew->point; Xnew->point=Rnew;

Rnew=Rnew->point;
}
//конец сортировки
}
AHTOXA
Цитата(Sneg_87 @ Mar 5 2010, 09:49) *
Сколько не пытался - ну никак не получается.

Код
void sortirovka ()
{
    Rnew=R0;
    Xnew=X0;    // --- заменить вот это
    X0 = R0;    // --- на вот это. А то X0 как был 0, так и остаётся.
...
}
Sneg_87
Цитата(AHTOXA @ Mar 5 2010, 11:16) *
Код
void sortirovka ()
{
    Rnew=R0;
    Xnew=X0;    // --- заменить вот это
    X0 = R0;    // --- на вот это. А то X0 как был 0, так и остаётся.
...
}


программа подвисает
AHTOXA
Цитата(Sneg_87 @ Mar 5 2010, 11:42) *
программа подвисает


Хм. Там оказывается весьма нетривиально всё. Прежде чем добавлять элемент в сортированный список, его нужно изъять из несортированного. И не забыть изначально добавить 0 в конец сортированного списка.

Короче, вот тестовая программа:
CODE

#include <stdio.h>
#include <stdint.h>

struct point
{
int x1;
point *next;
};

point *unsorted;
point *sorted;

point p1 = {68};
point p2 = {3};
point p3 = {4};
point p4 = {8};
point p5 = {10};
point p6 = {12};
point p7 = {43};
point p8 = {6};
point p9 = {58};

void print_points(char * name, point * arr)
{
printf("%s : ", name);
while (arr)
{
printf("%d, ",arr->x1);
arr = arr->next;
}
}

void fillpoints()
{
unsorted = &p1;
p1.next = &p2;
p2.next = &p3;
p3.next = &p4;
p4.next = &p5;
p5.next = &p6;
p6.next = &p7;
p7.next = &p8;
p8.next = &p9;
p9.next = 0;
}

void sort_points()
{
point * run;
point * tmp;
point * nxt;

// присваиваем начальное значение сортированному списку.
sorted = unsorted;

// изымаем этот элемент из несортированного списка
run = unsorted->next;

// не забываем терминатор для сортированного списка
sorted->next = 0;

// перебираем несортированный список, начиная со второго элемента:
while (run)
{
// запоминаем следующий элемент, потому что мы испортим его при вставке:
nxt = run->next;

// для первого элемента сортированного массива - особая проверка:
if (run->x1 < sorted->x1)
{
// если run меньше чем первый элемент сортированного списка,
// то вставляем его в начало списка, и не забываем
// переназначить переменную sorted:
run->next = sorted;
sorted = run;
run = nxt;
continue;
}

// теперь пробегаемся по сортированному массиву
// до первого элемента, следующий за которым больше чем run:
for (tmp = sorted; tmp->next; tmp = tmp->next)
if (tmp->next->x1 > run->x1) break;

// и вставляем run следом за tmp:
run->next = tmp->next;
tmp->next = run;
run = nxt;
}
}



int main(void)
{
fillpoints();

print_points("unsorted", unsorted);

sort_points();

print_points("sorted", sorted);
}
AHTOXA
Или даже вот так:
Код
// удалить первый элемент из списка
point * cut_item(point **list)
{
    if (*list)
    {
        point * item = *list;
        *list = item->next;
        item->next = 0;
        return item;
    }
    return 0;
}

// вставить элемент item в список list (с учётом сортировки)
void put_item(point **list, point * item)
{
    // пустой список
    if (*list == 0)
    {
        *list = item;
        item->next = 0;
        return;
    }

    // новая голова
    if (item->x1 < (*list)->x1)
    {
        item->next = *list;
        *list = item;
        return;
    }

    // обычная вставка
    point *p;
    for(p = *list; p->next; p=p->next)
        if (p->next->x1 > item->x1) break;
    item->next = p->next;
    p->next = item;
}

void sort_points()
{
    point *p;
    sorted = 0;
    while ((p=cut_item(&unsorted)))
        put_item(&sorted, p);
}
Sneg_87
Спасибо, AHTOXA, за ответы!
Меня интересует еще такой вопрос:
создается список указателей на структуру (Rnew = new TMyRect). как вернуться к указателю на первый элемент,когда нет указателя на начало?
AHTOXA
Если нет указателя на начало, то никакsmile.gif
Поэтому надо обязательно хранить указатель на начало.

Есть ещё вариант - закольцевать список, то есть, вместо NULL хранить у последнего элемента указатель на первый. Тогда, зная один любой элемент списка, мы можем перебрать весь список.
Sneg_87
Ситуация такая получается, что в Borlande dos'овском вывод значений списка начинается с начала, хоть его и нет. То есть указатель на сортированный список это поидее порвый элемент списка. Ну а Bilder'e мне выходит последний элемент списка, а откат на первое значение получается никак нельзя сделать >_<
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.