поиск минимального, максимального и среднего значения связанного списка

Question

У меня есть программа, в которой я должен создавать функции, используя связанные списки для выполнения различных задач. В настоящее время у меня возникла проблема с поиском минимального и максимального значения связанного списка. По какой-то причине, когда оба значения оказываются самыми высокими, то есть di git, равным 9, и когда я пытаюсь найти среднее значение в списке, оно все равно выходит как 9.

. Кроме того, я думаю, что это мешает моей поп-функции, которая должна удалить последний элемент, но когда я пытаюсь обработать его по разделам, одна часть не будет работать, пока предыдущий раздел не будет запущен по любой причине.

вот мой заголовок

#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;
}

единственные части, с которыми я действительно борюсь, это max, min и mean вместе с получить мою функцию поп на самом деле инициировать. Я знаю, что функция pop написана правильно, но с тех пор, как я установил максимум и минимум, она теперь не будет работать.

Answer 1

В коде я обнаружил несколько ошибок, и у меня есть несколько замечаний по этому поводу:

1. Вы должны использовать пробелы и более последовательно. Есть места без достаточного расстояния и места с слишком большим количеством пустых строк!
2. Если у вас есть две функции, такие как insert и append или pop и remove, они должны использовать друг друга, это означает, что append это просто insert(0) (обратите внимание, как я изменил его в коде).
3. Вы используете двойные циклы, когда это не имеет смысла (это не ошибка, но это ошибка!).
4. В функции max вы выполняли неправильное сравнение, спрашивая, является ли max больше текущего значения ...
5. Вы никогда не вернете значение из min и max, что должно как минимум создать предупреждение в процессе компиляции!
6. Вы создавали пустые узлы, а затем просто помещали разные значения в их указатели, что означает, что эта новая память была все еще выделены (поскольку не было delete), но больше не было возможности получить к ним доступ (это утечка памяти).
7. Самая большая ошибка из всех - Когда вы l oop в функциях min и max, вы меняете head списка, что является серьезной ошибкой (и именно поэтому вы получили ошибки после с использованием этой функции). Решение - простой, но важный урок в C ++ - Const Correctness .

Что такое const правильность и почему это важно?

Если у вас есть функция, которая не изменяет состояние вашего объекта, она должна быть объявлена ​​const. Это наш способ сказать компилятору (и другим программистам), что он не должен изменять состояние нашего объекта. Например, min, max и average являются функциями classi c const - они просто делают вычисления, которые не изменяют список, и возвращают. Если бы вы написали const в их объявлении, компиляция не удалась бы, поскольку вы на самом деле изменили список (изменив заголовок), хотя вы не должны этого делать!

Кроме того, при получении объектов в функцию по возможности следует указывать const T&, где T - это тип. Они заставят вас использовать только const функции этого типа.

Также я предлагаю компиляцию (по крайней мере, на g++) с флагами -Wpedantic -Werror'. The first adds some warnings about ISO C++ standards and the second makes all warnings into errors (and thus, your min , max and mean `не должен компилироваться, так как они не возвращают значение).

Вот код:

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;
}