Solved

sorting - linked lists

Posted on 2003-11-15
7
502 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
  • 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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
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 structures in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

747 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now