sort.c

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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#include "sort.h"


/* 排序空间内存段地址链表结构体 */
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毫秒) */

/* 排序函数 */
static void Sorting(int p, int r);
static int  Partition(int p, int r);
static void Reset(void);                        /* 初始化排序环境 */

/* 数据结构体操作函数 */
static int DoSwap(void *p1, void *p2);          /* 交换p1 p2的数据 */
static int DoCopy(void *p1, void *p2);          /* 拷贝函数, p2到p1 */
static int DoComp(char *p1, char *p2);          /* 字符串比较函数 */
static long Compare(void *p1, void *p2);        /* 按关键字数组进行比较 */
static void* get(int iOffset);                  /* 取第iOffset个元素的地址 */
static void* getlink(int iOffset);              /* 取第iOffset个元素的地址(链表中) */
static char* key_str(void *pCur, int iOrder);   /* 以字符取出关键字 */
static long* key_int(void *pCur, int iOrder);   /* 以整型或浮点型取出关键字 */
static double* key_dbl(void *pCur, int iOrder); /* 以双精度型取出关键字 */
static void** getnext(void* pCur);              /* 从结构体中取pNext的地址 */

/* 排序段空间管理函数 */
static int  ExtendSegment(void);
static void FreeSegment(void);
static void LinkToBuffer(void);
static void BufferToLink(void);


void Create()
{
  pOutHeader = NULL;
  pAddr = 0;
  iAddrCnt = 0;
  iTypeSize = 0;
  iNextSize = 0;
  iSegmentSize = 0;
  iNextOffset = 0;
  iCount = 0;
  iSortContent = 0;
  return;
}

void Destroy()
{
  FreeSegment();
  pOutHeader = NULL;
  pAddr = 0;
  iAddrCnt = 0;
  iTypeSize = 0;
  iNextSize = 0;
  iSegmentSize = 0;
  iNextOffset = 0;
  iCount = 0;
  iSortContent = 0;
  
  return;
}

void InitializationArray(void *const pArray, int iTSize, int iACount)
{
  pOutHeader = pArray;      /* 外部数组头地址 */
  iTypeSize = iTSize;       /* 数据元素大小 */
  iCount = iACount;         /* 数组元素总个数 */
  iSegmentSize = 16;        /* 每段内存的元素个数默认为 16 */
  iSortContent = 0;         /* 数组 */
  memset(KeyOrder, 0, sizeof(KeyOrder));
  return;
}

void InitializationLink(void *const pArray, int iTSize, void **ppNextAddr)
{
  pOutHeader = pArray;      /* 外部数组头地址 */
  iTypeSize = iTSize;       /* 数据元素大小 */
  iCount = 0;               /* 数组元素总个数 */
  iNextOffset = (int)((long)ppNextAddr - (long)pArray); /* pNext的偏移地址 */
  iNextSize = sizeof(void*);
  iSegmentSize = 16;        /* 每段内存的元素个数默认为 16 */
  iSortContent = 1;         /* 链表 */
  memset(KeyOrder, 0, sizeof(KeyOrder));
  FreeSegment();
  return;
}

/* 交换成功返回 1, 否则返回 0 */
int DoSwap(void *p1, void *p2)
{
  void *pTemp = (void*)malloc(iTypeSize);
  if(pTemp != NULL)
  {
    memcpy(pTemp, p1, iTypeSize);
    memcpy(p1, p2, iTypeSize);
    memcpy(p2, pTemp, iTypeSize);
    free(pTemp);
    return 1;
  }
  else
  {
    printf("Error: malloc is error\n");
    return 0;
  }
}

int DoCopy(void *p1, void *p2)
{
  memcpy(p1, p2, iTypeSize);
  return 1;
}

int DoComp(char *p1, char *p2)
{
  return strcmp(p1, p2);
}

void* get(int iOffset)
{
  if(iSortContent == 0)
    return (void*)((long)pOutHeader + (long)(iOffset * iTypeSize));
  else
    return getlink(iOffset);
}

