-------- Hash Tabellen ----- in C Algorithmen

Privet vsem:

Nedavno poluchili Sadanee: No k sozeleniu ya nimagu rasobratsy s nim i nash Proff. kak naslo ne chego tolkam ne obesnil da i sabalel k tamuze. A nan Eto sdat na sleducei Nedeli nado.

Thema: Hash-Tabelle. Kto imeet opit s etim i chto eto takoe. I kak ego est.

Mozet kto forum ili Literaturu posovetaet...

Samo Sadanie:

Thema: Gestreute Speicherung

Schreiben Sie ein Programm, das Adressen in einer binäre Direkt-Datei Adr.Dat zur Speicherung von Adressen mit folgendem Inhalt je Datensatz anlegt:

Name 15 Zeichen
Vorname 15 zeichen
Strasse 15 Zeichen
PLZ 5 Zeichen
Telefon 15 Zeichen

Es sollen Adressen eingegeben und unter Vorgabe der ersten vier Buchstaben des Namens als Suchschlüssel ausgegeben, verändert und gelöscht werden können. Da die ersten vier Buchstaben keinen eindeuitigen Suchschlüssel darstellen, muß bei der Suche nach einem Datensatz auf die weiteren Datensätze mit gleichem Suchschlüssel zugegriffen werden können.

Die Hausadresse des Satzes errechne man nach der Divisionsrest-Methode(Hashfunktion). Die Größe des Adreßbereiches betrage 59 (Primzahl!). Zur Kollisionsbehandlung setze man das Verfahren der linearen Sondierung ein.

Wird ein Datensatz gelöscht, so ist er lediglich als gelöscht zu markieren( Name(1:4)='ZZZZ').

Wird ein Datensatz geändert,so muß der Datensatz zumindest bei der Änderung der ersten vier Zeichen des Namens zunächst gelöscht und dann neu eingefügt werden!

Nu kak? Kto nibud snaet kak podoiti?

Spasibo vsem

Wolf

chesno govorj ya ne sovsem ponel chto ti imeesh v vidu....

Trotzdem Danke für deine Mühe und Zeit...

Wolf

Bolshoe Spasibo tebe Wolfenstein. Ya rad chto-est ludi gotovie Pomoch.

Da chatel sprosit, ti ne novichok. V etom dele. Mozesh Literaturu Posovetovat???

V rasdele Algorithmen und Datenstruckturen.

Ya sdes nashel odin Knizniy Magasin, ceni v dva rasa nize.

Posmotri: Пожалуйста зарегистрируйся для просмотра данной ссылки на страницу.

Esli sprogramiruu segodny obesatelno postovly Quelltext komu interessno. Spasibo...

Wolf

spasibo mvital,

sa sovet,
da no mne nado pisat v datei vse. Nu a esli ya Adressa sanesu v array to pri novom sapuske programmi. To etot array gde chranjtsy adressa ne budet naiden.(Arbeitspeicher)

Eto snachit chto i array s adressami nado toze v fail pisat. Ili

spasibo
Wolf

Ya tut voskresenie sidel i vchera do trech ece.

No poluchilos rabotaet a vot Quelltext:

Tak chto Spasibo vsem, sa charochuu informaciu.

Esli interesno to ya mogu postavit sleducee sadanie.

Kak vi dumaete. Esli kto Hochet...?

Tak mozno posmotret u kogo kakay technika programirovaniy..

Wolf

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

struct Daten{
char nname [15+1];
char vname [15+1];
char str [15+1];
char plz [ 5+1];
char telef [15+1];
};

const int block=sizeof(struct Daten);
FILE* init_feld(void);
void einlesen(struct Daten *neu);
int convert_key(char key[]);
int kolision (int adresse, FILE *fp);
int suchen (struct Daten *tmp, FILE *fp, int adresse, char key[]);
void ausgabe (struct Daten *tmp);
void del_daten (struct Daten *tmp);
int belegt (int arresse, FILE *fp);
void write (struct Daten *tmp, int adresse, FILE *fp);
int eintrag (void);
void fehler (int f);

