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
Solved

sorting - linked lists

Posted on 2003-11-15
7
505 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
Easy, flexible multimedia distribution & control

Coming soon!  Ideal for large-scale A/V applications, ATEN's VM3200 Modular Matrix Switch is an all-in-one solution that simplifies video wall integration. Easily customize display layouts to see what you want, how you want it in 4k.

 
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

Ransomware: The New Cyber Threat & How to Stop It

This infographic explains ransomware, type of malware that blocks access to your files or your systems and holds them hostage until a ransom is paid. It also examines the different types of ransomware and explains what you can do to thwart this sinister online threat.  

Question has a verified solution.

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

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.

790 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