Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > sorting the input

Reply
Thread Tools

sorting the input

 
 
arnuld
Guest
Posts: n/a
 
      04-23-2008
> On Tue, 22 Apr 2008 14:18:26 +0100, Ben Bacarisse wrote:


> In total your program had an array of 100 char pointers. One array of
> 100 characters (the "global" one) and a local array of 100 characters.
> That just can't be enough "in general". Where are the characters of
> the second line stored?


:-O



> and read into that:
>
> while( fgets(one_line, sizeof one_line, stdin) )


> and do the malloc here, to save the line. At this point we know how
> long it is (if we use strlen(one_line)) and we call allocate a copy
> the line.



you meant this ?


int readlines( char* arr_of_ptr[], const int max )
{
int num_lines, size_arr;
char *p;
char temp_arr[STR_SIZE];

num_lines = 0;

while( fgets(temp_arr, max, stdin) && num_lines < max )
{
size_arr = strlen( temp_arr );
if( (p = malloc( size_arr * sizeof( char* ))) )
{
strcpy( p, temp_arr );
*arr_of_ptr++ = p;
++num_lines;
}

}

return num_lines;
}


> and we'd store the pointer in arr_or_ptr[num_lines] (I prefer that
> style to your *arr_of_ptr++ = ... one).



That's the style I want to use but I don't use it as that lies to me
about the very basic fact of C. At some point I will also stop using []
notation in function arguments as it fakes the array, it lies that it is
not a pointer, that it is a box of characters we call array and we are
using it directly but we are not, in fact, it is a pointer that is
manipulating the array and hence this distinction is the source of most
troubles I have and this trouble is intensively painful than the troubles
I get by not using array indexing.





--
http://lispmachine.wordpress.com/
my email ID is at the above address

 
Reply With Quote
 
 
 
 
arnuld
Guest
Posts: n/a
 
      04-23-2008
> On Tue, 22 Apr 2008 15:50:11 +0100, Ben Bacarisse wrote:

>> arnuld <(E-Mail Removed)> writes:
>> while( fgets(temp_arr, max, stdin) && num_lines < max )
>> {
>> size_arr = strlen( temp_arr );
>> if( (p = malloc( size_arr * sizeof( char* ))) )


> You need size_arr + 1. You are storing chars, not char *s.



and what I am supposed to do with last element ?

I think NULL should be the last element but I can't find a way
to add it.


> Sorry, I can't follow that. It was a matter of style not correctness,
> so I am not sure it is worth pursuing.


okay


--
http://lispmachine.wordpress.com/
my email ID is at the above address

 
Reply With Quote
 
 
 
 
arnuld
Guest
Posts: n/a
 
      04-23-2008
> On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:



> I would not link these two sizes. You need two enum constants.


it is done.


> The second parameter has a bad name. At best it is one line.


sorry, my mistake



> I'd stick with reading the lines in first. Deal with sorting later.



okay, I am done with reading and printing lines now. It is working now, I
need to understand the sorting part now:


/* write a program to read a set of lines from input and sort them
* and then print them.
*
* version 1.0
*/


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

enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };

char* arr_of_ptr[ARR_SIZE];
char arr_of_char[STR_SIZE];

int readlines( char**, const int );
void printlines( char** );


/* main() will simply call the other functions to do the job */

int main( void )
{
if( readlines( arr_of_ptr, ARR_SIZE ) > 0 )
{
/* qsort( arr_of_ptr, ARR_SIZE, sizeof( char* )); */
printlines( arr_of_ptr );
}
else
{
fprintf( stderr, "error: out of memory\n" );
}

return 0;
}


/* 1) read lines till we get the NULL,
* 2) store those lines into an array of characters <arr_of_lines>,
* 3) pointer of arry of pointers <arr_of_ptr> will point to the
* individual elements of array of characters <arr_of_lines>,
*
*/

