Δομές Δεδομένων Help...!

sn0u · 8 Ιουνίου 2007

Θα ήθελα μια βοήθεια στα παρακάτω προβλήματα. Ευχαριστώ .

Άσκηση 1

Υλοποιήστε τα παρακάτω:

Μια συνάρτηση fillArrayRandom(int A[],int length) που θα γεμίζει έναν πίνακα με τυχαία στοιχεία σε εύρος που εσείς θέλετε(π.χ. 0..19). Πώς θα μπορούσαμε να πετύχουμε τυχαίους αριθμούς σε range [m..n], m<n;(rand()%(n-m-1)+m)

Τροποποιήστε την παραπάνω συνάρτηση σε

fillArrayRandom2(int A[],int length, int range) που να παίρνει σαν παράμετρο και το εύρος των τιμών του πίνακα Α[].

Μια συνάρτηση fillArrayKeyboard(int A[],int length) που να γεμίζει έναν πίνακα με στοιχεία από το πληκτρολόγιο. Πως μπορούμε να μην οδηγούμαστε σε run time error εάν δώσουμε μη αποδεκτές τιμές; (π.χ. χαρακτήρες αντί αριθμούς)

Μια συνάρτηση find_min(int A[],int length), που βρίσκει το ελάχιστο στοιχείο του πίνακα Α[] και να επιστρέφει τη θέση του στον πίνακα.

