Aus Linked-List löschen. Zeiger Problem.

[Ladnaks]

Hallo Leute

Ich habe eine Hash Table und wenn zwei Werte auf den gleichen Wert hashen lege ich als Eintrag eine Linked List an. Man soll auch wieder Elemente löschen können. Nun bin ich kein all zu erfahrener C Programmiere, und habe so meine Probleme mit den Zeigern. Ich dachte mir ich mach es so:
Ich gehe die Liste immer mit aktuellerKnoten->next durch und merke mir aber auch den vorherigen Knoten. Habe ich das Element erreicht das ich löschen will, dann lenke ich vorherigerKnoten->next auf aktuellerKnoten->next um. Ist das erste Element das zu entfernende Element wird der Beginn der Liste auf aktuellerKnoten->next umgeleitet.

Hier sind die relevanten Teile meines Codes. Beim Aufruf von delete erhalte immer nur "Speicherzugriffsfehler", ohne genaue Angaben wo was falsch läuft. Hat jemand einen Tipp?

struct node {
  struct node *next;
  long value;
  long count;
};


struct node **lookup(long key, struct node **table, size_t table_size)
/* comment */
{
  struct node **pp = table+hash(key,table_size);
  for (; *pp!=NULL; pp = &((*pp)->next))
    if ((*pp)->value == key)
      return pp;
  return pp;
}


