[C++] Kako vrniti NULL če je polje prazno

if (!n) return 0;

Na začetku funkcije, jasno.

Zakaj pa vračaš tabelo oziroma kazalec?

Saj funkciji podaš kazalec na tabelo in spreminjaš originalno tabelo (pass by reference).

Če bi moral vračati polje urejenih števil potem verjetno ne smeš spreminjati obstoječega? Sicer pa pri selection sortu ni potrebe po vračanju urejega polja, ker urediš obstoječega.

Če še vseeno želiš kakor imaš, pa pri uporabi funkcije preveri če je vrnila NULL (0) ali nekaj drugega.

int * out = urediZizbiranjem(in, 10);
if(out != NULL) {
for(int i = 0;i<10;i++) {
printf("%d ", i);
}
}else{
//polje je prazno
}

Meni program krešne če dodam tisti if (!n) return 0;

In sicer takrat ko podam prazno polje.

Napiše mi tudi napaka a algoritmu, ko podam prazno polje.

Tako, da te dve zadevi še morem popravit, da bo vrnila NULL ter da bo vrnila polje urejenih števil.

Lahko vam prilepim celotno nalogo z navodili, da boste videli kaj mislim.

Evo vam celotno kodo.

/*
 *  PROSTOR ZA GLAVO
 * (ime in priimek avtorja, vpisna stevilka, besedilo naloge)
 --- --- --- --- --- --- ---
 *  vaja1.cpp
 *
 *       Ustvarjeno: 5.3.2013
 *            Avtor:
 *  Vpisna stevilka:
 *  Besedilo naloge:
 *
1.1 Urejanje z izbiranjem
Napiši metodo urediZIzbiranjem(), ki vrne naraš?ajo?e ure
jeno polje celih števil. Vrnjeno
polje naj bo enake velikosti in z enakimi vrednostmi, kot so
hranjene v podanem polju.
Red rasti ?asovne zahtevnosti tega algoritma naj znaša
O(n^2)

1.2 Navadno iskanje zadnjega pojavljanja elementa
Napiši metodo poisci(), ki v polju poiš?e podani element ter
vrne indeks zadnjega pojavljanja tega elementa.
Red rasti ?asovne zahtevnosti tega algoritma naj znaša
O(n)

1.3 Iskanje zadnjega pojavljanja elementa z bisekcijo
Napiši metodo poisciZBisekcijo(), ki v
urejenem polju poiš?e podani element ter vrne
indeks zadnjega pojavljanja tega elementa. Red rasti ?asovne
zahtevnosti tega algoritma naj znaša
O(logn)
*
*/

//privzete vkljucitve
#include <iostream>
#include <ctime>

//definicija imenskega prostora(/podrocja)
namespace vaja1 {

//uporabljeni imenski prostori
using namespace std;

//proste metode v imenskem prostoru

//a predstavlja polje (celostevilskih) elementov
//n pa stevilo elementov polja
int* urediZIzbiranjem(int* a, int n) {
	//TUKAJ VSTAVI SVOJO KODO
        int najmanjsi;

    if(!n) return 0;

        for(int i = 0; i < n; i++) {//prva for zanka, ki gre skozi polje
                najmanjsi = i;//vzamemo prvi element v polju za najmanjsega ter za nadaljno primerjavo

            for(int j = i + 1; j < n; j++) {//druga for zanka, ki gre skozi polje
                if(a[j] < a[najmanjsi]) {//if ki preverja ce je j manjsi od prej najmanjsega elementa
                najmanjsi = j;//ce je j res manjsi ga shranimo v spremenljivko
                }
            }

        int zacasni = a[i];
        a[i] = a[najmanjsi];
        a[najmanjsi] = zacasni;
        }

    return a;
}

//el predstavlja element, ki ga iscemo, a predstavlja polje,
//n pa stevilo elementov polja
int poisci(int el, int* a, int n) {
	//TUKAJ VSTAVI SVOJO KODO
	for(int i = n; i >= 0; i--) {//gremo od vrha proti dnu, da najdemo zadnjo pojavitev iskanega elementa
            if(a[i] == el) {//stavek, ki preverja ali je element v polju enak iskanemu elementu
                    return i;//vrnemo indeks na katerem se nahaja element
            }
    }
    return -1;//vrnemo to vrednost ce iskanega elementa ni v polju
}
	/*vasa funkcija naj NE vraca -2, pac pa
	 index najdenega elementa (ce ga ne najde,
	 naj vrne -1)*/


//el predstavlja element, ki ga iscemo, a predstavlja polje,
//n pa stevilo elementov polja
int poisciZBisekcijo(int el, int* a, int n) {
	//TUKAJ VSTAVI SVOJO KODO
	int dno = 0;
	int vrh = n - 1;
	int najdi = -1;

    while(dno <= vrh) {

        int m = (dno + vrh) / 2;//mediana

        if(a[m] < el) {

                dno = m + 1;
        }

        else if(a[m] > el) {

                vrh = m - 1;
        }

        else if(a[m] == el) {

                najdi = m;
                dno = m + 1;
        }
    }
    return najdi;

	return -1;//ce iskanega elementa ni v tabeli
}

bool urejeno(const int* A, int n) {
	if (n <= 0 || A == NULL)
		return false;
	for (int i = 0; i < n - 1; i++)
		if (A[i] > A[i + 1])
			return false;
	return true;
}
}

using namespace vaja1;

//glavna metoda - globalna