Πώς θα μπορούσαμε να τροποποιήσουμε την find_min ώστε να «επιστρέφει» 2 τιμές; (και τη θέση του ελάχιστου και την ελάχιστη τιμή

Να κάνετε το ίδιο και για το μέγιστο στοιχείο του πίνακα.

Να φτιάξετε μια συνάρτηση sumArray(int A[],int length) που βρίσκει το άθροισμα των στοιχείων του πίνακα.

Να φτιάξετε μια συνάρτηση avArray(int A[], int length) που να υπολογίζει τον μέσο όρο των στοιχείων ενός πίνακα.

Αφού γεμίζουμε τον πίνακα με τυχαία στοιχεία συγκεκριμένου εύρους, π.χ. 0..κ-1, να φτιάξετε μια συνάρτηση που να βρίσκει τη συχνότητα εμφάνισης κάθε αριθμού(από το 0 μέχρι το κ-1 π.χ.) στον πίνακα Α[].

Όλα τα παραπάνω να καλούνται από ένα menu της παρακάτω μορφής:

1. fillArrayRandom

2. fillArrayRandom2

3. fillArrayKeyboard

4. find min element

5. find max element

6. find min element+position

7. find max element+position

8. μέσος όρος

9. Άθροισμα

10. Συχνότητα εμφάνισης αριθμών

11. Εκτύπωση πίνακα

12. Έξοδος

----------------------------------

Άσκηση 2

Serial search-binary search-bubble sort-recursion

1. Να φτιάξετε μια συνάρτηση ser_search(int A[], int length, int x) που να βρίσκει τη θέση του στοιχείου x στον πίνακα Α[], εάν υπάρχει, αλλιώς να επιστρέφει -1.

2. Τροποποιήστε την ser_search, έτσι ώστε να βρίσκει όλες τις εμφανίσεις του στοιχείου x (εάν υπάρχουν) στον πίνακα Α[].

3. Να γράψετε μια συνάρτηση void bubble(int A[],int length) που να ταξινομεί έναν πίνακα Α με length το πλήθος στοιχεία, με τη μέθοδο της φυσαλίδας (ευθεία ανταλλαγή).

4. Στο παραπάνω ερώτημα, και χρησιμοποιώντας τη συνάρτηση fillArrayRandom από την προηγούμενη άσκηση, να βρείτε τον αριθμό των αντιμεταθέσεων και των συγκρίσεων για πίνακες 50,500 και 5000 στοιχείων. Συμφωνούν οι τιμές που βρίσκετε με το θεωρητικό «κόστος» του αλγορίθμου Ο(n2).

5. Να γράψετε μια συνάρτηση bin_search(int A[],int length,int x) που να αναζητάτε το στοιχείο x στον πίνακα Α με τη μέθοδο της δυαδικής αναζήτησης (binary search). Μετρήστε το πλήθος των συγκρίσεων που γίνονται για πίνακες 50, 500 και 5000 στοιχείων αντίστοιχα. Επαληθεύεται το «κόστος» του αλγορίθμου Ο(logn);

6. Να υλοποιήστε μια συνάρτηση float power(int x, int y) που να υπολογίζει το x^y με επαναληπτικό και αναδρομικό τρόπο.

7. Να υλοποιήσετε την ακολουθία Fibonacci όπου αν=αν-1+αν-2 με α0=0 και α1=1.

8. Να υλοποιήσετε την binary search με αναδρομικό αλγόριθμο.

int binary_recursive(int A[],int left,int right);

-------------------------------------------------

Άσκηση 3

Συνεχίζοντας από την προηγούμενη άσκηση:

1. Υλοποιήστε την insertion sort.

2. Υλοποιήστε την selection sort. Μετρήστε κι εδώ τον αριθμό των επαναλήψεων και των αντιμεταθέσεων.

3. Να υλοποιήσετε την quicksort , παίρνοντας σαν pivot το πρώτο στοιχείο του πίνακα. Μετρήστε το πλήθος των επαναλήψεων-αντιμεταθέσεων.

4. Να υλοποιήσετε την «έξυπνη» εκδοχή της bubblesort και να κάνετε σύγκριση στο πλήθος επαναλήψεων με την απλή bubblesort. Τι παρατηρείτε;

5. Ξανατρέξτε το ερώτημα 4 της άσκησης 3 (τρεις πίνακες 50,500 και 5000 στοιχείων) για τις περιπτώσεις:

a. insertion sort

b. selection sort

c. quick sort (pivot=A[0])

6. Να υλοποιήσετε την interpolation search.(ο τύπος υπάρχει στις σημειώσεις του κ.Λουκόπουλου στο e-class, Θεωρία Δομές Δεδομένων)

7. Χρησιμοποιείστε έναν πίνακα 500 στοιχείων, από την προηγούμενη άσκηση, κάντε fillarray, μετά ταξινομήστε τον και στη συνέχεια κάντε αναζήτηση για στοιχεία με χρήση της binary search και της interpolation search. Να κάνετε σύγκριση ως προς τον αριθμό των αντιμεταθέσεων-επαναλήψεων της binary search και της interpolation search. Τι παρατηρείτε;

-------------------------------------------------

Άσκηση 4

Structs, Arrays of structs, files of structs

Σας ζητείται να φτιάξετε ένα πρόγραμμα για την γραμματεία του ΤΕΙ.

Θα χρησιμοποιήσετε μια struct foithths, με στοιχεία code,onoma,grade.

Να φτιάξετε ένα πίνακα με 1000 φοιτητές.

Να γίνει μενού με τις παρακάτω επιλογές:

1. εισαγωγή φοιτητή

2. αναζήτηση – παρουσίαση με βάση τον ΑΜ

3. αναζήτηση – παρουσίαση με βάση το ονοματεπώνυμο

4. Ταξινόμηση με βάση το όνομα

5. Ταξινόμηση με βάση τον αριθμό μητρώου

6. Ταξινόμηση με βάση το βαθμό

7. Έγγραφη σε αρχείο

8. Διάβασμα από αρχείο

9. Παρουσίαση όλων των φοιτητών

0. Έξοδος

Στην εισαγωγή φοιτητή να μην υπάρχουν διπλοεγγραφές.

Tip: χρησιμοποιείστε μια global μεταβλητή last, που θα δείχνει την επόμενη κενή θέση για εισαγωγή νέου φοιτητή. Οπότε για την παρουσίαση των φοιτητών αρκεί το loop:

for(i=0;i<last;i++)

printf(“%d %s %f\n”,foithths.code,foithths.name,foithths.grade);

Περισσότερες εξηγήσεις στα εργαστήρια….

Για εξάσκηση στα αρχεία, μπορείτε να φτιάξετε αρχικά ένα πρόγραμμα που θα γεμίζει έναν πίνακα ακεραίων, θα τον γράφει σε ένα αρχείο και μετά θα τον διαβάζει.

-------------------------------------------

Εργαστηριακή Ασκηση5

Linked Lists

Για αρχή, υλοποιήστε τις παρακάτω συναρτήσεις:

Struct node{

int val;

struct node *next;

}

void insert_list(struct node **head, int x);

void print_list(struct node *head);

int search_list(struct node *head, int x);

void delete_node(struct node **head, int x);

Στη συνέχεια, ξανα-υλοποιήστε την άσκηση 4 αλλά τώρα να χρησιμοποιήσετε αντί για πίνακα συνδεδεμένη λίστα:

Struct foithths{

int code;

char name[50];

float grade;

};

Να γίνει μενού με τις παρακάτω επιλογές:

1. εισαγωγή φοιτητή(στο τέλος της λίστας)

2. αναζήτηση φοιτητή

3. παρουσίαση φοιτητή

4. Διαγραφή φοιτητή

5. Έγγραφη σε αρχείο

6. Διάβασμα από αρχείο

7. Παρουσίαση όλων των φοιτητών

8. Έξοδος

Όπως βλέπετε δεν σας ζητείται να υλοποιήσετε τις ταξινομήσεις. Παρʼ όλα αυτά , πώς θα μπορούσαμε να ταξινομήσουμε μια απλά συνδεδεμένη λίστα;

Ποιος θα ήταν ένας πιο «έξυπνος» τρόπος να έχουμε τη λίστα μας πάντα ταξινομημένη;

Να σχολιάσετε το κόστος ταξινόμησης μιας λίστας, και «ταξινομημένης εισαγωγής».

---------------------------------------------

Άσκηση 6

1. Stacks

Να υλοποιήσετε μια δομή στοίβας. Δηλ. να γράψετε τις συναρτήσεις:

Initstack(?),pop(?),push(?).

Χρησιμοποιήστε αυτές τις συναρτήσεις για να μετατρέπετε έναν αριθμό από το δεκαδικό σύστημα στο δυαδικό.

2.Binary search trees

Ένα Binary search tree (Δυαδικό δένδρο αναζήτησης) είναι ένα δένδρο που το αριστερό υποδένδρο κάθε κόμβου περιέχει τιμές μικρότερες από τον κόμβο και το δεξί υποδένδρο περιέχει τιμές μεγαλύτερες από την τιμή του κόμβου.

Με βάση τον παρακάτω ορισμό του κόμβου του δένδρου,

struct tnode{

int val;

struct tnode *left;

struct tnode *right;

};

να υλοποιήσετε τις παρακάτω συναρτήσεις:

void insert_tree_node(struct tnode **root,int x);

void inorder(struct tnode *root);

void preorder(struct tnode *root);

void postorder(struct tnode *root);

3.Εφαρμογη των δυαδικών δένδρων αναζήτησης.

α)Φτιάξτε εάν πίνακα 30 στοιχείων με ακεραίους με τυχαίες τιμές από το 0 μέχρι το 99.

