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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как считать строку? http://www.cyberforum.ru/cpp-beginners/thread84194.html
Зачем надо при считывания переменной типа string надо писать getline(cin, ...)? Зачем там cin? Разве там ожет быть что либо иное?
C++ Оценка времени работы Можете оценить время работы алгоритма? http://acm.timus.ru/problem.aspx?space=1&num=1100 - это задача, на которую он проходит По моему мнению это O( 3*(N+M) ), или просто O(N+M), где N - количество команд, M - количество задач #include <iostream> #define FOR(i,a,b) for (int i(a),_b(b); i < _b; ++i) int main() { http://www.cyberforum.ru/cpp-beginners/thread84187.html
C++ считывает текст из файла
Написать программу, которая считывает текст из файла и выводит на экран только строки, не содержащие двузначных чисел.
В чём ошибка? C++
мне надо чтоб програма получив строку проверила её и если в ней есть двузначные числа выводила всю строку. что я не так сделал? #include "stdafx.h" #include "iostream" #include "cctype" using namespace std; int _tmain(int argc, _TCHAR* argv) { bool flag; char *c=new char;
C++ Создать матрицу B, каждый элемент которой равен произведению соответствующего элемента А на номер его строки http://www.cyberforum.ru/cpp-beginners/thread84179.html
Добрый день уважаемые форумчане! Помогите пожалуйста с решением задачи в Visual Studio 2008, я не представляю как решить. Искала по форуму аналогичное задание-ничего не нашла! Задана прямоугольная матрица А={a(ij)} размером 5х4 0.28 1.35 0.26 -0.23 1.89 1.64 1.16 -0.84 А={1.31 -0.17 0.29 -0.42 -0.89 -0.45 1.72 0.19
C++ Вырезать из матрицы всё лишнее, чтобы осталась только закрашенная часть Как можно вырезать из матрицы всё лишнее, чтобы осталась только закрашенная часть? подробнее

Показать сообщение отдельно
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2010, 09:55  [ТС]     Быстрый стек, с малым обьемом памяти
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 КБ
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru