Zawieszający się program

0

Witam.
Napisałem program na ćwiczenia analizujący złożoność poszczególnych metod przeszukiwania tablicy na podstawie liczby porównań.
Mam tylko problem program działa normalnie lecz w niektórych momentach zawiesza się.
Proszę o 2 rzeczy:
Znalezienie miejsca które powoduje zwiechy.
Sprawdzenie czy dobrze zliczam liczbę porównań(zmienna liczbap w funkcjach bezwartownika, zwartownikiem, binarnie)
W załączniku zamieszczam treść zadania a poniżej kod.
Z góry dzięki.

 
#include <stdio.h>
#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void wyswietl(int *tablica, int wielkosc)
{
	for(int i = 0; i < wielkosc - 1;i++)
	{
		printf("%i ", tablica[i]);
	}
	printf("\n");
}

void addDane(int *tablica, int wielkosc)
{
	srand((unsigned)time(NULL));
	int i = 0;
	
	for(int i = 0; i < wielkosc - 1;i++)
	{
		tablica[i] = 0 + rand() % (400 + 1);
	}

}

void sort(int *tablica, int wielkosc)
{
        bool swapped; // Czy zamieniono w ostatnim obrocie?
 
        do {
            swapped = false;
            for (int i = 0; i < wielkosc - 1; ++i) 
			{
                if (tablica[i] > tablica[i + 1])
				{
                    swap(tablica[i], tablica[i + 1]);
                    swapped = true;
                }
            }
        } while (swapped);
}

void bezwartownika(int *tablica, int wielkosc)
{
	int x, liczbap = 0;
	printf("Podaj szukana: \n");
	scanf("%i", &x);
	int i = 1;
	for(int i = 0; i < wielkosc; i++)
	{
		liczbap++;
		if(tablica[i] == x)
		{
		liczbap++;
		printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, i);
		return;
		}
		
	}
	printf("Nie ma elementu x w tablicy\n");

	printf("Liczba porownan: %i\n", liczbap);
}

void zwartownikiem(int *tablica, int wielkosc)
{
  
  int x, liczbap = 0;
  printf("Podaj szukana: \n");
  scanf("%i", &x);

  int i = 0;

  tablica[wielkosc] = x;
  for(int i = 0; tablica[i] != x; i++)
	  liczbap++;
  
  liczbap++;
  if(i == wielkosc)
  {
	  printf("Nie ma elementu x w tablicy\n");
  }
  else 
	  printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, i);
  

  printf("Liczba porownan: %i\n", liczbap);
}

void binarnie(int *tablica, int wielkosc)
{
	int x, liczbap = 0;
	printf("Podaj szukana: \n");
	scanf("%i", &x);
	int ip = 0;
	int ik = wielkosc - 1;
	int isr;
	do
	{
		liczbap++;
		isr = (ip + ik) / 2;
		if(x > tablica[isr])
			{
			liczbap++;
			ip++;
			}
		else 
			ik--;
	}while((tablica[isr] != x) || !(ip > ik));

	liczbap = liczbap + 2;

	if(tablica[isr] != x)
		 {
		liczbap++;
		 printf("Nie ma elementu x w tablicy\n");
		}
	else
	{
	printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, isr);
	}


	printf("Liczba porownan: %i\n", liczbap);
}

int main()
{
	int wielkosc = 10;
	printf("**********Tablica ustawiona na 10 elementow**********\n");
	int *tablica = new int(wielkosc);
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 10 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 10 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 10 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 10 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 100;
	printf("**********Tablica ustawiona na 100 elementow**********\n");
	tablica = new int(wielkosc);
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 100 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 100 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 100 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 100 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 100 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 100 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 1000;
	printf("**********Tablica ustawiona na 1000 elementow**********\n");
	tablica = new int(wielkosc);
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 1000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 1000 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 1000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 1000 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 10000;
	printf("Tablica ustawiona na 10000 elementow\n");
	tablica = new int(wielkosc);
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("Podawaj x ktory jest w tablicy.\n");
	printf("Bez wartownika 10000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10000 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("Podawaj x ktorego nie ma w tablicy.\n");
	printf("Bez wartownika 10000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10000 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("Podawaj x ktory jest w tablicy (dla posortowanych danych).\n");
	printf("Binarnie 10000 elementow\n");
	binarnie(tablica, wielkosc);
	printf("Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);
	delete []tablica;

	system("pause");
}
0
RedHat napisał(a):

Proszę o 2 rzeczy:
Znalezienie miejsca które powoduje zwiechy.

Zapewne się gdzieś zapętlił. Jak używałeś debuggera to nie zauważyłeś czegoś dziwnego? ;>

RedHat napisał(a):

lecz w niektórych momentach zawiesza się.

Nie wiem co to znaczy :P

0

int *tablica = new int(wielkosc);
źle zaalokowana tablica. nawiasy powinny być kwadratowe.
Później przy wypełnianiu powoduje to segmentation fault

0

Wywala komunikat : zadanie2.exe has triggered a breakpoint. I zawiesza się w momencie wprowadzania danych dla wyszukiwania binarnego dla 10 elementów tego w którym wprowadzam liczbę nie znajdująca się w tablicy. Wprowadzam liczbę daje enter i nic sie nie dzieje....

0

Nawiasy poprawione, lecz wiesza się dalej....

0 
a.cpp:20:13: warning: unused variable 'i' [-Wunused-variable]
        int i = 0;
            ^
a.cpp:51:13: warning: unused variable 'i' [-Wunused-variable]
        int i = 1;
            ^
2 warnings generated.

Nawiasy poprawione, lecz wiesza się dalej....
zamieniłeś wszędzie te nawiasy?

**********Tablica ustawiona na 10 elementow**********
303 252 162 126 305 88 14 288 316
**********Podawaj x ktory jest w tablicy.**********
Bez wartownika 10 elementow.
Podaj szukana:
88
Element o wartosci x: 88 znajduje sie na pozycji: 5
Z wartownikiem 10 elementow
Podaj szukana:
-123123
Element o wartosci x: -123123 znajduje sie na pozycji: 0
Liczba porownan: 11
**********Podawaj x ktorego nie ma w tablicy.**********
Bez wartownika 10 elementow.
Podaj szukana:
2
Nie ma elementu x w tablicy
Liczba porownan: 10
Z wartownikiem 10 elementow
Podaj szukana:
żółć
Element o wartosci x: 3338432 znajduje sie na pozycji: 0
Liczba porownan: 11
**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********
Binarnie 10 elementow
Podaj szukana:
0

Kod wygląda teraz tak..... Nie wiem chyba nic nie przeoczyłem....

#include <stdio.h>
#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void wyswietl(int *tablica, int wielkosc)
{
	for(int i = 0; i < wielkosc - 1;i++)
	{
		printf("%i ", tablica[i]);
	}
	printf("\n");
}

void addDane(int *tablica, int wielkosc)
{
	srand((unsigned)time(NULL));
	int i = 0;
	
	for(int i = 0; i < wielkosc - 1;i++)
	{
		tablica[i] = 0 + rand() % (400 + 1);
	}

}

void sort(int *tablica, int wielkosc)
{
        bool swapped; // Czy zamieniono w ostatnim obrocie?
 
        do {
            swapped = false;
            for (int i = 0; i < wielkosc - 1; ++i) 
			{
                if (tablica[i] > tablica[i + 1])
				{
                    swap(tablica[i], tablica[i + 1]);
                    swapped = true;
                }
            }
        } while (swapped);
}

void bezwartownika(int *tablica, int wielkosc)
{
	int x, liczbap = 0;
	printf("Podaj szukana: \n");
	scanf("%i", &x);
	int i = 1;
	for(int i = 0; i < wielkosc; i++)
	{
		liczbap++;
		if(tablica[i] == x)
		{
		liczbap++;
		printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, i);
		return;
		}
		
	}
	printf("Nie ma elementu x w tablicy\n");

	printf("Liczba porownan: %i\n", liczbap);
}

void zwartownikiem(int *tablica, int wielkosc)
{
  
  int x, liczbap = 0;
  printf("Podaj szukana: \n");
  scanf("%i", &x);

  int i = 0;

  tablica[wielkosc] = x;
  for(int i = 0; tablica[i] != x; i++)
	  liczbap++;
  
  liczbap++;
  if(i == wielkosc)
  {
	  printf("Nie ma elementu x w tablicy\n");
  }
  else 
	  printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, i);
  

  printf("Liczba porownan: %i\n", liczbap);
}

void binarnie(int *tablica, int wielkosc)
{
	int x, liczbap = 0;
	printf("Podaj szukana: \n");
	scanf("%i", &x);
	int ip = 0;
	int ik = wielkosc - 1;
	int isr;
	do
	{
		liczbap++;
		isr = (ip + ik) / 2;
		if(x > tablica[isr])
			{
			liczbap++;
			ip++;
			}
		else 
			ik--;
	}while((tablica[isr] != x) || !(ip > ik));

	liczbap = liczbap + 2;

	if(tablica[isr] != x)
		 {
		liczbap++;
		 printf("Nie ma elementu x w tablicy\n");
		}
	else
	{
	printf("Element o wartosci x: %i znajduje sie na pozycji: %i\n", x, isr);
	}


	printf("Liczba porownan: %i\n", liczbap);
}

int main()
{
	int wielkosc = 10;
	printf("**********Tablica ustawiona na 10 elementow**********\n");
	int *tablica = new int[wielkosc];
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 10 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 10 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 10 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 10 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 100;
	printf("**********Tablica ustawiona na 100 elementow**********\n");
	tablica = new int[wielkosc];
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 100 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 100 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 100 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 100 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 100 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 100 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 1000;
	printf("**********Tablica ustawiona na 1000 elementow**********\n");
	tablica = new int[wielkosc];
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("**********Podawaj x ktory jest w tablicy.**********\n");
	printf("Bez wartownika 1000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 1000 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("**********Podawaj x ktorego nie ma w tablicy.**********\n");
	printf("Bez wartownika 1000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 1000 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("**********Podawaj x ktory jest w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);
	printf("**********Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).**********\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);

	delete []tablica;

	wielkosc = 10000;
	printf("Tablica ustawiona na 10000 elementow\n");
	tablica = new int[wielkosc];
	
	addDane(tablica, wielkosc);
	wyswietl(tablica, wielkosc);

	printf("Podawaj x ktory jest w tablicy.\n");
	printf("Bez wartownika 10000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10000 elementow\n");
	zwartownikiem(tablica, wielkosc);

	printf("Podawaj x ktorego nie ma w tablicy.\n");
	printf("Bez wartownika 10000 elementow.\n");
	bezwartownika(tablica, wielkosc);
	printf("Z wartownikiem 10000 elementow\n");
	zwartownikiem(tablica, wielkosc);
	
	sort(tablica, wielkosc);
	printf("Podawaj x ktory jest w tablicy (dla posortowanych danych).\n");
	printf("Binarnie 10000 elementow\n");
	binarnie(tablica, wielkosc);
	printf("Podawaj x ktorego nie ma w tablicy (dla posortowanych danych).\n");
	printf("Binarnie 1000 elementow\n");
	binarnie(tablica, wielkosc);
	delete []tablica;

	system("pause");
}
0

Program wiesza się jeden krok dalej niż tutaj wkleiłes :D

0

Jakieś pomysły ??

0

  1. Wyszukiwanie binarne masz źle. Algorytm jest inny.

  2. Namieszałeś strasznie z liczbą elementów w tablicy i indeksowaniem. Zmień to, prawdopodobnie masz gdzieś błąd z tym związany. No i wyniki błędne - skoro ma być 10 elementów to użyj 10-ciu elementów, a nie 9-ciu.

  • jeśli tablica ma mieć 10 elementów to zrób tablicę 11-elementową (dodatkowy jeden element na wartownika)
        int wielkosc = 10;
        printf("**********Tablica ustawiona na 10 elementow**********\n");
        int *tablica = new int[wielkosc + 1];
  • sortuj, wyświetlaj itp. "normalnie":
void wyswietl(int *tablica, int wielkosc)
{
        // for(int i = 0; i < wielkosc - 1;i++)     - nie tak, a tak:
        for(int i = 0; i < wielkosc;i++)
        {
                printf("%i ", tablica[i]);
        }
        printf("\n");
}
/*...*/
wyswietl(tablica, wielkosc);
  • w metodzie "zwartownikiem" załóż, że tablica jest o ten jeden element większa (czyli w zasadzie nic nie zmieniaj bo do tej pory było źle, ale w nowych warunkach ten kod będzie poprawny :) )

1 użytkowników online, w tym zalogowanych: 0, gości: 1