節點不附加到鏈接列表

Question

我一直在C++中實現單向鏈表。但是，我正在努力在特定節點之後插入一個節點，並刪除一個有目標的節點。我檢查瞭解析到節點的節點，並發現節點甚至沒有附加到鏈表中。

struct SNode { 
string* element; 
SNode *next; // Pointer to the next node 

/* Creates a node. */ 
SNode(string* e, SNode* n) { 
    element = e; 
    next = n; 
} 
string* getElement() { return element; } 
void print() { cout << *element; } 
}; 

class SList { 
protected:  // data member 
SNode* head; 
long size;  // number of nodes in the list 

public: 
/* Default constructor that creates an empty list */ 
SList() { 
    head = NULL; 
    size = 0; 
} 
// ... update and search methods would go here ... 
long getSize() { return size; } 
int isEmpty() { return size<=0; } 

// add a new node to the beginning of the list 
SNode* addFirst(string* s) { 
    SNode* newNode = new SNode(s, head); 
    head = newNode; 
    size++; 
    return newNode; 
} 

//remove the first node in the list 
string* removeFirst() { 
    if (head==NULL) return NULL; 
    SNode* node = head; 
    head = head->next; 
    string* s = node->element; 
    node->next = NULL; 
    delete node->element; 
    size--; 
    return s; 
} 

// insert a new node after node n and store the string s there 
void insertAfter (SNode n, string* s) { 
    SNode* newNode = new SNode(s, n.next); 
    n.print();      //print out 2 
    cout << endl; 
    n.next = newNode; 
    (n.next)->print();    //print out 6 
    cout << endl; 
    ((n.next)->next)->print();  //print out 1 
    cout << endl; 
    size++; 
    SNode* iter = head; 
    while(iter != NULL){ 
     if(iter == &n){ 
      cout << "ok" << endl; 
     } 
     iter = iter->next; 
    }         //but not print out "ok" 
    print(); 
    return; 
} 

// delete node n and return the string stored in n 
string* insertAfter (SNode n) { 
    SNode* iter = head; 
    while(iter != NULL){ 
     if(iter->next == &n){ 
      break; 
     } 
     iter = iter->next; 
    } 
    iter->next = n.next; 
    n.next = NULL; 
    string* s = n.element; 
    delete n.element; 
    size--; 
    return s; 
} 

//display the list's data in order from head to tail 
void print() { 
    SNode* iter = head; 
    while (iter!=NULL) { 
     // call SNode method to display iter's data 
     iter->print(); 
     cout << endl; 
     iter = iter->next; 
    } 
    cout << endl; 
} 

int isNode(SNode n){ 
    SNode* iter = head; 
    while(iter != NULL){ 
     if(iter == &n){ 
      return 1; 
     } 
     iter = iter->next; 
    } 
    return 0; 
} 
}; 

int main(void) 
{ 
    SList* dl = new SList(); 
    string s1 = "1"; 
    SNode* p = dl->addFirst(&s1); 
    dl->print(); 

    string s2 = "2"; 
    //dl->addFirst(&s2); 
    SNode* p2 = dl->addFirst(&s2); 
    cout << endl; 
    dl->print(); 

    string s3 = "3"; 
    dl->addFirst(&s3); 
    dl->print(); 

    string s4 = "4"; 
    dl->addFirst(&s4); 
    dl->print(); 

    string s5 = "5"; 
    dl->addFirst(&s5); 
    dl->print(); 

    dl->removeFirst(); 
    dl->print(); 
    dl->removeFirst(); 
    dl->print(); 

    cout << dl->isNode(*p2) << endl;   //still not print "ok" 

    string s6 = "6"; 
    dl->insertAfter((*p2), &s6); 
    dl->print(); 

    return 0; 
} 

Answer 1

你傳入SNode對象按值到insertAfter()和isNode()，所以== &n將從未支票是真的。您需要通過指針代替。

此外，在該列表中的第二個節點p2點，但使用p2指針，現在應該是無效的調用insertAfter()之前，務必從列表中刪除2個節點（假若你實現一個有效的刪除功能，你沒」 T）。

嘗試一些更喜歡這個：

struct SNode { 
    string element; 
    SNode *next; // Pointer to the next node 

