sort.h

对结构体数据或单向链表快速排序,只为了练习,不是很合理.希望对初学者有点帮助.

#ifndef  CSORT_H
#define  CSORT_H

/***********************************************************************
 * 介    绍: 类 CSort 主要实现对任意结构体数组或简单链表的快速排序
 *
 * 说    明: 创建后调用Initalization()初始化对象时要把参数设好, 否
 *           则不能正常工作, 比较复杂, 要看这个函数的参数说明.在初
 *           始化好对象后调用SetSortKey()来设置排序的具体参数(主关
 *           键字及其他关键字和升降序).最后调用GetSorted()来获取排
 *           序结果, 直接存放在原数组或链表中.
 *
 * 输    出: 排序结果可调用GetSorted()函数, 并返回给数组或链表.
 *
 * 使用说明: 1. 用CSort来定义一个对象实例
 *           2. 调用Initialization()方法, 设置好初始环境
 *           3. 调用SetSortKey()来设置排序的关键字及类型(注意参数)
 *           4. 调用GetSorted()方法进行排序, 结果存放在原数组或链表
 *           5. 调用PrintInfo()可以查看排序的时间及其他信息.
 **********************************************************************/
  
class CSort
{ 
  private:
    //排序空间内存段地址链表结构体
    typedef struct SegmentAddr
    {
      int iIndex;
      void *pSegAddr;
      struct SegmentAddr *pNext;
    }TAddr, *PAddr;
    
    //排序关键字顺序结构体
    typedef struct SKEY
    {
      int iOrder;
      int iUse;
      int iIsChar;
      int iKeyOffset;
      int iKeySize;
      int iSortType;
      struct SKEY *pNext;
    }TKEY;
    
    TKEY KeyOrder[10]; //排序关键字优先选择数组
    
    PAddr pAddr;       //动态内存段的地址链
    int iAddrCnt;      //内存段的个数
    void *pOutHeader;  //外部传入的容器地址
    int iCount;        //排序的元素个数
    int iTypeSize;     //元素结构体大小
    int iNextOffset;   //pNext的偏移地址
    int iNextSize;     //pNext的空间大小
    int iSegmentSize;  //每段内存中能容纳的元素个数
    int iSortContent;  //排序的容器 0 数组, 非0 链表
    double iCostTime;  //排序消耗的时间(单位: 秒  精确到1毫秒)
    
    //排序函数
    void Sorting(int p, int r);
    int  Partition(int p, int r);
    void Reset(void);                        //初始化排序环境
    
    //数据结构体操作函数
    int DoSwap(void *p1, void *p2);
    int DoCopy(void *p1, void *p2);
    int DoComp(char *p1, char *p2);
    long Compare(void *p1, void *p2);        //按关键字数组进行比较
    void* get(int iOffset);                  //取第iOffset个元素的地址
    void* getlink(int iOffset);              //取第iOffset个元素的地址(链表中)
    char* key_str(void *pCur, int iOrder);   //以字符取出关键字
    long* key_int(void *pCur, int iOrder);   //以整型或浮点型取出关键字
    double* key_dbl(void *pCur, int iOrder); //以双精度型取出关键字
    void** getnext(void* pCur);              //从结构体中取pNext的地址
    
    //排序段空间管理函数
    int  ExtendSegment(void);
    void FreeSegment(void);
    void LinkToBuffer(void);
    void BufferToLink(void);
    
  public:
    CSort();
    ~CSort();
    void Initialization(void *const pArray, int iTSize, int iACount);
/************************************************************************  
* 函  数: 初始化函数 Initialization()                                     
* 说  明: 最重要的函数, 排序准备工作, 各个参数要设对, 不同的是最后一      
*         个参数, 如果传的是数组地址则要设定数组元素的个数, 如果传入      
*         的是链表则要把它的pNext地址作为参数传入,这也是唯一区分排序      
*         容器的地方, 只能调用两者其一.                                   
* 参  数: 1. pArray 待排序数组或链表地址                                  
*         2. iTSize 单元元素结构体大小                                    
*         3. iAcount 或 ppNextAddr                                        
*            (1)iAcount 数组元素的个数  传入此参数将在这个数组内排序      
*            (2)ppNextAddr 节点中pNext的地址  传入此参数则动态排序        
***********************************************************************/  
    void Initialization(void *const pArray, int iTSize, void **ppNextAddr);
    
    //获取排序结果
    int GetSorted(void);
    
/************************************************************************  
* 函  数: 参数设置函数 SetSortKey()
* 说  明: 设置排序的关键字及排序方式
* 参  数: 1. iOrder    排序关键字的次序 从0到9 主关键字为0, 不能间断设置
*         2. iSortType 升序 1,  降序 -1
*         3. pArray    待排序数组或链表地址
*         4. pKey      关键字在第一个元素结构体中的地址
*         5. iKeySize  这个关键字的空间大小, 整型和浮点型传入0, 字符型用
*                      sizeof求出, 双精度型传入-1.
*         6. iUse      这个第iOrder个关键字可用1, 不可用0
***********************************************************************/ 
    int SetSortKey(int iOrder, int iSortType, void *const pArray,
                   void *const pKey, int iKSize, int iUse);
    
    //输出排序过程的信息
    void PrintInfo(void);
};

#endif