Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.86
kracav4eg
1 / 1 / 0
Регистрация: 08.05.2009
Сообщений: 11
#1

Сортировка списка распределением - C++

08.05.2009, 20:07. Просмотров 2644. Ответов 8
Метки нет (Все метки)

(сортировка распределением) Упорядочить список Q двадцатибуквенных слов в алфавите П= {A,B,C} лексикографически ( т.е. так, как это принято в словарях) , используя следующий алгоритм :
1. Образуем 3 (сначало пустых) вспомогательных очереди Qa, Qb, Qc. Положим i=20.
2. Просматривая список Q , будем помещать очередное слово в очередь Qx , если i-ая буква слова равна x (x є П).
3. Сцепим очереди Qa, Qb, и Qc : к Qb присоединим Qc , к Qa – Qb . Это будет новый список Q .
4. Шаги алгоритма 2 и 3 последовательно повторим для I = 19, 18, … ,I. В результате будет получен искомый упорядоченный список Q.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2009, 20:07     Сортировка списка распределением
Посмотрите здесь:

Подкорректировать код (сортировка распределением) - C++
Вечер добрый, знатоки. Компилятор ошибку не отлавливает. Ошибка логическая и вылет программы происходит при входе в цикл: while (j > (l...

Сортировка методом каскадного слияния со специальным распределением - C++
Задание - реализовать этот алгоритм для однмоерного динамического массива. попытки почитать Кнута успехом не увенчались - не понятно. Буду...

Сортировка списка - C++
помогите сделать сортировку по возрасту, а то ничего не выходит #include <iostream> #include <conio.h> using namespace std; struct...

Сортировка списка - C++
Люди помогите плиз я уже не могу!! надо сортировать список!!! Останьные недоработки тоже можете указать. Вот код Жду ответов) ...

Сортировка списка - C++
Здравствуйте!!! Прошу помочь мне написать алгоритм сортировки односвязного списка. Задание такое: необходимо из элементов трёх списков...

Сортировка списка - C++
Всем привет задание такое Разработать программу работы со связным списком сеансов в кинотеатре. Для каждого сеанса должна храниться...

Сортировка списка - C++
Народ нужна помощь :) Элементы списка представлены следующим образом: class Node { public: char *name; Node *next; ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fantaz1
33 / 25 / 1
Регистрация: 08.11.2008
Сообщений: 107
09.05.2009, 10:18     Сортировка списка распределением #2
Ну так что у тебя не получается??? Покажи в чем проблема?
kracav4eg
1 / 1 / 0
Регистрация: 08.05.2009
Сообщений: 11
10.05.2009, 21:06  [ТС]     Сортировка списка распределением #3
ок , покажу свой код..пока не за своим компом

Добавлено через 22 часа 48 минут 48 секунд
C++
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
#include <iostream>
using namespace std;
struct Node{
       Node* next;
       char abc[20];
       };
 
       void sort(Node*& Q,Node* Q1,Node* Q2,Node* Q3,int i)  {
                          Node *q=Q;
                          Node *q1=Q1;
                          Node *q2=Q2;   // указатели сохраняем начальные
                          Node *q3=Q3;
                                while(q!=NULL){
                                         if(q->abc[i]=='a'){
                                         for(int j=0;j<20;j++)
                                        Q1->abc[j]=q->abc[j];
                                        Q1->next=new Node;           // тут сравниваем , если буква списка Q равна а,b или c : заносим в соответвующий список
                                        Q1=Q1->next;
                                        }
 
                                        else
 
                                        if(q->abc[i]=='b'){
                                        for(int l=0;l<20;l++)
                                        Q2->abc[l]=q->abc[l];
                                        Q2->next=new Node;
                                        Q2=Q2->next;
                                        }
 
                                        else
 
                                        if(q->abc[i]=='c'){
                                        for(int m=0;m<20;m++)
                                        Q3->abc[m]=q->abc[m];
                                        Q3->next=new Node;
                                        Q3=Q3->next;
                                        }
 
                       q=q->next;
                       }
                       Q3->next=NULL;
 
                       Q->next=q1;
                       Q1->next=q2;        // тут мы  меняем указатели.. и делаем список упорядоченный для i буквы
                       Q2->next=q3;
 
 
                       }
int main()
{
 
    Node * Q  = new Node;
    Node * Q1 = new Node;           //создаем начальные списки
    Node * Q2 = new Node;
    Node * Q3 = new Node;
    Node* top = Q;
      int n;
     cin>>n;
     cout<<endl;
     for(int k=0;k<n;k++){
    cin>>top->abc;                 // тут вводим слова в список Q
    top->next=new Node;
    top=top->next;}
 
    top->next=NULL;
 
    for(int s=19;s>=0;s--)
    sort(Q,Q1,Q2,Q3,s);   //вызываем функцию
 
    while(Q!=NULL)     {
    cout<<Q->abc<<'\n';   // выводим упорядоченный список
    Q=Q->next;
                       }
 
 
return 0;
}
Добавлено через 4 минуты 11 секунд
у меня после ввода слов, вылетает windows ошибка
kracav4eg
1 / 1 / 0
Регистрация: 08.05.2009
Сообщений: 11
12.05.2009, 20:53  [ТС]     Сортировка списка распределением #4
никто не знает? где я мог допустить ошибку в коде?
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
12.05.2009, 21:17     Сортировка списка распределением #5
как еще называеться эта сортировка?
просто у меня есть готовые функции для сортировок:
пузырьком
сортировка по средством выбора
сортировка вставками
сортировка шела
быстрая сортировка (qsort -ее исходник)

а так же сортировки для строк и не оч сложных структур
kracav4eg
1 / 1 / 0
Регистрация: 08.05.2009
Сообщений: 11
13.05.2009, 14:51  [ТС]     Сортировка списка распределением #6
(сортировка распределением). У меня дан алфавит из 3 букв... и слова тоже составлены из букв(1 слово= 20 букв) ..сортировка заключается в проверке с 20 буквы( сначало сортируем для 20), а потом идем дальше 19...1.

Добавлено через 16 часов 51 минуту 34 секунды
после компиляции , после введения слов ...вылетает ошибка Windows....я думаю где то идет утечка памяти или залезаю в чужую память или зацикливается

никто не знает где я мог напортачить??
Prolol
0 / 0 / 0
Регистрация: 24.11.2010
Сообщений: 4
24.11.2010, 22:50     Сортировка списка распределением #7
Цитата Сообщение от Акелла Посмотреть сообщение
как еще называеться эта сортировка?
просто у меня есть готовые функции для сортировок:
пузырьком
сортировка по средством выбора
сортировка вставками
сортировка шела
быстрая сортировка (qsort -ее исходник)

а так же сортировки для строк и не оч сложных структур
Будь добр выложи код сортировки для сторк%)
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
25.11.2010, 00:14     Сортировка списка распределением #8
Цитата Сообщение от Prolol Посмотреть сообщение
Будь добр выложи код сортировки для сторк%)
да не вопрос=)))