    /* Creates a node. */ 
    SNode(string e, SNode *n) { 
     element = e; 
     next = n; 
    } 

    string getElement() { return element; } 
    void print() { cout << element; } 
}; 

class SList { 
protected:  // data member 
    SNode* head; 
    long size;  // number of nodes in the list 

public: 
    /* Default constructor that creates an empty list */ 
    SList() { 
     head = NULL; 
     size = 0; 
    } 

    // ... update and search methods would go here ... 
    long getSize() { return size; } 
    int isEmpty() { return (size <= 0); } 

    // add a new node to the beginning of the list 
    SNode* addFirst(string s) { 
     SNode* newNode = new SNode(s, head); 
     head = newNode; 
     size++; 
     return newNode; 
    } 

    //remove the first node in the list 
    string removeFirst() { 
     if (head == NULL) return ""; 
     SNode* node = head; 
     head = node->next; 
     size--; 
     string s = node->element; 
     delete node; 
     return s; 
    } 

    // insert a new node after node n and store the string s there 
    void insertAfter (SNode *n, string s) { 
     SNode* iter = head; 
     while (iter != NULL) { 
      if (iter == n) { 
       break; 
      } 
      iter = iter->next; 
     } 
     if (iter == NULL) { 
      return; 
     } 
     SNode* newNode = new SNode(s, iter->next); 
     iter->next = newNode; 
     size++; 
    } 

    // delete node n and return the string stored in n 
    string removeNode (SNode *n) { 
     SNode *iter = head; 
     SNode *previous = NULL; 
     while (iter != NULL) { 
      if (iter == n) { 
       break; 
      } 
      previous = iter; 
      iter = iter->next; 
     } 
     if (iter == NULL) { 
      return ""; 
     } 
     if (previous != NULL) { 
      previous->next = iter->next; 
     } 
     if (head == iter) { 
      head = iter->next; 
     } 
     size--; 
     string s = iter->element; 
     delete iter; 
     return s; 
    } 

    //display the list's data in order from head to tail 
    void print() { 
     SNode* iter = head; 
     while (iter != NULL) { 
      // call SNode method to display iter's data 
      iter->print(); 
      cout << endl; 
      iter = iter->next; 
     } 
     cout << endl; 
    } 

    bool hasNode(SNode *n) { 
     SNode* iter = head; 
     while (iter != NULL) { 
      if (iter == n) { 
       return true; 
      } 
      iter = iter->next; 
     } 
     return false; 
    } 
}; 

int main(void) 
{ 
    SList* dl = new SList(); 
    SNode* p = dl->addFirst("1"); 
    dl->print(); 

    SNode* p2 = dl->addFirst("2"); 
    cout << endl; 
    dl->print(); 

    dl->addFirst("3"); 
    dl->print(); 

    dl->addFirst("4"); 
    dl->print(); 

    dl->addFirst("5"); 
    dl->print(); 

    cout << dl->hasNode(p2) << endl; 

    dl->insertAfter(p2, "6"); 
    dl->print(); 

    dl->removeFirst(); 
    dl->print(); 
    dl->removeFirst(); 
    dl->print(); 

    delete dl; 

    return 0; 
} 

話雖這麼說，你真的應該（在C++ 11或std::forward_list）使用std::list，而不是手動執行的列表：

#include <list> 
#include <string> 
#include <algorithm> 

//display the list's data in order from head to tail 
void printString(const std::string &s) { 
    std:::cout << s << std::endl; 
} 

void printList(const std::list<std::string> &v) { 
    std::for_each(v.begin(), v.end(), &printString); 
    std::cout << std::endl; 
} 

int main(void) 
{ 
    std::list<std::string> dl; 
    dl.push_front("1"); 
    printList(dl); 

    dl.push_front("2"); 
    std::list<std::string>::iterator p2 = dl.begin(); 
    std::cout << std::endl; 
    printList(dl); 

    dl.push_front("3"); 
    printList(dl); 

    dl.push_front("4"); 
    printList(dl); 

    dl.push_front("5"); 
    printList(dl); 

    dl.insert(p2+1, "6"); 
    printList(dl); 

    dl.pop_front(); 
    printList(dl); 
    dl.pop_front(); 
    printList(dl); 

    return 0; 
}