Thread: Double Linked List Sorting

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    6

    Unhappy Double Linked List Sorting

    Hello, I am doing a double linked list that is loaded with points of a rectangle xmin, ymin, xmax, ymax. Now after all the points are loaded, I want to sort on each dimension but leave the sequence in order. Up to now here is my code (for just one dimension):

    Code:
    typedef struct nodes {
    	int v[DIMS*2];
    	struct nodes *next;
    	struct nodes *prev;
    	int rid;
    	int used;
    	struct dimlist *xmin;
    } nodes;
    
    typedef struct dimlist {
    	 struct nodes *head;
    	 struct nodes *tail;
    } dimlist;
    After creating that structure I load the points:

    Code:
    void loadMatrix(){
    
    	char buffer [1000];
    	fgets(buffer,1000,inputFile);
    	
    	int count = 1;
    	
    	while (feof(inputFile)==0)
    	{
    		nodes *tNode = (nodes *)malloc(sizeof(nodes));
    		
    sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode->v[2],&tNode->v[3]);
    	
    		tNode->rid=count;
    		tNode->used=0;
    		
    		if (list->head==NULL) {
    			list->head=list->tail=tNode;
    			list->head->next=list->tail->prev=NULL;
    		} else {
    			tNode->prev=list->tail;
    			list->tail->next=tNode;
    			list->tail=tNode;
    		};
    	
    		count++;
    
    		fgets(buffer,1000,inputFile);
    		
    		
    	};
    	printf("OK: %d records inserted in list.\n", count);
    };
    Ok, so now after the points are loaded, I want to keep them in that order, but I just want to sort the xmin so that if I traverse the list using xmin they will be sorted by xmin in ascending order, and so on for the other dimensions! When I tried to do a quicksort or even a bubble sort, it crashed. Any help?

    Thanks a Lot!

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Code:
    void loadMatrix(){
    
    	char buffer [1000];
    	fgets(buffer,1000,inputFile);
    	
    	int count = 1;
    	
    	while (feof(inputFile)==0)
    	{
    		nodes *tNode = (nodes *)malloc(sizeof(nodes));
    		
    sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode->v[2],&tNode->v[3]);
    	
    		tNode->rid=count;
    		tNode->used=0;
    		
    		if (list->head==NULL) {
    			list->head=list->tail=tNode;
    			list->head->next=list->tail->prev=NULL;
    		} else {
    			tNode->prev=list->tail;
    			list->tail->next=tNode;
    			list->tail=tNode;
    		};
    	
    		count++;
    
    		fgets(buffer,1000,inputFile);
    		
    		
    	};
    	printf("OK: %d records inserted in list.\n", count);
    };
    While in this case using feof() is okay, the whole thing would be much more readable if you just did this:
    Code:
    void loadMatrix(){
    
    	char buffer [1000];
    	int count = 1;
    	
    	while (fgets(buffer,1000,inputFile))
    	{
    		nodes *tNode = (nodes *)malloc(sizeof(nodes));
    		
    sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode->v[2],&tNode->v[3]);
    	
    		tNode->rid=count;
    		tNode->used=0;
    		
    		if (list->head==NULL) {
    			list->head=list->tail=tNode;
    			list->head->next=list->tail->prev=NULL;
    		} else {
    			tNode->prev=list->tail;
    			list->tail->next=tNode;
    			list->tail=tNode;
    		};
    	
    		count++;
    	};
    	printf("OK: %d records inserted in list.\n", count);
    };
    I'd also use sizeof(buffer) rather than hard-coding the value 1000 into the fgets() call.

    The new code also puts the declaration of count right at the beginning of the block, making the code C89. As you originally had it, count was declared in the middle of a block, making the code C99, which is a newer standard that fewer compilers support to any degree. Unless you're using other C99-specific code, it's probably best to stick with C89.

    Code:
    nodes *tNode = (nodes *)malloc(sizeof(nodes));
    Casting malloc() is a bad idea. I don't feel like going over the details here -- search the boards if you're curious. Leaving out the cast works just fine.

    Also, using sizeof(*tNode) instead of sizeof(nodes) is a good idea, in case you change the type of tNode or something. They're both compile-time constants, so no worry there.

    So I'd use:
    Code:
    nodes *tNode = malloc(sizeof(*tNode));
    Also note that the parentheses around sizeof(*tNode) are optional; they always are when you're taking the sizeof a variable. You need them in when you're taking the sizeof a type like nodes.

    It would be a good idea to check the return value of sscanf() to see if it encountered any errors. In this case, it should return 4 on success (because there are four format specifiers, %d and %f etc).

    You don't need the semicolons after the closing curly braces. The only place you do need them is after compound initializers or struct/union/enum declarations.

    Shouldn't count be initialized to zero rather than to one?

    Code:
    typedef struct nodes {
    	int v[DIMS*2];
    	struct nodes *next;
    	struct nodes *prev;
    	int rid;
    	int used;
    	struct dimlist *xmin;
    } nodes;
    
    typedef struct dimlist {
    	 struct nodes *head;
    	 struct nodes *tail;
    } dimlist;
    You don't need to use struct nodes inside the declaration for dmlist. You can use just plain nodes, because the typedef has taken effect by then.

    I don't understand why you've declared xmin as you have. First let's make sure I have its use down properly. You want a doubly-linked list. You also want a way to transverse this list in minimum order, while retaining the order of the original doubly-linked list as well. Is that right?

    Well, the way you have it set up, the first struct nodes would have to be the smallest before you sort it. If the nodes are in "random" order, and you still want a way to transverse them in order, I'd suggest fields like this:
    Code:
    typedef struct nodes {
    	int v[DIMS*2];
    	struct nodes *next;
    	struct nodes *prev;
    	int rid;
    	int used;
    	struct nodes *xmin;
    } nodes;
    
    typedef struct dimlist {
    	 struct nodes *head;
    	 struct nodes *tail;
    	struct nodes *xmin;
    } dimlist;
    That way, the first (and smallest) struct nodes can be anywhere in the original list, and you can transverse the list with head to go forwards, tail to go backwards, or xmin to go in sorted order.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    6

    Thanks

    First of all thanks, that was very informative and insightful. Now, I managed to arrange the program a little bit. It's not optimised but at least it is working. I am attaching it for anyone who wants to check it out...

    Please feel free to comment on this code, because my next step is to fix it to be able to sort on all points and then implement an PR-Tree on it.

    Thanks...

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Well, if you want more comments then that's what you're going to get.

    The first issue I can see with your code is that you never call free(). While it's true that nearly all modern operating systems will free memory dynamically allocated by your program when your program exits, until then, any memory that you malloc() will keep taking up space. Since you allocate memory inside nearly every function, as well as inside a loop, this memory use could increase quite quickly.

    It's always a good idea to free any memory that you allocate. You have no way of knowing how your code might be used in the future. For example, when I was writing a program of mine (codeform) which simply syntax highlighted code and then exited, I could easily have ignored memory freeing because the program ran so quickly and used so little memory. But later on, when I incorporated codeform into a text editor, if I hadn't freed all of its memory, my text editor would have been a memory hog indeed . . .

    Here's another thing.
    Code:
    typedef struct nodes {
    	int v[DIMS*2];
    	struct nodes *next;
    	struct nodes *prev;
    	int rid;
    	int used;
    	int xmin[2];
    } nodes;
    You're using xmin to store addresses, and keep having to cast xmin[x] to (nodes*), right? Well, why not make xmin[] of type nodes* to begin with? You can compare pointers and do everything with a nodes* that you can do with an int in your program, as far as I can see.

    Not to mention that the address of something isn't guaranteed to fit into an int. If you really don't want to use a nodes* for some reason, consider a void* pointer, which can hold the address of any object in C.

    Code:
    void loadFile(char *location){
    	inputFile = fopen(location,"r");
    	if (!inputFile)
    		printf("ERROR: Invalid source file path.\n");
    	else printf("OK: Input file found.\n");	
    };
    You got rid of nearly all of the semicolons after closing curly braces -- there are only a few left, at the ends of functions and loops mostly. They probably shouldn't be there, because it makes it look like the end of a structure or something. You could search for }; and get rid of the semicolons that don't need to be there.

    Also consider making location const, since you don't modify it in any way. Also, you call LoadFile like this:
    Code:
    loadFile("c:/r.txt");
    and since string literals are supposed to be const, a compiler might warn you about passing a string literal like "c:/r.txt" to a function that takes a non-const char*. I can't think of any compilers that would, but still.

    Everywhere you use DIMS, you actually use DIMS*2. Why not simply change the #defined value to twice its current value.

    Code:
    nodes *tNode = malloc(sizeof(*tNode));
    /* ... */
    nodes *tNode = malloc(sizeof *tNode);
    While sizeof() with and without parentheses works in this case, I'd be consistent and either use them everywhere or nowhere.

    There are also a few things that I mentioned in my previous post that you might still want to do, such as using sizeof(buffer) instead of 1000 in the fgets() call. Read it over again and you might find something that you missed before; it's quite a long post.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    6
    Once again, I looked at my program and followed your suggestions. Attached file is the updated one.

    Now, I have included all the points, and the first set are sorted in ascending order, and the second set in descending order. This means that multiple rectangles are passed by their extreme points (2 min, 2 max) and then I have 4 sorted lists - the first two ascending on the minimums, and the other 2 descending on the maximums.

    About the free(node). I do not use it, because it messes up my results. Everytime I put it at the end of a function, the results are never the same!

    Also is there any other way to put the following in a loop? So that if I have more than 4 values, I do not have to type them down?

    Code:
    sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode->v[2],&tNode->v[3]);
    Once again thanks for the help.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    It's getting bigger: from 3.6KB to 4.1KB. Unfortunately I can't open attachments on this computer, so I will not comment on your attached code at this time.

    Also is there any other way to put the following in a loop? So that if I have more than 4 values, I do not have to type them down?
    Code:
    sscanf(buffer,"%d%d%d%d",&tNode->v[0],&tNode->v[1],&tNode->v[2],&tNode->v[3]);
    Sure. The %n format specifier for *scanf() stores current position into a pointer to int. Or, more eloquently:
    %n
    No input is consumed. The corresponding argument must be a pointer to the integer into which is to be written the number of bytes read from the input so far by this call to the fscanf() functions. Execution of a %n conversion specification does not increment the assignment count returned at the completion of execution of the function.
    In other words, you'd use something like this:
    Code:
    int x, n = 0;
    
    for(x = 0; x < 4; x ++) {
        sscanf(buffer + n, "%d%n", &tNode->v[x], &n);
    }
    Actually, I might suggest using strtol(). Here's what the code would look like:
    Code:
    int x;
    char *start = buffer, *end;
    
    for(x = 0; x < 4; x ++) {
        tNode->v[x] = strtol(start, &end, 0);  /* base 0 means decimal, hex, and octal */
        start = end;
    }
    (Neither versions have error checking; you'd probably want to add that in yourself.)
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM