Solved

bubble sort error

Posted on 2002-05-31
12
373 Views
Last Modified: 2008-03-17
i got this code off the net.  doesn't quite work for me. can anybody find the problem? error is marked in the code
thanks


main.cpp ------------------

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#include "io_func.h"


#define FALSE 0
#define TRUE  1

struct LIST_RECORD
{
  double data;
  struct LIST_RECORD *next;
};

FILE *infile_ptr;
FILE *outfile_ptr;

double Compute_Mean(struct LIST_RECORD *list_head);
double Compute_Variance(double mean, struct LIST_RECORD *list_head);
void   Sort_Data_List(struct LIST_RECORD *start_p, int num_records);


int main(void)
{
  static char in_file_name[20];
  static char input_buffer[256];

  int num_words = 0;
  int i = 1;

  double input_value;
  double mean = 0.0;
  double std_deviation = 0.0;
  double variance = 0.0;

  struct LIST_RECORD *list_ptr = NULL;
  struct LIST_RECORD *list_head = NULL;
  struct LIST_RECORD *list_tail = NULL;

  Write_KB_String("Enter input file name: ");

  /* Get input file name from the user. Exit immediately on error */
  /*if (!Read_KB_String(in_file_name))*/
  if (gets(in_file_name) == NULL)
  {
    printf("\nError while reading input file name.\n");
    getch();
    exit(1);
  }
   
  /* Open input file. Exit immediatedly on error */
  printf("\nin_file_name is %s\n", in_file_name);
  if ((infile_ptr = fopen(in_file_name, "r")) == NULL)
  {
    printf("\nFile open error: %s\n", in_file_name);
    getch();
    exit(1);
  }

  /* Open output file. Exit immediatedly on error */
  if ((outfile_ptr = fopen("output.txt", "w")) == NULL)
  {
    printf("\nFile open error: %s\n", "output.txt");
    getch();
    exit(1);
  }


  do
  {
    if (fscanf(infile_ptr, "%s", input_buffer) != EOF)
    {
          num_words++;
      input_value = atof(input_buffer);
          printf("\nin_buf = %s %f\n", input_buffer, input_value);

      if (list_ptr = (struct LIST_RECORD *)malloc(sizeof(struct LIST_RECORD)))
      {
        list_ptr->data = input_value;
        list_ptr->next = NULL;

        if (!list_head)
        {
          list_head = list_tail = list_ptr;
        }
        else
        {
          list_tail->next = list_ptr;
          list_tail = list_ptr;
        }
      }
      else
      {
        printf("\nError on malloc\n");
        getch();
        exit(0);
      }
      i++;
    }
  } while (!feof(infile_ptr));


  /* Print data list to console. */
  list_ptr = list_head;
 
  while (list_ptr)
  {
    printf("\ndata = %6.2f", list_ptr->data);
    list_ptr = list_ptr->next;
  }

  mean = Compute_Mean(list_head);
  printf("\nMean = %10.2f\n", mean);

  variance = Compute_Variance(mean, list_head);
  printf("\nVariance = %10.2f\n", variance);

  std_deviation = sqrt(variance);
  printf("\nStandard Deviation = %10.2f\n", std_deviation);

  Sort_Data_List(list_head, num_words);

  /* Print data list to console. */
  list_ptr = list_head;
 
  while (list_ptr)
  {
    printf("\ndata = %6.2f", list_ptr->data);
    list_ptr = list_ptr->next;
  }

  getch();

  return 0;
}

/*  */
double Compute_Mean(struct LIST_RECORD *list_head)
{
  double local_mean = 0.0;
  double sum = 0.0;
  int    num_records = 0;

  struct LIST_RECORD *ptr;

  ptr = list_head;

  while (ptr)
  {
    num_records++;
    sum += ptr->data;
    ptr = ptr->next;
  }

  if (num_records == 0)
    local_mean = 0.0;
  else
  {
    local_mean = sum / (double)num_records;
  }

  return local_mean;
}

