Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 06.06.2008, 20:24   #1
Rembo
Форумчанин
 
Аватар для Rembo
 
Регистрация: 29.10.2007
Сообщений: 628
По умолчанию Связанные списки в C++

Здравствуйте, в С++ есть такая тема как "связанные списки". Ни как не могу с ней разобраться Понял только то, что связанные списки связывают какое-то колличество объектов с помощью указателей. И мол не каждый класс может создавать связанные списки, а только такие:
Код:
class NameDataSet
{
 public:
        NameDataSet* pNext;
// другие члены класса.      
};
А больше, как например обращаться к ним, как заполнять, ну вообщем практическое применение в С++ так и не понял... Если кто может объяснить, помогите пожалуйста, объясните
Rembo вне форума Ответить с цитированием
Старый 06.06.2008, 21:19   #2
Greblin
Меркантильный кю
Участник клуба
 
Аватар для Greblin
 
Регистрация: 02.02.2008
Сообщений: 1,001
По умолчанию

Это такая стуктура данных, которая кроме каких-то пользовательских данных хранит ещё и ссылку на следующий и/или предыдущий элемент. Т.е. мы можем передвигаться только вперёд и/или назад.
С помощью списков, или на их основе, реализуются такие более сложные структуры, как, например дерево.
Достоинстовом списка является то, что он ограничен только памятью компа и размерностью указателя. Список используется, например, при рекурсии, (в этом случае это так называемый стэк). Мы заносим в него данные из вызывающей функции, а в вызванной достаём их оттуда.
Вот реализация стэка на C++ (возможно не самая лучшая, но вполне работающая)
Код:

struct stack
  {
  int a, b;
  stack *next;
  //указатель на следующий элемент списка
  };
//описание структуры

stack *head = NULL;
//указатель на голову стэка

void push(stack *data)
{
stack *p;
//обявляем указатель на структуру
p = new stack;
//создаём новую динамическую переменную
p->a = data->a;
p->b = data->b;
//заносим в неё данные
p->next = head;
//цепляем в начало стэка
head = p;
//обновляем голову стэка
}
//операция вставки в начало стэка элемента

stack *pop()
{
stack *p;
p = head;
//берём указатель на первый элемент
head = head->next;
//переносим голову стэка на элемент вперёд
return p;
}
//операция получения из стека элемента

bool nihil()
{
if (head == NULL)
  return true;
else
  return false;
}
//функция возвращает true если стэк пустой
Стэк - это структура типа Последний вошёл, первый вышел. Т.е. при получении элемента из стэка выбирается последний помещённый туда элемент. Ещё часто используется очередь - Первый вошёл, первый вышел. Как в нормальной очереди в магазине (в больнице не так, там структура сложнее :-))
Посмотри ещё в нете, про списки очень много инфы, ибо они используются буквально на каждом шагу
Росли вроде умными, выросли дурнями... (c)А.Васильев
Greblin вне форума Ответить с цитированием
Старый 06.06.2008, 21:37   #3
Rembo
Форумчанин
 
Аватар для Rembo
 
Регистрация: 29.10.2007
Сообщений: 628
По умолчанию

Ой, что-то в вашем примере нет даже классов... А я щас прохожу классы, объекты, а вот теперь связанные списки. Просто если взять в пример что-нибудь другое, отличное от классов, то мне вообще не разобраться А вообще спасибо за ваш ответ. Вот в книге есть такой пример:
Код:
//Приведенная ниже простая функция, добавляющая переданный 
//ей аргумент в начало списка, поможет вам разобраться 
//со связанными списками.
void addHead(LinkableClass* pLC)
{
pLC->pNext = pHead;
pHead = pLC;
}
Что происходит в этой функции? я только знаю, что в функцию, получается что, передается адрес какого-то объекта, чтобы этот адрес хранился в указатели LinkableClass* pLC... А например откуда берется pHead, а что это вообще, указатель? я не знаю... В книге написано, что это простая функция, а я вот до сих пор не могу разобраться...
Rembo вне форума Ответить с цитированием
Старый 06.06.2008, 21:40   #4
Olympian
Форумчанин
 
Аватар для Olympian
 
Регистрация: 06.06.2008
Сообщений: 105
По умолчанию

pHead - указатель на начало списка
pLC - мы добавляем

pLC->pNext = pHead; - здесь мы в наш новый элемент, пишем следующий за ним - то есть тот, что сейчас первый..
pHead = pLC; - подменяем первый элемент на текущий
Olympian вне форума Ответить с цитированием
Старый 06.06.2008, 21:45   #5
Greblin
Меркантильный кю
Участник клуба
 
Аватар для Greblin
 
Регистрация: 02.02.2008
Сообщений: 1,001
По умолчанию

у меня не класс а запись, можно обозвать её классом и запихнуть туды функции, получится то же самое
Росли вроде умными, выросли дурнями... (c)А.Васильев
Greblin вне форума Ответить с цитированием
Старый 06.06.2008, 21:52   #6
Rembo
Форумчанин
 
Аватар для Rembo
 
Регистрация: 29.10.2007
Сообщений: 628
По умолчанию

Olympian, Greblin, спасибо вам. Вот например я щас на ковылял программу, посмотрите пожалуйста, все ли там правильно, то ли я передаю в функцию?
Код:
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

class NameDataSet
{
 public:
        NameDataSet* pNext;      
};

void addHead (NameDataSet* pLC)
{
NameDataSet* pHead;
pLC->pNext = pHead;
pHead = pLC;
return;
}
 