int main(void)
{
FILE *P;

int adresse, f;
char Auswahl, Name[15+1];
struct Daten tmp;

do{
system("cls");
printf("\t\t MENU");
printf("\n\n");
printf("\n\t\t1 ---- ---- Mitglied eintragen");
printf("\n\t\t2 ---- ---- Mitgliedsdaten ausgeben");
printf("\n\t\t3 ---- ---- Mietgliedsdaten verändern");
printf("\n\t\t4 ---- ---- Mieglied loschen");
printf("\n\t\t5 ---- ---- Programm verlassen");

printf("\n\nIhre Auswahl: ");
Auswahl=getchar(); rewind(stdin);

switch(Auswahl)
{
case '1':
{
system("cls");
printf("\t\t\tMIETGLIED EINTRAGEN");
P=init_feld();
einlesen(&tmp);
adresse=convert_key(tmp.nname);
f=kolision(adresse, P);
if(f==0) write(&tmp, adresse, P);
if(f!=0) fehler(f);
fclose(P);
break;
}
case '2':
{
system("cls");
printf("\t\t\tMITGLIEDSDATEN AUSGEBEN");
P=init_feld();
printf("\nBitte Name eingeben: ");
scanf("%15[^\n]", Name); rewind(stdin);
adresse=convert_key(Name);
f=suchen(&tmp, P, adresse, Name);
if(f==0)
{
printf("\nDatensatz wurde erfolgreich gefunden\n");
ausgabe(&tmp);
}
if(f!=0) fehler(f);
fclose(P);
break;
}
case '3':
{
system("cls");
printf("\t\t\tMITGLIEDSDATEN VERÄNDERN");
P=init_feld();
printf("\nBitte Name eingeben: ");
scanf("%15[^\n]", Name); rewind(stdin);
adresse=convert_key(Name);
f=suchen(&tmp, P, adresse, Name);
if(f==0)
{
printf("\nDatensatz wurde erfolgreich gefunden\n");
ausgabe(&tmp);
printf("\nDatensatz andern? (j/n)");
Auswahl=getchar(); rewind(stdin);
if(Auswahl=='N' Auswahl=='n')
{
fclose(P); break;
}
system("cls");
del_daten(&tmp);
write(&tmp, adresse, P);
printf("\t\t\tNEU DATEN LAUTEN:");
einlesen(&tmp);
adresse=convert_key(tmp.nname);
f=kolision(adresse, P);
if(f==0) write(&tmp, adresse, P);
if(f!=0) fehler(f);
fclose(P); break;
}
if(f!=0) fehler(f);
fclose(P); break;
}
case '4':
{
system("cls");
printf("\t\t\tMITGLIED AUS DER LISTE ENTFERNEN");
P=init_feld();
printf("\nBitte Name eingeben: ");
scanf("%15[^\n]", Name); rewind(stdin);
adresse=convert_key(Name);
f=suchen(&tmp, P, adresse, Name);
if(f==0)
{
printf("\nDatensatz wurde erfolgreich gefunden\n");
ausgabe(&tmp);
printf("\nMietglied löschen? (j/n)");
Auswahl=getchar(); rewind(stdin);
if(Auswahl=='N' Auswahl=='n')break;
if(Auswahl=='J' Auswahl=='j')
{
del_daten(&tmp);
write(&tmp, adresse, P);
printf("\nMietglied wurde erfolgreich geloscht...");
printf("\nWeiter mit ENTER Taste");
getchar(); rewind(stdin);
}
}
if(f!=0) fehler(f);
fclose(P); break;
}
}
}while(Auswahl!='5');

return 0;
}

FILE* init_feld(void)
{
int i;
struct Daten tmp;
FILE *fp=fopen("Adr.dat", "rb");

if(fp==NULL)
{ printf("\nDie Datei exestiert nicht");
printf("\nDatei wird angelegt......");
printf("\nWeiter mit ENTER Taste...");
getchar(); rewind(stdin);
fp=fopen("Adr.dat", "wb+");
del_daten(&tmp);
for(i=0; i<59; i++)
{
rewind(fp);
fseek(fp, i*block, SEEK_SET);
fwrite(&tmp, block, 1, fp);
}
}
fclose(fp);
fp=fopen("Adr.dat", "rb+");
return(fp);
}

void del_daten(struct Daten *tmp)
{
int i=0;
for(i=0; i<15; i++)
{
tmp->nname[i]= ' ';
tmp->vname[i]= ' ';
tmp->str [i]= ' ';
tmp->telef[i]= ' ';
}
for(i=0; i<5; i++) tmp->plz[i]=' ';

for(i=0; i<4; i++) tmp->nname[i]='Z';

return;
}

