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

Списки - C++

Восстановить пароль Регистрация
 
HardMorg
2 / 25 / 3
Регистрация: 29.08.2010
Сообщений: 204
22.02.2012, 23:50     Списки #1
вопрос, в каких случаях используют односвязный список заместо двух связного?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2012, 23:50     Списки
Посмотрите здесь:

C++ C++ списки
C++ Списки в С++
C++ списки
С++ списки C++
C++ Списки
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
23.02.2012, 00:11     Списки #2
Когда достаточно перемещаться по списку в одну сторону. //КО
HomeR_J_SimpsoN
59 / 59 / 2
Регистрация: 15.10.2010
Сообщений: 356
23.02.2012, 00:13     Списки #3
Когда хочешь сэкономить 4 байта с каждого элемента твоего списка и при этом нет экстра нужды в проходе по списку в разные стороны.

Кратко говоря - все таже проблема время - память)

Если, предположим, тебе нужно достаточно часто получать указатель на родителя данного элемента списка, а список - односвязный, то тебе придется бегать от данного элемента в конец списка, уходить в его начало (если список предварительно не закольцован) и бежать до родителя этого элемента.
Проигрыш во времени. Пусть не очень значительный для небольших структур, но.
Если сделать список двусвязным, получишь сравнительно большой выигрыш во времени, но проиграешь 4 байта с каждого элемента.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
23.02.2012, 01:09     Списки #4
HardMorg, вот Вам пример сортированного односвязного списка. Кстати, ещё важный момент - неизвестное количество данных. Проблема для массивов...
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
    int value;
    struct NODE * next;
} node_t;
 
int insert(node_t ** list, int value){
    node_t * node = malloc(sizeof(node_t));
    if ( ! node )
        return -1;
    node->value = value;
    node->next = NULL;
    
    if ( ! *list )
        *list = node;
    else if ( (*list)->value > value ){
        node->next = *list;
        *list = node;
    }
    else {
        node_t * ptr = *list;
        while ( ptr->next && ptr->next->value < value )
            ptr = ptr->next;
        node->next = ptr->next;
        ptr->next = node;
    }
    
    return 0;
}
 
void dump(const node_t * list){
    while ( list ){
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}
 
void clear(node_t * list){
    node_t * tmp;
    while ( list ){
        tmp = list->next;
        free(list);
        list = tmp;
    }
}
 
int main(void){
    node_t * list = NULL;
    int value;
    
    while ( printf("Value: ") && scanf("%d", &value) == 1 ){
        if ( insert(&list, value) ){
            fprintf(stderr, "Memory error!\n");
            exit(1);
        }
    }
    
    printf("Ascendant sorted:\n");
    dump(list);
    
    clear(list);
    list = NULL;
    
    exit(0);
}
Код
~/cpp/numbers $ gcc -o sorted_list sorted_list.c 
~/cpp/numbers $ ./sorted_list 
Value: 34
Value: 23
Value: 43
Value: 11
Value: 36
Value: q
Ascendant sorted:
11 23 34 36 43 
~/cpp/numbers $
HardMorg
2 / 25 / 3
Регистрация: 29.08.2010
Сообщений: 204
23.02.2012, 15:27  [ТС]     Списки #5
Цитата Сообщение от easybudda Посмотреть сообщение
HardMorg, вот Вам пример сортированного односвязного списка. Кстати, ещё важный момент - неизвестное количество данных. Проблема для массивов...
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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
    int value;
    struct NODE * next;
} node_t;
 
int insert(node_t ** list, int value){
    node_t * node = malloc(sizeof(node_t));
    if ( ! node )
        return -1;
    node->value = value;
    node->next = NULL;
    
    if ( ! *list )
        *list = node;
    else if ( (*list)->value > value ){
        node->next = *list;
        *list = node;
    }
    else {
        node_t * ptr = *list;
        while ( ptr->next && ptr->next->value < value )
            ptr = ptr->next;
        node->next = ptr->next;
        ptr->next = node;
    }
    
    return 0;
}
 
void dump(const node_t * list){
    while ( list ){
        printf("%d ", list->value);
        list = list->next;
    }
    printf("\n");
}
 
void clear(node_t * list){
    node_t * tmp;
    while ( list ){
        tmp = list->next;
        free(list);
        list = tmp;
    }
}
 
int main(void){
    node_t * list = NULL;
    int value;
    
    while ( printf("Value: ") && scanf("%d", &value) == 1 ){
        if ( insert(&list, value) ){
            fprintf(stderr, "Memory error!\n");
            exit(1);
        }
    }
    
    printf("Ascendant sorted:\n");
    dump(list);
    
    clear(list);
    list = NULL;
    
    exit(0);
}
Код
~/cpp/numbers $ gcc -o sorted_list sorted_list.c 
~/cpp/numbers $ ./sorted_list 
Value: 34
Value: 23
Value: 43
Value: 11
Value: 36
Value: q
Ascendant sorted:
11 23 34 36 43 
~/cpp/numbers $
честно говоря я не очень понял зачем вы это написали вопрос был не об этом)
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
23.02.2012, 16:55     Списки #6
Цитата Сообщение от HardMorg Посмотреть сообщение
честно говоря я не очень понял зачем вы это написали вопрос был не об этом)
Пример, когда вполне достаточно односвязного списка - получение заведомо неизвестного количества данных и вывод их в отсортированном виде. По-моему очевидно...
HomeR_J_SimpsoN
59 / 59 / 2
Регистрация: 15.10.2010
Сообщений: 356
23.02.2012, 17:07     Списки #7
Эээм..
Вопрос стоял немного не так...
Когда лучше юзать односвязные, а не двусвязные списки - вот исходник.
Так что немного не в тему)
Посему солидарен с автором)
Без обид
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2012, 19:05     Списки
Еще ссылки по теме:

Списки в c++ C++
Списки, как склеить списки между собой? C++

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

Или воспользуйтесь поиском по форуму:
HardMorg
2 / 25 / 3
Регистрация: 29.08.2010
Сообщений: 204
23.02.2012, 19:05  [ТС]     Списки #8
Цитата Сообщение от HomeR_J_SimpsoN Посмотреть сообщение
Эээм..
Вопрос стоял немного не так...
Когда лучше юзать односвязные, а не двусвязные списки - вот исходник.
Так что немного не в тему)
Посему солидарен с автором)
Без обид
Верно подметили, меня просто интересует где в реальной жизни лучше использовать односвязный а где двух, понятно что односвязный требует меньше ресурсов, значит где то там где ограничения на память
Yandex
Объявления
23.02.2012, 19:05     Списки
Ответ Создать тему
Опции темы

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