查找链表的最小值，最大值和平均值

问题描述 投票：-1回答：1

我有一个程序，应该在其中使用链接列表构建函数来执行各种任务。目前，我在查找链表的最小值和最大值时遇到问题。由于某些原因，当两者都成为最高的那个数字9时，并且当我尝试查找列表的平均值时，它仍然是9。

另外，我认为这会干扰应该删除最后一项的pop函数，但是当我尝试按节进行操作时，无论出于何种原因，直到上一节开始运行之前，只有一个部分无法工作。

这是我的标题

#include <iostream>

using std::cout;
using std::endl;

#ifndef LINKEDLIST_H
#define LINKEDLIST_H


class LinkedList
{
    private:

        struct Node
        {
            int data;
            Node *next;
        };

        int size;
        Node *head, *tail;

    public:
        LinkedList();
        ~LinkedList();

        // misc
        void display();

        // sorting and searching
        // reverse --> sorting in descending
        int linearSearch(int key);
        void sort();
        void reverse();

        // various math
        int min();
        int max();
        int mean();

        // adding
        void append(int num);
        void insert(int num, int pos);

        // removing
        void pop();
        void remove(int pos);
};

#endif // LINKEDLIST_H

标题的源文件

#include "linkedlist.h"



LinkedList::LinkedList()
{
    head = nullptr;
    tail = nullptr;
    size = 0;
}

LinkedList::~LinkedList()
{
    if(head != nullptr)
    {
        Node *temp;

        while(head != nullptr)
        {
            temp = head->next;

            // deletes head
            delete head;

            // goes to next element
            head = temp;
        }
    }
}

void LinkedList::display()
{
    Node *temp = head;

    for(int i = 0; i < size; i++)
    {
        cout << temp->data << "\t";

        temp = temp->next;
    }

    cout << endl;
}

void LinkedList::append(int num)
{
    // list is empty
    if(head == nullptr)
    {
        head = new Node;

        head->data = num;
        head->next = nullptr;

        // sets tail to head
        tail = head;
    }

    else
    {
        // creates new node
        Node *temp = new Node;

        // sets new node data
        temp->data = num;
        temp->next = nullptr;

        // sets previous tail link to new node
        tail->next = temp;

        // sets this node to new tail
        tail = temp;
    }

    // increments size
    size++;
}

void LinkedList::pop()
{
    if(size > 1)
    {
        Node *temp = head;

        // loops to node before tail
        while(temp->next->next != nullptr)
        {
            temp = temp->next;
        }

        // deletes tail
        delete tail;

        // sets new tail
        tail = temp;
        tail->next = nullptr;
    }

    // if there's only one item
    else if(size == 1)
    {
        Node *temp = tail;

        // head and tail are now null
        head = nullptr;
        tail = nullptr;

        // deletes node
        delete temp;
    }

    size--;
}



void LinkedList::insert(int num, int pos)
{
    if(pos ==0)
    {

        Node *temp=new Node;
        temp->data=num;
        temp->next=head;
        head=temp;
    }

    if(pos>1)
    {
        Node *pre=new Node;
        Node *cur=new Node;
        Node *temp=new Node;
        cur=head;
        for(int i=1;i<pos+1;i++)
        {
          pre=cur;
          cur=cur->next;
        }
        temp->data=num;
        pre->next=temp;
        temp->next=cur;
    }



    size++;

}

int LinkedList::linearSearch(int key)
{
    Node *temp = head;
    for(int i = 0; i < size; i++)
    {
        if(temp->data == key)
        {
            return i;
        }

        temp = temp->next;
    }

    return -1;
}

int LinkedList::max()
{
    int max = INT_MIN;
    for(int i = 0; i < size; i++)
    {
        while (head != NULL)
        {
                if (head->data < max)
                    max = head->data;
                head = head->next;

        }

     }

}

int LinkedList::min()
{
    int min = INT_MAX;
    for(int i = 0; i < size; i++)
    {
        while (head != NULL)
        {
                if (head->data < min)
                    min = head->data;
                head = head->next;

        }

     }
}

