VPF::Ошибка в приоритетном, двухсвязном списке

DjoNIK

Дата 19.8.2007, 18:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 28.9.2006
Где: Питер/Георгиевск

Репутация: 4
Всего: 5

При 2-ом add-e в дебагере MS VC++(2005) в list.cpp в строчке 27 curr == 0x00355d30 и end == 0x00355d30, и цикл работает так, как я и ожидал.
При 3-ем же add-e на втором шаге цикла в строчке 27 curr == 0x00355d30 и end == 0x00355d30, НО(!) цикл работает уже не так, как я ожидал.
Что-то мне не верится что у меня глючная студия smile

. Но в то же время я сам не могу разобраться в корне проблемы!
Гуру(и пока ещё не очень), помогите новичку!

list.h:

Код


#if !defined(_LIST_H_)
#define    _LIST_H_

struct link
{
    int    data;
    link    *next;
    link    *prev;
};

class List
{
private:
    link    *start;
    link    *curr;
    link    *end;
public:
    void add(int d);
    void display(void);
public:
    List(void);
    virtual ~List(void);
};

#endif    //_LIST_H_

list.cpp:

Код


#include <iostream>
using namespace std;

#include "list.h"

void List::add(int d)
{
    if(!curr || !start || !end)
    {
        curr = start = end = new link;
        curr->data    = d;
        start->data    = d;
        end->data    = d;

        curr->next = start->next = end->next = NULL;
        curr->prev = start->prev = end->prev = NULL;
    }
    else
    {
        link *newelement = new link;
        newelement->data = d;
        newelement->next = NULL;
        newelement->prev = NULL;

        curr = start;

        while(curr!=end ||            // Возникает ошибка при 3-ем add-e
            newelement->data > curr->data)
        {
            curr = curr->next;
        }
        if(curr==start)
        {
            newelement->next = start;
            newelement->prev = NULL;
            start->prev = newelement;
            start = newelement;
            return;
        }
        if(curr==end)
        {
            newelement->prev = end;
            newelement->next = NULL;
            end->next = newelement;
            end = newelement;
            return;
        }
        link *previes = curr->prev;
        previes->next = newelement;
        curr->prev = newelement;
        newelement->next = curr;
        newelement->prev = previes;
    }
}

void List::display(void)
{
    curr = start;
    while(curr!=NULL)
    {
        cout<<curr->data<<'\n';
        curr = curr->next;
    }
}

List::~List(void)
{
    curr = start;
    while(curr!=end)
    {
        curr = curr->next;
        delete curr->prev;
    }
    delete curr;
    curr = start = end = NULL;
}

List::List(void) : start(NULL), curr(NULL), end(NULL)
{}

main.cpp:

Код


#include "list.h"

int main()
{

    List *lst = new List;

    lst->add(5);
    lst->add(3);
    lst->add(6);
    lst->add(2);
    lst->add(0);
    lst->add(1);

    lst->display();

    delete lst;

return 0;
}

Это сообщение отредактировал(а) DjoNIK - 19.8.2007, 18:56

--------------------

- Плесни-ка мне холодного кипятку.
- Как кипяток может быть холодным?! Ты, верно, хочешь кипяченой воды?
- Какая ещё кипяченая вода? Не пудри мне мозги - налейхолодного кипятку.
(разговор петербуржца и москвича)

Fin

Дата 19.8.2007, 20:49 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Код


if(!curr || !start || !end)
    {
        curr = start = end = new link;
        curr->data    = d;
        start->data    = d;
        end->data    = d;

        curr->next = start->next = end->next = NULL;
        curr->prev = start->prev = end->prev = NULL;
    }

раскажи мне пожайлуста смысл тройного дублирования кода?
Ведь curr, start и end у тебя ссылки на один и тот же участок памяти, следовательно при изменении значений в curr->d, автоматически будут изменены значения также и в start->d и end->d.

Сделай так

Код


struct link
{
    int    data;
    link    *next;
    link    *prev;
    link(int d)
   {
         data = d;
         next = null;
        prev = null;
   }
};

Тогда твой код можно сократить до

Код


if(!curr || !start || !end)
    {
        curr = start = end = new link(d);
    }

--------------------

Пролетал мимо.

DjoNIK

Дата 19.8.2007, 21:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 28.9.2006
Где: Питер/Георгиевск

Репутация: 4
Всего: 5

