VPF::Инициализация указателя (класс графа)

Firex

Дата 23.4.2012, 11:45 (ссылка)

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

Загрузка ...

Шустрый

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

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

Достопочтенные форумчане, подскажите по коду. Есть класс графа:

Код


typedef struct sNode *Node; //Тип: указатель на заголовочный узел.
typedef struct sArcNode *ArcNode; //Тип: указатель на дуговой узел.
//Описание типа заголовочного узла.
typedef struct sNode 
{
  int Key;    //Имя заголовочного узла.
  int Count;  //Количество предшественников.
  ArcNode arcList; //Указатель на список смежности.
  Node Next;  //Указатель на следующий узел в 
              //списке заголовочных узлов.
} HNode;

//Описание типа дугового узла.
typedef struct sArcNode 
{
  Node Id; 
  ArcNode Next; 
} TNode;

class Spisok {
  private:
    Node Head; //Указатель на список заголовочных узлов.
    Node Tail; //Указатель на фиктивный элемент
               //в конце списка заголовочных узлов.
    Node SearchGraph(int);
    Node Search(int);
  public:
    Spisok () {//Инициализация списка заголовочных узлов.
           Head = Tail = new (HNode); }
    ~Spisok(); //Деструктор.
    void MakeGraph();
    void AddGraph(int, int);
    void DeleteGraph(int, int);
    void PrintGraph();
    void DeleteY(int);
    void Free1Graph(Node *, Node *);
    void Free2Graph(ArcNode *);
};

и методы:

Код


void Spisok::MakeGraph ()
//Функция возвращает указатель Head на структуру 
//Вирта, соответствующую ориентированному графу.
{
  int x,y;
  Node p,q;    //Рабочие указатели.
  ArcNode t,r;    // Рабочие указатели.
  Boolean Res; //Флаг наличия дуги.

  cout<<"Вводите начальную вершину дуги: ";
  cin>>x;
  while (x!=0)
  {
    cout<<"Вводите конечную вершину дуги: "; cin>>y;
    //Определим, существует ли в графе дуга (x,y)?
    p=SearchGraph (x); q=SearchGraph (y);
    r = (*p).arcList; Res = FALSE;
    while ((r!=NULL)&&(!Res)) 
      if ((*r).Id==q) Res = TRUE; 
      else r = (*r).Next; 
    if (!Res) //Если дуга отсутствует, то поместим её в граф.
    { t = new (TNode); (*t).Id = q;
      (*t).Next = (*p).arcList; (*p).arcList = t; (*q).Count++; }
    cout<<"Вводите начальную вершину дуги: "; cin>>x;
  }
}

Код


Node Spisok::SearchGraph (int w)
//Функция возвращает указатель на заголовочный узел 
//с ключом w. Если заголовочный узел отсутствует, то он 
//добавляется в список. Head - указатель на структуру Вирта.
{
  Node h;

  h = Head; Tail->Key = w;
  while (h->Key!=w) h = h->Next;
  if (h==Tail)
  //В списке заголовочных узлов нет узла с ключом w.
  //Поместим его в конец списка Head.
  { Tail = new (HNode); (*h).Count = 0; 
    (*h).arcList = NULL; (*h).Next = Tail; }
  return h;
}

Вопроса: куда "указывают" указатели Head и Tail при инициализации конструктором? Или так, куда "указывает" указатель переменной h в методе SearchGraph при первом обращении к нему?

baldina

Дата 23.4.2012, 11:57 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 15
Всего: 101

Цитата(Firex @ 23.4.2012, 11:45

)

Head = Tail = new (HNode);

т.е. на выделенную область памяти. поскольку конструктора HNode нет, то в этой памяти мусор.
поэтому вот это

Цитата(Firex @ 23.4.2012, 11:45

)

while (h->Key!=w) h = h->Next;

при первом обращении будет работать неправильно

Firex

Дата 23.4.2012, 12:04 (ссылка)

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

Загрузка ...

Шустрый

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

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

У меня такие же сомнения, но код взят отсюда: http://khpi-iip.mipk.kharkiv.edu/library/d...u/din_0085.html, компилируется и работает правильно...

baldina

Дата 23.4.2012, 13:02 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 15
Всего: 101

оно работает правильно потому что

Код


(*Tail).Key = w;

а Tail == Head после инициализации. в первый раз я невнимательно посмотрел.
но код ужасный, какая то смесь C и C++.

Добавлено через 3 минуты и 49 секунд
поглядел Вирта. действительно, у него tail всегда указывает на новый (выделенный) узел, который еще не используется

Firex

Дата 23.4.2012, 13:17 (ссылка)

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

Загрузка ...

Шустрый

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

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

Спасибо, вроде бы дошло. Хотя всё равно, после инициализации Head==Tail и указатели содерджат мусор, а (*Tail).Key=w происходит уже после h=Head. Т.е. в h мусор?

Это сообщение отредактировал(а) Firex - 23.4.2012, 13:46

baldina

Дата 23.4.2012, 15:26 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 15
Всего: 101

h=Head=Tail => h->key == Head->key == Tail->key == w

Это сообщение отредактировал(а) baldina - 23.4.2012, 15:38

Firex

Дата 23.4.2012, 16:13 (ссылка)

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

Загрузка ...

Шустрый

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

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

Вот теперь ясно, спасибо!

baldina

Дата 23.4.2012, 16:20 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 15
Всего: 101

Firex, возможно, Вам интересно будет сравнить разные варианты:
однонаправленный список реализуется очень просто, псевдоэлементов не требуется
http://codepad.org/hoYgZQLg
двунаправленный список без последнего ограничивающего элемента
http://codepad.org/d8bPn5JN
двунаправленный список с ограничивающим элементом
http://codepad.org/f6rN0fol
сравните последние две версии: при наличии ограничивающего элемента добавление становится проще. проход по списку теперь ограничивается этим элементом, а не 0

для краткости освобождение памяти я опустил

если вставки очень частые, разница будет в пользу второго варианта
если списки часто создаются, но часто пустые - в пользу первого
хотя во всех случаях разница очень невелика

с точки зрения понимания и применения - вопрос вкуса

Firex

Дата 23.4.2012, 16:52 (ссылка)

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

Загрузка ...

Шустрый

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

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

baldina, благодарю, полезно.

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