C
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
/* быстрая сортировочка срочек ^_^. */
void quick_string(char items[][10], int count)
{
  qs_string(items, 0, count-1);
}
 
void qs_string(char items[][10], int left, int right)
{
  register int i, j;
  char *x;
  char temp[10];
 
  i = left; j = right;
  x = items[(left+right)/2];
 
  do {
    while((strcmp(items[i],x) < 0) && (i < right)) i++;
    while((strcmp(items[j],x) > 0) && (j > left)) j--;
    if(i <= j) {
      strcpy(temp, items[i]);
      strcpy(items[i], items[j]);
      strcpy(items[j], temp);
      i++; j--;
   }
  } while(i <= j);
 
  if(left < j) qs_string(items, left, j);
  if(i < right) qs_string(items, i, right);
}
пример использования:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>
 
void quick_string(char items[][10], int count);
void qs_string(char items[][10], int left, int right);
 
char str[][10] = { "one",
                   "two",
                   "three",
                   "four"
                 };
 
int main(void)
{
  int i;
 
  quick_string(str, 4);
 
  for(i=0; i<4; i++) printf("%s ", str[i]);
 
  return 0;
}
если нужны комментарии к коду - пиши. Исходники взяты у Шилдта.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.11.2010, 11:22     Сортировка списка распределением
Еще ссылки по теме:

Сортировка списка - C++
Дан список сел и расстояния до них от города. Нужно вывести села в порядке удаленности от города. Городов до 10^8. Расстояния - целые...

Сортировка списка - C++
Приветствую всех! Есть небольшая проблема: не могу понять, как создать сортировку в алфавитном порядке. Вот код: void SortList() { ...

Сортировка списка - C++
Привет, всем.. Ребята помогите у подруги зачет по программированию ей надо решить задачку.. Информационное поле элемента...

Сортировка списка - C++
Всем привет) Нужно реализовать сортировку списка, линейного однонаправленного. Написал, но что-то как-то не правильно... void...

Сортировка списка - C++
Здравствуйте, не совсем понимаю как должна быть реализована сортировка вставками в деке. Что имеется на данный момент: class List...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Prolol
0 / 0 / 0
Регистрация: 24.11.2010
Сообщений: 4
25.11.2010, 11:22     Сортировка списка распределением #9
блин.. что то не выходит..
Yandex
Объявления
25.11.2010, 11:22     Сортировка списка распределением
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru