링크 된 목록을 관리하는 함수

Question

문자열의 링크 된 목록을 관리하고 조작하는 여러 함수보다 StringList라는 클래스가 있습니다. AddtoBottom이라는 목록의 맨 위에 추가하는 AddtoTop이 있습니다.이 함수는 문자열을 추가하지만 알파벳 순서, 명확한 함수, 찾기 함수, 인쇄 및 제거 함수로 추가합니다. 모든 단일 기능을 작성했지만 주요 문제가 하나 있습니다. "AddtoTop"과 "AddtoBottom"을 사용할 때 링크 된 목록에 문자열을 추가합니다. 내 두 함수를 사용하여 배치 한 문자열을 제거하도록 요청하면 내 제거 함수가 작동합니다. "추가"기능으로 추가 한 단어를 제거하려고하면 프로그램이 중단됩니다. 함수 "remove"(아래 참조)는 "AddtoBottom"및 "AddtoTop"기능을 사용하여 추가 된 문자열을 제거 할 수 있지만 "add"를 사용하여 추가 한 문자열은 제거 할 수 없습니다. 나는 그것을 다른 방식으로 다시 쓰려고 노력하지만 나는 붙어있다. 여기 내 기능은 다음과 같은

StringList::StringList() //constructor 
{ 
    pTop=NULL; 
    pBottom=NULL; 
} 

StringList::~StringList() //destructor 
{ 
    StringListNode *next; 
    for (StringListNode *sp = pTop; sp != 0; sp = next) 
    { 
     next = sp->pNext; 
     delete sp; 
    } 
} 
void StringList::add(string s) //adds and places in alphabetical order 
{ 
    if(pTop) 
    { 
     if(s < pTop->data) 
     { 
      StringListNode *A=new StringListNode; 
      A->data = s; 
      A->pNext = pTop; 
      pTop = A; // new top 
      return; 
     } 
     // go further into list 
     StringListNode *iter = pTop; 
     while(iter->pNext)  
     { 
      if( iter->pNext->data < s) 
       iter = iter->pNext; 
      else 
       break; 
     } 
     StringListNode *in=new StringListNode; //actuallly inserts node 
     in->data = s; 
     in->pNext = iter->pNext; 
     iter->pNext = in; 
    } 
    else// new item 
    { 
     pTop = new StringListNode; 
     pTop->data = s; 
     pTop->pNext = NULL; 
    } 
} 

StringList::StringListNode *StringList::find(const string &s) //basic search function 
{ 
    StringListNode *sp = pTop; // Search 
    while (sp != 0 && sp->data != s) 
     sp = sp->pNext; 
    return sp; 
} 

void StringList::addToTop(string s) //add to top of nodes 
{ 
    if(isEmpty()) 
    { 
     StringListNode * pNewNode; 
     pNewNode = new StringListNode; 
     (*pNewNode).data = s; 
     pTop=pNewNode; 
     pBottom=pNewNode; 
     (*pNewNode).pPrev = NULL; 
     (*pNewNode).pNext = NULL; 
    } 
    else //it's not empty 
    { 
     StringListNode * pNewNode; 
     pNewNode = new StringListNode; 
     (*pNewNode).data = s; 
     (*pNewNode).pNext = pTop; 
     (*pTop).pPrev = pNewNode; 
     (*pNewNode).pPrev =NULL; 
     pTop=pNewNode; 
    } 
} 

void StringList::addToBottom(string s) // add to bottom 
{ 
    if(isEmpty()) 
    { 
     StringListNode * pNewNode; 
     pNewNode = new StringListNode; 
     (*pNewNode).data = s; 
     pTop=pNewNode; 
     pBottom=pNewNode; 
     (*pNewNode).pPrev = NULL; 
     (*pNewNode).pNext = NULL; 
    } 
    else 
    { 
     StringListNode * pNewNode; 
     pNewNode = new StringListNode; 
     (*pNewNode).data = s; 
     (*pBottom).pNext = pNewNode; 
     (*pNewNode).pPrev = pBottom; 
     (*pNewNode).pNext =NULL; 
     pBottom=pNewNode; 
    } 
} 

string StringList::print() //prints strings in linked list 
{ 
    string result; 
    StringListNode * pCurrent; 
    pCurrent=pTop; 
    while(pCurrent!=NULL) 
    { 
     result+=(*pCurrent).data+"\n"; 
     pCurrent=(*pCurrent).pNext; 
    } 
    return result; 
} 

void StringList::clear() //clears everything 
{ 
    pTop = NULL; 
    pBottom = NULL; 
} 

void StringList::remove(string s) //removes a string 
{ 
    StringListNode *curr = this->find(s); 
    if (curr->pPrev != 0) 
     curr->pPrev->pNext = curr->pNext; 
    if (curr->pNext != 0) 
     curr->pNext->pPrev = curr->pPrev; 
    if (pTop == curr) 
     pTop = curr->pNext; 
    if (pBottom == curr) 
     pBottom = curr->pPrev; 
} 

Answer 1

시도 뭔가 : 당신은 아마 사용하는 것이 더 낫다

void StringList::add(string s) //adds and places in alphabetical order 
{ 
    if(pTop) 
    { 
     StringListNode *iter = pTop; 
     while (iter && s > iter->data) 
      iter = iter->pNext; 

     if (iter) 
     { 
      // insert before 
      StringListNode *A=new StringListNode; 
      A->data = s; 
      A->pNext = iter; 
      A->pPrev = iter->pPrev; 
      if (iter->pPrev) 
       iter->pPrev->pNext = A; 
      else 
       pTop = A; 
      iter->pPrev = A; 
      return; 
     } 
    } 

    // add to bottom 
    addToBottom(s); 
} 

주의점 std::set (또는 std::multiset)이 아닌 것과 자신의 목록 코드를 압연 계속됩니다 문자열은 자동으로 정렬되며 조회 및 무작위 삽입은 일반적으로 선형이 아닌 대수 시간으로 수행됩니다.

Answer 2

add() 코드의 주된 문제점은 pPrev 포인터를 설정하지 않았다는 것입니다 (그러나해야 함). '제거하는 방법'질문에 대한 답에서 사용했던 다이어그램과 비슷한 다이어그램을 그려보고 새 노드를 추가 할 때 필요한 과제를 확인하십시오.

"데이터 구조가 올바른지 어떻게 확인할 수 있습니까?" 예를 들어,리스트의 중간에 각 노드 curr에서, 당신이 주장 할 수 있어야한다 :

assert(curr->pPrev->pNext == curr); 
assert(curr->pNext->pPrev == curr); 

최종 포인터가 null 인에 대한 조정, 당신은 작성할 수 있습니다

assert(curr->pPrev == 0 || curr->pPrev->pNext == curr); 
assert(curr->pNext == 0 || curr->pNext->pPrev == curr); 

귀하의 add() 코드는 않습니다 이러한 불변성이 유지되는지 확인하지 마십시오. 또한 문제가 발생합니다. 목록이 addToTop() 또는 addToBottom()에 의해 유지되는 경우 목록이 정렬 된 순서로 보장되지 않기 때문에 add()을 사용하면 안정적으로 작동하지 않습니다.

또한 이전 질문에 대한 대답에서 (구체적으로 논의하지는 않았지만) string s을 사용하는 대신 const string &s으로 문자열을 전달해야합니다. 일반적으로 코드의 효율성에 상당한 영향을 미칩니다.