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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

Быстрый стек, с малым обьемом памяти - C++

10.01.2010, 15:23. Просмотров 2213. Ответов 36
Метки нет (Все метки)

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
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
 
#define FOR(i,a,b) for (int i(a), _b(b); i < _b; ++i)
#define ABS(a) ( (a) < 0 ? -(a) : a )
 
using namespace std;
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    cin >> n;
    stack a[1000];
    while (n--)
    {
        int d;
        string s;
        cin >> s >> d;
        if (s == "PUSH")
        {
            int dd;
            cin >> dd;
            a[d-1].push(dd);
        }
        else
            cout << a[d-1].pop() << endl;
    }
    return 0;
}
http://acm.timus.ru/problem.aspx?space=1&num=1220
нужно за 1 секунду и 0,75Мб памяти обработать 0 < N ≤ 100000 запросов к 1 ≤ A ≤ 1000 разным стекам, гарантируется что все запросы коректны, т.е. вывод елемента со стека не может быть раньше чем ввод.
Вроде написал, но компилятор упорно говорит что cannot convert parameter 1 from 'int' to 'void *', как видно a = (int *) realloc(--sz, sizeof(int)); я (int *) дописал, т.е. все верно, может я чего-то непонял, в чем ошибка, подскажите пожалуйста..

Добавлено через 3 минуты
немного доработал ввод, на сишный, т.к. он быстрее, но ошибка с выделением памяти осталась, вот
код
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
#include <iostream>
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char* s;
        scanf("%s",&s);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else
            printf("%d",a[d-1].pop());
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2010, 15:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый стек, с малым обьемом памяти (C++):

Memory shift или самый быстрый способ перемещения блока памяти - C++
int* dataField = new int{0}; for (int i = 0; i &lt; 50; i++) dataField = 777; //тут должен быть memory shift delete dataField;...

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти - C++
Привет! Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1...

Стек и освобождение памяти - C++
Пишу класс стека, реслизую в виде односвязного списка. stack.h #ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED template &lt;class...

Стек. Нехватка памяти. Числа в тексте - C++
Здравствуйте, у меня возникла проблема, и как я понял, именно в нехватке памяти. Программа должна выводить число и второе число, ближайшее...

Используя стек, описать функцию проверяющую, является ли стек пустым - C++
Используя стек, описать функцию проверяющую, является ли стек пустым

Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами - C++
Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

36
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 19:00  [ТС] #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
#include <iostream>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
struct node
{
    node(){prev = 0; inf = 0;}
    ~node(){}
    int inf;
    node* prev;
};
 
class stack
{
public:
    stack(){head = 0;}
    ~stack(){}
    void push(int &n)
    {
        node* tmp = new node;
        tmp->inf = n;
        tmp->prev = head;
        head = tmp;
    }
    int pop()
    {
        int d = head->inf;
        node* tmp = head;
        head = head->prev;
        delete tmp;
        return d;
    }
private:
    node* head;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char s[10];
        scanf("%s%d",&s,&d);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else printf("%d",a[d-1].pop());
    }
    return 0;
}
неверное сравнение строк, можете помочь?

Добавлено через 2 минуты
GRANDEATH, я просто не могу понять как делать линковку, какому стеку отвечает какой элемент + нам нужет top..

Добавлено через 6 минут
вот пашет на малых:
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
#include <iostream>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
struct node
{
    node(){prev = 0; inf = 0;}
    ~node(){}
    int inf;
    node* prev;
};
 
class stack
{
public:
    stack(){head = 0;}
    ~stack(){}
    void push(int &n)
    {
        node* tmp = new node;
        tmp->inf = n;
        tmp->prev = head;
        head = tmp;
    }
    int pop()
    {
        int d = head->inf;
        node* tmp = head;
        head = head->prev;
        delete tmp;
        return d;
    }
private:
    node* head;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char s[10];
        scanf("%s%d",&s,&d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else printf("%d\n",a[d-1].pop());
    }
    return 0;
}
Добавлено через 1 минуту
кто знает сколько мугут потянуть указатели между элементами стека?

