Telefonbuch

SeppJ

beginner_offl schrieb:

Das würd mich jetzt auch interessieren... Werden Verkettete Listen "oft" benutzt in der Praxis, bzw. von Euch Profis?

Nein, verkettete Listen sind eine typische Hausaufgabenstruktur. Man sieht halt mal, dass es mehr auf der Welt gibt als nur Arrays und man kann schön Pointer und malloc üben, aber es ist nicht gleich so kompliziert wie eine Baumstruktur. Anschließend kann man dann noch schön über Komplexitätsklassen reden und gucken, welche Datenstruktur wo ihre Vorteile hat.
Insgesamt ergibt sich dann theoretisch ein sehr schönes Bild:
-Einfügen/Ausklinken an egal welcher Stelle in O(1), egal wie viele Elemente
-Iterieren ebenfalls O(1) (für den Sprung von einem Element zum nächsten)
Also: Klar besser, als ein einfaches Array, oder? Schließlich ist Einfügen/Löschen schneller, Iterieren genau so schnell, und den wahlfreien Zugriff des Arrays braucht man nicht immer.
Aber:
-Zum Einfügen/Ausklinken muss man normalerweise erst die passende Stelle finden, was dann wieder O(N) ist.
-Praktisch ist das Iterieren zwar O(1), aber die Konstante ist im Vergleich zu anderen Strukturen sehr groß.
Und: Man muss meist sehr viel häufiger auf den Inhalt zugreifen, als man Einfügen/Löschen muss. Da haut dann der lahme Zugriff richtig rein.
Die Liste ist also dann relevant, wenn man fast nur mit Einfügen/Löschen beschäftigt ist und Zugriffe nur selten und möglichst nur ganz am Anfang oder Ende hat. Ansonsten fährt man oft mit anderen Strukturen wie Arrays besser. Dann muss man eben notfalls mal eine teure Einfügeaktion schlucken. Aber Einfügen/Löschen in der Mitte hat man in der Praxis eben auch eher selten, weil man seine Daten so ordnen kann, dass diese nur am Anfang/Ende auftreten, wo wieder andere Strukturen dies ebenfalls flott können.

Das sind dann also sehr spezielle Anforderungen, wann eine verkettete Liste ihre Stärke ausspielen kann, ohne an ihren Schwächen zu scheitern. Der Fall, wo tatsächlich eine verkettete Liste sowohl theoretisch als auch praktisch die schnellste/beste/einfachste Lösung ist, ist daher sehr selten.

Braucht ihr das oft?

Bisher: 0 Mal.
Falls ich mal eine bräuchte, würde ich sie auch nicht selber programmieren, sondern was fertiges nehmen. Ist aber nett zu wissen, wie sie intern funktioniert (Dann versteht man auch, warum sie so lahm ist :p ).

P.S.: Ein Telefonbuch ist daher wohl eher ein Anti-Anwendungsfalls für Listen. Man hat bestimmt sehr viel mehr Zugriffe als Einfüge-/Löschaktionen. Und die Struktur sollte wohl geordnet sein, das macht das Einfügen bei der Liste wieder ineffizient, weil man erst die passende Stelle in O(N) suchen muss. Selbst bei einem Array wäre das nur O(log(N)) (auch wenn das Einfügen dann O(N) wäre). Ideal wären wohl Array oder eine Baumstruktur, das kommt dann drauf an, welche Aktionen man auf dem Telefonbuch am häufigsten durchführt. Der Baum wäre besser, wenn man oft löscht und einfügt (und zwar noch besser als die verkettete Liste).

mgaeckler

beginner_offl schrieb:

Das würd mich jetzt auch interessieren... Werden Verkettete Listen "oft" benutzt in der Praxis, bzw. von Euch Profis?
Bei mir ist C nur ein "Hobby", bzw. ne nützliche Erweiterung für mich , aber wie sieht´s aus bei den Jungs die Ihr Geld damit verdienen... ? Ich werd mich hald in verkettete Listen mal einarbeiten, weil´s irgendwie dazugehört.
Braucht ihr das oft?
mfg Martin

Hi,

Arrays werden sicherlich häufiger benutzt wie Listen. Es kommt aber natürlich auf den Anwendungsfall an.

Der Vorteil von Arrays kommt halt in den meisten Fällen zu tragen. Der Zugriff auf ein einzelnes Element mittendrin ist natürlich wesentlich schneller wie bei Listen, auch ist der Overhead deutlich geringer. Dafür geht bei Listen das Anhängen und Entfernen einzelner Elemente schneller wie bei Arrays, weil da nicht viel umkopiert werden muß. Eine einigermassen vernünftige Arrayimplementierung kann aber diesen Nachteil ganz gut minimieren.

