c 语言双指针的问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 1025 天前的主题，其中的信息可能已经有所发展或是发生改变。

https://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)AvlTree.html

 3 typedef struct avlNode *AvlTree; 5 /* empty avl tree is just a null pointer */ 6 7 #define AVL_EMPTY (0) 8

 9 struct avlNode { 10 struct avlNode *child[2]; /* left and right */ 11 int key; 12 int height; 13 }; 14 87 static void 88 avlRotate(AvlTree *root, int d) 89 { 90 AvlTree oldRoot; 91 AvlTree newRoot; 92 AvlTree oldMiddle; 93 94 oldRoot = *root; 95 newRoot = oldRoot->child[d]; 96 oldMiddle = newRoot->child[!d]; 97 98 oldRoot->child[d] = oldMiddle; 99 newRoot->child[!d] = oldRoot; 100 *root = newRoot; 101 102 /* update heights */ 103 avlFixHeight((*root)->child[!d]); /* old root */ 104 avlFixHeight(*root); /* new root */ 105 } 106 107 108 /* rebalance at node if necessary */ 109 /* also fixes height */ 110 static void 111 avlRebalance(AvlTree *t) 112 { 113 int d; 114 115 if(*t != AVL_EMPTY) { 116 for(d = 0; d < 2; d++) { 117 /* maybe child[d] is now too tall */ 118 if(avlGetHeight((*t)->child[d]) > avlGetHeight((*t)->child[!d]) + 1) { 119 /* imbalanced! */ 120 /* how to fix it? */ 121 /* need to look for taller grandchild of child[d] */ 122 if(avlGetHeight((*t)->child[d]->child[d]) > avlGetHeight((*t)->child[d]->child[!d])) { 123 /* same direction grandchild wins, do single rotation */ 124 avlRotate(t, d); 125 } else { 126 /* opposite direction grandchild moves up, do double rotation */ 127 avlRotate(&(*t)->child[d], !d); 128 avlRotate(t, d); 129 } 130 131 return; /* avlRotate called avlFixHeight */ 132 } 133 } 134 135 /* update height */ 136 avlFixHeight(*t); 137 } 138 } 139 140 /* insert into tree */ 141 /* this may replace root, which is why we pass 142 * in a AvlTree * */ 143 void 144 avlInsert(AvlTree *t, int key) 145 { 146 /* insertion procedure */ 147 if(*t == AVL_EMPTY) { 148 /* new t */ 149 *t = malloc(sizeof(struct avlNode)); 150 assert(*t); 151 152 (*t)->child[0] = AVL_EMPTY; 153 (*t)->child[1] = AVL_EMPTY; 154 155 (*t)->key = key; 156 157 (*t)->height = 1; 158 159 /* done */ 160 return; 161 } else if(key == (*t)->key) { 162 /* nothing to do */ 163 return; 164 } else { 165 /* do the insert in subtree */ 166 avlInsert(&(*t)->child[key > (*t)->key], key); 167 168 avlRebalance(t); 169 170 return; 171 } 172 }

这个实现中，avlRotate, avlRebalance, avlInsert 都用了双指针，我的理解是作者特意用了双指针。双指针相比于直接用指针有什么特别的优势么？
avl tree ，red black tree 还有什么写的很好的可以多学习下的实现么？

第 1 条附言 2022-12-28 12:32:54 +08:00

大家有没有什么高性能，牛皮的实现，让我学习学习

2 条回复 2022-12-28 12:38:14 +08:00

stein42

2022-12-28 12:10:27 +08:00

这个通常叫二级指针吧。

AvlTree 定义为指向根结点的指针。
对 AvlTree 进行修改，它的根结点可能改变，所以定义 AvlTree 为 AvlNode* 是必要的。

传参都是传 AvlTree*，相当于 AvlNode**，这是一个二级指针。

另一种定义方法是结构体：
struct AvlTree { AvlNode* root; }
结构体的好处是还可以包含其它字段，例如树的结点数量。
没有其它字段的话用指针也是可以的。

Or2

2022-12-28 12:38:14 +08:00 via Android

哈哈，豁然开朗啊！