使用c ++语言的双向链表 [英] two way linked list using c++ language

问题描述

#include<iostream>
#include<cstring>
using namespace std;

struct node
{
    int a;
    node *previous;
    node *next;
};

 struct node *head=NULL;
 struct node *tail=NULL;

int insert_in_first()
{
    node *tmp=new node;
    cout<<"\ninput a.\n";
    cin>>tmp->a;
        if(head==NULL)
        {
            tmp->next=NULL;
            tmp->previous=NULL;
            head=tmp;
            tail=head;
        }
        else
        {
            tmp->next=head;
            tmp->previous=NULL;
            head->previous=tmp;
            head=tmp;
        }
        return 0;
}

int traverse_form_head()
{
    node *tmp=new node;
    tmp=head;
    if (tmp==NULL)
    {
        cout<<"\nnothing for traverse\n";
        return 0;
    }
    while(tmp!=NULL)
    {
        cout<<"a="<<tmp->a<<"\n";
        tmp=tmp->next;
    }
    return 0;
}


int traverse_form_tail()
{
    node *tmp=new node;
    tmp=tail;
    if (tmp==NULL)
    {
        cout<<"\nnothing for traverse\n";
        return 0;
    }
    while(tmp!=NULL)
    {
        cout<<"a="<<tmp->a<<"\n";
        tmp=tmp->previous;
    }
    return 0;
}

int insert_at_last()
{
    node *tmp=new node;
    node *tmp1=new node;
    tmp=tail;
    if (tmp==NULL)
    {
        cout<<"\nthere is no element\n";
        return 0;
    }
    else
    {
        cout<<"\nimput a\n";
        cin>>tmp1->a;
        tmp1->next=NULL;
        tmp1->previous=tmp;
        tmp->next=tmp1;
        tmp=tmp1;
    }
    return 0;
}


int main()
{
    int i;
    do
    {
        cout<<"\nimput 1 for first insert\ninput 2 for traverse from head\ninput 3 for traverse from tail\ninput 4 for last insert\ninput 9 for break\n";
        cin>>i;
        switch(i)
        {
            case 1:
            insert_in_first();
            break;
            case 2:
            traverse_form_head();
            break;
            case 3:
            traverse_form_tail();
            break;
            case 4:
            insert_at_last();
            break;

            case 9:
            break;

        }
    }
    while (i!=9);
    return 0;
}

我输入3个节点，其中前2个节点用于第一个插入，最后一个节点用于最后一个插入。然后我显示遍历表单头，它是正确的但是当我显示traverse form tail时，最后一个节点丢失了。为什么？

I input 3 node which first 2 node is for first insert and last node is for last insert .then i show traverse form head and it was right but when i show traverse form tail there was a missing of last node. why?

推荐答案

您似乎认为必须使用new分配一个新对象来初始化指针：

You seem to be under the impression that you have to allocate a new object with "new" to initialize a pointer:

