Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Инициализация указателя (класс графа)

Автор: Firex 23.4.2012, 11:45

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

Код


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

Цитата(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

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

Автор: baldina 23.4.2012, 13:02

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

Код


(*Tail).Key = w;

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

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

Автор: Firex 23.4.2012, 13:17

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

Автор: baldina 23.4.2012, 15:26

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

Автор: Firex 23.4.2012, 16:13

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

Автор: baldina 23.4.2012, 16:20

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

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

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

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

Автор: Firex 23.4.2012, 16:52

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