时间戳

首页 > 解决方案 > 在某个值后从链表中删除项目

c++ - 在某个值后从链表中删除项目

问题描述

我有这个问题，其中用户输入 n 并且我的程序需要从链表中删除 n 之后且不等于 n 的任何元素。例如，如果我的列表是 1,2,4,8,4,6,1 并且用户输入 4 它应该输出 1,2,4,4。

到目前为止我只有这个代码（如果列表是 1,2,4,8,4,6,1 它输出 4 8 4 6 1）：

#include <iostream>
#include <algorithm>
using namespace std;

struct elem
{
    int num;
    elem *next;
    elem(int n){num = n; next= NULL;}
};

void append(elem *&first, elem *&last, int n){
        elem *p = new elem(n);
        if(first==NULL)
            first=last=p;
        else {
            last->next=p;
            last = p;
        }
}

void deleteListItems(elem *&first, int n){
    elem *p;
    while(first){
        if(first->num==n){

            break;
        }
        else{
            p = first->next;
            delete first;
            first=p;
        }

    }
}

void print(elem *first){
    elem *p = first;
    while(p!=NULL){
        cout<<p->num<<" ";
        p = p->next;
    }
    cout<<endl;
}

int main () {

    int aa[] = {1,2,4,8,4,6,1};
    elem *first=NULL; 
    elem *last=NULL; 
    elem *p; 
    int n;

    for(int i=0; i<7; ++i){
        append(first, last, aa[i]);
    }

    print(first);

    cout<<"Input n: "<<endl;
    cin>>n;
    elem *prev;


    print(first);
    deleteListItems(first, n);
    print(first);


    /// delete list
    p = first;
    while (p!=NULL){
        first = first->next;
        delete p;
        p = first;
    }
};

标签： c++

解决方案

你的问题需要分解成两部分

  1. 找到目标值的第一个实例。
  2. 如果找到，则前进到经过它的节点，并删除每个不是目标值的节点。

使用指向指针的方法使这变得微不足道。执行此操作的代码如下所示，我尽我所能在注释中记录它是如何工作的。

void deleteListItems(elem *&first, int n)
{
    // start at head of the list
    elem **pp = &first;

    // find the first instance of n
    while (*pp && (*pp)->num != n)
        pp = &(*pp)->next;

    // if we found one...
    if (*pp)
    {
        // advance past it
        pp = &(*pp)->next;

        // now walk the rest of the list
        while (*pp)
        {
            // if this does NOT match the target value
            if ((*pp)->num != n)
            {
                // remember the node, overwrite the list pointer
                //  referring to it with it's own 'next', and then
                //  delete now-unhitched node.
                elem *p = *pp;
                *pp = p->next;
                delete p;
            }
            else
            {
                // otherwise, it's another instance of the target
                //  value, so just skip to the next node.
                pp = &(*pp)->next;
            }
        }
    }
}

这适用于我能想到的所有情况，包括没有重复的列表、完全重复的列表、空列表、单节点列表等。值得一提的是，tail指针main很容易悬空，但这是你的原始问题代码，我怀疑你会尽快解决这个问题。

推荐阅读