正確地實現單鏈表C++

Question

我有僱主如名稱的列表：

節點1：小杰，馬特，喬，鮑勃，馬特

節點2：傑夫，詹姆斯，約翰，喬納森，約翰，愛德華

節點3：馬特，能源部，羅恩，巴勃羅，滾裝ñ，大通，羅恩，大通，路易

，我想它去的地方，如果它看到一個重複將其發送到列表的前面，並刪除當前節點，所以它看起來像這樣

節點1：馬特，吉爾，喬，鮑勃

節點2：約翰，傑夫，詹姆斯，喬納森·愛德華

節點3：大通，羅恩，馬特，能源部，巴勃羅，路易

不幸的是，我的輸出是接近我想要什麼。它會刪除重複的條目，但不會發送到前面。 。

我的輸出：

節點1：小杰，馬特，喬，鮑勃，

Answer 1

我改變了你的變量名是更具可讀性，但保留了向前聲明的情況下，你希望它像那。我發現的問題是，無論您是否發現它是重複的，您總是將該節點插入列表的末尾。此外，您的評論線條看起來很接近，但只有在一個人的情況下。隨着pp=p的東西，它會導致問題。嘗試以下方法，看看它是否有效。你仍然可以泄漏內存，但它會幫助您入門：

void list::put(int i) { //Where i is a random number 
    node *current =head; 
    node *added =new node(employers[i]); 
    node *tail =head; 
    node *prev = NULL; 
    bool foundRepeat = false; 



    while (current!=NULL) 
    { 
     if (current->data == added->data) 
     { 
      if (prev) 
       prev->next = current->next; 

      current->next=head; 
      head=current; 
      foundRepeat = true; 
      break; 
     } 
     prev = current; 
     current=current->next; 
    } 

    if (!foundRepeat) 
    { 
     while (tail->next) 
     { 
      tail=tail->next; 
     } 
     tail->next=added; 
    } 

    N++; 
} 

Answer 2

好吧，讓我們來看看：

當你在這一點上打if (ptr->data == p->data)：

• pp點結束的名單
• p是你的新節點（沒有指向它，它指向什麼都沒有）
• ptr點與重複數據

爲了刪除您需要實際需要有next指針指向ptr節點的節點，否則你怎麼能刪除列表中的ptr？所以你實際上需要檢查：

if (head && head->data == p->data) 
{ 
    // do nothing as duplicate entry is already head of list 
    delete p; 
    return; 
} 

node *ptr = head; 
while (ptr) 
{ 
    if (ptr->next && ptr->next->data == p->data) 
    { 
     node *duplicate = ptr->next; 
     ptr->next = duplicate->next; // skip the duplicate node 
     duplicate->next = head;  // duplicate points to head 
     head = duplicate;   // head is now the duplicate 
     delete p;     // otherwise leaking memory 
     return; 
    } 
    ptr = ptr->next; 
} 

if (pp) // points to tail as per your code 
{ 
    pp->next = p; 
    ++N; 
} 

Answer 3

對於它的價值，我可能會這樣實現它。

class EmployerCollection 
{ 
public: 
    typedef std::list<std::string> EmployerList; 

public: 
    bool AddEmployer(const std::string& name) 
    { 
     EmployerList::const_iterator it = std::find(m_employers.begin(), m_employers.end(), name); 
     if (it != m_employers.end()) // Already exists in list. 
     { 
      m_employers.splice(m_employers.begin(), m_employers, it, std::next(it)); 
      return true; 
     } 
     m_employers.push_front(name); 
     return false; 
    } 

private: 
    EmployerList m_employers; 
}; 

int main() 
{ 
    const int NUM_EMPLOYERS = 15; 
    std::string employers[NUM_EMPLOYERS] = {"Jill", "Jeff", "Doe", "Pablo", "Loui", "Ron", "Bob", "Joe", "Monica", "Luis", "Edward", "Matt", "James", "Edward", "John"}; 

    EmployerCollection c; 

    for (int i=0; i<NUM_EMPLOYERS; i++) 
    { 
     bool duplicate = c.AddEmployer(employers[i]); 
     printf("Added %s to employer list - duplicate: %s \n", employers[i].c_str(), duplicate ? "True" : "False"); 
    } 

    system("pause"); 
} 

Answer 4

我添加了一個查找功能

typedef struct node{ 
    string data; 
    struct node *net, *prev; 
}node;  


class list { 
public: 
    list():head(NULL), N(0){} 
    ~list(){ 
    //Implementation for cleanup 
    } 

void add(string name){ //rather than accessing the global data, use the value passed 
    node* p = new node(name); 
    p->next=p->prev=NULL; 
    node* pp = find(name); 
    if(pp==NULL){ 
     // No match found, append to rear 
     if(head==NULL) 
     head=p; //list empty, add first element 
     else{ 
     node* cur=head; 
     while(cur->next!=NULL) //Keep looking until a slot is found 
      cur=cur->next; 
     cur->next=p; 
     p->prev=cur; 
     } 
    } 
    else{ 
     //Match found, detach it from its location 
     node* pPrev = pp->prev; 
     pPrev->next = pp->next; 
     pp->next->prev=pPrev; 
     p->next = head; //append it to the front & adjust pointers 
     head->prev=p; 
    } 
    N++; 
    } 

    //MER: finds a matching element and returns the node otherwise returns NULL 
    node* find(string name){ 
     node *cur=head; 
     if(cur==NULL) // is it a blank list? 
      return NULL; 
     else if(cur->data==head) //is first element the same? 
      return head; 
     else // Keep looking until the list ends 
      while(cur->next!=NULL){ 
      if(cur->data==name) 
      return cur; 
      cur=cur->next; 
      } 
     return NULL; 
} 
friend ostream& operator << (ostream& os, const list& mylist); 

private: 
    int N; 
    node *head; 

}; 

現在有些人可能會告訴你使用STL中的列表絕對不要編寫自己的代碼，因爲你不能擊敗STL，但對我來說這是很好的，你正在實現自己的清晰的想法如何在現實中運作。