abellong's Blog

c 语言的标准库有一个函数实现了快速排序----qsort().

man 3 qsort

看看 qsort 函数原型

void qsort(void *base, size_t nmemb, size_t size,
                  int(*compar)(const void *, const void *));

base 指向要排序的数组. 长度为 nmemb, 每个元素的大小是 size. compar 是比较函数, 如果第一个参数"小于"("等于", "大于")第二个参数, 那么比较函数返回一个负整数(0, 正整数). 数组按升序排序, 改变"小于"的定义就可以按需要的顺序排序了. 下面是 man page 里的一个程序例子, 这个程序将它的参数进行排序

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

static int
cmpstringp(const void *p1, const void *p2)
{
  /* The actual arguments to this function are "pointers to
     pointers to char", but strcmp(3) arguments are "pointers
     to char", hence the following cast plus dereference */

  return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int
main(int argc, char *argv[])
{
  int j;

  if (argc < 2) {
    fprintf(stderr, "Usage: %s <string>...\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  qsort(&argv[1], argc - 1, sizeof(argv[1]), cmpstringp);

  for (j = 1; j < argc; j++)
    puts(argv[j]);
  exit(EXIT_SUCCESS);
}

关键句

  qsort(&argv[1], argc - 1, sizeof(argv[1]), cmpstringp);

由于 qsort 函数第四个参数类型要求, 不能直接使用 strcmp 函数, 改写的 cmpstringp 函数的类型是:

int(*)(const void *, const void *)

这就符合要求了. qsort 的调用和函数 cmpstringp 的写法有些让人难懂.

我的理解:

&argv[1] 的类型为 char *, 作为实参传给 qsort 函数自动转变为 void * 型指针, 这样在 qsort 函数内部并不知道数组的类型(仅仅知道是void型数组), 因此需要一个参数 size 来标明数组元素的大小.

  return strcmp(* (char * const *) p1, * (char * const *) p2);

中的 *  (char * const *) p1 应该这么理解: 首先将 p1 转变成 (char * const  *) 型指针, 然后在作 * 运算, p1 is a pointer to a const pointer to char. 好费解!  *p1 是指向一个 (char * const) 数据, 即 (const char *)数据, 即常字符串. 关于const 的理解可以用"倒读"的方法, 见 const int vs. int const as function parameter in C++ and C 上 Ates Goral 的回答.

qsort 还能怎么用, 看看一个浮点数数组的排序该怎么写, 只需要改变比较函数就可以了

#define eps 0.000001
int numcmp(const void *x,const void *y){  // 排序比较函数
  float z=*((double*)x)-*((double*)y);
  if(z>eps) return 1;
  if(z<-eps)	return -1;
  return 0;
}

要排序的数组为 price, 如此调用即可:

float price[10] = {32.0, 12, 8, 45.1,
                         13, 30, 53.2, 34.1, 80, 22}
qsort(price, 10, sizeof(float), numcmp);

原先装有 ubuntu 10.04 和 windows 7 双系统. windows 7 几乎没用, 占用空间. ubuntu整个安装在一个逻辑分区上, 分割很不合理, 到现在没有多余的空间可用, 有些空间又动不得. ubuntu 系统感觉越来越丑, 有许多问题, 不想再折腾配置了, 一到重装所有的软件全部没了. 还是早些换掉系统吧.

本想换个 archlinux 或 gentoo 玩玩, 这个安装可能就需要很多时间, 要熟悉它又要很久. 现在 ubuntu (的包管理)都没学好, 换来换去意义不大. 可喜的是, 在寒假装了 LFS, 完全从源代码编译的小系统. 这个用来学习 linux 再好不过了. 当初十分英明的将LFS安装在一个10G的主分区上, 重装系统可以保留它.

这次重装系统, 分区是这样的:

• /boot   /dev/sda1    ---100M
• /home  /dev/sda2   ---120G
• LFS       /dev/sda3   ---10G
• /             /dev/sda5 ---40G
• swap                       ---2.5G

总共用去了100多G, 还剩下120G 可用于扩展.

安装过程相当顺利, 装好重启, 在进入系统时还是出现花屏, 连ubuntu字样都没出现, 有些失望, 之前的系统也出现花屏让我不爽. 试了两次, 换了专有显卡驱动后好多了.

熟悉熟悉Unity 的界面, 便不想换成 awesome 窗口管理器了, 我在 awesome(现在看来比较丑) 上积累的一些经验怕是又浪费了. 给firefox安装了Pentadactyl插件. 遇到了一个问题, 有时 hint-mode 出现问题, 折腾很久才知道是和 ibus 不完全兼容, 没想去 hack 找原因, 还是用小企鹅输入法. 配置好快捷键, 中英文切换切换有问题, 已经设定为shift键, 按了没用, 一阵折腾发现竟要连续摁两次shift键才能切换. 

安装好了emacs, vim, zim 等软件. 我发现 ubuntu 11.10 最有趣的是软件中心. 界面相当漂亮, 每个软件有详细的介绍, 一些插件附件可选安装, 还可以评论评分, 另一个很酷的功能是, 它有详细的软件安装卸载的历史记录, 按时间顺序列出, 让你清楚地知道对系统干了什么事.