coach

#include <stdio.h>
#include <stdlib.h>

int* InterpolationSearch(int *arrkey, int *arrvalid, int duzina, int x) {

	int start, end, pos, r;
	start = 0; end = duzina - 1;

	while (start <= end && x >= arrkey[start] && x <= arrkey[end]) {
		if ((x - arrkey[start]) !=0) {
			pos = start + (((end - start) / (arrkey[end] - arrkey[start])*(x - arrkey[start])));
		}
		else { pos = start; }
		if ((arrkey[pos] == x) && (arrvalid[pos] == 1)) { return pos; }
		else if ((arrkey[pos] == x) && (arrvalid[pos] == 0)) {
			for (r = pos - 1; ; r--) {
				if ((arrkey[r] == x) && (arrvalid[r] == 1)) { return r; }
			}
		}
		else if (x > arrkey[pos]) start = pos + 1;
		else end = pos - 1;
	}
	return -1;
}

int* InterpolationSearchM(int *arrkey, int *arrvalid, int duzina, int y) {

	int start, end, pos=0, r, max;
	start = 0; end = duzina - 1;
	max = end;
	while (start <= end && y >= arrkey[start] && y <= arrkey[end]) {

		pos = start + (((end - start) / (arrkey[end] - arrkey[start])*(y - arrkey[start])));
		if ((arrkey[pos] == y) && (arrvalid[pos] == 1)) { return pos; }
		else if ((arrkey[pos] == y) && (arrvalid[pos] == 0)) {
			for (r = pos - 1; ; r--) {
				if ((arrkey[r] == y) && (arrvalid[r] == 1)) { return r; }
			}
		}
		else if (y > arrkey[pos]) start = pos + 1;
		else end = pos - 1;
	}
	if (y < arrkey[0]) { return pos = 0; }
	else if (y > arrkey[max]) { return pos = max; }
	else { return pos; }
}

int FreeLocation(int *arrvalid, int duzina, int npos) {

	for (int i = npos; i < duzina; i++) if (arrvalid[i] == 0) return 1;
	return 0;
}

int* InsertKey(int *arrkey, int *arrvalid, int duzina, int y) {

	int npos, p = 0, z, o;
	if (InterpolationSearch(arrkey, arrvalid, duzina, y) != -1) {
		printf("\nKljuc koji zelimo da umetnemo postoji ");
		return arrkey, arrvalid;
	}
	else {
		npos = InterpolationSearchM(arrkey, arrvalid, duzina, y);
		if (arrvalid[npos] == 1) {
			if (FreeLocation(arrvalid, duzina, npos) == 1) {
				int t, i;
				t = npos;
				if (y < arrkey[npos]) {
					npos += 1;
					while (arrvalid[npos] == 1) {
						npos++;
					}
					for (i = npos; i >= t; i--) {
						arrkey[i] = arrkey[i - 1];
						arrvalid[i] = arrvalid[i - 1];
					}
				}
				else {

					npos -= 1;
					while (arrvalid[npos] == 1) {
						npos--;
					}
					for (i = npos; i<=t; i++) {
						arrkey[i] = arrkey[i + 1];
						arrvalid[i] = arrvalid[i + 1];
					}
				}
				arrkey[t] = y;
				arrvalid[t] = 1;
				printf("\nNpvi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrkey[i]);
				}
				printf("\nNovi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrvalid[i]);
				}
				return arrkey, arrvalid;
			}
			else {
				int duzina2, j = 0, j2 = 0, l, brj = 0, k = 0, i, u, t; duzina2 = 2 * (duzina+1);
				for (l = 0; l < duzina; l++) {
					if (arrvalid[l] == 1) brj++;
				}
				brj += 1;
				int *niz = calloc(brj, sizeof(int));
				for (l = 0; l < (duzina+1); l++) {
					if (arrvalid[l] == 1) {
						niz[j] = arrkey[l];
						j++;
					}
					if ((brj-1) == l) { niz[j] = y; }
				}

				for (i = 0; i < brj - 1; i++)
					for (u = i + 1; u < brj; u++)
						if (niz[i] > niz[u]) {
							t = niz[i];
							niz[i] = niz[u];
							niz[u] = t;
						}

				arrkey = realloc(arrkey, duzina2 * sizeof(int));
				arrvalid = realloc(arrvalid, duzina2 * sizeof(int));

				int fu = duzina2 / brj;
				for (j = 0; j < brj; j++) {
					int br1 = 0;
					while (br1 < fu) {
						arrkey[k] = niz[j];
						br1++;
						k++;
					}
				}
				 printf("\nNiz elemenata je: ");
				 for (i = 0; i < duzina2; i++) {
					 printf("%d ", arrkey[i]);
				 }
				for (i = 0; i < brj; i++) {
					int br2 = 0;
					arrvalid[j2] = 1;
					while (br2 < fu) {
						j2++;
						arrvalid[j2] = 0;
						br2++;
					}
				}
				printf("\nNiz elemenata je: ");
				for (i = 0; i < duzina2; i++) {
					printf("%d ", arrvalid[i]);
				}
				return arrkey, arrvalid, duzina2;
			}
		}
		else {
			o = npos;
			while (arrvalid[--o] == 0) {
				p++;
			}
			p = p / 2;
			z = npos - p;
			arrkey[z] = y;
			arrvalid[z] = 1;
			z += 1;
			while (arrvalid[z] == 0) {
				arrkey[z] = y;
				arrvalid[z] = 0;
				z += 1;
			}
			printf("\nNpvi niz elemenata je: ");
			for (int i = 0; i < duzina; i++) {
				printf("%d ", arrkey[i]);
			}
			printf("\nNovi niz elemenata je: ");
			for (int i = 0; i < duzina; i++) {
				printf("%d ", arrvalid[i]);
			}
			return arrkey, arrvalid;
		}
	}

}



