• C

Using Vectors in C

First of all, is there any difference between an array and a vector? Or is it just different names for the same thing basically?
This is actually a follow up question to my last question http://www.experts-exchange.com/Programming/Languages/C/Q_25661801.html.
As suggested by Infinity08, I am trying to write separate functions that will use the NameVector struct to add, remove, sort, search names etc...
At this stage, I am trying to get the last written program (refer to last post) into the AddName() function. One function at the time!
I am struggling about the arguments to pass to the function and/or its return value . I am thinking that I need to pass either the struct with its size so that the next name is appended to the existing name or pass a pointer to the struct NameVector instead...
I am getting so many errors...
Please point me in the right direction as i am a bit lost. Thank you!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//#include "struct.h"
//#include "ShowMenu.h"
#include "AddName.h"
//#include "DeleteName.h"

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};

int main(void)
{
	int answer;
	
	NameVector myNames;
	myNames.data = (Name*) malloc(myNames.allocated_size * sizeof (Name));
	myNames.allocated_size = 1;
	myNames.size = 0;
	Name* tmp;

	answer = ShowMenu();
		
	while (answer > 1 || answer <= 7)
	{
		switch(answer)
		{
			case 1: 
				//AddName();
				printf("\ncase one");
				break;

			case 2:
				//DeleteName();
				printf("\ncase two");
				break;

			case 3:
				//SortNames();
				printf("\ncase three");
				break;

			case 4:
				//SearchForName();
				printf("\ncase four");
				break;

			case 5:
				//ModifyName();
				printf("\ncase five");
				break;
				
			case 6:
				//PrintOutNames();
				printf("\ncase six");
				break;

			case 7:
				exit(1);
				break;
			default:
				printf("\nWrong choice! Enter a choice ranging from 1 to 7");
				break;
		
		}
		printf("\n\nPlease enter your choice: ");
		scanf("%d", &answer);
					
	}
	getchar();
	return 0;
}

 void AddName( NameVector* p, Name* s)
{
	
	char A_name[100];

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	gets(A_name);
	while (!feof(stdin))
	{
		strncpy(p->data[p->size], A_name, 24);
		p->data[p->size][24] = '\0';
		//increase the size of the array
		Name* s = (Name* )realloc(p->data, (p->allocated_size + 1) * sizeof(Name));
		p->allocated_size += 1;
		//check whether realloc did work and act accordingly
		if (!s)
		{
			exit(1);
		}
		p->data = s;
		p->size += 1;
								
		printf("\nPlease enter a name: ");
		gets(A_name);
	}
	//return NameVector;
}

Open in new window

SmanyxAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

SuperdaveCommented:
Lines 24 and 25 should be switched--set allocated_size before you reference it.

You should pass the NameVector struct (myNames) to the function so it can maintain the structure automatically.  The Name *s you're declaring in the function doesn't seem to have a purpose.
0
SmanyxAuthor Commented:
>>>Lines 24 and 25 should be switched--set allocated_size before you reference it.
I have done it.

>>>You should pass the NameVector struct (myNames) to the function so it can maintain the structure >>>automatically.

In main, i am calling AddName(myNames) and since I am not using a pointer as argument to the function, I have changed the operator -> to the operator .

Still, the program is not running!
void AddName(NameVector myNames)
{
	
	char A_name[100];

	puts("To end, press EOF (Ctrl + Z)");
	printf("\nPlease enter a name: ");
	gets(A_name);
	while (!feof(stdin))
	{
		strncpy(myNames.data[myNames.size], A_name, 24);
		myNames.data[myNames.size][24] = '\0';
		//increase the size of the array
		Name* s = (Name* )realloc(myNames.data, (myNames.allocated_size + 1) * sizeof(Name));
		myNames.allocated_size += 1;
		//check whether realloc did work and act accordingly
		if (!s)
		{
			exit(1);
		}
		myNames.data = s;
		myNames.size += 1;
		
								
		printf("\nPlease enter a name: ");
		gets(A_name);
	}
	//return NameVector;
}

Open in new window

0
shajithchandranCommented:
how do you want to  maintain the data ? in on structure (myNames) or different structures?
I think you should go for one structure per data. In that case.. you will have use an array of structure pointers.

#define INITIAL_COUNT 10
NameVector *myNames;