int kolision (int adresse, FILE *fp) // Algorithmus - "Lineare Sondierung"
{
int m, n=1; // Schrittzahl n
for(;;)
{
m=belegt(adresse, fp); // 1 - nicht belegt(gelöscht markiert), 0 - belegt
if(m==1) return 0; // Speicherzelle gefunden
if(adresse==58) adresse=0; // adresse==58 dann wird adresse zu 0 gemacht
if(adresse<58) adresse++; // adresse=adresse+1 jedesmal bis 59

if(n==59) return (-3); // Datei ist voll
n++; // Anzahl der bereits besetzten Felder
}
return 0;
}

int convert_key(char key[]) // Konvertierung ( Name -> Key -> Hausadresse)
{
return ((((key[0]*256+key[1])*256+key[2])*256+key[3])%59);
}

void einlesen(struct Daten *neu)
{
char Auswahl;
do{
printf("\n");
printf("Bitte Name eingeben: ");
scanf("%15[^\n]", neu->nname); rewind(stdin);
printf("Bitte Vorname eingeben: ");
scanf("%15[^\n]", neu->vname); rewind(stdin);
printf("Bitte Strasse eingeben: ");
scanf("%15[^\n]", neu->str); rewind(stdin);
printf("Bitte PLZ eingeben: ");
scanf("%5[^\n]", neu->plz); rewind(stdin);
printf("Bitte die Telefonnummer eingeben: ");
scanf("%15[^\n]", neu->telef); rewind(stdin);
printf("\n\nSind die Daten korrekt? (j/n)");

Auswahl=getchar(); rewind(stdin);

}while(Auswahl!='j');

return;
}

void ausgabe(struct Daten *tmp)
{
printf("\nName: \t%s", tmp->nname);
printf("\nVorname: \t%s", tmp->vname);
printf("\nStrasse: \t%s", tmp->str);
printf("\nPLZ: \t%s", tmp->plz);
printf("\nTelefon: \t%s", tmp->telef);

printf("\n\nWeiter mit ENTER Taste");
getchar(); rewind(stdin);
return;
}

int belegt(int adresse, FILE *fp) // 1 - nicht belegt oder als gelöscht markiert, 0 - belegt
{
int x=0, i;
struct Daten temp;

rewind(fp);
fseek(fp, adresse*block, SEEK_SET);
fread(&temp, block, 1, fp);
for(i=0; i<4; i++)
{
if(temp.nname[i]=='Z') x++;
}
return x==4;
}

void write(struct Daten *tmp, int adresse, FILE *fp)
{
rewind(fp);
fseek(fp, adresse*block, SEEK_SET);
fwrite(tmp, block, 1, fp);
return;
}

void fehler(int f)
{
if(f==-3)
{
printf("\nDie Datei ist voll...........");
printf("\nBitte entfernen Sie ein Mitglied aus der Liste");
printf("\nWeiter mit ENETER Taste");
getchar(); rewind(stdin); return;
}
if(f==-1)
{
printf("\nFehler in der Datei");
printf("\nWeiter mit ENTER Taste");
getchar(); rewind(stdin); return;
}
if(f==-2)
{
printf("\nMietglied konnte nicht gefunden werden");
printf("\nWeiter mit ENTER Taste");
getchar(); rewind(stdin); return;
}
return;
}

int suchen(struct Daten *tmp, FILE *fp, int adresse, char key[])
{
int n=1;
for(;;)
{
rewind(fp);
fseek(fp, block*adresse, SEEK_SET);
fread(&(*tmp), block, 1, fp);

if(strcmp(key, tmp->nname)==0) return 0; // suche war erfolgreich
if(adresse==58) adresse=0; // adresse==58 dann wird adresse zu 0 gemacht
if(adresse<58) adresse++; // adresse=adresse+1 jedesmal bis 59

if(n==59 belegt(adresse, fp)==1) return (-2); // 1 - nicht belegt, Suche erfolglos
n++;
}
}

Lutsche Anhahng posmotrite: A to chtoto pri Einfügen u meny ves text po shvam rasasholsy.. :lol:

Wolf

an ter:
eta neplochay Algorithmen und Datenstrukturen Programmieren

Spasibo

Wolf