Проверка, является ли односвязный список пустым c ++ - PullRequest
Новая
       22

Проверка, является ли односвязный список пустым c ++

1 голос
/ 27 апреля 2011

Я пытаюсь выяснить, какой самый лучший и простой способ определить, является ли односвязный список пустым или нет.

Нужно ли мне создавать логический метод?

Спасибо

Метод чтения

void List :: Read (istream & r) {

char c[13];
r >> c;
r >> numberOfInts;

Node *node = new Node();

for(int i = 0; i < numberOfInts; i++)
{
    r >> node->data;
    cout << node->data << endl;
    node->next = new Node;
    //node = node->next;

    head = node;
}
}
else
{
    if(node->data > head->data)
    {
        head->next;
    }
    else if(node->data < head->data)
    {
        Node* tempNode;
        tempNode = head;
        head->data = node->data;
        node->data = tempNode->data;
    }
}
system("pause");

}

Заголовочный файл 

class Node
{
public:
    Node() {}
    Node(int d, Node* q = 0) : data(d), next(q) {} //constructor with parameters data and next
    int data; //holds data in node
    Node* next;//pointer to next node
};

class List
{
public:
    void Read(istream&);
    void Write(ostream&);

    void setReadSort(bool);
    void sortOwn();
    void insertionSort(Node*);
    bool isEmpty();

    bool _sortRead;
    int numberOfInts;

    List(void);
    ~List(void);
protected:
    Node *head;
    Node current;
};

Ответы [ 3 ]

2 голосов
/ 27 апреля 2011

Это полностью зависит от реализации.Однако обычно это можно сделать очень быстро, проверив, существует ли первый узел, имеет ли он содержимое и т. Д.

0 голосов
/ 27 апреля 2011

Я не проверял это, но оно должно работать.

[edit] Изменена программа для учета всегда существующей головы.

[edit] Изменена программа для учета классавместо struct 

bool isEmpty(){return (this->head == NULL)};

Это даст более правильный результат

Еще одна вещь, я вижу, что вы используете system ("pause") ;.Я знаю, что это домашнее задание, но это крайне плохая практика.Лучшим способом было бы сначала очистить буфер в stdin (при необходимости), а затем игнорировать символ.Примером может быть: 

cin >> somenumber; // Extract a number (assuming its safe)
cin.ignore(1, 10); // Ignore 1 character, or a newline, whichever comes first
                   // ^ this clears the buffer, it does NOT wait for input since
                   // the formatted extraction left a character in the buffer ('\n')
cin.ignore();      // Essentially the same as above, but since there is nothing in
                   // the buffer, it reads a single character from stdin
0 голосов
/ 27 апреля 2011

Да.Причина в том, что иногда мы используем итератор для вставки элемента, было бы очень неудобно (или невозможно) обрабатывать количество элементов в итераторах.Это причина, по которой многие реализации STL имеют линейное время для функции size_t size(void).bool empty(void) - эффективный способ проверить, пуст ли список и имеет ли он постоянное время.

Просто заметьте: при использовании STL предпочитайте использовать bool empty(void) против size_t size(void).Больше информации в: Мейерс: Эффективный STL .

Функция проста: 

bool empty( void ) const
{
  return ( this->begin() == this->end() );
}

В вашем случае: 

bool empty( void ) const
{
  return ( this->head == 0 );
}
...