Solved

sorting - linked lists

Posted on 2003-11-15
7
507 Views
Last Modified: 2010-04-15
Hello

I am working on my homework and am stuck. I have 2 arrays of strings gotten from a single data file of 2 columns of names, and need to sort them into a single linked list. I believe my problem lies in the while loop below. It wont exit. I am trying to execute the code in the loop as long as there are elements still in the arrays to be compared. while (list1[index1] && list2[index2])

I haven't yet starting to write the data back to the data file which I need to do. Any help much appreciated.

#include <stdio.h>
#define CHARS 30
#define NAMES 20
main()
{
struct NODE {
   char name[CHARS];
   struct NODE *next;
};
typedef struct NODE Node;

int count= -1;
int index1=0,index2=0;
int i;
char list1[NAMES][CHARS],list2[NAMES][CHARS];
FILE *fp;

/* open the file and load the strings into 2 arrays  */
 fp=fopen("merge.dat","r");
 while (!feof(fp)) {
   count++;
   fscanf(fp,"%s %s ",list1[count],list2[count]);
 }
 fclose(fp);

  Node* head;
  head = (Node*)malloc(sizeof(Node));
  Node* curr;
  curr = head;

  while (list1[index1] && list2[index2]){
    if ( 0 > strcmp(list1[index1], list2[index2]) ) {
      curr->next = (Node*)malloc(sizeof(Node));
      curr = curr->next;
      strcpy(curr->name,list1[index1]);
      index1++;
    }
    else{  
      curr->next = (Node*)malloc(sizeof(Node));      
      curr = curr->next;
      strcpy(curr->name,list2[index2]);
      index2++;
    }
  }
   
  curr = head;
  while (!feof(fp)) {
    count++;
    fscanf(fp,"%s\n",curr->name[count]);
  }
 
}
0
Comment
Question by:Nicholas Niggel
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
  • +1
7 Comments
 

Expert Comment

by:mulderbaba
ID: 9756764
Hey Jim_Pgh,

If I didn't get you wrong, you need a sorting in an alphabetical way.
The code reads from the merge.dat to one list. And then build up the
linked list. I used only one list array. Warn me if it is prohibited.
The result is written to merged.dat file.

 Hope this helps.
 mulderbaba


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

#define FALSE 0
#define TRUE ~FALSE

#define CHARS 30
#define NAMES 20

struct NODE {
      char name[CHARS];
      struct NODE *next;
};

typedef struct NODE Node;

/***************************************************************/

int main()
{
      int count = -1;
      int index= 0;

      Node *head;
      Node *curr;
      Node *newNode;

      char list[NAMES][CHARS];
      FILE *fp;

      /* open the file and load the strings into 2 arrays  */
      fp = fopen("merge.dat","r");
      while (!feof(fp)) {
          count = count + 1;
          fscanf(fp,"%s",list[count]);
      }
      fclose(fp);

      /* defining the head of the linked list */
      head = (Node*) malloc(sizeof(Node));;
      strcpy(head->name, "");
      head->next = NULL;

      while (index <= count)    {
          curr = head;

          if(head->next == NULL) /*If the linked list is empty,*/
          {
              newNode = (Node*) malloc(sizeof(Node));
              strcpy(newNode->name, list[index]);
              newNode->next = NULL;
              head->next = newNode;

          }
          else /* If the linked list is not empty, */
          {
             /* Iterating to the place where the inserting will be done */
             while (strcmp(list[index], curr->next->name) > 0 && curr->next != NULL)
                  curr = curr->next;

             /* Inserting newNode into the linked list */
             newNode = (Node*) malloc(sizeof(Node));
             strcpy(newNode->name, list[index]);
             newNode->next = curr->next;
             curr->next = newNode;
          }

          index = index + 1;
      }

      /* Writing the result to merged.dat file by reading from linked list. */
      curr = head->next;
      fp = fopen("merged.dat","w");
      while (curr != NULL) {
          fprintf(fp, "%s\n", curr->name);
          curr = curr->next;
      }
      fclose(fp);

      return TRUE;
}
0
 

Author Comment

by:Nicholas Niggel
ID: 9756874
Hey mulderbaba
Thanks for responding. The assignment actually calls for the data to be put into 2 arrays. the dat file looks like this

alex       bob
gary      carl
jim        fred
etc...

each column is already sorted. We need to read the data into 2 arrays, then combine them sorted in one pass as we put them into the linked list using a merge sort.

-  jim
0
 

Author Comment

by:Nicholas Niggel
ID: 9756990
also I can't use these

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

just
#include <stdio.h>
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Expert Comment

by:dhyanesh
ID: 9757736
hi

The problem is definitely in the while loop.

while(list1[index1] && list2[index2]) does not make any sense.

A better way would be to use two counters. If the number of elements in both the lists is same as it seems in your case then both counters say count1 and count2 would be initialize to 'count+1' which would be no. of elements in each list.