void Delete(int *arrkey, int *arrvalid, int duzina, int e) {

	int npos, p = 0, z, o;
	if (InterpolationSearch(arrkey, arrvalid, duzina, e) == -1) {
		printf("\nKljuc koji zelimo da obrisemo ne postoji ");
		return arrkey, arrvalid;
	}
	else {
		npos = InterpolationSearch(arrkey, arrvalid, duzina, e);
		if (npos == 0) {
			arrvalid[npos] = 0;
			npos += 1;
			while (arrvalid[npos] == 0) {
				npos++;
			}
			int d = arrkey[npos];
			npos -= 1;
			while (arrvalid[npos] == 0) {
				arrkey[npos] = d;
				npos--;
			}
		}
		else {
			arrvalid[npos] = 0;
			int t = npos, k;
			npos -= 1;
			k = arrkey[npos];

			while (arrvalid[t] == 0) {
				arrkey[t] = k;
				t++;
			}
		}
	}
	return arrkey, arrvalid;
}

int main() {

	int *niz, i, j = 0, n, fu, k = 0, index, x, t, u, y, nkey, izbor, e;

	while (1) {
		printf("\n1. Inicijalno formiranje povecane tabele\n"
			"2. Pretraga elementa\n"
			"3. Ubacivanje elementa\n"
			"4. Brisanje elementa\n"
		);
		scanf("%d", &izbor);

		switch (izbor) {

		case 1: printf("Duzina niza je: ");
			scanf("%d", &n);

			niz = calloc(n, sizeof(int));
			if (niz == NULL) {
				printf("Greska u alokaciji!\n");
				exit(1);
			}

			printf("Faktor uvecanja je: ");
			scanf("%d", &fu);
			printf("Niz elemenata je: ");
			for (i = 0; i < n; i++) {
				scanf("%d", &niz[i]);
			}
			printf("Niz elemenata je: \n");
			for (i = 0; i < n; i++) {
				printf("%d ", niz[i]);
			}

			for (i = 0; i < n - 1; i++)
				for (u = i + 1; u < n; u++)
					if (niz[i] > niz[u]) {
						t = niz[i];
						niz[i] = niz[u];
						niz[u] = t;
					}

			printf("\nSortirani niz elemenata je: ");
			for (i = 0; i < n; i++) {
				printf("%d ", niz[i]);
			}

			int duzina;
			duzina = n * fu;
			int *arrkey, *arrvalid;

			arrkey = calloc(n * fu, sizeof(int));
			if (arrkey == NULL) {
				printf("Greska u alokaciji!\n");
				exit(1);
			}

			for (i = 0; i < n; i++) {
				int br1 = 0;
				while (br1 < fu) {
					arrkey[k] = niz[i];
					br1++;
					k++;
				}
			}
			printf("\nNiz elemenata je: ");
			for (i = 0; i < duzina; i++) {
				printf("%d ", arrkey[i]);
			}

			arrvalid = calloc(n * fu, sizeof(int));
			if (arrvalid == NULL) {
				printf("Greska u alokaciji!\n");
				exit(1);
			}

			for (i = 0; i < n; i++) {
				int br2 = 0;
				arrvalid[j] = 1;
				while (br2 < fu) {
					j++;
					br2++;
				}
			}
			printf("\nNiz elemenata je: ");
			for (i = 0; i < duzina; i++) {
				printf("%d ", arrvalid[i]);
			}
			break;
		case 2:printf("\nPotrebno je naci element: ");
			scanf("%d", &x);
			index = InterpolationSearch(arrkey, arrvalid, duzina, x);

			printf("Element je na poziciji: %d", index);
			break;
		case 3: printf("\nElement koji zelimo da umetnemo: ");
			scanf("%d", &y);
			nkey = InsertKey(arrkey, arrvalid, duzina, y);
			/*	printf("\nNpvi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrkey[i]);
				}
				printf("\nNovi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrvalid[i]);
				}*/
			break;
			case 4: printf("\nElement koji zelimo da obrisemo: ");
				scanf("%d", &e);
				Delete(arrkey, arrvalid, duzina, e);
				printf("\nNpvi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrkey[i]);
				}
				printf("\nNovi niz elemenata je: ");
				for (i = 0; i < duzina; i++) {
					printf("%d ", arrvalid[i]);
				}
				break;

		}
	}
}