myNames = malloc(INITIAL_COUNT*sizeof(NameVector);
current_count= INITIAL_COUNT;
current =  0;
The above code will allocate 10 structure elements. So you can save 10 inputs.

while (answer > 1 || answer <= 7)
{
case 1:
              /* Here you will be adding data to a structure element.
              if(current >= current_count) {
                      temp = realloc(myNames,(current_count+5)*sizeof(NameVector);
                      if(temp)
                            myNames=temp;
                       else
                           exit(1); /*no memory;*/
               
                      myNames[current].data = (Name*) malloc(myNames.allocated_size * sizeof (Name));
                      myNames[current].allocated_size = 25;
                      myNames.size = 0;
                     addname(myNames[current);
                     current++;


This way... you can maintain data per structure element.
0
Acronis True Image 2019 just released!

Create a reliable backup. Make sure you always have dependable copies of your data so you can restore your entire system or individual files.

shajithchandranCommented:
opps. i missed current_count+=5.

Add that after successful realloc.
0
SuperdaveCommented:
Pass the pointer to the structure, like the first argument of the first version of AddName.
Sorry my previous advice was unclear; I was thinking "pointer" but didn't say it.  So the call will be AddName(&myNames) and the declaration will be void AddName(struct NameVector *p).
0
cupCommented:
Tp answer your original question: what is the difference between an array and a vector

A vector is a dynamically resizing array.  They can grow and shrink: normally implemented by using realloc.
0
Infinity08Commented:
>> As suggested by Infinity08, I am trying to write separate functions that will use the NameVector struct to add, remove, sort, search names etc...

>> Please point me in the right direction as i am a bit lost. Thank you!

What if I give you a set of function signatures, that you can then try to implement one by one ?

        NameVector* vec_create();                                                /* creates an empty vector */
        void vec_destroy(NameVector* vec);                                 /* destroys a vector (frees memory etc.) */
        void vec_add_name(NameVector* vec, char name[25]);    /* add a name to the vector */

Once these three are implemented and working, you can write a main that does something useful with them.

And then, you can always add new functions, as you need new functionality for the vector (like removing a name eg.).
0
itsmeandnobodyelseCommented:
>>>>> First of all, is there any difference between an array and a vector? Or is it just different names for the same thing basically?

The term "vector" was mostly used as a synonym for a dynamic array (class) which can grow and shrink dynamically. The most prominent vector class is C++ std::vector which is a template class from STL what is the Standard Template Library from C++ standard.

In C there are no classes and no class member functions. So you can't create new class types with built-in operators like in C++. But, you can define a structure which holds a pointer together with size information as members which could be used like a dynamic array in C++ with the exception that you need a global function for each operation you want to do with that array. One possible 'interface' for such an array structure was suggested by Infinity:  

(1)   NameVector* vec_create();

Creates a new NameVector (use malloc with argument sizeof(NameVector) ).  The data member of the new NameVector would point to an array of Name elements using an initial size (say 100 or use a macro defined as VEC_INIT_SIZE). You create the data by calling malloc with argument  VEC_INIT_SIZE * sizeof(Name) . The member allocated_size  would be assigned to VEC_INIT_SIZE and the size member to 0 (cause you didn't add a name until now).

(2) void vec_destroy(NameVector* vec);

Here you firstly free vec.data and then free vec.

(3) void vec_add_name(NameVector* vec, char name[25]);

Now it becomes thrilling ;-)

First check whether the size is equal to size_allocated. If so, you need to increase the array pointed to by the data member. Use realloc to add a new 'portion' of VEC_INIT_SIZE Name elements. Then increase the vec->allocated_size.

After the check the vec->size is less than the vec->allocated_size and you can allocate a new Name (pointer) to the slot vec->data[vec->size] . If done, copy the name argument to the newly allocated pointer (e. g. by strncpy where you copy max 24 characters and set terminating zero char to last char).

Finally increment the vec->size by 1 and you are thru.
0
Infinity08Commented:
>>         NameVector* vec_create();                                                /* creates an empty vector */

An alternative to this would be to use :

        void vec_create(NameVector* vec);                                         /* creates an empty vector */

Which one your prefer is up to you. It depends on how you want to use it.

This second form is more consistent with your current approach, and would be easiest to implement. Plus, it allows for the vector struct to be on the stack.
0
itsmeandnobodyelseCommented:
>>>> This second form is more consistent with your current approach

Then all functions operating on NameVector have a NameVector * as first argument.

>>>> Plus, it allows for the vector struct to be on the stack.

You can use it like

   NameVector nv;    // create an instance on the stack
   vec_create(&nv);  // pass it by address (pointer) to vec_create

Note, if you do so, you must not free the vec in vec_destroy (or it would crash in case it was created on the stack).

0
stefan73Commented:
A couple of thoughts:
- Performance: Don't realloc every time you add a new element. Realloc some more space (e.g., double the size when more space is needed) and keep an extra variable tracking the available free space.
- Functions needed: Basically, there are four functions, similar to the vector class in C++
  - constructor
  - read (with bounds check)
  - write  (with bounds check and reallocation)
  - destructor
All of those should be as generic as possible so that you can use them for other data types as well. This is not easy in C (see __typeof__ extensions & such).

The read access can have a "perl style autovivify" (e.g., you access something that doesn't exist and the read function will create it using a default value - in this case, an empty string).
0
itsmeandnobodyelseCommented:
>>>> The read access can have a "perl style autovivify"

Probably not. The get function can have a *bool* return which could indicate an out-of-boundary access.

  int vec_at(NameVector * vec, char name[25]);

"autovivify" is not so much common in C/C++. I know only one in std::map::operator[] where it was done that way (which was quite handy but actually made the operator[] unusable for simple find operations where you don't want to create a new entry). For the vector structure above it is important to have a standard behavior. In C++ the at function or operator[] could throw an exception in case of a wrong index (but doesn't for std::vector::operator[] !!!) . In C you would use an error return (if designed that way) or return the out-of-boundary element of the internal array what probably would crash later but didn't hide the wrong call argument.
0
itsmeandnobodyelseCommented:
>>>> int vec_at(NameVector * vec, char name[25]);

Of course an index should be passed also ...

int vec_at(NameVector * vec, int idx, char name[25]);

0
SmanyxAuthor Commented:
>>What if I give you a set of function signatures, that you can then try to implement one by one ?

I am happy to follow your directives. That way I learn to do things the best way.
I am not sure I fully understand how we'll go about achieving the end result. But I am willing to take up the challenge and follow your suggestions.
Please bear with me as I might ask "stupid" questions.
Please try to give a little more details in your posts to help me dig deeper. I am still very frail with pointers...

Here is what I think could be done. But it's not working. I am getting 2 error messages:

1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector2\implementnamevector2\main.cpp(29) : error C3861: 'vec_add_name': identifier not found
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector2\implementnamevector2\main.cpp(39) : error C2440: '=' : cannot convert from 'NameVector *' to 'Name (*)'


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 100

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void add_name(NameVector* vec, char name[25]);




int main(void)
{
	NameVector vec;
	Name name[25];

	vec_create(&vec);
	vec_destroy(&vec);
	vec_add_name(&vec, name);
	
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;

	vec->data = (NameVector*)malloc(vec->allocated_size * sizeof(NameVector));
	
}

void vec_destroy(NameVector* vec)
{

}

void add_name(NameVector* vec, char name[25])
{

}

Open in new window

0
itsmeandnobodyelseCommented:
>>>> error C3861: 'vec_add_name': identifier not found
You called it add:name above.

   void add_name(NameVector* vec, char name[25]);

>>>> error C2440: '=' : cannot convert from 'NameVector *' to 'Name (*)'
vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
         

 
0
Infinity08Commented:
>> Please bear with me as I might ask "stupid" questions.

That's the idea :) Whenever you're unsure about something, ask us, and we'll be happy to assist you further :)


>> 1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector2\implementnamevector2\main.cpp(29) : error C3861: 'vec_add_name': identifier not found

Notice how you named the function add_name instead of vec_add_name :

>> void add_name(NameVector* vec, char name[25]);


>>         vec->data = (NameVector*)malloc(vec->allocated_size * sizeof(NameVector));

vec->data is a Name*, not a NameVector*, so the cast is wrong.
0
Infinity08Commented:
Other than that, the vec_create looks good. I wouldn't allocate 100 items to begin with though ... Chances are that that's a lot bigger than it needs to be. I'd start with 2 or 4.
0
itsmeandnobodyelseCommented:
A tip: take the error messages literally.

>>>> main.cpp(29): error C3861: 'vec_add_name': identifier not found

means in line 29 of your main.cpp you used the name 'vec_add_name'  but the identifier ''vec_add_name' was not known to that time.

Note, the compiler needs to know function prototypes before you can call them. That's why all vec functions must be *declared* before first use. And of course the declaration must match to call and implementation.

>>>> main.cpp(3) error C2440: '=' : cannot convert from 'NameVector *' to 'Name (*)'

In line 39 of main.cpp you tried to assign a pointer 'NameVector *' to a (member) variable that was declared as Name* .

0
itsmeandnobodyelseCommented:
>>>> I wouldn't allocate 100 items to begin with though ... Chances are that that's a lot bigger than it needs to be. I'd start with 2 or 4.

You probably know pretty good how many names you will use for the test program. Try to use an initial size that is about a third of that you would need lastly. That way you would realloc about 2 times what is a reasonable compromise for having a dynamical growing array rather than having a fixed array with maximum size.

Some implementations of dynamic arrays do not grow in equally sized chunks but were doubling their current size. Though you have much less reallocations even for huge arrays that way - cause the size would grow exponantially - it nevertheless isn't a good idea cause it requires bigger and bigger contiguous memory each time while the old (freed) memory cannot be used for that purpose as it is too small. So, I usually don't spare with the initial size (2.5 k actually is nothing for nowadays memory) and would grow in chunks of the same size.
0
Infinity08Commented:
In any case ... it's useful to keep the initial size low for testing - that way you can easily test whether the realloc's work as they're supposed to.
0
SmanyxAuthor Commented:
Thanks I have corrected the pointed mistakes.
But in the program I have:
typedef char Name[25];
and
void vec_add_name(NameVector* vec, char name[25]);
I am confused about Name and name.
So is the compiler too because it is giving me this error message:
error C2664: 'vec_add_name' : cannot convert parameter 2 from 'Name [25]' to 'char []'
0
Infinity08Commented:
>> typedef char Name[25];
>> and
>> void vec_add_name(NameVector* vec, char name[25]);

To take away your confusion, change the function prototype to :

        void vec_add_name(NameVector* vec, Name name);

name is the name of the parameter that is passed to the function, and Name is its type.

Note that Name has been typedef'd to be an array of 25 char's.
0
itsmeandnobodyelseCommented:
Name is a char[25] and Name[25] is an array of 25 names.

if you pass char[25] as argument you were passing one single name (what is a char array of 25).

>>>> cannot convert parameter 2 from 'Name [25]' to 'char []'

You should/could pass one single name to the vec_add_name e. g. like

   Name name = "John";
   vec_add_name(&vec, name);

or alternatively (not using the type Name).  

   vec_add_name(&vec, "Mary");

or

   char name[25];
   ...
   strcpy(name, "Bob");
   vec_add_name(&vec, "Mary");
   
0
itsmeandnobodyelseCommented:
Last should be
>>>> vec_add_name(&vec, name);

Note a Name is typedef'd to be a char[25] array. But, when passing an array to a function C (and C++) actually passes a pointer to char (pointing to first char of array) and looses size information of the array, i. e. the 'char name[25]' argument was equivalent to 'char name[]' which was equivalent to 'char * name' and also to 'Name name'  (because of the typedef).
0
SmanyxAuthor Commented:
>>>void vec_add_name(NameVector* vec, Name name);
name is the name of the parameter that is passed to the function, and Name is its type.
Note that Name has been typedef'd to be an array of 25 char's.

with this I am getting the following 2 error messages:

1>main.obj : error LNK2001: unresolved external symbol "void __cdecl vec_add_name(struct NameVector *,char (* const)[25])" (?vec_add_name@@YAXPAUNameVector@@QAY0BJ@D@Z)
1>C:\Documents and Settings\user1\My Documents\Visual Studio 2005\Projects\ImplementNameVector2\ImplementNameVector2\Debug\ImplementNameVector2.exe : fatal error LNK1120: 1 unresolved externals

>>>Last should be
>>>> vec_add_name(&vec, name);

With this I am getting one error message:

 error C2664: 'vec_add_name' : cannot convert parameter 2 from 'Name [25]' to 'char []'

Please look at my code.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, char name[25]);
//void vec_add_name(NameVector* vec, Name name[25]);





int main(void)
{
	NameVector vec;
	Name name[25];

	vec_create(&vec);
	vec_destroy(&vec);
	vec_add_name(&vec, name);
	
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;

	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_destroy(NameVector* vec)
{

}

void add_name(NameVector* vec, char name[25])
{

}

Open in new window

0
itsmeandnobodyelseCommented:
>>>>        Name name[25];

That is still wrong. You must not add an array of 25 names but only one single name

        NameVector vec;
        Name name;
 
        vec_create(&vec);
        vec_destroy(&vec);
        strcpy(name, "John");
        vec_add_name(&vec, name);
        strcpy(name, "Mary");
        vec_add_name(&vec, name);
        // ... and so on

        // or
        vec_add_name(&vec, "Bob");
        vec_add_name(&vec, "Lisa");

0
SmanyxAuthor Commented:
>>> NameVector vec;
        Name name;
 
        vec_create(&vec);
        vec_destroy(&vec);
        strcpy(name, "John");
        vec_add_name(&vec, name);
        strcpy(name, "Mary");
        vec_add_name(&vec, name);
        // ... and so on

        // or
        vec_add_name(&vec, "Bob");
        vec_add_name(&vec, "Lisa");

I thought I was creating an empty vector!

>>         NameVector* vec_create();                                                /* creates an empty vector */

>>An alternative to this would be to use :

        void vec_create(NameVector* vec);                                         /* creates an empty vector */

>>Which one your prefer is up to you. It depends on how you want to use it.

At this point in time, I don't have any names yet. How can I cater for that, knowing that will be added but at a later stage?

I have change from name from an array:Name name[25]; to a simple variable:Name name; but still isn't working...
0
Infinity08Commented:
>> I have change from name from an array:Name name[25]; to a simple variable:Name name; but still isn't working...

Did you do what I suggested in http:#30717289 ? It should make things a bit clearer.

Could you post your entire latest code ?



>> At this point in time, I don't have any names yet. How can I cater for that, knowing that will be added but at a later stage?

Don't worry about that for now. The create and destroy functions should work first. Make sure to modify the allocated_size member !!
0
SmanyxAuthor Commented:
>>>Could you post your entire latest code ?
I posted it already at http:#30721113 

>>>Did you do what I suggested in http:#30717289 ? It should make things a bit clearer.
I think I did, but it's still not working.
0
Infinity08Commented:
>> I posted it already at http:#30721113 

That's not the latest code - you made modifications after that, as you said in http:#30724773.


>> I think I did, but it's still not working.

I can't see that in the code you posted ;)
0
SmanyxAuthor Commented:
Sorry, I think I made a mistake.
Ok, here is the code as it stands now.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, char name[25]);
//void vec_add_name(NameVector* vec, Name name[25]);





int main(void)
{
	NameVector vec;
	Name name;

	vec_create(&vec);
	vec_destroy(&vec);
	
	vec_add_name(&vec, name);
	
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;

	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_destroy(NameVector* vec)
{

}

void add_name(NameVector* vec, char name[25])
{

}

Open in new window

0
itsmeandnobodyelseCommented:
I assume it compiles ?

>>>>      Name name;

Better initialize it like

   Name name = "";

or

   Name name = "Smanyx";

cause otherwise you might add garbage to the vector.

0
Infinity08Commented:
Well, my suggested change is not there yet :

>> void vec_add_name(NameVector* vec, char name[25]);

would be clearer if it were :

        void vec_add_name(NameVector* vec, Name name);


Note that the implementation of the function needs to match the prototype :

>> void add_name(NameVector* vec, char name[25])
>> {
>> 
>> }

The function name is not the same, and the second parameter has to be adjusted like above.


And then finally, in your main, you have :

>>       vec_destroy(&vec);
>>       
>>       vec_add_name(&vec, name);

The calls are right, but the order is not. You should destroy the vector only AFTER you don't need it any more - ie. after the call to vec_add_name in this case.


Ok. Now, on to the vec_destroy function.
0
SmanyxAuthor Commented:
>>>I assume it compiles ?
Unfortunately, it doesn't.
I am getting this weird error messages:

1>main.obj : error LNK2019: unresolved external symbol "void __cdecl vec_add_name(struct NameVector *,char * const)" (?vec_add_name@@YAXPAUNameVector@@QAD@Z) referenced in function _main
1>C:\Documents and Settings\user1\My Documents\Visual Studio 2005\Projects\ImplementNameVector3\ImplementNameVector3\Debug\ImplementNameVector3.exe : fatal error LNK1120: 1 unresolved externals
0
Infinity08Commented:
See my previous post ;)
0
itsmeandnobodyelseCommented:
Use

void vec_add_name(NameVector* vec, Name name);

for prototype and

void vec_add_name(NameVector* vec, Name name)
{
   
}

for implementation as Infinity told you.

You currently still have 'add_name' function implemented what is the reason for the linking error.
0
SmanyxAuthor Commented:
Yes, I made all the changes carefully and the program is now, finally compiling. Thanks.
0
Infinity08Commented:
Great :) Now, for the vec_destroy function :)
0
SmanyxAuthor Commented:
By destroying the NameVector I think I understand to free the memory that was set aside to hold it...
I am trying this:
void vec_destroy(NameVector* vec)
{
      free(vec->data);
      free(vec);
}
but it's not working...
0
Infinity08Commented:
>>       free(vec);

Don't do this. There's no need (and in fact, it might be harmful).

The vec_destroy function should do the complete opposite of the vec_create function, ie. a free instead of the malloc, and set the allocated_size and size back to 0.
0
Infinity08Commented:
Also, don't forget to set the pointer to NULL after doing the free :

        free(vec->data);
        vec->data = 0;
0
itsmeandnobodyelseCommented:
>>>> free(vec);

No, you can't free it here cause it wasn't  (no longer) created by your create function.

>>>> but it's not working...

what is not working?
0
SmanyxAuthor Commented:
//Windows has triggered a breakpoint in ImplementNameVector3.exe.
//This may be due to a corruption of the heap, and indicates a bug in ImplementNameVector3.exe or
//any of the DLLs it has loaded.
//The output window may have more diagnostic information

This is the error message I am getting.
0
Infinity08Commented:
See my last two posts.
0
SmanyxAuthor Commented:
void vec_destroy(NameVector* vec)
{
      vec->allocated_size = 0;
      vec->size = 0;
      free(vec->data);
      vec->data = NULL;
      
}

This works perfect !!!
0
itsmeandnobodyelseCommented:
Very good.

did you move the vec_destroy behind the vec_add_name ?
0
SmanyxAuthor Commented:
This is great :)
As adding a name was already working, I have just modified it to suit to vec_add_name() function.
Here is the code, as it stands right now.
No compiling errors !!!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
//void vec_add_name(NameVector* vec, char name[25]);
void vec_add_name(NameVector* vec, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";

	vec_create(&vec);
	vec_add_name(&vec, name);
	vec_destroy(&vec);
	
	getchar();
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	vec->data = (Name*) malloc(vec->allocated_size * sizeof(Name));

	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(name);
	while (!feof(stdin))
	{
		strncpy(vec->data[vec->size], name, 24);
		vec->data[vec->size][24] = '\0';
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + 1) * sizeof(Name));
		vec->allocated_size += 1;
		if (!tmp)
		{
			//check whether realloc did work and act accordingly
			exit(1);
		}
		vec->data = tmp;
		vec->size += 1;
								
		printf("\nPlease enter a name: ");
		gets(name);
	}
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
SmanyxAuthor Commented:
A question just crosses my mind. Where exactly are all the names entered actually stored??
I am thinking of vec->data, but this is not an array as such, is it?!
0
itsmeandnobodyelseCommented:
>>>>      puts("To end, press Ctrl + Z");
>>>>      printf("\nPlease enter a name: ");
>>>>      gets(name);
>>>>      while (!feof(stdin))
      