β)Γράψτε τα στοιχεία του πίνακα σε ένα αρχείο. Διαβάστε το αρχείο και κάντε εισαγωγή τα στοιχεία που διαβάζετε σε ένα Δυαδικό Δένδρο Αναζήτησης.

γ)Διαπεράστε το δένδρο με την inorder, preorder και postorder. Τι παρατηρείτε στην διαπέραση inorder;

.

takeda · 8 Ιουνίου 2007

άσε και το όνόμα καθηγητή να πάμε να την παραδώσουμε κιολας

καφεδάκι πως το πίνεις;

bokarinho · 8 Ιουνίου 2007

Ε είπαμε να σε βοηθήσουμε στην άσκηση αλλά τι περιμένεις δηλαδή να στα λύσουμε όλα; Δεν καταλαβαίνω, δώσε κώδικα να δω προσπάθεια και θα βοηθήσω τα μέγιστα.

dalton85 · 8 Ιουνίου 2007

Αμαν. Μηπος θες να ερθουμε να γραψουμε και για σενα θεωρια. Κανα αλλο μαθημα?

Meredoth · 8 Ιουνίου 2007

Ετσι παντα ο ελλήνας να την βγαλει καθαρη με τον ευκολο τρόπο.

xpapias · 8 Ιουνίου 2007

καφεδάκι πως το πίνεις;

:-P :-P :-P

eirinikp · 8 Ιουνίου 2007

Enta3ei bre paidia, min koroideuete! Kakws esteile oli tin ergasia o sn0u, alla skefteite oti autin tin periodo oloi pnigomaste me proetoimasia gia tin e3etastiki kai projects. Den ton dikaiologw alla otan den prolabaineis oute na koimi8eis, katafeugeis se mi nomima mesa...

Den 3erw an pragmati eisai se auti tin katastasi sn0u, alla an eisai tote de nomizw oti prepei na sou paroume to kefali. Frontise na baleis se mia ta3i to programma sou kai elpizw na ta prolabeis ola!

An bebaia ola ta parapanw den isxuoun kai eisai... loufa kai paralagi, tote sumfwnw kai epau3anw me olous tous parapanw!!!

bokarinho · 8 Ιουνίου 2007

Παρακάτω βρίσκεται ο κώδικας για όλο το πρώτο ερώτημα σου. Ελπίζω να σου φανεί χρήσιμος, το μόνο που πρέπει να κάνεις είναι να φτιαξεις το μενού και μετά να καλείς τις συναρτήσεις όπως θέλεις. Αν θες περαιτέρω βοήθεια γιατί όντως δεν προλαβαίνεις στείλε μήνυμα!!

>
//Bokarinho Version 1st Exercise

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>

//Functions Statements.
int *CreateArray(int length);
int FillArrayRandom(int *A, int length, int range);
void PrintArray(int *A, int length);
int FillArrayRandom2(int *A, int length, int m, int n);
int FillArrayRandom3(int *A, int length, int n, int m);
int FillArrayFromKeyboard(int *A, int length);
int FindMinElement(int *A, int length, int *index);
int FindMaxElement(int *A, int length, int *index);
int* Histogram(int* A, int Alen, int low, int high);
int SumElementsofArray(int *A, int Alen);
float AverageOfSumElements(int *A, int Alen);

int main(int argc, char *argv[])
{
int minIndex = 0, maxIndex = 0;
int *p = CreateArray(10);
//FillArrayFromKeyboard(p,10);
FillArrayRandom2(p, 10, 2, 6);
FindMinElement(p,10,&minIndex);
printf("Minimun element of the array is %d in place %d\n",p[minIndex],minIndex);
FindMaxElement(p,10,&maxIndex);
printf("Maximun element of the array is %d in place %d\n",p[maxIndex],maxIndex);
PrintArray(p,10);
{
	int* h = Histogram(p, 10, p[minIndex], p[maxIndex]);
	int hlen = p[maxIndex] - p[minIndex] + 1;
	int i = 0;
	printf("Frequencies:\n");
	for(i = 0; i < hlen; i++)
	{
		printf("f(%d) = %d\n", i + p[minIndex], h[i]);
	}
}
{
       int value = SumElementsofArray(p,10);
       float average  = AverageOfSumElements(p,10);
       printf("Sum is %d and avarage is %f\n",value,average);
       } 
getchar();
return 0;
}

int *CreateArray(int length)
{
int *p = (int*)calloc(length,sizeof(int));
if(p)
	return p;
else
	return NULL;
}
int FillArrayRandom(int *A, int length, int range)
{
if(A)
{
	if(length > 0)
	{
		int i = 0;
		srand(time(NULL));
		for(i = 0; i < length; i++)
			A[i] = rand() % range;
		return 0;
	}
	else
	{
		printf("Size of input array must be more than zero.\n");
		return -1;
	}
}
else
{
	printf("Memory Fault.\n");
	return -2;
}
}
int FillArrayRandom2(int *A, int length, int m, int n)
{
if(A)
{
	if(length > 0)
	{
		if(n > m)
		{
			int i = 0;
			int range = n - m -1;
			srand(time(NULL));
			for(i = 0; i < length; i++)
				A[i] = (rand() % range) + m;
			return 0;
		}
		else
		{
			printf("Syntax Error, Check the given range limits.\n");
			return -1;
		}
	}
	else
	{
		printf("Size of input array must be more than zero.\n");
		return -2;
	}
}
else
{
	printf("Memory Fault.\n");
	return -3;
}
}
int FillArrayRandom3(int *A, int length, int m, int n)
{
if(A)
{
	if(length > 0)
	{
		if(n > m)
		{
			int i = 0;
			int j = 0;
			int range = n - m -1;
			srand(time(NULL));
			do
			{
				A[i] = (rand() % range) + m;
				for(j = 0; j < i && A[j] != A[i]; j++);
				if(i == j)
					i++;
			}while(i < length);
			if(i == length)
				return 0;
		}
		else
		{
			printf("Syntax Error, Check the given range limits.\n");
			return -1;
		}
	}
	else
	{
		printf("Size of input array must be more than zero.\n");
		return -2;
	}
}
else
{
	printf("Memory Fault.\n");
	return -3;
}
}

