selecttm.cpp

这时清华大学数据结构课程的源代码

#ifndef SELECTTM_H     
#define SELECTTM_H
#include "datalist.cpp"

template <class Type> void dataList <Type>::Swap (const int mark1, const int mark2) {
    Type temp = Element[mark1];
    Element [mark1] = Element [mark2];
    Element [mark2] = temp;
}

template <class Type>
int dataList<Type>::MaxKey (const int low, const int high) {
 //查找数组Element[low]～Element[high]中的
 //最大值，函数返回其位置
      int max = low;	
     for (int k=low+1;k<=high;k++)
  	 if (Element[max]<Element[k]) 
  	      max = k;				
      return max;
 }


//template <class Type> ostream& operator << (ostream& outStream, const dataList<Type> outList) {
    //outStream << "Array Contents:\n" ;
    //for (int i = 0; i < OutList.ArraySize ; i++)
    //outStream << outList.Element[i] << ' ' ;
    //outStream << endl;
    //outStream << "Array Current Size:" << outList.ArraySize << endl;
    //return outStream;
//}

template<class Type> 
void dataList<Type>::show(){
	for (int i = 0; i < ArraySize ; i++){
		cout<<Element[i]<<' ';
		cout<<endl;
	}
}

//template <class Type> istream& operator >> (istream& inStream,dataList<Type> inList) {
    //cout << "Enter array Current Size:";
    //inStream >> inList.ArraySize;
    //cout << "Enter array elements:\n";
    //for (int i=0; i<inList.ArraySize; i++) {
	//cout << "Element" << i << ":" ;
	//inStream >> inList.Element[i];
    //}
    //return inStream;
//}

template <class Type>
void dataList<Type>::add(){
	cin>>ArraySize;
	for (int i=0; i<ArraySize; i++) {
		cin>>Element[i];
	}
}

template <class Type> void dataList <Type>::Sort() {
    for (int i = ArraySize - 1; i > 0; i-- ) {
	int j = MaxKey ( 0, i );
	if ( j != i ) Swap ( j, i );
    }
}

template<class Type>
void dataList<Type>::bubbleSort(){
	   int i = 1;  int exchange = 1;		
 	 //当exchange为0则停止排序
       while ( i < ArraySize && exchange ) { 
           BubbleExchange (i, exchange );
           i++;
      } 	//一趟比较

}

template<class Type>
void dataList<Type>::BubbleExchange(const int i, int & exchange ){
     exchange = 0;	           //假定元素未交换
     for ( int j = ArraySize-1; j>=i; j--)
          if ( Element[j-1] > Element[j] ) {	
	   Swap ( j -1, j );	 //发生逆序
		//交换Element[j-1]与Element[j]
             exchange = 1;	//做“发生了交换”标志
          }
 }   
#endif