Thread: need other's perspective in reviewing array shifting & sorting functions

  1. #1
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42

    need other's perspective in reviewing array shifting & sorting functions

    Couldn't find the errors initially & yet for both sets of code, so need someone else's perspective.


    1) Does this function work OK in shifting an array of index entries for a new entry?

    Code:
    void indexinsert(const int& location, Index dindex[], int& size, const int& trrn, char addkey[]){
    	int i;
    	dindex = (Index*) realloc (dindex, (size+1) * sizeof(Index));
    	if (dindex==NULL) exit (1);
    	
    	printf("Range of Index entries shifted: start: %d end: %d\n",location,size);
    	for(i = size; i > location; i--){
    		dindex[i] = dindex[i-1];
    	}
    
    	strcpy(dindex[location].key,addkey);
    	dindex[location].rrn = trrn;
    
    	size++;
    	
    	return;
    }
    I've used printing statements for debugging & what I've found is this:

    the last 3 entries of index before calling function above:
    ie key -> associated data, which is the rrn.
    N8500R -> 15
    N87BC -> 1
    N97890 -> 25

    but after call to function, I get this for the end of the array:
    N8500R -> 15
    N87BC -> 1
    N97890 -> 25
    -> 0

    NOTE: the new key to be inserted is not put in the right place & what I get is that weird last line with rrn of 0.

    If this function is incorrect, how should I rewrite it?


    2) Does this function perform insert sort correctly? It seemed to be ok when I used this function to sort an index of 26 entries but just today, when the index was greater than 26 entries, something funny happens.

    If the additional entries (entries after 26th one) should go before the 1st entry (if sorting 26 entries), then the 1st entry just gets duplicated in the index from the sort, rather than placing the additional entries in the correct place. If the additional entries should go after the 1st entry it seems ok.

    ie.:
    1st entry is CP-188
    if 27th entry is ABC123, result is that you will see CP-188 appear twice in index after sort.
    if 27th entry is NBC123, sort works as intended with NBC123 being in sorted list at right place.

    Code:
    int compare(const Index entry1, const Index entry2){
    	return strcmp(entry1.key, entry2.key);
    }//this function orignally for use by cstdlib's qsort function, but was abandoned so for use below.
    
    
    void insert_sort(Index data[], int size){
    	Index temp;
    	int n = 1;
    	int i = 0, k = 0, j = 0;
    
    	for(i = 1; i < size; ++i){
    		temp = data[i];
    		j = i;
    		for(k = i - 1; k >= 0; k--){
    			if(compare(data[k],temp) > 0){
    				data[j--] = data[k];
    			}else{
    				data[j] = temp;
    				n = NULL;
    				break;
    			}
    		}
    		if(n != NULL)
    			data[j] = temp;
    	}
    	
    	return;
    }
    If this function is incorrect, how should I rewrite it?

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    126
    You know, if you really want to do sorting and insertion and the like, you should probably use an STL container like a vector or list. But if you're doing that just to gain a better understanding sorting and insertion algorithms...I couldn't help you. It's kind of hard to tell from your code whether you are a C or a C++ programmer...

  3. #3
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42
    well, so far in my classes, I haven't had the opportunity to learn how to use vectors. And a quick search of the web got me nowhere. Do you know of any sites with info on using vectors?

    As for lists, are you talking about linked lists? If so, is it not easier to search, sort an array rather than a linked list?

    The code listed here is for a lab project. I didn't write it to learn searching & sorting. I wrote the add/insert function of (1) based on my knowledge of working with arrays and I wrote the insert sort function based on the pseudocode from a course textbook. But I haven't been able to find possible errors, if any, so need some assistance.

    As for STL, didn't get to learn STL, but went over using linked lists, stacks, queues, b-trees, which is similar to what STL offers.

    As for C/C++, I try to make it C, so which parts make it be C++ then, aside from the ++& --, I suppose? The array argument parameter []? the const & pass by ref arguments?

    Oh, and a member told me to post here when I posted in the C forum, so that's why I post here.

  4. #4
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42
    thanks for the suggestions, Salem. A few quick things tho:

    I was thinking when using realloc, assigning the reallocation to the original array was ok, thus, bypassing a temp variable. And I thought that since dindex is an array of struct Index, I could pass it in without * reference (guess I was thinking C++, I didn't have a formal course in C, unlike C++)

    So in C, you pass arrays also with pointers and pass by reference is done by pointers? Any good websites where I can learn the standard structure of C coding?

  5. #5
    Registered User daluu's Avatar
    Join Date
    Dec 2002
    Posts
    42
    Salem,

    for some reason, your code suggestion partially works. Could it be how the rest of the programs functions are implemented? Since the index read/write functions were implemented as I thought they should be kinda like the indexinsert.

    When applying your code, the new keys gets placed in the correct place, but in the process the rest of the array is messed up. The output goes like this:

    |1145328692
    |0
    DDT451|19
    |0
    |0


    one of the array elements will look like the 1st line, and the rest of the elements are empty with the 0 rrn. Only the new key gets placed where it should be.

    This is how dindex was originally allocated before 1st use:

    Code:
    dindex = (Index *) malloc(sizeof(Index)*size); //in int main()
    this is how index was read from file into dindex array:

    Code:
    void readindex(const long& flength, FILE* dfile, int byte, Index the_index[]){
    	unsigned char ch;
    	// i = Index entry pos, k = key elem pos, t = tmp elem pos
    	int k = 0, i = 0, t = 0;
    	char tmp[6];
    	ch = fgetc(dfile);
    	byte++; //increment byte offset indicator
    	while(!feof(dfile)){		
    		//store key up to 6 chars 
    		if(k < 6) the_index[i].key[k++] = ch;
    		ch = fgetc(dfile); 
    		byte++;
    		
    		if(k == 6){ //PARSE RRN
    			the_index[i].key[k] = '\0'; //NULL delimit key string
    			ch = fgetc(dfile); //discard tab char
    			byte++;
    			t = 0;
    			tmp[0] = 0;
    			memset(tmp,'\0',6);
    			tmp[t++] = ch; //store RRN digit
    			ch = fgetc(dfile); //get next char
    			byte++;
    			while((ch != 10) && (ch != 13)){ //while char not tab char
    				tmp[t++] = ch; //continue store RRN digits
    				ch = fgetc(dfile); 
    				byte++; }
    			the_index[i].rrn = atoi(tmp); //convert RRN string to int & store
    			if(ch == 13){ //discard Windows's extra endline representation	
    				ch = fgetc(dfile);
    				byte++;}
    			if(ch == 10){ //when hit endline start parse next key entry in index
    				i++; //next index entry
    				ch = fgetc(dfile); //Discard endline value
    				byte++;
    				if(byte == flength) return; //discard last byte ...
    				k = 0; } //Reset field array position 
    		}
    	}
    
    	return;
    }
    These code work okay for my index delete, binary search, sorting, & creation functions. It only seems to give me problems in the indexinsert function. I wonder why?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 03-31-2009, 12:34 PM
  2. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  3. Array of Structures: Sorting
    By Drainy in forum C Programming
    Replies: 3
    Last Post: 04-13-2005, 09:55 AM
  4. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM