https://mp.weixin.qq.com/s/Ddonv6FdY4oroIT32IGxOw


https://mp.weixin.qq.com/s/0M9EgP1Sn4X4xXh93BTYqg

task_struct

简单链表实现

## 非侵入式链表
数据和指针保存在同一个数据结构中，数据类型和链表是耦合在一起的，缺点对每一种类型都得实现
一个，或者一整条链必须是同一种类型。但是有时候就是想把很多东西串起来。



## 侵入式链表
数据节点包含指针节点，指针结构和数据类型是分开，只要一个数据结构类型包含了该指针结构类型，就能成为链表中的一个节点。

linux内核的链表都是侵入式链表实现，因为需要用链表来管理很多类型。设备，task_struct，mem_page等等。


## list_head
list_head即是内核链表中的通用指针结构类型，内核中链表都为双向循环链表。
```c
struct list_head {
  struct list_head *next, *prev;
};
```

#### 初始化
调用`LIST_HEAD`宏直接初始化一个头结点，前后指针都指向自身。记住，第一个节点，也就是头结点，不存数据。

```c
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name)
   
   
// 示例  
// 1. 链表节点初始化，前驱和后继都指向自己（初始化）
//  struct list = LIST_HEAD(list);
```

还有接口初始化
```c
static inline void INIT_LIST_HEAD(struct list_head *list)
{
   list->next = list;
   list->prev = list;
}
```

上面就是内核链表的指针数据结构，怎么使用呢?

```c

struct data{
    int val;
    struct list_head list;
}

struct data first_data =
{ 
    .val = 1,
    
    .list = LIST_HEAD_INIT(data.list),
};
```

#### add接口
```c
static inline void list_add(struct list_head *new, struct list_head *head)
{
   __list_add(new, head, head->next);
}


static inline void __list_add(struct list_head *new,
         struct list_head *prev,
         struct list_head *next)
{
   next->prev = new;
   new->next = next;
   new->prev = prev;
   prev->next = new;
}
```

#### 尾插
```c
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
   __list_add(new, head->prev, head);
}
```

### del
```c
static inline void list_del(struct list_head *entry)
{
    /* __list_del_entry(entry) 也行*/
   __list_del(entry->prev, entry->next);
    
    /* 指向特定的位置，反初始化 */
   entry->next = LIST_POISON1; //代表节点无效，指向某个特殊地址。
   entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
 next->prev = prev;
 prev->next = next;
}
```
### 删除一个节点
```c
static inline void __list_del_entry(struct list_head *entry)
{
   __list_del(entry->prev, entry->next);
}
```


https://mp.weixin.qq.com/s/vt78z95V1BJER3Hb0a6vSw


https://mp.weixin.qq.com/s/yol66GJettPUk-AZt6XFmQ


https://mp.weixin.qq.com/s/Ddonv6FdY4oroIT32IGxOw

内核链表详解

![image.png](/static/img/adcb3d0ab0c238f08f277d5546ea4cd5.image.webp)

小根堆模拟一下即可


```cpp
class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
            std::priority_queue<int> pq; // 使用大顶堆存储礼物数量



    for (int gift : gifts) {
        pq.push(gift);
    }

    while (k-- > 0) {
        int maxGifts = pq.top(); // 获取当前剩余礼物数量最多的堆
        pq.pop();

        if (maxGifts == 0) {
            break; // 如果最大礼物数量为0，提前结束
        }

        int take = static_cast<int>(std::sqrt(maxGifts)); // 取走礼物的数量为平方根（向下取整）

        pq.push(take); // 将剩余的礼物数量重新放入堆中

        //k--;
    }

    long long remaining = 0;
    while (!pq.empty()) {
        remaining += pq.top();
        pq.pop();
    }

    return remaining;
    }
};
```

每日一题10.28

![image.png](/static/img/d5c14eb5e47245b5c5ea72681abfd1e9.image.webp)



思路很简单，排序，然后判断后面的位数（后面每个数大于等于当前数）是否多于当前数，从后往前遍历剪枝
```cpp
class Solution {
public:
    int hIndex(vector<int>& citations) {
        std::sort(citations.begin(), citations.end());  // 将数组排序

     int h = 0;

    int n = citations.size();

    for (int i = n - 1; i >= 0; i--) {

        // 找到满足条件的最大 h 值

        if (citations[i] >= n - i) {

            h = n - i;

        } else {

            break;

        }

    }

    return h;
    }
};
```