C zadatak sa nizovima

[Goonotora]

Zadatak sa junskog ispitnog roka 2012 iz C programiranja:

Trazi se funkcija za spajanje dva ucitana niza celih brojeva u niz koji sadrzi sve elemente iz dva niza osim onih elemenata koji su isti u oba niza.

E sad ako sam dobro razumeo trazi se ovako nesto (matematicki receno) (AUB)/(A∩B)
ucitavanje nizova mi nije problem, jedino mi je problem ta funkcija, jer ne znam da li treba da poredim prvo jedan niz pa drugi ili neki drugi nacin...

Nasao sam jedan slican zadatak, ali on u treci niz stavlja elemente koji su isti u oba niza. Da li da krenem od njega?

Unapred hvala za pomoc.

[voodoo_]

Mislim da je nešto u ovom fazonu (uzmimo da su to dva niza od po 20 elemenata)

int niz1[20];
int niz2[20];

// Prvo prebrojimo koliko ima elemenata zrelih za novi niz, a ima ih po dva za svaki indeks za koji se elementi razlikuju

int counter = 0;

for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i]) counter += 2;


// Dinamički zauzimamo memoriju za novi niz, pošto nismo na početku znali koliki će biti

int* noviniz = (int*) malloc(counter * sizeof(int));

counter = 0;
for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i]
    {
        noviniz[counter] = niz1[i];
        noviniz[counter+1] = niz2[i];
        counter += 2;
    }

// Kad završimo sa poslovima u vezi sa nizom, oslobađamo memoriju
free(noviniz);

Alternativno, može se napraviti i verzija sa jednim prolazom kroz izvorne nizove, s tim što ćemo na kraju uraditi realokaciju na tačnu dužinu:

int niz1[20];
int niz2[20];
int* noviniz = (int*) malloc(40 * sizeof(int)); // Ne može biti više od 40 elemenata u najgorem slučaju


int counter = 0;

for (int i=0; i<20; i++)
    if (niz1[i] != niz2[i])
    {
        noviniz[counter] = niz1[i];
        noviniz[counter+1] = niz2[i];
        counter += 2;
    }

realloc((int*) noviniz, counter * sizeof(int));


free(noviniz);

E sad, ako oni pod elementom podrazumevaju samo vrednost, a ne vrednost sa indeksom, onda se nizovi tretiraju kao skupovi različitih veličina i rešenje je dosta složenije. Recimo, možeš da napraviš kopije nizova očišćene od duplikata u njima samima, sortiraš ih rastuće ili opadajuće i onda zaređaš duplu petlju gde porediš svaki element jednog sa svakim elemenom drugog i ubacuješ u finalni niz koji povećavaš za dva komada pre svakog uspešnog dodavanja.

Uglavnom, ako je ovo drugo, nizovi nisu najsrećniji metod. Mnogo elegantnije se rešava preko ulančane liste. Recimo, za svaki element druge liste ispitaš da li postoji u prvoj. Ako ne postoji, dodaš ga u prvu. Ako postoji, preskočiš ga, a iz prve ga ukloniš. Na kraju, ono što je ispalo od prve liste je rezultat.

[fingerprint]

Evo rešenja za taj problem. Nisam znao kako da nazovem funkciju pa sam samo lupio ime.
Kod nije preterano lep ali radi, nadam se bez puno bagova. Sutra kad ustanem napisaću ukratko i kako radi, mada mislim da je jasno.

#include "stdlib.h"
#include "stdio.h"

int comparator(const void *a, const void *b)
{
	return (*(int *)a - *(int *)b);
}

void wubzidub(int *a, int size_a, int *b, int size_b, int **result_out, int *result_size_out)
{
	int *ab = (int*)malloc(sizeof(int) * (size_a+size_b));
	int *result = (int*)malloc(sizeof(int) * (size_a+size_b));
	memcpy(ab, a, size_a * sizeof(int));
	memcpy(ab + size_a, b, size_b * sizeof(int));
	qsort(ab, size_a+size_b, sizeof(int), &comparator);

	int *iter = ab, *end = ab + (size_a + size_b);
	int result_size = 0;
	while(iter != end)
	{
		int current = *iter;
		if((iter + 1) != end && *(iter + 1) == current)
		{
			//lookahead
			int *ahead_iter = iter + 1;
			while(ahead_iter != end && *ahead_iter == current)
				ahead_iter++;
			iter = ahead_iter;
		}
		else
		{
			result[result_size] = *iter;
			result_size++;
			iter++;
		}
	}
	free(ab);
	*result_out = result;
	*result_size_out = result_size;
}


int main(int argc, char* argv[])
{
	int a[5] = {1, 2, 5, 6, 2};
	int b[5] = {6, 2, 5, 8, 3};
	int *result;
	int sz;
	wubzidub(a, 5, b, 5, &result, &sz);
	for(int i = 0; i < sz; ++i)
		printf("%d ", result[i]);
	printf("\n");
	getchar();
	return 0;
}

