提问者:小点点

单链表查找max,min


**这是一个单链表,教授想让我2从单链表的定义极限中找出max min(类似的2找数组,但用单链表代替),然而当我想要2时,移除单链表中的数字,即使我没有完成它,它被击中这里是我的代码,谢谢你的贡献,我是一个新手,我不知道很多事情,只是一个大学生。 菜单前的数字是单个链表可以容纳多少个数字**

# include<bits/stdc++.h>
using namespace std;
class Node
{
public:
    int n; 
    Node*next;
};
bool isEmpty(Node*head)
{
    if (head==NULL)return true;
    else return false;
}
char menu()
{
    char choice;
    cout<<"Menu\n";
    cout<<"1.Add an item.\n";
    cout<<"2.Remove an item.\n";
    cout<<"3.Show The List.\n";
    cout<<"4.Exit.\n";
    cin>>choice;
    return choice;
}
void insert(Node*&head,Node*&last,int n) 
{
    Node*node = new Node(); // allocate memory 2 node let node be an abstract data
    node->n = n; // define data in the new node as new data (saving data define in there)
    node->next = NULL; // Let next of the new node as head
    head = node; // let pointer name head point new node
    last = node;
}
void append(Node*&head,Node*&last,int n)
{ 
    if(isEmpty(head)) insert(head,last,n);
    else
    {  
    Node*node = new Node(); // allocate memory 2 node let node be abstract data
    node->n = n; // define data in the new node as new data (saving data define in there)
    node->next = NULL; // This new node is going to be the last node, so make next of it as NULL
    last->next = node; // Change the next of last node
    last = node;
    }
}
void remove(Node*&head,Node*&last)
{
    if(isEmpty(head))cout<<"The List is Empty.\n";
    else if (head==last)
    {
        delete head;
        head == NULL;
        last == NULL;
    }
    else
    {
        Node *node=head;
        head =head->next;
        delete node;
    }
}
void print(Node*node) // Function Prints Content of the singly linked list
{ 
    if(isEmpty(node))cout<<"The list is empty\n";
    else
    {
    cout << "The List contains: \n";
    while (node!= NULL) 
    { 
        cout<<node->n<<endl; 
        node = node->next; 
    }
    }
} 
int main()
{
    Node* head = NULL; // Start with empty List
    Node* last = NULL;
    char choice;int i,n,x;
    cin>>x;
    for(i=0;i<x;i++)
    {
    choice = menu();
    switch(choice)
    {
        case '1': cout<<"Please enter a number: ";
                  cin>>n;
                  append(head,last,n);
                  break;
        case '2': remove(head,last);
                  break;
        case '3': print(head);
                  break;
        default: cout<< "System exit\n";
    } 
    } while(choice!='4'); return 0;
}

**Reality Output:3(这是单链表可以容纳的数据量)菜单

  1. 添加项目。
  2. 删除项目。
  3. 显示列表。
  4. 退出。 1请输入数字:22 menu
  5. 添加项目。
  6. 删除项目
  7. 显示列表。
  8. 退出。 1请输入数字:12 menu
  9. 添加项目。
  10. 删除项目
  11. 显示列表。
  12. 退出。 2
  • (光标不能做任何事情,只能在空白的黑色输出上闪烁)预期的输出3菜单
  1. 添加项目。
  2. 删除项目。
  3. 显示列表。
  4. 退出。 1请输入数字:22 menu
  5. 添加项目。
  6. 删除项目
  7. 显示列表。
  8. 退出。 1请输入数字:12 menu
  9. 添加项目。
  10. 删除项目
  11. 显示列表。
  12. 退出。 2菜单
  13. 添加项目。
  14. 删除项目
  15. 显示列表。
  16. 退出。 3列表包含12个菜单
  17. 添加项目。
  18. 删除项目
  19. 显示列表。
  20. 退出。 1请输入数字:22 menu
  21. 添加项目。
  22. 删除项目
  23. 显示列表。
  24. 退出。 1请输入数字:34 menu
  25. 添加项目。
  26. 删除项目
  27. 显示列表。
  28. 退出。 3列表包含12 22 34 Max=34 Min=12

附注。 我很感谢每个来回答这个问题的人,因为我试了两天这个问题对我来说太重了


共2个答案

匿名用户

第一个错误

    delete head;
    head == NULL;
    last == NULL;

应该是

    delete head;
    head = NULL;
    last = NULL;

使用==进行比较,使用=进行分配。

编译器确实应该警告您,像head==null;这样的语句什么也不会实现。 因此,要么您需要注意编译器给出的WANRING(您应该更改代码直到没有编译器警告),要么如果编译器没有警告您,那么您没有正确使用编译器。 所有编译器都有选项,这些选项会导致它们对类似这样的可疑代码发出警告。 如果您的编译器没有警告您这类代码,那么您应该花时间找出如何使它这样做。 这样做总比浪费两天时间去修复编译器可能会告诉你的问题要好。