All that must be moved to main and then call vec_add_name for each name you got from user input.

>>> I am thinking of vec->data, but this is not an array as such

vec_data is an array. As told pointers and arrays are pretty much exchangeable in C. You allocated an array of Name elements by malloc(vec->allocated_size * sizeof(Name)). That way you got an array and the pointer return from malloc was pointing to the first array element.
0
itsmeandnobodyelseCommented:
>>>> gets(name);

BTW, the Name is only 24 chars + terminating zero. You would need to check that after input.

So it would be better to use a (much) bigger buffer for the gets and copy a maximum of 24 chars to the name:

   Name name = "";  
   char input[128] = { '\0' };  
   ...
   gets(input);
   // copy only so much chars from input so that the name buffer was not exceeded
   // a terminating zero char in input would stop the strncpy (and the 0 was copied to name)
   strncpy(name, input, sizeof(Name));
   // just to make sure it was terminated in case it was 25 chars or more
   name[24] = '\0';

0
SmanyxAuthor Commented:
>>>So it would be better to use a (much) bigger buffer for the gets and copy a maximum of 24 chars to the name:

Okay, I have implemented it. It's running fine. What should be next?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
//void vec_add_name(NameVector* vec, char name[25]);
void vec_add_name(NameVector* vec, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	vec_destroy(&vec);
	
	getchar();
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	vec->data = (Name*) malloc(vec->allocated_size * sizeof(Name));

	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + 1) * sizeof(Name));
	vec->allocated_size += 1;
	//check whether realloc did work and act accordingly
	if (!tmp)
	{
		exit(1);
	}
	vec->data = tmp;
	vec->size += 1;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
In vec_add_name :


>>       vec->data = (Name*) malloc(vec->allocated_size * sizeof(Name));

This was already done in the vec_create function, so there's no need to do it again.


>>       strncpy(vec->data[vec->size], name, 24);
>>       vec->data[vec->size][24] = '\0';

Before you copy the name into the array, you have to make sure that there's still room in the array. In other words, you have to make sure that the allocated_size is sufficiently big.


>>       Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + 1) * sizeof(Name));

You should only call realloc when you NEED to (ie. only when there is no more room in the array to add the new name).
Note that it's also a good idea to add more than just 1 position to the array.
0
itsmeandnobodyelseCommented:
In addition to above comment you might look at http:#30699620 for a brief description how the vec_add_name could/should be implemented.


When the vec_add_name was done you can go for the vec_get_name which could have a prototype

  Name * vec_at(NameVector * vec, int idx);

or - alternatively -

  int vec_get_name(NameVector * vec, int idx, Name name);

The first would return the a pointer to the name stored in vec array at position idx (or NULL if idx is out-of-boundaries).  

The second would fill the name passed (note a char array passed to a function is actually a char pointer pointing to first char element) with the array element if idx is valid or would return -1 otherwise.

I think the second would fit better to your current interface which was not dealing with pointers to Name.
0
SmanyxAuthor Commented:
I have adjusted the code to reflect your last remarks.
I don't really get my head around vec_get_name() function. What is it supposed to do? Is it like a search function, searching the array for a name entered by the user?
I think I need a little more hints. Thanks.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, int index, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}

	//vec_get_name(&vec, index, name);
	vec_destroy(&vec);
	
	getchar();
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	if ((vec->size) < (vec->allocated_size))
	{
		strncpy(vec->data[vec->size], name, 24);
		vec->data[vec->size][24] = '\0';
	}
	else
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		//check whether realloc did work and act accordingly
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
		strncpy(vec->data[vec->size], name, 24);
		vec->data[vec->size][24] = '\0';
		
	}
	vec->size += 1;
}

