Ces messages sont apparemment dans le mauvais ordre ! C'est le numéro 3 d'une série de 3 messages. Désolé.
J'ai "pris quelques libertés supplémentaires" avec le code de Lie Ryan. Il est vrai que la liste chaînée prenait du temps pour accéder à chaque éléments individuels en raison de la surcharge de recherche, c'est-à-dire parcourir la liste jusqu'à ce que vous trouviez le bon élément. J'ai maintenant remédié à cela en en maintenant un vecteur d'adresses contenant les indices 0 à n'importe quel indice associé à des adresses mémoire. Cela fonctionne car le vecteur d'adresse est alloué en une seule fois, donc contigu en mémoire. Puisque la liste chaînée n'est plus nécessaire, j'ai supprimé le code et la structure qui lui étaient associés.
Cette approche n'est pas aussi efficace qu'un simple tableau statique, mais au moins vous n'avez pas à "parcourir la liste" à la recherche du bon élément. à la recherche de l'élément approprié. Vous pouvez maintenant accéder aux éléments en utilisant un indice. Pour permettre cela, j'ai dû ajouter du code pour gérer les cas où des éléments sont supprimés et où les indices "réels" ne seraient pas reflétés dans les indices du vecteur de pointeurs. dans les indices du vecteur de pointeurs. Cela peut être important ou non pour les utilisateurs. Pour moi, c'est important, donc J'ai donc rendu la renumérotation des souscripts facultative. Si la renumérotation n'est pas utilisée, le programme passe à un élément fictif "manquant" qui renvoie une erreur. "manquant" qui renvoie un code d'erreur, que les utilisateurs peuvent choisir d'ignorer ou de traiter selon les besoins.
À partir de là, je conseille aux utilisateurs de coder la partie "éléments" en fonction de leurs besoins et de s'assurer qu'elle fonctionne correctement. Si vos éléments ajoutés sont des tableaux, codez soigneusement les sous-routines pour y accéder, étant donné qu'il y a une structure de tableau supplémentaire qui n'était pas nécessaire avec les tableaux statiques. qui n'était pas nécessaire avec les tableaux statiques. Bonne lecture !
#include <glib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
// For pointer-to-pointer info see:
// https://stackoverflow.com/questions/897366/how-do-pointer-to-pointers-work-in-c-and-when-might-you-use-them
typedef struct STRUCT_SS_VECTOR
{ size_t size; // # of vector elements
void** items; // makes up one vector element's component contents
int subscript; // this element's subscript nmbr, 0 thru whatever
// struct STRUCT_SS_VECTOR* this_element; // linked list via this ptr
// struct STRUCT_SS_VECTOR* next_element; // and next ptr
} ss_vector;
ss_vector* vector; // ptr to vector of components
ss_vector* missing_element(int subscript) // intercepts missing elements
{ printf("missing element at subscript %i\n",subscript);
return NULL;
}
typedef struct TRACKER_VECTOR
{ int subscript;
ss_vector* vector_ptr;
} tracker_vector; // up to 20 or so, max suggested
tracker_vector* tracker;
int max_tracker=0; // max allowable # of elements in "tracker_vector"
int tracker_count=0; // current # of elements in "tracker_vector"
int tracker_increment=5; // # of elements to add at each expansion
void bump_tracker_vector(int new_tracker_count)
{ //init or lengthen tracker vector
if(max_tracker==0) // not yet initialized
{ tracker=calloc(tracker_increment, sizeof(tracker_vector));
max_tracker=tracker_increment;
printf("initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
tracker_count++;
return;
}
else if (max_tracker<=tracker_count) // append to existing tracker vector by writing a new one, copying old one
{ tracker_vector* temp_tracker=calloc(max_tracker+tracker_increment,sizeof(tracker_vector));
for(int i=0;(i<max_tracker);i++){ temp_tracker[i]=tracker[i];} // copy old tracker to new
max_tracker=max_tracker+tracker_increment;
free(tracker);
tracker=temp_tracker;
printf(" re-initialized %i-element tracker vector of size %lu at %lu\n",max_tracker,sizeof(tracker_vector),(size_t)tracker);
tracker_count++;
return;
} // else if
// fall through for most "bumps"
tracker_count++;
return;
} // bump_tracker_vector()
ss_vector* ss_init_vector(size_t item_size) // item_size is size of one array member
{ ss_vector* vector= malloc(sizeof(ss_vector));
vector->size = 0; // initialize count of vector component elements
vector->items = calloc(1, item_size); // allocate & zero out memory for one linked list element
vector->subscript=0;
bump_tracker_vector(0); // init/store the tracker vector
tracker[0].subscript=0;
tracker[0].vector_ptr=vector;
return vector; //->this_element;
} // ss_init_vector()
ss_vector* ss_vector_append( int i) // ptr to this element, element nmbr
{ ss_vector* local_vec_element=0;
local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
local_vec_element->subscript=i; //vec_element->size;
local_vec_element->size=i; // increment # of vector components
bump_tracker_vector(i); // increment/store tracker vector
tracker[i].subscript=i;
tracker[i].vector_ptr=local_vec_element; //->this_element;
return local_vec_element;
} // ss_vector_append()
void bubble_sort(void)
{ // bubble sort
struct TRACKER_VECTOR local_tracker;
int i=0;
while(i<tracker_count-1)
{ if(tracker[i].subscript>tracker[i+1].subscript)
{ local_tracker.subscript=tracker[i].subscript; // swap tracker elements
local_tracker.vector_ptr=tracker[i].vector_ptr;
tracker[i].subscript=tracker[i+1].subscript;
tracker[i].vector_ptr=tracker[i+1].vector_ptr;
tracker[i+1].subscript=local_tracker.subscript;
tracker[i+1].vector_ptr=local_tracker.vector_ptr;
if(i>0) i--; // step back and go again
}
else
{ if(i<tracker_count-1) i++;
}
} // while()
} // void bubble_sort()
void move_toward_zero(int target_subscript) // toward zero
{ struct TRACKER_VECTOR local_tracker;
// Target to be moved must range from 1 to max_tracker
if((target_subscript<1)||(target_subscript>tracker_count)) return; // outside range
// swap target_subscript ptr and target_subscript-1 ptr
local_tracker.vector_ptr=tracker[target_subscript].vector_ptr;
tracker[target_subscript].vector_ptr=tracker[target_subscript-1].vector_ptr;
tracker[target_subscript-1].vector_ptr=local_tracker.vector_ptr;
}
void renumber_all_subscripts(gboolean arbitrary)
{ // assumes tracker_count has been fixed and tracker[tracker_count+1]has been zeroed out
if(arbitrary) // arbitrary renumber, ignoring "true" subscripts
{ for(int i=0;i<tracker_count;i++)
{ tracker[i].subscript=i;}
}
else // use "true" subscripts, holes and all
{ for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0) // renumbering "true" subscript tracker & vector_element
{ tracker[i].subscript=tracker[i].vector_ptr->subscript;}
else // renumbering "true" subscript tracker & NULL vector_element
{ tracker[i].subscript=-1;}
} // for()
bubble_sort();
} // if(arbitrary) ELSE
} // renumber_all_subscripts()
void collapse_tracker_higher_elements(int target_subscript)
{ // Fix tracker vector by collapsing higher subscripts toward 0.
// Assumes last tracker element entry is discarded.
int j;
for(j=target_subscript;(j<tracker_count-1);j++)
{ tracker[j].subscript=tracker[j+1].subscript;
tracker[j].vector_ptr=tracker[j+1].vector_ptr;
}
// Discard last tracker element and adjust count
tracker_count--;
tracker[tracker_count].subscript=0;
tracker[tracker_count].vector_ptr=(size_t)0;
} // void collapse_tracker_higher_elements()
void ss_vector_free_one_element(int target_subscript, gboolean Keep_subscripts)
{ // Free requested element contents.
// Adjust subscripts if desired; otherwise, mark NULL.
// ----special case: vector[0]
if(target_subscript==0) // knock out zeroth element no matter what
{ free(tracker[0].vector_ptr);}
// ----if not zeroth, start looking at other elements
else if(tracker_count<target_subscript-1)
{ printf("vector element not found\n");return;}
// Requested subscript okay. Freeit.
else
{ free(tracker[target_subscript].vector_ptr);} // free element ptr
// done with removal.
if(Keep_subscripts) // adjust subscripts if required.
{ tracker[target_subscript].vector_ptr=missing_element(target_subscript);} // point to "0" vector
else // NOT keeping subscripts intact, i.e. collapsing/renumbering all subscripts toward zero
{ collapse_tracker_higher_elements(target_subscript);
renumber_all_subscripts(TRUE); // gboolean arbitrary means as-is, FALSE means by "true" subscripts
} // if (target_subscript==0) else
// show the new list
// for(int i=0;i<tracker_count;i++){printf(" remaining element[%i] at %lu\n",tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
} // void ss_vector_free_one_element()
void ss_vector_free_all_elements(void)
{ // Start at "tracker[0]". Walk the entire list, free each element's contents,
// then free that element, then move to the next one.
// Then free the "tracker" vector.
for(int i=tracker_count;i>=0;i--)
{ // Modify your code to free vector element "items" here
if(tracker[i].subscript>=0) free(tracker[i].vector_ptr);
}
free(tracker);
tracker_count=0;
} // void ss_vector_free_all_elements()
// defining some sort of struct, can be anything really
typedef struct APPLE_STRUCT
{ int id; // one of the data in the component
int other_id; // etc
struct APPLE_STRUCT* next_element;
} apple; // description of component
apple* init_apple(int id) // make a single component
{ apple* a; // ptr to component
a = malloc(sizeof(apple)); // memory for one component
a->id = id; // populate with data
a->other_id=id+10;
a->next_element=NULL;
// don't mess with aa->last_rec here
return a; // return pointer to component
}
int return_id_value(int i,apple* aa) // given ptr to component, return single data item
{ printf("was inserted as apple[%i].id = %i ",i,aa->id);
return(aa->id);
}
ss_vector* return_address_given_subscript(int i)
{ return tracker[i].vector_ptr;}
int Test(void) // was "main" in the example
{ int i;
ss_vector* local_vector;
local_vector=ss_init_vector(sizeof(apple)); // element "0"
for (i = 1; i < 10; i++) // inserting items "1" thru whatever
{local_vector=ss_vector_append(i);} // finished ss_vector_append()
// list all tracker vector entries
for(i=0;(i<tracker_count);i++) {printf("tracker element [%i] has address %lu\n",tracker[i].subscript, (size_t)tracker[i].vector_ptr);}
// ---test search function
printf("\n NEXT, test search for address given subscript\n");
local_vector=return_address_given_subscript(5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(9);
printf("finished return_address_given_subscript(9) with vector at %lu\n",(size_t)local_vector);
// ---test single-element removal
printf("\nNEXT, test single element removal\n");
ss_vector_free_one_element(5,TRUE); // keep subscripts; install dummy error element
printf("finished ss_vector_free_one_element(5)\n");
ss_vector_free_one_element(3,FALSE);
printf("finished ss_vector_free_one_element(3)\n");
ss_vector_free_one_element(0,FALSE);
// ---test moving elements
printf("\n Test moving a few elements up\n");
move_toward_zero(5);
move_toward_zero(4);
move_toward_zero(3);
// show the new list
printf("New list:\n");
for(int i=0;i<tracker_count;i++){printf(" %i:element[%i] at %lu\n",i,tracker[i].subscript,(size_t)tracker[i].vector_ptr);}
// ---plant some bogus subscripts for the next subscript test
tracker[3].vector_ptr->subscript=7;
tracker[3].subscript=5;
tracker[7].vector_ptr->subscript=17;
tracker[3].subscript=55;
printf("\n RENUMBER to use \"actual\" subscripts\n");
renumber_all_subscripts(FALSE);
printf("Sorted list:\n");
for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0)
{ printf(" %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);
}
else
{ printf(" %i:element[%i] at 0\n",i,tracker[i].subscript);
}
}
printf("\nBubble sort to get TRUE order back\n");
bubble_sort();
printf("Sorted list:\n");
for(int i=0;i<tracker_count;i++)
{ if ((size_t)tracker[i].vector_ptr!=0)
{printf(" %i:element[%i] or [%i]at %lu\n",i,tracker[i].subscript,tracker[i].vector_ptr->subscript,(size_t)tracker[i].vector_ptr);}
else {printf(" %i:element[%i] at 0\n",i,tracker[i].subscript);}
}
// END TEST SECTION
// don't forget to free everything
ss_vector_free_all_elements();
return 0;
}
int main(int argc, char *argv[])
{ char cmd[5],main_buffer[50]; // Intentionally big for "other" I/O purposes
cmd[0]=32; // blank = ASCII 32
// while(cmd!="R"&&cmd!="W" &&cmd!="E" &&cmd!=" ")
while(cmd[0]!=82&&cmd[0]!=87&&cmd[0]!=69)//&&cmd[0]!=32)
{ memset(cmd, '\0', sizeof(cmd));
memset(main_buffer, '\0', sizeof(main_buffer));
// default back to the cmd loop
cmd[0]=32; // blank = ASCII 32
printf("REad, TEst, WRITe, EDIt, or EXIt? ");
fscanf(stdin, "%s", main_buffer);
strncpy(cmd,main_buffer,4);
for(int i=0;i<4;i++)cmd[i]=toupper(cmd[i]);
cmd[4]='\0';
printf("%s received\n ",cmd);
// process top level commands
if(cmd[0]==82) {printf("READ accepted\n");} //Read
else if(cmd[0]==87) {printf("WRITe accepted\n");} // Write
else if(cmd[0]==84)
{ printf("TESt accepted\n");// TESt
Test();
}
else if(cmd[0]==69) // "E"
{ if(cmd[1]==68) {printf("EDITing\n");} // eDit
else if(cmd[1]==88) {printf("EXITing\n");exit(0);} // eXit
else printf(" unknown E command %c%c\n",cmd[0],cmd[1]);
}
else printf(" unknown command\n");
cmd[0]=32; // blank = ASCII 32
} // while()
// default back to the cmd loop
} // main()
1 votes
Il s'agit d'un (très, très petit) problème en C, mais comment avez-vous manqué toutes les solutions en C++ et C# pour cela ?
18 votes
"Si les pointeurs sont la seule solution, comment puis-je en garder la trace pour éviter les fuites ?". Attention, attention, et valgrind. C'est exactement la raison pour laquelle les gens ont si peur du C en premier lieu.
46 votes
Vous ne pouvez pas utiliser efficacement le C sans utiliser les pointeurs. N'ayez pas peur.
0 votes
Sans grandes librairies, une seule fonction pour tous, même pour les structures, par exemple : stackoverflow.com/questions/3456446/
14 votes
Utiliser le langage C sans pointeurs, c'est comme utiliser une voiture sans carburant.
2 votes
C est une tronçonneuse avec toutes les sécurités enlevées. Mais ne vous inquiétez pas, si vous perdez un doigt ou une main, C vous en donnera un autre. (Une autre tronçonneuse, bien sûr.)