C++ Печать двусвязного списка

У меня есть некоторые трудности с классом двусвязных списков, который является частью моего университетского проекта. Код класса такой:

class container
{
public:
    class node
    {
        public:
        node * prev;
        node * next;
        int value;
    };

container(int v);

node *start; // first element of the list
node *finish; // last element of the list
void insert_start(node *start, int val);
void print_container(); 
}

Функция insert_start должна добавить элемент в начало списка. Код выглядит следующим образом:

void container :: insert_start(node *start, int val)
{
    if(start!=NULL)
    {
        cout << "in insert_start" << endl;
        cout << "number added:" << val << endl;

        node *element = new node;

        element->value=val;
        element->next=start;
        start=element;
        start->prev=NULL;
    }
    else
    {
        cout << "List is empty" << endl;
    }
}

И функция print_container должна распечатать мой связанный список. Код выглядит так:

void container::print_container()
{
    node *tmp;
    tmp = start;
    while(tmp!=nullptr)
    {
        cout << tmp->value << endl;
        tmp=tmp->next;
    }
}

К сожалению, в моей программе есть две проблемы. Во-первых, кажется, что добавляется одно и то же случайное значение в добавленные элементы структуры данных. Во-вторых, ошибка сегментации при выполнении функции print_container. Я предполагаю, что это может быть ошибка (или ошибки) в функции insert_start, но я не совсем уверен в этом.

Вот тестовая программа:

int main(void)
{
    int how_many_pieces;

    container L(6);

    L.insert_finish(L.finish,3);
    cout << "added element: " << L.finish->value << endl;

    L.insert_start(L.start,8);
    cout << "added element: " << L.start->value << endl;

    L.insert_start(L.start,12);
    cout << "added element: " << L.start->value << endl;


   //show elements of the L list
   L.print_container();
   cout << "\n";

return 0;
}

Спасибо за любую помощь.


c++ doubly-linked-list
person V8Interceptor    schedule 05.01.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Во-первых, не передавайте узел в качестве параметра - вам это не нужно. Класс-контейнер уже может видеть начальный и конечный узлы, и их передача только запутывает ситуацию.

Во-вторых, вы должны сделать их приватными, чтобы любой, кто использует класс, должен был использовать ваши функции insert_start или insert_finish.

Новый класс будет выглядеть так:

class container
{
    private:
        class node
        {
            public:
            node * prev;
            node * next;
            int value;
        };

        node *start; // first element of the list
        node *finish; // last element of the list

    public:
        container(int v);

        void insert_start(int val);
        void print_container();
};

В-третьих, убедитесь, что вы установили ссылки для каждого направления. Например, в вашей функции insert_start:

node *element = new node;

element->value = val;
element->next = start;
element->prev = NULL;
start->prev = element; //This part was missing
start = element;

Не возвращая исходный узел к новому, вы рассматриваете его как обычный односвязный список. Если вам нужна гибкость обхода, которую предлагает двусвязный список, вам необходимо правильно настроить ссылки.

person Maglos    schedule 05.01.2016

arrow_upward
1
arrow_downward

В этом коде:

void container :: insert_start(node *start, int val)
{
    if(start!=NULL)

к какому start должна относиться последняя строка? Это проверка значения параметра или значения общедоступного класса?

Кроме того, если список пуст, вы, вероятно, захотите сделать что-то другое, кроме вывода сообщения. Список должен начинаться каким-то образом.

(дополнение)

Есть как минимум два способа предотвратить эту проблему. Покажу сразу три:

void container :: insert_start(node *node_to_insert, int val)
{
    if (this->start != NULL)  // is list not empty?

Выглядит почти так же, верно?

  • Формальное имя параметра теперь указывает на его значение. Название предполагает, что узел, на который указывает указатель, должен быть добавлен в список.
  • Доступ к значениям экземпляра объекта осуществляется с помощью ключевого слова this. Это синтаксически устраняет неоднозначность области действия переменных с одинаковыми именами и действительно помогает программисту легко определить, что к чему.
  • Комментарий разъясняет высокоуровневое намерение оператора, что позволяет любому, кто проверяет код, выявить возможное несоответствие.
  • Имена параметров больше не соответствуют именам членов объекта. Хотя часто бывает полезно, чтобы имена были параллельны друг другу (p_x, p_y, p_z для значений трех параметров для инициализации переменных-членов x, y, z), на самом деле их следует различать для простоты и ясности.
person wallyk    schedule 05.01.2016
comment
Значение открытого класса. Я хотел, чтобы узел *start был виден для всех функций в контейнере класса без осложнений с доступом к этому узлу. Вероятно, есть лучшие, более безопасные и приятные способы сделать это, но я еще не очень хорошо разбираюсь в С++, и я хочу сначала написать рабочий класс контейнера. В любом случае, спасибо за вашу помощь. - person V8Interceptor; 05.01.2016