Ajutor! Eliminarea zerourilor din tablou

Buna seara!
Am nevoie de putin ajutor .
Se da urmatoarea problema : Se considera un tablou de n numere intregi. Sa se comprime tabloul fara a utiliza un tablou auxiliar in asa mod, incat zerourile sa fie eliminate din tablou. Daca in tabloul initial nu sunt zerouri sa se afiseze mesajul respectiv.

Nu am nici cea mai mica idee cum sa fac acest program.

Cel mai important e sa fi trecut printr-o facultate, atunci ai sanse mai mari sa fi auzit termenul de sparse matrix, si deci stii ce sa cauti, daca nu esti autodidact. Daca esti autodidact, citesti si singur.

Pasul urmator: google: sparse matrix.

Cu placere.

Presupun că este vorba de un tablou unidimensional.

 Ludw1kk, on 12 decembrie 2017 - 18:30, said:

black box approach
avem un input -> black box -> output
output - input = black box

Trebuie eliminate, adică să nu mai apară în tablou nici o informație legată de zero-uri? Sau trebuie comprimate, adică să ocupe mai puțin spațiu, dar să reținem suficiente informații încât să putem reface tabloul original dacă este nevoie?

#include <stdio.h>
	#include <stdlib.h>
	void stergeElement(int numberDe_Elimunat, int *arr, size_t *lungimeARR);
	int main(void){
		int arr[] = { 1, 0, 9, 4, 0, 6, 255, 132, 0, 19, 20, 101, 0, 25};
		long unsigned int lungimeARR;
		int numberDe_Elimunat = 0;
		lungimeARR = sizeof arr / sizeof arr[0];
		printf("Inainte:\n\t");
		for ( size_t i = 0 ; i < lungimeARR ; i++ ){
			printf("%d ", arr[i]);
		}
		printf("\nDupa:\n");
		stergeElement( numberDe_Elimunat, arr, &lungimeARR );
		for ( size_t j = 0 ; j < lungimeARR ; j++ ){
			printf("%d ", arr[j]);
		}
		printf("\n");
	}
	void stergeElement(int numberDe_Elimunat, int *arr, size_t *lungimeARR){
		if (arr == NULL ){
			printf("Eroare, NULL Pointer\n");
			exit( EXIT_FAILURE );
		}
		if ( *arr == '\0' ){
			printf("Eroare, Buferul este Gol\n");
			exit( EXIT_SUCCESS );
		}
		int arrTemp[*lungimeARR];
		long unsigned int j = 0, c, gasit = 0;
		for ( size_t i = 0 ; i < *lungimeARR ; i++ ){
			if ( arr[i] == numberDe_Elimunat ){
					gasit++;
					continue;
			}else{
				arrTemp[j] = arr[i];
				j++;
			}
		}
		for ( size_t k = 0 ; k < j ; k++ ){
			arr[k] = arrTemp[k];
		}
		c = j;
		while ( *lungimeARR > c ){
			arr[c] = 0;
			c++;
		}
		*lungimeARR = j;
		printf("\nAu fost eliminati %zu de Zero\n\t",gasit);
	}

Output:

Quote

Edited by TARA24, 20 December 2017 - 20:06.

arrTemp este un tablou auxiliar, deci nu respectă cerințele. Și ar mai  fi de comentat...

Și ce te oprește ?

Pleci de la 2 pointeri spre acelasi vector. Unul inainteaza mereu, celalalt doar cand valoarea != 0. Copiezi dintr-unul in altul.

Transversarea era mai ușor de înțeles pentru autorul Topicului, care e de la sine înțeles ca nu înțelege încă multe, dar ce săi faci, noroc cu “profesorii” de voi.

int arr[] = { 1, 0, 9, 4, 0, 6, 255, 132, 0, 19, 20, 101, 0, 25};
int found=1;
while(found > 0){
for(int i=0;i<arr.length()-1;i++){
  if(arr[i] == 0)
  {
   if(arr[i+1] <> 0)
   {
	arr[i] = arr[i+1];
	arr[i+1] = 0;
	found++;
   }
  }
}
if(found == 1) found = 0;
}

