一个带有优先级的链表:
struct list {
struct list* next;
u32 priority;
}
如果要按照优先级插入某个新节点node,算法一般会写成:
int list_insert(list **head, list* new)
{
if (head == null || *head == null || new == null)
return 1;
list *prev = null;
list *cur = *head;
while (cur != null) {
if (new->priority > cur->proirity) {
new->next = cur;
if (prev != null) // new放在表中
prev->next = new;
else // new放在表头
*head = new;
return 0;
}
prev = cur;
cur = cur->next;
}
}
如果规定不让使用临时变量呢?思考一下如何实现?
int list_insert(list **head, list* new)
{
if (head == null || *head == null || new == null)
return 1;
while (*head != null) {
if (new->priority > (*head)->proirity) {
break;
}
head = &((*head)->next);
}
new->next = *head;
*head = new;
}
为什么这种方法能行?有几个核心原因(以a->b->c为例):
- p = &(a->next),表示p就是b的地址?*p = new会把b覆盖?错误!p是a->next的地址,不是b的地址,a->next只是数值上和b的地址相同,不是等价的!
- b和new进行比较时,拿的不是b,而是a->next的地址,这样才可以做到a->next和new->new均可修改
标签:head,技巧,list,next,链表,插入,new,null,cur From: https://www.cnblogs.com/moon-sun-blog/p/18259585