雙向鏈表C++用類

Question

我想創建一個雙向鏈表實現：

class DblLinkedBag 
{ 
    private: 
    struct node{ 


    string data; 
    node* next; 
    node* prev; 
}*start=NULL; 

int itemCount; 
string item; 
    node *head; 
    node *tail; 



public: 
DblLinkedBag(); 
~DblLinkedBag();      
int getCurrentSize(); 
bool isEmpty(); 
string add(string value); 
bool remove(string item); 
void clear(); 
bool contains(string target); 
int getFrequencyOf(); 
string toVector(); 
string getItem(); 
void display(); 


}; 

到目前爲止，我已經得到了補充，的isEmpty，getCurrentSize和明確的工作。現在我只需要其餘的工作，我很難。我的教授給了我們一個要求，這個類必須像這樣實現：

#include <iostream> 
    #include <string> 
    #include "LinkedBag.h" 

    using namespace std; 

    void displayBag(LinkedBag<string>& bag) 
{ 
cout << "The bag contains " << bag.getCurrentSize() 
    << " items:" << endl; 
vector<string> bagItems = bag.toVector(); 

int numberOfEntries = (int) bagItems.size(); 
for (int i = 0; i < numberOfEntries; i++) 
{ 
    cout << bagItems[i] << " "; 
} // end for 
cout << endl << endl; 
} // end displayBag 

    void copyConstructorTester() 
{ 
    LinkedBag<string> bag; 
string items[] = {"zero", "one", "two", "three", "four", "five"}; 
    for (int i = 0; i < 6; i++) 
    { 
     cout << "Adding " << items[i] << endl; 
    bool success = bag.add(items[i]); 
    if (!success) 
    cout << "Failed to add " << items[i] << " to the bag." << endl; 
} 
displayBag(bag); 

LinkedBag<string> copyOfBag(bag); 
cout << "Copy of bag: "; 
displayBag(copyOfBag); 

    cout << "The copied bag: "; 
displayBag(bag); 
    } // end copyConstructorTester 

void bagTester() 
{ 
LinkedBag<string> bag; 
cout << "Testing the Link-Based Bag:" << endl; 
cout << "isEmpty: returns " << bag.isEmpty() 
<< "; should be 1 (true)" << endl; 
    displayBag(bag); 

    string items[] = {"one", "two", "three", "four", "five", "one"}; 
    cout << "Add 6 items to the bag: " << endl; 
    for (int i = 0; i < 6; i++) 
    { 
    bag.add(items[i]); 
    } // end for 

    displayBag(bag); 

    cout << "isEmpty: returns " << bag.isEmpty() 
<< "; should be 0 (false)" << endl; 

cout << "getCurrentSize: returns " << bag.getCurrentSize() 
<< "; should be 6" << endl; 

cout << "Try to add another entry: add(\"extra\") returns " 
<< bag.add("extra") << endl; 

cout << "contains(\"three\"): returns " << bag.contains("three") 
<< "; should be 1 (true)" << endl; 
cout << "contains(\"ten\"): returns " << bag.contains("ten") 
<< "; should be 0 (false)" << endl; 
cout << "getFrequencyOf(\"one\"): returns " 
<< bag.getFrequencyOf("one") << " should be 2" << endl; 
cout << "remove(\"one\"): returns " << bag.remove("one") 
<< "; should be 1 (true)" << endl; 
cout << "getFrequencyOf(\"one\"): returns " 
<< bag.getFrequencyOf("one") << " should be 1" << endl; 
cout << "remove(\"one\"): returns " << bag.remove("one") 
<< "; should be 1 (true)" << endl; 
cout << "remove(\"one\"): returns " << bag.remove("one") 
<< "; should be 0 (false)" << endl; 
cout << endl; 

displayBag(bag); 

cout << "After clearing the bag, "; 
bag.clear(); 

cout << "isEmpty: returns " << bag.isEmpty() 
<< "; should be 1 (true)" << endl; 
} // end bagTester 

    int main() 
    { 
copyConstructorTester(); 
bagTester(); 
return 0; 
} // end main 