int readlines( char* arr_of_ptr[], const int max )
{
char *p, **p_arrptr;
int num_lines, size_arr;
char temp_arr[STR_SIZE];

num_lines = 0;
p_arrptr = arr_of_ptr;

while( fgets(temp_arr, max, stdin) && num_lines < max )
{
size_arr = strlen( temp_arr ) + 1;
if( (p = malloc( size_arr * sizeof( char ))) )
{
strcpy( p, temp_arr );
*p_arrptr++ = p;
++num_lines;
}

}

return num_lines;
}




/* it will simply print the lines pointed to by the elements of
* arrays of pointers <arr_of_ptr>.
*
*/
void printlines( char* arr_of_ptr[] )
{
printf("\n-------------------------\n");
while( *arr_of_ptr )
{
printf("%s", *arr_of_ptr++ );
}
}

============= OUTPUT ===================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra 5-7.c
/home/arnuld/programs/C $ ./a.out
Ben & Richard
both are helping
C newbie.... arnuld

-------------------------
Ben & Richard
both are helping
C newbie.... arnuld
/home/arnuld/programs/C $







--
http://lispmachine.wordpress.com/
my email ID is at the above address

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      04-23-2008
arnuld <(E-Mail Removed)> writes:

> On Tue, 22 Apr 2008 13:05:13 +0100, Ben Bacarisse wrote:
>> I'd stick with reading the lines in first. Deal with sorting later.

>
> okay, I am done with reading and printing lines now. It is working
> now,


Sorry, not quite.

> I need to understand the sorting part now:


I think you need to show your best attempt at the sort call and people
will help you get the details right.

> /* write a program to read a set of lines from input and sort them
> * and then print them.
> *
> * version 1.0
> */


> enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };
>
> char* arr_of_ptr[ARR_SIZE];
> char arr_of_char[STR_SIZE];


This second array seem not to be used now (that is as I would expect)
so you should get rid of it.

> if( readlines( arr_of_ptr, ARR_SIZE ) > 0 )


> int readlines( char* arr_of_ptr[], const int max )
> {
> char *p, **p_arrptr;
> int num_lines, size_arr;
> char temp_arr[STR_SIZE];
>
> num_lines = 0;
> p_arrptr = arr_of_ptr;
>
> while( fgets(temp_arr, max, stdin) && num_lines < max )

^^^?

Safe (because max happens to be less that STR_SIZE) but not correct.

> {
> size_arr = strlen( temp_arr ) + 1;
> if( (p = malloc( size_arr * sizeof( char ))) )


You can omit sizeof(char). It is 1 by definition. I can see why some
people might want a size there, but if you are one of them then you
should use the c.l.c-approved idiom:

if( (p = malloc(size_arr * sizeof *p)) )

> {
> strcpy( p, temp_arr );
> *p_arrptr++ = p;
> ++num_lines;
> }
>
> }
>
> return num_lines;
> }


--
Ben.
 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      04-24-2008
arnuld wrote:

>> On Wed, 23 Apr 2008 13:17:26 +0100, Ben Bacarisse wrote:

>
>>> arnuld wrote:
>>> size_arr = strlen( temp_arr ) + 1;
>>> if( (p = malloc( size_arr * sizeof( char ))) )

>
>> You can omit sizeof(char). It is 1 by definition. I can see why
>> some people might want a size there, but if you are one of them then
>> you should use the c.l.c-approved idiom:
>>
>> if( (p = malloc(size_arr * sizeof *p)) )

>
> where is "p" pointing to ? nowhere . so you can't dereference it yet.


That's perfectly legal. Sizeof is a compile time operator and no actual
deferencing of the pointer is done.

 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      04-24-2008
> On Wed, 23 Apr 2008 13:17:26 +0100, Ben Bacarisse wrote:

>> arnuld <(E-Mail Removed)> writes:


>> okay, I am done with reading and printing lines now. It is working
>> now,


> Sorry, not quite.


