• C

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]);
  }
 
}
Nicholas NiggelAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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
What were the top attacks of Q1 2018?

The Threat Lab team analyzes data from WatchGuard’s Firebox Feed, internal and partner threat intelligence, and a research honeynet, to provide insightful analysis about the top threats on the Internet. Check out our Q1 2018 report for smart, practical security advice today!

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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.