V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Or2
V2EX  ›  问与答

c 语言双指针的问题

  •  
  •   Or2 · 2022-12-28 10:37:14 +08:00 · 829 次点击
    这是一个创建于 457 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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 }
    
    1. 这个实现中,avlRotate, avlRebalance, avlInsert 都用了双指针,我的理解是作者特意用了双指针。 双指针相比于直接用指针有什么特别的优势么?
    2. avl tree ,red black tree 还有什么写的很好的可以多学习下的实现么?
    第 1 条附言  ·  2022-12-28 12:32:54 +08:00
    大家有没有什么高性能,牛皮的实现,让我学习学习
    2 条回复    2022-12-28 12:38:14 +08:00
    stein42
        1
    stein42  
       2022-12-28 12:10:27 +08:00   ❤️ 1
    这个通常叫二级指针吧。

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

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

    另一种定义方法是结构体:
    struct AvlTree { AvlNode* root; }
    结构体的好处是还可以包含其它字段,例如树的结点数量。
    没有其它字段的话用指针也是可以的。
    Or2
        2
    Or2  
    OP
       2022-12-28 12:38:14 +08:00 via Android
    哈哈,豁然开朗啊!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2780 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 15:04 · PVG 23:04 · LAX 08:04 · JFK 11:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.