void LinkedList::reverse()
{
    Node* temp = head;

    // Traverse the List
    while (temp) {
        Node* min = temp;
        Node* r = temp->next;

        // Traverse the unsorted sublist
        while (r)
        {
            if (min->data < r->data)
                min = r;

            r = r->next;
        }

        // Swap Data
        int x = temp->data;
        temp->data = min->data;
        min->data = x;
        temp = temp->next;
    }
}

void LinkedList::remove(int pos)
{
    Node *temp = head;

    if(pos ==0)
    {

        head = temp->next;
        free(temp);
    }

    if(pos>1)
    {
       for(int i=0; temp!=NULL && i<pos-1;i++)
       {
           temp=temp->next;
       }

       temp->next = temp->next->next;
       free(temp->next);
       temp->next = temp->next;
    }



    size--;
}

int LinkedList::mean()
{


        int sum = 0;
        float avg = 0.0;

         Node *temp = head; 
        while (head != NULL)
        {

            sum += temp->data;
            temp = temp->next;
        }

        // calculate average
        avg = (double)sum / size;
}

void LinkedList::sort()
{
    Node* temp = head;

    // Traverse the List
    while (temp) {
        Node* min = temp;
        Node* r = temp->next;

        // Traverse the unsorted sublist
        while (r) {
            if (min->data > r->data)
                min = r;

            r = r->next;
        }

        // Swap Data
        int x = temp->data;
        temp->data = min->data;
        min->data = x;
        temp = temp->next;
    }
}

和主要

#include <iostream>

#include "linkedlist.h"

using namespace std;

int main()
{
    LinkedList nums;

    // adding through append
    nums.append(8);
    nums.append(6);
    nums.append(7);
    nums.append(8);
    nums.append(0);
    nums.append(9);

    // displays list
    cout << "List after append: " << endl;
    nums.display();
    cout << endl;

    // adding through insert
    nums.insert(1, 0);
    nums.insert(5, 4);
    nums.insert(3, 8);


    // displays list
    cout << "List after inserting: " << endl;
    nums.display();
    cout << endl;

    // testing searching
    cout << "Testing linear search:" << endl;

    int pres = nums.linearSearch(7);

    if(pres < 0)
    {
        cout << "7 is not present in the list." << endl;
    }

    else
    {
        cout << "7 can be found at location " << pres << endl;
    }

    pres = nums.linearSearch(5);

    if(pres < 0)
    {
        cout << "5 is not present in the list." << endl;
    }

    else
    {
        cout << "5 can be found at location " << pres << endl;
    }

    cout << endl;

    // does math
    cout << "Minimum, maximum, and average before removing any items: " << endl;
    cout << "Min: " << nums.min() << endl;
    cout << "Max: " << nums.max() << endl;
    cout << "Mean: " << nums.mean() << endl << endl;

    // displays items reversed
    cout << "Items reversed: " << endl;
    nums.reverse();
    nums.display();
    cout << endl;

   // removing through pop
    nums.pop();
    nums.pop();

    // displays list
    cout << "List after popping: " << endl;
    nums.display();
    cout << endl;

    // removing through remove
    nums.remove(0);
    nums.remove(2);
    nums.remove(4);

    // displays list
    cout << "List after removing: " << endl;
    nums.display();
    cout << endl;

   // displays items sorted
    cout << "Items sorted: " << endl;
    nums.sort();
    nums.display();
    cout << endl;

    // does math
    cout << "Minimum, maximum, and average after removing items: " << endl;
    cout << "Min: " << nums.min() << endl;
    cout << "Max: " << nums.max() << endl;
    cout << "Mean: " << nums.mean() << endl << endl;

    // testing searching
    cout << "Testing linear search:" << endl;

    pres = nums.linearSearch(7);

    if(pres < 0)
    {
        cout << "7 is not present in the list." << endl;
    }

    else
    {
        cout << "7 can be found at location " << pres << endl;
    }

    pres = nums.linearSearch(5);

    if(pres < 0)
    {
        cout << "5 is not present in the list." << endl;
    }

    else
    {
        cout << "5 can be found at location " << pres << endl;
    }

    return 0;
}