mfg Martin

OK, das war sehr ausführlich und interessant erklärt.

@SeppJ.. kannst du meine RekursionThread mal noch angucken, ob das mit dem **char so stimmt?

Falls ich mal eine bräuchte, würde ich sie auch nicht selber programmieren, sondern was fertiges nehmen

Gibt's da sowas wie ne "fertige" Bibliothek für den Programmierer, oder wie muss man sich das vorstellen?

SeppJ

beginner_offl schrieb:

@SeppJ.. kannst du meine RekursionThread mal noch angucken, ob das mit dem **char so stimmt?

Ja, aber nicht mehr heute.

beginner_offl schrieb:

Falls ich mal eine bräuchte, würde ich sie auch nicht selber programmieren, sondern was fertiges nehmen

Gibt's da sowas wie ne "fertige" Bibliothek für den Programmierer, oder wie muss man sich das vorstellen?

Ja, C++ :p

@SeppJ.. kannst du meine RekursionThread mal noch angucken, ob das mit dem **char so stimmt?

Ja, aber nicht mehr heute.

OK. Danke schonmal!!

Ich habe jetzt soweit ein Programm mit meinen Komilitonen ich will mal sagen zusammen gebastelt. ich habe aber erst im labor einen compiler zur verfügung. Vielleicht könnt ihr mir aber mal ein feedback geben was dvon zu halten ist.

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

#define FILENAME "telefonbuch.txt"
#define pufferlaenge 20

struct Person{
char Vorname[20];
char Nachname[20];
char Rufnummer[20];
struct Person *naechsteSilbe;
};

int buchPrinten(struct Person *);
int neuerEintrag(struct Person **);
int eintragSuchen(struct Person *);
int eintragLoeschen(struct Person **);
int buchLaden(struct Person **);
int buchSpeichern(struct Person *);
int buchLoeschen(struct Person **);

int main (void){

int eingabe=0;

struct Person *telefonbuch;
telefonbuch = NULL;

do{

printf("\nMenue\n");
printf("1. Telefonbuch anzeigen\n");
printf("2. Person hinzufuegen\n");
printf("3. Eintrag suchen\n");
printf("4. Einzelnen Eintrag loeschen\n");
printf("5. Telefonbuch laden\n");
printf("6. Telefonbuch speichern\n");
printf("7. Telefonbuch loeschen\n");
printf("9. Programm beenden\n");

printf("Bitte Ziffer eingeben: ");
scanf("%d",&eingabe);

switch (eingabe){
case 1: buchPrinten(telefonbuch);
break;
case 2: neuerEintrag(&telefonbuch);
break;
case 3: eintragSuchen(telefonbuch);
break;
case 4: eintragLoeschen(&telefonbuch);
break;
case 5: buchLaden(&telefonbuch);
break;
case 6: buchSpeichern(telefonbuch);
break;
case 7: buchLoeschen(&telefonbuch);
break;
default: printf("\nBeendet\n");
break;
}

}while (eingabe!=9);
return 0;
}

int buchPrinten(struct Person *telefonbuch){

struct Person *index;
index = telefonbuch;

if(index!=NULL){
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n",index->Nachname,index->Vorname,index->Rufnummer);
while(index->naechsteSilbe!=NULL){
index=index->naechsteSilbe;
printf("------------------------------------");
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n",index->Nachname,index->Vorname,index->Rufnummer);
}
}
else{
printf("\nKein Eintrag vorhanden\n");
}
}

