加急！数据结构作业：输入一个字符串，用链表存储输出，重复的删除，然后在输出.求答案

答案:2 悬赏:0 手机版

解决时间 2021-01-25 01:44

提问者网友：温柔港
2021-01-24 05:49

最佳答案

五星知识达人网友：玩家
2021-01-24 06:33

整体思路就是遍历单链表，然后在判断当前节点是否在已访问的节点集合中，如果不在，说明该元素不重复，则将其插入到访问节点集合中，然后继续比较下一个节点，如果在其中，说明是重复出现，则从单链表中删除当前节点，然后继续比较下一个。



这里用了c++标准库中的set来保存访问过的元素，所以很方便的就可以判断当前节点是否在set集合中，直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。

还有就是这里没有申请新的内存来存储新节点，而是直接在之前的单链表上进行操作，空间上不需要什么消耗。

#include
#include
#include
using namespace std;
struct Data{
    string name;
};
//定义链表结构
struct Node{
    Data data;
    Node* next;
};
typedef Node* List;
//For test
string names[] = {"hello", "world", "hello","hello world", "zht","zhengh", "zht", "hello", "world", "hello world"};
void createList(List &list)
{
    list = new Node;
    list->data.name = "zhtsuc";
    List p = list;
    for(int i  = 0; i < 10; i++)
    {
        Node* node = new Node;
        node->data.name = names[i];
        p->next = node;
        p = node;
    }
    p->next = NULL;
}
void printList(List list)
{
    List p = list;
    while(p != NULL)
    {
        cout << p->data.name << endl;
        p = p->next;
    }
}
int main(int argc, char* argv[])
{
    List list;
    createList(list);
    set allNames;    //保存所有不重复的name

    allNames.insert(list->data.name);  //首先，把第一个元素直接加进去。因为第一个不用比较
    List pre = list; //保存前一个指针
    List cur = list->next; //当前指针

    while(cur != NULL)
    {
        //如果在set中没有找到当前元素的name，则说明该记录不重复，将该记录的name加入到set，继续下一个
        if (allNames.find(cur->data.name) == allNames.end())
        {
            allNames.insert(cur->data.name);
            pre = cur;
            cur = cur->next;
        }
        else
        {
            //如果在set中找到当前元素的name，则说明重复，即删掉此元素，然后继续下一个
            Node* temp = cur; //先保存当前节点指针
            cur = cur->next;
            pre->next = cur; //改变指针指向，删除当前节点
            //在这里释放掉temp节点
            delete temp;
        }
    }
    printList(list); //这是我的测试代码
    return 0;
}

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息