C:是否有可能有一个递归函数,它将一个函数指针数组作为其参数之一？

Question

这是更长的版本.(TL; DR版本在我的帖子标题中.)

让我们考虑一个递归quick_sort这是目前设置如下功能:(i)其有一个参数-一个链表,(ii)其按升序排序的元素,以及(iii)它返回一个排序的链表.下面的说明性代码(我可以根据要求发布实际代码 - 更长时间).

#include "list.h"  /*our linked-list implementation which includes definitions
                     for `concatenate`, which we use below*/

typedef int (*ordinal(int referenceValue, int currentValue));

int smaller(int referenceValue, int currentValue)
{
  return currentValue <= referenceValue ? 1 : 0;
}

int larger(int referenceValue, int currentValue)
{
  return currentValue > referenceValue ? 1 : 0;
}

List *getElements(List *fullList, ordinal compare)  /*let's assume this function exists*/
  /*implementation of getElements*/

List* quickSort(List* originalList)
{
  /*code to handle the two base cases, i.e., the cases
    in which the input list has either 0 or 1 elements */

  List *pivotElement = List_create();
  List_push(pivotElement, originalList->first->value);

  /*we're simply using the first element in the list as the pivot-point*/

  List *prePivotElements = quickSort( getElements(originalList, smaller) );
  List *postPivotElements = quickSort ( getElements(originalList, larger) );
  List *newList = concatenate(prePivotElements, pivotElement, postPivotElements);

  return newList;
}

现在让我们说我们想要修改我们的quick_sort函数,以便它有两个参数:一个链表和一个函数指针数组.我们的想法是使用第二个参数(即函数指针数组)来指定排序顺序.函数调用的语法如下所示:quick_sort(linked_list, increasing[])或quick_sort(linked_list, decreasing[]).

我应该提一下,我的重点是理解递归传递函数指针数组的正确语法的可行性,而不是算法效率等等.换句话说,让我们试着忽略可怕的效率/内存管理方面快速排序的这个特殊实现:)

为了quick_sort如上所述进行修改,我认为以下代码可能有用......

#include "list.h" 

typedef int (*ordinal(int referenceValue, int currentValue));

int smaller(int referenceValue, int currentValue)
{
  return currentValue <= referenceValue ? 1 : 0;
}

int larger(int referenceValue, int currentValue)
{
  return currentValue > referenceValue ? 1 : 0;
}

/*two new global arrays of function pointers*/
int (*increasing[2]) (int referenceValue, int currentValue) = {smaller, larger};
int (*decreasing[2]) (int referenceValue, int currentValue) = {larger, smaller};

List *getElements(List *fullList, ordinal compare)
  /*implementation of getElements*/

/*updated argument list*/
List* quickSort(List* originalList, ordinal compare[])
{
  /*base cases*/
  List *pivotElement = List_create();
  List_push(pivotElement, originalList->first->value);

  /*updated recursive function call*/
  List *prePivotElements = 
              quickSort( getElements(originalList, compare[0]), compare );
  List *postPivotElements = 
              quickSort ( getElements(originalList, compare[1]), compare );
  List *newList = concatenate(prePivotElements, pivotElement, postPivotElements);

  return newList;
}

...但会导致以下错误:

error: declaration of ‘compare’ as array of functions
   List* quickSort(List* originalList, ordinal compare[])
                                               ^
error: type of formal parameter 2 is incomplete
   List *prePivotElements = quickSort( getElements(originalList, compare[0]), compare );
   ^
error: type of formal parameter 2 is incomplete
   List *postPivotElements = quickSort ( getElements(originalList, compare[1]), compare );
   ^

回顾一下我的问题:C是否允许我们将函数指针数组传递给其他函数？怎么递归呢？如果允许,那么正确的语法是什么？

请原谅长度的帖子,我相信你们其中一个退伍军人会更加简洁!

(关于SO规则all posted code must compile:我认为在这种情况下坚持使用概念相关的代码是有意义的.但是,如果人们更喜欢,我可以发布完整的.c文件和.h文件.)

更新: 这里要求的是工作版本的相关文件quick_sort.我还包括shell输出,包括用于编译/链接的命令.仅供参考,代码板给出一些没有任何意义的奇怪错误(例如,在具有正确/可编译函数头的行上,它声称我缺少一个括号):

• quick_sort.c:http://codepad.org/O2ZlWssl
• list.h:http://codepad.org/SVS12bI5
• list.c:http://codepad.org/x7pex3Tl
• dbg.h:http://codepad.org/ZRifL1hE
• Shell输出(和命令):http://codepad.org/WIxIrQ6E

Answer 1

typedef int (*ordinal(int referenceValue, int currentValue));

是不正确的.它在语法上是有效的,但是括号没有效果,它只是定义了一个函数类型而不是函数的指针.键入dede函数指针的正确方法是

typedef int (*ordinal)(int, int);

这是括号绕过标识符和* 唯一(和参数名称无关).

并且使用该typedef更好地声明函数数组,而不是重复定义.

ordinal increasing[2] = {smaller, larger};