/* */
double Compute_Variance(double mean, struct LIST_RECORD *list_head)
{
  struct LIST_RECORD *ptr;

  int    num_records = 0;
  double diff = 0.0;
  double local_variance = 0.0;
  double sum = 0.0;

  ptr = list_head;

  while (ptr)
  {
    num_records++;
    diff = ptr->data - mean;
    sum += (diff * diff);
    ptr = ptr->next;
  }

 if (num_records == 0)
    local_variance = 0.0;
  else
  {
    local_variance = sum / (double)num_records;
  }

  return local_variance;
}

 /* this is a bubble sort */
void Sort_Data_List(struct LIST_RECORD *start_p, int num_records)
{
  struct LIST_RECORD *curr_p;
  struct LIST_RECORD *last_p;

  int i;

  for (i = 1; i < num_records; i++)
  {
    curr_p = start_p;
    last_p = NULL;

    while (curr_p->next != NULL)
    {
      /********************************************/
      /********************************************/
      /********************************************/
      /******************************************/
      /* this line fails because curr_p->next is */
      /* null and access violation occurs */
      if (curr_p->data > curr_p->next->data)  /* need to swap */
      {
        if (last_p == NULL)  /* head of list */
        {
          start_p = curr_p->next;
          curr_p->next = curr_p->next->next;
          start_p->next = curr_p;
        }
        else
        {
          last_p->next = curr_p->next;
          curr_p->next = curr_p->next->next;
          last_p->next->next = curr_p;
        }
      }

      last_p = curr_p;
      curr_p = curr_p->next;
    }
  }
}

io_funcs.cpp -----------------

#include "stdio.h"

/* Returns TRUE if no error on keyboard string read */
int Read_KB_String(char *str)
{
  return (gets(str) != NULL);
}


void Write_KB_String(char *str)
{
  puts(str);
}

io_funcs.h ------------------------

int Read_KB_String(char *str);

