Сортировка односвязных списков

← →
tesseract © (2007-09-13 15:48) [40]

> а что лучше, завести несколько переменных (как в сортировке
> выборкой или вставками) но вроде короче цикл; или обходиться
> двумя переменными, но долго перебирать?

Кнут вроде рекомендует заводить вспомогательный массив как раз для ускорения доступа к элементам массива.

← →
Галинка © (2007-09-13 15:51) [41]

Я имею в виду, что экономнее/быстрее/удобнее использовать несколько переменных и мало проходов цикла, или одну переменную и много проходов цикла?

← →
Галинка © (2007-09-13 15:53) [42]

tesseract © (13.09.07 15:48) [40]

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

← →
clickmaker © (2007-09-13 15:56) [43]

> экономнее/быстрее/удобнее

эти три понятия мало сочетаются друг с другом
везде разумный компромисс нужен

← →
Галинка © (2007-09-13 16:07) [44]

Хэширование это из этой же оперы?

← →
clickmaker © (2007-09-13 16:10) [45]

> [44] Галинка © (13.09.07 16:07)

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

← →
Галинка © (2007-09-13 16:13) [46]

Если кто-то может показать пример с использование массива ссылок на элементы массива буду очень благодарна.

← →
iam (2007-09-13 16:17) [47]

Галинка © (13.09.07 16:13) [46]
объясни подробней what you want)

← →
Sandman31 (2007-09-13 16:21) [48]

clickmaker © (13.09.07 15:56) [43]

"Быстро, дешево, хорошо - выберите любые два" :)

← →
Eraser © (2007-09-13 16:37) [49]

> Галинка © (13.09.07 16:13) [46]

http://www.natahaus.ru/2005/11/08/fundamentalnye_algoritmy_i_struktury_dannyh_v_delphi.html

← →
Сергей М. © (2007-09-13 16:38) [50]

> Галинка © (13.09.07 16:13) [46]

А что непонятно ?

← →
Сергей М. © (2007-09-13 16:39) [51]

> массива ссылок на элементы массива

Массива ссылок на элементы списка !

ты же о списке ведешь речь)

← →
Галинка © (2007-09-13 16:47) [52]

Сергей М. © (13.09.07 16:39) [51]

Объяснить подробней можно? Или статью какую почитать, где человеческим языком с примером (для домохозяек) написано?

← →
Romkin © (2007-09-13 16:54) [53]

Хочешь освоить список?
http://www.delphimaster.ru/articles/dsort/index.html
:-P

← →
Zeqfreed © (2007-09-13 16:55) [54]

> Галинка © (13.09.07 16:47) [52]

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

← →
Галинка © (2007-09-13 17:01) [55]

Zeqfreed © (13.09.07 16:55) [54]

Пасиб. А как организуется массив ссылок на элементы массива? И как быть, если список часто меняется? Все время актуализировать массив? И сколько под него выделять памяти? Или всегда с запасом, а использовать только столько, сколько надо?

← →
Сергей М. © (2007-09-13 17:02) [56]

> Объяснить подробней можно?

Объяснить что ?

Давай уже подробно, в порядке следования "непониманий", от простого к сложному ..

← →
Zeqfreed © (2007-09-13 17:08) [57]

> Галинка © (13.09.07 17:01) [55]

Массив строится тогда, когда он нужен. Разумеется, он должен отражать актуальное состояние списка для корректных результатов. Все зависит от задачи. Если доступ по индексу нужен все время, то удобней, видимо, будет обновлять массив при каждой модификации списка. А если только для сортировки, то хватит и временного массива.

← →
Галинка © (2007-09-13 17:09) [58]

Есть список из структур struct node{int val; struct node *next} (в соответствие со связанным хранением). Значения полей val структур в списке, например {5, 7, 4, 6, 3, 9, 8, 2, 1}. Как создать ("ключевой") массив? И как ждементы массива будут собственно связаны с узлами списка?

← →
Галинка © (2007-09-13 17:10) [59]

Zeqfreed © (13.09.07 17:08) [57]

т.е. в процедуре сортировки и можно создать этот массив? И как его создать?

← →
tesseract © (2007-09-13 17:11) [60]

> Как создать ("ключевой") массив? И как ждементы массива
> будут собственно связаны с узлами списка?

Ссылки на узлы списка в массиве будут. Это же базовая алгоритмика первого курса!!!!!

← →
Игорь Шевченко © (2007-09-13 17:12) [61]

Дешево/Хорошо/Быстро

Выберите любые два

← →
Zeqfreed © (2007-09-13 17:12) [62]

> Галинка © (13.09.07 17:10) [59]

Ну, вероятно, выделить память под него. И пройдя в цикле по списку заполнить массив.

> Как создать ("ключевой") массив? И как ждементы массива
> будут собственно связаны с узлами списка?