/*
 * Povzetek(/Summary):
 * (*description*)
 * Opombe(/Remarks):
 * (*description*)
 * Parametri(/Parameters):
 *     ime(/name): argn (int)
 *     Stevilo argumentov programa - tj. dolzina polja args (2. parametra metode).
 *     ime(/name): args (char**)
 *     Argumenti programa (oz. argumenti podani v program ob zagonu) v obliki nizov,
 *     ki se prenesejo v main kot polje (C-jevskih) nizov (tj. polja polj znakov,
 *     zaradi cesar je tip parametra kazalec na polje (C-jevskih) nizov (tj.
 *     kazalec na polje polj znakov).
 * Vracilo(/Return): (int)
 * (*description*)
 */
int main(int argn, char** args) {
	int polje[] = {1, 2, 3, 4 , 4, 4, 4};
	const int dolzina = sizeof(polje) / sizeof(int);
	int element = 4;

	clock_t start = clock();
	int* urejenoPolje = vaja1::urediZIzbiranjem(polje, dolzina);
	clock_t cilj = clock();
	float t = float (difftime(cilj, start)) / CLOCKS_PER_SEC;
	cout << "Cas izvajanja uredi z vstavljanjem: " << t//difftime(cilj, start)
			<< endl;

	if (!vaja1::urejeno(urejenoPolje, dolzina))
		cout << "napaka v algoritmu" << endl;
	else
		cout << "testni vzorec OK" << endl;

	int index = vaja1::poisci(element, urejenoPolje, dolzina);
	cout << "Element " << element << " je na mestu: " << index << endl;

	int index2 = vaja1::poisciZBisekcijo(element, urejenoPolje, dolzina);
	cout << "Element " << element << " je na mestu: " << index2 << endl;

	if (index != index2)
		cout << "napaka v iskanju" << endl;

    // TUKAJ VSTAVI SVOJE PRIMERE
	// npr. ce poisci in poisciZBisekcijo res vrneta indeks elementa,
	// ki je skrajno levo v polju (torej prvo pojavljanje).
	//int polje[] = { 109, 114, 84, 71, 51, 106, 51, 79, 64, 42 };
	//const int dolzina = sizeof(polje) / sizeof(int);
	//int element = 42;
	// Ce poisci in poisciZBisekcijo pri praznem polju res vrne -1.
	//int polje[] = { 109, 114, 84, 71, 51, 106, 51, 79, 64, 42 };
	//const int dolzina = sizeof(polje) / sizeof(int);
	//int element = 51;
	// Ce urediZVstavljanjem res narascujoce uredi polje in ce so se pri tem vsi elementi ohranili.
    // Ce poisci in poisciZBisekcijo vracata pravilni indeks iskanega elementa v polju.
	// Ce se poisciZBisekcijo pri vecjem stevilu elementov res hitreje izvede kot Poisci.
	// Ce poisci in poisciZBisekcijo med iskanjem ne spreminja polja.
	// ...

	return 0;
}

Tako, da zdaj res več nevem kako naj popravim še tisti dve napaki.

Napiše mi tudi napaka a algoritmu, ko podam prazno polje.

if (n <= 0 || A == NULL)
        return false;

Če je polje prazno in algoritem vrne NULL, potem mora funkcija urejeno vrniti false, kar pomeni da izpiše "napaka v algoritmu" - ta del je v redu.

Tako, da te dve zadevi še morem popravit, da bo vrnila NULL ter da bo vrnila polje urejenih števil.

Funkcija vrne NULL če je prazno polje in urejeno polje, če ni prazno.

Tebi crashne ker pri funkciji poisci dostopaš do A[0] čeprav je polje prazno. For zanka v tej funkciji se ne sme izvesti, če je n enako 0.

keworkian je 15. mar 2013 ob 21:25 izjavil:

Kaj pa tole?

 if (!n) return NULL;

Še bolj primerno, ker NULL ni nujno 0, recimo v C++11 je NULL enako nullptr, ki pa ni 0.

Torej vsa moja koda deluje OK?

Koliko vidite gre za nalogo za faks.

Podatkovne strukture? Sicer pa ne deluje OK, ker:

Tebi crashne ker pri funkciji poisci dostopaš do A[0] čeprav je polje prazno. For zanka v tej funkciji se ne sme izvesti, če je n enako 0.

Urejanje je kul, težavo imaš pri zaporednem iskanju.

Prej si napisal:

Meni program krešne če dodam tisti if (!n) return 0;

potem si pa pozabil na to?


Polje a pri urejanju je prazno, torej vrne NULL.

int *a=NULL;
int n = 0;
poisci(1, a, n);

int poisci(int el, int* a, int n) { //a = NULL, n = 0
    for(int i = n; i >= 0; i--) { //i = n = 0, i >= 0, 0 >= 0 -> zanka se izvede 1x
            if(a[i] == el) { //a = NULL, a[i]=??????????
                    return i;
            }
    }
    return -1;
}

1.1 Urejanje z izbiranjem
Napiši metodo urediZIzbiranjem(), ki vrne naraš?ajo?e ure
jeno polje celih števil. Vrnjeno
polje naj bo enake velikosti in z enakimi vrednostmi, kot so
hranjene v podanem polju.
Red rasti ?asovne zahtevnosti tega algoritma naj znaša
O(n^2)

Torej moreš vrnit drugo polje in ne tega ki ga vračaš ti.

Tako bi bilo verjetno še najbolj optimalno ja.

Problem je v tem ker tega ne znam :(

Sem probaval nekaj z new pa mi ni uspelo.

Ampak saj v resnici ne piše, da mora biti novo polje. Originalno polje je ustrezne velikosti in če pri "urejanju" ne izgubi nobenega elementa, ima prav te elemente (samo v drugem vrstnem redu).

Matic1911, naslednjič ti priporočam, da svoje kode ne deliš pred rokom :P Če nočeš imeti potem problemov s prepisovanjem :)

Ciklamen:

Bom upošteval tvoj nasvet za naslednjič :)

Tako nalogo sem oddal upam da bo sprejeta :)

Še enkrat hvala vsem za pomoč.