理解給定的頭文件

Question

根據給定的頭文件，我從計算機科學的大學課程中獲得任務，構建二叉搜索樹。 但是，我不太瞭解它的功能，它是指針和結構的組合。

這是頭文件：

#ifndef GENBST_H 
#define GENBST_H 
#include <stdio.h> 
#include <stdlib.h> 
typedef void* Elm; 
typedef void* BST; 
typedef void* BST_ROOT; 
typedef enum {SUCEESS, OUT_OF_MEM, BAD_ARGS, FAILURE } Result; 
BST_ROOT BSTCreate(Elm root_val, Elm (*create_elm)(), 
    void (*cpy_elm) (Elm,Elm), 
    int (*cmp_elm) (Elm, Elm), 
    void (*free_elm)(Elm)); 
void BSTDestroy (BST_ROOT root); 
Result BSTAddElement (BST_ROOT root, Elm node); 
Result BSTRemoveElement (BST_ROOT root, Elm node); 
Elm BSTFindElement (BST_ROOT root, Elm node); 
#endif 

你能幫我找出每一個功能意味着什麼？ 具體在BSTCreate函數中？

Answer 1

我不能給出一個完整的答案，但我希望這個解釋能幫助你。

首先，正如Magix的評論所述，頭文件中沒有函數定義，但頭文件給出了接口應該如何的規範。它指定了函數原型和變量的類型，給定這些，你應該能夠實現BST。

試着寫下一個算法，看看你是否可以通過使用在這個頭中聲明的所有原型來實現它。 說，這樣做對兩行解釋也會有很大的幫助;）

讓我們來看看每一個標題！ 樹中的所有首先你給出的元素和BST的類型：

typedef void* Elm; 
typedef void* BST; 
typedef void* BST_ROOT; 

然後枚舉指定一些返回類型，你可以使用的值：

typedef enum { 
SUCCESS,   // 0 (I corrected the spell) 
OUT_OF_MEM,  // 1 
BAD_ARGS,   // 2 
FAILURE   // 3 
} Result;   

在這裏，你明白你必須提供一個創建BST的函數。

BST_ROOT BSTCreate( 
    Elm root_val, 
    Elm (*create_elm)(), 
    void (*cpy_elm) (Elm,Elm), 
    int (*cmp_elm) (Elm, Elm), 
    void (*free_elm)(Elm)); 

此功能必須使用其他四個功能：

Elm (*create_elm)(), 
    void (*cpy_elm) (Elm,Elm), 
    int (*cmp_elm) (Elm, Elm), 
    void (*free_elm)(Elm) 

最後，你還應該提供一組函數來修改BST：

void BSTDestroy (BST_ROOT root); 
Result BSTAddElement (BST_ROOT root, Elm node); 
Result BSTRemoveElement (BST_ROOT root, Elm node); 
Elm BSTFindElement (BST_ROOT root, Elm node); 

Answer 2

這是某種形式的半 - 對類型泛型編程的失敗嘗試和創建ADT（「抽象數據類型」）。 「半失敗」，因爲太慷慨地使用void指針而沒有類型安全。特別是，隱藏typedef後面的指針是非常糟糕的做法。無論如何...

Elm可能指的是「元素」，即存儲在樹中的實際數據。那麼root_val顯然會成爲樹的最高值。

其餘參數是函數指針。它是一個排序模板：函數必須具有指定的格式。

顯然你是爲了給你創建的每一棵樹提供指向數據特定函數的指針。對於每種特定的數據類型，這些功能可以以適當的方式實現。你可以爲int設置一組函數，爲字符串等設置一組函數。併爲每個這樣的數據類型創建一種樹。

create_elm和free_elm是指向創建/刪除特定類型的元素（與C++中的構造函數/析構函數進行比較）的函數的指針。

cpy_elm可能應該是一個複製特定元素的函數（與C++中的重載賦值運算符進行比較）。

而cmp_elm是實際的比較函數，可能應該返回-1,0或1，具體取決於param1小於，等於還是大於param2。看看如何使用C標準bsearch函數，這個函數的含義會變得更清晰。 SO上有很多例子。