EDIT: Ovaj program zapravo ne radi šta treba u svim slučajevima. Pogledaću sutra :|

[Ivan452]

@Goonotora
Koliko kapiram ovo ti je ispit iz nekog uvoda u programiranje?
Ako je tako smatram da je resenje koje ti je fingerprint ponudio isuvise komplikovano za razumevanje(posebno bez pojasnjenja autora).
Resenje koje cu ti ja ponuditi nadovezuje se na ovo koje ti je voodoo ponudio (medjutim u zadatku kada se kaze na element mislis se bilo gde u nizu a ne na odredjenoj poziciji pa njegovo nije to ispunilo).
Kod pisem napamet, pa javi se ako nesto ne radi. Generalno ne volim da dajem 100% resenja, tako da ces neke stvari morati sam da resis.

int niz1[20];
int niz2[20];
int* niz3= (int*) malloc(40 * sizeof(int));

int counter = 0;
int postoji=0;

for (int i=0; i<20; i++)
    {
        for (int j=0; j<20; j++)
        {
            if (niz1[i] == niz2[j])
            {
                postoji=1;
                break;
            }
        }

        if(postoji==0)
            niz3[counter++] = niz1[i];

        postoji=0;
    }

for (int i=0; i<20; i++)
{
    for (int j=0; j<20; j++)
    {
        if (niz2[i] == niz1[j])
        {
            postoji=1;
            break;
        }
    }
    if(postoji==0)
        niz3[counter++] = niz2[i];

    postoji=0;
}

realloc((int*) niz3, counter * sizeof(int));
free(niz3);

Ovo ti je najjednostavnije, skolsko resenje, ali takodje i najneoptimalnije.
Prvo prolazis kroz sve element prvog niza i uporedjujes sa svim clanovima drugog niza.
Ako se nadje isti clan promenljiva postoji se postavlja na 1 i izlazi se iz unutrasnje petlje (jer je nepotrebno dalje da se proverava).
Ako po izlasku iz unutrasnje petlje promenljiva postoji nije promenila vrednost ona znaci da taj element ne postoji u oba niza i on se upisuje u niz3.
Kada se ovo zavrsi, potom se svaki element drugog niza uporedjuje sa svakim elementom prvog niza. I radi se istva stvar.


Kada ovo razumes, prva popravka bi bila da resis problem ako jedan niz sadrzi 2 ista elementa koja drugi niz nema. Npr:
niz1: 1 1 2 3 4
niz2: 2 3 4 5 6
rezultujuci niz3 bi bio: 1 1 5 6.
Posle toga mozes da resavas da nizovi ne budu fiksirani na maksimum od 20 elemenata.

Ako se od vas ipak ocekuje malo bolje resenje ovakvih problema (sa algoritamske strane).
Mnogo bolje resenje mozes npr. da dobijes ovako:

1. Sortiras niz1 i niz2 i ocistis od duplikata.
2. Jednim prolazom kroz oba niza uporedjujes da li je prvi clan niza1 manji od prvog clana niza2. Ako jeste povecavas index niza1 koji gledas i upisujes u niz3. Ako je posmatrani element niza2 manji od niza1 upisujes taj element niza2 u niz3 i povecavas index niza2.

Ovim dobijas optimalno resenje kompleksnosti O(n) i od ovog ne moze bolje. Naravno, varijacije na temu postoje.

[Stevvan]

int niz1[20], n1;
int niz2[20], n2;
int res[40], r;

void dodajElement(int elem, int *niz, int *duzina) {
    for (int i = 0; i < (*duzina); i++) {
        if (niz[i] == elem)
            return;
    }
    niz[*duzina] = elem;
    (*duzina)++;
}

int main() {
    //Ucitaj niz1, niz2 i njihove duzine
    r = 0;
    for (int i = 0; i < n1; i++)
        dodajElement(niz1[i], res, &r);
    for (int i = 0; i < n2; i++)
        dodajElement(niz2[i], res, &r);
    return 0;
}

Nisam testirao, trebalo bi da radi slozenost je manja od (n1+n2)^2. Ako si upoznat sa pokazivacima, resenje ne bi trebalo da te zbunjuje previse

Edit:
Zaboravio sam da napomenem, izbaci ce sve moguce kopije iz nizova, tako da ce ostati samo skroz razlicite vrednosti. Tako da ako se nadje npr. da niz1 ima clanove 1 2 5 2 3, uzece samo prvu dvojku

[tina]

znali neko da mi uradi zadate iz programiranja il da mi barem objasni.hvala u napred

[ivan90BG]

Pa prvo moraš da nam napišeš zadatak.