Developing.ru

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

[Syntax="C#"]

public class Spisok
{
public class Node //структура элемента списка
{
public string Name;
public string Type;
public string Value;

public Node Next;
}

public Node First = new Node(); //первый элемент
Node Now; //текущий элемент

public Spisok() //конструктор по-умолчанию
{
First.Name = null;
First.Type = null;
First.Value = null;

Now = First;

}

public void Add(string name, string type, string value) //добавление элемента
{
Now = First;
do
{
if (Now.Name == null) { Now.Name = name; Now.Type = type; Now.Value = value; Now.Next = new Node(); }
else
{
Now = Now.Next;
}

} while (Now.Name != name);
}


public void Out(Node T) //обход дерева
{
if (T.Name != null) { Console.Write(T.Name.TrimEnd(':') + " ") ; Console.Write(T.Type + " "); Console.WriteLine(T.Value); }
if (T.Next != null) { Out(T.Next); }
}

...
}

[/Syntax]

Есть и другие методы, но не в этом суть...

Никак не могу добавить вменяемо работающую процедуру сортировки... Помогите, кто чем может... ;-) Заранее благодарен.

Мне, главное, увидеть бы реализацию. Не обязательно на шарпе.. ((

поюзай интернет!!! Там должна быть инфа на такую тему!!!

Для успешной сортировки, прежде всего, нужно определиться с функией сравнения узлов списка (объектов типа Node).

StarWorm писал(а):поюзай интернет!!! Там должна быть инфа на такую тему!!!

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

Albor писал(а):Для успешной сортировки, прежде всего, нужно определиться с функией сравнения узлов списка (объектов типа Node).

Ну сортировка должна происходить по полю Name. Для сравнения я предполагал использовать функцию CompareTo().

Alex_Burn писал(а):Ну сортировка должна происходить по полю Name. Для сравнения я предполагал использовать функцию CompareTo().

Думаю, дальнейшие действия примерно такие: Пройтись по списку некоторое количество раз, пока, после прохода, не будет сделано перестановок. Перестановка будет заключаться в переписывании указателя Next (я не пишу на C#, поэтому могу ошибаться в терминах - там, по-моему нет указателей, но, наверное, смысл понятен).

Если нужно сортировать "на месте", то надо сначала научиться переставлять местами 2 элемента:

previous - это предыдущий элемент перед обмениваемыми (curr и nxt)
curr=previous.next; nxt:=curr.next;

previous.next=nxt;
curr.next=nxt.next; //правильно стаботает даже если curr и nxt это последние 2 элемента
nxt.next=curr;

Итого надо переставить 3 указателя.

Ну а теперь можно попробовть метод пузырька как в предыдущем посте.
Попарно сравниваем и если надо, переставляем.

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

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

Прошу прощения, а нельзя ли на конкретном маленьком примерчике?