void delete(long key, struct node **table, size_t table_size)
{
        struct node **pp = table+hash(key,table_size);
        struct node *old = NULL;

          for (; *pp!=NULL; pp = &((*pp)->next)){
            if ((*pp)->value == key){
              if(old != NULL){
                  ((old)->next) = ((*pp)->next);
                }{
                  (*pp) =((*pp)->next);
                }
            }
        old = *pp;
        }

 

[sheel]

Hi

Du solltest die Funktion nicht delete nennen.
delete gibts schon.
Nimm "del", "remove" oder etwas in der Art.

kA., woher beim Hinzufügen die Daten kommen,
wenn du sie aber Listen-intern mit new erzeugst,
musst du sie auch wieder mit dem (echten) delete entfernen.

lookup schau ich mir jetzt mal nicht an, da es in delete nicht vorkommt.

Wenn du dir in der ersten delete-Zeile gleich ein node* holst, mit

struct node *pp = *(table + hash(key, table_size));

würdest du dir mit den ganzen * und -> darunter dann leichter tun,
weil du weniger brauchst. Geht aber so auch.

Die {}-Klammerung verwirrt mich etwas.
Dich vllt. auch?
Zuerst ein

if(old != NULL){...}

und dann wieder ein {}, das gar nicht nötig wäre
und einen zuerst an else denken lässt.
Bis man sieht, dass es ja keines ist.

Warum das:

{
    (*pp) =((*pp)->next);
}

...Kannst du vllt. einmal ein kompilierbares Minimalbeispiel machen?
Alle Listenfunktionen,
und im main etwas hinzufügen und wieder löschen?

 

[Ladnaks]

Die {}-Klammerung verwirrt mich etwas.
Dich vllt. auch?

Das soll eigentlich ein else hin. Ist beim Kopieren irgendwie verschwunden. Wenn old!=null ist soll old->next auf pp->next gesetzt werden. Andernfalls ist pp das erste Element der Liste.

 

[sheel]

Kannst du trotzdem einmal ein kompilierbares Minimalbeispiel machen?
Alle Listenfunktionen,
und im main etwas hinzufügen und wieder löschen?

 

[deepthroat]

Hi.

Hi

Du solltest die Funktion nicht delete nennen.
delete gibts schon.
Nimm "del", "remove" oder etwas in der Art.

Es scheint sich hier nicht um C++ zu handeln. In C ist ein benutzerdefiniertes "delete" schon OK...

\edit: @Ladnaks: Verwende einen Debugger. In welcher Zeile genau stürzt das Programm denn ab? Welchen Compiler / Betriebssystem verwendest du?

Gruß

 

[Ladnaks]

Erst mal danke für die Hilfe. Ich habe hier den ausführbaren Code hochgeladen.

Die delete Methode habe ich nochmal neu geschrieben. Das ist die neue Version:

void delete(long key, struct node **table, size_t table_size)
{

	struct node *currP = *(table + hash(key, table_size));
	struct node *currP2 = *(table + hash(key, table_size));

	struct node *prevP;
	prevP = NULL;
	for(;
		currP!=NULL;
		prevP = currP, currP = currP->next){
		if((currP)->value == key){
			if(prevP == NULL){
				currP2=(currP)->next;
			} else {
				prevP->next = (currP)->next;
			}
			free(currP);
		}
	}

}

So funktioniert es schon viel besser als zuvor, aber noch nicht ganz. Der Fehler tritt immer bei free(currP) auf. Aber nicht beim ersten mal wenn diese Stelle erreicht wird sondern erst nach mehreren Durchläufen.
Wenn ich free(currP) auskommentiere funktioniert alles. Weiß jemand woran das liegen könnte?

EDIT NG

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <malloc.h>
 
struct node {
  struct node *next;
  long value;
  long count;
};
 
long cube(long n)
{
  return n*n*n;
}
 
size_t size_table(long n)
/* compute the table size so it is not too densely or too sparsely occupied
   and is a power of 2 */
{
  return 1<<(long)(log((double)n)*(2.0/(3.0*log(2.0))));
}
 
size_t hash(long key, size_t hash_size)
/* assumes that hash_size is a power of two */
{
  return key&(hash_size-1);
}
 
struct node **lookup(long key, struct node **table, size_t table_size)
/* comment */
{
  struct node **pp = table+hash(key,table_size);
  for (; *pp!=NULL; pp = &((*pp)->next))
    if ((*pp)->value == key)
      return pp;
  return pp;
}
 
void delete(long key, struct node **table, size_t table_size)
{
 
        struct node *currP = *(table + hash(key, table_size));
        struct node *currP2 = *(table + hash(key, table_size));
 
        struct node *prevP;
        prevP = NULL;
        printf("methode \n");
        for(;
                currP!=NULL;
                prevP = currP, currP = currP->next){
                if((currP)->value == key){
                        printf("if1 \n");
                        if(prevP == NULL){
                                printf("if2 \n");
                                currP2=(currP)->next;
                        } else {
                                printf("else \n");
                                prevP->next = (currP)->next;
                        }
                        free(currP);
                }
        }
 
}
 
main(int argc, char **argv)
{
  long n;
  char *endptr;
  long i,j;
  long count=0;
  struct node **table;
  size_t table_size;
  long occupation=0;
  struct mallinfo m;
 
  if (argc != 2)
    goto usage;
  n = strtol(argv[1],&endptr,10);
  if (*endptr != '\0')
    goto usage;
  table_size = size_table(n);
  table = calloc(table_size,sizeof(struct node*));
 
  for (i=0; cube(i)<=n; i++)
    for (j=i+1; cube(i)+cube(j)<=n; j++) {
      long sum = cube(i)+cube(j);
      struct node **sumnodepp = lookup(sum,table,table_size);
      if (*sumnodepp != NULL) {
        (*sumnodepp)->count++;
        if ((*sumnodepp)->count==2){    /* don't count additional hits */
          count++;
           delete(sum,table,table_size);
        }
      } else {
        struct node *new = malloc(sizeof(struct node));
        new->next = NULL;
        new->value = sum;
        new->count = 1;
        *sumnodepp = new;
        occupation++;
      }
    }
  printf("%ld Ramanujan numbers up to %ld\noccupation=%ld, size=%ld\n",count,n,occupation,table_size);
  m = mallinfo(); /* for some reason, this does not record the calloc()
                     above for larger n (the limit is between 10^6 and
                     10^7); since the benchmark size is 10^11, we add
                     the calloc()ed size below */
  printf("Memory usage: %lu\n",m.uordblks+table_size*sizeof(struct node*));
  return 0;
 
 usage:
  fprintf(stderr,"usage: %s <n>\n",argv[0]);
  exit(1);
}

 

[sheel]

Warum hängst du den Code nicht als Anhang an?
Der Link geht nicht.

 

[deepthroat]

Wie rufst du das Programm denn auf?

Generell: Kompiliere das Programm mit Debuginformationen (Option -g). Starte das Programm unter gdb. Lass es laufen bis es abstürzt. Dann erstellst du ein Stacktrace mit "bt full" und schaust ihn dir an.

\edit: Und bevor du da etwas wildes berechnest, stelle doch erstmal sicher, das eine Datenstruktur ordentlich funktioniert. Schreibe dir einen Testtreiber und Testfälle und definiere welche Werte erwartet werden und prüfe auf Richtigkeit.

Verwende valgrind.

Verwende Funktionen. Du verwaltest eine Liste, hast aber keine Listenfunktionen. Der Code ist für die Liste ist vermengt mit dem restlichen Code. Für die Hashtable gibt es nur die Funktionen lookup und delete - kein add?

Gruß