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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.60
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
#1

Односвязный список - C++

11.12.2009, 11:50. Просмотров 1907. Ответов 22
Метки нет (Все метки)

Всем привет,

Дaн oднocвязный cпиcoк, элeмeнт этoгo cпиcка coдержит маccив из 10 цeлых пeрeмeнных. Эти пeрeмeнные нужнo xранит в пoрядке вoзраcтания. Такжe маccив можeт быть запoлнен нe пoлнocтью.

Функция дoлжна включaть значeниe в элeмeнт этoгo cпиcка, нo c coхранением упoрядoченнocти. Eсли маccив пeрeпoлнитьcя, тo нужнo будет coздать нoвый элeмeнт cпиcка и в негo уже включить пoлoвину значeний из перепoлненнoгo.

С чего начать и в какую сторону копать?
Спасибо за любой ответ!

//C++
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2009, 11:50     Односвязный список
Посмотрите здесь:

Односвязный список C++
C++ Односвязный список
C++ Односвязный список
односвязный список C++
C++ Односвязный список
C++ Односвязный список
Односвязный список C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
11.12.2009, 13:46     Односвязный список #2
нужнo будет coздать нoвый элeмeнт cпиcка и в негo уже включить пoлoвину значeний из перепoлненнoгo.
вот эта конструкция не совсем понятна.
пусть наш массив 11,23,35,42,54, 65,70,89,93,102.
вот пришло новое значение 57. Что и в каком порядке должно остаться в этом массиве, а что и в каком порядке будет лежать в следующем?

тот же вопрос, если вместо 57 придёт значение 13
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
11.12.2009, 14:03  [ТС]     Односвязный список #3
Пусть наш был массив:
11,35,42,65,89,102.

После прихода новых значении 23,54,70,93:
11,23,35,42,54, 65,70,89,93,102.

Теперь при переполнение после прихода 57, происходит некое разделение:
1) 11, 23, 35,42,54.
2) 57, 65,70,89,93,102.

или после прихода 13:

1) 11, 13, 23,35,42,
2) 54, 65,70,89,93,102.
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
11.12.2009, 17:41  [ТС]     Односвязный список #4
Цитата Сообщение от Vladimir. Посмотреть сообщение
вот эта конструкция не совсем понятна.
пусть наш массив 11,23,35,42,54, 65,70,89,93,102.
вот пришло новое значение 57. Что и в каком порядке должно остаться в этом массиве, а что и в каком порядке будет лежать в следующем?

тот же вопрос, если вместо 57 придёт значение 13
Это еще полбеды, хотя бы сделать без этого
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
11.12.2009, 18:09     Односвязный список #5
linked_list.h
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
#ifndef UTWO_LINKED_LIST
#define UTWO_LINKED_LIST 1
#include <iostream>
#include "nodes.h"
 
class linked_lists
{
    public:
        
        
        void show(); // для контроля
        void add(int value);
                
        linked_lists(){tail = NULL;}
        ~linked_lists();
    
    private:
        nodes* tail;        
};
 
 
// =======================================
void linked_lists::add(int value)
{
    if (tail==NULL) { tail = new nodes(); tail->prior=NULL;}
    //если список пуст, создаём узел.
 
    if(!tail->is_full())// если узел не полнoн, то засовываем туда value
    {
        tail->push(value);
        tail->sort();
    }
    else 
    //если узел полон, создаем новый, перекидываем в него пять последних элементов
    {
        nodes* node = new nodes();
        node->prior = tail;//связали со списком.
        
        int tmp;
        for(int i=1;i<=5;i++)
        {
            tail->pop(&tmp);
            node->push(tmp);
        }
        // 5 элемент сравнивается с value. больший отпавляется в новый узел.
        // меньший остается.
        tail->pop(&tmp);
        if(value<tmp) {tail->push(value);node->push(tmp);}
        else {tail->push(tmp);node->push(value);}
        
        // осталось только переопределить указатель на хвост
        
        tail = node;
        
    }
    
}
 
 
void linked_lists::show()
{
    if(tail==NULL) {std::cout<<"\n linked-list is empty now..\n\n";return;}
    nodes* ip = tail;
    while (true)
    {
        std::cout<<ip;
        ip->show();
        std::cout<<"\n";
        if(ip->prior==NULL) break;
        ip=ip->prior;
    }
 
}
 