int vec_get_name(NameVector* vec, int index, Name name)
{
	
	return index;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
The vec_add_name looks good now.

Just one thing. You currently have these lines in both the if and the else blocks :

>>             strncpy(vec->data[vec->size], name, 24);
>>             vec->data[vec->size][24] = '\0';

This means you can move them outside of the if-else structure !


>> int vec_get_name(NameVector* vec, int index, Name name)

First of all, use size_t for indexes (not int).

Then, for the implementation, there are a few things you need to do : check that the index is valid, and then simply copy the name at that index to the name parameter.
0
itsmeandnobodyelseCommented:
>>>> I don't really get my head around vec_get_name() function. What is it supposed to do?

The vec functions are supposed to handle a dynamic array. The main purpose of an array is to allow you to retrieve the elements back and the major retrieval function would retrieve one single name by index. In fixed-sized arrays you do that by (operator) [], e. g.

  int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  int x = arr[5];  // x is 6 after that

For the NameVector you could do

   NameVector vec;
   vec_create(&vec);
   // store 3 names
   vec_add_name(vec, "John");
   vec_add_name(vec, "Mary");
   vec_add_name(vec, "Sam");
   printf("Name 1: %s\n", vec.data[0]);
   printf("Name 2: %s\n", vec.data[1]);
   printf("Name 3: %s\n", vec.data[2]);
 
what would work. But the code would access the internal data array of the vec and has no error check. The goal is to access the vector only with functions in order to have the container functionality encapsulated. So we need a function for reading one single name back from our vec without needing to know that the names were stored in the data member. That is where the vec_get_name comes into play:

   NameVector vec;
   int i = 0;
   vec_create(&vec);
   // store 3 names
   vec_add_name(vec, "John");
   vec_add_name(vec, "Mary");
   vec_add_name(vec, "Sam");
   for (i = 0; i < 3; ++i)
   {
         Name name;
         // get name by index from vec container
         if (vec_get_name(&vec, i, name) != 0)
             break;
         // print the name
         printf("Name %d: %s\n", i+1, name);
   }

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
itsmeandnobodyelseCommented:
>>>> First of all, use size_t for indexes (not int).
The size_t is a typedef of an unsigned integer. That means it runs from 0 to 4294967295 in a 32-bit system where the second number is 2^32 - 1.  Normal (signed) integers run from -2147483648 to 2147483647 what is -2^31 to 2^31-1. In the range from 0 to 2^31-1 both integers have identically bits and as long as your integers are in that range you could use signed int or unsigned int with no difference. You easily see that for your vector structure we only need integers from range 0 to 2^31. We neither need negative sizes nor do we want to store more than 2GB of names. From that both size_t and int were valid alternatives for size and index variables.

However mixing signed and unsigned integers is not so good an idea. For any comparision between a size_t and an int , the compiler will give you a warning that you were comparing signed int with unsigned int. That is because of negative numbers in the signed int which would turn to huge numbers if looked on as unsigned int.

    int i = -1;
    size_t s = -2;   // that compiles but s is now 4294967294
    if (s - i > 0)      
    {
         // s-i is greater 0 cause (s-i) is an unsigned and != 0        

To avoid such subtile errors use either int or either size_t for integers you have to compare but not both. And as you started with size_t for allocated_size and size in struct NameVector you also should use the size_t for the index (as suggested by Infinity):

int vec_get_name(NameVector * vec, size_t idx, Name name);

Note, of course you can use 'int' for return code of the vec_get_name same as your main function has an int return. In C functions with an int return normally return 0 on success or !=0 otherwise.
0
Infinity08Commented:
>> The size_t is a typedef of an unsigned integer.

Not necessarily. It is an unsigned integral type, yes. But not necessarily an unsigned int.
It is the type that is returned by sizeof, and thus guaranteed to be able to hold all sizes of any existing structure (an array in this case).
So, it's a good candidate to be used as the type for array indexes.


>> In the range from 0 to 2^31-1 both integers have identically bits and as long as your integers are in that range you could use signed int or unsigned int with no difference.

I don't like taking that risk ... especially if there's no real reason to do so heh. A size_t is guaranteed to work for any valid index (which is not necessarily the case for int's or unsigned int's).
0
SmanyxAuthor Commented:
I'm still not sure whether this is the way you wanted it implemented...
There is no compile errors but the program is not running 100%.
Don't really know what I have done wrong but somehow it just doesn't feel right...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 2

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int result, index = 0;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	
	puts("\n\n");
	puts("To end, press Ctrl + Z");
	printf("\nEnter the name to search for: ");
	gets(name);
	while (!feof(stdin))
	{
		if (result = vec_get_name(&vec, index, name) != -1)
		{
			printf("\n %s found at position %d", name, index);
		}
		else
		{
			printf("\n %s was not found.");
		}
		printf("\nEnter the name to search for: ");
		gets(name);
	}
	vec_destroy(&vec);
	
	getchar();
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	int begin = 0;
	int end;
	int condition;

	end = (sizeof(vec->data) / sizeof(vec->data[0])) - 1;

	while (begin <= end)
	{
		index = (begin + end) / 2;
		if ((condition = strcmp(vec->data[vec->size], name)) == 0)
		{
			return index;
		}
		else if (condition < 0)
		{
			begin = index + 1;
		}
		else
		{
			end = index - 1;
		}
		return -1;
	}
	return index;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
Ok, it looks like what you were trying to implement, is a search that looks for the name in the array.

What Alex had in mind with the vec_get_name function, is to get the name at a specific index in the array. So, if the array contain s the names "Alice", "Bob" and "Cindy" (in that order), and you call the function like this :

        Name name = "";
        vec_get_name(&vec, 1, name);

then this would get the name at the second position (at index 1) in the vector. After this call, the 'name' variable will contain "Bob".
0
itsmeandnobodyelseCommented:
>>>> I don't like taking that risk ... especially if there's no real reason to do so heh.

You know I never use(d) size_t and unsigned for numbers myself (but only for binary data) and I can tell you that the risk is minimal to not existing at least in my experience. You also will know that the constant -1 often was assigned to unsigned integers cause of course -1 is much more handy than 4294967295 or 0xffffffff. And - for god sake - you always can compare an unsigned int with -1 for being equal

  if (uindex == -1)   // true if before there was an assignment i = -1;

On the other side I have seen much flaws like

   unsigned int i1 = 10;
   unsigned int i2 = 11;
   if (i1 - i2 >= 0)   // unfortunately unsigned ints always were greater-equal to zero
        ...

or

   unsigned int i = 10;
   while (--i >= 0)  // always true
   {
          // welcome in the infinite loop
          ....

which only were due to the usage of unsigned integers and discontinuosity left of the 0.

(we could/should continue that discussion outside of this thread, if you like).

>>>> It is an unsigned integral type, yes. But not necessarily an unsigned int.
Yes,  the VC compiler used by Smanyx (and me) has size_t defined as 'unsigned __int64'.
0
itsmeandnobodyelseCommented:
>>>> what you were trying to implement, is a search that looks for the name in the array.

That would be a new (senseful) function to add

  size_t vec_search_name(NameVector * vec, Name name);

The return value would be the index in the array if the name was found or -1 if not found. To avoid the -1 in the functions you could define a constant above like

#define NAME_NOT_FOUND -1

and use that macro for assignment and comparision.
0
SmanyxAuthor Commented:
I went off track with my last post !!
I did not quite get what you wanted to achieve with vec_get_name(), but I do now.
Below is what I think you wanted me to implement...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 2

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	printf("\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}
	
	vec_destroy(&vec);
	
	getchar();
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	//check that the index passed as parameter is valid
	int x;  //number of elements in the array

	x = (sizeof(vec->data) / sizeof(vec->data[0])) - 1;
	if (index > x)
	{//invalid index
		printf("invalid index entered.");
		exit(1);
	}
	strcpy(name, vec->data[index]);
	
	return index;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
>>       x = (sizeof(vec->data) / sizeof(vec->data[0])) - 1;

You don't need x. You already have the 'size' member. You can use that to decide if the given index is valid or not.


I also wouldn't call exit(1), just because the user entered an invalid index. You can set an error flag instead.

Furthermore, I don't see the point in returning the index. The function was called with that same index, so the caller already knows what it is (there's no added value in returning it).

What you could do however, is return an error code (eg. 0 if success, 1 if failure).
0
itsmeandnobodyelseCommented:
>>>> I did not quite get what you wanted to achieve with vec_get_name(), but I do now.

Hmm, that is essential. The NameVector is a container (a little database). The only purpose of a container is to store elements for later use. If you want to use a container with entries you would need to "get" the stored elements somehow.

Assume you have opened an empty textfile with an editor, say notepad. Assume further you would add 'names', one name per line to that text file and finally store the file. Then you have a stored or persistent container with names. If you want to 'use' that container in a program, e. g. for writing mails to the names stored in the textfile, you would open the textfile and read line by line to retrieve the names you added by the editor.

Same happens here. We create a new container, and (let the user) add names which we store element by element. We do that to be able *later* to use these names stored in the container, e. g. by sorting those names alphabetically or to print them out or to print only those which start with 'A'' or, or, ...  And the basic retrieval function for *any* array container is to retrieve the entries by their index where they were stored in the array. That way you can get all names for example by iterating the index from 0 to size-1 or by iterating from 0 until the vec_get_name would return error. But for example a sort function would not only read from 0 to size-1 incrementing by 1 but would access also from the middle:

// assume we have a function that gives us the size from vector
siz = vec_get_size(&vec);

// that if is important because if the unsigned
if (siz > 1)
{
   for (i = 0; i < siz - 1; ++i)
   {
        Name nam1;
        // get name from slot i to nam1
        vec_get_name(&vec, i, nam1);
        for (j = 0; j < siz; ++j)
        {
            Name nam2;
            // get name from slot j to nam2
            vec_get_name(&vec, j, nam2);
            // check if nam1 > nam2
            if (strcmp(nam1, nam2) > 0)
            {
                   // swap both names
                   vec_swap(&vec, i, j);
             }
        }
   }

Voilà, we now have a sorted NameVector !!!!

Do you now understand why we/you need a get function for the array and for what it could be used?
0
SmanyxAuthor Commented:
>>>You don't need x. You already have the 'size' member. You can use that to decide if the given index is valid or not.

I have adjusted the program according to that remark.

>>>Do you now understand why we/you need a get function for the array and for what it could be used?

Yeah, little by little, one step at the time as we are developing the program I am getting a good feel of what we are achieving. Thanks a lot for the explanation beside the code. Reading it opens further
my horizon.

The code that I have posted does compile but the vec_search_name () is not executing for some weird reasons...


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5
#define NAME_NOT_FOUND -1
#define INVALID_INDEX -1


typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;
	int result;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	printf("\n\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		//printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}
	

	printf("\n\n\nEnter the name to search for: ");
	gets(input);
	while (!feof(stdin))
	{
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		result = vec_search_name(&vec, name);
		if (result != -1)
		{
			printf("\n %s found at position %d", name, index);
		}
		else
		{
			printf("\n %s was not found.");
		}
		printf("\nEnter the name to search for: ");
		gets(input);
	}
	
	vec_destroy(&vec);
	
	system("pause");
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	int MaxIndex;

	//check that the index passed as parameter is valid
	MaxIndex = (vec->size) - 1;
	if (index > MaxIndex)
	{
		printf("Invalid index entered.");
		return INVALID_INDEX;
	}
	strcpy(name, vec->data[index]);
	printf("\n%s", name);

	return 0;
}
size_t vec_search_name(NameVector* vec, Name name)
{
	int index;
	int begin = 0;
	int end = (vec->size) - 1;
	int found = 0;

	while (end >= begin && found == 0)
	{
		index = (end + begin) / 2;
		if (strcmp(name, vec->data[vec->size]) == 0)
		{
			found = 1;
			return index;
		}
		else
		{
			if (strcmp(name, vec->data[vec->size]) < 0)
			{
				end = index -1;
			}
			else
			{
				begin = index + 1;
			}
		}
		/*if (found == 1)
		{
			printf("\nThe name %s was found at location %d", name, index);
		}
		else
		{
			printf("\nThe name %s was not found.", name);
		}*/
	}
	return NAME_NOT_FOUND;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
>> I have adjusted the program according to that remark.

That looks good - with one minor detail : the type of MaxIndex should be size_t, not int (for the same reason as before).


>> I am getting a good feel of what we are achieving.

That's great :) Once you're ready, you can move all the NameVector functionality into a separate .c and .h file. That way, all you need to do to be able to use the NameVector type, is to include that header file, and call the appropriate functions.

Can you also see that your main has become a lot cleaner, compared to the original code where everything was done in main ?


>> but the vec_search_name () is not executing for some weird reasons...

First of all : pay attention to the types. Where needed, use size_t instead of int !

Then, take a look at this line :

>>             if (strcmp(name, vec->data[vec->size]) == 0)

What are you comparing here ... specifically the second argument of strcmp. Shouldn't you be using 'index' ?
0
itsmeandnobodyelseCommented:
>>>> the type of MaxIndex should be size_t,

Better omit the temporary MaxIndex at all,  cause (vec->size) - 1 is not well defined in case vec->size == 0. Generally, try to avoid subtraction (especially near 0) when dealing with unsigned integers.

So use

      //check that the index passed as parameter is valid
      if (index >= vec->size)
                {


>>>> end = index -1;

That statement is dangerous when using size_t for variables 'end' and 'index' in case index==0  (what actually is a valid case). Then the while condition (end >= begin) never would be true.

I strongly recommend to not using size_t when doing a binary search. It has no advantages but only malfits.

0
SmanyxAuthor Commented:
>>>What are you comparing here ... specifically the second argument of strcmp. Shouldn't you be using 'index' ?

Thanks. That's what happens when copy-paste is used extensively...
I have changed it to:
 if (strcmp(name, vec->data[index]) == 0)
but still doesn't work!
size_t vec_search_name(NameVector* vec, Name name)
{
	size_t index;
	size_t begin = 0;
	size_t end = (vec->size) - 1;
	size_t found = 0;

	while (end >= begin && found == 0)
	{
		index = (end + begin) / 2;
		if (strcmp(name, vec->data[index]) == 0)
		{
			found = 1;
			return index;
		}
		else
		{
			if (strcmp(name, vec->data[index]) < 0)
			{
				end = index -1;
			}
			else
			{
				begin = index + 1;
			}
		}
		
	}
	return NAME_NOT_FOUND;
}

Open in new window

0
itsmeandnobodyelseCommented:
should mean

>>> the while condition (end >= begin) never would be false.

0
itsmeandnobodyelseCommented:
>>>> but still doesn't work!

Can you tell "what" doesn't work?
0
Infinity08Commented:
>> I strongly recommend to not using size_t when doing a binary search. It has no advantages but only malfits.

That's not true. Using an int instead of size_t would have the same problem you're referring to - only at the other end of the scale (due to overflow rather than underflow).

So, there's no advantage of using int over size_t - the code will be similar and equally complicated/simple. It does however have a downside, and that is that an int cannot hold every valid index (as has been said before), so it cannot be correct all the time.

You just have to take care of treating an empty vector as a special case (which should be caught before ever starting the binary search), and of treating the index 0 as a special case.

Note that, since you use the highest size_t value as an error code, it cannot be a valid index. Keep that in mind in the rest of your code.
0
SmanyxAuthor Commented:
>>>> but still doesn't work!
Can you tell "what" doesn't work?

The vec_search_name() function doesn't get executed at all.
From line 59: gets(input);,  it jumps straight to line 77: vec_destroy(&vec);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5
#define NAME_NOT_FOUND -1
#define INVALID_INDEX -1


typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;
	int result;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	printf("\n\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		//printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}
	

	printf("\n\n\nEnter the name to search for: ");
	gets(input);
	while (!feof(stdin))
	{
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		result = vec_search_name(&vec, name);
		if (result != -1)
		{
			printf("\n %s found at position %d", name, index);
		}
		else
		{
			printf("\n %s was not found.");
		}
		printf("\nEnter the name to search for: ");
		gets(input);
	}
	
	vec_destroy(&vec);
	
	system("pause");
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	if (index >= vec->size)
	{
		printf("Invalid index entered.");
		return INVALID_INDEX;
	}
	strcpy(name, vec->data[index]);
	printf("\n%s", name);

	return 0;
}
size_t vec_search_name(NameVector* vec, Name name)
{
	size_t index;
	size_t begin = 0;
	size_t end = (vec->size) - 1;
	size_t found = 0;

	while (end >= begin && found == 0)
	{
		index = (end + begin) / 2;
		if (strcmp(name, vec->data[index]) == 0)
		{
			found = 1;
			return index;
		}
		else
		{
			if (strcmp(name, vec->data[index]) < 0)
			{
				end = index -1;
			}
			else
			{
				begin = index + 1;
			}
		}
		
	}
	return NAME_NOT_FOUND;
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
>> The vec_search_name() function doesn't get executed at all.

You used Ctrl+Z to end the input ... So, the eof of stdin is reached. No more input will be read from stdin.

Instead of using Ctrl+Z, use an empty line to signify the end of input. When you read an empty line, you can end the loop.
0
itsmeandnobodyelseCommented:
>> The vec_search_name() function doesn't get executed at all.

Hmm. It should be executed at least once. Try to set a breakpoint (click left margin to set a breakpoint) before and in the while loop and step by F10.
0
SmanyxAuthor Commented:
>>>You used Ctrl+Z to end the input ... So, the eof of stdin is reached. No more input will be read from stdin.
What I find weird is that I also use Ctrl+Z to end input for the vec_add_name() and the vec_get_name() without any trouble. Why not for the vec_search_name??

>>>use an empty line to signify the end of input. When you read an empty line, you can end the loop.
I have changed the loop condition to:
while (input != "")

The logic in the vec_search_name() doesn't seem to be correct as I am getting incorrect output.

>>>Hmm. It should be executed at least once. Try to set a breakpoint (click left margin to set a breakpoint) before and in the while loop and step by F10.

I am doing it.  Going step by step, trying to get down to the source of  errors...
0
SmanyxAuthor Commented:
>>>> end = index -1;
>>That statement is dangerous when using size_t for variables 'end' and 'index' in case index==0  (what actually is a valid case).

What do you recommend to do instead?
0
Infinity08Commented:
>> while (input != "")

That comparison won't work. You'll have to either use strcmp, or simply check whether the first character of the string is '\0'.

You'll also have to do the same for the other use (ie. don't use Ctrl+Z at all).


>> What do you recommend to do instead?

Treat an empty vector, and index 0 as special cases ;) See my previous post.
0
SmanyxAuthor Commented:
>> while (input != "")
>>>That comparison won't work. You'll have to either use strcmp, or simply check whether the first character of the string is '\0'.

I will fix that in a moment. But, at present it's working but not correctly. Here is a sample output from running the program. As you can see, the output is not correct, any idea about what is going wrong?


To end, press Ctrl + Z

Please enter a name: aaa

Please enter a name: bbb

Please enter a name: ccc

Please enter a name: ddd

Please enter a name: eee

Please enter a name: ^Z



Please enter a position: 2

ccc
Please enter a position: ^Z



Enter the name to search for: ddd

 ddd found at position 2
Enter the name to search for: ddd

 ddd found at position 2
Enter the name to search for: aaa

 aaa found at position 2
Enter the name to search for: ccc

 ccc found at position 2
Enter the name to search for: kkk

 (null) was not found.
Enter the name to search for: bbb

 bbb found at position 2
Enter the name to search for: mmm

 (null) was not found.
Enter the name to search for: aaa

 aaa found at position 2
Enter the name to search for: ggg

 (null) was not found.
Enter the name to search for: eee

 eee found at position 2
Enter the name to search for:
0
Infinity08Commented:
Compare what you get returned from the function :

>>             result = vec_search_name(&vec, name);

and what you're printing :

>>                  printf("\n %s found at position %d", name, index);
0
SmanyxAuthor Commented:
>>>>Compare what you get returned from the function :
>>             result = vec_search_name(&vec, name);
and what you're printing :
>>                  printf("\n %s found at position %d", name, index);

Thanks. I've fixed that up. It's fine now.
0
SmanyxAuthor Commented:
>>>>>What if I give you a set of function signatures, that you can then try to implement one by one ?

             NameVector* vec_create();                                                /* creates an empty vector */
             void vec_destroy(NameVector* vec);                                 /* destroys a vector (frees memory etc.) */
             void vec_add_name(NameVector* vec, char name[25]);    /* add a name to the vector */

             Once these three are implemented and working, you can write a main that does something    useful with them

Which other functions can I try to implement now?
0
itsmeandnobodyelseCommented:
>>>>> That's not true. Using an int instead of size_t would have the same problem you're referring to - only at the other end of the scale

???? Sorry Infinity, you know that is not the same quality. Who ever had problems at the 2 GB boundary when implementing a container for an assignment. There is no compiler on the world (today)  which would allow to allocate contiguous memory of 2GB or more. So the 'other end' is much far away while the zero end *is* an issue.

 
>> What do you recommend to do instead?

There are only two valid approaches:

(1) You were using int for the indexes and the binary search and at begin and return you cast to size_t.

(2) You do not subtract from size_t variable and never compare size_t variables with <, >, <= or >=


   

(1)

size_t vec_search_name(NameVector* vec, Name name)
{
   int index;
   int begin = 0;
   int end   = ((int)vec->size) - 1;
   int compare = 0;
    while (end >= begin)
    {
       index = (end + begin) / 2;
       compare = strcmp(name, vec->data[index]) ;
       if (compare == 0)
           return (size_t)index;
       else if (compare < 0)
           end = index -1;
       else
           begin = index + 1;
    }
    return NAME_NOT_FOUND;
}


(2)

size_t vec_search_name(NameVector* vec, Name name)
{
   size_t index;
   size_t begin = 0;
   // end is incremented by 1 and is *NOT* a valid index bot out-of-bounds initially
   size_t end  = vec->size;
   int compare = 0;   // note the result from strcmp is an int
   // now we can compare with != and are safe
   while (end != begin)
   {
       // end is at least 1 greater than begin 
       // hence the middle is less than end and 
       // therefore a valid index 
       index = (end + begin) / 2;
       compare = strcmp(name, vec->data[index]) ;
       if (compare == 0)
           return (size_t)index;
       else if (compare < 0)
           end = index;   // !!!!
       else
           begin = index + 1;
    }
    return NAME_NOT_FOUND;
}

Open in new window

0
Infinity08Commented:
>> (1) You were using int for the indexes and the binary search and at begin and return you cast to size_t.

There's no point in using size_t, if you'll use int for intermediate results/values. It defeats the whole point.


>> (2) You do not subtract from size_t variable and never compare size_t variables with <, >, <= or >=

There's no need to be so rash ... A size_t is just an unsigned integer type like any other. This implies the same caveats as any other unsigned integer type, but it does not imply as many restrictions as you suggest.

Either way, I don't see why we're having this discussion anyway. As you clearly showed in your two code samples, neither code is more complicated than the other, so why would you prefer ints ? There's no advantage - only disadvantages.
0
itsmeandnobodyelseCommented:
>>>> neither code is more complicated than the other

??? don't you see all the hurdles I had to take for the second solution? Why not simply admit that the unsigned integers have a big big problem at the 0 which signed integers don't have ?

>>>> There's no point in using size_t, if you'll use int for intermediate results/values. It defeats the whole point.

What point? It is simpler. It is safer. It is how you would/should do it. You know that in math the N0 set (all positive integers and the 0) play no role at all because of the short-comings this set has.  Same applies with using unsigned integers for numbers where you actually want to use the full set of N (all integers).  

size_t for sizes makes some sense. A size is never negative. A size_t for an index is different. If the size of the container is 0 what will you set the initial size? How will you indicate that there is no matching index? Nearly all containers of this world will return -1 for an index out-of-bounds. But because of the unsigned property of size_t they cannot name it -1 but use some artificial constant which is nothing else but -1. The only reason why indexes for standard containers mostly were of type size_t is that (silly) compiler warning when comparing unsigned integers with signed integers.

>>>> There's no need to be so rash ...
No? Isn't it true that for any C++ iterator you must not compare with <, >, <, >= but only with == or != ? Isn't it true that the while (end >= begin)  in the above code would fail when searching for a name  which is less than all the names stored in the container? Isn't it true that the index-1 turns to a huge number for index==0 ?

Smanyx, I am sorry for those differences between us experts and I really don't want to force you on my side. But if you decide to using size_t rather than int in the interface (what I fully support) you always must be aware that there is a problem when you were near zero with these size_t variables. Cause the next decrement operation would blow up the unsigned integer to a huge integer.
0
itsmeandnobodyelseCommented:
>>>> There's no point in using size_t, if you'll use int for intermediate results/values.

The interface of a function is one thing. The internal implementation is an other. A linked list would use pointers but would not have (necessarily) pointers in the interface. A string class may have an internal char pointer which was not revealed in the interface. Same is here. The NameVector uses a Name* as member but has only Name type in the interface. So, if the interface uses size_t and the internal implementation uses int, there is nothing wrong with that. Actually it is normal.
0
SmanyxAuthor Commented:
>>>Smanyx, I am sorry for those differences between us experts and I really don't want to force you on my side.

Don't you worry. I am enjoying your discussions as they are constructive. I have to admit that I do not get everything out of them right now but I know that further down the road, once we finish implementing the task at hand, I will be coming back and trying out for myself, reading thouroughly your comments and reading some more about the subject and learning, comparing, understanding. Eventually, asking even more questions!!!
Only then, all your discussions will really sink in. It's beneficial for me, definitely.

At the moment, may I suggest we carry on with using size_t as that what I have used mostly. I will need to personaly try out later using int instead and see. I had not used size_t before so I am learning...
This way we can move on and hopefully implement this NameVector.
Thanks to you both.
0
Infinity08Commented:
>> At the moment, may I suggest we carry on with using size_t as that what I have used mostly.

>> This way we can move on and hopefully implement this NameVector.

Let's do that :)

So :

>> Which other functions can I try to implement now?

We currently have the main functionality needed to be able to do something useful.

Right now, I would recommend placing all of the NameVector functionality into a separate .c and .h file, so it can be treated as a separate module (that can be easily plugged into any application that needs a name vector).

Do you have any experience with this ?
0
itsmeandnobodyelseCommented:
>>> Let's do that :)

Yes ;-)

>> Which other functions can I try to implement now?

First, take the second variant of vec_search_name I posted above (or apply the changes I made regarding 'end' and while condition (begin != end)  to your code).

BTW, your search function requires a sorted array. So you either have an additional member of struct NameVector - say 'is_sorted' - which tells whether the array was sorted and dependent on that uses a linear search or a binary search - OR - you always make sure the array is sorted by inserting each new name in sorted way.

Then you could implement the

  vec_get_size         // simply returns the current number of elements
  vec_swap              // swap two array names from positions i and j
  vec_sort                // sort array (only if you don't sort at insert)
  vec_delete_name  // delete a name from array and compress the array
  vec_resize             // add empty slots at end of array or shrink array to new size



0
Infinity08Commented:
A vector is not something that is usually kept sorted (it's too much overhead to do so). A vector is simply an dynamic array. If you need a data structure that is sorted, you're better off with a tree structure, or a hash table, or something similar. I wouldn't bother with any functions that are related to sorting the array.
0
SmanyxAuthor Commented:
>>If you need a data structure that is sorted, you're better off with a tree structure, or a hash table, or something similar. I wouldn't bother with any functions that are related to sorting the array.

But for the  vec_search_name() to work, the names in the array need to be sorted. So far, I have been careful to just input names in alphabetical order for testing the function. That wouldn't be the case when the program will be used. What if names are entered in random order?
0
Infinity08Commented:
>> But for the  vec_search_name() to work, the names in the array need to be sorted.

Which would be one of those functions I wouldn't implement for a vector ;)
0
itsmeandnobodyelseCommented:
>>>> That wouldn't be the case when the program will be used. What if names are entered in random order?

In the vec_add_name you would always make sure that the names are sorted. That means you wouldn't put a given name to the next slot but doing a binary search before (same as you did in vec_search_name) to find the index where the new name would be inserted. After that you would shift the entries at that position right to make space for the new name. You could do the shift with a loop starting from the index position found

    // make a loop from right to left and copy the names
    for (i = vec->size; i != index; --i)
          strcpy(vec->data[i], vec->data[i-1]);

Alternatively you could use memmove which - contrary to memcpy - could make copies within a contiguous piece of memory (what is the vec array with names).

      if (index != vec->size)   // if we somewhere in the middle
          memmove(&vec->data[index+1],  &vec->data[index],  (vec->size - index)*sizeof(Name));

>>>> A vector is not something that is usually kept sorted

If using data from a database you can make a sorted query there and automatically read data in a sorted way. Then the array field automatically could be built as a sorted array which indeed some advantages.  I was often using sorted arrays and binary search algorithms on them, e. g. recently when I had to calculate differences in working-days where the holidays had to be considered as well. For that I added all working-days of the time-period in question to an array (in ascending order). For calculating the difference in days I searched the indexes of both dates in my array and the difference of the positions was the number of working-days between the dates. Sorted arrays are quite more handy than unsorted ones and in many cases it is worth the overhead.





0
SmanyxAuthor Commented:
Sorry guys, I have been very unwell for the past couple of days. I am feeling a bit better now so... back to programming.

>>>In the vec_add_name you would always make sure that the names are sorted.

I have tried to make the changes to implement that but I am not sure since the program does not compile at this time.

I also have the vec_delete_name() function.

I am getting these two error messages and I don't understand them.

main.cpp(139) : error C2664: 'vec_search_name' : cannot convert parameter 1 from 'NameVector **__w64 ' to 'NameVector *'

main.cpp(213) : error C2664: 'vec_get_size' : cannot convert parameter 1 from 'NameVector **__w64 ' to 'NameVector *'

Please find enclose the full code as it stands now. Thanks.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5
#define NAME_NOT_FOUND -1
#define INVALID_INDEX -1


typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);
size_t vec_get_size(NameVector* vec);
void vec_delete_name(NameVector* vec, Name name);
void vec_sort_names(NameVector* vec);


int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;
	int result;
	int siz;
	char answer;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");

	//ADD NAME TO THE NAME VECTOR
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}

	//GET NAME AT A SPECIFIED POSITION
	printf("\n\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		//printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}

	//GET THE SIZE OF THE NAME VECTOR
	siz = vec_get_size(&vec);
	printf("\nThe size of the array is: %d", siz);

	//PROCESS A NAME SEARCH
	printf("\n\n\nEnter the name to search for: ");
	gets(input);
	while (input[0] != '\0')
	{
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		result = vec_search_name(&vec, name);
		if (result != -1)
		{
			printf("\n %s found at position %d", name, result);
		}
		else
		{
			printf("\n %s was not found.", name);
		}
		printf("\nEnter the name to search for: ");
		gets(input);
	}

	//DELETE NAME FROM THE VECTOR
	puts("Do you want to delete a name, Y - N ?");
	scanf("%c",answer);
	while (answer != 'N')
	{
		printf("\nEnter name you want to delete: ");
		gets(input);
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';

		vec_delete_name(&vec, name);

		puts("Do you want to delete a name, Y - N ?");
		scanf("%c",answer);
	}

	vec_destroy(&vec);

	puts("\n");
	system("pause");
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	size_t found, i;
	size_t index = 0;

	//check that there is enough room to enter a new name
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	//search for the name in the vector
	found = vec_search_name(&vec, name);
	if (found >= 0)
	{
		printf("\nExisting record");
	}
	else
	{
		//find the right spot the insert the name
		while ((strcmp(name, vec->data[index])) > 0)
		{
			index += 1;
		}
		strncpy(vec->data[index], name, 24);
		vec->data[index][24] = '\0';
		vec->size += 1;

		//reorganise data after the entry
		for (i = vec->size; i != index; --i)
		{
			strcpy(vec->data[i], vec->data[i-1]);
		}
	}
	
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	if (index >= vec->size)
	{
		printf("Invalid index entered.");
		return INVALID_INDEX;
	}
	strcpy(name, vec->data[index]);
	printf("\n%s", name);

	return 0;
}


size_t vec_search_name(NameVector* vec, Name name)
{
   size_t index;
   size_t begin = 0;
   // end is incremented by 1 and is *NOT* a valid index bot out-of-bounds initially
   size_t end  = vec->size;
   int compare = 0;   // note the result from strcmp is an int
   // now we can compare with != and are safe
   while (end != begin)
   {
       // end is at least 1 greater than begin 
       // hence the middle is less than end and 
       // therefore a valid index 
       index = (end + begin) / 2;
       compare = strcmp(name, vec->data[index]) ;
       if (compare == 0)
           return (size_t)index;
       else if (compare < 0)
           end = index;   // !!!!
       else
           begin = index + 1;
    }
    return NAME_NOT_FOUND;

}

size_t vec_get_size(NameVector* vec)
{

	return vec->size;
}
void vec_delete_name(NameVector* vec, Name name)
{
	size_t x, z, i; //loop indexes

	x = vec_get_size(&vec);

		for (i = 0; i <= x; i++)
		{
			if ((strcmp(vec->data[i], name)) == 0)
			{
				//vec->data[i] = '\0';
				name = NULL;
			}
		}
		//Adjust index after name has been deleted
		for (z = i + 1; z <= x; z++)
		{
			strcpy(vec->data[z], vec->data[z-1]);
		}
}

void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
A vector is a dynamic array. Items are placed in and retrieved from an array using indexes. Keeping a vector sorted is counter-intuitive, because the order and position of the items might change at any time. This means that you don't know where an item will end up once you placed it in there - you can no longer reliably retrieve it using its index.

Seriously : I would drop the idea of keeping the vector sorted. If you want a sorted data structure, go with a tree instead. It's more logical, more efficient, and will cause less confusion.


>> main.cpp(139) : error C2664: 'vec_search_name' : cannot convert parameter 1 from 'NameVector **__w64 ' to 'NameVector *'

Have a look at the type of what you're passing as argument. If vec is a NameVector*, then &vec is a NameVector**. If you want to pass a NameVector*, you should just use vec.
0
SmanyxAuthor Commented:
>>>Keeping a vector sorted is counter-intuitive, because the order and position of the items might change at any time.

>>>We currently have the main functionality needed to be able to do something useful.

Okay. Let's forget about the sorting and stuff. I changed my code back to what it was before trying to implement the sort, delete etc...

>>>Right now, I would recommend placing all of the NameVector functionality into a separate .c and .h file, so it can be treated as a separate module (that can be easily plugged into any application that needs a name vector).
>>>Do you have any experience with this ?

No, I do not have any experience with this. I will happily be following your instructions.
Please look at my code, so we know exactly where we stand.
Thanks.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define VEC_INIT_SIZE 5
#define NAME_NOT_FOUND -1
#define INVALID_INDEX -1


typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};
//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);
size_t vec_get_size(NameVector* vec);
//void vec_delete_name(NameVector* vec, Name name, int siz);


int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;
	int result;
	int siz;
	int found;
	char answer;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	printf("\n\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		//printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}
	siz = vec_get_size(&vec);
	printf("\nThe size of the array is: %d", siz);
	
	printf("\n\n\nEnter the name to search for: ");
	gets(input);
	while (input[0] != '\0')
	{
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		result = vec_search_name(&vec, name);
		if (result != -1)
		{
			printf("\n %s found at position %d", name, result);
		}
		else
		{
			printf("\n %s was not found.", name);
		}
		printf("\nEnter the name to search for: ");
		gets(input);
	}

	vec_destroy(&vec);

	puts("\n");
	system("pause");
	return 0;
}

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	if (index >= vec->size)
	{
		printf("Invalid index entered.");
		return INVALID_INDEX;
	}
	strcpy(name, vec->data[index]);
	printf("\n%s", name);

	return 0;
}


size_t vec_search_name(NameVector* vec, Name name)
{
   size_t index;
   size_t begin = 0;
   // end is incremented by 1 and is *NOT* a valid index bot out-of-bounds initially
   size_t end  = vec->size;
   int compare = 0;   // note the result from strcmp is an int
   // now we can compare with != and are safe
   while (end != begin)
   {
       // end is at least 1 greater than begin 
       // hence the middle is less than end and 
       // therefore a valid index 
       index = (end + begin) / 2;
       compare = strcmp(name, vec->data[index]) ;
       if (compare == 0)
           return (size_t)index;
       else if (compare < 0)
           end = index;   // !!!!
       else
           begin = index + 1;
    }
    return NAME_NOT_FOUND;

}

size_t vec_get_size(NameVector* vec)
{

	return vec->size;
}


void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}