int main(int argc, char* pArgs[])
{

NameDataSet ob;
addHead(&ob);
  

system("PAUSE");
return 0;
}
Ну вот добавили мы элемент в этот список, и что дальше делать? Как им пользоваться...
PS: это такая тема, достаточно сложная или я что-то "туплю"?
Rembo вне форума Ответить с цитированием
Старый 06.06.2008, 21:58   #7
Olympian
Форумчанин
 
Аватар для Olympian
 
Регистрация: 06.06.2008
Сообщений: 105
По умолчанию

Код:
   1. #include <stdio.h>  
   2. #include <iostream>  
   3. #include <string>  
   4. using namespace std;  
   5.   
   6. class NameDataSet  
   7. { 
   8.  public: 
   9.         NameDataSet* pNext;       
  10. };  
  11.   
  12. void addHead (NameDataSet* pLC)  
  13. { 
  14. NameDataSet* pHead; 
  15. pLC->pNext = pHead; 
  16. pHead = pLC; 
  17. return; 
  18. }  
  19.    
  20. int main(int argc, char* pArgs[])  
  21. { 
  22.  
  23. NameDataSet ob; 
  24. addHead(&ob); 
  25.    
  26.  
  27. system("PAUSE"); 
  28. return 0; 
  29. }
Нет, немного не верно - переменная
14. NameDataSet* pHead;
Должна быть не локальной в функции, а глобальной. От локальной толку мало - создаем, и тут же удаляем.

По своему опыту скажу - первый раз - это дейтсвительно не просто, мне было. Но если понять один раз саму идею, независимо от реализаций - т.е. абстракцию, как это выглядит примерно - то уже всё просто будет.
Olympian вне форума Ответить с цитированием
Старый 06.06.2008, 21:58   #8
Rembo
Форумчанин
 
Аватар для Rembo
 
Регистрация: 29.10.2007
Сообщений: 628
По умолчанию

Цитата:
Сообщение от Greblin Посмотреть сообщение
у меня не класс а запись, можно обозвать её классом и запихнуть туды функции, получится то же самое
Если не сложно, можете переписать тот пример, используя класс и запихнув туда функций? Пожалуйста, если не отвлекаю
Rembo вне форума Ответить с цитированием
Старый 06.06.2008, 22:06   #9
Rembo
Форумчанин
 
Аватар для Rembo
 
Регистрация: 29.10.2007
Сообщений: 628
По умолчанию

Olympian Если переношу строчку NameDataSet* pHead; в функцию main, то не работает, а сунул после класса, вроде заработало:
Код:
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

class NameDataSet
{
 public:
        NameDataSet* pNext;      
};
NameDataSet* pHead;
void addHead (NameDataSet* pLC)
{
pLC->pNext = pHead;
pHead = pLC;
return;
}
 
int main(int argc, char* pArgs[])
{

NameDataSet ob;
addHead(&ob);
  

system("PAUSE");
return 0;
}
Так? ну ладно, ну вот с помощью функцией addHead мы добавили элемент. Получается что мы к блоку добавили еще один блок что-ли?
А как теперь это использовать? можно ли, допустим, обратиться ко второму блоку, и заполнить какие-либо члены класса class NameDataSet данными?
Цитата:
По своему опыту скажу - первый раз - это дейтсвительно не просто, мне было. Но если понять один раз саму идею, независимо от реализаций - т.е. абстракцию, как это выглядит примерно - то уже всё просто будет.
Странно, искал много информации и в электронных самоучителях и просто в интернете и не нашел, чтобы там, как Вам сказать, очень простым языком описана была тема "связанные списки", но так ничего и не понял... Но чувствую, если эту тему не понять, в дальнейшем худо будет. Вот решил обратиться на форум, спросить

Последний раз редактировалось Rembo; 06.06.2008 в 22:14.
Rembo вне форума Ответить с цитированием
Старый 06.06.2008, 23:44   #10
MaTBeu
Eclipse Foundation
Старожил
 
Аватар для MaTBeu
 
Регистрация: 19.09.2007
Сообщений: 2,619
По умолчанию

Устройство связных списков довольно простое. Суть вот в чем. Представьте себе гирлянду. Каждый фонарь - элемент, а провод между ними - указатель на следующий элемент. Тоесть первый фонарь имеет односторонний доступ (если список односвязный) только к следующему фонарю. А следующий - к следующему. И так далее.
А теперь к спискам. Данное поле в классе
Код:
NameDataSet* pNext;
хранит указатель на следующий элемент. Тоесть вся работа со списками организовывается на разыменовывании указателей. Тоесть, если у вас указатель на первый элемент pHead (допустим так), то у него в информации хранится указатель на следующий элемент. По логике обращение к следующему элементу заключается в простом разыменовывании указателя (обращение к полю класса, которое является указателем на объект этого же класса). Само обращение имеет вид
Код:
pHead=pHead->pNext;
, тоесть мы "переместили" указатель с первого элемента на второй.
Вот и все.
MaTBeu вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Связанные таблицы в Аксессе mirawoo Microsoft Office Access 8 12.03.2008 00:13
Не отображаются данные связанные с гл. таблицей? zimmion БД в Delphi 11 27.02.2008 18:50
Связанные таблицы - проблема при обращении к полю БД nataly_ukr БД в Delphi 7 13.11.2007 10:47
Добавление записей в связанные таблицы с помощью Навигатора ~MaGic~ БД в Delphi 2 09.07.2007 08:01