到目前爲止，這是我的。

#include <iostream> 
#include <string> 
#include <vector> 
#include <stdio.h> 
#include <stdlib.h> 

using namespace std; 



    class DblLinkedBag 
{ 
    private: 
    struct node{ 


    string data; 
    node* next; 
    node* prev; 
    }*start=NULL; 

    int itemCount; 
    string item; 
    node *head; 
    node *tail; 



    public: 
DblLinkedBag(); 
~DblLinkedBag();      
int getCurrentSize(); 
bool isEmpty(); 
string add(string value); 
bool remove(string item); 
void clear(); 
bool contains(string target); 
int getFrequencyOf(); 
string toVector(); 
string getItem(); 
void display(); 


}; 


    DblLinkedBag::DblLinkedBag() 
{ 
    itemCount=0; 
    item; 
} 




string DblLinkedBag::add(string value) 
{ 

    node* n; 

     cout<<itemCount<<endl; 
     if(itemCount==0) 
{ 
    n=new node; 
    n->data=value; 
    n->prev=NULL; 
    head=n; 
    tail=n; 



    } 

if(itemCount>0 && itemCount<7) 
{ 
    n= new node; 
    n->data=value; 
    n->prev=tail; 
    tail->next=n; 
    tail=n; 


} 

    itemCount++; 
    return value; 
    } 

    void DblLinkedBag::display() 
{ 
struct node* temp=start; 
while(temp != NULL) 
{ 

cout<<temp->data<<endl; 
temp=temp->next; 
} 


} 



    int DblLinkedBag::getCurrentSize() 
    { 
return itemCount; 
} 



bool DblLinkedBag::contains(string target) 
    { 
    //need help here, supposed to tell if the linked list contains a certain //string 
    bool found= false; 
    node* curPtr=start; 
    int i=0; 

    while (!found && (curPtr!=NULL)&& (i<itemCount)) 
    { 

    if(target==curPtr->data) 
    { 
     found=true; 
    } 
    else 
    { 
     i++; 
     curPtr=curPtr->next; 
    } 
    } 
    return found; 
    } 
    bool DblLinkedBag::isEmpty() 
    { 
    bool empty; 
    if (itemCount==0) 
    { 
empty=true; 
} 

    else 
    empty=false; 

    return empty; 
} 

void DblLinkedBag::clear() 
{ 
    node* nodeToDelete=start; 
    while (start != NULL) 
{ 
    start=start->next; 
    nodeToDelete->next=NULL; 
    delete nodeToDelete; 
    } 
     itemCount=0; 
    } 

    bool DblLinkedBag::remove(string item) 
{ 
    //need help here 
} 
    string DblLinkedBag::toVector() 
    { 
    //need help here this is supposed to send the linked list to a vector 
    vector<string> vct; 
    node* curPtr= start; 
    int counter = 0; 
    while ((curPtr != NULL) && (counter < itemCount)) 
    { 
    vct.push_back(curPtr->data); 
    curPtr = curPtr->next; 
    counter++; 

} 

} 

int DblLinkedBag::getFrequency() 
{//supposed to show how many of a certain item are in the linked list 


DblLinkedBag::~DblLinkedBag() 
{ 
} 

任何執行這些類函數來創建其他功能我的教授給我將不勝感激的幫助下，我已經嘗試了各種不同類型的實現，我似乎無法弄清楚。

Answer 1

首先：你的方法DblLinkedBag ::明確了一個錯誤，nodeToDelete永遠不會改變（只是刪除第一個節點）

bool DblLinkedBag::remove(string item) 
{ 
    node* curPtr=start; 

    while (curPtr!=NULL) 
    { 
     if(item==curPtr->data) 
     { 
      if(curPtr->prev) curPtr->prev->next = curPtr->next; 
      if(curPtr->next) curPtr->next->prev = curPtr->prev; 
      delete curPtr; 
      itemCount--; 
      return true; 
     } 
     else 
     { 
      curPtr=curPtr->next; 
     } 
    } 
    return false; 
} 

你有什麼期望getFrequency（）做什麼？