int insert_at_last()
{
    node *tmp=new node; // <------ this is wrong
    node *tmp1=new node;
    tmp=tail;

你只想写：

You just wanted to write:

int insert_at_last()
{
    node *tmp=tail;
    node *tmp1=new node;

但即便如此也是不必要的。你已经有一个尾指针。为什么要将它分配给tmp指针？



下一行代码也是错的：

But even that is unneccessary. You have already a tail pointer. Why assign it to a tmp pointer?

The next lines of code are also wrong:

if (tmp==NULL)
{
    cout<<"\nthere is no element\n";
    return 0;
}

如果tmp（在这种情况下指向尾节点）为NULL，则列表为empy。为什么不能将节点插入空队列。



我的建议：比较函数insert_at_first和insert_at_last。它们应该是完全对称的。双链表中的所有其他内容都是对称的，因此在列表的开头和结尾插入的代码应该是。

If tmp (which points to the tail node in that case) is NULL the list is empy. Why can't you insert a node into an empty queue.

My suggestion: Compare the function insert_at_first and insert_at_last. They should be totally symmetrical. All else in your double linked list is symmetrical, so should the code for insert at the begin and end of the list be.

如果您不知道调试的含义和使用方法然后调试器开始以最高优先级了解它。如果您正在使用Windows，请使用 Visual Studio [ ^ ]作为您的IDE（链接快递版本）是免费的） - 在我看来它是地球上最好的C ++开发环境，它集成了一流的代码编辑器和调试器。如果您使用的是Linux，我建议您使用代码::阻止 [ ^ ]作为您的IDE - 这是一个非常好的，免费的，开源的，多平台软件，支持许多平台上的许多编译器（包括gcc）。



安装以前的一个IDE并搜索您选择的IDE的调试教程。为了能够选择一个好的教程，我简单地描述了调试中最有用的东西：

您可以在启动前使用所谓的断点标记一些代码行来使用调试器你的计划。如果程序的执行在其中一个断点上运行或发生致命错误（崩溃），则调试器会暂停程序的执行，并允许您检查/修改程序/变量的状态。

结账时最重要的观点：

- 调用堆栈：显示您在当前线程上执行的函数调用堆栈

- watch / autos view / tooltip：帮助您读取/修改全局/本地/成员变量的值



当您完成程序状态检查后，您可以发出以下命令操作：

- 继续执行程序直到另一个断点被击中。

- 您可以通过输入函数告诉调试器执行单行代码（步入）或者不输入它们（跳过）



其他提示：

- 一个好的调试器可以让你随时暂停程序执行但是这个不是很有用，通常你想只在标有断点的特定点停止。

- 在一个好的调试器中，你可以随时放置断点但这通常（并且实际上）在启动调试应用程序之前或当应用程序被暂停时完成击中断点。



许多人都懒得发现未知的调试器。可惜的是，在我的（汇编）编程之旅的前1-2年里，我既没有使用过IDE也没有调试器（因为我不知道存在这样的事情）。使用IDE和调试器可以从根本上缩短学习曲线，有助于理解正在运行的程序/进程中的内容，而不必去论坛上让人们调试出简单/明显崩溃的原因。在没有调试器的情况下找到崩溃的原因通常是不可能的，而同样的崩溃通常非常容易使用调试器捕获。



您接下来的步骤：安装并设置/与我提到的IDE之一建立联系，然后学习如何在其中进行调试。

If you don't know what debugging means and how to use a debugger then start learning about about it with highest priority. If you are working on windows then use Visual Studio[^] as your IDE (the linked express version is free) - its the best C++ dev env on Earth in my opinion with a superb code editor and debugger integrated together. If you are on linux then I recommend using Code::Blocks[^] as your IDE - this one is a very good, free, opensource, multiplatform software supporting many compilers on many platforms (including gcc).

Install one of the previous IDEs and search for a debugging tutorial for the IDE of your choice. In order to be able to choose a good tutorial I describe in a nutshell the most useful things involved in debugging:
You use the debugger by marking some of the code lines with so called "breakpoints" before starting your program. If the execution of your program runs on one of these breakpoints or a fatal error happens (crash) then the debugger suspends the executions of your program and allows you to inspect/modify the state of your program/variables.
The most important views when checking out things:
- Call stack: shows the stack of function calls you are executing on the current thread
- watch/autos view/tooltip: helps you to read/modify the value of global/local/member variables

When you are done with checking out the state of your program you can issue the following operations:
- continue program execution until another breakpoint is hit.
- you can tell the debugger to execute a "single line of code" by entering functions (step in) or without entering them (step over)

Other hints:
- A good debugger allows you to pause program execution at any time but this is not very useful, usually you want to stop only at specific points marked with breakpoints.
- In a good debugger you are allowed to place breakpoints anytime but this is usually (and practically) done before starting the debugged application or when the application is suspended because of hitting a breakpoint.

Many people are lazy to discover the unknown like the usage of a debugger. Its a pity that I have used neither an IDE nor a debugger in the first 1-2 years of my (assembly) programming journey (because I didn't know that such thing exists). Using an IDE and a debugger shortens your learning curve radically, helps in understanding whats goin on inside a running program/process, and you don't have to go to forums to ask people to debug out the reason of your simple/obvious crashes. Finding the reason for a crash if often impossible without a debugger while the same crash is often very-very easy to catch using a debugger.

Your next steps to take: Install and setup/befriend one of the IDEs I've mentioned and then learn how to debug in it.

这篇关于使用c ++语言的双向链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！