Добавлено через 2 минуты
этот код не канает, 10-ий тест - выделено пямяти: 1 653 КБ
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 19:01 #17
Дай 20 мин подумать
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 19:24  [ТС] #18
я думал так: если вы говорите, что для програмы выделяется куча, и даже если мы освобождаем память в систем она не возвращается, тогда нет другого пути как сделать все элементы статическими, что со стороны полный бред, но..
если мы запишем все 100000 операций в масив, после записи будем идти по нему, соответственно давая ответы на запросы?

Добавлено через 12 минут
и еще один вопрос: можно каким-то образом сново заполнять память которую мы освободили?
0
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 21:03 #19
Вообщем сдал я эту задачу.
Блок состоит из 19 чисел и одного указателя на предыдущий блок.
Для прикола сделал еще список свободных блоков.
Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков.
Когда нужен блок, то он сначала берется из этого списка,
а если список пуст, тогда уже берется из системы.

Я думаю что вообщем освобождение блоков не нужно,
но проверять это уже лень.

Добавлено через 1 минуту
Да - блоки выделяются обычным malloc().

Добавлено через 3 минуты
Еще вариант - вообще без блоков.
Выделяем 100000*7 байт
4 байта - число
3 байта - ссылка на предыдущий элемент ( 2-ух байт на 100000 не хватит )
Если 50 Kбайт хватит для работы программы то влезем
Но похоже накладные расходы больше.
У меня при сдаче получилось 725Kb
А я выделял блоками по 19+1 значение.
То есть там еще дофига должно было остаться.
Хитрая задача.

Добавлено через 39 секунд
Еще - не делайте на C++.
У С++ накладные расходы по памяти сильно большие !
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 21:23  [ТС] #20
Цитата Сообщение от odip Посмотреть сообщение
Блок состоит из 19 чисел и одного указателя на предыдущий блок.
Для прикола сделал еще список свободных блоков.
Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков.
Когда нужен блок, то он сначала берется из этого списка,
а если список пуст, тогда уже берется из системы.
вы описывали стек как структуру которая выделяет память блоками по 19 елементов?
0
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 21:24 #21
C
1
2
3
4
5
6
struct block_t;
struct block_t {
    int value[MAX_BLOCK_SIZE];
    struct block_t *prev_blk;
};
typedef struct block_t block_t;
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 21:47  [ТС] #22
int value[MAX_BLOCK_SIZE];
я запутался, а где тогда выделять malloc-ом память? или здесь надо просто указатель которому выделяем память?
0
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 21:52 #23
в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 22:02  [ТС] #24
Цитата Сообщение от odip Посмотреть сообщение
в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );
извените коль что просто я и си++ не очень хорошо знаю, а чистый си вообще.. и кажется где-то читал что определять размер струкруры нельзя

Добавлено через 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
#include <stdio.h>
 
struct block_t;
struct block_t
{
    int val[19];
    struct block_t* prev;
};
 
typedef struct block_t block_t;
 
struct stack
{
    block_t* inf;
    int top;
    stack()
    {
        inf->prev = 0;
        top = 0;
    }
    ~stack(){}
    void push(int &n)
    {
        if (top == 19)
        {
            top = 0;
            block_t* tmp = malloc(sizeof(block_k));
        }
        else
        {
            inf->val[top++] = n;
        }
    }
};
 
int main()
{    
    return 0;
}
Добавлено через 11 секунд
куча ошибок:

Добавлено через 1 минуту
16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before "stack"

16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] no semicolon at end of struct or union
19 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] data definition has no type or storage class
20 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token
22 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '&' token

C:\Documents and Settings\Администратор\Рабочий стол\timus.c In function `push':

27 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `block_k' undeclared (first use in this function)
(Each undeclared identifier is reported only once for each function it appears in.)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `inf' undeclared (first use in this function)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `n' undeclared (first use in this function)
At top level:
34 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 22:20 #25
У меня другое решение. Я создаю массив определенного размера и массив дескрипторов на него. То есть грубо говоря - разбиваю массив на страницы (извиняюсь, за неправильный термин, но не знаю, как ещё можно сказать). Отдельно есть массив char, содержащий 0 - если данный блок свободен, 1 - если занят. Я думаю, что сдесь лучше сего было использовать биты, а не байты, то было бы лучше. Если объясните, как делать тоже самое, только с битами, скажу СПАСИБО.
Тут два класса Memory - описывающий функции allocate_block free_block - выделяющий память и помечающий блок, как свободный. Реализация стека через выделяемые блоки памяти.
Писал на С++, поэтому накладных расходов много.
Вот код. Извиняюсь за неструктурированнось, так классы были разбиты по файлам, которые я инклюдил.
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// Task_2.cpp : Defines the entry point for the console application.
#include <stdio.h>
//#include <malloc.h>
 
 
 