void Write_KB_String(char *str);
0
Comment
Question by:omom
[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
  • 4
  • 4
  • 3
  • +1
12 Comments
 
LVL 1

Expert Comment

by:Toad224
ID: 7047733
You do know that bubble sort is very inefficient, right?

What problem are you having?  It seems to compile and work fine for me.  You need to create a file, and put numbers in there, and input that as the filename when the program starts.
0
 

Author Comment

by:omom
ID: 7047738
sorry, the input file i am working with contains
39.7
22.56
801
56.2
54.6
211
33.5

0
 
LVL 86

Expert Comment

by:jkr
ID: 7047751
Where do you get the error? There's no "mark" in the above code...
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!

 
LVL 1

Expert Comment

by:Toad224
ID: 7047756
ah.. now I get the error.. I was using the data:

8 7 5 4
1 2 3 4
3 6 9


before...  hmm.. let me see what's wrong...
0
 
LVL 1

Expert Comment

by:Toad224
ID: 7047771
ah.. now I get the error.. I was using the data:

8 7 5 4
1 2 3 4
3 6 9


before...  hmm.. let me see what's wrong...
0
 
LVL 1

Expert Comment

by:Toad224
ID: 7047785
ah.. now I get the error.. I was using the data:

8 7 5 4
1 2 3 4
3 6 9


before...  hmm.. let me see what's wrong...
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 7047803
Unless sorting a linked list is part of the assignment, this will get you an A:

void Sort_Data_List(struct LIST_RECORD *start_p, int num_records)
{
     struct LIST_RECORD *p;
     int i;

     for (i = 1; i < num_records; i++) {
          p= start_p;          
          while ( p && p->next ) {
               if      (p->data > p->next->data ) { // swap em
                    double nTmp= p->data;
                    p->data= p->next->data;
                    p->next->data= nTmp;
               }
               p= p->next;
          }
     }
}

-- Dan
0
 

Author Comment

by:omom
ID: 7047804
not an assigment, nice thought though
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 7047806
It is simpler becasue it just swaps the data elements rather than rearranging all of the links.  The end result is the same, but it does not illustrate how to swap links (a technique that would be needed for larger or more complex payloads).

-- Dan
0
 

Author Comment

by:omom
ID: 7047840
think i figured it out:


#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "math.h"
#include "io_func.h"


#define FALSE 0
#define TRUE  1

struct LIST_RECORD
{
  double data;
  struct LIST_RECORD *next;
};

FILE *infile_ptr;
FILE *outfile_ptr;

double Compute_Median(struct LIST_RECORD *list_head, int num_records);
double Compute_Mean(struct LIST_RECORD *list_head);
double Compute_Variance(double mean, struct LIST_RECORD *list_head);
struct LIST_RECORD * Sort_Data_List(struct LIST_RECORD *start_p, int num_records);


int main(void)
{
  static char in_file_name[20];
  static char input_buffer[256];

  int num_words = 0;
  int i = 1;

  double input_value;
  double mean = 0.0;
  double median = 0.0;
  double std_deviation = 0.0;
  double variance = 0.0;

  struct LIST_RECORD *list_ptr = NULL;
  struct LIST_RECORD *list_head = NULL;
  struct LIST_RECORD *list_tail = NULL;

  Write_KB_String("Enter input file name: ");

  /* Get input file name from the user. Exit immediately on error */
  /*if (!Read_KB_String(in_file_name))*/
  if (gets(in_file_name) == NULL)
  {
    printf("\nError while reading input file name.\n");
    getch();
    exit(1);
  }
   
  /* Open input file. Exit immediatedly on error */
  printf("\nin_file_name is %s\n", in_file_name);
  if ((infile_ptr = fopen(in_file_name, "r")) == NULL)
  {
    printf("\nFile open error: %s\n", in_file_name);
    getch();
    exit(1);
  }

  /* Open output file. Exit immediatedly on error */
  if ((outfile_ptr = fopen("output.txt", "w")) == NULL)
  {
    printf("\nFile open error: %s\n", "output.txt");
    getch();
    exit(1);
  }


  do
  {
    if (fscanf(infile_ptr, "%s", input_buffer) != EOF)
    {
          num_words++;
      input_value = atof(input_buffer);
          printf("\nin_buf = %s %f\n", input_buffer, input_value);

      if (list_ptr = (struct LIST_RECORD *)malloc(sizeof(struct LIST_RECORD)))
      {
        list_ptr->data = input_value;
        list_ptr->next = NULL;

        if (!list_head)
        {
          list_head = list_tail = list_ptr;
        }
        else
        {
          list_tail->next = list_ptr;
          list_tail = list_ptr;
        }
      }
      else
      {
        printf("\nError on malloc\n");
        getch();
        exit(0);
      }
      i++;
    }
  } while (!feof(infile_ptr));


  /* Print data list to console. */
  list_ptr = list_head;
 
  while (list_ptr)
  {
    printf("\ndata = %6.2f", list_ptr->data);
    list_ptr = list_ptr->next;
  }

  mean = Compute_Mean(list_head);
  printf("\nMean = %10.2f\n", mean);

  variance = Compute_Variance(mean, list_head);
  printf("\nVariance = %10.2f\n", variance);

  std_deviation = sqrt(variance);
  printf("\nStandard Deviation = %10.2f\n", std_deviation);

  list_head = Sort_Data_List(list_head, num_words);
  list_ptr = list_head;

  /* Print out sorted list */
  while (list_ptr)
  {
    printf("\ndata = %6.2f", list_ptr->data);
    list_ptr = list_ptr->next;
  }

  median = Compute_Median(list_head, num_words);
  printf("\nMedian = %10.2f\n", mean);

  getch();

  return 0;
}

/*  */
double Compute_Mean(struct LIST_RECORD *list_head)
{
  double local_mean = 0.0;
  double sum = 0.0;
  int    num_records = 0;

  struct LIST_RECORD *ptr;

  ptr = list_head;

  while (ptr)
  {
    num_records++;
    sum += ptr->data;
    ptr = ptr->next;
  }

  if (num_records == 0)
    local_mean = 0.0;
  else
  {
    local_mean = sum / (double)num_records;
  }

  return local_mean;
}

double Compute_Median(struct LIST_RECORD *list_head, int num_records)
{
  return 3.4;
}

/* */
double Compute_Variance(double mean, struct LIST_RECORD *list_head)
{
  struct LIST_RECORD *ptr;

  int    num_records = 0;
  double diff = 0.0;
  double local_variance = 0.0;
  double sum = 0.0;

  ptr = list_head;

  while (ptr)
  {
    num_records++;
    diff = ptr->data - mean;
    sum += (diff * diff);
    ptr = ptr->next;
  }

 if (num_records == 0)
    local_variance = 0.0;
  else
  {
    local_variance = sum / (double)num_records;
  }

  return local_variance;
}

 /* this is a bubble sort */
/*void*/ struct LIST_RECORD * Sort_Data_List(struct LIST_RECORD *start_p, int num_records)
{
  struct LIST_RECORD *curr_p;
  struct LIST_RECORD *last_p;

  int i;

  for (i = 1; i < num_records; i++)
  {
    curr_p = start_p;
    last_p = NULL;

    while (curr_p->next != NULL)
    {
      /* this line fails because curr_p->next is null and access violation occurs. */
      if (curr_p->data > curr_p->next->data)  /* need to swap */
      {
        if (last_p == NULL)  /* head of list */
        {
          start_p = curr_p->next;
          last_p = curr_p->next;
          curr_p->next = curr_p->next->next;
          start_p->next = curr_p;
        }
        else
        {
          last_p->next = curr_p->next;
          curr_p->next = curr_p->next->next;
          last_p->next->next = curr_p;
          last_p = last_p->next;
          /*curr_p = curr_p->next;*/
        }
      }
      else
      {
        last_p = curr_p;
        curr_p = curr_p->next;
      }
    }
  }
  return (start_p);
}

0
 
LVL 49

Expert Comment

by:DanRollins
ID: 7047857
Did you try my solution?  It works perfectly and is much simpler.

-- Dan
0
 
LVL 49

Accepted Solution

by:
DanRollins earned 300 total points
ID: 7047883
If you feel the urge to shiffle link pointers, this will do it:

void   Sort_Data_List(struct LIST_RECORD** pStart_p, int num_records);
...
Sort_Data_List( &list_head, num_words);
...

void Sort_Data_List( struct LIST_RECORD** pStart_p, int num_records )
{
     struct LIST_RECORD* p;
     struct LIST_RECORD* pPrev;
     struct LIST_RECORD* pHead= *pStart_p;
     int i;

     for (i = 1; i < num_records; i++) {
          p= pHead;
          pPrev= NULL;
          while ( p && p->next ) {
               if ( p->data > p->next->data ) { // swap em
                    if ( ! pPrev ) {   // at head
                          pHead=       p->next;
                          p->next=     p->next->next;
                          pHead->next= p;
                          pPrev=       p->next;
                    }
                    else {
                         pPrev->next=       p->next;
                         p->next=           p->next->next;
                         pPrev->next->next= p;
                    }
               }
              pPrev= p;
               p=     p->next;
          }
     }
     *start_p= pHead;
}
0

Featured Post

On Demand Webinar - Networking for the Cloud Era

This webinar discusses:
-Common barriers companies experience when moving to the cloud
-How SD-WAN changes the way we look at networks
-Best practices customers should employ moving forward with cloud migration
-What happens behind the scenes of SteelConnect’s one-click button

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Getting IP address 8 121
Move constructor only called if marked noexcept? 6 119
Why isn't object file created? 6 104
cmake and message 1 16
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

740 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