Min or max v seznamu – C / C++ – Fórum – Programujte.com

Moc prosím jestli by mi nemohl někdo pomoct s vytvořením funkce na vyhledání největšího nebo nejmenšího prvku v seznamu.

#include <cstdlib>
#include <iostream>

using namespace std;

class List{
private:

    typedef struct node{
        int data;
        node* next;
    }* nodePtr;

    nodePtr head;
    nodePtr curr;
    nodePtr temp;

public:

    List();
    void AddNode(int addData);
    void DeleteNode(int delData);
    void PrintList();

};

List::List(){
    head = NULL;
    curr = NULL;
    temp = NULL;
}

void List::AddNode(int addData){
    nodePtr n = new node;
    n->next = NULL;
    n->data = addData;

    if(head != NULL){
        curr = head;
        while(curr->next != NULL){
            curr = curr->next;
        }
        curr->next = n;
    }
    else{
        head = n;
    }
}

void List::DeleteNode(int delData){
    nodePtr delPtr = NULL;
    temp = head;
    curr = head;
    while(curr != NULL && curr->data != delData){
        temp = curr;
        curr = curr->next;
    }
    if(curr == NULL){
        cout << "Nelze smazat hodnotu " << delData << ", neni v seznamu.\n";
        delete delPtr;
    }
    else{
        delPtr = curr;
        curr = curr->next;
        temp->next = curr;
        if(delPtr == head){
            head = head->next;
            temp = NULL;
        }
        delete delPtr;
        cout << "Hodnota " << delData << " byla smazana.\n";
    }
}

void List::PrintList(){
    curr = head;
    while(curr != NULL)
    {
        cout << curr->data << endl;
        curr = curr->next;
    }
}

int main(){

    List First;
    First.AddNode(1);
    First.AddNode(2);
    First.AddNode(3);
    First.AddNode(4);
    First.AddNode(5);
    First.PrintList();

    First.DeleteNode(3);
    First.DeleteNode(5);
    First.PrintList();

    First.DeleteNode(8);
    First.PrintList();

    First.DeleteNode(1);
    First.PrintList();

    system("pause");
}

#1 Karel
Teoreticky, co bude taková funkce dělat? Funkce začne na začátku seznamu (budeš mít ukazatel ukazatel na první element tvého seznamu

nodePtr pTraverse = head;

který použiješ pro projití celého seznamu dokud pTraverse != NULL. Samotné projití seznamu ti ovšem maximální hodnotu neuloží, jak to tedy udělat? Jednoduše, uděláš si ještě jeden pointer, například

nodePtr pMax = head;

a v samotném while cyklu při traverzování seznamem doplníš podmínku, když hodnota traverzovaného elementu je větší než aktuální hodnota v uzlu pMax (pTraverse.value() > pMax.value()), tak pMax přesměruješ na aktuální traverzovaný prvek.

#2 ondrej39
Mohl bys mi to trochu více podrobněji vysvětlit? Nebo spíše napsat ukázku té funkce. Já jsem to zkusil, ale nějak mi to pořád nejde.

Mělo by to třeba vypadat takhle?

void List::Max(){
    nodePtr pTraverse = head;
    while(pTraverse != NULL)
        nodePtr pMax = head;
    if(pTraverse.value > pMax.value())
        pMax = pMax->curr;
}

to je asi spíš úplně špatně.

#3 Karel
Nejede ti to, protože ti vznikne nekonečný cyklus. Když píšeš cykly, ify, dávej si pozor na závorky.
 Pochopitelně, volání value() jsem napsal jen obecně, jedná se o hodnotu daného uzlu, kterou ty máš jako int data.

int List::Max()
{
	nodePtr pMax = NULL;
	nodePtr curr = head;

	while (curr != NULL)
	{
		if (pMax == NULL || curr->data > pMax->data)
		{
			pMax = curr;
		}
		curr = curr->next;
	}

	return pMax->data;
}

EDIT: Jinak takhle je to docela špatný. Co se stane, když v seznamu nebude žádný uzel a head tedy bude NULL? Pak bude NULL i výsledný uzel pMax, z něhož chceš vytáhnout data (pMax->data... program ti tady spadne). Dalo by se to nějak opravit? Ano, dalo. Například nebudeš vracet pMaxt->data, ale konkrétní int, můžeš vrátit hodnotu -1, když se maximum nepovede najít, ale co když uděláš seznam, v němž bude maximální hodnota právě -1? Jak pak rozlišíš tyto dvě situace?

Nejlogičtější by bylo nevracet int, ale ukazatel na uzel, když se ti vráti NULL, tak tam maximum prostě není, v opačném případě ano. Nicméně úplně nevím, jak vrátit ukazatel na strukturu, kterou máš ve třídě List vnořenou jako private. S tím ti bude muset poradit někdo jiný. (Předpokládám, že budeš potřebovat ještě jeden getter.)

#4 ondrej39
No jasně já to špatně pochopil, jsem myslel, že ta value je nějaká "funkce" která dává hodnotu. Vůbec mi to nemyslí. Mockrát děkuju za vysvětlení a pomoc.

#5 Karel
No já jsem s tím měl právě problémy s tím private. Měl jsem napsaný už jiný spojový seznam a v něm jsem měl moc věcí v privatu. A nemohl jsem se do toho dostat. Už jsem zkoušel napsat funkci Max ale pokaždé jsem se nemohl dostat do toho privatu. Pořád mi to házelo inaccessible. A mockrát děkuju.