请注意，这不是家庭作业：我正在尝试实现以下功能并理解这一切。这些代码是从我的教科书中复制并放在一起的。还有其他 .h 和 .cpp 文件，这些函数将协同工作以产生输出。我的问题是：我的实现在逻辑上是否正确？尽管我直接从书中复制了所有内容，但无法编译。main.cpp 和 list.h & 就是这样从书中获取的，我自己在这里的工作是尝试实现排序功能。它无法编译所需的内容？建议？想法，批评者？谢谢你
#ifndef SORTLIST_H
#define SORTLIST_H
#include "LIST.H"
#include "KEY.H"
#include "RECORD.H"
template <class Record>
class Sortable_list: public List<Record> {
public:
void insertion_sort(ItemType theArray[], int n) // todo: implement insertion sort
{
for (int unsorted = 1; unsorted < n; unsorted++)
{
ItemType nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc> 0)&& (theArray[loc - 1] > nextItem))
{
theArray[loc] = theArray[loc - 1];
}
theArray[loc] = nextItem;
loc--;
}
}
void selection_sort(ItemType the Arrray[], int n) // todo: implement selection sort
{
for(int last = n-1; last >1; last--)
{
int largest = findIndexofLargest(theArray, last+1);
std::swap(theArray[largest], theArray[last]);
}
}
int findIndexofLargest(const ItemType theArray[], int size)
{
int indexSoFar = 0 ; //index of largest entry found so far
for (int currentIndex = 1; currentIndex <size; currentIndex++)
{
if (theArray[currentIndex] > theArray[indexSoFar])
indexSoFar = currentIndex;
}
return indexSoFar;
}
void quick_sort(ItemType the Array [], int first, int last) // todo; implement quick sort
{
if(last - first + 1 <MAX_LIST)
{
insertionSort(theArray, first, last);
}
else
{
//create subarray s1 & s2
int pivotIndex = partition(theArray, first, last);
//sort subarrays s1 & s2
quick_sort(theArray, first, pivotIndex - 1);
quick_sort(theArray, pivotIndex + 1, last);
}
}
void bubble_sort(ItemType theArray[], int n) // todo; implement bubble sort
{
bool sorted = false; //false when swap occur
int pass = 1;
while (!sorted && (pass < n))
{
sorted = true; //assume sorted
for (int index = 0; index < n - pass; index++)
{
int nextIndex = index + 1;
if (theArray[index] > theArray[nextIndex])
{
//exchange entry
std::swap(theArray[index], theArray[nextIndex]);
sorted = false;
}
}
pass++;
}
}
void merge(ItemType theArray[], int first, int mid, int last) // starting merge sort
{
ItemType tempArray[MAX_LIST]; //temporary array
int first1= first;
int last1 = mid;
int first2 = mid+1;
int last2 = last;
int index = first1; // next available in tempArray
while ((first1 <= last1) && (first2 <= last2))
{
if (theArray[first1] <= theArray[first2])
{
tempArray[index] = theArray[first1]);
first1++;
}
else
{
tempArray[index] = theArray[first2];
first2++;
}
index++;
}
while (first1 <= last1) // finish the first subarray if necessary
{
tempArray[index] = theArray[first1;
first++;
index++;
}
//finish the second subArray
while (first2 <= last2)
{
tempArray[index] = theArray[first2];
first2++;
index++;
}
for (index = first; index <= last; index++)
theArray[index] = tempArray[index];
}
void merge_sort(ItemType theArray[], int first, int last) // todo; implement merge sort
{
if (first < last)
{
//sort each half
int mid = first + (last - first) / 2; //index of midpoint
// sort left half
merge_sort(theArray, first, mid);
//sort right half
merge_sort(theArray, mid + 1, last);
//merge the two halves
merge_sort(theArray, first, mid, last);
}
}
private:
// add private member functions if needed
};
#endif
//Main.cpp is the test driver to test the Sortlist class.
//It contains user interface, filling the list with random integers,
//calling Sortlist sorting functions and calculate the CPU time,
//the number of comparison of keys, and the number of assignments of
//list entries during the sorting list.
#include "stdafx.h"
#include "RANDOM.H"
#include "TIMER.H"
#include "SORTLIST.H" // SORTABLE LIST SPECIFICATION
#include <iostream>
using namespace std;
void write_entry(Record &c)
{
cout << ((Key) c).the_key() << " ";
}
void help()
{
cout << "User options are:\n"
<< "[H]elp [Q]uit (re)[F]ill list \n"
<< "write [D]ata write sorted [O]utput \n"
<< "[0] insertion sort \n"
<< "[1] selection sort \n"
<< "[2] shell sort \n"
<< "[3] quick sort\n"
<< "[4] heap sort\n"
<< "[5] bubble sort \n"
<< "[6] merge sort \n"
<< endl;
}
void intro()
{
cout << "Testing program for sorting methods for a contiguous list."
<< endl;
help ();
}
void main()
{
List<Record> s; List<Record> t = s; // help out an old compiler
intro();
int n;
Random dice;
bool report;
Record target;
Sortable_list<Record> the_list;
Sortable_list<Record> copy_list;
char command = ' ';
while (command != 'q' && command != 'Q') {
cout << "Enter a command of H, Q, F, O, D, "
<< "0, 1, 2, 3, 4, 5, 6: "
<< flush;
cin >> command;
switch (command) {
case 'h': case 'H':
help();
break;
case 'd': case 'D':
cout << "\nUnsorted list \n";
the_list.traverse(write_entry);
cout << endl;
break;
case 'o': case 'O':
cout << "\nLast sorted list \n";
copy_list.traverse(write_entry);
cout << endl;
break;
case '0': case '1': case '2': case '3': case '4': case '5': case '6':
{
copy_list = the_list;
Key::comparisons = 0;
Key::assignments = 0;
Timer clock;
switch (command) {
case '0':
cout << "Insertion Sort ";
copy_list.insertion_sort();
break;
case '1':
cout << "Selection Sort ";
copy_list.selection_sort();
break;
case '2':
cout << " Shell Sort ";
copy_list.shell_sort();
break;
case '3':
cout << " Quick Sort ";
copy_list.quick_sort();
break;
case '4':
cout << " Heap Sort ";
copy_list.heap_sort();
break;
case '5':
cout << " Bubble Sort ";
copy_list.bubble_sort();
break;
case '6':
cout << " Merge Sort ";
copy_list.merge_sort();
break;
}
cout << "Time: " << clock.elapsed_time() << " seconds.\n"
<< "Comparisons: " << Key::comparisons << "\n"
<< "Assignments: " << Key::assignments
<< endl <<endl;
}
break;
case 'f': case 'F':
the_list.clear();
cout << "How many list entries would you like? "
<< flush;
cin >> n;
for (int i = 0; i < n; i++) {
target = dice.random_integer(0, 10 * n);
the_list.insert(i, target, report);
if (report == false) {
cout << "Available list space filled up at " << i
<< " entries." << endl;
break;
}
if (report != true) i--;
}
break;
} // end of outer switch statement
} // end of outer while statement
}
这是 List.h 是 List 类的基于模板的基于数组的实现
const int MAX_LIST=10000;
template <class T>
class List
{
public:
List(); //default constructor. Create an empty list.
bool isEmpty() const; // test if the list is empty
bool isFull() const; // test if the list is full
int getLength() const; // get the length of the list
void insert(int index, const T& newItem, bool& success);
//Insert the newItem into the list at position index. NOTE: 0<=index<=getlength()
void remove(int index, bool& success);
//Remove an item from the list at position index. NOTE: 0<=index<=getlength()
void retrieve(int index, T& dataItem, bool& success) const;
// Retrieve a list item by position index. NOTE: 0<=index<=getlength()
void traverse (void(*visit)(T &));
//Traverse all items in the list from the beginning to the end
void clear(); // Remove all items from the list.
protected:
T items[MAX_LIST];
int size; // number of items in the list
};
template <class T>
List<T>::List()
{
size=0;
}
template <class T>
bool List<T>::isEmpty() const
{
return (size==0);
}
template <class T>
bool List<T>::isFull() const
{
return (size >= MAX_LIST);
}
template <class T>
int List<T>::getLength() const
{
return size;
}
template <class T>
void List<T>::clear()
{
size=0;
}