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

структуры данных. сортировка однонаправленного списка - C++

Восстановить пароль Регистрация
 
s-mumrik
Сообщений: n/a
25.05.2012, 14:49     структуры данных. сортировка однонаправленного списка #1
значит так, есть вот эта программа:

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
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
#include <stdio.h>
#include <conio.h>
#include <math.h>
struct spisok
{   int info;
    spisok *link;
};
spisok *first=NULL;
 
 
void add(int data )
{
    if (first==NULL)
    {
    first=new (spisok);
    first->info=data;
    first->link=NULL;
    }
    else
    {
    spisok *adr;
    adr=first;
    while (adr->link!=NULL)
    {
      adr=adr->link;
    }
    adr->link=new (spisok);
    adr=adr->link;
    adr->info=data;
    adr->link=NULL;
    }
}
void print()
{
  spisok *adr;
  if (first==NULL)
    printf("!!!spisok pust \n");
  else{
    adr=first;
    while (adr!=NULL){
      printf("%d  ",adr->info);
      adr=adr->link;
    }
    printf("\n");
  }
}
 
void del(int data)
{
    spisok *adr,*adr1;
    adr=first;
    if (first==NULL)
      printf("!!!spisok pust \n");
    else
    {
      if (adr->info==data)
      {
    first=adr->link;
    delete adr;
      }
      else
      {
    if(adr->link->info==data)
    {
      adr1=adr->link;
      adr->link=adr->link->link;
      delete adr1;
    }
    else
    printf("\n!!!takogo elementa net \n");
      }
    }
}
 
void sortirovka (spisok *head )
{int k;
do
{
  k=0;
  int l=0;
  while (head->link != NULL)
  {
    if (head->info>head->link->info)
    {
    head;
    spisok *q=head;
    spisok *qq=head->link->link;
    first=head->link;
    first->link=q;
    first->link->link=qq;
    k=k+1;
    head=head->link;
    }
    else
    {
      head=head->link;
    }
    printf("%d",k);
  }
}
while (k!=0);
}
 
main()
{       clrscr();
    int n,a;
    do
    {
    printf("\n");
    printf("1. dobavit element \n");
    printf("2. posmotret spisok \n");
    printf("3. udalit element \n");
    printf("4. sortirovka elementov \n");
    printf("5. vyhod \n\n");
    printf("vyberite punkt menu: ");
    scanf("%d",&n);
    if (n==1)
    {
     printf("vvedite element \n");
     scanf("%d",&a);
     add(a);
    }
    if (n==2) print();
    if (n==3)
    {
        printf("vvedite ydaljaemoe chislo \n");
        scanf("%d",&a);
        del(a);
    }
    if (n==4) sortirovka(first);
    }
    while (n!=5);
}
все работает, кроме сортировки. то есть сортировка тоже работает, но только для сферического списка в вакууме(только для 2-х элементов). сортировка без перестановки элементов, то есть можно только перенаправить указатели. помогите пожалуйста разобраться, уже 2-ю неделю мучаюсь с прогой.

