/*qksort 快速排序函数*/
int qksort(void *data, int size, int esize, int i, int k, int(*compare)(const void *key1, const void *key2))
{
int j;
/*递归地继续分区,直到不能进一步分区*/
while(i < k)
{
/*决定从何处开始分区*/
if((j = partition(data,esize,i,k,compare))<0)
return -1;
/*递归排序左半部分*/
if(qksort(data,size,esize,i,j,compare) < 0)
return -1;
/*递归排序右半部分*/
i=j+1;
}
return 0;
}
在一个层次结构的文件系统中,文件通常分目录进行组织。在任何一个目录中,我们会看到此目录包含的文件列表和子目录。例如,在UNIX系统中,可以通过命令ls来显示目录。在windows的命令行中,通过dir来显示目录。
本节展示一个函数directls,它能实现与ls同样的功能。它调用系统函数readdir来创建path路径中指定的目录列表。directls默认将文件按照名字排序,这一点与ls一样。由于在建立列表时调用了realloc来分配空间,因此一旦不再使用列表时,也需要用free来释放空间。
directls的时间复杂度为O(nlgn),其中n为目录中要列举的条目数。这是因为调用qksort来对条目进行排序是一个O(nlgn)级的操作,所以总的来说,遍历n个目录条目是一个O(n)级别的操作。
示例:获取目录列表的头文件
/*directls.h*/
#ifndef DIRECTLS_H
#define DIRECTLS_H
#include <dirent.h>
/*为目录列表创建一个数据结构*/
typedef struct Directory_
{
char name[MAXNAMLEN+1];
}Directory;
/*函数接口定义*/
int directls(const char *path,Directory **dir);
#endif // DIRECTLS_H
示例:获取目录列表的实现
/*directls.c*/
#include <dirent.h> /*是POSIX.1标准定义的unix类目录操作的头文件,包含了许多UNIX系统服务的函数原型,例如opendir函数、readdir函数. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "directls.h"
#include "sort.h"
/*compare_dir 目录比较*/
static int compare_dir(const void *key1,const void key2)
{
int retval;
if((retval = strcmp(((const Directort *)key1)->name,((const Directory *)key2)->name))>0)
return 1;
else if (retval < 0)
return -1;
else
return 0;
}