Каждый элемент массива должен содержать указатель на соотв.структуру node, т.е. элементы массива должны иметь указательный тип.

Для получения доступа к соотв. элементу ориг.списка из процедуры сортировки нужно просто разыменовать соотв. ему указатель из этого массива.

т.е. получится что-то типа struct node *keys[100], и соответственно:
struct node *start; //ссылка на начало списка struct node *keys[100]; //массив ссылок на элементы списка struct node *list = start; int j, i = 0; while (list != NULL){ keys[i] = list; list = list->next; i++; } // заполнение массива ссылок
а как теперь с сортировкой?

#include <stdio.h> #include <stdlib.h> #define RANDOM_RANGE(a, b) 1 + (int) (b * (rand() / (RAND_MAX + a))) struct Node { int value; struct Node *next; }; static struct Node head = {0, 0}; static int len = 0; static void append(int value) { int i = len; struct Node *node = &head; struct Node *new = (struct Node *) malloc(sizeof(struct Node)); while (i--) node = node->next; new->value = value; new->next = 0; node->next = new; len++; } static void sort() { struct Node **els = malloc(sizeof(struct Node) * len); struct Node *node = &head; int i = 0; while (node = node->next) els[i++] = node; int swapped = 1; struct Node *tmp; while (swapped) { swapped = 0; for (i = 1; i < len; i++) { if (els[i - 1]->value > els[i]->value) { tmp = els[i]; els[i] = els[i - 1]; els[i - 1] = tmp; swapped = 1; } } } printf("sorted: "); for (i = 0; i < len; i++) printf("%d ", els[i]->value); printf("\n"); } int main(int argc, char **argv) { srand(time(0)); int i = 10; while (i--) append(RANDOM_RANGE(0.0, 100.0)); sort(); struct Node *node = &head; printf("original: "); while (node = node->next) printf("%d ", node->value); printf("\n"); return 0; }

Спасибо. Попробую. Почитаю.

← →
iam (2007-09-14 10:10) [67]

using System; using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //формирование связного списка LinkedList<Person> linkedList = new LinkedList<Person>(); linkedList.AddLast(new Person(3, "Петя", "Петечкин")); linkedList.AddLast(new Person(2, "Вася", "Васечкин")); linkedList.AddLast(new Person(1, "Гоша", "Гошечкин")); //отображение содержимого связного списка LinkedListNode<Person> node = linkedList.First; while (node != null) { Console.WriteLine(node.Value.ToString()); node = node.Next; } Console.WriteLine(); //формирование обычного списка на основе связного и его сортировка на основе //функции сравнения представляемой классом PersonComparer List<Person> list = new List<Person>(); foreach (Person p in linkedList) list.Add(p); list.Sort(new PersonComparer()); //очистка и затем заполнение связного списка из отсортированного обычного списка linkedList.Clear(); foreach (Person p in list) linkedList.AddLast(p); //отображение содержимого связного списка foreach (Person p in linkedList) { Console.WriteLine(p.ToString()); } Console.ReadLine(); } } public class Person { public Person(int id, string firstName, string lastName) { this.id = id; this.firstName = firstName; this.lastName = lastName; } public int id; public string firstName; public string lastName; public override string ToString() { return id.ToString() + " " + firstName + " " + lastName; } } public class PersonComparer : IComparer<Person> { public int Compare(Person person1, Person person2) { if (person1.id < person2.id) return -1; if (person1.id > person2.id) return 1; return 0; } } }
вот тебе ещё пример;)

> [67] iam (14.09.07 10:10)

щас будет
"Четвертый раз в этом топике говорю, я пишу сейчас на чистом СИ!!! Даже без ++."
:)

← →
iam (2007-09-14 10:25) [69]

clickmaker © (14.09.07 10:17) [68]
и она походу этим гордится)))
я ей тем более предложил книгу по алгоритмам и структурам данных на C#
отказалась почему-то) ну хочет возиться с C пусть возится)
"чистый Си" звучит прямо с какой-то гордостью у неё;)

> "чистый Си" звучит прямо с какой-то гордостью у неё;)

Лаба такая.

> tesseract (14.09.2007 12:53:10) [70]

Карма

Шеф сказал, что на простом Си. Без объектов. Тем более что проект ведется с 2001 года. Работает туева хуча людей. И что им теперь всем на шарп переходить? Да еще и винду в кассы засовывать?

iam, в шарпе я пользовала ArrayList. Это и список и массив одновременно. Т.е. обладает свойствами и того и другого. Там вообще было все просто, там был Sort. И я его успешно применяла. Но теперь нет ни шарпа, ни даже ООП.

Спасибо Zeqfreed © (13.09.07 17:46) [65]. Разобралась вроде.

Сортировка односвязных списков Найти похожие ветки