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

линейный однонаправленный список (вопрос по сути) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.94
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
15.08.2010, 15:43     линейный однонаправленный список (вопрос по сути) #1
Не понимаю смысла линейного однонаправленного списка.
Допустим есть список:
C++
1
2
3
4
5
6
7
8
9
10
11
struct Node
{
    int d;                //хранимое значение
    Node *next;       //указатель на следующий элемент списка
} L
 
int main()
{
        Node L;              //это мы создали один элемент списка
        return 0;   
}
если я всё правильно понял, то вопрос-как создать остальные элементы списка?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Luchic
11 / 11 / 1
Регистрация: 02.05.2010
Сообщений: 117
15.08.2010, 15:48     линейный однонаправленный список (вопрос по сути) #2
Вот тебе Реализация - односвязный список
если я правильно поняла, тебе это нужно?
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 <iostream>
using namespace std;
 
 
struct Element
{
   // Данные
   char data;
   // Адрес следующего элемента списка
   Element * Next;
};
 
// Односвязный список
class List
{
   // Адрес головного элемента списка
   Element * Head;
   // Адрес головного элемента списка
   Element * Tail;
   // Количество элементов списка
   int Count;
 
public:
   // Конструктор
   List();
   // Деструктор
   ~List();
    
   // Добавление элемента в список
   // (Новый элемент становится последним)
   void Add(char data);
    
   // Удаление элемента списка
   // (Удаляется головной элемент)
   void Del();
   // Удаление всего списка
   void DelAll();
    
   // Распечатка содержимого списка
   // (Распечатка начинается с головного элемента)
   void Print();
    
   // Получение количества элементов, находящихся в списке
   int GetCount();
};
 
List::List()
{
   // Изначально список пуст
   Head = Tail = NULL;   
   Count = 0;
}
 
List::~List()
{
   // Вызов функции удаления
   DelAll();
}
 
int List::GetCount()
{
   // Возвращаем количество элементов
   return Count;
}
 
void List::Add(char data)
{
   // создание нового элемента
   Element * temp = new Element;
 
   // заполнение данными
   temp->data = data;
   // следующий элемент отсутствует
   temp->Next = NULL;
   // новый элемент становится последним элементом списка
   // если он не первый добавленный
   if(Head!=NULL){
        Tail->Next=temp;
        Tail = temp;
   }
   // новый элемент становится единственным
   // если он первый добавленный
   else{
       Head=Tail=temp;
   }
}
 
void List::Del()
{
   // запоминаем адрес головного элемента
   Element * temp = Head;
   // перебрасываем голову на следующий элемент
   Head = Head->Next;
   // удаляем бывший головной элемент
   delete temp;
}
 
void List::DelAll()
{
   // Пока еще есть элементы
   while(Head != 0)
      // Удаляем элементы по одному
      Del();
}
 
void List::Print()
{
   // запоминаем адрес головного элемента
   Element * temp = Head;
   // Пока еще есть элементы
   while(temp != 0)
   {
      // Выводим данные
      cout << temp->data << " ";
      // Переходим на следующий элемент
      temp = temp->Next;
   }
 
   cout << "\n\n";
}
 
// Тестовый пример
void main()
{
   // Создаем объект класса List
   List lst;
 
   // Тестовая строка
   char s[] = "Hello, World !!!\n";
   // Выводим строку
   cout << s << "\n\n";
   // Определяем длину строки
   int len = strlen(s);
   // Загоняем строку в список
   for(int i = 0; i < len; i++)
      lst.Add(s[i]);
   // Распечатываем содержимое списка
   lst.Print();
   // Удаляем три элемента списка
   lst.Del();
   lst.Del();
   lst.Del();
   //Распечатываем содержимое списка
   lst.Print();
}
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
15.08.2010, 16:12  [ТС]     линейный однонаправленный список (вопрос по сути) #3
в 20 строчке наверное адрес текущего элемента списка?
Luchic
11 / 11 / 1
Регистрация: 02.05.2010
Сообщений: 117
15.08.2010, 16:23     линейный однонаправленный список (вопрос по сути) #4
это последний элемент списка

тут по определению
Односвязный список - это совокупность объектов, называемых элементами списка, в которой каждый объект содержит информацию о местоположении следующего, связанного с ним объекта.
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
15.08.2010, 18:42  [ТС]     линейный однонаправленный список (вопрос по сути) #5
огромное спасибо! всё стало ясно!

Добавлено через 1 час 24 минуты
79 и 80 строку можно заменить на одну лишь 80. я не прав?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
15.08.2010, 18:44     линейный однонаправленный список (вопрос по сути) #6
velodro, Вроде как нет) Обе важны.
C++
1
2
                Tail->Next=temp;
                Tail = temp;
Следующий элемент за последним = temp. Сам хвост = temp.
Luchic
11 / 11 / 1
Регистрация: 02.05.2010
Сообщений: 117
15.08.2010, 18:49     линейный однонаправленный список (вопрос по сути) #7
не, нельзя
velodro
72 / 1 / 1
Регистрация: 28.11.2009
Сообщений: 78
15.08.2010, 18:58  [ТС]     линейный однонаправленный список (вопрос по сути) #8
Tail.next=temp
Tail=temp
одно и тоже?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
15.08.2010, 19:05     линейный однонаправленный список (вопрос по сути) #9
velodro, нет.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
15.08.2010, 19:13     линейный однонаправленный список (вопрос по сути) #10
Цитата Сообщение от velodro Посмотреть сообщение
одно и тоже?
сказали же, что нет. Происходит добавление элемента в хвост списка. Описываю подробно:
  1. Сначала у нас хвостом списка является элемент Tail
  2. Делаем следующим элементом для Tail новый элемент temp (Tail->next = temp)
  3. И после этого делаем концом списка новый элемент Tail = temp
А если сделать так, как предлагаешь ты, то мы просто делаем хвостом списка новый элемент, только вот он становится никак не связан с предыдущими элементами списка (эта связь создается выражением Tail->next = temp).

Тебе привели код с подробными комментариями. Постарайся разобраться сам, так ты лучше поймешь предмет этой темы. Отладь программу в пошаговом режиме, просмотри значение переменных в ключевых шагах, организуй печать промежуточных данных. Можешь даже испробовать свой вариант, посмотришь, что получится. Вот тогда и разберешься, что к чему.


Плохо, что функции деструктора в приведенном примере выполняет рядовой метод. А еще хуже, что этот метод не вызывается для удаления списка.
Lexa_Aleynik
0 / 0 / 0
Регистрация: 19.08.2010
Сообщений: 8
19.08.2010, 18:27     линейный однонаправленный список (вопрос по сути) #11
Действительно, деструктор тут не высвобождает динамическую память, он лишь уничтожает связи между записями, не уничтожая их. А вот как бы высвободить память правильно - другой интересный вопрос.
Iriska_humory
4 / 4 / 0
Регистрация: 03.12.2009
Сообщений: 8
31.03.2011, 13:06     линейный однонаправленный список (вопрос по сути) #12
А можно добавлять новые элементы не в конец, а в начало списка?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.03.2011, 16:45     линейный однонаправленный список (вопрос по сути)
Еще ссылки по теме:

Линейный однонаправленный список C++
C++ Линейный циклический однонаправленный список
Линейный однонаправленный список C++

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

Или воспользуйтесь поиском по форуму:
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
31.03.2011, 16:45     линейный однонаправленный список (вопрос по сути) #13
Iriska_humory, можно
Yandex
Объявления
31.03.2011, 16:45     линейный однонаправленный список (вопрос по сути)
Ответ Создать тему
Опции темы

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