#define BLOCK_SIZE 40
#define ARRAY_SIZE 400000
#define NUMBER_OF_POINTERS 10000 // = ARRAY_SIZE / BLOCK_SIZE
 
 
 
class Memory
{
public:
    //set_free();
    int* allocate_block(); //?????? ??????
    void free_block(int *p); // ???????? ??????
    Memory(void);
    ~Memory(void);
    void print(int a,int b);
 
private:
    int* data;
    char* indexes;
};
 
 
 
struct Descriptor
{
    int* position; //??????? ? ???? ????????
    Descriptor *next; //????????? ??????????
};
 
 
 
 
class stack
{
public:
    stack(void);
    ~stack(void);
    void push(int i);
    int pop();
    int debug_info_pos(); 
private:
    Descriptor root; //?????? ??????
    int pos; //?????? ???????
    int* local_pointer; // ????????? ?? ??????? ????. ???????? ????????.
};
 
 
int main()
{
 
        
        int n;
        scanf("%d",&n);
        stack *a = new stack[1000];
  
        char* temp = new char[20]; // 
        while (n--)
        {
                int d;
                scanf("%s",temp);
                //cin >> temp;
                scanf("%d",&d);
                //cin >> d;
                if (temp[1] == 'U') //
                {
                        int dd;
                        //cout << dd;
                        scanf("%d",&dd);
                        //cin >> dd;
                        a[d-1].push(dd);
                }
                else
                        //cout << a[d-1].pop() << endl;
                        printf("%d\n",a[d-1].pop());
        }
        
    
    //system("pause");
    
    return 0;
}
 
 
Memory my_memory;
 
stack::stack(void)
{
    local_pointer = root.position = my_memory.allocate_block(); //Âûäåëèòü áëîê ГЁГ§ "ГЄГіГ·ГЁ"
    root.next = NULL;
    pos = 0;
}
 
 
 
 
void stack::push(int i)
{
    if (pos == BLOCK_SIZE - 1) //Åñëè óæå Г*ГҐГІ ïÿìÿòè Гў ýòîé Г±ГІГ°Г*Г*èöå
    {
        Descriptor *temp = &root;
        while ( temp->next!= NULL)
        {
            temp = temp->next;
        }; //Èùåì Гў Г±ГЇГЁГ±ГЄГҐ Г*óëåâîé ГіГЄГ*Г§Г*òåëü
        
        
        temp->next = new Descriptor; // ÑîçäГ*ГҐГ¬ äåñêðèïòîð
        temp->next->position = my_memory.allocate_block();
        local_pointer = temp->next->position;
        temp->next->next = NULL; //Ñëåäóùåãî Г*ГҐГІ
        
        pos = 0; // Г‡Г*ïîëГ*ГїГІГј áëîê Г± 0-ГЈГ® ýëåìåГ*ГІГ*
        
    }
    *(local_pointer + pos) = i; //Г‡Г*ГЇГЁГёГЁ ГІГіГ¤Г* Г¤Г*Г*Г*ûå
    pos++; //Óâåëè÷ü ïîçèöèþ Г*Г* 1
}
 