我真正要苦苦挣扎的唯一部分是最大值，最小值和均值，以及使我的pop函数真正启动的过程。我知道pop函数是正确编写的，但是自从我设置了max和min以来，它现在就无法工作了。

c++ linked-list max min
1个回答
0
投票

我在代码中发现了一些错误，对此我有几点评论：

  1. 您应该使用空格，并且更一致。有些地方没有足够的间距，而空白行很少！
  2. [如果您有两个功能，例如insert和append或pop和remove，它们应该互相使用，这意味着append只是insert(0)（请注意，我如何在代码中对其进行了更改）。
  3. 您正在使用没有意义的双循环（这不是一个错误，但这是一个错误！）。
  4. 在函数max中，您进行了错误的比较，询问max是否大于当前值...
  5. 您永远不会从min和max返回值，这至少应该在编译过程中发出警告！
  6. 最大的错误-循环执行min和max函数时，将更改列表的head，这是一个主要错误（这就是使用它后出现错误的原因）。解决方案是C ++中的简单课程-常量正确性。

这里是代码：

class LinkedList
{
    private:

        struct Node
        {
            int data;
            Node *next;

            Node(int data_, Node* next_ = nullptr) :
                data(data_),
                next(next_)
            {
            }
        };

        int size;
        Node *head, *tail;

    public:
        LinkedList();
        ~LinkedList();

        void clear();

        // various math
        int min() const;
        int max() const;
        int average() const;

        // adding
        void append(int data);
        void insert(int data, int pos);

        // removing
        void pop();
        void remove(int pos);
};

LinkedList::LinkedList()
{
    head = nullptr;
    tail = nullptr;
    size = 0;
}

LinkedList::~LinkedList()
{
    clear();
}

void LinkedList::clear()
{
    if (head != nullptr)
    {
        Node *temp;

        while(head != nullptr)
        {
            temp = head->next;

            delete head;

            head = temp;
        }
    }

    head = nullptr;
    tail = nullptr;

    size = 0;
}

void LinkedList::display()
{
    Node *temp = head;

    for(int i = 0; i < size; i++)
    {
        std::cout << temp->data << "\t";

        temp = temp->next;
    }

    std::cout << std::endl;
}

void LinkedList::insert(int data, int pos)
{
    if (pos == 0)
    {
        Node* prev_head = head;
        head = new Node(data, prev_head);

        if (size == 0)
        {
            tail = head;
        }
    }
    else
    {
        Node *pre=nullptr;
        Node *cur = head;

        for(int i = 0 ; i < pos + 1; ++i)
        {
          pre = cur;
          cur = cur->next;
        }

        Node *temp = new Node(data, cur);
        pre->next = temp;
    }

    ++size;
}

void LinkedList::append(int data)
{
    insert(data, 0);
}

void LinkedList::pop()
{
    if (size == 1)
    {
        Node *temp = tail;

        head = nullptr;
        tail = nullptr;

        delete temp;
    }
    else
    {
        Node *temp = head;

        while(temp->next != tail)
        {
            temp = temp->next;
        }

        Node* node_to_pop = tail;

        tail = temp;
        tail->next = nullptr;

        delete node_to_pop;
    }  

    --size;
}

int LinkedList::max() const
{
    int max = INT_MIN;
    for (Node* temp = head; temp != nullptr; temp = temp->next)
    {   
        if (temp->data > max)
        {
            max = temp->data;
        }
    }

    return max;
}

int LinkedList::min() const
{
    int min = INT_MAX;
    for(Node* temp = head; temp != nullptr; temp = temp->next)
    {
        if (head->data < min)
        {
            min = temp->data;
        }
     }

     return min;
}

int LinkedList::average() const
{
    int sum = 0;

    for(Node* temp = head; temp != nullptr; temp = temp->next)
    {

        sum += temp->data;
        temp = temp->next;
    }

    return (double)sum / size;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.