以下来自qsort函数实现,作为K&R挑战问题之一的解决方案。挑战是阅读单词列表并根据出现次数对它们进行排序。还显示了结构Word。链接到完整代码:http://clc-wiki.net/wiki/K%26R2_solutions:Chapter_6:Exercise_4
typedef struct WORD
{
char *Word;
size_t Count;
struct WORD *Left;
struct WORD *Right;
} WORD;
...
CompareCounts(const void *vWord1, const void *vWord2)
{
int Result = 0;
WORD * const *Word1 = vWord1;
WORD * const *Word2 = vWord2;
assert(NULL != vWord1);
assert(NULL != vWord2);
/* ensure the result is either 1, 0 or -1 */
if((*Word1)->Count < (*Word2)->Count)
{
Result = 1;
}
else if((*Word1)->Count > (*Word2)->Count)
{
Result = -1;
}
else
{
Result = 0;
}
return Result;
}
我的问题是关于这些方面:
WORD * const *Word1 = vWord1;
WORD * const *Word2 = vWord2;
这是一个指向常量变量的常量指针的声明吗?或者是其他东西?为什么必须以这种方式定义才能使排序工作?
您链接到的源代码是一个小应用程序,它读取文本样本,生成包含单词频率的树数据结构(每个单词出现在文本样本中的次数),然后打印出最频繁的单词列表至少频繁。
/*
Chapter 6. Structures
Write a program that prints out the distinct words in its
input sorted into decreasing order of frequency of occurrence.
Precede each word by its count.
Author: Bryan Williams
*/
该应用中使用的图案具有经典而优雅的K&R感觉。第一步是处理生成树结构的文本样本,其中每个节点包含一段文本(来自文本样本的单词)以及找到该段文本的次数的频率计数。第二步是按频率计数对树节点进行排序。第三步是按频率顺序打印排序的树节点,以提供找到的文本块列表以及在文本样本中找到文本块的次数。
使用的树是binary tree,树节点具有以下结构:
typedef struct WORD
{
char *Word; // pointer to the text piece, a word of text
size_t Count; // frequency count for this word
struct WORD *Left; // pointer to tree node child left
struct WORD *Right; // pointer to tree node child right
} WORD;
使用树结构是为了有效地确定是否已经找到文本块并且仅增加计数或者将具有计数的文本块添加到我们的数据存储中(如果不是)。
但是,排序步骤对树中项目的顺序使用与处理文本样本不同的标准。文本示例使用文本块作为命令树节点的方式,但对于实际输出,我们需要基于频率计数的订单。所以我们需要在频率计数上对树的节点进行排序。
由于这是一个内存树,该程序的第一个想法是创建一个数组中的树节点列表,然后对列表进行排序。但是,排序数组通常需要移动数组元素,除了已经排序的数组的特殊情况。由于正在制作节点的副本,因此该方法还将使用于树节点的内存量加倍。
而不是制作树节点的副本然后对该列表进行排序,而是程序创建指向树节点的指针列表,然后通过引用指针指向的树节点来对指针列表进行排序。
关于qsort()
界面的一点点
CompareCounts(const void *vWord1, const void *vWord2)
的函数定义意味着vWord1
是指向const
变量的指针,该变量的类型未知或可能是任何东西。
如果我们查看qsort()
函数声明,它看起来像:
void qsort (void* base, size_t num, size_t size,
int (*comparator)(const void*,const void*));
因此,与qsort()
一起使用的比较函数必须具有兼容的参数列表或接口描述,否则现代C编译器将发出错误。
传统上使用与qsort()
以及bsearch()
一起使用的比较函数,我们将有一个比较函数,如下所示:
CompareCounts(const void *vWord1, const void *vWord2)
在比较函数中,我们将获取void *
参数并将它们转换为将在比较中使用的实际类型的指针。之后,我们使用本地的,正确类型化的变量来进行比较操作。
qsort()
所做的是获取它想要比较的数组的两个元素,并使用指向这两个元素的指针调用比较函数。使用void *
是为了解决C编译器的类型检查问题。
接口指定void *
指针指向const
,因为qsort()
不希望您更改它提供的数据。它要求您测试提供的两个数据项,并指出在用于对数据进行排序的整理顺序中哪个更大或更小。
void *
指针的原因是因为qsort()
函数不知道数据是什么或数据是如何构造的。 qsort()
只知道每个数据元素的字节数,大小,以便它可以逐个元素地遍历项目数组。这允许数组是任何大小的struct
或其他类型的数据。
具体实例比较功能
CompareCounts()
的界面,参数是如何投射的,在我查看你链接到的源代码之前,对我来说看起来很奇怪。该程序生成树结构,然后生成指向树中实际节点的指针数组。这是指向节点的指针数组,传递给qsort()
进行排序。
因此,提供给qsort()
的数据数组是一个数组,其每个元素指向一个树节点,该树节点是存储在树数据结构中的WORD
元素。指针数组根据指针指向的数据进行排序。
为了通过使用传递给qsort()
函数的数组访问特定节点,我们必须获取数组元素并取消引用它以获取实际的树节点。
由于qsort()
传递一个指向数组元素的指针,因此void *vWord1
是一个指向数组元素的指针,我们必须取消引用该指针以获取实际的数组元素,即指向树元素的指针。但是,它不是我们想要用作排序标准的指针值,而是指针指向的指针值。这要求我们取消引用数组元素的指针,以便访问我们想要比较的树中的WORD
元素的数据。
WORD * const *Word1 = vWord1;
做了一个void *
指针vWord1
的演员,是一个指向WORD
的const指针。这意味着Word1
是一个指针,qsort()
用来指向要排序的项目,这是一个指针,它是const
(qsort()
不希望你改变的数组元素本身)和const
指向的Word1
指针to,指向WORD
(指向树节点的指针,该节点是数组包含的数据)。
树的每个节点包含的是一个文本字以及一个关于在文本样本中找到该字的次数的计数。 qsort()
函数用于对树的节点进行排序,这是通过检查从最频繁到最不频繁的文本样本输入得到的。节点指针列表是提供给qsort()
的。
因此,排序不是基于数组值对数组进行排序,而是基于数组值(树节点指针)指向的排序。
顺便说一句,当我尝试编译示例时,我看到一个警告warning C4090: 'initializing': different 'const' qualifiers
与Visual Studio 2015的行:
WORD * const *Word1 = vWord1;
WORD * const *Word2 = vWord2;
但是,通过以下更改,编译器警告消失:
const WORD * const * Word1 = vWord1;
const WORD * const * Word2 = vWord2;
这种变化实际上与qsort()
所要求的一致,即无论是来自数组元素的指针还是来自数组元素的指针所指向的数据,都不应该改变任何数据。
无论如何,表达式(*Word1)->Count
正在获取由qsort()
提供的数组元素的指针,取消引用它以获取指向树节点的指针,然后解引用指向树节点的指针以获取我们想要的WORD
结构的成员反对。排序使用存储在Count
中的单词的频率计数作为排序标准。
附录主题:玩const
提出的一个问题是,通过这种复杂的定义,const WORD * const * Word1 = vWord1;
通过打破const
以及查看何时使用const
来生成编译器错误的各种方法可以提供额外的保护措施,防止无意中修改不应修改的内容。
如果我们在没有const
修饰符的情况下使用这个定义,我们将使用WORD * * Word1 = vWord1;
,这意味着我们有一个指针变量Word1
,其含义类似于:
Word1 - > ptr - > WORD
其中Word1
是我们的指针变量,它指向一个未知指针,而该指针又指向WORD
类型的变量。
让我们看几个不同的定义变体。
WORD * * Worda = vWord1; // no const
WORD * * const Wordb = vWord1; // Wordb is const pointer which points to a non-const pointer which points to a non-const WORD
WORD * const * Wordc = vWord1; // WordC is a non-const pointer which points to a const pointer which points to a non-const WORD
const WORD * const * Wordd = vWord1; // Wordd is a non-const pointer which points to a const pointer which points to a const WORD
const WORD * const * const Worde = vWord1; // Worde is a const pointer which points to a const pointer which points to a const WORD
在WORD * const * Word1 = vWord1;
定义的问题的源代码中,Word1
是一个非const指针,指向一个指向非const WORD
的const指针。所以让我们看看几种不同的作业:
Word1 = vWord2; // replace the value of the pointer Word1, allowed since non-const
(*Word1)++; // Error: increment value of pointer pointed to by Word1, not allowed since pointer pointed to is const so compiler error
(*Word1)->Count++; // increment value of variable pointed to by the pointer pointed to by Word1, allowed since non-const
这是一个指向常量变量的常量指针的声明吗?
不,它只是一个指向常量变量的指针,而不是一个常量指针。
为了说清楚,你正在排序一个WORD*
数组,对于这个特定的问题,这个WORD*
指针是一个整体:
typedef WORD *wordptr;
然后以下声明更清楚:
wordptr const *Word1 = vWord1;
为什么必须以这种方式定义才能使排序工作?
这是为了确保比较器不会修改指针的内容。