Open in new window

0
Infinity08Commented:
>> No, I do not have any experience with this. I will happily be following your instructions.

The idea is to create two new files in your project. One called name_vector.h, and one called name_vector.c. In the .h file, you place the NameVector type definition, and the vector specific function prototypes (don't forget to add the include guards). In the .c file, you place all the vector specific function implementations (don't forget to include name_vector.h at the top).

Your main.c file then consists only of the main function, and an include for the name_vector.h file.
0
itsmeandnobodyelseCommented:
>>>> Seriously : I would drop the idea of keeping the vector sorted.
Infinity, you may think very little of my experiences, but I did very much with sorted arrays and can tell you that none of the arguments you brought up IMO has a practical relevance. When using a sorted-array you don't expect an item keeping its index as long as the array is growing. The idea of a sorted vector is to have a container which initially was filled in a sorted manner and then only serves for retrieval purposes. But even if it grows later, there is no need to store/use indexes longer than for one call. Also a sorted array has advantages for output purposes.

Note, there were C++ array containers before STL and all of them I used (or made myself) had a derived class SortedArray which exactly did that what Smanyx now tried with the NameVector.

>>>> go with a tree instead
A sorted vector actually is a binary tree though with much less overhead as it needs no pointers.

0
SmanyxAuthor Commented:
I think I tried to implement what you said but I am getting a incredible number of error messages.
I am certainly misrepresenting what you said or maybe I am missing something...

