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

фаил! что от меня хотят?! - C++

Восстановить пароль Регистрация
 
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
20.02.2011, 08:41     фаил! что от меня хотят?! #1

это задание моего варианта по пяву
но дело вовсе не в том что я не могу решить.... я даже понять задание толком не могу...

1.Моделирование распределения памяти в операционной системе. Дан линейный односвязный список свободных блоков памяти (адрес начала блока, размер блока). На входе подается запрос на блок памяти определенного размера. Требуется найти в списке первый подходящий по размеру узел, произвести необходимые изменения в списке или выдать сообщение, что подходящего блока памяти в списке нет.

особенно добивает фраза произвести необходимые изменения в списке
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.02.2011, 10:06     фаил! что от меня хотят?! #2
olleg90, да вроде все понятно. Список хранит некую в качестве своих элементов некоторые структуры, которые моделируют блоки памяти. В некоторый момент времени определенные узлы этого списка (т.е. блоки памяти) помечены как свободные, другие - как занятые. Из постановки задачи следует, что размер блока не является одинаковым для каждого узла. Под "необходимыми изменениями" можно понимать следующее: пометить блок памяти (узел списка) как занятый.
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
20.02.2011, 12:20  [ТС]     фаил! что от меня хотят?! #3
мне кажется что не все так сложно.... видимо надо изменить стек таким образом что бы нужный узел был первым...
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.02.2011, 12:41     фаил! что от меня хотят?! #4
Цитата Сообщение от olleg90 Посмотреть сообщение
мне кажется что не все так сложно.... видимо надо изменить стек таким образом что бы нужный узел был первым...
а вот это гораздо сложнее, чем я предложил. Сейчас выложу свой вариант.

Добавлено через 20 минут
Вот. Программа принимает один необязательный аргумент - число блоков, которые содержатся в нашей памяти. Выделение памяти происходит так: первоначальный размер блока равен 1 байту, каждые четыре блока размер блока увеличивается на 1 байт. Т.е., размеры первых блоков таковы: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, ... Запрос блока происводится с помощью функции lookupForMemBlock, которая возвращает адрес начала выделенной для блока памяти, помечая блок как занятый, или NULL, если нет свободного блока памяти заданного размера.
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
209
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
 
#define safeFree(ptr) free(ptr), ptr = NULL
 
#define BLOCKS_NUM 100      /* count of blocks */
#define MAX_SIZE 256        /* max block size in bytes */
 
typedef struct
{
    int isFree;
    void*  memPtr;
    size_t memSize;
} memBlock_t;
 
typedef struct node
{
    memBlock_t value;
    struct node* next;
} node_t;
 
typedef struct
{
    node_t* head;
    node_t* tail;
    size_t  size;
} list_t;
 
typedef list_t* pMemory_t;
 
void emptyMem(pMemory_t);
void addBlock(pMemory_t, memBlock_t);
void clearMem(pMemory_t);
void initializeMem(pMemory_t, size_t);
 
void* lookupForMemBlock(pMemory_t, size_t);
int freeMemBlock(pMemory_t, void*);
 
void errExit(int, const char*, ...);
 
int main(int argc, char* argv[])
{
    size_t cnt;
    pMemory_t memory;
    char* endptr;
    char* words[6];
    size_t i = 0;
    size_t len;
    
    const char constWords[6][4] = { "abc", "acb", "bac", "bca", "cab", "cba" };
        
    if(argc > 2)
    errExit(1,
        "Too many arguments were specified: %d\n"
        "Usage: %s [BLOCKS].\n",
        argc - 1, *argv);
 
    if(argc == 2)
    {
    cnt = strtoul(argv[1], &endptr, 10);
    if(*argv[1] == '\0' || *endptr != '\0')
        errExit(1, "Block count `%s' is not a valid unsigned decimal number.\n", argv[1]);
    }
    else
    cnt = BLOCKS_NUM;
    
    if((memory = malloc(sizeof(list_t))) == NULL)
    errExit(1, "Memory allocation failure.\n");
 
    initializeMem(memory, cnt);
 
    for(i = 0, len = strlen(*constWords); i < 6 && len < MAX_SIZE; )
    {
    if((words[i] = lookupForMemBlock(memory, len + 1)) == NULL)
    {
        ++len;
        
        /* Print error and continue */
        errExit(0, "Can't allocate memory block with size %u byte(s). "
            "Now looking for one with size %u byte(s)\n", len, len + 1);
        continue;
    }
    strcpy(words[i], constWords[i]);
    
    ++i;
    }
 
    if(len == MAX_SIZE)
    errExit(1, "Max block size is reached: %u.\n", MAX_SIZE);
    
    for(i = 0; i < 6; ++i)
    printf("word #%u: `%s'.\n", i + 1, words[i]);
            
    clearMem(memory);
    
    exit(0);
}
 
void emptyMem(pMemory_t mem)
{
    mem->head = mem->tail = NULL;
    mem->size = 0;
}
 