linked_lists::~linked_lists()
{
    if(tail==NULL) {std::cout<<"\nmemory is free!!\n";return;}
    
    nodes* ip = tail;
    while (ip->prior!=NULL)
    {
        tail = ip;
        ip=ip->prior;
        delete tail;
    }
    delete ip;
    std::cout<<"\n memory is free!!!";  
    }
 
 
#endif


Добавлено через 28 секунд
nodes.h
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
#ifndef UTWO_NODES
#define UTWO_NODES 1
 
#include<iostream>
struct nodes
{
    
    void sort();
    void push(int value);
    void pop(int* value);
    void show();
    bool is_full();
    
    int* array;
    nodes* prior;
    
    nodes(){array = new int [10];top = 0;}
    ~nodes(){delete[] array;}
    private:
        int top; // показывает на первое свободное место
};
 
 
//=========================================
void nodes::push(int value)
{
    if (top>9) return; // на всякий случай.
    array[top++]=value;
}
 
void nodes::pop(int* out)
{
    if (!top) return; // на всякий случай.
    
    *out = array[--top];
}
 
void nodes::show()//для контроля
{
    for(int i=0;i<top;i++) std::cout<<"  "<<array[i];
}
 
void nodes::sort()                  //вставками.
{ 
    int tmp, i, j;
    for ( i=0; i < top; i++)
    {  
        tmp = array[i];   
        for ( j=i-1; j>=0 && array[j] > tmp; j--)
            array[j+1] = array[j];
        array[j+1] = tmp;
    }
}
bool nodes::is_full()
{
    return (top==10);
}
#endif


Добавлено через 43 секунды
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
#include <iostream>
#include "nodes.h"
#include "linked_list.h"
 
int main()
{
    linked_lists a;
    
    a.show();
    system("pause");
    for(int i=0;i<15;i++) 
    {
        a.add(-i*i+10*i);
        a.show();
        system("pause");
    }
    system("cls");
    
    
    a.show();   
    system("pause");
    delete &a;
    system("pause");
    return 0;
}
Добавлено через 3 минуты
на здоровье...
код сырой, классы не "сворачивал". будут вопросы - отвечу.
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
11.12.2009, 20:53  [ТС]     Односвязный список #6
на здоровье...
код сырой, классы не "сворачивал". будут вопросы - отвечу.
Огромное спасибо! Но честно говоря мы еще классы не изучали.
В принципе общая идея понятна, теперь буду смотреть как бы без классов обойтись?!

ух тут еще #ifndef #endif

Добавлено через 43 минуты
Цитата Сообщение от utwo Посмотреть сообщение
Огромное спасибо! Но честно говоря мы еще классы не изучали.
В принципе общая идея понятна, теперь буду смотреть как бы без классов обойтись?!

ух тут еще #ifndef #endif
т.е. хотел сказать не изучали #ifndef #endif
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
11.12.2009, 21:44     Односвязный список #7
C++
1
2
3
4
5
6
7
8
#ifndef UTWO_LINKED_LIST
// Если UTWO_LINKED_LIST не объявлялось, то  включить код  до #endif иначе, перейти к строке за #endif
#define UTWO_LINKED_LIST 1
// объявление UTWO_LINKED_LIST..
 
//"включаемый код"
 
#endif
идея состоит в том, что "включаемый код" в подобном "обрамлении" может быть включен только один раз.
В принципе, можно закоментить это всё.
C++
1
теперь буду смотреть как бы без классов обойтись?!
структуры проходили??
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 18:57  [ТС]     Односвязный список #8
да проходили!
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
12.12.2009, 19:12     Односвязный список #9
Цитата Сообщение от utwo Посмотреть сообщение
да проходили!
меняй слово class на слово struct, чтоб "красивше" можно затереть модификаторы private: public:..
Всё будет работать.
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 19:15  [ТС]     Односвязный список #10
получиться все в один cpp объединить?
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
12.12.2009, 19:34     Односвязный список #11
Да.
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
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
#include <iostream>
 