Now when you copy an element from list1 decrement count1 and for list2 decrement count2. The check condition would be:

while (count1 > 0 && count2>0)

Also at the end you would have two loops one after the other to copy any remaining elements into the link list. The loops would be :

while (count1 > 0)
{
   //copy remaining elements from list1 to link list
}

while (count2 > 0)
{
   //copy remaining elements from list2 to link list
}

These are required as it is possible that one of the arrays is completely copied while the other is not.

At the end of all the loops you have to set.

curr->next = NULL to indicate end of link list.

First to write the data you have to close the file and open it in write mode i.e.

fclose(fp);
fp=fopen("output.dat","w");

Also to write the data you can use fputs(). You will have to take curr = head again and until it is not equal to NULL display curr->name using fputs(curr->name,fp).

Dhyanesh
0
 
LVL 4

Accepted Solution

by:
dhyanesh earned 200 total points
ID: 9757744
hi

One more thing I forgot.

If you cannot use string.h then you cannot use strcmp() and strcpy() functions. These require string.h

You will have to define your own functions for these. This should not be too difficult as for strcmp you have to just compare the array char by char and see if it is same. Also for strcpy the array is copied char by char.

Also for malloc() you will require either alloc.h or stdlib.h.

Dhyanesh
0
 
LVL 3

Expert Comment

by:guynumber5764
ID: 9757892
I've done this in past with something like...

while ( !eof(1) && !eof(2) )
{
     while( !eof(1) && (eof(2) || (current1 < current2)) )
      {
            addtail current1
            getnext current1
      }
     while( !eof(2) && (eof(1) || (current2 < current1)) )
      {
            addtail current2
            getnext current2
      }
}

0
 

Expert Comment

by:mulderbaba
ID: 9758404
Hey Jim.
I think this will be helpful to you. It is doing the merge sort on an unsorted linked list. If you do not use the string.h or stdlib.h you'll get the prototype warning. Be careful about that.


#include <stdio.h>

#define FALSE 0
#define TRUE ~FALSE

#define CHARS 30
#define NAMES 20

struct NODE {
      char name[CHARS];
      struct NODE *next;
};

typedef struct NODE Node;


/* prototypes */
Node* merge_sort(Node *);
Node* split (Node *);
Node* merge(Node *, Node *);


Node* merge_sort(Node *list1)  {
    Node *list2;

    if (list1 == NULL || list1->next == NULL) /* checking for empty or single list */
      return list1;
    list2 = split(list1);
    list1 = merge_sort (list1);
    list2 = merge_sort (list2);
    return merge (list1, list2);
}


Node* split (Node *list1) {
   Node *list2;

    if (list1 == NULL || list1->next == NULL)
       return NULL;
   list2 = list1->next;
   list1->next = list2->next;
   list2->next = split (list2->next);
   return list2;
}

Node* merge(Node *list1, Node *list2)  {
   if (list1 == NULL) return list2;
   if (list2 == NULL) return list1;

   if (strcmp(list1->name, list2->name) < 0) {
      list1->next = merge (list1->next, list2);
      return list1;
   }
   else {
      list2->next = merge (list1, list2->next);
      return list2;
   }
}

/******************************************************************/

int main()
{
      int count1 = -1, count2 = -1;

      Node *head;
      Node *curr;
      Node *newNode;

      char list1[NAMES][CHARS], list2[NAMES][CHARS];
      FILE *fp;

      clrscr();

      /* open the file and load the strings into 2 arrays  */

      fp = fopen("merge.dat","r");
      while (!feof(fp)) {
          count1 = count1 + 1;
          count2 = count2 + 1;
          fscanf(fp,"%s %s",list1[count1], list2[count2]);
      }
      fclose(fp);

      /* defining the head of the linked list */
      head = (Node*) malloc(sizeof(Node));;
      strcpy(head->name, "");
      head->next = NULL;

      curr = head;

      /* inserting from the list1 into the linked list */
      while(count1 >= 0)
      {
         newNode = (Node*) malloc(sizeof(Node));
         strcpy(newNode->name, list1[count1]);
         newNode->next = curr->next;
         curr->next = newNode;
         count1 = count1 - 1;
      }

      /* inserting from the list2 into the linked list */
      while(count2 >= 0)
      {
         newNode = (Node*) malloc(sizeof(Node));
         strcpy(newNode->name, list2[count2]);
         newNode->next = curr->next;
         curr->next = newNode;
         count2 = count2 - 1;

      }

      /* Doing the Merge Sort */
      head = merge_sort(head);

      /* Writing the result to merged.dat file by reading from linked list. */

      curr = head->next;
      fp = fopen("merged.dat","w");
      while (curr != NULL) {
          fprintf(fp, "%s\n", curr->name);
          curr = curr->next;
      }
      fclose(fp);

      return TRUE;
}
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question