在基於數組的列表上實現選擇排序

Question

我的問題是我做錯了什麼。插入功能無法正常工作。我無法檢索列表本身。因爲這個我的選擇排序不會執行。任何幫助，將不勝感激。

頁眉：

/** @file ListA.h */ 
#include <string> 
using namespace std; 
const int MAX_LIST = 100; 
typedef string ListItemType; 
class List 
{ 

public: 
    List(); 
    bool isEmpty() const; 
    int getLength() const; 
    void insert(int index, const ListItemType& newItem, bool& success); 
    void retrieve(int index, ListItemType& dataItem, bool & success) const; 
    void remove(int index, bool& success); 
    int selectionSortArray(int numdata[], int xnums); 
    List selectionSort(List selectList); 
private: 
    ListItemType items[100]; 
    int size; 
    int translate(int index) const; 
}; 

CPP：

/** @file ListA.cpp */ 
#include "ArrayList.h" // header file 
#include <iostream> 
#include <fstream> 
List::List() : size() 
{ 
} 
bool List::isEmpty() const 
{ 
    return size == 0; 
} 
int List::getLength() const 
{ 
    return size; 
} 
void List::insert(int index, const ListItemType& newItem, bool& success) 
{ 
    success = (index >= 1) && 
      (index <= size + 1) && 
      (size < MAX_LIST); 
    if (success) 
    { 
     for (int pos = size; pos >= index; --pos) 

     items[translate(pos + 1)] = items[translate(pos)]; 
     items[translate(index)] = newItem; 

     ++size; 

    } 

} 
void List::remove(int index, bool& success) 
{ 
    success = (index >= 1) && (index <= size); 
    if (success) 
    { 
     for (int fromPosition = index + 1; 
     fromPosition <= size; 
     ++fromPosition) 
     items[translate(fromPosition - 1)] = items[translate(fromPosition)]; 
     --size; // decrease the size of the list by one 
    } // end if 

} // end remove 

void List::retrieve(int index, ListItemType& dataItem, 
bool& success) const 
{ 
    success = (index >= 1) && (index <= size); 
    if (success) 
     dataItem = items[translate(index)]; 
} 

int List::translate(int index) const 
{ 
    return index - 1; 
} 

//List List::selectionSort(List selectList) 

//{ 


//return selectList; 


int List::selectionSortArray(int numdata[], int xnums) 
{ 
int tmp; 
for (int i = 0; i < xnums -1; i++) 
     for (int j = i+1; j < xnums; j++) 
      if (numdata[i] > numdata[j]) 
      { 
       tmp = numdata[i]; 
       numdata[i] = numdata[j]; 
       numdata[j] = tmp; 
      } 
    //for(int i = 0; i < 5; i++) 
     //cout << numdata[i] << " "; 
     return *numdata; 
} 

int main() 
{ 
ListItemType insertType = "listItem1"; 
ListItemType retrieveType = "listitem2"; 
int numberofitems; 
cout << "Please enter the number of data items:" << endl; 
cin >> numberofitems; 
cout << endl; 
cout << "Please enter the data items, one per line:" << endl; 
int listofitems[numberofitems]; 
List myArrayList; 
cout << myArrayList.getLength() << endl; 
     if (myArrayList.isEmpty()) // tests before 
    { 
     cout << "This list is empty \n" << endl; 
    } 
    else 
    { 
     cout << "List is not empty! \n"<< endl; 
    } 
bool mainsucc = true; 
for (int i = 0; i<numberofitems; i++) 
{ 
cout << "Enter number " << i+1 << " : " << endl; 
cin >> listofitems[i]; 
} 
for (int i =0; i <numberofitems; i++){ 
myArrayList.insert(listofitems[i], insertType, mainsucc);} 
cout << "Size of the list is : " << myArrayList.getLength() << endl; 
int listRetrieveSize = myArrayList.getLength(); 
int listRetrieve[listRetrieveSize]; 
for (int j=0; j<listRetrieveSize; j++) 
{ 
myArrayList.retrieve(listofitems[j], retrieveType, mainsucc); 
} 
if (myArrayList.isEmpty()) // tests after 
    { 
     cout << "This list is empty \n" << endl; 
    } 
    else 
    { 
     cout << "List is not empty! \n"<< endl; 
    } 
numberofitems= myArrayList.selectionSortArray(listofitems, numberofitems); 
for (int i=0;i>numberofitems;i++) 
{ 
cout<<listofitems[i]; 
} 
return 1; 
} 

Answer 1

您的選擇排序是絕對錯誤：

int List::selectionSortArray(int numdata[], int xnums) 
{ 
    int tmp; 
    for (int i = 0; i < xnums -1; i++) { 
     //you should find the smallest integer inside this for loop 
     for (int j = i+1; j < xnums; j++) { 
      if (numdata[i] > numdata[j]) 
      { 
       //why do you swap inside this for loop? 
       tmp = numdata[i]; 
       numdata[i] = numdata[j]; 
       numdata[j] = tmp; 
      } 
     }//missing closing } 
     //smap numdata[i] with currently smallest int 

    }//missing closing } 
    return *numdata; 
} 

用繩子你插入功能的交易，但你是那種做選擇整數。

typedef string ListItemType; 

定義string爲ListItemType。

Answer 2

我很確定你實施的是Bubble sort algorithm而不是selection sort algorithm。