int stack::pop()
{
    pos--; // ÓìåГ*ГјГёГј ГЁГ*äåêñ
    
    
    if (pos < 0) //Åñëè ГЁГ*äåêñ ìåГ*ГјГёГҐ 0. Г’Г® ГҐГ±ГІГј ГІГҐГЄГіГ№ГЁГ© áëîê ïóñòîé
    {
        Descriptor *temp = &root;
        if (temp->next != NULL) //Åñëè Г*ГҐ îäèГ* áëîê
        {   
            while ( temp->next->next!= NULL)
            {
                temp = temp->next;
            }; //Èùåì Гў Г±ГЇГЁГ±ГЄГҐ Г*äðåñ äåñêðèïòîðГ*, Г·ГҐГ© ñëåäóþùèé ýëåìåГ*ГІ Г± Г*óëåâûì ГіГЄГ*Г§Г*òåëåì
            
            my_memory.free_block(temp->next->position); //îñâîáîäèòü ýòîò áëîê
            temp->next = NULL; //Г“Г*è÷òîæèòü áëîê
            local_pointer = temp->position; //ÏðèñâГ*ГЁГўГ*ГҐГ¬ Г*äðåñ Г*Г* âåðõóøêó Г±ГІГҐГЄГ*
            pos = BLOCK_SIZE - 2; // ÏîñëåäГ*ГїГї ïîçèöèÿ Гў ýòîì áëîêå
        }
        else throw(1);
        
    }
    //int *p = (local_pointer + pos);
    int res = *(local_pointer + pos); //Èçâëåêè Г¤Г*Г*Г*ûå
    //cout << "pos = " << pos << " ";
    //if (res == 59) throw(2);
    /*static bool first = true;
    if (first)
    {
        my_memory.print(0,20);
        first = false;
    } */
    return res;
}
 
stack::~stack(void)
{
}
 
int stack::debug_info_pos()
{ 
    return pos;
};
 
Memory::Memory(void)
{
    data = new int[ARRAY_SIZE];
    indexes = new char[NUMBER_OF_POINTERS];
    for (int i = 0; i < NUMBER_OF_POINTERS; i++)
        indexes[i] = 0; //Âñå ñâîáîäГ*Г®
}
 
int* Memory::allocate_block()
{
    int i = 0;
    while (i++ < NUMBER_OF_POINTERS)
    {
        if (indexes[i] == 0) //Åñëè ýòîò áëîê ñâîáîäåГ*
        {
            indexes[i] = 1; //ÓñòГ*Г*îâèòü ГґГ«Г*ГЈ Г§Г*Г*ÿòîñòè
            return &data[BLOCK_SIZE*i]; //ÂåðГ*ГіГІГј ГіГЄГ*Г§Г*òåëü Г*Г* ýòîò áëîê. ÄëèГ*Г*Г* ГЄГ*æäîãî áëîêГ* BLOCK_SIZE
        }
    }
    
    return NULL; //ГЌГҐГІ ГІГ*êîé ГЇГ*ìÿòè
}
 
void Memory::free_block(int* p)
{
    int offset = (p - &data[0])/sizeof(int); //Îïðåäåëè ñìåùåГ*ГЁГҐ
    indexes[0] = 0; //ÓñòГ*Г*îâè ГґГ«Г*ГЈ ñâîáîäГ*îñòè
}
 
Memory::~Memory(void)
{
 
};
/*void Memory::print(int a,int b)
{
    for (int i = a; i < b; i++)
        cout << "memory[" << i << "] = " << data[i] << endl;
    cout << endl;
}*/
Выложил, вдруг кому-то станет интересен принцип.

Добавлено через 33 секунды
Результат:
1220 C++ Accepted 0.078 761 KB
Добавлено через 55 секунд
Извиняюсь за кодировку...
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 22:41  [ТС] #26
Цитата Сообщение от GRANDEATH Посмотреть сообщение
как делать тоже самое, только с битами
кажется на си++ есть библиотека для работы с битмасками

Добавлено через 9 минут
подскажите как мне доделать свой вариант? катать ваш пример не хочу, толку будет мало, а так в голове останется..
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 23:31 #27
Я так понимаю, что ты хочешь сделать через списки.
Тебе потребуется массив из 1000 структур, содержащие
1. Смещение внутри твоего 19-ти элементного блока
2. Указатель на начало списка

Список состоит из структур, котрые, как уже я увидел ты сделал.

