merge algorithm

Ja, jeg fik sendt kopieret merge algoritmen to gange i mit spoergsmaal, saa det ser vaerre ud end det er.
Lad mig poste det igen, saa det ser mere overskueligt ud:


Algorithm for merge
Assumption: ListA and ListB are sorted. ListC is big enough to hold lenA+lenB elements.
input: listA, lenA, ListB , LenB
output: listC (sorted), lenC

Local variables i, j, k as indices for ListA, ListB, and ListC

1.    set i to be the index of the first element in the listA
2.    set j to be the index of the first element in the listB
3.    set k to be the index of the first element in the listC

4.    As long as i is less than or equal to the index of the last element in ListA
and j is less than or equal to the index of the last element in ListB do the following:


4.1.    if ListA[i] < listB[j]     
            listC[k] gets the value of listA[i]
increment i
4.2.    Else
            listC[k] gets the value of listB[j]
increment j

4.3.    increment k

5.    store the leftover elements in listC.
6.    lenC = lenA + lenB


oversat til foelgende:
**********************

void merge_function (int listA [], int& lenA, int listB [], int& lenB, int listC [], int& lenC)
{
   
    int A, B, C;
    int i = listA [0];
    int j = listB [0];
    int k = listC [0];
    while (i <= listA [lenA - 1] && j<= listB [lenB - 1])
        if    (listA [i] < listB [j])
            listC [k] = listA [i];
        else
            listC [k] = listB [j];
            j++;
           
        k++;


        for (C; i< lenA; i++; k++)
        {
            C[k]= A[i];
            k++;
            i++;
        }
        for (C; j< lenB; j++; k++)
        {
            C[k]= B[j];
            k++;
            j++;
        }
        lenC = lenA + lenB;
}

Du laver et par få fodfejl i initieringen, din while betingelse, du mangler nogle tuborg-klammer og du får talt indeksene på de to lister op, selvom du ikke har brugt elementerne endnu:

void merge_function (int listA [], int& lenA, int listB [], int& lenB, int listC [], int& lenC)
{
    int i = 0; // Alle indekser starter med det første element.
    int j = 0;
    int k = 0;
    while (i <= lenA && j<= lenB) // Indtil begge lister er tømt.
    { // Turborg klamme her for at få k++ med i løkken.
      // Hvis een af listerne er blevet tom, skal du blot tømme den anden.
      if (i > lenA)
        listC[k] = listB[j++];
      else
      {
        if (j > lenB)
          listC[k] = listA[i++];
        else
        { // Manglede klamme - og du skal kun tælle indekset for den liste du bruge op => i++ hvis liste a, j++ hvis liste b
          if (listA[i] < listB[j])
            listC[k] = listA[i++];
          else
            listC[k] = listB[j++];
        };
      };
      k++;
    }; // Slut på while.
    lenC = lenA + lenB;
}

Mange tak for dit hurtige svar, det var en stor hjaelp.
Jeg satte det ind i mit program og proevde at faa det til at virke. Men jeg har vist problemer med function call. Til mit prgram laver jeg to tekst filer i notepad, gemmer dem i \\c og kalder dem hhv datafileA og datafileB.
Hvis du har tid til at kigge paa det er det en stor hjaelp, men jeg kan udmaerket fortsaa hvis ikke.


#include <iostream.h>                      // for input and output statements
#include <fstream.h>                      // for reading from and writing to a file

#define  DATAFILE_A "c:\\datafileA.txt"    // the file containing integer numbers
#define  DATAFILE_B "c:\\datafileB.txt"

const int MAX_LEN = 50;                    // maximum number of elements
const char BLANK = ' ';                    // used for a dummy character
const int DONT_CARE = 0;                  // used for a dummy integer variable
const int SO_MANY_CHARS = 100;            // to be used with ignor() to skip blanks

enum message_type {OPENING,CLOSING,WARNING, NOT_FOUND};

//==========================================================================================
//                                    prototypes
//==========================================================================================

void print_message(message_type sttm, char ch, int val, int pos);
void fill_list(ifstream &infile, int list[], int& len);
void insertion_sort (ifstream& infile, int list[], int& len );
int where_in_the_array(int list [], int len, int buffer);
void shift_right (int list[], int len, int pos);
void merge (int listA [], int& lenA, int listB [], int& lenB, int listC [], int& lenC);

//******************************************************************************************
//                                    main()
//******************************************************************************************

