стек, используя связанный список - PullRequest
Новая
       0

стек, используя связанный список

0 голосов
/ 28 января 2012

Я получил "ошибку сегментации" в моем коде. что случилось? заранее спасибо. ps это стек с использованием связанного списка. 

#include <iostream>
//stack using linked list
class LinkedList {
 public:
  LinkedList() : head(0), tail(0) {}
  ~LinkedList() {
    while (!empty()) pop();
    delete head;
  }
  void pop() {
    node* temp;
    temp = head;
    for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
    }
    delete temp;
    tail->next_ = 0;
  } //removes, but does not return, the top element
  int top() {
    return tail->value_;
  } //returns, but does not remove, the top element
  bool empty() {
    return head == 0;
  }
  void push(const int& value) {
    node* element = new node(value);
    if (empty()) {
      head = tail = element;
    } else {
      tail->next_ = element;
      tail = element;
    }
  } //place a new top element
 private:
  class node {
   public:
    node(const int& input) : value_(input), next_(0) {};
    int value_; //store value
    node* next_; //link to the next element
  };
  node* head;
  node* tail;
};
int main() {
  LinkedList list;
  list.push(1);
  list.push(2);
  list.push(3);
  list.pop();
  std::cout << list.top() << std::endl;
  return 0;
}

Ответы [ 5 ]

2 голосов
/ 28 января 2012

Эта часть не выглядит правильно 

for ( ; temp->next_ != tail; temp = temp->next_) {
    tail = temp;
}

потому что если вы установите tail равным temp, temp->next != tail всегда будет истинным.

1 голос
/ 28 января 2012

Этот метод 

  void pop() {
    node* temp;
    temp = head;
    for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
    }
    delete temp;
    tail->next_ = 0;
  } //removes, but does not return, the top element

должно быть так: 

  void pop() {
    if( head == tail )
    {
        delete head;
        head = 0;
    } 
    else
    {
        node* temp;
        temp = head;
        for ( ; temp->next_ != tail; temp = temp->next_) {
        }
        delete tail;
        temp->next_ = 0;
        tail = temp;
    }
  } //removes, but does not return, the top element
1 голос
/ 28 января 2012 
for ( ; temp->next_ != tail; temp = temp->next_) {
      tail = temp;   
}

Условие должно было быть 

temp->next_ != 0
0 голосов
/ 29 января 2012

Деструктор кажется мне глючным: вы продолжаете «всплывать», пока empty () не вернет true, что происходит, когда head является нулевым указателем. Но тогда вы не можете вызвать delete on head после окончания цикла while ...

Я не знаю, в этом ли проблема, но я бы это проверил.

Еще один скромный совет: вы не сказали нам, где происходит ошибка сегмента ... Если вы запускаете свой код с помощью gdb (или если вы просто добавляете много «cout» в свой код), вы можете обнаружить строку это вызывает у вас проблемы.

0 голосов
/ 28 января 2012

Я думаю, что проблема в следующем: 

for ( ; temp->next_ != tail; temp = temp->next_) {
  tail = temp;   
}
delete temp;
tail->next_ = 0;

tail = temp должен быть после того, как вы найдете темп, который ведет к tail (т.е. вне цикла for). Кроме того, temp = не хвост, а тот, что перед хвостом. Так что, вероятно, вам нужно: 

for ( ; temp->next_ != tail; temp = temp->next_) {}
delete tail;
tail = temp;
tail->next_ = 0;
...