第二个错误与列表无关。 main中的循环不正确。 如果正确地缩进代码,您可以更好地看到这些内容。 你应该一直这样做,这样可以节省时间。 这是正确缩进的代码。

cin>>x;
for(i=0;i<x;i++)
{
    choice = menu();
    switch(choice)
    {
    case '1': 
        cout<<"Please enter a number: ";
        cin>>n;
        append(head,last,n);
        break;
    case '2':
        remove(head,last);
        break;
    case '3':
        print(head);
        break;
    default:
        cout<< "System exit\n";
    } 
}
while(choice!='4');

现在看看末尾的while循环。 它看起来像是在结束上面的for循环,但是没有for...while循环这样的东西。 相反,这是一个完全独立于前面的for循环的循环。 它只是永远循环(因为choice不等于“4”,循环永远不会更改任何内容)。 这就是为什么你的代码似乎冻结了。 下面是代码的样子。

do
{
    choice = menu();
    switch(choice)
    {
    case '1': 
        cout<<"Please enter a number: ";
        cin>>n;
        append(head,last,n);
        break;
    case '2':
        remove(head,last);
        break;
    case '3':
        print(head);
        break;
    default:
        cout<< "System exit\n";
    } 
}
while(choice!='4');

我将两个循环(for后跟while)更改为一个do.。。while循环,并去掉了没有任何作用的x变量。 我猜您一直想编写一个do.。。while循环,但对语法感到困惑。

总体来说,代码相当不错。 你似乎比许多新手更了解指针。 特别是第二个错误非常不寻常,很难发现。 您可能应该研究一下如何使用调试器。 使用调试器很容易找到这样的bug。

匿名用户

对于初学者来说,声明类节点没有太大意义

class Node
{
public:
    int n; 
    Node*next;
};

使其所有数据成员公共,然后定义独立函数,而不是定义类成员函数。

类节点应该是类列表的一个内部类,它包含指向列表开头和结尾的两个指针,因为您试图定义一个双面单链接列表。

类似于

class List
{
private:
    struct Node
    {
        int value;
        Node *next;
    } *head = nullptr, *tail = nullptr;

public:
    List() = default;
    List( const List & ) = delete;
    List & operator =( const List & ) = delete;
    
    void push_front( int value )
    {
        head = new Node { value, head };
        if ( !tail ) tail = head;
    }
    
    void push_back( int value )
    {
        Node *new_node = new Node { value, nullptr };
        
        if ( tail )
        {
            tail = tail->next = new_node;
        }
        else
        {
            head = tail = new_node;
        }
    }
    
    bool empty() const { return head == nullptr; }
    
    void pop_front()
    {
        if ( head )
        {
            delete std::exchange( head, head->next );
            if ( !head ) tail = nullptr;
        }
    }

    // and so on.
};

函数insert在编写时也没有意义,因为它忽略了这样一个事实,即由于这些语句,列表可以包含已有节点。

node->next = NULL; // Let next of the new node as head
head = node; // let pointer name head point new node
last = node;

最好编写一个类似push_front的函数,该函数可以定义为

void push_front( Node * &head, Node * &last, int n ) 
{
    head = new Node { n, head };

    if ( !last )
    {
        last = head;
    }
}

最好将函数append重命名为push_back。 该函数可以看起来像

void push_back( Node * &head, Node * &last, int n )
{ 
    if ( isEmpty( head ) ) 
    {
        push_front( head, last, n );
    }
    else
    {
        last = last->next = new Node { n, nullptr };  
    }
}

函数remove表现为函数pop_front。 因此重命名它,函数将不会输出任何消息。 它是函数的用户应该决定是否输出任何消息。 该函数有几个bug。

对于初学者,它使用比较运算符而不是赋值运算符

    head == NULL;
    last == NULL;

如果列表只包含一个被删除的节点,那么函数会忘记将指针last设置为NullPtr。

else
{
    Node *node=head;
    head =head->next;
    delete node;
}

该函数可以按以下方式定义

bool pop_front( Node * &head, Node * &last )
{
    bool success = not isEmpty( head );

    if ( success )
    {
        Node *node = head;
        head = head->next;
   
        delete node;

        if ( !head ) last = head;
    }

    return success;
}

这一结构主要

for(i=0;i<x;i++)
{
    //...
} while(choice!='4'); return 0;

是不正确的。 使用for循环没有任何意义使用do while循环

do
{
    //...
} while(choice!='4'); 

return 0;

标签default下的语句没有意义

default: cout<< "System exit\n"

最好写成例子

default: 
    cout<< "Incorrect choice. Try again.\n";
    break;