void main()
{

    int listA [MAX_LEN];  // the list A for holding up to MAX_LEN numbers
    int listB [MAX_LEN];    // the list B for holding up to MAX_LEN numbers
    int listC [2* MAX_LEN];    // the list C for holding up to MAX_LEN numbers
    int length;        //  number of elements of the array
    int lenA, lenB, lenC;
       

    ifstream infile;    //input file stream


    infile.open(DATAFILE_A,ios::in|ios::nocreate);//open datafile A for reading
    if (infile.fail())
        cout<<"*** Can't open the file**"<<endl;
    else
    {   
        print_message(OPENING,BLANK,DONT_CARE,DONT_CARE);

        insertion_sort (infile,listA,length);
        fill_list (infile, listA, length);
        fill_list (infile, listB, length);
        merge_function (listA, lenA, listB, lenB, listC, lenC);
       
        infile.close();
    }

    infile.open(DATAFILE_B,ios::in|ios::nocreate);//open datafile B for reading
    if (infile.fail())
        cout<<"*** Can't open the file**"<<endl;
    else
    {   
        print_message(OPENING,BLANK,DONT_CARE,DONT_CARE);

        insertion_sort (infile,listB,length);


      merge_function (listA, lenA, listB, lenB, listC, lenC);
               

        infile.close();
    }
   
}
//******************************************************************************************
// print_message()
// This function writes messages on the screen.
//******************************************************************************************
void print_message(/*in*/  message_type sttm,  //type of message
                    /*in*/  char ch,            //used with UNKNOWN_CHAR message
                    /*in*/  int val,            //used with NOT_FOUND and POSITION_INLIST message
                    /*in*/  int pos)            //used with POSITION_INLIST message
{
    switch (sttm)
    {
   

   

    case OPENING:      cout<<"This program takes two sorted lists and combines them into one.  "
                            <<"Here is the lists (read from files):" << endl;
                      break;

    case CLOSING:    cout<<"***********************************************************n";
                      cout<<"      Thanks for choosing our program and bye now.n";
                      cout<<"***********************************************************n";
                      break;

      case WARNING:    cout<<"----Warning---> The file contains more than " << MAX_LEN<<" elements. ";
                      cout<<"Only the first "<< MAX_LEN<<" elements will be processed.n";
                      break;//UNNECESSARY BUT A GOOD HABIT

    case NOT_FOUND:    cout<<"=======> Sorry "<<val<<" is not in the listn";
                      break;

    }

}
//******************************************************************************************
//                                        fill_list()
// This function fills up the array with numbers in the file.  If the file contains
// more than MAX_LEN numbers only the first MAX_LEN numbers will be processed.
//******************************************************************************************
void fill_list(/* in*/ ifstream &infile,//contains the numbers
              /*out*/ int list[],        //for holding the numbers
              /*out*/ int& len)        //length of the list
{
    int buffer;                            //temporary storage for numbers 
    len=0;                                //initialize the length

                                       
    infile >> buffer;                    // priming read in the buffer
    while (infile && (len < MAX_LEN))    // as long as the file is not empty and
    {                                    // there are enough locations in the array
        list[len]=buffer;               
        len++;                         
        infile >> buffer;                // read the next number
    }       

    if (infile)                            //More than MAX_LEN elements
        print_message(WARNING,NOT_FOUND,BLANK,DONT_CARE);
}

//******************************************************************************************
// insertion_sort()
// This function finds the correct position in the buffer if there is
// room in the array
//******************************************************************************************
void insertion_sort (ifstream& infile, int list[], int& len )
{
    int buffer;                            //temporary storage for numbers
    int position;
    len=0;
    infile >> buffer;                    // priming read in the buffer
    while(infile && len < MAX_LEN)        // as long as the file is not empty and
    {                                    // there are enough locations in the array
    position = where_in_the_array(list, len, buffer);
    shift_right (list, len, position);
    list[position]=buffer;
    len++;
    infile>>buffer;                        // priming read in the buffer
    }
    if (infile)                            //More than MAX_LEN elements
        print_message(WARNING,NOT_FOUND,BLANK,DONT_CARE);
}
//******************************************************************************************
// where_in_the_array()
// This function makes room for the position you want to enter
//
//******************************************************************************************
int where_in_the_array(int list [], int len, int buffer)
{
    int curr_pos = 0;
    bool found = false;
    while ( curr_pos <= len-1 && found)
    {
        if(buffer < list [curr_pos])
            curr_pos ++;
        else
            found= true;
    }
    return curr_pos;
}
//******************************************************************************************
// shift_right()
// This function makes room for the position you want to enter
//
//******************************************************************************************
void shift_right (int list[], int len, int pos)
{
    for( int i = len; i> pos; i-- )
    {
        list[i]=list[i-1];
    }
   
}


//******************************************************************************************
// merge()
// This function takes two sorted lists and combines them into one 
// sorted list
//******************************************************************************************
       
void merge_function (int listA [], int& lenA, int listB [], int& lenB, int listC [], int& lenC)
{
    int i = 0; // Alle indekser starter med det første element.
    int j = 0;
    int k = 0;
    while (i <= lenA && j<= lenB) // to both lists are empty
    {
     
      if (i > lenA)
        listC[k] = listB[j++];
      else
      {
        if (j > lenB)
          listC[k] = listA[i++];
        else
        {
          if (listA[i] < listB[j])
            listC[k] = listA[i++];
          else
            listC[k] = listB[j++];
        };
      };
      k++;
    }; // end while.
    lenC = lenA + lenB;
}