-4

作为 C++ 的新手，我正在尝试了解为什么以及在何处使用 New。所以我试图在这个链接列表示例中不使用新的，

////////////////////////////////////////////////////////////////
struct link //one element of list
{
    int data; //data item
    link* next; //pointer to next link
};
////////////////////////////////////////////////////////////////
class linklist //a list of links
{
private:
    link* first; //pointer to first link
public:
    linklist() //no-argument constructor
    { first = NULL; } //no first link
    void additem(int d); //add data item (one link)
    void display(); //display all links
};
//--------------------------------------------------------------
void linklist::additem(int d) //add data item
{
    link* newlink = new link; //make a new link
    newlink->data = d; //give it data
    newlink->next = first; //it points to next link
    first = newlink; //now first points to this
}
//--------------------------------------------------------------
void linklist::display() //display all links
{
    link* current = first; //set ptr to first link
    while( current != NULL ) //quit on last link
    {
        cout << current->data << endl; //print data
        current = current->next; //move to next link
    }
}
////////////////////////////////////////////////////////////////
int main()
{
    linklist li; //make linked list
    li.additem(25); //add four items to list
    li.additem(36);
    li.additem(49);
    li.additem(64);

    return 0;
}

到以下：

 ////////////////////////////////////////////////////////////////
struct link //one element of list
{
    int data; //data item
    link* next; //pointer to next link
};
////////////////////////////////////////////////////////////////
class linklist //a list of links
{
private:
    link first; //pointer to first link
public:
    linklist() //no-argument constructor
    { first = NULL; } //no first link
    void additem(int d); //add data item (one link)
    void display(); //display all links
};
//--------------------------------------------------------------
void linklist::additem(int d) //add data item
{
    link newlink; //make a new link
    newlink.data = d; //give it data
    newlink.next = first; //it points to next link
    first = newlink; //now first points to this
}
//--------------------------------------------------------------
void linklist::display() //display all links
{
    link current = first; //set ptr to first link
    while( current != NULL ) //quit on last link
    {
        cout << current.data << endl; //print data
        current = current.next; //move to next link
    }
}
////////////////////////////////////////////////////////////////
int main()
{
    linklist li; //make linked list
    li.additem(25); //add four items to list
    li.additem(36);
    li.additem(49);
    li.additem(64);
    return 0;
}

但这不起作用。在我继续尝试之前，我想知道这个特定的示例是否必须坚持使用 New 并且如果不使用它就无法完成。

4

6 回答 6

2

如果没有动态内存分配或某种形式的动态内存分配，就无法创建链表new，因为您无法在堆栈上创建指向永久节点的永久节点。

但是，幸运的是您不必自己编写容易出错的new代码，因为 C++ 已经为您提供了一个方便的std::list类。此外，它还提供了 C++11 中的单链接forward_list。

于 2013-06-10T16:38:39.457 回答
2

我认为您不了解堆栈内存与堆内存。你应该做的就是所谓的“动态分配”。

如果您在仅在堆栈上创建它时定义一个变量link newlink; ，这意味着当您退出函数时它不再存在，它被“释放”。该列表需要的是请求一个新的内存区域，当你完成你的函数时它不会被释放。为此，您需要使用动态分配。执行此操作的方法之一是new操作员。另一种规范的做法是 malloc 函数。

TL;DR 你不能按照你想要的方式去做，你似乎误解了内存在 C\C++ 中是如何工作的。你必须使用指针和动态分配，这就是他们称之为动态链表的原因。

此外，不要使用 std:list 作为您的问题，并且您编写代码的方式向我指出，链表实现是一种家庭作业。在运行到其他人的实现之前学习了解基本功能。

于 2013-06-10T16:40:28.640 回答
0

通过这个动作

first = newlink;

您在旧数据上记录数据。

在上面的每个操作中，您只有一个linklist类字段并覆盖数据。

当你使用new时，它会在堆中（外部linklist）分配实例，这些实例（link）通过指针相互连接。在您的第二段代码中它没有发生，并且您在内存中只有一个link.