struct nodes
{
    
    void sort();
    void push(int value);
    void pop(int* value);
    void show();
    bool is_full();
    
    int* array;
    nodes* prior;
    
    nodes(){array = new int [10];top = 0;}
    ~nodes(){delete[] array;}
    int top; // показывает на первое свободное место
};
//============================================================
struct linked_lists
{
 
        void show(); // для контроля
        void add(int value);
                
        linked_lists(){tail = NULL;}
        ~linked_lists();
        nodes* tail;        
};
 
//============================================================
int main()
{
        linked_lists a;
        
        a.show();
        system("pause");
        for(int i=0;i<15;i++) 
        {
                a.add(-i*i+10*i);
                a.show();
                system("pause");
        }
        system("cls");
        
        
        a.show();       
    system("pause");
    delete &a;
    system("pause");
        return 0;
}
 
//============================================================
void nodes::push(int value)
{
    if (top>9) return; // на всякий случай.
    array[top++]=value;
}
 
void nodes::pop(int* out)
{
    if (!top) return; // на всякий случай.
    
    *out = array[--top];
}
 
void nodes::show()//для контроля
{
    for(int i=0;i<top;i++) std::cout<<"  "<<array[i];
}
 
void nodes::sort()                  //вставками.
{ 
    int tmp, i, j;
    for ( i=0; i < top; i++)
    {  
        tmp = array[i];   
        for ( j=i-1; j>=0 && array[j] > tmp; j--)
            array[j+1] = array[j];
        array[j+1] = tmp;
    }
}
bool nodes::is_full()
{
    return (top==10);
}
 
 
// =====================================================================
void linked_lists::add(int value)
{
    if (tail==NULL) { tail = new nodes(); tail->prior=NULL;}
    //если список пуст, создаём узел.
 
    if(!tail->is_full())// если узел не полнoн, то засовываем туда value
    {
        tail->push(value);
        tail->sort();
    }
    else 
    //если узел полон, создаем новый, перекидываем в него пять последних элементов
    {
        nodes* node = new nodes();
        node->prior = tail;//связали со списком.
        
        int tmp;
        for(int i=1;i<=5;i++)
        {
            tail->pop(&tmp);
            node->push(tmp);
        }
        // 5 элемент сравнивается с value. больший отпавляется в новый узел.
        // меньший остается.
        tail->pop(&tmp);
        if(value<tmp) {tail->push(value);node->push(tmp);}
        else {tail->push(tmp);node->push(value);}
        
        // осталось только переопределить указатель на хвост
        
        tail = node;
        
    }
    
}
 
 
void linked_lists::show()
{
    if(tail==NULL) {std::cout<<"\n linked-list is empty now..\n\n";return;}
    nodes* ip = tail;
    while (true)
    {
        std::cout<<ip;
        ip->show();
        std::cout<<"\n";
        if(ip->prior==NULL) break;
        ip=ip->prior;
    }
 
}
 
linked_lists::~linked_lists()
{
    if(tail==NULL) {std::cout<<"\nmemory is free!!\n";return;}
    
    nodes* ip = tail;
    while (ip->prior!=NULL)
    {
        tail = ip;
        ip=ip->prior;
        delete tail;
    }
    delete ip;
    std::cout<<"\n memory is free!!!";  
    }
 
 
//======================================================================
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 21:05  [ТС]     Односвязный список #12
Цитата Сообщение от Vladimir. Посмотреть сообщение
"Да."
Vladimir.,
Спасибо огромное!
Буду пробовать и разбираться.

Добавлено через 16 минут
Что-то очистить память не получается?
Как полечить это сообщение?
http://pic.ipicture.ru/uploads/09121...KR4FbFO5y.jpeg