I have shown you the output and it seems ok to me. Did you find something
wrong ?



>> I need to understand the sorting part now:


> I think you need to show your best attempt at the sort call and people
> will help you get the details right.



I can't understand the 13.8 of FAQs: http://c-faq.com/lib/qsort1.html

/* compare strings via pointers */
int pstrcmp(const void *p1, const void *p2)
{
return strcmp(*(char * const *)p1, *(char * const *)p2);
}


parameters are made void* but in fact we are passing char**, which is 2 levels of
indirection. and what about the cast:

(char* const*)p1


we are casting a <pointer to void> to <pointer to a const pointer to char>
, right ?



>> char* arr_of_ptr[ARR_SIZE];
>> char arr_of_char[STR_SIZE];


> This second array seem not to be used now (that is as I would expect)
> so you should get rid of it.


okay


>> while( fgets(temp_arr, max, stdin) && num_lines < max )

> ^^^?
>
> Safe (because max happens to be less that STR_SIZE) but not correct.



incorrect ?


If the user enters the 1001 characters then program will crash or behave
strangely or something but I can't do anything here as the array-size has
to be there at compile-time. Even if I do malloc() for array then for user
input I use fgets() I will still need a limit to read the characters.




>> if( (p = malloc( size_arr * sizeof( char ))) )


> You can omit sizeof(char). It is 1 by definition.


you mean, by default, if I type: <malloc( size_arr )> then it will be
converted to <malloc(size_arr * 1)> ?




> I can see why some
> people might want a size there, but if you are one of them then you
> should use the c.l.c-approved idiom:
>
> if( (p = malloc(size_arr * sizeof *p)) )


okay




--
http://lispmachine.wordpress.com/
my email ID is at the above address

 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      04-24-2008
On Fri, 25 Apr 2008 01:58:51 +0500, arnuld <(E-Mail Removed)> wrote:

>> On Wed, 23 Apr 2008 13:17:26 +0100, Ben Bacarisse wrote:

>
>>> arnuld wrote:
>>> size_arr = strlen( temp_arr ) + 1;
>>> if( (p = malloc( size_arr * sizeof( char ))) )

>
>> You can omit sizeof(char). It is 1 by definition. I can see why some
>> people might want a size there, but if you are one of them then you
>> should use the c.l.c-approved idiom:
>>
>> if( (p = malloc(size_arr * sizeof *p)) )

>
>where is "p" pointing to ? nowhere . so you can't dereference it yet.


Since sizeof does not evaluate its operand (except for VLA), the *p
does not involve a dereference. *p simply identifies the type that
sizeof should operate on.


Remove del for email
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      04-24-2008
On Fri, 25 Apr 2008 02:04:45 +0500, arnuld <(E-Mail Removed)> wrote:

>I have tried the strcmp function from FAQ:
>
> http://c-faq.com/lib/qsort1.html
>
>it fails to do its job. It Segfaults . If I remove its call from the
>program, my program compiles and runs fine:


Is sorting important to your program or not? If not, leave it out. If
it is, then your program does not run fine without it. The output
will not be sorted.

