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

Создание двухсвязного списка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
andrew1ee
0 / 0 / 0
Регистрация: 05.06.2013
Сообщений: 25
05.06.2013, 11:19     Создание двухсвязного списка #1
Есть задание:
Реализовать двухсвязный список. Каждый элемент списка может содержать один объект. Объект может быть трех типов: "целое число", "вещественное число", "строка". В разных узлах одного списка может быть любой объект одного из допустимых типов. Каждый объект должен иметь возможность вывести свое содержимое на консоль. У списка должен быть метод, выводящий все элементы.
Класс списка реализовать с "нуля" (не используя темплейты, std::list или аналоги) При реализации класса "строка" можно использовать std::string.

Есть код:

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
#include <stdlib.h>
#include <iostream.h>
 
struct Node       //Структура являющаяся звеном списка
 {
     int x;     //Значение x будет передаваться в список
     Node *Next,*Prev; //Указатели на адреса следующего и предыдущего элементов списка
 };
 
 class List   //Создаем тип данных Список
 {
     Node *Head,*Tail; //Указатели на адреса начала списка и его конца
 public:
     List():Head(NULL),Tail(NULL){}; //Инициализируем адреса как пустые
     ~List(); //Деструктор
     void Show(); //Функция отображения списка на экране
     void Add(int x); //Функция добавления элементов в список
 };
 
List::~List() //Деструктор
 {   
     while (Head) //Пока по адресу на начало списка что-то есть
     {
         Tail=Head->Next; //Резервная копия адреса следующего звена списка
         delete Head; //Очистка памяти от первого звена
         Head=Tail; //Смена адреса начала на адрес следующего элемента
     }
 }
 
 void List::Add(int x)
 {
   Node *temp=new Node; //Выделение памяти под новый элемент структуры
   temp->Next=NULL;  //Указываем, что изначально по следующему адресу пусто
   temp->x=x;//Записываем значение в структуру
 
   if (Head!=NULL) //Если список не пуст
   {
       temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
       Tail->Next=temp; //Указываем адрес следующего за хвостом элемента
       Tail=temp; //Меняем адрес хвоста
   }
   else //Если список пустой
   {
       temp->Prev=NULL; //Предыдущий элемент указывает в пустоту
       Head=Tail=temp; //Голова=Хвост=тот элемент, что сейчас добавили
   }
 }
 
 void List::Show()
 {
 
     Node *temp=Head; //Временно указываем на адрес первого элемента
      while (temp!=NULL) //Пока не встретим пустое значение
     {
     cout<<temp->x<<" "; //Выводим каждое считанное значение на экран
     temp=temp->Next; //Смена адреса на адрес следующего элемента
     }
     cout<<"\n";
 }
 
int main ()
{
 system("CLS");
 List lst; //Объявляем переменную, тип которой есть список
 lst.Add(100); //Добавляем в список элементы
 lst.Add(200);
 lst.Add(900);
 lst.Add(888);
 
 lst.Show(); //Отображаем список на экране
  system("PAUSE");
}
Как в эту программу добавить тип данных double и string, не используя стандартные библиотеки вроде tuple или что-то подобное?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2013, 11:19     Создание двухсвязного списка
Посмотрите здесь:

C++ создание списка
Создание списка C++
C++ Создание однонаправленного списка
C++ Создание списка
Создание линейного списка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.06.2013, 11:53     Создание двухсвязного списка #2
andrew1ee, сделайте в Node не int, а void* и при добавлении выделяйте память под нужный тип, ещё нужно будет поле типа добавить, чтобы знать что под void* кроется. Или можно union использовать, только вместо string придется char[] использовать.
andrew1ee
0 / 0 / 0
Регистрация: 05.06.2013
Сообщений: 25
05.06.2013, 17:00  [ТС]     Создание двухсвязного списка #3
А можно пример реализации ?
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
05.06.2013, 17:59     Создание двухсвязного списка #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
enum DataKind { symbol, value, string };
struct Node 
{
   void* data;
   DataKind kind;
   Node *Next,*Prev; 
};
 
void List::Add(void* data, DataKind kind)
{
   Node *temp=new Node; 
   temp->Next=NULL;  
   temp->kind = kind;
   temp->data = data;
...
}
Перед вызовом Add() нужно выделить память под сами данные. Например для целого:
C++
1
2
int* data = new int( 42 ); 
lst->Add( data, value );
Это всё так, в общих чертах.
andrew1ee
0 / 0 / 0
Регистрация: 05.06.2013
Сообщений: 25
06.06.2013, 15:49  [ТС]     Создание двухсвязного списка #5
Куда конкретно вставить строки?:

C++
1
2
int* data = new int( 42 ); 
lst->Add( data, value );
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.06.2013, 15:55     Создание двухсвязного списка #6
Цитата Сообщение от andrew1ee Посмотреть сообщение
Куда конкретно вставить строки?:
Там, где надо добавлять в список. У Вас в коде с 65 строки начинается.
andrew1ee
0 / 0 / 0
Регистрация: 05.06.2013
Сообщений: 25
06.06.2013, 16:31  [ТС]     Создание двухсвязного списка #7
А как теперь в Show() правильно записать cout c новыми переменными?
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.06.2013, 16:50     Создание двухсвязного списка #8
Цитата Сообщение от andrew1ee Посмотреть сообщение
А как теперь в Show() правильно записать cout c новыми переменными?
C++
1
2
3
4
5
switch( kind )
{
   case value: cout<< *static_cast<int*>(temp->data) <<" "; break;
   // Для других типов аналогично
}
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
06.06.2013, 17:04     Создание двухсвязного списка #9
2Tulosba Нет, потому что это список для типа указатель, а не для типов "целое число", "вещественное число", "строка".

