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

Естественное двухпутевое слияние - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
nekto_igor
0 / 0 / 0
Регистрация: 07.01.2012
Сообщений: 5
18.02.2013, 19:59     Естественное двухпутевое слияние #1
Реализация связи элементов линейного списка - указатели. Способ организации линейного связанного списка - дек.
Алгоритм сортировки - Естественное двухпутевое слияние. Не могу написать код сортировки, сам алгоритм понял, а с кодом разобраться не могу. Помогите заочнику закрыть задолжность ..

Добавлено через 20 часов 8 минут
вот код без сортировки

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
#include "stdafx.h"
#include "iostream"
 
using namespace std;
  
struct Value
{
        public:int val;
        Value* Next;
        Value* Prev;
        Value(int n):Next(0),Prev(0),val(n){};
};
 class deq
{
        Value* Head;
        Value* Tail;
        public:void Add_First(int n);
        public:void Add_Last(int n);
        public:void Delete_First();
        public:void Delete_Last();
        public:void Print();
        public:void Sort();
        public:deq(){Head=NULL;Tail=NULL;}
};
 void deq::Add_First(int n)
{
        Value* Elem=new Value(n);    
        Elem->Prev=NULL;
        if (Head!=NULL)
        {
             Elem->Next=Head;
            Head->Prev=Elem;
            Head=Elem;
        }
        else
        {
            Elem->Next=NULL;
            Head=Tail=Elem;
        }
}
void deq::Add_Last(int n)
{
        Value* Elem=new Value(n);    
        Elem->Next=NULL;
        if (Tail!=NULL)
        {
            Elem->Prev=Tail;
            Tail->Next=Elem;
            Tail=Elem;
        }
        else
        {
            Elem->Next=NULL;
            Tail=Head=Elem;
        }
}
 void deq::Delete_First()
{
        Value *p;
        p=Head->Next;
        delete Head;
        Head=p;
        p->Prev=NULL;
}
void deq::Delete_Last()
{
        Value *p;
        p=Tail->Prev;
        delete Tail;
        Tail=p;
        p->Next=NULL;
}
 void deq::Print()
{
        Value *p=Head;
        while(p!=NULL)
        {
                cout<<p->val<<"  ";
                p=p->Next;
        }
        cout<<"\n";
        }
 void deq::Sort()
{}
int main()
{     deq elements;
 
        elements.Add_First(15);
        elements.Add_First(1);
        elements.Add_First(3);
        elements.Add_First(7);
        elements.Add_First(9);
        elements.Add_Last(4);
        elements.Add_Last(6);
        elements.Print();
        elements.Sort();
        cout << "\n";
        elements.Print();
 
        system("pause");
        return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2013, 19:59     Естественное двухпутевое слияние
Посмотрите здесь:

C++ Черезстрочное слияние
C++ Слияние массивов
Слияние массивов C++
Простое двухпутевое слияние.Сортировка. Реализация C++
C++ Бинарное слияние
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nekto_igor
0 / 0 / 0
Регистрация: 07.01.2012
Сообщений: 5
04.03.2013, 13:39  [ТС]     Естественное двухпутевое слияние #2
всё, разобрался
Genag
1 / 1 / 0
Регистрация: 15.11.2012
Сообщений: 9
12.05.2013, 13:17     Естественное двухпутевое слияние #3
nekto_igor, можешь скинуть код сортировки, который у тебя получился?
nekto_igor
0 / 0 / 0
Регистрация: 07.01.2012
Сообщений: 5
12.05.2013, 23:40  [ТС]     Естественное двухпутевое слияние #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
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
 int deq::GetValue(int n)
{
  Value *p=Head;
  for(int i=1; i<n; i++)
   p = p->Next;
 
  return p->val;
}
 
void deq::SetValue(int n, int val)
{
  Value *p=Head;
  for(int i=1; i<n; i++)
  {
   if (!p->Next)
    Add_Last(0);
   p = p->Next;
  }
  p->val = val;
}
 void deq::Sort(int n)
{
    // deq r,r1;
    int s,f,d,i,j,g,k,p;
   // n=10; //
    s = 1;
    do
    {
        s=1-s; 
        d=1; 
        f=1; 
 
        if (s == 0)
        {
            i = 1; 
            j = n; 
            k = n+1; 
            g = 2*n; 
        }
        else
        {
            i = n+1; 
            j = 2*n; 
            k = 1; 
            g = n; 
        }
 
        while(i!=j)//
        {
           // if(K[i]<K[j])
            if (GetValue(i) > GetValue(j))
            {
               // R[k] = R[j];
                SetValue(k, GetValue(j));
                k = k+d; 
                j = j-1; 
 
               // if (!(K[j+1]<=K[j]))
                if (GetValue(j+1) <= GetValue(j))
                {
                }
                else
                {
                    do
                    {
                       // R[k]=R[i];
                        SetValue(k, GetValue(i));
                        k=k+d; counter++;
                        i=i+1; counter++;
                    }
                   // while(!K[i-1]>=K[i]);
                    while(GetValue(i-1) < GetValue(i));
 
                    f = 0; 
                    d = -d; 
                    p = k; 
                    k = g; 
                    g = p; 
                }
            }
            else
            {
               // R[k]=R[i];
                SetValue(k, GetValue(i));
                k=k+d; counter++;
                i=i+1; counter++;
               // if(K[i-1]<=K[i])
                if (GetValue(i-1) <= GetValue(i))
                {
                }
                else
                {
                      do
                       {
                         // R[k] = R[j];
                          SetValue(k, GetValue(j));
                          k = k+d; counter++;
                          j = j-1; counter++;
                       }
                         // while(K[j+1]>=K[j]);
                         while (GetValue(j+1) < GetValue(j));
                    f=0; 
                    d=-d; 
                    p=k; 
                    k=g; 
                    g=p; 
                }
            }
        }
        //R[k]=R[i];
        SetValue(k, GetValue(i));
    }   while (f!=1);
    
       if(s==0)
     {
    for(int z=1; z<=n; z++)
   // R[z] = R[z+n];
   SetValue(z, GetValue(z+n));
}[CPP]
[/CPP]

Добавлено через 59 секунд
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
int deq::GetValue(int n)
{
  Value *p=Head;
  for(int i=1; i<n; i++)
   p = p->Next;
 
  return p->val;
}
 
void deq::SetValue(int n, int val)
{
  Value *p=Head;
  for(int i=1; i<n; i++)
  {
   if (!p->Next)
    Add_Last(0);
   p = p->Next;
  }
  p->val = val;
}
 void deq::Sort(int n)
{
    // deq r,r1;
    int s,f,d,i,j,g,k,p;
   // n=10; //
    s = 1;
    do
    {
        s=1-s; 
        d=1; 
        f=1; 
 
        if (s == 0)
        {
            i = 1; 
            j = n; 
            k = n+1; 
            g = 2*n; 
        }
        else
        {
            i = n+1; 
            j = 2*n; 
            k = 1; 
            g = n; 
        }
 
        while(i!=j)//
        {
           // if(K[i]<K[j])
            if (GetValue(i) > GetValue(j))
            {
               // R[k] = R[j];
                SetValue(k, GetValue(j));
                k = k+d; 
                j = j-1; 
 
               // if (!(K[j+1]<=K[j]))
                if (GetValue(j+1) <= GetValue(j))
                {
                }
                else
                {
                    do
                    {
                       // R[k]=R[i];
                        SetValue(k, GetValue(i));
                        k=k+d; counter++;
                        i=i+1; counter++;
                    }
                   // while(!K[i-1]>=K[i]);
                    while(GetValue(i-1) < GetValue(i));
 
                    f = 0; 
                    d = -d; 
                    p = k; 
                    k = g; 
                    g = p; 
                }
            }
            else
            {
               // R[k]=R[i];
                SetValue(k, GetValue(i));
                k=k+d; counter++;
                i=i+1; counter++;
               // if(K[i-1]<=K[i])
                if (GetValue(i-1) <= GetValue(i))
                {
                }
                else
                {
                      do
                       {
                         // R[k] = R[j];
                          SetValue(k, GetValue(j));
                          k = k+d; counter++;
                          j = j-1; counter++;
                       }
                         // while(K[j+1]>=K[j]);
                         while (GetValue(j+1) < GetValue(j));
                    f=0; 
                    d=-d; 
                    p=k; 
                    k=g; 
                    g=p; 
                }
            }
        }
        //R[k]=R[i];
        SetValue(k, GetValue(i));
    }   while (f!=1);
    
       if(s==0)
     {
    for(int z=1; z<=n; z++)
   // R[z] = R[z+n];
   SetValue(z, GetValue(z+n));
}
Genag
1 / 1 / 0
Регистрация: 15.11.2012
Сообщений: 9
13.05.2013, 00:07     Естественное двухпутевое слияние #5
nekto_igor, Спасибо большое!!
nekto_igor
14.05.2013, 00:26  [ТС]
  #6

Не по теме:

Ты где учишься?

Genag
14.05.2013, 00:40
  #7

Не по теме:

Москва, МГУПИ

nekto_igor
14.05.2013, 00:43  [ТС]
  #8

Не по теме:

куда тебе можно написать?
не спеши сдавать

Genag
1 / 1 / 0
Регистрация: 15.11.2012
Сообщений: 9
14.05.2013, 00:57     Естественное двухпутевое слияние #9
nekto_igor,

Не по теме:

grigoryang1995@yandex.ru

Добавлено через 8 минут
nekto_igor, а я все равно пройдусь по коду и отредактирую, просто пока времени не было

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2013, 13:34     Естественное двухпутевое слияние
Еще ссылки по теме:

C++ слияние списков
C++ Слияние массивов
Внешние сортировки. Сортировка слиянием. Естественное слияние C++

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

Или воспользуйтесь поиском по форуму:
The_Immortal
1548 / 484 / 8
Регистрация: 04.04.2009
Сообщений: 1,891
14.05.2013, 13:34     Естественное двухпутевое слияние #10
nekto_igor,
Genag,
 Комментарий модератора 
Уважаемые, если общение выходит за рамки изначально обсуждаемой темы, то будьте любезны пользоваться соответствующими тегами оффтопа (OFF).
Благодарю.
Yandex
Объявления
14.05.2013, 13:34     Естественное двухпутевое слияние
Ответ Создать тему
Опции темы

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