Here are the three files I 've got:

/*name_vector.c*/

#include "name_vector.h"

void vec_create(NameVector* vec)
{
	vec->allocated_size = VEC_INIT_SIZE;
	vec->size = 0;
	vec->data = (Name*)malloc(vec->allocated_size * sizeof(Name));
	
}

void vec_add_name(NameVector* vec, Name name)
{
	if ((vec->size) == (vec->allocated_size))
	{
		Name* tmp = (Name* )realloc(vec->data, (vec->allocated_size + VEC_INIT_SIZE) * sizeof(Name));
		vec->allocated_size += VEC_INIT_SIZE;
		if (!tmp)
		{
			exit(1);
		}
		vec->data = tmp;
	}
	strncpy(vec->data[vec->size], name, 24);
	vec->data[vec->size][24] = '\0';
	vec->size += 1;
}

int vec_get_name(NameVector* vec, size_t index, Name name)
{
	if (index >= vec->size)
	{
		printf("Invalid index entered.");
		return INVALID_INDEX;
	}
	strcpy(name, vec->data[index]);
	printf("\n%s", name);

	return 0;
}


size_t vec_search_name(NameVector* vec, Name name)
{
   size_t index;
   size_t begin = 0;
   // end is incremented by 1 and is *NOT* a valid index bot out-of-bounds initially
   size_t end  = vec->size;
   int compare = 0;   // note the result from strcmp is an int
   // now we can compare with != and are safe
   while (end != begin)
   {
       // end is at least 1 greater than begin 
       // hence the middle is less than end and 
       // therefore a valid index 
       index = (end + begin) / 2;
       compare = strcmp(name, vec->data[index]) ;
       if (compare == 0)
           return (size_t)index;
       else if (compare < 0)
           end = index;   // !!!!
       else
           begin = index + 1;
    }
    return NAME_NOT_FOUND;

}

