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

Динамическая структура данных(контейнер) типа "Вектор" - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
Кепит
0 / 0 / 0
Регистрация: 11.10.2012
Сообщений: 25
30.10.2012, 01:37     Динамическая структура данных(контейнер) типа "Вектор" #1
Здравствуйте, у меня вот какая проблема:задали лабораторную работу, но я что то никак не могу понять как ее делать, дело в том, что в ней нельзя использовать объекты, классы, шаблоны классов, а также библиотеку STL.

Разработайте в MS Visual Studio программное решение на языке Си,
которое реализует динамическую структуру данных (контейнер) типа «Динамический
массив (вектор)». Каждый элемент контейнера содержит строки символов произвольной
длины.

В программном решении следует реализовать следующие операции над контейнером:
• создание и уничтожение контейнера;
• поиск, добавление и извлечение элементов контейнера;
• обход всех элементов контейнера в прямом и обратном направлениях (итератор);
• удаление из контейнера дублирующих элементов;
• вычисление количества элементов в контейнере;
• сортировка элементов контейнера;
• объединение, пересечение и вычитание контейнеров;
• сохранение контейнера в дисковом файле и восстановление контейнера из файла.
Если можно покажите пару-тройку реализаций из
этого списка в качестве примера, буду очень признателен.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
30.10.2012, 03:20     Динамическая структура данных(контейнер) типа "Вектор" #2
Вам в раздел Си, не?

> но я что то никак не могу понять как ее делать, дело в том, что в ней нельзя использовать объекты, классы, шаблоны классов, а также библиотеку STL.

Как-как, структурами, функциями и дефайнами!

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct vector {
    char **data;
    size_t size;
};
 
inline void INIT_VECTOR(struct vector *vec)
{
    vec->data = NULL;
    vec->size = 0;
}
 
void clean_vector(struct vector *vec)
{
    size_t i;
    for (i = 0; i < vec->size; ++i) {
        free(vec->data[i]);
    }
    free(vec->data);
    vec->data = NULL;
    vec->size = 0;
}
 
inline void delete_vector(struct vector *vec)
{
    clean_vector(vec);
    free(vec);
}
 
struct vector* create_empty_vector(void)
{
    struct vector *res = malloc(sizeof(*res));
    if (!res) {
        return NULL;
    }
    INIT_VECTOR(res);
    return res;
}
 
struct vector* create_vector(size_t size, const char *init)
{
    size_t i;
    size_t init_len;
    struct vector *res = create_empty_vector();
    if (!res) {
        return NULL;
    }
    
    res->data = malloc(size * sizeof(*res->data));
    if (!res->data) {
        return res;
    }
    init_len = strlen(init) + 1;
    for (i = 0; i < size; ++i) {
        if (!(res->data[i] = malloc(init_len))) {
            res->size = i;
            goto cleanup;
        }
        strcpy(res->data[i], init);
    }
    res->size = size;
    goto out;
cleanup:
    clean_vector(res);
out:
    return res;
}
 
int vector_set(struct vector *vec, size_t index, const char *data)
{
    char *new_el;
    
    if (index >= vec->size) return -1;
 
    new_el = realloc(vec->data[index], strlen(data) + 1);
    if (!new_el) {
        return -1;
    }
    strcpy(new_el, data);
    vec->data[index] = new_el;
    return 0;
}
 
#define vector_foreach_forward(ptr, vector)       \
    for ((ptr) = (vector)->data;                  \
         (ptr) < (vector)->data + (vector)->size; \
         ++(ptr))
 
int main(void)
{
    struct vector *vec = create_vector(5, "1");
    
    char **str;
    vector_foreach_forward(str, vec) {
        printf("%s ", *str);
    }
    printf("\n");
    
    vector_set(vec, 3, "42");
    
    vector_foreach_forward(str, vec) {
        printf("%s ", *str);
    }
    delete_vector(vec);
    return 0;
}
Кепит
0 / 0 / 0
Регистрация: 11.10.2012
Сообщений: 25
30.10.2012, 18:25  [ТС]     Динамическая структура данных(контейнер) типа "Вектор" #3
А что означает функция inline и можно ли ее убрать? Просто мы ее не изучали и и вроде как использовать нельзя.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
30.10.2012, 18:38     Динамическая структура данных(контейнер) типа "Вектор" #4
Это такой намёк компилятору, чтобы он постарался все вызовы этой функции заменить прямиком на её код. Можно убрать, ничего не поломается (в смысле, если само слово убрать).
Кепит
0 / 0 / 0
Регистрация: 11.10.2012
Сообщений: 25
30.10.2012, 22:54  [ТС]     Динамическая структура данных(контейнер) типа "Вектор" #5
А можете как-то пояснить в виде комментариев,хотя бы несколько функций?Я просто не совсем понимаю что к чему.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
30.10.2012, 23:42     Динамическая структура данных(контейнер) типа "Вектор" #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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/*
 * Представляет вектор. Хранит массив строк с данными и длину этого массива.
 */