Суть в чем - у тебя есть массив из структур, назови его своеобразной кучей
struct data_block
{
int data[19];
data_block *next;
}
и есть массив битов, которые показывают свободен ли этот блок.
1. Запись
Записывай в текущем блоке преременные, пока смещение не будет 18 (счет в си с 0 )
Если блок забит - найди по биту первый свободный блок и пристыкуй его к своему списку.
Установи смещение на 0.
2. Чтение.
Считывай, пока смещение не станет 0.Как только стало нулем отстыкуй блок. Пометь его как свободный (для дальнейшего использования). Установи смещение на 18 (последный элемент).

В целом - это примитивный алгоритм.
Я бы описал основные данные так:
struct data_block
{
int data[19];
data_block *next;
} - твоя единица памяти
data_block array[ Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ];
byte access[Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ]; // Здесь бы использовать битовое поле. Но я его не знаю.

struct stack_begin
{
int offset;
data_block* last; //Это излишне. Для того, что бы каждый раз тебе не пробегать по списку, для нахождения последнего элемента. Быстродействие увечилит в разы, а память сожрет только паку килобайт (ну или десятков)
data_block* first; //Указатель на первый блок
}

Теперь надо будет обьявить пару функций
1. Запихни в стек
2. Вытащи из стека
+ дополнит. функции
1. Верни свободный блок из кучи
2. Возвтрати блок в кучу.
3. Верни адрес предпоследнего блока в списке.
Ты так хотел делать?
1
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2010, 09:55  [ТС] #28
GRANDEATH, то как я хотел сделать я сделал, дальше я потерялся, просто у меня выходит, что выделяем мы память сразу всю, и при этом говорим две вещи:
1) каждому непустому стеку как минимум 1 блок
2) в каждом блоке 19 элементов
Вот эти две вещи меня и запутали, т.к. у нас каждый стек, который занимает больше N*19 элементов будет занимать на 18*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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set, //масив, для занятых/свободных блоков
       * heap; //блок на все стеки, или просто куча
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top; 
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int)); // вделяем память на "битмаску" и "кучу"
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0); //освобождаем --||--
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find() //ищем и возвращаем указатель на ближайший свободный блок
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n) //определяем блок как свободный
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack() //выделяем память на корень стека
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack() //освобождаем память
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size) //если текущий блок забит ищем новый
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0) //если текущий блок пуст, переходим к предыдущему
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[top--];
}
Есть проблемка: почему-то int stack :: pop() пашет неправельно, он достает элемент перед тем который надо достать

Добавлено через 39 минут
поисправлял ошибки, int stack :: pop() возвращала не предыдущий а следующий, вот верный код:
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
        head->val[top++] = n;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[--top];
}
Добавлено через 3 минуты
С++ Wrong answer 0.015сек 481 КБ

Добавлено через 5 минут
У меня вылетает последний елемент блока

Добавлено через 6 минут
нашел, исправил,
вот
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size;
    }
    return head->val[--top];
}


Добавлено через 1 минуту
Результат проверки № теста Время работы Выделено памяти
Memory limit exceeded 10 0.062 869 КБ
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
11.01.2010, 15:41 #29
Memory limit exceeded 10 0.062 869 КБ
Вот оно и гадость( Попробуй выделить не 20, а 40?
+ сотри #icnclude <iostream>
Мало ли что системе в голову взбредет...
1
odip
Эксперт С++
7157 / 3219 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.01.2010, 15:45 #30
Memory limit exceeded 10 0.062 869 КБ
Да фигню какую-то в коде написал.
Например зачем вот это:
Memory::Memory()
{
bit_set = (int *) calloc (heap_size, sizeof(int));
heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2010, 15:45
Привет! Вот еще темы с ответами:

Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? - C++
Есть у меня пробелы в познаниях, хотел бы их устранить. 1. Что такое стек в самом языке С++ ? 2. В какой памяти он хранится и почему...

при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"? - C++
Сабж g++ 4.5.0

исчезла папка обьемом 13Гб. нет и ее и в скрытых файлах. - Носители информации
Здравствуйте! Может поможете в решении проблемы: После использования программы SAFE1.8(прячет файлы в сейф ), на переносном жестком...

Прочитать последовательность из файла и создать стек в памяти - Pascal
В файл записывается последовательность целых чисел. Прочитать последовательность из файла и создать стек в памяти из этих чисел таким...


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
11.01.2010, 15:45
Ответ Создать тему
Опции темы

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