P**********c
发帖数: 3417 | 1 programming perls里13章第4题的答案里说可以这样
void insert (t) {
for(p=&head; (*p)->val < t; p= & ((*p)->next))
;
if((*p)->val==t)
return;
*p = new node (t, *p);
n++;
}
书里的意思似乎是说因为用了pointer to pointer, 就不需要update老的parent的next
了。为什么会这样呢？没想明白。即使pointer to pointer，原来那个位置的parent的
next必须指向新的node, 也就是新的*p啊。虽然p没变，但是*p变了还是不行的吧。后
面第7题又用了类似的方法。是不是我有一个memory的基本东西没转过弯来呢。 |
P**********c
发帖数: 3417 | 2 只new了一次啊。for循环里什么也没做，到>t的node就出来了。 |
t**r
发帖数: 3428 | 3 哦 那就对了嘛
你再想想for循环是怎么执行的 就明白了 ：） |
o***i
发帖数: 603 | 4 这个就好像i=i+1
for出来的*p就是你说的parent 3 指向 5
现在先new node（4，*p），新建一个node，指向5，值为4
然后把原来指向5的p改成指向这个新node
明白？
的next是原来p指向
它本来的next是指向5的node地址啊，
所以我觉得*p变了他们就得update
【在 P**********c 的大作中提到】
: 只new了一次啊。for循环里什么也没做，到>t的node就出来了。
|
s*****n
发帖数: 5488 | 5 茴香豆的写法就别研究了。
这程序过不了code review.
的next是原来p指向
它本来的next是指向5的node地址啊，
所以我觉得*p变了他们就得update
【在 P**********c 的大作中提到】
: 只new了一次啊。for循环里什么也没做，到>t的node就出来了。
|
P**********c
发帖数: 3417 | 6 哦，明白了，我忘记了本来指向*p的就是它的parent.
【在 o***i 的大作中提到】
: 这个就好像i=i+1
: for出来的*p就是你说的parent 3 指向 5
: 现在先new node（4，*p），新建一个node，指向5，值为4
: 然后把原来指向5的p改成指向这个新node
: 明白？
:
: 的next是原来p指向
: 它本来的next是指向5的node地址啊，
: 所以我觉得*p变了他们就得update
|
i**********e
发帖数: 1145 | 7 请看我之前发过的帖子：
http://www.mitbbs.com/article_t0/JobHunting/31881903.html
看下12楼我贴的图片，可以对 pointer to pointer 的理解更进一步。
这个方法很巧妙，在很多情况下可以用，例如：
1）linked list insertion，就如 lz 说的.
2）linked list merge/intersection
3）BST insert (iterative)
如果不用 pointer to pointer，那以上的程序一就是需要利用递归，二就是因为处理
个别状况而写起来很繁琐。
以下是一个使用的例子：
Node *head = NULL; // this will be the result stored in linked list
Node **p = &head; // pointer to pointer used to advance the result
......
// to insert new node to p.
*p = new Node(val);
p = &((*p)->next);
......
// finally return the head of the result.
return head; |