struct vector {
    char **data;
    size_t size;
};
 
/* Инциализация @vec.
 * Естественно, это не обнуление; просто чтоб мусор убрать.
 */
inline void INIT_VECTOR(struct vector *vec)
{
    vec->data = NULL;
    vec->size = 0;
}
 
/* А вот это обнуление @vec.
 * Сначала удаляем каждую строку, затем весь массив строк,
 * затем затираем данные NULL на всякий пожарный.
 * И размер в ноль, естессно.
 */
void clean_vector(struct vector *vec)
{
    size_t i;
    for (i = 0; i < vec->size; ++i) {
        free(vec->data[i]);
    }
    free(vec->data);
    vec->data = NULL;
    vec->size = 0;
}
 
/* Для удобства. Обнулить @vec и удалить из кучи.
 * Не стоит это применять для векторов созданных *не* create_vector().
 */
inline void delete_vector(struct vector *vec)
{
    clean_vector(vec);
    free(vec);
}
 
/* Динамически создать новый пустой вектор.
 *
 * Если какие-то проблемы с выделением, возвращаем NULL.
 *
 * INIT_VECTOR() вызывается как раз для того, чтобы убрать мусор,
 * который возможно был в памяти. После неё у нас чистый опрятный вектор.
 */
struct vector* create_empty_vector(void)
{
    struct vector *res = malloc(sizeof(*res));
    if (!res) {
        return NULL;
    }
    INIT_VECTOR(res);
    return res;
}
 
 
/* Динамически создать новый вектор размер @size, заполненный строками @init.
 *
 * Пытаемся создать сначала пустой вектор. Проблемы - NULL.
 * Потом выделяем место под указатели на строки. Проблемы - пустой вектор.
 * Потом выделяем место под сами строки. Проблемы - удаляем всё, что
 * навыделяли и возвращаем пустой вектор.
 * 
 * Если всё окей, копирум строку @init во все новые элементы вектора,
 * устанавливаем новый размер вектора и выходим, вернув созданный вектор.
 */
struct vector* create_vector(size_t size, const char *init)
{
    size_t i;
    size_t init_len;
    struct vector *res = create_empty_vector();
    if (!res) {
        return NULL;
    }
    
    res->data = malloc(size * sizeof(*res->data));
    if (!res->data) {
        return res;
    }
    init_len = strlen(init) + 1;
    for (i = 0; i < size; ++i) {
        if (!(res->data[i] = malloc(init_len))) {
            res->size = i;
            goto cleanup;
        }
        strcpy(res->data[i], init);
    }
    res->size = size;
    goto out;
cleanup:
    clean_vector(res);
out:
    return res;
}
 
 
/* Установить элемент @vec с индексом @index равным @data.
 *
 * Выход за границы - вернуть -1 и ничего не трогаем.
 *
 * Изменяем размеры строки, которую мы будем менять, чтобы в неё влезли
 * новые данные. Проблемы - возвращаем -1 и ничего не трогаем.
 * 
 * Если всё окей, копирум строку @data, обновляем элемент и выходим.
 */
int vector_set(struct vector *vec, size_t index, const char *data)
{
    char *new_el;
    
    if (index >= vec->size) return -1;
 
    new_el = realloc(vec->data[index], strlen(data) + 1);
    if (!new_el) {
        return -1;
    }
    strcpy(new_el, data);
    vec->data[index] = new_el;
    return 0;
}
 
/* Устраивает цикл для обхода вектора @vector в прямом порядке. Итератор -
 * указатель @ptr (типа char**), который должен быть создан и макросу заранее.
 *
 * Раскрывается это всё, очевидно, в цикл for. В нём можно использовать *ptr,
 * чтобы добраться до текущего просматриваемого элемента вектора.
 */
#define vector_foreach_forward(ptr, vector)       \
    for ((ptr) = (vector)->data;                  \
         (ptr) < (vector)->data + (vector)->size; \
         ++(ptr))
 
int main(void)
{
    struct vector *vec = create_vector(5, "1");
    
    char **str;
    vector_foreach_forward(str, vec) {
        printf("%s ", *str);
    }
    printf("\n");
    
    vector_set(vec, 3, "42");
    
    vector_foreach_forward(str, vec) {
        printf("%s ", *str);
    }
    delete_vector(vec);
    return 0;
}
Yandex
Объявления
30.10.2012, 23:42     Динамическая структура данных(контейнер) типа "Вектор"
Ответ Создать тему
Опции темы

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