Thread: Please help: counting string occurances using scanf and arrays

  1. #16
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    What I was meaning: I have never liked two dimesnional arrays. Reason is propably that I've not used them much, and thus I have difficulties in pondering how the dual indexing accesses data. Thus I would perhaps have thought:

    I have word[100] array. This is 100 bytes wide chunck of memory,

    Code:
     |------------------100B-------------------|
    In other words, 
     |--20B--|--20B--|--20B--|--20B--|--20B--|
    Thus I could store 5 STRING type datas in this space.

    So I could have one STRING type variable s, which I used with scanf to obtain and store input. Then I would *copy* this data in word - array, (not store a pointer to this same variable). The correct location for first item would be position starting from

    &(word[0])

    If we look at my fancy ascii art , it is the first 20B block in reserved 100 byte space.

    Code:
     |--20B--|--20B--|--20B--|--20B--|--20B--|

    after storing the first, I would have increased char (byte) counter with
    sizeof(STRING) == 20 B

    Then I would have stored the next user input in same STRING type variable where I stored the first one. (I would have the original in safe place, copied in word array).

    I would then copy the next word in position starting from
    &(word[counter]), which is now same as &(word[sizeof(STRING)]), eg &(word[20]).

    This is naturally the second 20B block eg.

    Code:
     |--20B--|--20B--|--20B--|--20B--|--20B--|

    Then I would again increase conter with sizeof(STRING), to get the third 20B block as starting point at next loop...


    And from now on, your most important thing to avoid is writing out of the reserved space. It will result death and destruction. Unexpectedly.

    When we keep this in mind, we have 3 major things to consider.

    1, How to ensure user does not give so long word, that it would go past the reserved 20 B. (19 characters + terminating '\0')?

    2. How to ensure we won't get more words than fits into word[] array.

    1. is not that difficult. It is possible for example to change scanf() to some function, which allows us to specify the maximum amount of data it will obtain from stdin.

    2. is a bit problematic. It really is not funny to limit words user can give to , lets say 5. Or 10. Or 100 for that matters. It just feels dull. On the other hand, larger array we reserve, more memory our program uses. I've seen programs using astonishing amounts of memory for just some simple tasks... No wonder we need gigs of mem nowadays...

    I assume it is just fine for your assignment to define upperlimit for the words. you can choose 100, 200, or 2000 bytes as you wish, but you should do it. Similar to restricting the amount of characters in word.

    Anyways, another possibility would be dynamically reserving the memory when needed. You could for example initially allocate 100 bytes, and if user wants to give 6.th word, then allocate more. Or you could allocate memory for one word at a time (which is not preferred because allocations are quite heavy operations, and eat quite a many cycles of cpu time). This would soon lead you to the world of linked lists etc.

    What was my point? Good question. I originally just wanted to show you what I meant by using 1 dimensional array, and then got carried away. However, as we quickly noticed, really much of C programming is just storing and retrieving data from memory. And this is often also the most problematic part. Data structures which would be effective, fast to access, dynamic, simple to understand and easy to use are utopia

    Oh, and Hi Tater :]
    Last edited by Maz; 09-23-2011 at 02:00 AM. Reason: cleaned

  2. #17
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Maz View Post
    What I was meaning: I have never liked two dimesnional arrays. Reason is propably that I've not used them much, and thus I have difficulties in pondering how the dual indexing accesses data. Thus I would perhaps have thought:

    I have word[100] array. This is 100 bytes wide chunck of memory,
    Thus I could store 5 STRING type datas in this space.
    Well yes you can and no you can't... There's a lot of overhead in your method...
    Code:
    word[100][20]
    This gives you space for 100 strings, each of which can be 20 characters long.

    When working with strings, it behaves like a single dimensional array...
    Code:
    printf("%s", word[31]);
    is perfectly legit and will work...
    but it's far easier to use than trying to stack strings up in a unidimensional array and uses the same amount of memory.

  3. #18
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    About the only big improvement our new friend could make would be to use structs...
    Code:
    typedef struct t_WordList
      { char text[32];  
         int uses; }
      WordList, *pWordList;
    
    WordList words[100] = {0};
    Then adding new words, searching etc is done by dotted reference...
    Code:
    strcpy(words[count].text, s);
    
    words[count].uses++;
    and so on....

    The big advantage of that technique is that sorting gets easier...
    Code:
    WordList temp;
    
    temp = words[i];
    words[i] = words[j];
    words[j] = temp;
    ... letting her swap the structs and thus the text and the uses count all in one pass.
    Last edited by CommonTater; 09-23-2011 at 02:20 AM.

  4. #19
    Registered User Nancy Franklin's Avatar
    Join Date
    Sep 2011
    Posts
    15
    [QUOTE=Yep that's how the swap works... [/QUOTE]

    Would this work, or do I have it backwards?
    Code:
    STRING temp2=" ."
    
    for(i = 0; i < count; i++){
        for(j = i; j < count; j++){
             if(a[j]>a[j-1]){
    
                  temp = count[i];
                  count[i] = count[j];
                  count [j] = temp; 
     
                  temp2 = word[i]; 
                  strcpy(word[i], word[j]);
                  strcpy(word[j], temp2);
    
             } //end if 
         }
    }
    I really don't want to delve into 'structs' or memory addresses like that- the teacher would know something's up.
    Last edited by Nancy Franklin; 09-23-2011 at 02:40 AM.

  5. #20
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Quote Originally Posted by CommonTater View Post
    Well yes you can and no you can't... There's a lot of overhead in your method...
    Code:
    word[100][20]
    This gives you space for 100 strings, each of which can be 20 characters long.

    When working with strings, it behaves like a single dimensional array...
    Code:
    printf("%s", word[31]);
    is perfectly legit and will work...
    but it's far easier to use than trying to stack strings up in a unidimensional array and uses the same amount of memory.

    I guess something like this would have been my approach - basically this is based on an unidimensional array

    Code:
    #include <stdio.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef char STRING[20];
    
    typedef struct mystringstore
    {
        struct mystringstore *first;
        struct mystringstore *next;
        struct mystringstore *prev;
    	size_t free;
    	size_t space;
        char text[1];
    }mystringstore;
    
    
    mystringstore *init_sstore(size_t datasize);
    int addin_sstore(mystringstore *_this,STRING tmpstr,unsigned int tmplen);
    void destroy_sstore(mystringstore **store);
    
    int main()
    {
        int rval;
        STRING tmp;
    	mystringstore *store=init_sstore(100);
    	
    	if(NULL==store)
    	{
    		perror("sstore init failed!\n");
    		return -1;
    	}
    	for(;;)
    	{
    		unsigned int tmplen;
            printf("givemeword or quit to quit\n");
    		if(NULL==fgets(tmp,20,stdin))
    		{
    		    /* User gave EOF */
    			break;
    		}
    		tmplen=strlen(tmp);
    		if('\n' == tmp[tmplen-1])
    		{
    		    tmplen--;
    			if(tmp[tmplen-1]=='\r')
    			    tmplen--;
    		}
    		if(4==tmplen)
    		{
    			if( *((int32_t *)"quit")==*((int32_t *)tmp))
    			{
    				/* quit */
    				break;
    			}
    		}
    		if((rval=addin_sstore(store,tmp,tmplen)))
    		{
    				perror("Mysterious error\n");
    				return -1;
    		}
    	}
        return 0;
    }
    mystringstore* additem_sstore(mystringstore *_this)
    {
    	mystringstore* _new=init_sstore(_this->space);
    	if(NULL==_new)
    	{
    		printf("Failed to add new store item!\n");
    	}
    	else
    	{
    		_new->first=_this;
    		_new->prev=_this;
    		while(NULL!=_new->prev->next)
    			_new->prev=_new->prev->next;
    		_new->prev->next=_new;
    	}
    	return _new;
    }
    int addin_sstore(mystringstore *_this,STRING tmpstr,unsigned int tmplen)
    {
    	mystringstore *curr;
    	
    	if(NULL==_this)
    	{
    		printf("ASSERT: Uninitialized store? %s:%d\n", __FILE__,__LINE__);
    		return -1;
    	}
    	if(tmplen>=_this->space)
    	{
    		printf("Cannot store %u bytes, store is only %u bytes\n",tmplen,_this->space);
    		return -1;
    	}
    	curr=_this;
    	while(NULL!=curr)
    	{
    		if(curr->free>tmplen)
            {
    			break;
            }
            curr=curr->next;
    	}
    	if(NULL==curr)
    	{
    		curr=additem_sstore(_this);
    		if(NULL==curr)
    		{
    			return -1;
    		}
    	}
    	memcpy(&(curr->text[curr->space-curr->free]),tmpstr,tmplen);
    	curr->free-=(tmplen+1);
    	return 0;
    }
    mystringstore *init_sstore(size_t datasize)
    {
    	mystringstore *_this=calloc(1,sizeof(mystringstore)+datasize-1);
    	if(NULL!=_this)
    	{
    		memset(_this,0,datasize);
    	}
    	_this->space=datasize;
    	_this->free=datasize;
    	return _this;
    }
    
    void destroy_sstore(mystringstore **store)
    {
    	if(NULL!=store && NULL != *store)
    	{
    		free(*store);
    		*store=NULL;
    	}
    }

  6. #21
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Actually that's a linked list...

  7. #22
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Nancy Franklin View Post
    Would this work, or do I have it backwards?
    Code:
    STRING temp2=" ."
    
    for(i = 0; i < count; i++){
        for(j = i; j < count; j++){
             if(a[j]>a[j-1]){
    
                  temp = count[i];
                  count[i] = count[j];
                  count [j] = temp; 
     
                  temp2 = word[i]; 
                  strcpy(word[i], word[j]);
                  strcpy(word[j], temp2);
    
             } //end if 
         }
    }
    Like this...

    Code:
                 strcpy(temp2, word[i]); 
                  strcpy(word[i], word[j]);
                  strcpy(word[j], temp2);
    STRING temp2 = " ."; is an error just use STRING temp2;

    Strings ... no equals stuff...
    Last edited by CommonTater; 09-23-2011 at 04:07 AM.

  8. #23
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Quote Originally Posted by CommonTater View Post
    Actually that's a linked list...
    Yes, but still, inside each linked list we have one dimensional array. Linked list is just a construct sitting on top of that to add new arrays when old ones are filled.

    ... I guess I should ask for a bit more work ...

  9. #24
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Maz View Post
    Yes, but still, inside each linked list we have one dimensional array... ...to add new arrays when old ones are filled.
    What? You have a 1 character array, that you are using so you can get away with mallocing extra space onto the end of your structure. Why you are doing that, no one knows, when you could just be using a character pointer and allocating whatever space you wanted like a regular person. What all of that has to do with the phrase "when old ones are filled" is anyone's guess.


    Quzah.
    Hope is the first step on the road to disappointment.

  10. #25
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Quote Originally Posted by quzah View Post
    What? You have a 1 character array, that you are using so you can get away with mallocing extra space onto the end of your structure. Why you are doing that, no one knows, when you could just be using a character pointer and allocating whatever space you wanted like a regular person. What all of that has to do with the phrase "when old ones are filled" is anyone's guess.


    Quzah.
    The one character array is accesspoint to data (a placeholder), appended at the end of the struct. As you can see from init function, there will be space allocated at the end of the struct. That way we dont get scattered pieces of memory allocated. This technique *may* at some environments help us from getting cache misses.

  11. #26
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    That way we dont get scattered pieces of memory allocated.
    O_o

    Code:
    struct mystringstore *first; // pointer
    struct mystringstore *next; // pointer
    struct mystringstore *prev; // pointer
    How are you going to manage that again?

    Soma

  12. #27
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Maz View Post
    The one character array is accesspoint to data (a placeholder), appended at the end of the struct. As you can see from init function, there will be space allocated at the end of the struct. That way we dont get scattered pieces of memory allocated. This technique *may* at some environments help us from getting cache misses.
    I know why you are doing it. I just don't know WHY you are doing it. I really doubt you're gaining anything from it. I guess you have one less malloc call, for whatever that's worth.


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #28
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Allright. Yes. Naturally linked list itself gets scattered. But we do not get yet another block of memory for allocated character array.

    eg, instead of

    [list header] -> [ char array]
    |
    [list header] -> [ char array]

    we have

    [list header + char array]
    |
    [list header + char array]

    => half the pieces.

  14. #29
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If you're going to do something pointless, why don't you just malloc off a huge block of memory, and then get some points and point them at spots of it whenever you decide you have a string? It's not like it's any worse a solution than padding structures to pretend they have big arrays stuck on the end.


    Quzah.
    Hope is the first step on the road to disappointment.

  15. #30
    Registered User Maz's Avatar
    Join Date
    Nov 2005
    Location
    Finland
    Posts
    194
    Quote Originally Posted by quzah View Post
    I know why you are doing it. I just don't know WHY you are doing it. I really doubt you're gaining anything from it. I guess you have one less malloc call, for whatever that's worth.


    Quzah.
    In this example? Nothing. Absolutely nothing.

    Depending on what such a list does contain - possibly a lot. Maybe it would be a message queue? Networking protocol stack? Maybe a slab memory pool, who knows.

    [EDIT]
    Okay, slab pool is a bad idea, as this kind of a structure does not provide fast enough access to other data but queue head. A FIFO / FILO storages could be well done with this princible, right? Creating head and tail item staying same, and adding a tail pointer to point at tail would speed up things. Anyways, as Tater notes at his next post, we're being carried away :]

    Oh, and please point me the position the structure is broken? (It may well be, this is untested what comes to operation, compilation I did check).
    [/EDIT]
    Last edited by Maz; 09-23-2011 at 04:58 AM. Reason: responded to messages following this one :]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Counting Occurances of a Character
    By eeengenious in forum C Programming
    Replies: 5
    Last Post: 03-31-2011, 07:50 AM
  2. Replies: 18
    Last Post: 09-28-2010, 11:07 AM
  3. Counting String Occurances
    By Lesaras in forum C++ Programming
    Replies: 5
    Last Post: 12-14-2006, 09:43 AM
  4. Need help fast with counting consecutive occurances
    By c_323_h in forum C++ Programming
    Replies: 1
    Last Post: 07-04-2006, 12:48 AM
  5. occurances of string in a file
    By MB1 in forum C++ Programming
    Replies: 3
    Last Post: 03-28-2005, 04:03 PM

Tags for this Thread