使用插入和删除修改c++链表

Question

我需要取第一个链表，并使用插入和删除函数将其转换为注释的第二个列表。我不知道怎么做，因为我不知道如何使用删除函数或插入函数不止一次。

编辑:我更新了代码，插入和删除了某些部分，程序在打印功能上遇到了问题。

#include <iostream>
#include <string>
using namespace std;
struct Cafe
    {
    string item;
    int count;
    Cafe *link;
    };
typedef Cafe* CafePtr; 
void head_insert(CafePtr& head, string i, int c);
CafePtr searchnum(CafePtr& head, int target);
CafePtr searchstr(CafePtr& head, string target); 
void insert (CafePtr after_me, string i, int c);//insert a node in the list
void print (CafePtr head);                      //print the list
void remove(CafePtr before, CafePtr discard);   //remove a node from the list
int main(){
    CafePtr head;
    CafePtr iter, h;
    head = new Cafe;
    head->link = NULL;
    head_insert(head, "QL", 3808);
    head_insert(head, "CHGHS", 1312);
    head_insert(head, "REI", 10466);
    head_insert(head, "CPT", 1678);
    head_insert(head, "NetApp", 6887);
    head_insert(head, "EJ", 36937);
    head_insert(head, "WFM", 41717);
    head_insert(head, "SAS", 6046);
    head_insert(head, "BCG", 1958);
    head_insert(head, "Google", 18500);
    print (head);
    CafePtr before = searchstr(head, "Google"); 
    CafePtr discard = searchstr(head, "BCG");
    remove(before, discard);
    before = searchstr(head, "Google");
    discard = searchstr(head, "SAS"); 
    remove(before, discard);
    CafePtr after_me = searchstr(head, "Google");
    insert(after_me, "SAS", 6373);
    after_me = searchstr(head, "SAS");
    insert(after_me, "CHGHS", 1378);
    before = searchstr(head, "CHGHS");
    discard = searchstr(head, "WFM"); 
    remove(before, discard);
    after_me = searchstr(head, "CHGHS");
    insert(after_me, "BCG", 2314);
    before = searchstr(head, "BCG");
    discard = searchstr(head, "EJ"); 
    remove(before, discard);
    after_me = searchstr(head, "BCG");
    insert(after_me, "WFM", 43927);
    before = searchstr(head, "WFM");
    discard = searchstr(head, "NetApp"); 
    remove(before, discard);
    after_me = searchstr(head, "WFM");
    insert(after_me, "NetApp", 7426);
    before = searchstr(head, "NetApp");
    discard = searchstr(head, "CPT"); 
    remove(before, discard);
    after_me = searchstr(head, "NetApp");
    insert(after_me, "Hilcorp", 1012);
    before = searchstr(head, "Hilcorp");
    discard = searchstr(head, "REI"); 
    remove(before, discard);
    after_me = searchstr(head, "Hilcorp");
    insert(after_me, "EJ", 35114);
    //before = searchstr(head, "EJ");
    //discard = searchstr(head, "CHGHS"); <- If this bunch gets uncommented, the program breaks.
    //remove(before, discard);
/*  after_me = searchstr(head, "EJ");
    insert(after_me, "Ultimate", 1440);
    after_me = searchstr(head, "CHGHS"); //These things just need to be added after, these are the two final additions to the list
    insert(after_me, "CPT", 1896);
    */

    cout << endl;
    print(head); //If i remove this from the program, and uncomment the problem lines above, the program runs fine.
    return 0;
}
void head_insert(CafePtr& head, string i, int c)
{
    CafePtr temp_ptr;
    temp_ptr = new Cafe;
    temp_ptr -> item = i;
    temp_ptr -> count = c;
    temp_ptr -> link = head;
    head = temp_ptr;
}
CafePtr searchnum(CafePtr& head, int target)
{
    CafePtr here = head;
    if(here == NULL)
    {
        return NULL;
    }
    else
    {
        while(here->count !=target && here->link != NULL)
            here = here->link;
        if(here->count == target)
            return here;
        else
            return NULL;
    }
}
CafePtr searchstr(CafePtr& head, string target)
{
    CafePtr here = head;
    if(here == NULL)
    {
        return NULL;
    }
    else
    {
        while(here->item !=target && here->link != NULL)
            here = here->link;
        if(here->item == target)
            return here;
        else
            return NULL;
    }
}
void insert (CafePtr after_me, string i, int c)
{
    CafePtr temp_ptr;
    temp_ptr = new Cafe;
    temp_ptr->item = i;
    temp_ptr->count = c;
    temp_ptr->link = after_me->link;
    after_me->link = temp_ptr;          
}

void print (CafePtr head)
{
    for (CafePtr iter = head; iter !=NULL; iter=iter->link)
    {
        cout << (iter->item) << "t" << (iter->count) << endl; //This line is where the debugger encounters a problem
    }
}
void remove(CafePtr before, CafePtr discard)
{
    before->link = discard->link;
    delete discard;                 
}

Answer 1

Ok

你需要销毁一个链表，并创建一个与你销毁的链表完全相同的第二个链表。

让我们一步一步来。

1) Remove one element from head of linked list 1
2) Add the element thus removed to the end of list 2.

或1)移除链表1尾部的元素2)将删除的元素添加到链表2的头部

因为它是一个奇异链表，让我们接近1/-删除1的头部并添加到2的尾部

在此之前，您需要在现有的remove函数中添加null保护。

 
// The second argument is not needed. before's link should be discard.
void remove(CafePtr before) // , CafePtr discard)
{
    CafePtr discard = before->link;
    // The guard. If before is the tail.
    if (discard != NULL)
        before->link = discard->link;
    // deletion on NULL has no effect so the above guard is unnecessary here.
    delete discard;
}
 

现在，我们需要添加一个remove_head函数

// This will just remove the current head from linked list but won't delete the object.
CafePtr remove_head(CafePtr& head)
{
    if (head == NULL) return NULL;
    CafePtr to_discard = head;
    head = to_discard->link;
    to_discard->link = nullptr;
    return to_discard;
}

现在在这里施展你的魔法。

我把剩下的留作家庭作业。如果有帮助，请告诉我。

我不知道你想做什么。但是你目前的链表方法设计是错误的。

在标准的单链表中，以下应该是方法，

// Insert should accept preallocated toInsert element and a after pointer after which we want to insert
void insert(CafePtr toInsert, CafePtr after);
// Remove should accept the element to remove. If elemToRemove not found, it should return gracefully.
void remove(CafePtr elemToRemove);

以上方法提供了更多的优雅和更多的控制。

但是在当前代码中做这个

before = searchstr(head, "SAS");
discard = searchstr(head, "CHGHS"); //<- If this bunch gets uncommented, the program breaks.

你会好的。

首先设计你的链表，写下你想要做的事情，然后运行你的算法以便调试。