Добавлено через 50 минут
Три сообщения об ошибках:
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
_CrtIsValidHeapPointer(pUserData)
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)

Добавлено через 20 минут
Похоже сразу после разделения первый раз отобразилось не верно, затем "нолик постоянно" не может отсортироваться.
Вывод сейчас выглядит таким образом:
Код
00343840  0

00343840  0  9

00343840  0  9  16

00343840  0  9  16  21

00343840  0  9  16  21  24

00343840  0  9  16  21  24  25

00343840  0  9  16  21  24  24  25

00343840  0  9  16  21  21  24  24  25

00343840  0  9  16  16  21  21  24  24  25

00343840  0  9  9  16  16  21  21  24  24  25

00346180  [COLOR="Red"]25  24  24  21  21  16[/COLOR]
00343840  0  9  9  16  [COLOR="Red"]0[/COLOR]

00346180  -11  16  21  21  24  24  25
00343840  0  9  9  16  [COLOR="Red"]0[/COLOR]

00346180  -24  -11  16  21  21  24  24  25
00343840  0  9  9  16  [COLOR="Red"]0[/COLOR]

00346180  -39  -24  -11  16  21  21  24  24  25
00343840  0  9  9  16  [COLOR="Red"]0[/COLOR]

00346180  -56  -39  -24  -11  16  21  21  24  24  25
00343840  0  9  9  16  [COLOR="Red"]0[/COLOR]
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
13.12.2009, 09:48     Односвязный список #13
Цитата Сообщение от utwo Посмотреть сообщение
Похоже сразу после разделения первый раз отобразилось не верно, затем "нолик постоянно" не может отсортироваться.
Вывод сейчас выглядит таким образом:
Всё верно, там вообще сортировка не выполнялась...
Строка 121:
C++
1
tail = node;
Сделать так:
C++
1
2
3
tail = node;
tail->sort();
tail->prior->sort();
насчёт "лечения" ничего подсказать не могу..
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
13.12.2009, 20:01  [ТС]     Односвязный список #14
Цитата Сообщение от utwo Посмотреть сообщение
Что-то очистить память не получается?
Как полечить это сообщение?
http://pic.ipicture.ru/uploads/09121...KR4FbFO5y.jpeg

Три сообщения об ошибках:
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
_CrtIsValidHeapPointer(pUserData)
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
если закомментировать строку 49: delete &a;
то ошибок не возникает. На сколько это критично?
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
13.12.2009, 20:21     Односвязный список #15
покажите еще раз свой код, полностью, со всеми изменениями..
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
13.12.2009, 20:36  [ТС]     Односвязный список #16
В принципе пока никаких изменений не вносилось. Тот же код что был указан выше, плюс исправление на счет сортировки.
Вот.
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
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
#include <iostream>
 
struct nodes
{
        
        void sort();
        void push(int value);
        void pop(int* value);
        void show();
        bool is_full();
        
        int* array;
        nodes* prior;
        
        nodes(){array = new int [10];top = 0;}
        ~nodes(){delete[] array;}
        int top; // показывает на первое свободное место
};
//============================================================
struct linked_lists
{
 
                void show(); // для контроля
                void add(int value);
                                
                linked_lists(){tail = NULL;}
                ~linked_lists();
                nodes* tail;            
};
 
//============================================================
int main()
{
        linked_lists a;
        
        a.show();
        system("pause");
        for(int i=0;i<15;i++) 
        {
                a.add(-i*i+10*i);
                a.show();
                system("pause");
        }
        system("cls");
        
        
        a.show();       
    system("pause");
   delete &a;
    system("pause");
        return 0;
}
 
//============================================================
void nodes::push(int value)
{
        if (top>9) return; // на всякий случай.
        array[top++]=value;
}
 
void nodes::pop(int* out)
{
        if (!top) return; // на всякий случай.
        
        *out = array[--top];
}
 
void nodes::show()//для контроля
{
        for(int i=0;i<top;i++) std::cout<<"  "<<array[i];
}
 