int neuerEintrag(struct Person **telefonbuch){

struct Person *neuesElement;
struct Person *index = (struct Person *telefonbuch;

neuesElement = (struct Person*) malloc(sizeof(*neuesElement));
printf("Speicher reservieren: %d\n",neuesElement);

printf("Neuer Eintrag:\n");
printf("Nachname: ");
scanf("%s",neuesElement->Nachname);
printf("Vorname: ");
scanf("%s",neuesElement->Vorname);
printf("Rufnummer: ");
scanf("%s",neuesElement->Rufnummer);
neuesElement->naechsteSilbe=NULL;

if (index!=NULL){
while(index->naechsteSilbe!=NULL){
index=index->naechsteSilbe;
}
index->naechsteSilbe=neuesElement;
}

else{
*telefonbuch=neuesElement;
}
}

int eintragSuchen(struct Person *telefonbuch){

struct Person *index;
index = telefonbuch;

char namenSuchen[20];
printf("Bitte den zu suchenden Nachnamen eingeben: ");
scanf("%s",&namenSuchen);

if(index!=NULL){
if(strcmp(namenSuchen,(const char*)index->Nachname)==0){
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
}
while(index->naechsteSilbe!=NULL){
index=index->naechsteSilbe;

if(strcmp(namenSuchen,(const char*)index->Nachname)==0){
printf("------------------------------------");
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
}
}
}
else{
printf("\nDas Telefonbuch ist leer\n");
}
}

int eintragLoeschen(struct Person **telefonbuch){

struct Person *index;
struct Person *davor;
struct Person *dahinter;
index = *telefonbuch;
davor = *telefonbuch;

char namenSuchen[20];
printf("Eingeben des Namen vom zu loeschenden Eintrag: ");
scanf("%s",&namenSuchen);

if(index!=NULL){
if(strcmp(namenSuchen,(const char*)index->Nachname)==0){
dahinter=index->naechsteSilbe;
printf("------------------------------------");
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
printf("Speicher freigeben: %d\n",index);
free(index);
*telefonbuch=dahinter;
}
while(index->naechsteSilbe!=NULL){
davor=index;
index=index->naechsteSilbe;

if(strcmp(namenSuchen,(const char*)index->Nachname)==0){
davor->naechsteSilbe=index->naechsteSilbe;
printf("------------------------------------");
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
printf("Speicher freigeben: %d\n",index);
free(index);
}
}
}
else{
printf("\nDas Telefonbuch ist leer\n");
}
}

int buchLaden(struct Person **telefonbuch){

struct Person *neuesElement;

FILE *filepointer;
char buffer[pufferlaenge];

if ( (filepointer = fopen (FILENAME,"r"))==NULL){
printf("Fehler beim oeffenen der Datei!\n");
}

int result=0;
while(result!=EOF){

struct Person *index = (struct Person telefonbuch;
neuesElement = (struct Person) malloc(sizeof(*neuesElement));
printf("Speicher reservieren: %d\n",neuesElement);

result=fscanf(filepointer,"%20s%20s%20s",neuesElement->Nachname,neuesElement->Vorname,neuesElement->Rufnummer);
if (result==EOF) {
printf("Speicher freigeben: %d\n",neuesElement);
free(neuesElement);
}
else
{
neuesElement->naechsteSilbe=NULL;

if (index!=NULL){
while(index->naechsteSilbe!=NULL){
index=index->naechsteSilbe;
}
index->naechsteSilbe=neuesElement;
}
else{
*telefonbuch=neuesElement;
}
}
}
fclose(filepointer);
}

int buchSpeichern(struct Person *telefonbuch){

FILE *filepointer;
char buffer[pufferlaenge];

if ( (filepointer = fopen (FILENAME,"w"))==NULL){
printf("Fehler beim oeffenen der Datei!\n");
}

struct Person *index;
index = telefonbuch;

if(index!=NULL){

fprintf(filepointer,"%-20s%-20s%-20s\n",index->Nachname,index->Vorname,index->Rufnummer);

while(index->naechsteSilbe!=NULL){

index=index->naechsteSilbe;
fprintf(filepointer,"%-20s%-20s%-20s\n",index->Nachname,index->Vorname,index->Rufnummer);
}
}
fclose(filepointer);
}

int buchLoeschen(struct Person **telefonbuch){

struct Person *index = (struct Person *telefonbuch;

if (index!=NULL){

if (index==*telefonbuch&&index->naechsteSilbe==NULL){
printf("Speicher freigeben: %d\n",index);
free(index);
*telefonbuch=NULL;
}
else{
while(index->naechsteSilbe!=NULL){

if ( index->naechsteSilbe->naechsteSilbe==NULL){
printf("Speicher freigeben: %d\n",index->naechsteSilbe);
free(index->naechsteSilbe);
index->naechsteSilbe=NULL;
buchLoeschen(telefonbuch);
}
else{
index=index->naechsteSilbe;
}
}
}
}
else{
printf("Telefonbuch geloescht");
}
}

Mir ist klar das ich beim kompilieren noch auf fehler treffen werde die ich dann vor ort lösen muss, aber die struktur sollte stimmen weil ich nur 90 minuten zeit habe.

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

#define FILENAME "telefonbuch.txt" 
#define pufferlaenge 20 

struct Person{ 
char Vorname[20]; 
char Nachname[20]; 
char Rufnummer[20]; 
struct Person *naechsteSilbe; 
}; 

int buchPrinten(struct Person *); 
int neuerEintrag(struct Person **); 
int eintragSuchen(struct Person *); 
int eintragLoeschen(struct Person **); 
int buchLaden(struct Person **); 
int buchSpeichern(struct Person *); 
int buchLoeschen(struct Person **); 

int main (void){ 

int eingabe=0; 

struct Person *telefonbuch; 
telefonbuch = NULL; 

do{ 

printf("\nMenue\n"); 
printf("1. Telefonbuch anzeigen\n"); 
printf("2. Person hinzufuegen\n"); 
printf("3. Eintrag suchen\n"); 
printf("4. Einzelnen Eintrag loeschen\n"); 
printf("5. Telefonbuch laden\n"); 
printf("6. Telefonbuch speichern\n"); 
printf("7. Telefonbuch loeschen\n"); 
printf("9. Programm beenden\n"); 

printf("Bitte Ziffer eingeben: "); 
scanf("%d",&eingabe); 

switch (eingabe){ 
case 1: buchPrinten(telefonbuch); 
break; 
case 2: neuerEintrag(&telefonbuch); 
break; 
case 3: eintragSuchen(telefonbuch); 
break; 
case 4: eintragLoeschen(&telefonbuch); 
break; 
case 5: buchLaden(&telefonbuch); 
break; 
case 6: buchSpeichern(telefonbuch); 
break; 
case 7: buchLoeschen(&telefonbuch); 
break; 
default: printf("\nBeendet\n"); 
break; 
} 

}while (eingabe!=9); 
return 0; 
} 

int buchPrinten(struct Person *telefonbuch){ 

struct Person *index; 
index = telefonbuch; 

if(index!=NULL){ 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n",index->Nachname,index->Vorname,index->Rufnummer);
 while(index->naechsteSilbe!=NULL){ 
index=index->naechsteSilbe; 
printf("------------------------------------"); 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n",index->Nachname,index->Vorname,index->Rufnummer);
 } 
} 
else{ 
printf("\nKein Eintrag vorhanden\n"); 
} 
} 

int neuerEintrag(struct Person **telefonbuch){ 

struct Person *neuesElement; 
struct Person *index = (struct Person *) *telefonbuch; 

neuesElement = (struct Person*) malloc(sizeof(*neuesElement)); 
printf("Speicher reservieren: %d\n",neuesElement); 

printf("Neuer Eintrag:\n"); 
printf("Nachname: "); 
scanf("%s",neuesElement->Nachname); 
printf("Vorname: "); 
scanf("%s",neuesElement->Vorname); 
printf("Rufnummer: "); 
scanf("%s",neuesElement->Rufnummer); 
neuesElement->naechsteSilbe=NULL; 

if (index!=NULL){ 
while(index->naechsteSilbe!=NULL){ 
index=index->naechsteSilbe; 
} 
index->naechsteSilbe=neuesElement; 
} 

else{ 
*telefonbuch=neuesElement; 
} 
} 

int eintragSuchen(struct Person *telefonbuch){ 

struct Person *index; 
index = telefonbuch; 

char namenSuchen[20]; 
printf("Bitte den zu suchenden Nachnamen eingeben: "); 
scanf("%s",&namenSuchen); 

if(index!=NULL){ 
if(strcmp(namenSuchen,(const char*)index->Nachname)==0){ 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
 } 
while(index->naechsteSilbe!=NULL){ 
index=index->naechsteSilbe; 

if(strcmp(namenSuchen,(const char*)index->Nachname)==0){ 
printf("------------------------------------"); 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
 } 
} 
} 
else{ 
printf("\nDas Telefonbuch ist leer\n"); 
} 
} 

int eintragLoeschen(struct Person **telefonbuch){ 

struct Person *index; 
struct Person *davor; 
struct Person *dahinter; 
index = *telefonbuch; 
davor = *telefonbuch; 

char namenSuchen[20]; 
printf("Eingeben des Namen vom zu loeschenden Eintrag: "); 
scanf("%s",&namenSuchen); 

if(index!=NULL){ 
if(strcmp(namenSuchen,(const char*)index->Nachname)==0){ 
dahinter=index->naechsteSilbe; 
printf("------------------------------------"); 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
 printf("Speicher freigeben: %d\n",index); 
free(index); 
*telefonbuch=dahinter; 
} 
while(index->naechsteSilbe!=NULL){ 
davor=index; 
index=index->naechsteSilbe; 

if(strcmp(namenSuchen,(const char*)index->Nachname)==0){ 
davor->naechsteSilbe=index->naechsteSilbe; 
printf("------------------------------------"); 
printf("\nNachname: %s\nVorname: %s\nRufnummer: %s\n", index->Nachname, index->Vorname, index->Rufnummer);
 printf("Speicher freigeben: %d\n",index); 
free(index); 
} 
} 
} 
else{ 
printf("\nDas Telefonbuch ist leer\n"); 
} 
} 

int buchLaden(struct Person **telefonbuch){ 

struct Person *neuesElement; 

FILE *filepointer; 
char buffer[pufferlaenge]; 

if ( (filepointer = fopen (FILENAME,"r"))==NULL){ 
printf("Fehler beim oeffenen der Datei!\n"); 
} 

int result=0; 
while(result!=EOF){ 

struct Person *index = (struct Person *) *telefonbuch; 
neuesElement = (struct Person*) malloc(sizeof(*neuesElement)); 
printf("Speicher reservieren: %d\n",neuesElement); 

result=fscanf(filepointer,"%20s%20s%20s",neuesElement->Nachname,neuesElement->Vorname,neuesElement->Rufnummer);
 if (result==EOF) { 
printf("Speicher freigeben: %d\n",neuesElement); 
free(neuesElement); 
} 
else 
{ 
neuesElement->naechsteSilbe=NULL; 

if (index!=NULL){ 
while(index->naechsteSilbe!=NULL){ 
index=index->naechsteSilbe; 
} 
index->naechsteSilbe=neuesElement; 
} 
else{ 
*telefonbuch=neuesElement; 
} 
} 
} 
fclose(filepointer); 
} 

int buchSpeichern(struct Person *telefonbuch){ 

FILE *filepointer; 
char buffer[pufferlaenge]; 

if ( (filepointer = fopen (FILENAME,"w"))==NULL){ 
printf("Fehler beim oeffenen der Datei!\n"); 
} 

struct Person *index; 
index = telefonbuch; 

if(index!=NULL){ 

fprintf(filepointer,"%-20s%-20s%-20s\n",index->Nachname,index->Vorname,index->Rufnummer);

while(index->naechsteSilbe!=NULL){ 

index=index->naechsteSilbe; 
fprintf(filepointer,"%-20s%-20s%-20s\n",index->Nachname,index->Vorname,index->Rufnummer);
 } 
} 
fclose(filepointer); 
} 

int buchLoeschen(struct Person **telefonbuch){ 

struct Person *index = (struct Person *) *telefonbuch; 

if (index!=NULL){ 

if (index==*telefonbuch&&index->naechsteSilbe==NULL){ 
printf("Speicher freigeben: %d\n",index); 
free(index); 
*telefonbuch=NULL; 
} 
else{ 
while(index->naechsteSilbe!=NULL){ 

if ( index->naechsteSilbe->naechsteSilbe==NULL){ 
printf("Speicher freigeben: %d\n",index->naechsteSilbe); 
free(index->naechsteSilbe); 
index->naechsteSilbe=NULL; 
buchLoeschen(telefonbuch); 
} 
else{ 
index=index->naechsteSilbe; 
} 
} 
} 
} 
else{ 
printf("Telefonbuch geloescht"); 
} 
}

Haben sie das mal compiliert?

@code_tags_sind_toll
Ja, sind sie. Noch toller ist es aber, wenn die Einrückung erhalten bleibt.
Das kann man dann über 'Zitieren' machen und da die Code-Tags einfügen.

@Mirko1234567
Das wäre dann deine Aufgabe. So wie es jetzt ist, schaut sich das fast keiner an.

Trenne Funktion von Ein/Ausgabe
neuerEintrag macht zuviel.
Du brauchst eine Funktion, die Daten vom User entgegen nimmt.
Du brauchst eine Funktion, die einen neuen Knoten in die Liste einfügt/anhängt.

Genauso für eintragSuchen und eintragLoeschen

Bei %s bei fscanf werden die maximal zu lesenden Zeichen angegeben.
Da aber noch Platz für die '\0' bleiben muss, musst du da eins weniger angeben. (hier also %19s)
Bei fgets ist das anders.

Obwohl alle deine Funktionen einen int als Rückgabewert haben (ist das sinnvoll?), gibt es in dem ganzen Programm nur ein return.

Mirko1234567 schrieb:

Haben sie das mal compiliert?

Nö.