void PrintArray(int *A, int length)
{
if(A)
{
	int i = 0;
	while(i < length)
	{
		printf("A[%d]  =  %d\n",i,A[i]);
		i++;
	}
}
}
int FillArrayFromKeyboard(int *A, int length)
{
if(A)
{
	if(length > 0)
	{
		int i = 0; 
		int j = 0;
		char buffer[40] = {0};
		char usedBuffer[40] = {0};
		char *p = NULL;
		while(i < length)
		{
			j = 0;
			printf("Give me the number to insert in the %d place of the array:",i);
			if(fgets(buffer,40,stdin) != NULL)
			{
				for(p = buffer;*p; p++)
				{
					if(isdigit(*p))
						usedBuffer[j++] = *p;
				}
				if(!j)
				{
					printf("Error, Enter a valid number from keyboard.\n");
					continue;
				}
				else
				{
					usedBuffer[j] = '\0';
					A[i++] = atoi(usedBuffer);
				}
			}
		}
		return 0;
	}
	else
	{
		printf("Size of input array must be more than zero.\n");
		return -1;
	}
}
else
{
	printf("Memory Fault.\n");
	return -2;
}
}
int FindMinElement(int *A, int length, int *index)
{
if(A)
{
	if(length > 0)
	{
		int i = 0;
		int j = 0;
		int min = 0;
		min = A[0];
		for(i = 0; i < length; i++)
		{
			if(A[i] < min)
			{
				min = A[i];
				*index = i;
			}
		}
		return min;
	}
	else
		return -1;
}
else
	return -2;
}
int FindMaxElement(int *A, int length, int *index)
{
if(A)
{
	if(length > 0)
	{
		int i = 0;
		int j = 0;
		int max = 0;
		max = A[0];
		for(i = 0; i < length; i++)
		{
			if(A[i] > max)
			{
				max = A[i];
				*index = i;
			}
		}
		return max;
	}
	else
		return -1;
}
else
	return -2;
}

int* Histogram(int* A, int Alen, int low, int high)
{
int i;
int hlen = high - low + 1;
int* h = calloc(hlen, sizeof(int));
for (i = 0; i < Alen; i++)
{
	if (A[i] >= low && A[i] <= high)
		h[A[i] - low]++;
}
return h;
}
int SumElementsofArray(int *A, int Alen)
{
   if(A)
   {
        if(Alen)
        {
                int i = 0;
                int value = 0;
                for(i = 0; i < Alen; i++)
                      value += A[i];
                if(i == Alen)
                return value;
        }
        else
        return -1;
   }
   else
   return -1;
}
float AverageOfSumElements(int *A, int Alen)
{
   if(A)
   {
        if(Alen)
        {
                int sum = SumElementsofArray(A,Alen);
                float average = (float)sum / Alen;
                return average;
        }
        else
        return -1;
   }
   else
   return -1;
}

Είμαστε εδώ για να βοηθάμε αλλά όχι να μας περάσουνε και για @@κες.

Σύνδεση

Δομές Δεδομένων Help...!

Προτεινόμενες αναρτήσεις

sn0u

takeda

bokarinho

dalton85

Meredoth

xpapias

eirinikp

bokarinho

Αρχειοθετημένο

Σύνδεση