void nodes::sort()                                      //вставками.
{ 
        int tmp, i, j;
        for ( i=0; i < top; i++)
        {  
            tmp = array[i];   
        for ( j=i-1; j>=0 && array[j] > tmp; j--)
                array[j+1] = array[j];
        array[j+1] = tmp;
        }
}
bool nodes::is_full()
{
        return (top==10);
}
 
 
// =====================================================================
void linked_lists::add(int value)
{
        if (tail==NULL) { tail = new nodes(); tail->prior=NULL;}
        //если список пуст, создаём узел.
 
        if(!tail->is_full())// если узел не полнoн, то засовываем туда value
        {
                tail->push(value);
                tail->sort();
        }
        else 
        //если узел полон, создаем новый, перекидываем в него пять последних элементов
        {
                nodes* node = new nodes();
                node->prior = tail;//связали со списком.
                
                int tmp;
                for(int i=1;i<=5;i++)
                {
                        tail->pop(&tmp);
                        node->push(tmp);
                }
                // 5 элемент сравнивается с value. больший отпавляется в новый узел.
                // меньший остается.
                tail->pop(&tmp);
                if(value<tmp) {tail->push(value);node->push(tmp);}
                else {tail->push(tmp);node->push(value);}
                
                // осталось только переопределить указатель на хвост
                
                tail = node;
 
                tail->sort();
                tail->prior->sort();;
                
        }
        
}
 
 
void linked_lists::show()
{
        if(tail==NULL) {std::cout<<"\n linked-list is empty now..\n\n";return;}
        nodes* ip = tail;
        while (true)
        {
                std::cout<<ip;
                ip->show();
                std::cout<<"\n";
                if(ip->prior==NULL)     break;
                ip=ip->prior;
        }
 
}
 
linked_lists::~linked_lists()
{
        if(tail==NULL) {std::cout<<"\nmemory is free!!\n";return;}
        
        nodes* ip = tail;
        while (ip->prior!=NULL)
        {
                tail = ip;
                ip=ip->prior;
                delete tail;
        }
        delete ip;
        std::cout<<"\n memory is free!!!";      
        }
 
 
//======================================================================


Открытым остался вопрос по поводу системных ошибках при компиляции.
Ошибки пропали после комментирования оператора удаленияdelete &a. Но на сколько это правильно?
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
13.12.2009, 20:56     Односвязный список #17
возможно я неправ, вы пробывали писать delete &a без знака "&"?
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
14.12.2009, 06:42  [ТС]     Односвязный список #18
Цитата Сообщение от outoftime Посмотреть сообщение
возможно я неправ, вы пробывали писать delete &a без знака "&"?
error C2440: delete: невозможно преобразовать 'list' в 'void *'
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
14.12.2009, 12:34     Односвязный список #19
проблему нужно искать либо на уровне vs либо ОС (например, будет ли такая- же ошибка выпадать, если DEP отключить?).
Имеет смысл зайти к товарищу с VSС++ и попробывать скомпилировать у него.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2009, 08:01     Односвязный список
Еще ссылки по теме:

C++ Односвязный список
C++ Односвязный список
Односвязный список C++
C++ Односвязный список
C++ Односвязный список

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

Или воспользуйтесь поиском по форуму:
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
17.12.2009, 08:01  [ТС]     Односвязный список #20
Ошибка похоже действительно на уровне VSС++ и OS.


Теперь если немного усложнить задачку
Надo, чтoбы элeмeнты включалиcь в списoк упoрядoченнo.

Напримeр:
Былo всeгo 2 элeмeнта списка с 7ми числами:
-1 3 5 7
-23 24 30

Вставляeм цифру 6 - сталo 3 элeмeнта списка:
-1 3
-5 6 7
-23 24 30

Тeпeрь вставляeм цифру 10 - сталo 3 элeмeнта списка:
-1 3
-5 6 7 10
-23 24 30
Yandex
Объявления
17.12.2009, 08:01     Односвязный список
Ответ Создать тему
Опции темы

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