これらの投稿は間違った順序である可能性があります! これは、3 つの投稿のシリーズの #2 です。ごめん。
私は、Lie Ryan のコードで「いくつかの自由を取り」、連結リストを実装して、連結リストを介して彼のベクトルの個々の要素にアクセスできるようにしました。これによりアクセスが可能になりますが、個々の要素にアクセスするには、検索のオーバーヘッドが原因で時間がかかります。つまり、適切な要素が見つかるまでリストを下っていきます。これは、0 からメモリ アドレスとペアになっているものまでを含むアドレス ベクトルを維持することで解決できます。これは単純な配列ほど効率的ではありませんが、少なくとも適切な項目を検索するために「リストをたどる」必要はありません。
// Based on code from https://stackoverflow.com/questions/3536153/c-dynamically-growing-array
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* ss_init_vector(size_t item_size) // item_size is size of one array member
{ vector= malloc(sizeof(ss_vector));
vector->this_element = 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;
vector->next_element=NULL;
// If there's an array of element addresses/subscripts, install it now.
return vector->this_element;
}
ss_vector* ss_vector_append(ss_vector* vec_element, int i)
// ^--ptr to this element ^--element nmbr
{ ss_vector* local_vec_element=0;
// If there is already a next element, recurse to end-of-linked-list
if(vec_element->next_element!=(size_t)0)
{ local_vec_element= ss_vector_append(vec_element->next_element,i); // recurse to end of list
return local_vec_element;
}
// vec_element is NULL, so make a new element and add at end of list
local_vec_element= calloc(1,sizeof(ss_vector)); // memory for one component
local_vec_element->this_element=local_vec_element; // save the address
local_vec_element->next_element=0;
vec_element->next_element=local_vec_element->this_element;
local_vec_element->subscript=i; //vec_element->size;
local_vec_element->size=i; // increment # of vector components
// If there's an array of element addresses/subscripts, update it now.
return local_vec_element;
}
void ss_vector_free_one_element(int i,gboolean Update_subscripts)
{ // Walk the entire linked list to the specified element, patch up
// the element ptrs before/next, then free its contents, then free it.
// Walk the rest of the list, updating subscripts, if requested.
// If there's an array of element addresses/subscripts, shift it along the way.
ss_vector* vec_element;
struct STRUCT_SS_VECTOR* this_one;
struct STRUCT_SS_VECTOR* next_one;
vec_element=vector;
while((vec_element->this_element->subscript!=i)&&(vec_element->next_element!=(size_t) 0)) // skip
{ this_one=vec_element->this_element; // trailing ptr
next_one=vec_element->next_element; // will become current ptr
vec_element=next_one;
}
// now at either target element or end-of-list
if(vec_element->this_element->subscript!=i)
{ printf("vector element not found\n");return;}
// free this one
this_one->next_element=next_one->next_element;// previous element points to element after current one
printf("freeing element[%i] at %lu",next_one->subscript,(size_t)next_one);
printf(" between %lu and %lu\n",(size_t)this_one,(size_t)next_one->next_element);
vec_element=next_one->next_element;
free(next_one); // free the current element
// renumber if requested
if(Update_subscripts)
{ i=0;
vec_element=vector;
while(vec_element!=(size_t) 0)
{ vec_element->subscript=i;
i++;
vec_element=vec_element->next_element;
}
}
// If there's an array of element addresses/subscripts, update it now.
/* // Check: temporarily show the new list
vec_element=vector;
while(vec_element!=(size_t) 0)
{ printf(" remaining element[%i] at %lu\n",vec_element->subscript,(size_t)vec_element->this_element);
vec_element=vec_element->next_element;
} */
return;
} // void ss_vector_free_one_element()
void ss_vector_insert_one_element(ss_vector* vec_element,int place)
{ // Walk the entire linked list to specified element "place", patch up
// the element ptrs before/next, then calloc an element and store its contents at "place".
// Increment all the following subscripts.
// If there's an array of element addresses/subscripts, make a bigger one,
// copy the old one, then shift appropriate members.
// ***Not yet implemented***
} // void ss_vector_insert_one_element()
void ss_vector_free_all_elements(void)
{ // Start at "vector".Walk the entire linked list, free each element's contents,
// free that element, then move to the next one.
// If there's an array of element addresses/subscripts, free it.
ss_vector* vec_element;
struct STRUCT_SS_VECTOR* next_one;
vec_element=vector;
while(vec_element->next_element!=(size_t) 0)
{ next_one=vec_element->next_element;
// free(vec_element->items) // don't forget to free these
free(vec_element->this_element);
vec_element=next_one;
next_one=vec_element->this_element;
}
// get rid of the last one.
// free(vec_element->items)
free(vec_element);
vector=NULL;
// If there's an array of element addresses/subscripts, free it now.
printf("\nall vector elements & contents freed\n");
} // 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(ss_vector* vec_element,int i)
// always make the first call to this subroutine with global vbl "vector"
{ ss_vector* local_vec_element=0;
// If there is a next element, recurse toward end-of-linked-list
if(vec_element->next_element!=(size_t)0)
{ if((vec_element->this_element->subscript==i))
{ return vec_element->this_element;}
local_vec_element= return_address_given_subscript(vec_element->next_element,i); // recurse to end of list
return local_vec_element;
}
else
{ if((vec_element->this_element->subscript==i)) // last element
{ return vec_element->this_element;}
// otherwise, none match
printf("reached end of list without match\n");
return (size_t) 0;
}
} // return_address_given_subscript()
int Test(void) // was "main" in the original example
{ ss_vector* local_vector;
local_vector=ss_init_vector(sizeof(apple)); // element "0"
for (int i = 1; i < 10; i++) // inserting items "1" thru whatever
{ local_vector=ss_vector_append(vector,i);}
// test search function
printf("\n NEXT, test search for address given subscript\n");
local_vector=return_address_given_subscript(vector,5);
printf("finished return_address_given_subscript(5) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,0);
printf("finished return_address_given_subscript(0) with vector at %lu\n",(size_t)local_vector);
local_vector=return_address_given_subscript(vector,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,FALSE); // without renumbering subscripts
ss_vector_free_one_element(3,TRUE);// WITH renumbering subscripts
// ---end of program---
// don't forget to free everything
ss_vector_free_all_elements();
return 0;
}