c++ - 我如何在我的程序中使用这个单链表结构来提高我的性能？

Question

大家好，我有一个程序可以对字符串集进行操作。我要实现两组字符串的加减等功能。我需要将其降低到 O(N+M) 的性能，其中 N、M 是字符串集。现在，我相信我的表现是 O(N*M)，因为我对 N 的每个元素，我都遍历了 M 的每个元素。我特别专注于获得正确性能的减法，好像我可以将其归结为适当的性能，我相信我可以将这些知识运用到我必须实现的其他事情中。

例如，'-' 运算符假设是这样工作的。

声明set1为空集。
声明 set2 为包含 { a b c } 元素的集合
声明 set3 是一个包含 ( b c d } 元素的集合

组 1 = 组 2 - 组 3

现在 set1 假设等于 { a }。所以基本上，只需从 set3 中删除也在 set2 中的任何元素。

对于加法实现(重载“+”运算符)，我还对字符串进行排序(因为我们必须这样做)。

顺便说一句，所有功能现在都可以正常工作。

所以我想知道是否有人可以

a) 确认目前我正在做 O(N*M) 性能
b) 给我一些关于如何将性能提高到 O(N+M) 的想法/实现

注意:我不能向类 strSet 或节点结构添加任何成员变量或函数。

主程序的实现不是很重要，但我会贴出我的类定义和成员函数实现的代码:

strSet2.h(我的类和结构的实现)

// Class to implement sets of strings

// Implements operators for union, intersection, subtraction,
//  etc. for sets of strings

// V1.1 15 Feb 2011 Added guard (#ifndef), deleted using namespace RCH

#ifndef _STRSET_
#define _STRSET_

#include <iostream>
#include <vector>
#include <string>
// Deleted: using namespace std;  15 Feb 2011 RCH

struct node {
    std::string s1;
    node * next;
};

class strSet {

private:
    node * first;

public:
    strSet ();  // Create empty set
    strSet (std::string s); // Create singleton set
    strSet (const strSet &copy); // Copy constructor
    ~strSet (); // Destructor

    int SIZE() const;

    bool isMember (std::string s) const;

    strSet  operator +  (const strSet& rtSide);  // Union
    strSet  operator -  (const strSet& rtSide);  // Set subtraction
    strSet& operator =  (const strSet& rtSide);  // Assignment


};  // End of strSet class

#endif  // _STRSET_

strSet2.cpp(成员函数的实现)

#include <iostream>
#include <vector>
#include <string>
#include "strset2.h"

using namespace std;

strSet::strSet() {
    first = NULL;
}

strSet::strSet(string s) {
    node *temp;
    temp = new node;
    temp->s1 = s;
    temp->next = NULL;
    first = temp;
}

strSet::strSet(const strSet& copy) {
    if(copy.first == NULL) {
        first = NULL;
    }
    else {
        node *n = copy.first;
        node *prev = NULL;
        while (n) {
            node *newNode = new node;
            newNode->s1 = n->s1;
            newNode->next = NULL;
            if (prev) {
                prev->next = newNode;
            }
            else {
                first = newNode;
            }
            prev = newNode;
            n = n->next;
        }
    }
}

strSet::~strSet() {
    if(first != NULL) {
        while(first->next != NULL) {
            node *nextNode = first->next;
            first->next = nextNode->next;
            delete nextNode;
        }
    }
}

int strSet::SIZE() const {
    int size = 0;
    node *temp = first;
    while(temp!=NULL) {
        size++;
        temp=temp->next;
    }
    return size;
}    

bool strSet::isMember(string s) const {
    node *temp = first;
    while(temp != NULL) {
        if(temp->s1 == s) {
            return true;
        }
        temp = temp->next;
    }
    return false;
}

strSet strSet::operator +  (const strSet& rtSide) {
    strSet newSet;
    newSet = *this;
    node *temp = rtSide.first;
    while(temp != NULL) {
        string newEle = temp->s1;
        if(!isMember(newEle)) {
            if(newSet.first==NULL) {
                node *newNode;
                newNode = new node;
                newNode->s1 = newEle;
                newNode->next = NULL;
                newSet.first = newNode;
            }
            else if(newSet.SIZE() == 1) {
                if(newEle < newSet.first->s1) {
                    node *tempNext = newSet.first;
                    node *newNode;
                    newNode = new node;
                    newNode->s1 = newEle;
                    newNode->next = tempNext;
                    newSet.first = newNode;
                }
                else {
                    node *newNode;
                    newNode = new node;
                    newNode->s1 = newEle;
                    newNode->next = NULL;
                    newSet.first->next = newNode;
                }
            }
            else {
                node *prev = NULL;
                node *curr = newSet.first;
                while(curr != NULL) {
                    if(newEle < curr->s1) {
                        if(prev == NULL) {
                            node *newNode;
                            newNode = new node;
                            newNode->s1 = newEle;
                            newNode->next = curr;
                            newSet.first = newNode;
                            break;
                        }
                        else {
                            node *newNode;
                            newNode = new node;
                            newNode->s1 = newEle;
                            newNode->next = curr;
                            prev->next = newNode;
                            break;
                        }
                    }
                    if(curr->next == NULL) {
                        node *newNode;
                        newNode = new node;
                        newNode->s1 = newEle;
                        newNode->next = NULL;
                        curr->next = newNode;
                        break;
                    }
                    prev = curr;
                    curr = curr->next;
                }
            }
        }
        temp = temp->next;
    }
    return newSet;
}

strSet strSet::operator - (const strSet& rtSide) {
    strSet newSet;
    newSet = *this;
    node *temp = rtSide.first;
    while(temp != NULL) {
        string element = temp->s1;
        node *prev = NULL;
        node *curr = newSet.first;
        while(curr != NULL) {
            if( element < curr->s1 ) break;
            if( curr->s1 == element ) {
                if( prev == NULL) {
                    node *duplicate = curr;
                    newSet.first = newSet.first->next;
                    delete duplicate;
                    break;
                }
                else {
                    node *duplicate = curr;
                    prev->next = curr->next;
                    delete duplicate;
                    break;
                }
            }
            prev = curr;
            curr = curr->next;
        }
        temp = temp->next;
    }
    return newSet;
}

strSet& strSet::operator =  (const strSet& rtSide) {
    if(this != &rtSide) {
        if(first != NULL) {
            while(first->next != NULL) {
                node *nextNode = first->next;
                first->next = nextNode->next;
                delete nextNode;
            }
        }
        if(rtSide.first == NULL) {
            first = NULL;
        }
        else {
            node *n = rtSide.first;
            node *prev = NULL;
            while (n) {
                node *newNode = new node;
                newNode->s1 = n->s1;
                newNode->next = NULL;
                if (prev) {
                    prev->next = newNode;
                }
                else {
                    first = newNode;
                }
                prev = newNode;
                n = n->next;
            }
        }
    }
    return *this;
}

Answer 1

是的，我相信您当前的 operator- 是 O(N*M)。

因为这是作业，我不想给你太多信息，但是......

如果你的链表是有序的，那么你可以在 O(N+M) 中写减法。这给你留下了两个问题:如何保持列表有序？以及如何在给定有序列表的情况下编写 O(N+M) 减法算法。