Как отсортировать односвязный список?
Есть идеи как можно реализовать сортировку внутри класса односвязного списка?
class LinkedListNode < //создание переменной Value в которой будет храниться значение public T Value; // Следущий узел public LinkedListNodeNext; public LinkedListNode(T value, LinkedListNode next = null) < Value = value; Next = next; >>class LinkedList where T : IComparable < private LinkedListNode_head; private LinkedListNode _tail; private int _count; //создание свойства "колво элементов" public int Count < get < return _count; >> public LinkedListNode Current < get < return _head; >> public LinkedList() < >/* вырезаный блок кода с разными методами добавления у даления элементов */ public void Sort () < // . >>Вот пример кода сортировки массива чисел, желательно, чтобы сортировка была этим же методом, но только внутри класса:
for (int i = 0; i < intArray.Length; i++) < int minID = i; for (int j = i; j < intArray.Length; j++) if (intArray[minID] >intArray[j]) minID = j; int temp = intArray[i]; intArray[i] = intArray[minID]; intArray[minID] = temp; >- Вопрос задан более двух лет назад
- 859 просмотров
Как отсортировать односвязный список на Си?
Всем доброго времени суток)) Задача следующая: «Ввести предложения на русском в односвязный список, организованный в виде очереди (в списке должны храниться только адреса, а сами предложения размещаться в памяти отдельно). Определить предложение, в котором используется наибольшее количество различных букв русского алфавита, и сделать это предложение первым в списке. И исключить из списка предложение, в котором меньше всего различных букв. Разработать функцию, определяющую количество различные буквы, используемые в данной строке символов». Прошу помощи с двумя пунктами:
1)Посмотрите функцию int CountAlpha() для поиска количества разных букв и скажите точно ли с ней все ок
2)Помогите с реализацией алгоритма сортировки односвязного списка по кол-ву разных букв в предложении(опять же предложения на русском языке). Хотя бы дайте наводку как и что нужно делать Всем заранее спасибо за помощь 🙂 Код:
#include #include #include #include #define LMES 80 typedef struct inform < // структура данных int index; char message[LMES]; >INFORM; typedef struct list_elem < // структура элемента списка INFORM inform; struct list_elem* next; >LEL; void MakeList(void); // прототипы функций LEL* AddElem(LEL* last); void PrintList(void); int CountAlpha(); LEL* Sort(); void FreeList(void); LEL* list; // указатель на начало списка void main(void) < setlocale(LC_ALL, "rus"); system("chcp 1251"); MakeList(); // формирование списка PrintList(); // печать сформированного списка FreeList(); // освобождение ДП >// Функция формирования списка-очереди void MakeList(void) < puts("\n Входные данные (для завершения индекс - 0):\n"); LEL* list_end = NULL; // указатель на последний элемент списку do < list_end = AddElem(list_end); >while (list_end != NULL);// цикл формирования списка > // Функция добавления нового элемента до хвоста списку LEL* AddElem(LEL* last) < LEL* pel; // указатель на новый элемент static int num = 1; // номер элемента, который вводиться pel = (LEL*)malloc(sizeof(LEL)); // выдиление ДП для элемента if (pel == NULL) < puts("\n Нет больше свободной памяти. \n Формирование списка завершено."); return NULL; // нет свободной ДП >printf("\n %d элемент: \nИндекс - ", num); scanf_s("%d", &pel->inform.index); rewind(stdin); if (pel->inform.index == 0) < // конец введения free(pel); return NULL; >printf("Предложение: "); gets_s(pel->inform.message); pel->next = NULL; // элемент будет последним в списке if (list == NULL) // если это первый элемент list = pel; // делаем его головой списка else last->next = pel; // иначе добавляем к последнему в списке num++; return pel; > // Функция вывода на экран списка void PrintList(void) < LEL* pel = list; int n = 0; puts("\n\n\t Сформированный список:\n"); while (pel != NULL) < printf(" %d)%7d\t%-.65s\n", ++n, pel->inform.index, pel->inform.message); pel = pel->next; > > // Функция нахождения кол-ва уникальных букв в предложениях int CountAlpha() < LEL* pel = list; char* p1, * p2; int count = 0, saveCount = 1; p1 = pel->inform.message; while (pel != NULL) < for (p1; *p1 != '\0'; p1++) < p2 = p1++; for (p2; *p2 != '\0'; p2++) < if (*p2 == *p1) < saveCount = 0; >count += saveCount; > > return count; pel = pel->next; > > LEL* Sort() < . >// Функция стирания всего списка void FreeList(void) < LEL* pel = list; while (pel != NULL) < list = list->next; // первым в списке становится следующий элемент free(pel); // удаление поточного элемента pel = list; > puts("\n\n Список вытерт. \n"); > Отслеживать
задан 14 мая 2022 в 18:48
user494534 user494534
14 мая 2022 в 21:23
Нарушено требование задачи «в списке должны храниться только адреса». Вы храните сами фразы, не их адреса.
15 мая 2022 в 8:26
В задаче не требуется упорядочивать список. Требуется только переставить самое «богатое» предложение первым. Это в десять раз проще сортировки.
15 мая 2022 в 8:34
Скорее всего от вас хотят чтобы вы динамически выделяли память под предложения в структуру списка struct list_elem < char* message; list_elem* next; >
2301. (Односвязный линейный список) Слияние двух сортированных списков
(Односвязный линейный список) Слияние двух сортированных списков
Учебные задачи: алгоритмы и структуры данных
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
2 отсортированных списка с головами Head1, Head2
Нужно слить в один сортированный список.
Напишите процедуру слияния.
Используйте следующий шаблон:
#include #include using namespace std; struct NODE< int Number; NODE *Next; >; NODE * MakeList(int*, int); NODE *JoinTwoList(NODE*, NODE*); int main()< int Arr1[]=; int Arr2[]=; NODE *Head1, *Head2; Head1=MakeList(Arr1,sizeof(Arr1)/sizeof(int)); Head2=MakeList(Arr2,sizeof(Arr2)/sizeof(int)); NODE *Head = JoinTwoList(Head1, Head2); cout for(NODE* p1=Head->Next; p1!=NULL; p1=p1->Next) < cout " Number; > return 0; > NODE *JoinTwoList(NODE *Head1, NODE *Head2) < //Выполнить слияние списков с головами Head1 и Head2 // Функция возвращает указатель на голову списка, // являющегося результатом слияния // . > NODE * MakeList(int Arr[], int n) < //Эта функция создаёт один список // Arr - массив чисел, которые должны быть помещены в список // n - их количество NODE *Head=new NODE,*x; Head->Next=NULL; //Явно указываем на NULL Head->Number=INT_MAX; // Условное значение головы x=Head; // Создание собственно списка for (int i = 0; i < n; i++) < x->Next=new NODE; x=x->Next; x->Number=Arr[i]; x->Next = NULL; > return Head; >
Сортировка односвязного списка
Здравствуйте уважаемые киберфорумщики!
Нужна срочная помощь.
В общем у меня есть задача которую нужно сделать но нет ни знаний ни времени на изучение сего вопроса.
Поэтому прошу помочь мне с этим знающих людей. Желательно с объяснениями)
Построить класс для работы с односвязным списком. Элементы списка — целые числа. сформировать
список, упорядочить элементы списка по возрастанию, используя сортировку: a) методом
выбора, б) методом пузырька, в) методом вставки.
Лучшие ответы ( 1 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Сортировка односвязного списка
Доброго времени суток. Третий день пытаюсь понять как мне отсортировать сведения структуры.
Сортировка односвязного списка
Помогите пишу курсач сделал все ф-ции кроме сортировки в голову не приходит как что не пробовал без.
Сортировка односвязного списка
Прошу сразу не ругаться ,знаю что на форуме миллион разных кодов сортировки ,но я не понимаю как их.
Сортировка односвязного списка
Добрый день форумчанам! Есть задача но не знаю как написать ее так как не знаю динамического.
Почетный модератор
5850 / 2861 / 392
Регистрация: 01.11.2011
Сообщений: 6,907
Для нахождения остальных десяти тысяч тем, воспользуйтесь поиском по форуму: поиск по форуму.
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
Сообщение было отмечено taiggerrock как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
#include #include struct node { node* next; int val; }; class slist { private: node* lst; size_t cnt; public: slist(void); ~slist(); bool add(int val); void clear(void); void isort(void); void bsort(void); void ssort(void); size_t size(void) const { return cnt; } bool empty(void) const { return (lst == NULL); } node* begin(void) const { return lst; } node* begin(void) { return lst; } }; void slist_print(std::ostream& _out, const slist& lst); int main(void){ int n; slist l1, l2, l3; for(int i = 0; i 32; ++i){ n = rand() % 10; l1.add(n); l2.add(n); l3.add(n); } l1.bsort(); l2.ssort(); l3.isort(); slist_print(std::cout, l1); slist_print(std::cout, l2); slist_print(std::cout, l3); return 0; } slist::slist(void):lst(NULL), cnt(0){} slist::~slist(){ clear(); } //Сортировка вставками void slist::isort(void){ node* a, *b, *p, *h = NULL; for(node* i = lst; i != NULL; ) { a = i; i = i->next; b = h; for(p = NULL; (b != NULL) && (a->val > b->val); ) { p = b; b = b->next; } if(p == NULL){ a->next = h; h = a; } else { a->next = b; p->next = a; } } if(h != NULL) lst = h; } //Пузырьковая сортировка void slist::bsort(void){ node* t, *m, *a, *b; if(lst == NULL) return; for(bool go = true; go; ){ go = false; a = t = lst; b = lst->next; while(b != NULL){ if(a->val > b->val){ if(t == a) lst = b; else t->next = b; a->next = b->next; b->next = a; m = a, a = b, b = m; go = true; } t = a; a = a->next; b = b->next; } } } //Сортировка выбором void slist::ssort(void){ node* a, *b; node* p1, *p2, *r1, *r2; for(p1 = r1 = lst; p1 != NULL; p1 = p1->next){ a = p2 = r2 = p1; for(b = p1->next; b != NULL; b = b->next){ if(b->val p2->val){ r2 = a; p2 = b; } a = b; } if(p1 != p2){ if(p1 == lst) lst = p2; else r1->next = p2; b = p2->next; if(p1 == r2){ p2->next = p1; p1->next = b; } else { a = p1->next; r1->next = p2; r2->next = p1; p1->next = b; p2->next = a; } p1 = p2; } r1 = p1; } } //добавление bool slist::add(int val){ node* p = new (std::nothrow) node(); if(p != NULL){ p->val = val; p->next = lst; lst = p; ++cnt; } return (p != NULL); } //удаление всех void slist::clear(void){ node* t; while(lst != NULL){ t = lst; lst = lst->next; delete t; } cnt = 0; } //печать void slist_print(std::ostream& _out, const slist& lst){ for(const node* p = lst.begin(); p != NULL; p = p->next) _out - >val <' '; _out :: endl; }