size_t vec_get_size(NameVector* vec)
{

	return vec->size;
}


void vec_destroy(NameVector* vec)
{
	vec->allocated_size = 0;
	vec->size = 0;
	free(vec->data);
	vec->data = NULL;
	
}


/*name_vec.h*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VEC_INIT_SIZE 5
#define NAME_NOT_FOUND -1
#define INVALID_INDEX -1

typedef char Name[25];

struct NameVector
{
	Name* data;
	size_t allocated_size;
	size_t size;
};

//FUNCTION PROTOTYPES
void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);
size_t vec_get_size(NameVector* vec);


/*main.c*/

#include "name_vector.h"

typedef char Name[25];

int main(void)
{
	NameVector vec;
	Name name = "";
	char input[128]={'\0'};
	int index;
	int result;
	int siz;
	int found;
	char answer;

	vec_create(&vec);
	puts("To end, press Ctrl + Z");
	printf("\nPlease enter a name: ");
	gets(input);
	while (!feof(stdin))
	{
		
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		vec_add_name(&vec, name);

		printf("\nPlease enter a name: ");
		gets(input);
	}
	printf("\n\n\nPlease enter a position: ");
	scanf("%d", &index);
	while (!feof(stdin))
	{
		vec_get_name(&vec, index, name);
		//printf("\n%s", name);

		printf("\nPlease enter a position: ");
		scanf("%d", &index);
	}
	siz = vec_get_size(&vec);
	printf("\nThe size of the array is: %d", siz);
	
	printf("\n\n\nEnter the name to search for: ");
	gets(input);
	while (input[0] != '\0')
	{
		strncpy(name, input, sizeof(Name));
		name[24] = '\0';
		result = vec_search_name(&vec, name);
		if (result != -1)
		{
			printf("\n %s found at position %d", name, result);
		}
		else
		{
			printf("\n %s was not found.", name);
		}
		printf("\nEnter the name to search for: ");
		gets(input);
	}

	vec_destroy(&vec);

	puts("\n");
	system("pause");
	return 0;
}

Open in new window

0
Infinity08Commented:
>> I am certainly misrepresenting what you said or maybe I am missing something...

It looks quite good. There are just a few things that are off :

(a) you should really add include guards in the header file, to avoid multiple inclusion. They look like this .

        #ifndef YOUR_HEADER_FILE_H
        #define YOUR_HEADER_FILE_H

        /* contents of the header file */

        #endif /* YOUR_HEADER_FILE_H */


(b) you still have the typedef for Name in the main .c file. Since it's already in the name_vector.h file, it should not be there.


After fixing this, could you show the errors you are getting here ? You did build both .c files, didn't you ?
0
SmanyxAuthor Commented:
This is what my name_vector.h file looks like now:
/*name_vec.h*/

#ifndef NAME_VECTOR_H
#define NAME_VECTOR_H

typedef char Name[25];

struct NameVector
{
      Name* data;
      size_t allocated_size;
      size_t size;
};

void vec_create(NameVector* vec);
void vec_destroy(NameVector* vec);
void vec_add_name(NameVector* vec, Name name);
int vec_get_name(NameVector* vec, size_t index, Name name);
size_t vec_search_name(NameVector* vec, Name name);
size_t vec_get_size(NameVector* vec);

#endif /* YOUR_HEADER_FILE_H */


