Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 512
  • Last Modified:

sorting - linked lists

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
Nicholas Niggel
Asked:
Nicholas Niggel
  • 2
  • 2
  • 2
  • +1
1 Solution
 
mulderbabaCommented:
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
 
Nicholas NiggelAuthor Commented:
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
 
Nicholas NiggelAuthor Commented:
also I can't use these

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

just
#include <stdio.h>
0
Independent Software Vendors: 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!

 
dhyaneshCommented:
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
 
dhyaneshCommented:
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
 
guynumber5764Commented:
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
 
mulderbabaCommented:
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

Independent Software Vendors: 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!

  • 2
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now