char* key_str(void *pCur, int iOrder)
{
  return (char*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

long* key_int(void *pCur, int iOrder)
{
  return (long*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

double* key_dbl(void *pCur, int iOrder)
{
  return (double*)((long)pCur + (KeyOrder + iOrder)->iKeyOffset);
}

void** getnext(void* pCur)
{
  return (void**)((long)pCur + iNextOffset);
}

int GetSorted()
{
  clock_t t1, t2;
  Reset();  /* 初始化排序环境 */
  t1 = clock();
  if(iSortContent == 0)
    Sorting(0, iCount - 1);
  else
  {
    LinkToBuffer();
    Sorting(0, iCount - 1);
    BufferToLink();
  }
  t2 = clock();
  iCostTime = (double)((t2 - t1)/(clock_t)1000); /* 换算成毫秒为单位 */
  return iCount;
}

void Sorting(int p, int r)
{
  int j = 0;

  if(p < r)
  {
    j = Partition(p, r);
    if(j == -1)
    {
      printf("Error: return -1");
      return;
    }
    Sorting(p, j - 1);
    Sorting(j + 1, r);
  }
}

int Partition(int p, int r)
{
  int i = p;
  int j = r + 1;
  void *temp = (void*)malloc(iTypeSize);
  
  if(temp == NULL)
  {
    printf("Error: Partition malloc false\n");
    return -1;
  }
  
  DoCopy(temp, get(p));

  if( p < r)
  {
    while(1)
    {
      while(Compare(get(++i), temp) < 0 && i <= r);
      while(Compare(get(--j), temp) > 0 && j >= p);
      
      if(i >= j) break;
      DoSwap(get(i), get(j));
    }
    DoCopy(get(p), get(j));
    DoCopy(get(j), temp);
  }
  free(temp);
  /*printf("--location--a[%d]=\n", j);*/

  return j;
}

void Reset()
{
  FreeSegment();
  pAddr = 0;
  iAddrCnt = 0;
  if(iSortContent != 0)
    iCount = 0;
}

/************************************************************************  
 * 函  数: 初始化函数 Compare()
 * 说  明: 根据关键字数组中的方式来比较p1和p2的大小, 返回比较结果(p1 - p2)
 *         保证排序关键字数组KeyOrder[]的设置正确.
 * 参  数: 两个待比较结构体头指针
 * 返  回: > 0   升序 p1 > p2    降序 p1 < p2
 *         = 0   p1 == p2
 *         < 0   升序 p1 < p2    降序 p1 > p2
 ***********************************************************************/
long Compare(void *p1, void *p2)
{
  int i = 0;
  long lRet = 0;
  double db = 0.0;
  while(1)
  {
    /* 在以后分支情况中只要不满足条件就用break跳出, 返回 lResult = 0 */
    if((KeyOrder + i)->iUse == 1)
    {
      if((KeyOrder + i)->iIsChar > 0)
      { /* 字符型 */
        lRet = DoComp(key_str(p1, i), key_str(p2, i)) * (KeyOrder + i)->iSortType;
        if(lRet == 0)
          i++;
        else
          break;
      }
      else if((KeyOrder + i)->iIsChar == 0)
      { /* 整型或浮点型 */
        lRet = (*(key_int(p1, i)) - *(key_int(p2, i))) * (KeyOrder + i)->iSortType;
        if(lRet == 0)
          i++;
        else
          break;
      }
      else
      { /* 双精度型 */
        db = (*(key_dbl(p1, i)) - *(key_dbl(p2, i))) * (KeyOrder + i)->iSortType;
        if(db == 0.0)
          i++;
        else
        {
          if(db > 0)
            lRet = 1;
          else
            lRet = -1;
          break;
        }
      }
    }
    else
      break;
  }
  return lRet;
}

int SetSortKey(int iOrder, int iSortType, void *const pArray,
               void *const pKey, int iKSize, int iUse)
{
  KeyOrder[iOrder].iKeyOffset = (int)((long)pKey - (long)pArray);
  KeyOrder[iOrder].iKeySize = iKSize;
  if(iKSize == 0)
    KeyOrder[iOrder].iIsChar = 0;  /* 整型或浮点型 */
  else if(iKSize > 0)
    KeyOrder[iOrder].iIsChar = 1;  /* 字符型 */
  else
    KeyOrder[iOrder].iIsChar = -1; /* 双精度型 */
  KeyOrder[iOrder].iUse = iUse;
  KeyOrder[iOrder].iSortType = iSortType;
  return iOrder;
}

int ExtendSegment(void)
{
  void *p = NULL;
  PAddr pTemp = NULL;
  pTemp = (PAddr)malloc((iAddrCnt + 1) * sizeof(TAddr));
  if(pTemp != NULL)
  {
    if(pAddr != NULL)
    {
      memcpy(pTemp, pAddr, iAddrCnt * sizeof(TAddr));
      free(pAddr);
    }
    pAddr = pTemp;
    pTemp = NULL;
    p = (void*)malloc(iSegmentSize * iTypeSize);
    if(p != NULL)
      pAddr[iAddrCnt].pSegAddr = p;
    else
    {
      printf("Error: malloc is false in ExtendSegment\n");
      exit(1);
    }
    iAddrCnt++;
    return 0;
  }
  else
  {
    printf("Error: malloc is false in ExtendSegment\n");
    exit(1);
  }
}

void FreeSegment(void)
{
  int i = 0;
  for(i = 0; i < iAddrCnt; i++)
    free(pAddr[i].pSegAddr);
  
  free(pAddr);
  return;
}

void* getlink(int iOffset)
{
  int iAddr, iIndex;
  iAddr = (int)(iOffset / iSegmentSize);
  iIndex = (int)(iOffset % iSegmentSize);
  return (void*)((long)(pAddr[iAddr].pSegAddr) + iIndex * iTypeSize);
}

void LinkToBuffer()
{
  void *pPre = NULL;
  void *pCur = pOutHeader;
  void **ppTemp = NULL;
  
  if(pCur == NULL)
    return;
  
  /* 第一个元素特殊处理, 不释放, 返回时保持一样 */
  if(iCount >= iSegmentSize * iAddrCnt)
  {
    ExtendSegment();
  }
  
  memcpy(getlink(iCount), pCur, iTypeSize);
  pPre = pCur;
  
  while(1)
  {
    iCount++;
	  pCur = *getnext(pCur);
	  
    if(iCount >= iSegmentSize * iAddrCnt)
      ExtendSegment();
    
    if(pCur == NULL)
      break;
    
    memcpy(getlink(iCount), pCur, iTypeSize);
    pPre = pCur;
  }
  return;
}

void BufferToLink()
{
  int i = 0;
  void* pCur = pOutHeader;

  if(iCount <= 0)
    return;
  
  for(i = 0; i < iCount; i++)
  {
    /* 先把pNext赋给动态值 */
    memcpy(getnext(getlink(i)), getnext(pCur), iNextSize);
    memcpy(pCur, getlink(i), (iTypeSize));
    pCur = *getnext(pCur);
  }
  return;
}

void PrintInfo(void)
{
  int i = 0;
  char type[10] = "ASC";
  char content[10] = "Array";
  
  if(iSortContent != 0)
    sprintf(content, "Link");
  printf("The Private Information\n");
  printf("*******************************************\n");
  printf("* count of unit                : %d\n", iCount);
  printf("* count of segment             : %d\n", iAddrCnt);
  printf("* size of segment              : %d\n", iSegmentSize);
  printf("* address from outer           : 0x%x\n", pOutHeader);
  printf("* address of segment's header  : 0x%x\n", pAddr);
  while(KeyOrder[i].iUse !=0)
  {
    if(KeyOrder[i].iSortType > 0)
      sprintf(type, "ASC");
    else
      sprintf(type, "DESC");
    i++;
    printf("* Key[%d]'s sort type           : %s\n", i, type);
  }
  printf("* sort conetent(array or link) : %s\n", content);
  printf("* cost time (s)                : %0.02fs\n", iCostTime/1000);
  printf("*******************************************\n");
}

void InitObject(CSort * obj)
{
  obj->Create = Create;
  obj->Destroy = Destroy;
  obj->InitializationArray = InitializationArray;
  obj->InitializationLink = InitializationLink;
  obj->GetSorted = GetSorted;
  obj->SetSortKey = SetSortKey;
  obj->PrintInfo = PrintInfo;
  Create();
  return;
}