0

好的，我从来没有使用过列表，但我会尽力解释我想要做什么。

struct node {
 node(int value=0) { data=value; next=prev=this; }
 int data;
 node *next;
 node *prev;
};

class list {
 public:
 list(int N=0, int value=0);
 ˜list();
 bool empty() const { return N == 0; }
 bool full() const { return false; }
 int size() const { return N; }
 void resize(int);
 void clear();
 void insert(int, const int &);
 void remove(int);
 void push_back(const int &din) { insert(N, din); }
 void pop_back() { remove(N-1); }
 const int & back();
 int & operator[](int);
 private:
 int N;
 node *head;
 node *findnode(int);
}

_________________________________________
inline
node *list::findnode(int i) {
 if (i == -1)
 return head;
 node *p = head->next; 
 while (i--)
 p = p->next;
 return p;
}

我应该重写findnode()函数来做正向搜索 wheni<(N/2)和做反向搜索 when i>(N/2)。我试过了，但我不断收到分段错误。我想我只是不完全了解发生了什么。列表类中列出的所有其他函数均已正确编写。

我已经更正了我的节点结构。很抱歉，当涉及到这些对象指针和真正发生的事情时，我非常迷茫。这是我尝试过的。

 97 inline
 98 node *list::findnode(int i) {
 99         if (i == -1)
100                 return head;
101 
102         if (i < N/2){
103                 node *p = head->next;
104                 while (i--)
105                         p = p->next;
106 
107                 return p;
108         }
109 
110 
111         if (i > N/2){
112                 node *p = head->prev;
113 
114                 i =( i - N/2 );
115                 while (i--)
116                         p = p->prev;
117 
118                 return p;
119         }
120 }
4

1 回答 1

0

我不会给出完整的答案。但本质上是使用 if-else 来分割你的两种情况。在第一种情况下，像上面一样向前搜索。在第二种情况下反向搜索。但是为了做到这一点，你应该增加你的节点类来拥有一个 prev 成员，使它实际上是一个双向链表。让列表存储列表的尾部。您必须修改大多数列表函数才能完成此操作。 

inline
node *list::findnode(int i) {
 if(i < size()/2) {
   //search from beginning of list
 }
 else {
   //search from end of list by starting at tail
   node *p = tail;
   i = i-size/2;
   while(i--) {
     p = p->prev;
   }
   return p;
 }
于 2013-09-17T20:29:20.093 回答