I have added #include <stdio.h> in the main.c file just after #include "name_vector.h". Not having it adds one more error.

The other errors are:

1>------ Build started: Project: ImplementNameVector7, Configuration: Debug Win32 ------
1>Compiling...
1>name_vector.c
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : warning C4142: benign redefinition of type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2370: 'size_t' : redefinition; different storage class
1>        c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c : see declaration of 'size_t'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2146: syntax error : missing ';' before identifier 'index'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2059: syntax error : 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(12) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(12) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(12) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(13) : error C2054: expected '(' to follow 'vec'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(20) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(20) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(20) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(20) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(20) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(21) : error C2054: expected '(' to follow 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : warning C4142: benign redefinition of type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2370: 'size_t' : redefinition; different storage class
1>        c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c : see declaration of 'size_t'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2146: syntax error : missing ';' before identifier 'index'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2059: syntax error : 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(37) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(51) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(51) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(51) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(51) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(51) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(52) : error C2054: expected '(' to follow 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(77) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(77) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(77) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(78) : error C2054: expected '(' to follow 'vec'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(84) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(84) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(84) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.c(85) : error C2054: expected '(' to follow 'vec'
1>main.c
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(15) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(16) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(17) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : warning C4142: benign redefinition of type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2370: 'size_t' : redefinition; different storage class
1>        c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c : see declaration of 'size_t'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2146: syntax error : missing ';' before identifier 'index'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2059: syntax error : 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(18) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2040: 'Name' : 'int' differs in levels of indirection from 'char [25]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(19) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2143: syntax error : missing ')' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2143: syntax error : missing '{' before '*'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(20) : error C2059: syntax error : ')'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(7) : error C2065: 'NameVector' : undeclared identifier
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(7) : error C2146: syntax error : missing ';' before identifier 'vec'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(8) : error C2275: 'Name' : illegal use of this type as an expression
1>        c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\name_vector.h(6) : see declaration of 'Name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(8) : error C2146: syntax error : missing ';' before identifier 'name'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(8) : warning C4047: '=' : 'int' differs in levels of indirection from 'char [1]'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(9) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(10) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(11) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(12) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(13) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(14) : error C2143: syntax error : missing ';' before 'type'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(16) : warning C4013: 'vec_create' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(19) : error C2065: 'input' : undeclared identifier
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(19) : warning C4047: 'function' : 'char *' differs in levels of indirection from 'int'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(19) : warning C4024: 'gets' : different types for formal and actual parameter 1
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(23) : warning C4013: 'strncpy' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(24) : error C2109: subscript requires array or pointer type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(25) : warning C4013: 'vec_add_name' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(28) : warning C4047: 'function' : 'char *' differs in levels of indirection from 'int'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(28) : warning C4024: 'gets' : different types for formal and actual parameter 1
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(34) : warning C4013: 'vec_get_name' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(39) : error C2065: 'siz' : undeclared identifier
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(39) : warning C4013: 'vec_get_size' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(43) : warning C4047: 'function' : 'char *' differs in levels of indirection from 'int'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(43) : warning C4024: 'gets' : different types for formal and actual parameter 1
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(44) : error C2109: subscript requires array or pointer type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(47) : error C2109: subscript requires array or pointer type
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(48) : error C2065: 'result' : undeclared identifier
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(48) : warning C4013: 'vec_search_name' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(58) : warning C4047: 'function' : 'char *' differs in levels of indirection from 'int'
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(58) : warning C4024: 'gets' : different types for formal and actual parameter 1
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(61) : warning C4013: 'vec_destroy' undefined; assuming extern returning int
1>c:\documents and settings\user1\my documents\visual studio 2005\projects\implementnamevector7\implementnamevector7\main.c(64) : warning C4013: 'system' undefined; assuming extern returning int
1>Generating Code...
1>Build log was saved at "file://c:\Documents and Settings\user1\My Documents\Visual Studio 2005\Projects\ImplementNameVector7\ImplementNameVector7\Debug\BuildLog.htm"
1>ImplementNameVector7 - 96 error(s), 20 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
0
Infinity08Commented:
You're missing the typedef for the NameVector type :
typedef struct NameVector
{
      Name* data;
      size_t allocated_size;
      size_t size;
} NameVector;

Open in new window

0
evilrixSenior Software Engineer (Avast)Commented:
I'm not going to join the debate over whether to sort or not to sort but...

>> A sorted vector actually is a binary tree though with much less overhead as it needs no pointers.
Um, no it isn't.

It is true the vector is more efficient in terms of storage; however, this is largely offset by the time complexities you'll encounter when trying to emulate a binary tree using it.

The insert complexity for a binary tree is O(log N).

The insert complexity for a vector (assuming you want to insert into it to keep it sorted) is O(N [+ A] log M), where N is how many items will be displaced, M is the number of searches required to locate the upper or lower bound and A is the number of items affected in the case that the vectors buffer need to be reallocated.

You can read up more about container time complexities here: http:/A_2812.html
0
SmanyxAuthor Commented:
>>>You're missing the typedef for the NameVector type :
I have fixed it. It's working fine. So, what to do next ?
0
Infinity08Commented:
So, now you have a separate module for the NameVector type. This can be used anywhere, by just including the header file.

You have a basic name vector type now. Make sure that the current functionality is working fine. When you encounter some new features that you'd like to add, you can do so. But for now, I think you have a good basic set of operations.
0
SmanyxAuthor Commented:
>>>You have a basic name vector type now. Make sure that the current functionality is working fine.

That is where the problem resides now. If you take a look of a sample run of the program, the output is obviously erroneous.

/* SAMPLE PROGRAM OUTPUT:
   ========================
To end, press Ctrl + Z

Please enter a name: ccc

Please enter a name: ttt

Please enter a name: www

Please enter a name: aaa

Please enter a name: ccc

Please enter a name: mmm

Please enter a name: kkk

Please enter a name: ^Z



Please enter a position: 3

aaa
Please enter a position: ^Z

The size of the array is: 7


Enter the name to search for: ccc

 ccc found at position 4
Enter the name to search for: kkk

 kkk was not found.
Enter the name to search for: www

 www was not found.
Enter the name to search for:


Press any key to continue . . .

*/
0
Infinity08Commented:
That seems to be related to your search function, which assumes that the vector is sorted.

If you want a search function for an unsorted vector, you'll need to check all items in the vector, one by one.
0
SmanyxAuthor Commented:
>>>If you want a search function for an unsorted vector, you'll need to check all items in the vector, one by one.

How do you do it? Is it a practical thing to do?
0
Infinity08Commented:
Simply have a loop that iterates over all items in the array. It's very simple to implement.
0
itsmeandnobodyelseCommented:
>> A sorted vector actually is a binary tree though with much less overhead as it needs no pointers.
>>>> Um, no it isn't.

It wasn't a technical or C assertment but a logical one. The root of the "tree" is the middle of the array. Then you have two branches left and right of the middle. Take the middle of the left branch ... and so on. A sorted array can be searched and displayed as binary tree with no efforts and with the same (or better) speed.

Insert complexity has nothing todo with tree property. As told sorted arrays are used normally for one-time filling, e. g. to take master data from a database table. If the input data were already sorted the insert complexitity turns to 0. If the data were inserted by dialog input (as it was here) the insert complexity is negligible as well. So a sorted array is well suited for the current task (not for all, of course). Note, I didn't recommend to use sorted arrays here. The idea of using a binary search on the array came from Smanyx and my input was that the array must be sorted to do so.

My only concern is to object against the the general assertment that sorting a dynamic array (or keep a dynamic array sorted all the time) is a non-recommendable idea.

A quite different question is whether we really need a sorted vector here. Dispassionately I would say it is "nice to have" (and a good practice).

0
itsmeandnobodyelseCommented:
>>>> How do you do it? Is it a practical thing to do?
>>>> Simply have a loop that iterates over all items in the array. It's very simple to implement.

Take a for loop

   size_t index;
   ...
   for (index = 0; index != vec->size; ++index)

In the loop body compare each name (using strcmp) same as you did in the binary loop. And return the index if you found it.  After the loop return 'not found'.
0
SmanyxAuthor Commented:
A lot has been said in dealing with this question. From my original post, where I said:
>>>As suggested by Infinity08, I am trying to write separate functions that will use the NameVector struct to add, remove, sort, search names etc...
At this stage, I am trying to get the last written program (refer to last post) into the AddName() function. >>>One function at the time!
 
I think we have gone beyond the problem presented.

>>>So, now you have a separate module for the NameVector type. This can be used anywhere, by just including the header file.
>>>You have a basic name vector type now. Make sure that the current functionality is working fine. When you encounter some new features that you'd like to add, you can do so. But for now, I think you have a good basic set of operations.

Yes, I do. And I have also learnt a lot. I can add other features to the vector when the need rises..
I think I need to close the question here. Other questions will always follow...

>>>The idea of using a binary search on the array came from Smanyx and my input was that the array must be sorted to do so.

Yeah, I will try on my own with different search algorithms as well.

I did appreciate your input guys. I tried an extensive search for course materials, tutorials, books dealing with data structures in C especially but i can't get any thing that talks about vectors in C.
Most of what I find deals with C++. , vectors in C++, the STL etc...
In C, most books talk about linked lists, BST, stacks, deque, queues, trees, but no vectors...
Could you please recommend some links, books or any things that focuses on this subject in C, not C++?

0
SmanyxAuthor Commented:
Once again, thank you so much !!!
0
itsmeandnobodyelseCommented:
>>>> In C, most books talk about linked lists, BST, stacks, deque, queues, trees, but no vectors...
The name 'vector' you mostly did find with C++ because of STL std::vector. In C the terminus "dynamic array" would be more common. However, because a 'dynamic array' in C easily could be implemented by reallocating a pointer passing a bigger size, there is no (real) need as with linked list, BST, tree, ... to add much functions which help you manage the array but you could do it from scratch every time using a pointer variable and a size variable. Note, that doesn't mean that what you made above is not senseful. On the contrary, encapsulating a container into a new type with associated functions adds some kind of Object-Oriented-Programming (OOP) to C, where the container (object) got the main focus and not the functioniality operating on the container (which turns to 'properties' of the container). Such coding generally leads to a better design as it makes the code less error-prone and better readable. I think all good C programs would follow such kind of paradigm therefore.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.