0

在基于数组的列表的程序中，我有一个调用以下 3 次的函数：

list->remove(1)

我的问题是，当它打印出来时，它说它正在删除原始的第一项 3 次，而不是转到下一个新的第一项。

具体来说，当调用此代码时test.cpp： 

for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
                cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
                cout << "*** Error deleting from position " << i << " ***" << endl;
        }
}

它返回以下内容：

删除项目 1.
删除项目 1
删除项目 2.
删除项目 1
删除项目 3.
删除项目 1

这是ABList我创建的课程。我认为错误出在我的remove方法中，但我不知道在哪里： 

#ifndef _ABLIST_H_
#define _ABLIST_H_

#define LIST_MAX 10

#include <iostream>
#include "ABCList.hpp"

using namespace std;

template <class T>
class ABList : public ABCList<T> {

    private:
        T    a[LIST_MAX];
        int  size;

    public:
        ABList ();
        ~ABList ();
        virtual bool isEmpty ();
        virtual int  getLength ();
        virtual void insert (int pos, T item);
        virtual T    remove (int pos);
        virtual T    retrieve (int pos);
};


template <class T>
ABList<T>::ABList () {
    size = 0;
}

template <class T>
bool ABList<T>::isEmpty () {
    if (size == 0)
        return true;
    return false;
}

// returns size, which is updated whenever the list is lengthened or shortened
template <class T>
int ABList<T>::getLength() {
    return size;
}

template <class T>
void ABList<T>::insert(int pos, T item) {

    try {
        // if list is at maximum size
        if (size >= LIST_MAX)
            throw "Size is greater than or equal to LIST_MAX\n";
        // if "pos" is a negative number
        if (pos < 0)
            throw "Pos must be greater than 0\n";
        // if "pos" is outside the bounds of the existing list
        if (pos > size + 1)
            throw "Pos must be less than or equal to list size\n";

        //shift all items at indices > pos one index up
        for (int i = size; i >= pos; --i) {
            a[i] = a[i-1];
        }
        //insert new item
        a[pos-1] = item;
        //increment size
        size++;

    } catch (char* message) {
        cout << "Error: " << message;
        throw 1; // any int will do, to catch exception flag in test.cpp
    }
}

template <class T>
T ABList<T>::remove(int pos) {

    try {
        if (pos < 1)
            throw "Pos cannot be less than 1";
        if (pos > size)
            throw "Pos cannot be greater than size";
        //find T to be removed, to return later
        T temp = retrieve(pos);
        //shift all items greater than pos down one index
        for (int i = pos + 1; i <= size; i++)
            a[i] = a[i+1];
        // decrement size
        size--;
        return temp;
    } catch (char* message) {
        cout << "Error: " << message;
        throw 1;
    }
}

template <class T>
T ABList<T>::retrieve(int pos) {
    try {
        //check that pos is valid
        if (pos < 1 || pos > size)
            throw "Position is outside bounds of ABList\n";

        return a[pos-1];

    } catch (char* message) {
        cout << "Error: " << message;
    }
}


#endif

这是主程序。（为了这个问题，我不得不假设它是不可变的）： 

int main () {
    // Testing the List implmenetations; first, get a list:
    ABCList<string> * list = getList();

    // Test "insert"
    cout << "Let's populate the list with a few items." << endl;
    for (int i = 1; i <= TEST_SIZE; i++) {
        int pos = getPos(i); // Randomise "i" to test
        string input;

        cout << "Enter a word to place into the list at position " << pos << ": ";
        cin >> input;

        try {
            list->insert(pos, input);
            cout << "Successfully inserted at position " << pos << "." << endl;
        }
        catch (int e) {
            cout << "*** Error inserting at position " << pos << " ***" << endl;
        }
}


    // Test "retrieve" & "getLength"
    cout << "List is as follows: \n\t";
    for (int i = 1; i <= list->getLength(); i++) {
        cout << list->retrieve(i) << " ";
    }
    cout << endl;


    // Test "delete" and "isEmpty"
    for (int i = 1; i <= 3 && ! list->isEmpty(); i++) {
        cout << "Deleting item " << i << "." << endl;
        try {
            cout << "Deleted item " << list->remove(1) << endl;
        }
        catch (int e) {
            cout << "*** Error deleting from position " << i << " ***" << endl;
        }
    }

    // Done. Let the destructor handle the rest.
    delete list;

    return 0;
}
4

2 回答 2

2

在删除期间，您在获得项目后执行此操作(1)（这实际上是项目在a[0]：

for (int i = pos + 1; i <= size; i++)
    a[i] = a[i+1];

现在pos输入这个是什么时候？是的(1)，所以你正在将列表从(2)到size，将所有内容从3..(size+1)到2...(size)。“位置” 1 处的项目（同样，它实际上位于0数组中的插槽中，永远不会被覆盖，因此它始终是报告的返回项目。

这不仅是不正确的，而且当阵列完全填充时，它也是 UB（未定义的行为），您将在最后一个可行位置之后的一个插槽中访问数据。

您想在 处丢弃该项目pos，这是基于 1 的（您的设计；不是我的）。它的底层元素位于a[pos-1]数组中的位置。所以试试这个：

for (int i = pos; i < size; ++i)
    a[i-1] = a[i];

如果您检查以确保始终或更大，这应该是安全的（实际上，您似乎这样做了）。就我个人而言，我会坚持使用从零开始的索引系统，但我敢肯定，你有你的设计原因。pos1

于 2012-12-24T19:42:02.953 回答
1

在 remove 方法中，您错误地向下移动了一个索引。它应该是这样的：

for (int i = pos + 1; i <= size; i++)
    a[i-1] = a[i]; // instead of a[i] = a[i+1];

另一种方式可能是

for (int i = pos; i <= size; i++)
    a[i] = a[i+1];

请检查它是否有效。

于 2012-12-24T19:46:50.777 回答