于 2013-06-10T16:37:48.470 回答
0

链表本质上是单个动态分配的块的集合，因此new 无论它是否暴露给客户端代码都是一种需求。正如@Alok 所建议的那样， astd::list更可取，因为它封装了此内存分配并确保不会发生泄漏等。除非您获取其地址，否则您在堆栈上分配的尝试newLink将编译失败，您当然不想这样做（ asnewLink将在函数返回后立即从堆栈中弹出）。

于 2013-06-10T16:39:50.397 回答
0

当你说

link newlink; //make a new link

您在堆栈上创建了一个链接，该链接将在函数结束时超出范围。

我认为您应该使用“避免原始指针”规则，而不是避免使用新指针。如果您改用 std::make_shared 并持有 std::unique_ptr 而不是原始指针，这可能是一个有用的学习练习。

于 2013-06-10T16:54:58.730 回答
0

要解决您的问题，您必须首先了解以下内容：

堆栈

有许多文档深入解释了堆栈是什么。但是非常简化的堆栈内存是仅在 c++ 范围内可用的临时内存。举例：

int* p;
{
   int a; //Create a variable in stack memory
   a = 10; //Assing stack memory
   p = &a; //Create a pointer to stack memory
} //Variable a is released since the scope has ended

printf("%d",*p); //The pointer now points to released memory. Probably it will not be 10

这同样适用于函数，因此：

void suma()
{
    int a; //This variable will only exists for this function
}

你的代码

您正在做的是创建和复制稍后将在函数结束时释放的变量。

link first; //pointer to first link

void linklist::additem(int d) //add data item
{
    link newlink; //I'll only exists in this function
    newlink.data = d; 
    newlink.next = first; //Does even this compiles???
    first = newlink;  //After the function sends first will point to a released memory. Aren't you missing a & operator ? &newlink
}

解决方案

您需要将链接节点存储在某处。新运营商会为您做到这一点。但是如果你不想使用它。您可以将其存储在静态内存中。

例如，您可以有两个像这样的静态变量：

link staticLinks[100];
int lastUsedLink = 0;

在程序的整个执行过程中不会释放此内存，因此您可以执行以下操作：

void linklist::additem(int d) //add data item
{
    staticLinks[lastUsedLink].data = d; //Now this data will no dissapear
    lastUsedLink[lastUsedLink].next = first; //Point to the last element
    first = &lastUsedLink[lastUsedLink]; //No this becomes the last element
    lastUsedLink++; //Use the next element of the array for the next addition
}

这是非常可改进的。例如，您可以添加一个守卫以避免使用 101 个或更多的数组元素。但现在你可能明白问题所在了。

完整代码##

////////////////////////////////////////////////////////////////
struct link //one element of list
{
    int data; //data item
    link* next; //pointer to next link
};

link staticLinks[100];
int lastUsedLink = 0;

////////////////////////////////////////////////////////////////
class linklist //a list of links
{
private:
    link* first; //pointer to first link
public:
    linklist() //no-argument constructor
    { first = NULL; } //no first link
    void additem(int d); //add data item (one link)
    void display(); //display all links
};
//--------------------------------------------------------------
void linklist::additem(int d) //add data item
{
    staticLinks[lastUsedLink].data = d; //give it data
    lastUsedLink[lastUsedLink].next = first; //it points to next link
    first = &lastUsedLink[lastUsedLink]; //now first points to this
    lastUsedLink++;
}
//--------------------------------------------------------------
void linklist::display() //display all links
{
    link current = first; //set ptr to first link
    while( current != NULL ) //quit on last link
    {
        cout << current.data << endl; //print data
        current = current.next; //move to next link
    }
}
////////////////////////////////////////////////////////////////
int main()
{
    linklist li; //make linked list
    li.additem(25); //add four items to list
    li.additem(36);
    li.additem(49);
    li.additem(64);
    return 0;
}
于 2013-06-10T17:00:25.690 回答