>
>
> /* write a program to read a set of lines from input and sort them
> * and then print them.


One might infer that sorting is important.

> *
> * version 1.0
> */
>
>
>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>
>enum MAXLINES { ARR_SIZE = 100, STR_SIZE = 1000 };
>
>char* arr_of_ptr[ARR_SIZE];
>/* char arr_of_char[STR_SIZE]; */
>
>int readlines( char**, const int );
>void printlines( char** );
>int p_strcmp( const void*, const void* );
>
>
>/* main() will simply call the other functions to do the job */
>int main( void )
>{
> if( readlines( arr_of_ptr, ARR_SIZE ) > 0 )
> {
> qsort( arr_of_ptr, ARR_SIZE, sizeof( char* ), p_strcmp );


The second argument to qsort is the number of array elements to
process. While there are ARR_SIZE elements, most of them contain NULL
and should not be processed. readlines told you how many elements to
process but you threw that information away.

> printlines( arr_of_ptr );
> }
>
>
> return 0;
>}
>
>
>/* 1) read lines till we get the NULL,
> * 2) store those lines into an array of characters <arr_of_lines>,
> * 3) pointer of arry of pointers <arr_of_ptr> will point to the
> * individual elements of array of characters <arr_of_lines>,
> *
> */
>
>int readlines( char* arr_of_ptr[], const int max )
>{
> char *p, **p_arrptr;
> int num_lines, size_arr;
> char temp_arr[STR_SIZE];
>
> num_lines = 0;
> p_arrptr = arr_of_ptr;
>
> while( fgets(temp_arr, max, stdin) && num_lines < max )


People have already told you that max is not appropriate in the call
to fgets. If you won't listen, why post?

> {
> size_arr = strlen( temp_arr ) + 1;


It is a nit but this will include the '\n' that fgets inserts for a
line shorter than the buffer. Most seem to think it is worth
eliminating.

> if( (p = malloc( size_arr * sizeof( char ))) )
> {
> strcpy( p, temp_arr );
> *p_arrptr++ = p;
> ++num_lines;
> }
>
> }
>
> return num_lines;
>}
>
>
>
>/* it will simply print the lines pointed to by the elements of
> * arrays of pointers <arr_of_ptr>.
> *
> */
>void printlines( char* arr_of_ptr[] )
>{
> printf("\n-------------------------\n");
> while( *arr_of_ptr )
> {
> printf("%s", *arr_of_ptr++ );
> }
>}
>
>
>/* compare 2 strings using pointers */
>int p_strcmp( const void* pv1, const void* pv2 )
>{
> return strcmp( *(char* const*)pv1, *(char* const*)pv2 );


When either v1 or v2 is NULL, this invoked undefined behavior. A
segfault is one of the nicer manifestations of same.

>}



Remove del for email
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      04-24-2008
arnuld wrote:
>> On Thu, 24 Apr 2008 10:20:07 +0000, Richard Heathfield wrote:

>
>
>> He isn't dereferencing it: sizeof does not evaluate its operand (except
>> for one tiny corner-case in C99 that doesn't apply here), so no
>> dereferencing is taking place.

>
> so, sizeof() operator does not evaluate its operands. It finds the number
> of bytes without evaluating anything ?
>

It is evaluating the size of a type, at compile time.

--
Ian Collins.
 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      04-24-2008
In article <(E-Mail Removed)>,
arnuld <(E-Mail Removed)> wrote:

>> He isn't dereferencing it: sizeof does not evaluate its operand (except
>> for one tiny corner-case in C99 that doesn't apply here), so no
>> dereferencing is taking place.


>so, sizeof() operator does not evaluate its operands. It finds the number
>of bytes without evaluating anything ?


In effect, it instructs the compiler to find the number of bytes
used by the argument. That depends on the *type* of the argument,
not its value. And you don't need to evaluate an expression to
determine its type: if a and b are ints, a+b is an int regardless
of the values of a and b; if x is an array of doubles, x[5] is always
a double, and so on.

The compiler does some calculations to determine the type and hence
the size, so you could say it evaluates *something*, but it doesn't
evaluate the argument itself.

-- Richard
--
:wq
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sorting list vs sorting vector boltar2003@boltar.world C++ 2 07-06-2010 09:40 AM
Sorting the Input arnuld C Programming 1 09-30-2008 07:47 AM
sorting the input arnuld C++ 16 09-25-2008 04:44 PM
fired event Sorting which wasn't handled - sorting and SelectedIndexChanged Jason ASP .Net Web Controls 0 10-04-2006 02:19 PM
sorting by multiple criterias (sub-sorting) Tom Kirchner Perl Misc 3 10-11-2003 05:16 PM



Advertisments