ceva in genul asta?

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
	class Program
	{
		static void Main()
		{
			int[] arr = new int[] { 1, 0, 9, 4, 0, 6, 255, 132, 0, 19, 20, 101, 0, 25 };
			int found = 0;
			bool swap = true;
			Debug.WriteLine(" starting ... \n");
			while (swap)
			{
				swap = false;
				for (int i = 0; i < arr.Length - 1; i++)
				{
					if (arr[i] == 0)
					{
						if (arr[i + 1] != 0)
						{
							arr[i] = arr[i + 1];
							arr[i + 1] = 0;
							found++;
							swap = true;
						}
					}
				}
				for (int i = 0; i < arr.Length; i++)
				{
					Debug.Write(String.Format("{0} ", arr[i].ToString()));
				}
				Debug.WriteLine("");
			}
			Debug.WriteLine("Finished: {0} loops", found);
			for (int i = 0; i < arr.Length; i++)
			{
				Debug.Write(String.Format("{0} ", arr[i].ToString()));
			}
			Debug.WriteLine("\n");
		}
	}
}

c#, e tot ce am la indemana care sa compileze in seara asta, dar merge pe post de proof

starting ...
1 9 4 0 6 255 132 0 19 20 101 0 25 0
1 9 4 6 255 132 0 19 20 101 0 25 0 0
1 9 4 6 255 132 19 20 101 0 25 0 0 0
1 9 4 6 255 132 19 20 101 25 0 0 0 0
1 9 4 6 255 132 19 20 101 25 0 0 0 0
Finished: 21 loops
1 9 4 6 255 132 19 20 101 25 0 0 0 0