Уместное замечание, но к сожалению корень проблемы не решает :(

Это сообщение отредактировал(а) DjoNIK - 19.8.2007, 21:16

--------------------

Fin

Дата 19.8.2007, 21:16 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Судя по твоей логике, curr не нужен в мемберах класса. Твой код можно переписать так

Код


void List::add(int d)
{
   if(start == null) start = end = new link(d);
   else
   {
      link *newelement = new link(d);
      link *curr = start;
      link *temp = start;

      while((curr != null) && (d > curr->data))
      {
         temp=curr;
         curr = curr->next;
      }
      if (curr == null)
      {
         temp->next=newelement;
         newelement->prev = temp;
         end = newelement;
      }
      else
      {
         if (curr->prev != null) 
         {
            newelement->prev=curr->prev;
            newelement->prev->next=newelement;
         }
         else start=newelement;
         curr->prev=newelement;
         newelement->next=curr;
      }
   }
}

--------------------

Пролетал мимо.

DjoNIK

Дата 19.8.2007, 21:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 28.9.2006
Где: Питер/Георгиевск

Репутация: 4
Всего: 5

Да, это тоже верно с точки зрения правильного стиля и эффективности(просто код переделывался из обычного односвязного списка без приоритетности). Но опять же программа не хочет работать.

--------------------

Fazil6

Дата 20.8.2007, 00:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1653
Регистрация: 3.5.2006
Где: Минск

Репутация: 35
Всего: 60

Код


#if !defined(_LIST_H_)
#define    _LIST_H_

#include <iostream>



template <typename T>
class PriorList
{
        struct lItem
        {
            T item;
            lItem *n;
            lItem *pr;

            lItem() : n(NULL) , pr(NULL)
            {}
        };

public:
        void add(const T &d)
        {
            lItem *curr = new lItem();
            curr->item = d;

            if(!headItem)  
            {
                headItem = curr;
                endItem  = curr;
            }
            else
            {
                if(curr->item <= headItem->item)
                {
                    headItem->pr    = curr;
                    curr->n            = headItem;
                    headItem        = curr;
                    return;
                }

                if(curr->item > endItem->item)
                {
                    endItem->n = curr;
                    curr->pr   = endItem;
                    endItem    = curr;
                    return;
                }

                lItem *iter = headItem ;

                while(iter)
                {
                    if(curr->item > iter->item)
                    {
                        iter = iter->n;
                    }
                    else
                    {
                        lItem *pr    = iter->pr;
                        
                        curr->n        = iter;
                        iter->pr    = curr;
                        curr->pr    = pr;
                        pr->n        = curr;
                        
                        break;
                    }
                }
            }

        }
        void display(void)
        {
            lItem *iter = headItem ;
            while(iter)
            {
                std::cout << iter->item << "\n";
                iter = iter->n;            
            }
        }

        PriorList() : headItem(NULL), endItem(NULL)
        {

        };

        ~PriorList()
        {
            while(headItem)
            {
                lItem *iter   = headItem->n ;
                delete headItem;
                headItem = iter ;            
            }
        }
private:
    lItem *headItem;
    lItem *endItem;


};

#endif    //_LIST_H_

Код


#include "list.h"

int main()
{

    PriorList<int> lst ;

    lst.add(5);
    lst.add(3);
    lst.add(4);
    lst.add(6);
    lst.add(2);
    lst.add(0);
    lst.add(1);
    lst.add(10);

    lst.display();


    return 0;
}

Это сообщение отредактировал(а) Fazil6 - 20.8.2007, 00:27

Fin

Дата 20.8.2007, 00:28 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 3
Всего: 10

Вот я прогнал твой код у себя на компе
list.h

Код


#ifndef _LIST_H_
#define    _LIST_H_

#define null 0

struct linkstr
{
   int    data;
   linkstr    *next;
   linkstr    *prev;
   linkstr (int d)
   {
      data = d;
      next = null;
      prev = null;
   }
};

class List
{
   private:
      linkstr *start;
      linkstr *end;
   public:
      void add(int d);
      void display(void);
      List(void);
      virtual ~List(void);
};

#endif    //_LIST_H_

list.cpp

Код


#include <iostream>
using namespace std;

#include "list.h"


void List::add(int d)
{
   if(start == null) start = end = new linkstr(d);
   else
   {
      linkstr *newelement = new linkstr(d);
      linkstr *curr = start;
      linkstr *temp = start;

      while((curr != null) && (d > curr->data))
      {
         temp=curr;
         curr = curr->next;
      }
      if (curr == null)
      {
         temp->next=newelement;
         newelement->prev = temp;
         end = newelement;
      }
      else
      {
         if (curr->prev != null) 
         {
            newelement->prev=curr->prev;
            newelement->prev->next=newelement;
         }
         else start=newelement;
         curr->prev=newelement;
         newelement->next=curr;
      }
   }
}

void List::display(void)
{
   linkstr *curr = start;
   while(curr!=NULL)
   {
      cout<<curr->data<<'\n';
      curr = curr->next;
   }
}

List::~List(void)
{
   linkstr *curr = start;
   linkstr *temp = null ;
   
   while(curr!=null)
   {
      temp = curr;
      curr = curr->next;
      delete temp;
   }
   start = end = null;
}

List::List(void): start(null), end(null)
{}

Чуть чуть подкорректировал другие функции. Изменил имя структуры с link на linkstr. У меня слово link компилятор посчитал зарезервированным словом.

--------------------

Пролетал мимо.

DjoNIK

Дата 20.8.2007, 08:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 320
Регистрация: 28.9.2006
Где: Питер/Георгиевск

Репутация: 4
Всего: 5

Ужас, из-за чего весь сыр-бор завел - в цикле надо было поставить логическое И, чтобы при не выполнении какого-либо условия он завершался. А я по запарке подумал, что раз надо выходить по одному из условий, то мне нужно логическое ИЛИ.
Вот ....
smile

Fin спасибо smile

Это сообщение отредактировал(а) DjoNIK - 20.8.2007, 08:46

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »