program ma za zadanie przechowywac przedzialy liczb rzeczywistych (obustronnie domkniete) w kolejce (mozna zalozyc ze beda podawane rosnaco, ale wskazane jest zeby nie). Nastepnie program ma zapytac o jakas liczbe rzeczywista i znalezc przedzial do ktorego ta liczba nalezy, przy czym wyrzukiwanie musi byc wydajniejsze niz O(n)... czyli lepsze niz liniowe przejescie while'em po wszystkich przedzialach.. Znam jeszcze bisekcje ale ona sie nadaje do tablic... Czy macie pomysl na jakis inny algorytm wyszukiwania? z gory wielkie dzieki
# include <conio.h>
# include <cstdio>
# include <cstdlib>
# include <iostream>
# include <cstring>
using namespace std;
struct kolejka {
double x1,x2;
kolejka *ref;
};
kolejka *pointer;
kolejka *tmp;
kolejka *tmp2;
kolejka *first; //wskaznik do pierwszego elementu kolejki
void dodaj_element(double _x1, double _x2)
{
int flag = 1;
tmp2=first;
while (tmp2 != NULL) {
if (!(_x2 < tmp2->x1 || _x1 > tmp2->x2)) {
flag = 0;
printf("\nPrzedzial nie jest rozlaczny z jednym z juz istniejacych.\n");
}
tmp2=tmp2->ref;
}
if (flag) {
tmp=new kolejka;
tmp->ref=NULL;
tmp->x1 = _x1;
tmp->x2 = _x2;
if (pointer == NULL) first=tmp;
else pointer->ref = tmp;
pointer=tmp;
}
}
void skasuj_element()
{
if (first!=NULL) {
tmp=first->ref;
printf("\nUsunieto: <%d;%d>\n",first->x1,first->x2);
delete first;
first=tmp;
} else {
printf("Kolejka jest pusta.\n");
}
}
void wyswiet_kol()
{
printf("\n\nZawartosc kolejki:\n");
tmp=first;
while (tmp!=NULL) {
cout << "x1 = " << tmp->x1 << ", x2 = " << tmp->x2 << endl;
tmp=tmp->ref;
}
}
void oproznij_kol() {
while (first!=NULL)
skasuj_element();
printf("\nKolejka oczyszczona.\n\n");
}
void wyszukaj_przedzial () {
// ????
}
int main() {
double x1, x2;
char operation = '\0';
do {
printf("\nWybierz operacje ktora chcialbys wykonac: "
"\n'A' aby dodac przedzialy do kolejki wprowadz kolejno lewa i prawa krawedz przedzialu (domkniete)"
"\n'B' aby skasowac pierwszy przedzial z kolejki"
"\n'C' aby wypisac przedzialy zawarte w kolejce"
"\n'D' aby usunac wszystko i zakonczyc program\n"
);
scanf("%c",&operation);
if (operation == 'A') {
printf("Dane: \nx1 = ");
scanf("%d",&x1);
printf("x2 = ");
scanf("%d",&x2);
dodaj_element(x1,x2);
} else if (operation == 'B') {
skasuj_element();
} else if (operation == 'C') {
wyswiet_kol();
}
} while (operation != 'D');
// schemat:
// printf("Podaj liczbe a zostanie zwrocony przedzial");
// wyszukaj_przedzial();
oproznij_kol();
system("pause");
return 0;
}