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

Теория/списки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.95
Ieroglif
 Аватар для Ieroglif
18 / 18 / 1
Регистрация: 23.06.2011
Сообщений: 237
12.03.2012, 17:02     Теория/списки #1
День добрый, форумчане.
У меня вопрос по спискам, точнее - по такой составляющей их как head (голова).

Она(голова), как мне известно, должна указывать на начало списка. В связи с этим и возникает ряд вопросов.

1. Где мы объявляем голову? Нужно/можно ли объявлять её в структуре списка?
C++
1
2
3
4
5
6
7
struct list//описание структуры списка.
{ 
int inf;
list *next;
list *pred;
list *head;
};
Или же можно ставить как глобальную переменную?
C++
1
2
3
4
5
6
7
8
9
10
struct list//описание структуры списка.
{ 
    int inf;
    list *next;
    list *pred;
};
 
list *head;
 
//Далее описание функций работы со списком и прочее
2. Как программа определяет, что данная конструкция должна указывать именно на начало списка (у меня вот она вовсе отказывается это делать).

То есть, если реализовать такой код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct list//описание структуры списка.
{ 
    int inf;
    list *next;
    list *pred;
};
 
list *cur;
list *head;
 
void func_cr()//создание списка-1го элемента списка
{
list *pAdd=new list;
cout<<"Создание списка. Введите первый элемент списка (число): ";
cin>>pAdd->inf;
cur=pAdd;
cur->next=NULL;
cur->pred=NULL;
cout<<"\n\nСозданный элемент: "; 
cout<<cur->inf<<"\n\n";
head=cur;
}
... то голова будет (спасибо последней строчке кода) указывать на первый и единственный элемент. Если же добавить элементы перед этим, то голова своего значения "не изменит". Это следствие такой фиксации?

Иными словами, как обозначать голову и сделать так, чтобы она всегда указывала на первый элемент списка?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2012, 17:02     Теория/списки
Посмотрите здесь:

теория C++
теория C++
C++ Теория
Теория C++
теория C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
12.03.2012, 17:19     Теория/списки #2
Цитата Сообщение от Ieroglif Посмотреть сообщение
Иными словами, как обозначать голову и сделать так, чтобы она всегда указывала на первый элемент списка?
C
1
2
3
4
5
6
7
8
9
10
struct node
{
    struct node *prev;
    struct node *next;
};
 
struct list
{
    struct node *head;
};
Ieroglif
 Аватар для Ieroglif
18 / 18 / 1
Регистрация: 23.06.2011
Сообщений: 237
12.03.2012, 17:24  [ТС]     Теория/списки #3
Непривычно выглядит.

Можете объяснить? Подробно, если это возможно.

Первая структура просто содержит ссылки для навигации, в то время как во второй находится голова?
Почему у элемента второй структуры тип первой?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
12.03.2012, 17:30     Теория/списки #4
Ieroglif, вторая структура представляет список. Список содержит указатель на свой первый узел — голову. Первая структура представляет собой узел. Узел хранит указатели на предыдущий и следующий элемент списка, а также обычно и какие-нибудь данные (fasked это поле не указал, но в принципе, для рассмотрения примера оно не обязательно):
C
1
2
3
4
5
6
struct node
{
    data_type data; /* какой-нибудь встроенный тип или typedef на тип структуры, перечисления, объединения... */
    struct node *prev;
    struct node *next;
};
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
12.03.2012, 17:59     Теория/списки #5
Вот пример простого связного списка — стека (LIFO):
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
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
struct node
{
    struct node* next; /* следующий элемент */
    int data; /* значение, которое хранится в узле */
};
 
struct stack
{
    struct node* top; /* вершина стека */
};
 
/* добавление элемента в стек */
void push(struct stack* stack, int value)
{
    struct node* new_node = malloc(sizeof(struct node));
    
    new_node->data = value;
    new_node->next = stack->top;
    
    stack->top = new_node;
}
 
/* получение элемента с вершины стека */
int top(const struct stack* stack)
{
    assert(stack->top != NULL);
 
    return stack->top->data;
}
 
/* удаление элемента с вершины стека */
void pop(struct stack* stack)
{
    struct node* del_node = stack->top;
    assert(stack->top != NULL);
    stack->top = stack->top->next;
    free(del_node);
    del_node = NULL;
}
 
/* проверка стека на пустоту */
int empty(const struct stack* stack)
{
    return stack->top == NULL;
}
 
/* инициализация стека */
void init(struct stack* stack)
{
    stack->top = NULL;
}
 
/* очистка стека */
void clear(struct stack* stack)
{
    while(!empty(stack))
    pop(stack);
}
 
int main(void)
{
    struct stack stack;
    int i;
    
    init(&stack);
 
    for(i = 0; i < 5; ++i)
    {
    printf("Push %d\n", i);
    push(&stack, i);
    }
 
    while(!empty(&stack))
    {
    printf("Pop %d\n", top(&stack));
    pop(&stack);
    }
    
    clear(&stack);
    exit(0);
}
Функции, с которыми работает пользователь (init, push, pop и т.д.) работают только с типом struct stack, и это логично. Пользователю не нужно ничего знать о типе узла стека, об этом заботятся определения этих функций
Ieroglif
 Аватар для Ieroglif
18 / 18 / 1
Регистрация: 23.06.2011
Сообщений: 237
13.03.2012, 08:47  [ТС]     Теория/списки #6
Спасибо большое! Буду осваивать
Yandex
Объявления
13.03.2012, 08:47     Теория/списки
Ответ Создать тему
Опции темы

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