通用连续列表实现 [英] Generic contigous list implementation

问题描述

我试图实现一个连续的列表.现在，这可以很好地编译，但是在尝试使用列表的这种小型插入方法时，条目不会插入列表中.这是主程序中的一个示例:
Main.cpp

Hi,
I was trying to implement a contiguous list. Now, this is compiling well, but on trying this small insert method of list, the entries are not inserted into the list. Here;s an example from the main program:
Main.cpp

#include <iostream>
#include "List.h"
#include "Random.h"
#include "Timer.h"
#include "Key.h"
using namespace std;
int main()
{
    int n;
    List<int> the_list;
    cout<<"Enter the number of records to be stored. "<<endl;
    cin>>n;
    for(int i=1;i<n;i=i+2)//Enter only odd values upo n
    {
    the_list.insert(i,i);//(position, List_entry &x)
    }
    cout<<the_list.size();
    return 0;
}

输出:输入要存储的记录数:
5
0(应该是5)

List.h

Output: Enter the number of records to be stored:
5
0 (which should have been 5)

List.h

const int maxlist=1000;
enum Error_code
{
    success,
    overflow,
    underflow,
    range_error
};
template <class List_entry>
class List
{
    public:
    //List();

    List():count(0)
    {}

    bool empty()
    {
        return count==0;
    }
    bool full()
    {
         return count==maxlist;
    }
    int size()
    {
        return count;
    }
    Error_code insert(int position, const List_entry &x)
    {
        if(full()) 
        {
            return overflow;
        }
        if(position<0 || position>count){ return range_error;}
        for(int i=count-1;i>=position;i++)
        {
            entry[i+1]=entry[i]; 
        }
        entry[position]=x;
        count++;
        return success;
    }
    Error_code retrieve(int position, List_entry &x)const
    {
        if(empty()) return underflow;
        if(position<0 || position>count) return range_error;
        x=entry[position];
        return success;
    }

    Error_code replace(int position, const List_entry &x)
    {
        if(empty()) return underflow;
        if(position<0 || position>count) return range_error;
        entry[position]=x;
        return success;
    }
    Error_code remove(int position, List_entry &x)
    {
        if(empty()) return underflow;
        if(position>0 || position>=count) return range_error;
        for(int i=position;i<=count-1;i++)
        entry[i+1]=entry[i];
        count--;
        return success;
    }

    void traverse(void (*visit)(List_entry &x))//*visit is the      pointer to function which performs operation on list
    {
        for(int i=0;i<count;i++)
        (*visit)(entry[i]);
    }

    protected:
    int count;
    List_entry entry[maxlist];
};

这里出了什么问题?

经过编辑以提高可读性
-Emilio-

What''s going wrong here?

Edited for readability
-Emilio-

推荐答案

在实际插入"之前，您必须先移动内部内容.
但是这里有一个错误

Before to actually "insert", you have to shift what is already inside.
But there is a bug here

for(int i=count-1;i>=position;i++)
{
    entry[i+1]=entry[i];
}

要前进"，您必须向后走(否则，您的脚将被覆盖).您从count-1(最后一个元素)开始，直到下一个插入点，但是...您踏入i++，但它应该是i--.


-建议:除非特别要求，否则使用++ i和--i而不是i ++和i--.除非您使用整数是没有问题的，但是在将来您将使用通用代码和迭代器时，前缀增量会更有效，因为它们不需要复制和销毁.



-认可:您的代码非常基础，远非高效:
尝试寻找一种方法来获得逻辑"列表，其中顺序不一定与物理顺序相同.您可以通过这种方式避免所有转变".

To shift "one advance" you must walk backwardly (otherwise you''ll overwrite your foots). You start at count-1 (last element) to go down to the insertion point but ... you step i++, but it should have been i--.


-Suggestion: unless specifically required, use ++i and --i rather than i++ and i--. Until you work with integers that''s not a problem, but when in future you''ll move to generic code and iterators, prefix increment are more efficient, since they don''t require a copy and destroy.



-Emprovement: Your code is very basic, and it is far from being efficient:
Try finding a way to have a "logic" list where the sequence is not necessarily the same as the physical one. You can this way avoid all the "shifts".

根据您以前的文章，您将从Lakos的Large Scale C ++ Design中学到很多东西.他的书会回答您在codeproject上提出的几个问题.

Based on your prior posts, you will learn a lot from Large Scale C++ Design by Lakos. His book would have answered several of the questions you have asked on codeproject.

我不必全吃鸡蛋来说明它不好，对吗?

因此，在测试样本中，您总是在小于count的索引处插入；返回range_error-即使没有调试器，也可以毫无武装地看到.就这些吗?

好吧，我不想检查所有代码:它不值得.而且这个问题太微不足道了.但是我认为您应该知道代码中的不良之处.几乎所有内容:

I don''t have to eat all the egg to tell it''s bad, right?

So, in your test sample, you always insert at the index less than count; which returns range_error -- quite visible with unarmed eye, even without debugger. Is that all?

Well, I don''t want to examine all the code: it does not deserve it; and the problem is too trivial. But I think you ought to know what''s bad in your code. Nearly everything:

1. maxList是硬编码的；您可以使用limits.h，但这并不是很重要，因为有下一项.
2. maxList和恒定大小的数组很糟糕:您总是在内存中占用整个数组；如果count小于，则不使用它；否则，不使用它.同时容量可能不足.
   您可以改用堆内存.或者，您可以使用在随机位置插入时更好的链表.
3. 如果异常，浪费时间不合时宜，则返回Error_code:您最好改用异常.
4. 为什么所有这些
5. 与include无关的行?
6. 标记为protected的内容应该是私有的(从这一类派生出其他类是没有意义的).
7. traverse根本不灵活.您应该已经实现了迭代器模式；
8. 由于格式不正确，您的代码不可读.
9. 也许，更多...购买就足够了.

1. maxList is hard-coded; you could use limits.h, but this is not so important because of next item.
2. maxList and constant-size array is bad: you always occupy whole array in memory; it is not used if count is less; at the same time the capacity may be not enough.
   You could use heap memory instead; alternatively, you could use linked list which is better with random-position insertion.
3. Returning Error_code if fantastic, wasteful anachronism: you should better use exceptions instead.
4. Why all those irrelevant include lines?
5. What you marked protected should be private (deriving other classes from this one is pointless).
6. traverse is not flexible at all; you should have implemented iterator pattern instead; which is easy enough to do.
7. You code is not readable due to poor formatting.
8. Maybe, more... buy that''s enough.

做学校作业?嗯...

A school assignment? Hm...

这篇关于通用连续列表实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！