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

Динамические Списки!!!! Очень нужно...! - C++

Восстановить пароль Регистрация
 
Nyto4ka
0 / 0 / 0
Регистрация: 10.05.2010
Сообщений: 22
01.07.2010, 18:14     Динамические Списки!!!! Очень нужно...! #1
Помогите пожалуйста решить задачи на Си....горит стипендия((
Задача 1.
Описать функцию, которая за каждым отрицательным элементом очереди вставляет элемент, содержащий его значение по модулю.
Задача 2.
Описать функцию, которая подсчитывает количество элементов дека начинающихся с одной и той же буквы. Результатом является последовательность букв и соответствующее количество слов.

Для каждого задания необходимо написать функцию создания структуры (Create()), добавления элемента (Add()), удаления элемента (Delete()) и поэлементной печати структуры. Для реализации структур очередь и стек использовать динамические списки. При реализации программы осуществить контроль вводимых данных.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.07.2010, 18:14     Динамические Списки!!!! Очень нужно...!
Посмотрите здесь:

Динамические списки C++
C++ Динамические структуры.Списки
Динамические структуры (связанные списки) C++
Динамические списки C++
C++ Две задачи на списки (динамические структуры)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.07.2010, 02:23     Динамические Списки!!!! Очень нужно...! #2
Nyto4ka, первая вот:
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
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <ctype.h>
#include <limits.h>
 
typedef struct NODE {
    long val;
    struct NODE * next;
} node_t;
 
node_t * new_node(long val, node_t * last){
    node_t * n;
    if ( ( n = (node_t*)malloc(sizeof(node_t)) ) == NULL )
        return NULL;
    n->val = val;
    n->next = NULL;
    if ( last )
        last->next = n;
    return n;
}
 
int insert_after(node_t * prev, long val){
    node_t * n;
    if ( ! prev )
        return -1;
    if ( ( n = (node_t*)malloc(sizeof(node_t)) ) == NULL )
        return -1;
    n->val = val;
    n->next = prev->next;
    prev->next = n;
    return 0;
}
 
/* возвращает указатель на структуру, после которой не получилось добавить элемент,
   или NULL если ошибок небыло */
node_t * add_abs(node_t * n){
    node_t * a;
    while ( n ){
        if ( n->val < 0 ){
            if ( insert_after(n, n->val * -1) )
                break;
        }
        n = n->next;
    }
    return n;
}
 
void print_nodes(const node_t * n, int width){
    while ( n ){
        printf("%*ld\n", width, n->val);
        n = n->next;
    }
}
 
void delete_nodes(node_t * n){
    node_t * t;
    while ( n ){
        t = n->next;
        free(n);
        n = t;
    }
}
 
/* возвращает 0 если в *pNum удалось поместить число,
   1 если ввод закончен, и -1 в случае ошибки */
int get_num(long * pNum){
    static char buf[BUFSIZ] = { 0 };
    char * tail;
    printf("Number: ");
    if ( ! fgets(buf, BUFSIZ, stdin) ){
        fprintf(stderr, "Can't get string.\n");
        return -1;
    }
    if ( *buf == '\n' )
        return 1;
    if ( ! isdigit(*buf) && *buf != '-' && ! isspace(*buf) ){
        fprintf(stderr, "Not a number.\n");
        return -1;
    }
    *pNum = strtol(buf, &tail, 10);
    if ( errno == ERANGE ){
        if ( *pNum == LONG_MAX )
            fprintf(stderr, "Too big.\n");
        else
            fprintf(stderr, "Too small.\n");
        errno = 0;
        return -1;
    }
    if ( ! isspace(*tail) ){
        fprintf(stderr, "Only digits allowed.\n");
        return -1;
    }
    return 0;
}
 
/* Описать функцию, которая за каждым отрицательным элементом очереди вставляет элемент,
    содержащий его значение по модулю. */
 
#define WIDTH 10
 
int main(void){
    node_t * first, * last;
    long val;
    int ret;
 
    first = last = NULL;
    printf("Enter some numbers. Empty string - finish.\n");
    while ( 1 ){
        if ( ! ( ret = get_num(&val) ) ){
            if ( ( last = new_node(val, last) ) == NULL ){
                fprintf(stderr, "Memory or another error.\n");
                if ( first )
                    delete_nodes(first);
                exit(EXIT_FAILURE);
            }
            if ( ! first )
                first = last;
        }
        else if ( ret == -1 )
            fprintf(stderr, "Wrong number! Try another one...\n");
        else
            break;
    }
 
    if ( ! first ){
        fprintf(stderr, "No values in list.\n");
        exit(EXIT_FAILURE);
    }
 
    printf("\nEntered values:\n");
    print_nodes(first, WIDTH);
 
    if ( last = add_abs(first) ){
        fprintf(stderr, "Can't add absolute value after %ld\n", last->val);
        delete_nodes(first);
        exit(EXIT_FAILURE);
    }
 
    printf("\nValues with added absolute if needed:\n");
    print_nodes(first, WIDTH);
 
    delete_nodes(first);
    exit(EXIT_SUCCESS);
}
проверяйте, если что - спрашивайте...
А вторую задачу просто не понял - каких элементов какого "дека"?
fasked
02.07.2010, 04:04
  #3

Не по теме:

Цитата Сообщение от easybudda Посмотреть сообщение
каких элементов какого "дека"?
может быть dqueue

Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
02.07.2010, 04:23     Динамические Списки!!!! Очень нужно...! #4
Цитата Сообщение от easybudda Посмотреть сообщение
каких элементов какого "дека"
Может, это?
Дек (контейнер deque) представляет последовательность элементов, оптимизированную для добавления и уничтожения элементов с обоих концов контейнера. Кроме того, он обеспечивает достаточно быстрый произвольный доступ. Однако на деки не распространяется основное ограничение векторов - необходимость хранения всех элементов в непрерывном блоке памяти. Вместо этого в типичной реализации дека используется цепочка блоков, каждый из которых содержит непрерывную последовательность элементов (все блоки и порядок их следования отслеживаются контейнером в нерперывной структуре данных). При такой базовой структуре затраты на добавление и удаление элементов с любого конца дека относительно невелики. Вдобавок, деку, в отличие от вектора, не приходится копировать и уничтожать объекты при выделении нового блока, поэтому при добавлении заранее неизвестного количества элементов с любого конца контейнера дек работает гораздо эффективнее вектора. Таким образом, вектор оптимален лишь в том случае, если вы хорошо знаете, сколько объектов будет храниться в контейнере.

Формат

template <
class Type,
class Allocator=allocator<Type>
>
class deque

Параметры

Type
Тип элемента данных, хранящихся в деке.
Allocator
Тип, представляющий хранящийся объект-распределитель, который инкапсулирует детали распределения памяти для дека. Этот аргумент - необязательный, значение по умолчанию - allocator<Type>.
Nyto4ka
0 / 0 / 0
Регистрация: 10.05.2010
Сообщений: 22
02.07.2010, 22:10  [ТС]     Динамические Списки!!!! Очень нужно...! #5
easybudda! спасибо большое, вроде бы все понятно...а дека я и сама не знаю что это такое...(
Den UA
0 / 0 / 0
Регистрация: 23.06.2010
Сообщений: 9
12.07.2010, 13:34     Динамические Списки!!!! Очень нужно...! #6
Скорей всего не дека а списка! Задача же по Динамическим спискам!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2010, 19:23     Динамические Списки!!!! Очень нужно...!
Еще ссылки по теме:

C++ Динамические структуры. Односвязные линейные списки
C++ Динамические структуры. Линейные списки
Динамические структуры данных. Списки C++

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
12.07.2010, 19:23     Динамические Списки!!!! Очень нужно...! #7
Цитата Сообщение от Den UA Посмотреть сообщение
Скорей всего не дека а списка!
Вот и я так и не придумал, куда там двухстороннюю очередь прилепить... Вот со списками:
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
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
 
typedef struct WRD {
    char * text;
    struct WRD * next;
} wrd_t;
 
typedef struct CHARCOUNT {
    char ch;
    int cnt;
    struct CHARCOUNT * next;
} charcount_t;
 
wrd_t * new_word(const char * s, wrd_t * last){
    wrd_t * w;
    if ( ( w = (wrd_t*)malloc(sizeof(wrd_t)) ) == NULL )
        return NULL;
    if ( ( w->text = strdup(s) ) == NULL ){
        free(w);
        return NULL;
    }
    w->next = NULL;
    if ( last )
        last->next = w;
    return w;
}
 
void clear_words(wrd_t * w){
    wrd_t * t;
    while ( w ){
        t = w->next;
        free(w->text);
        free(w);
        w = t;
    }
}
 
wrd_t * words_list(const char * string, const char * delim){
    char * buf, * p;
    wrd_t * first, * last;
 
    first = last = NULL;
    if ( ( buf = strdup(string) ) == NULL ){
        fprintf(stderr, "Memory error!\n");
        return NULL;
    }
    for ( p = strtok(buf, delim); p != NULL; p = strtok(NULL, delim) ){
        if ( ( last = new_word(p, last) ) == NULL ){
            fprintf(stderr, "Can't add word to list!\n");
            if ( first )
                clear_words(first);
            free(buf);
            return NULL;
        }
        if ( ! first )
            first = last;
    }
    free(buf);
    return first;
}
 
charcount_t * new_counter(const wrd_t * w, charcount_t * last){
    charcount_t * chcnt;
    if ( ( chcnt = (charcount_t*)malloc(sizeof(charcount_t)) ) == NULL )
        return NULL;
    chcnt->ch = toupper(*(w->text));
    chcnt->cnt = 1;
    chcnt->next = NULL;
    if ( last )
        last->next = chcnt;
    return chcnt;
}
 
void clear_counters(charcount_t * chcnt){
    charcount_t * tmp;
    while ( chcnt ){
        tmp = chcnt->next;
        free(chcnt);
        chcnt = tmp;
    }
}
 
charcount_t * get_counter(const charcount_t * counters, const wrd_t * w){
    char ch = toupper(*(w->text));
    while ( counters ){
        if ( counters->ch == ch )
            break;
        counters = counters->next;
    }
    return (charcount_t*)counters;
}
 
charcount_t * create_counters(const wrd_t * words){
    charcount_t * first, * last, * found;
 
    first = last = NULL;
    while ( words ){
        if ( ( found = get_counter(first, words) ) == NULL ){
            if ( ( last = new_counter(words, last) ) == NULL ){
                fprintf(stderr, "Can't create new counter!\n");
                if ( first )
                    clear_counters(first);
                return NULL;
            }
            if ( ! first )
                first = last;
        }
        else
            found->cnt += 1;
        words = words->next;
    }
    return first;
}
 
charcount_t * first_counter(const charcount_t * cntrs){
    const charcount_t * first = cntrs;
    while ( cntrs = cntrs->next )
        if ( cntrs->ch < first->ch )
            first = cntrs;
    return (charcount_t*)first;
}
 
void swap_counters(charcount_t * a, charcount_t * b){
    charcount_t tmp;
    tmp.ch = a->ch;
    tmp.cnt = a->cnt;
    a->ch = b->ch;
    a->cnt = b->cnt;
    b->ch = tmp.ch;
    b->cnt = tmp.cnt;
}
 
void sort_counters(charcount_t * cntrs){
    charcount_t * first;
    while ( cntrs->next ){
        if ( ( first = first_counter(cntrs) ) != cntrs )
            swap_counters(first, cntrs);
        cntrs = cntrs->next;
    }
}
 
void print_counters(const charcount_t * cntrs){
    printf("Character      Words started\n");
    while ( cntrs ){
        printf("'%c'            %d\n", cntrs->ch, cntrs->cnt);
        cntrs = cntrs->next;
    }
}
 
#define DELIM " ,.!?\t\n"
 
int main(void){
    char buf[BUFSIZ];
    wrd_t * words;
    charcount_t * counters;
 
    printf("String: ");
    if ( ! fgets(buf, BUFSIZ, stdin) ){
        fprintf(stderr, "Can't get some string!\n");
        exit(EXIT_FAILURE);
    }
    if ( ( words = words_list(buf, DELIM) ) == NULL ){
        fprintf(stderr, "Can't create list of words!\n");
        exit(EXIT_FAILURE);
    }
    if ( ( counters = create_counters(words) ) == NULL ){
        fprintf(stderr, "Can't create counters!\n");
        clear_words(words);
        exit(EXIT_FAILURE);
    }
    sort_counters(counters);
    print_counters(counters);
 
    clear_words(words);
    clear_counters(counters);
    exit(EXIT_SUCCESS);
}
Можно было чуть проще сделать, но так интереснее...


Цитата Сообщение от Nyto4ka Посмотреть сообщение
вроде бы все понятно...
может тогда и мне объясните...
C
1
2
3
4
5
6
7
8
9
10
11
12
13
...
node_t * add_abs(node_t * n){
        node_t * a;
        while ( n ){
                if ( n->val < 0 ){
                        if ( insert_after(n, n->val * -1) )
                                break;
                }
                n = n->next;
        }
        return n;
}
...
node_t * a; с какой целью объявлена?
Yandex
Объявления
12.07.2010, 19:23     Динамические Списки!!!! Очень нужно...!
Ответ Создать тему
Опции темы

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