Добавлено через 21 час 32 минуты
вот этот участок не работает, подскажите пожалуйста, где ошибка.
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
void sortirovka (spisok *head )
{int k;
do
{
  k=0;
  int l=0;
  while (head->link != NULL)
  {
    if (head->info>head->link->info)
    {
    head;
    spisok *q=head;
    spisok *qq=head->link->link;
    first=head->link;
    first->link=q;
    first->link->link=qq;
    k=k+1;
    head=head->link;
    }
    else
    {
      head=head->link;
    }
    printf("%d",k);
  }
}
while (k!=0);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2012, 14:49     структуры данных. сортировка однонаправленного списка
Посмотрите здесь:

C++ Сортировка однонаправленного линейного списка
Сдвиг элементов однонаправленного списка C++
C++ Структуры и массивы, сортировка списка.
C++ Создание однонаправленного списка
C++ Сортировка однонаправленного списка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stawerfar
 Аватар для stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
25.05.2012, 16:33     структуры данных. сортировка однонаправленного списка #2
сортировка не работает корректно потому что для этого необходимо каждое число сравнивать с каждым элементом списка. Для этого необходимо создать иметь два указателя на начало списка.
допустим First и Second;
Тогда сравнения каждого элемента списка со всеми элементами списка будет выглядеть вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
spisok*First;
spisok*Second = First ->link;
spisok*temp;//для обмена
spisok * memory = Sicond;//запомнить первое положение
while(First->link)
{
   while(Second)
     {
       
      if(First->info<Second->info)
       { temp = First;
          First = Second;
          Second = temp;
        }
        Second = Second ->link;
       }
       First = First->link;
        Second = First->link ;
}
Вот как то так.
Конечно это не рабочий код так как надо предусмотреть и обмен внутренних указателей *.link.
Я просто объяснил логику сортировки списка!
s-mumrik
Сообщений: n/a
25.05.2012, 16:56     структуры данных. сортировка однонаправленного списка #3
спасибо, попробую этим методом
stawerfar
 Аватар для stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
25.05.2012, 20:42     структуры данных. сортировка однонаправленного списка #4
Ну или так:
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
#include<iostream>
#include<list>
 
 
 
 
bool more(int o,int w)
{return o <w ? true : false;}
 
 
 
 
 
 
 
int main(void)
{
    std::list<int> list;
    std::list<int>::iterator iter;
    
    list.push_back(5);
    list.push_back(3);
    list.push_back(4);
    list.push_back(1);
    list.push_back(2);
    
    for(iter = list.begin(); iter != list.end() ; iter++)
    {
        std::cout << *iter << ' ';
    }
    list.sort(more);
    std::cout<<std::endl;
    for(iter = list.begin(); iter != list.end() ; iter++)
    {
        std::cout << *iter << ' ';
    }
    
    std::cout<<std::endl;
    
    system("pause");
return 0;
}
код рабочий. Поймешь его после ознакомления с STL ;
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
25.05.2012, 20:49     структуры данных. сортировка однонаправленного списка #5
Цитата Сообщение от stawerfar Посмотреть сообщение
код рабочий. Поймешь его после ознакомления с STL ;
Знаешь для чего дают такие задания? Чтоб человек как-раз разобрался с базовыми алгоритмами и контейнерами STL.

Кстати, и для чего ты функцию-предикат написал, я не понял. list.sort() работает точно так же.
И запись int main(void) - C-шный стиль. Ну и название у списка неудачное.
stawerfar
 Аватар для stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
25.05.2012, 23:04     структуры данных. сортировка однонаправленного списка #6
Да, да, ты кроме критики , что нибудь позитивное сказать можешь? Почему то ты не отвечал на его вопрос, а мой ответ критикуешь? Знаю я таких как ты. Ни чего личного... Лучше вместо этого алгоритм написал а не умничал "капитан" очевидность!
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4925 / 2668 / 243
Регистрация: 29.11.2010
Сообщений: 7,421
25.05.2012, 23:28     структуры данных. сортировка однонаправленного списка #7
Цитата Сообщение от stawerfar Посмотреть сообщение
Да, да, ты кроме критики , что нибудь позитивное сказать можешь? Почему то ты не отвечал на его вопрос, а мой ответ критикуешь? Знаю я таких как ты. Ни чего личного... Лучше вместо этого алгоритм написал а не умничал "капитан" очевидность!
Вот позитивное: код рабочий.

Некоторые люди просят покритиковать их, дабы научиться языку. А вы, я смотрю, уже мастер и критику в свой адрес воспринимаете очень жестко. Люди на ошибках учаться. В первую очередь, я помогаю вам, а не пытаюсь задеть. А ответ автору уже вы дали во 2 посте и вполне адекватный.

Ну и раз ты называешь мои посты "очевидными", а меня капитаном очевидностью, зачем тогда пишешь?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2012, 23:37     структуры данных. сортировка однонаправленного списка
Еще ссылки по теме:

Шаблон однонаправленного кольцевого списка C++
C++ Формировка однонаправленного Списка
C++ Создание линейного однонаправленного списка

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

Или воспользуйтесь поиском по форуму:
stawerfar
 Аватар для stawerfar
141 / 55 / 4
Регистрация: 14.12.2010
Сообщений: 347
Записей в блоге: 1
25.05.2012, 23:37     структуры данных. сортировка однонаправленного списка #8
Да все в порядке у меня с восприятием к критики если она конструктивная.
Дело в том что я человеку ответил дважды, причём единственный в силу сложившихся обстоятельств. А со стороны заходит человек и критика выглядит нападением. Моя последующая реакция типична для 98% людей. Я просто защищался чисто интуитивно. Так что все нормаль , без обид! :-)
А по поводу стиля, так он у каждого свой. Так вот "void" писать мне просто нравиться, да и к тому же это полезная инфа об методе или функции, говорящая что функция 100% ни чего ни принимает, ведь могут и значения по умолчанию. Это помогает другим программистам, более комфортно чувствовать себя при работе с Вашим кодом. Ну этом моё мнение, их много и каждый придерживается своей.
Yandex
Объявления
25.05.2012, 23:37     структуры данных. сортировка однонаправленного списка
Ответ Создать тему
Опции темы

Текущее время: 23:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru