С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

11.12.2009, 11:50. Просмотров 2030. Ответов 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++
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2009, 11:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Односвязный список (C++):

Сформировать список из 10 книг, используя динамическую структуру данных односвязный список - C++
друзья спасайте Сформировать список из 10 книг, используя динамическую структуру данных односвязный список С++

Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов - C++
Задание: создайте двусвязный список групп факультета. Каждая группа представляет собой односвязный список студентов. Помогите пожалуйста,...

Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке - C++
Задали односвязный линейный список с целыми числами. Создать новый список, который содержит элементы заданного списка в обратном порядке.

Односвязный список - C++
Здравствуйте! Кто может разъяснить как вставить в узел заданного места значение.. 1. Нужно выделить память Elem *Ins = new Elem ...

Односвязный список - C++
Во общем, программа создает список и заносит туда элементы с помощью массива. Но при выводе, программа выводит лишний элемент первым. Где...

Односвязный список - C++
"Односвязный список 2.exe" (Win32). Загружено "C:\Users\Владислав\Documents\Visual Studio 2012\Projects\Односвязный список...

22
Vladimir.
158 / 158 / 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
1
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.
0
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
Это еще полбеды, хотя бы сделать без этого
0
Vladimir.
158 / 158 / 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 минуты
на здоровье...
код сырой, классы не "сворачивал". будут вопросы - отвечу.
1
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
11.12.2009, 20:53  [ТС] #6
на здоровье...
код сырой, классы не "сворачивал". будут вопросы - отвечу.
Огромное спасибо! Но честно говоря мы еще классы не изучали.
В принципе общая идея понятна, теперь буду смотреть как бы без классов обойтись?!

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

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

ух тут еще #ifndef #endif
т.е. хотел сказать не изучали #ifndef #endif
0
Vladimir.
158 / 158 / 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
теперь буду смотреть как бы без классов обойтись?!
структуры проходили??
1
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 18:57  [ТС] #8
да проходили!
0
Vladimir.
158 / 158 / 10
Регистрация: 24.11.2009
Сообщений: 375
12.12.2009, 19:12 #9
Цитата Сообщение от utwo Посмотреть сообщение
да проходили!
меняй слово class на слово struct, чтоб "красивше" можно затереть модификаторы private: public:..
Всё будет работать.
1
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 19:15  [ТС] #10
получиться все в один cpp объединить?
0
Vladimir.
158 / 158 / 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!!!";  
    }
 
 
//======================================================================
1
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
12.12.2009, 21:05  [ТС] #12
Цитата Сообщение от Vladimir. Посмотреть сообщение
"Да."
Vladimir.,
Спасибо огромное!
Буду пробовать и разбираться.

Добавлено через 16 минут
Что-то очистить память не получается?
Как полечить это сообщение?
http://pic.ipicture.ru/uploads/091212/thumbs/wKR4FbFO5y.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]
0
Vladimir.
158 / 158 / 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();
насчёт "лечения" ничего подсказать не могу..
1
utwo
3 / 3 / 0
Регистрация: 10.10.2009
Сообщений: 108
13.12.2009, 20:01  [ТС] #14
Цитата Сообщение от utwo Посмотреть сообщение
Что-то очистить память не получается?
Как полечить это сообщение?
http://pic.ipicture.ru/uploads/091212/thumbs/wKR4FbFO5y.jpeg

Три сообщения об ошибках:
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
_CrtIsValidHeapPointer(pUserData)
_BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
если закомментировать строку 49: delete &a;
то ошибок не возникает. На сколько это критично?
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
13.12.2009, 20:21 #15
покажите еще раз свой код, полностью, со всеми изменениями..
0
13.12.2009, 20:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2009, 20:21
Привет! Вот еще темы с ответами:

Односвязный список - C++
Дан список целых чисел , удалить все положительные. struct my_list{ int num; struct my_list*Next; } int x; my_list...

Односвязный список - C++
Посмотрите программу, правильно ли я вывожу список? Почему список выводится только из 7 цифр, и как можно написать с помощью функций?...

Односвязный список - C++
Здравствуйте уважаемые форумчане. Помогите пожалуйста с задачкой: В памяти хранится односвязный список. Вам дан указатель на первый...

Односвязный список C++ - C++
помогите решить проблему с выводом суммы, буду благодарен #include &lt;iostream&gt; #include &lt;cctype&gt; using namespace std; struct...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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