0

我创建了一个简单的测试程序，如下所示（省略了错误检查）。

我的 Tree_Find() 和 Node_Find() 函数似乎工作正常，但我想知道是否有更有效的方法来实现相同的目标。

节点.h

typedef struct _Node Node;

Node* Node_Create(int nTag);
void Node_Destroy(Node **ppNode);
void Node_Append(Node **ppParent, Node *pChild);
Node* Node_Find(Node *pNode, int nTag);

树.h

#include "Node.h"

typedef struct _Tree Tree;

Tree* Tree_Create(void);
void Tree_Destroy(Tree **ppTree);
void Tree_Init(Tree *pTree);
Node* Tree_Find(Tree *pTree, int nTag);

节点.c

#include "Node.h"

struct _Node
{
    int nTag;
    struct _Node *pFirstChild;
    struct _Node *pNextSibling;
};

Node* Node_Create(int nTag)
{
    Node *pNode = malloc(sizeof(*pNode));
    pNode->nTag = nTag;
    pNode->pFirstChild = NULL;
    pNode->pNextSibling = NULL;

    return pNode;
}

void Node_Destroy(Node **ppNode)
{
    Node *pNode = NULL;

    if (!ppNode)
        return;

    if ((pNode = *ppNode) == NULL)
        return;

    Node_Destroy(&(pNode->pFirstChild));
    Node_Destroy(&(pNode->pNextSibling));

    free(pNode);
    *ppNode = NULL;
}

void Node_Append(Node **ppParent, Node *pChild)
{
    Node *pLastChild = NULL;

    if (!(*ppParent))
        return;

    if (!((*ppParent)->pFirstChild))
    {
        (*ppParent)->pFirstChild = pChild;

        return;
    }

    pLastChild = (*ppParent)->pFirstChild;
    while (pLastChild->pNextSibling)
        pLastChild = pLastChild->pNextSibling;

    pLastChild->pNextSibling = pChild;
}

Node* Node_Find(Node *pNode, int nTag)
{
    Node *pNodeFound = NULL;

    if (!pNode)
        return NULL;

    if (pNode->nTag == nTag)
        return pNode;

    if ((pNodeFound = Node_Find(pNode->pFirstChild, nTag)) == NULL)
        pNodeFound = Node_Find(pNode->pNextSibling, nTag);

    return pNodeFound;
}

树.c

#include "Tree.h"

struct _Tree
{
    Node *pRoot;
};

Tree* Tree_Create(void)
{
    Tree *pTree = malloc(sizeof(*pTree));

    pTree->pRoot = NULL;

    return pTree;
}

void Tree_Destroy(Tree **ppTree)
{
    Tree *pTree = NULL;

    if (!ppTree)
        return;

    if ((pTree = *ppTree) == NULL)
        return;

    Node_Destroy(&(pTree->pRoot));

    free(pTree);
    *ppTree = NULL;
}

void Tree_Init(Tree *pTree)
{
    Node *p1 = Node_Create(1);
    Node *p2 = Node_Create(2);
    Node *p3 = Node_Create(3);
    Node *p4 = Node_Create(4);
    Node *p5 = Node_Create(5);

    Node_Append(&p1, p2);
    Node_Append(&p1, p3);
    Node_Append(&p3, p4);
    Node_Append(&p3, p5);

    pTree->pRoot = p1;
}

Node* Tree_Find(Tree *pTree, int nTag)
{
    if (!pTree)
        return NULL;

    return Node_Find(pTree->pRoot, nTag);
}

主程序

#include "Tree.h"

int main(void)
{
    Node *pNodeToFind = NULL;

    Tree *pTree = Tree_Create();

    Tree_Init(pTree);

    pNodeToFind = Tree_Find(pTree, 1);
    pNodeToFind = Tree_Find(pTree, 2);
    pNodeToFind = Tree_Find(pTree, 3);
    pNodeToFind = Tree_Find(pTree, 4);
    pNodeToFind = Tree_Find(pTree, 5);
    pNodeToFind = Tree_Find(pTree, 6); // Not found!

    Tree_Destroy(&pTree);

    return 0;
}
4

2 回答 2

0

正如 Linus Torvalds 所说，一切都与数据结构有关。你的算法本身不能优化太多，但你的数据结构可以。重复的指针访问并不便宜，你可以在一个节点中存储一个包含 256 个对象的数组以获得更高的性能。

于 2012-09-08T20:06:37.353 回答
0

如果您的目标是构建和搜索没有键顺序的任意树，那么您已经完成了几乎所有可以做的事情，除了一件事：您的 append 方法将具有 O(n^2) 运行时间，其中 n 是单个节点可能具有的子节点。如果你维护一个队列而不是一个列表，你可以在单位时间内追加。有一个很好的技巧来实现一个队列，在头中只有一个指针，而不是单独的头和尾指针。使子列表循环并让父指向循环列表的尾部。那么 parent->children 是尾部元素，而 parent->children->sibling 是头部。使用此设置，您可以推送到尾部，并从子列表的头部推送和弹出。这些操作的代码可以非常优雅，并且您的追加将是恒定的时间。

或者，您可以将子项存储在自动调整大小的数组中。存在轻微的存储损失（您需要为每个节点存储一个指针和子节点计数），但在某些情况下随机访问子节点可能很方便。

于 2012-09-08T20:24:57.310 回答