#include "stdafx.h"
int main()
{
int arr[] = { 1, 0, 9, 4, 0, 6, 255, 132, 0, 19, 20, 101, 0, 25 };
int swaps = 0;
int loop_no = 0;
int zeroes = 0;
bool swap = true;
int arrLen = sizeof(arr) / sizeof(arr[0]);
printf(" starting ... \n");
while (swap)
{
swap = false;
printf("Loop %02d : ", loop_no);
loop_no++;
for (int i = 0; i < arrLen - 1; i++)
{
if (arr[i] == 0)
{
if (arr[i + 1] != 0)
{
	 arr[i] = arr[i + 1];
	 arr[i + 1] = 0;
	 swaps++;
	 swap = true;
}
}
}
for (int i = 0; i < arrLen; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
printf("Finished in %d swaps \t", swaps);
for (int i = 0; i < arrLen; i++)
{
if (arr[i] != 0) printf("%d ", arr[i]);
else zeroes++;
}
printf("; found %d zeroes\n", zeroes);
return 0;
}

starting ...
Loop 00 : 1 9 4 0 6 255 132 0 19 20 101 0 25 0
Loop 01 : 1 9 4 6 255 132 0 19 20 101 0 25 0 0
Loop 02 : 1 9 4 6 255 132 19 20 101 0 25 0 0 0
Loop 03 : 1 9 4 6 255 132 19 20 101 25 0 0 0 0
Loop 04 : 1 9 4 6 255 132 19 20 101 25 0 0 0 0
Finished in 21 swaps	1 9 4 6 255 132 19 20 101 25 ; found 4 zeroes

versiunea cpp

Edited by DeeJay, 21 December 2017 - 09:35.

 TARA24, on 20 decembrie 2017 - 21:45, said:

Era prea târziu în noapte. Eram ocupat cu alte lucruri. Dar comentez acum.

if ( *arr == '\0' ){
	printf("Eroare, Buferul este Gol\n");
	exit( EXIT_SUCCESS );
}

Bucata asta de cod dorește să verifice dacă array-ul pe care ar trebui să îl procesăm are 0 elemente...
1. Din moment ce funcția primește in mod explicit lungimea prin lungimeARR, verificarea corectă at fi if (lungimeArr == 0) ... .
2. arr este pointer către primul element din array, *arr este valoarea primului element din array. În cazul în care array-ul este gol, atunci evident că nu are nici un element, deci *arr are o valoare nedefinită. Deci verificarea nu va da rezultate corecte în cazul respectiv.
3. '\0' - este un char, mai mult decât atât este terminatorul unui șir de caractere, valoarea lui în int este 0. Adică condiția ta testează dacă *arr are valoarea 0, adică dacă primul element al array-ului este 0. Deci verificarea nu va da rezultate corecte în cazul în care primul element are valoarea 0. Un array {0, 1, 2, 3} va fi considerat gol.
4. Folosirea '\0' îmi dă de bănuit că ai încurcat array-urile cu șirurile de caractere.
5. Printează că este o eroare dar apeleză exit cu success, deci este inconsistent, dacă este eroare este eroare, iar dacă este succes este succes. Ce are mai mult sens pentru funcția de eliminat pentru cazul în care array-ul este gol, succes sau eroare?

Ar mai fi folosirea inutilă a lui continue, denumirea variabilei numberDe_Elimunat (engleză + română greșită), etc...

@deeJay, algoritmul tău are o complexitate în anumite cazuri de O(N^2). Vezi ce se întâmplă atunci când array-ul este sub forma de {0, element, 0, element, ... }.
Se poate mai bine în cazul simplu de eliminat valoarea 0, vezi sugestia lui @dani.user.

Nu e vorba de nici un sparse matrix, e vorba de un tablou cu n elemente, unele dintre ele zero-uri (nu se specifica proportia), care trebuie eliminate. Daca nu exista zero-uri se afiseaza un mesaj.

#include <iostream>

using namespace std;

void printArray(int array[], int arraySize)
{
	for (int i = 0; i < arraySize; ++i)
	{
		cout << array[i] << " ";
	}
	cout << endl; 
}

int compactArray(int array[], int arraySize)
{
	int result = -1;
 
	int* pFullTraverse = array;
	int* pNonZeroTraverse = array;
	for (int i = 0; i < arraySize - 1; ++i)
	{
		pFullTraverse++;
		if (*pNonZeroTraverse != 0)
		{
			pNonZeroTraverse++;
		}
		if (*pFullTraverse != 0 && *pNonZeroTraverse == 0)
		{
			*pNonZeroTraverse = *pFullTraverse;
			*pFullTraverse = 0;
			result = 0;
		}
	}
 
	return result;
}

void processArray(int array[], int arraySize)
{
	printArray(array, arraySize);
 
	if (compactArray(array, arraySize) == 0)
	{
		printArray(array, arraySize);
	}
	else
	{
		cout << "There are no null elements";
	} 
}

int main()
{
	int nullArray[] = {1, 0, 4, 0, 6, 255, 132, 0, 19, 1, 0, 0, 25, 0};
	processArray(nullArray, sizeof(nullArray)/sizeof(*nullArray));

	cout << endl;

	int nonNullArray[] = {1, 4, 6, 255, 132, 19, 1, 25};
	processArray(nonNullArray, sizeof(nonNullArray)/sizeof(*nonNullArray));
}

test cu 24 elemente 0:

starting ...
Loop 00 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Finished in 0 swaps	 ; found 24 zeroes

test cu 23 zero si unul non-zero:

starting: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Loop 00 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Loop 01 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
Loop 02 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
Loop 03 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
Loop 04 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
Loop 05 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
Loop 06 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
Loop 07 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
Loop 08 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
Loop 09 : 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Loop 10 : 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
Loop 11 : 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
Loop 12 : 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 13 : 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 14 : 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 15 : 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 16 : 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 17 : 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 18 : 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 19 : 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 20 : 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 21 : 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 22 : 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Loop 23 : 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Finished in 23 swaps 1 ; found 23 zeroes

complexitate (n/2)^2 ... cred

starting: 0 0 0 0 0 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23
Loop 00 : 0 0 0 0 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0
Loop 01 : 0 0 0 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0
Loop 02 : 0 0 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0
Loop 03 : 0 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0
Loop 04 : 0 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0
Loop 05 : 0 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0
Loop 06 : 0 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0
Loop 07 : 0 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0
Loop 08 : 0 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0 0
Loop 09 : 0 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0 0 0
Loop 10 : 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0 0 0 0
Loop 11 : 11 12 13 14 15 16 17 18 19 20 21 22 23 0 0 0 0 0 0 0 0 0 0 0
Finished in 143 swaps 11 12 13 14 15 16 17 18 19 20 21 22 23 ; found 11 zeroes

Edited by DeeJay, 21 December 2017 - 11:42.

daca schimb ordinea de parcurgere, se misca mai repede

for (int i = arrLen - 1; i > 0; i--)
{
if (arr[i] == 0)
{
if (arr[i - 1] != 0)
{
	 arr[i] = arr[i - 1];
	 arr[i - 1] = 0;
	 swaps++;
	 swap = true;
}
}
}

starting: 0 1 0 1 0 1 0 1 0 1 0 0 12 13 14 15 16 17 18 19 0 21 22 23 24
Loop 00 : 0 0 1 0 1 0 1 0 1 0 1 0 0 12 13 14 15 16 17 18 19 21 22 23 24
Loop 01 : 0 0 0 1 0 1 0 1 0 1 0 1 0 12 13 14 15 16 17 18 19 21 22 23 24
Loop 02 : 0 0 0 0 1 0 1 0 1 0 1 0 1 12 13 14 15 16 17 18 19 21 22 23 24
Loop 03 : 0 0 0 0 0 1 0 1 0 1 0 1 1 12 13 14 15 16 17 18 19 21 22 23 24
Loop 04 : 0 0 0 0 0 0 1 0 1 0 1 1 1 12 13 14 15 16 17 18 19 21 22 23 24
Loop 05 : 0 0 0 0 0 0 0 1 0 1 1 1 1 12 13 14 15 16 17 18 19 21 22 23 24
Loop 06 : 0 0 0 0 0 0 0 0 1 1 1 1 1 12 13 14 15 16 17 18 19 21 22 23 24
Loop 07 : 0 0 0 0 0 0 0 0 1 1 1 1 1 12 13 14 15 16 17 18 19 21 22 23 24
Finished in 33 swaps 1 1 1 1 1 12 13 14 15 16 17 18 19 21 22 23 24 ; found 8 zeroes

starting: 0 0 0 0 0 0 0 0 0 0 0 0 12 13 14 15 16 17 18 19 0 21 22 23 24
Loop 00 : 0 0 0 0 0 0 0 0 0 0 0 0 0 12 13 14 15 16 17 18 19 21 22 23 24
Loop 01 : 0 0 0 0 0 0 0 0 0 0 0 0 0 12 13 14 15 16 17 18 19 21 22 23 24
Finished in 8 swaps	 12 13 14 15 16 17 18 19 21 22 23 24 ; found 13 zeroes

Edited by DeeJay, 21 December 2017 - 12:09.

Un banal if e suficient in interiorul unui for.

• Sirul e parcurs o singura data, deci O(N)
  
• Valorile de interes sunt copiate peste cele existente (e mai rapid sa copiez un int decat sa am un if suplimentar de executat la fiecare pas)
  
• Profit de faptul ca se cere eliminarea acelor 0, nu mutarea lor la finalul sirului. Astfel, daca vectorul initial are 5 valori, din care 2 sunt 0 (sau ce anume se doreste eliminat), codul meu specifica ca, dupa executia functiei, cele 3 valori non 0 se vor gasi pe primele pozitii (in aceeasi ordine). Ce se va gasi pe ultimele doua pozitii e nespecificat (memoria e inca alocata, dar poti gasi orice acolo, asa ca nu le mai citesti, te limitezi la primele 3 pozitii).

#include <algorithm>
#include <iostream>
#include <iterator>
#include <cstddef>

template<typename T>
std::ptrdiff_t removeValue(T* ptr, size_t nrOfElements, T toRemove)
{
	T* const start = ptr;
	T* const stop = ptr + nrOfElements;
	T* current = ptr;

	for (; ptr < stop; ++ptr)
	{
		if (*ptr != toRemove)
		{
			*current++ = *ptr;
		}
	}

	return current - start;
}

int main()
{
	int values[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 12, 13, 14, 15, 16, 17, 18, 19, 0, 21, 22, 23, 24};

	std::cout << "Before: ";
	std::copy(std::begin(values), std::end(values), std::ostream_iterator<int>(std::cout, " "));
	std::cout << '\n';

	auto nrOfValuesRemainingAfterRemovingZeros = removeValue(values, sizeof(values) / sizeof(values[0]), 0);

	std::cout << "After: ";
	std::copy(std::begin(values), std::begin(values) + nrOfValuesRemainingAfterRemovingZeros, std::ostream_iterator<int>(std::cout, " "));
	std::cout << '\n';
}

Quote