数据结构快速排序和堆排序

Question

从一文件中读取待排数字，利用快速排序（或者堆排序）把数字大于某个值的所有元素排出，并把排序结果和比较次数等信息写入到输出文件中去，要求具有较好的变量命名和较好人机交互处理过程 C语言

Answer 1

#include <stdio.h> 
#include <stdlib.h>
#include <string>
 
 
//下面的方法提前声明
char* openFileOnlyRead(char * fileName);
int Partion(int list[], int low, int high);
void QSort(int list[], int low, int high);
void QuickSort(int list[], int n);
void transformCharArrayToIntArray(char * pChar);
void writeQuickSortResult(char *pResult);
 
//全局变量的声明
char *m_pCharBuf = NULL;
int m_nList[100];
int m_nCount = 0;
 
//主程序
int main(void)
{
    //文件内容读取出来
    char *pText = openFileOnlyRead("resource.txt");
    printf("%s\n\n", pText);
 
    //读出的数据转换为数组，方便下一步进行排序
    transformCharArrayToIntArray(pText);
 
    //对数组进行排序
    QuickSort(m_nList, m_nCount - 1);
 
    //将结果写入到result中
    char result[1000] = { "QuickSortResult:" };
    for (int i = 0; i < m_nCount; ++i)
    {
        printf("%d ", m_nList[i]);
        char number[100] = {};
        _itoa(m_nList[i], number, 10);
        strcat(result, " ");
        strcat(result, number);
    }
 
    //将结果写出到文件：QuickSortResult.txt
    writeQuickSortResult(result);
 
	getchar();
    free(m_pCharBuf);
	return 0;
}
 
//读取文件的内容
char* openFileOnlyRead(char * fileName)
{
    
    int  nLen = 0;
    FILE *pFile = fopen(fileName, "r");      //打开文件
 
    fseek(pFile, 0, SEEK_END);     //文件指针移到文件尾
    nLen = ftell(pFile);           //得到当前指针位置, 即是文件的长度
    rewind(pFile);                 //文件指针恢复到文件头位置
 
    //动态申请空间, 为保存字符串结尾标志\0, 多申请一个字符的空间
    m_pCharBuf = (char*)malloc(sizeof(char)* nLen + 1);
 
    if (!m_pCharBuf)
    {
        perror("内存不够!\n");
        exit(0);
    }
 
    //读取文件内容//读取的长度和源文件长度有可能有出入，这里自动调整 nLen
    nLen = fread(m_pCharBuf, sizeof(char), nLen, pFile);
 
    m_pCharBuf[nLen] = '\0'; //添加字符串结尾标志
    
    //printf("%s\n", pchBuf); //把读取的内容输出到屏幕
 
    fclose(pFile);  //关闭文件
    //free(pchBuf); //释放空间
 
    return m_pCharBuf;
}
 
//写入排序完成后的结果
void writeQuickSortResult(char *pResult)
{
    FILE *pFile = fopen("QuickSortResult.txt", "w");    //打开文件
    fputs(pResult, pFile);      //写入数据
    fclose(pFile);              //关闭文件
}
 
//快速排序的一次过程
int Partion(int list[], int low, int high)
{
    int prvotkey = list[low];
    int nChange = 0;
    while (low < high)
    {
        while (low < high && list[high] >= prvotkey)
            --high;
        nChange = list[low];
        list[low] = list[high];
        list[high] = nChange;
 
        while (low < high && list[low] <= prvotkey)
            ++low;
        nChange = list[low];
        list[low] = list[high];
        list[high] = nChange;
    }
 
    return low;
}
 
//快速排序——迭代方法
void QSort(int list[], int low, int high)
{
    int prvotloc;
    if (low < high)
    {
        prvotloc = Partion(list, low, high);    //将第一次排序的结果作为枢轴
        QSort(list, low, prvotloc - 1);         //递归调用排序 由low 到prvotloc-1
        QSort(list, prvotloc + 1, high);        //递归调用排序 由 prvotloc+1到 high
 
    }
}
 
//快速排序
void QuickSort(int list[], int n)
{
    QSort(list, 0, n);  //第一个作为枢轴 ，从第一个排到第n个
}
 
//将char * 数据转换为整型数组
void transformCharArrayToIntArray(char * pChar)
{
    int j = 0;
    int nNum = 0;
    for (int i = 0; ; ++i)
    {
        //找到空格，将后面的数字取出，添加到整型数组中
        if (' ' == pChar[i] && ' ' != pChar[i + 1])
        {
            char pSub[200] = {};
            strncpy(pSub, pChar + j, i);
            j = i;
            nNum = atoi(pSub);
            m_nList[m_nCount] = nNum;
            ++m_nCount;
        }
 
        //将最后一个数字取出，添加到整型数组中
        if ('\0' == pChar[i])
        {
            char pSub[200] = {};
            strncpy(pSub, pChar + j, i);
            j = i;
            nNum = atoi(pSub);
            m_nList[m_nCount] = nNum;
            ++m_nCount;
            break;
        }
    }
}