Тем более, вот такой вод код приведет к сегфолту при использовании Вашей идеи.
C++
1
2
3
4
    {
    int value = 42;
    list->addd(&value);
    }
обратите внимание на область видимости.

Добавлено через 7 минут
Вопрос должен ли список знать о хранимым им типам? Я думаю нет. Если да, то правильной реализацией может быть такая конструкция
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef void (*_cpy_func)(void *to, void *from);
typedef void (*_del_func)(void* item);
typedef void (*_show_func)(void* item);
 
struct Node
{
    void *data;
    size_t size_of_data;
 
    _show_func show_func;
    _cpy_func cpy_func;
    _del_func del_func;;
};
 
 
--------
 
class List
{
--------
     void add(void* item, size_t size_of_item, _show_func show_func, _cpy_func cpy_func, _del_func del_func);
--------
};
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.06.2013, 17:04     Создание двухсвязного списка #10
Цитата Сообщение от stima Посмотреть сообщение
Нет, потому что это список для типа указатель, а не для типов "целое число", "вещественное число", "строка".
Не понял, к чему относится это "Нет".
Цитата Сообщение от stima Посмотреть сообщение
Тем более, вот такой вод код приведет к сегфолту
Это из разряда вызова delete для адреса стековой переменной. Никто не обещал, что это будет работать.
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
06.06.2013, 17:07     Создание двухсвязного списка #11
Цитата Сообщение от Tulosba Посмотреть сообщение
Не понял, к чему относится это "Нет".
К Вашей идеи.

Цитата Сообщение от Tulosba Посмотреть сообщение
Это из разряда вызова delete для адреса стековой переменной. Никто не обещал, что это будет работать.
Нужно написать что-то рабочее, или нет?) Тем более в задании не сказано, как алоцируется эта переменная, и должен ли работать список с указателем на пеерменную или с копией переменной
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.06.2013, 17:07     Создание двухсвязного списка #12
Цитата Сообщение от stima Посмотреть сообщение
Вопрос должен ли список знать о хранимым им типам? Я думаю нет.
В таком случае вообще правильнее завести общий базовый класс. Если не упираться на то, что исходные типы должны являться фундаментальными (char,int ... )

Цитата Сообщение от stima Посмотреть сообщение
void add(void* item, size_t size_of_item, _show_func show_func, _cpy_func cpy_func, _del_func del_func);
Имхо, слишком многословно для простого добавления в контейнер.
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
06.06.2013, 17:11     Создание двухсвязного списка #13
Цитата Сообщение от Tulosba Посмотреть сообщение
Если не упираться на то, что исходные типы должны являться фундаментальными (char,int ... )
В задании четко сказано, что за типы.

Цитата Сообщение от Tulosba Посмотреть сообщение
Имхо, слишком многословно для простого добавления в контейнер.
Такая задача, и в общем приблизительно так реализуется и дженерик Си лист, только там лис однотипен и данные функции инициализируются в "конструкторе".
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
06.06.2013, 17:19     Создание двухсвязного списка #14
Цитата Сообщение от stima Посмотреть сообщение
В задании четко сказано, что за типы.
Цитата Сообщение от andrew1ee Посмотреть сообщение
Объект может быть трех типов: "целое число", "вещественное число", "строка"
Чётко, говорите? С такой формулировкой, если честно, самое правильно свою иерархию классов построить. А не переносить решение проблемы C++ кода в плоскость языка C.

Добавлено через 1 минуту
Цитата Сообщение от andrew1ee Посмотреть сообщение
Каждый объект должен иметь возможность вывести свое содержимое на консоль.
А эта фраза, собственно, еще более подтверждает идею о базовом классе и виртуальных функциях.
stima
429 / 284 / 16
Регистрация: 22.03.2011
Сообщений: 923
Завершенные тесты: 1
06.06.2013, 17:23     Создание двухсвязного списка #15

Не по теме:


Поверьте в продакшин коде Вы и не такое увидите. И реки (поставленные задачи) звучат иногда оочень странно.



Добавлено через 3 минуты
Цитата Сообщение от Tulosba Посмотреть сообщение
А эта фраза, собственно, еще более подтверждает идею о базовом классе и виртуальных функциях.
Не спорю, если типами выступает класс а не встроенные типы данных.
andrew1ee
0 / 0 / 0
Регистрация: 05.06.2013
Сообщений: 25
06.06.2013, 19:08  [ТС]     Создание двухсвязного списка #16
Если честно я запутался. Немного пугают слова. "Никто не обещал, что это будет работать". Какой вариант использовать для решения задачи?
В
C++
1
2
3
4
5
switch( kind )
{
   case value: cout<< *static_cast<int*>(temp->data) <<" "; break;
   // Для других типов аналогично
}
компилятор на cout ругается.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2013, 10:24     Создание двухсвязного списка
Еще ссылки по теме:

Переписать с С# в С++. Реализация двухсвязного списка C++
C++ Создание односвязного списка
C++ Добавление элементов в любое место двухсвязного списка

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
07.06.2013, 10:24     Создание двухсвязного списка #17
Цитата Сообщение от andrew1ee Посмотреть сообщение
"Никто не обещал, что это будет работать"
Суть этой фразы в том, что при предложенном подходе, добавляемые в список данные, должны быть расположены в динамической памяти (т.е. создаваться через new).
Но так как хранимыми типами у Вас выступают некие "целое число", "вещественное число", "строка" (а не конкретные типы: int, double, char*), то правильнее всего будет реализовать иерархию классов с общим базовым типом. Вместо использования void* или union.
Yandex
Объявления
07.06.2013, 10:24     Создание двухсвязного списка
Ответ Создать тему
Опции темы

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