void addBlock(pMemory_t mem, memBlock_t block)
{
    node_t* pnode;
    if((pnode = malloc(sizeof(node_t))) == NULL)
    errExit(1, "Memory allocation failure.\n");
 
    pnode->value = block;
    pnode->next = NULL;
 
    if(mem->tail == NULL)
    mem->head = pnode;
    else
    pnode->next = mem->tail;
    
    mem->tail = pnode;
    
    ++(mem->size);
}
 
void clearMem(pMemory_t mem)
{
    node_t* pnode;
    
    pnode = mem->tail;
    while(pnode != NULL)
    {
    mem->tail = mem->tail->next;
    safeFree(pnode->value.memPtr);
    safeFree(pnode);
    --(mem->size);
    pnode = mem->tail;
    }
 
    safeFree(mem);
}
 
void initializeMem(pMemory_t mem, size_t cnt)
{
    size_t memSize;
    size_t i;
    memBlock_t block;
 
    block.isFree = 1;
    
    emptyMem(mem);
 
    for(i = 0, memSize = 1;
    i < cnt;
    ++i, memSize += (i % 4 == 0 ? 1 : 0))
    {
    if((block.memPtr = malloc(memSize)) == NULL)
        errExit(1, "Memory allocation failure.\n");
    block.memSize = memSize;
    addBlock(mem, block);
    }
}
 
void errExit(int code, const char* fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    vfprintf(stderr, fmt, ap);
    va_end(ap);
    if(code)
    exit(code);
}
 
void* lookupForMemBlock(pMemory_t mem, size_t size)
{
    node_t* pnode;
 
    pnode = mem->tail;
    while(pnode != NULL)
    {
    if(pnode->value.isFree && pnode->value.memSize == size)
    {
        pnode->value.isFree = 0;
        return pnode->value.memPtr;
    }
    pnode = pnode->next;
    }
 
    return NULL;
}
 
int freeMemBlock(pMemory_t mem, void* ptr)
{
    node_t* pnode;
 
    pnode = mem->tail;
    while(pnode != NULL)
    {
    if(pnode->value.memPtr ==  ptr)
    {
        pnode->value.isFree = 1;
        return 1;
    }
 
    pnode = pnode->next;
    }
 
    return 0;
}
В функции main происходит тестирование описанных функций. В ней мы сначала инициализируем память с заданным количеством блоков, потом пытаемся выделить память под массив из 6 строк, чтобы скопировать в них массив constWords и вывести их на экран. Если запускать программу без аргументов, программа успешно выделит память под 4 строки размера 4 байт (размер строк из constWords), после чего блоки памяти по 4 байта закончатся. Следующая попытка закончится неудачей (т.к. мы имеем всего по 4 блока памяти каждого размера), программа напечатает сообщение об ошибке, увеличит размер памяти, которая будет выделятся, на 1 байт, и продолжит попытки довыделить память под оставшиеся 2 строки или завершится с ошибкой, если этого не получится.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
20.02.2011, 13:09     фаил! что от меня хотят?! #5
Nameless One,
Цитата Сообщение от Nameless One Посмотреть сообщение
а вот это гораздо сложнее
Это вы, конечно, в относительном смысле имеете ввиду? Ведь поменять местами пару указателей в разных узлах списка - задача тривиальная. Но ваш вариант более соответствует здравому смыслу.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.02.2011, 13:13     фаил! что от меня хотят?! #6
silent_1991, ну, может про "гораздо" я погорячился, но во-первых, это сложнее, чем изменить значение флага isFree, во-вторых, я просто-напросто не понимаю, как можно решить задачу таким способом.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
20.02.2011, 13:23     фаил! что от меня хотят?! #7
Цитата Сообщение от Nameless One Посмотреть сообщение
я просто-напросто не понимаю, как можно решить задачу таким способом
Это да, с этим не поспоришь .
Может надо ввести фиктивный блок-разделитель, слева от которого используемые блоки памяти, справа - не использованные. Вот так и тягать эти блоки справа налево и наоборот)))
Но, повторюсь, флагом и логичнее, и проще.
olleg90
 Аватар для olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
21.02.2011, 15:23  [ТС]     фаил! что от меня хотят?! #8
Большое спасибо за помощь сегодня узнал у преподавателя что значит "произвести необходимые изменения в списке". Nameless One был прав)
Цитата Сообщение от Nameless One Посмотреть сообщение
Под "необходимыми изменениями" можно понимать следующее: пометить блок памяти (узел списка) как занятый.
почти так, только если блок памяти равен по величине с размером необходимого блока то удаляем узел из стека, если же блок памяти больше искомого то необходимо увеличить адреса на размер исходного блока и уменьшить значение текущего блока на значение искомого. вот
сегодня или завтра выложу свой код)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2012, 17:52     фаил! что от меня хотят?!
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
tyu
1 / 1 / 0
Регистрация: 09.03.2012
Сообщений: 5
09.03.2012, 17:52     фаил! что от меня хотят?! #9
Напиши свой код если не трудно тоже такая работа попалась.
Yandex
Объявления
09.03.2012, 17:52     фаил! что от меня хотят?!
Ответ Создать тему
Опции темы

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