Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/18: Рейтинг темы: голосов - 18, средняя оценка - 4.83
Ieroglif
19 / 19 / 2
Регистрация: 23.06.2011
Сообщений: 238
1

Теория/списки

12.03.2012, 17:02. Просмотров 3348. Ответов 5
Метки нет (Все метки)

День добрый, форумчане.
У меня вопрос по спискам, точнее - по такой составляющей их как 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;
}
... то голова будет (спасибо последней строчке кода) указывать на первый и единственный элемент. Если же добавить элементы перед этим, то голова своего значения "не изменит". Это следствие такой фиксации?

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

Списки, как склеить списки между собой?
Ребят, привет всем, есть код, в классе которого описаны несколько методов:...

Теория по С++
Помогите с вопросами по экзамену по файлам 10) Беззнаковые типы данных. ...

теория
народ мож кто знает где можно найти теорию или что-нибудь на подобии...

теория
дана тема организация доступа, что мне в ней расписывать не знаю, подскажите...

теория
Добрый день!!! срочно нужины 2 примера : 1)чтобы нельзя было заменить цыкл for...

5
fasked
Эксперт С++
4982 / 2561 / 241
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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;
};
1
Ieroglif
19 / 19 / 2
Регистрация: 23.06.2011
Сообщений: 238
12.03.2012, 17:24  [ТС] 3
Непривычно выглядит.

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

Первая структура просто содержит ссылки для навигации, в то время как во второй находится голова?
Почему у элемента второй структуры тип первой?
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
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;
};
1
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
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, и это логично. Пользователю не нужно ничего знать о типе узла стека, об этом заботятся определения этих функций
1
Ieroglif
19 / 19 / 2
Регистрация: 23.06.2011
Сообщений: 238
13.03.2012, 08:47  [ТС] 6
Спасибо большое! Буду осваивать
0
13.03.2012, 08:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2012, 08:47

Теория по С++
Здравствуйте. Необходимо ответить на вопрос, что такое идентификаторы,...

Теория по С++
Помогите ответить на вопросы, очень нужно к экзамену. На что-то ответила, но...

теория
какя разница между кодами ? if(a&gt;b) a++; b++; и if(a&gt;b) a++;


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru