Chinaunix首页 | 论坛 | 博客
  • 博客访问: 46863
  • 博文数量: 18
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 12
  • 用 户 组: 普通用户
  • 注册时间: 2018-04-03 10:12
文章分类
文章存档

2018年(18)

我的朋友

分类: C/C++

2018-07-27 15:28:48

(八)旋转链表的第一个节点到最后
这个函数的操作的最终结果是将head的next与head自己本身进行了交换。
  1. static inline void list_rotate_left(struct list_head *head)
  2. {
  3.     struct list_head *first;
  4.     if (!list_empty(head)) {
  5.         first = head->next;
  6.         list_move_tail(first, head);
  7.     }
  8. }
(九)分割链表
这里提供的函数接口是:
static inline void __list_cut_position(struct list_head *list,
struct list_head *head, struct list_head *entry)
list:将剪切的结点要加进来的链表
head:被剪切的链表
entry:所指位于由head所指领头的链表内,它可以指向head,但是这样的话,head就不能被剪切了,在代码中调用了INIT_LIST_HEAD(list)。
是将head(不包括head)到entry之间的所有结点剪切下来加到list所指向的链表中。这个操作之后就有了两个链表head和list。具体的结果参看下面的截图:
  1. static inline void list_cut_position(struct list_head *list,
  2.         struct list_head *head, struct list_head *entry)
  3. {
  4.     if (list_empty(head))
  5.         return;
  6.     if (list_is_singular(head) &&
  7.         (head->next != entry && head != entry))
  8.         return;
  9.     if (entry == head)
  10.         INIT_LIST_HEAD(list);
  11.     else
  12.         __list_cut_position(list, head, entry);
  13. }
真正的分割操作是下面的函数:
  1. static inline void __list_cut_position(struct list_head *list,
  2.         struct list_head *head, struct list_head *entry)
  3. {
  4.     struct list_head *new_first = entry->next;
  5.     list->next = head->next;
  6.     list->next->prev = list;
  7.     list->prev = entry;
  8.     entry->next = list;
  9.     head->next = new_first;
  10.     new_first->prev = head;
  11. }
分割之前的情况:
 
分割之后的结果:
 
(十)链表的合并
提供的接口有四个:
static inline void list_splice(const struct list_head *list,
struct list_head *head)
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
static inline void list_splice_init(struct list_head *list,
   struct list_head *head)
static inline void list_splice_tail_init(struct list_head *list,
struct list_head *head)
真正的合并操作是这个函数实现的:
  1. static inline void __list_splice(const struct list_head *list,
  2.                  struct list_head *prev,
  3.                  struct list_head *next)
  4. {
  5.     struct list_head *first = list->next;
  6.     struct list_head *last = list->prev;

  7.     first->prev = prev;
  8.     prev->next = first;

  9.     last->next = next;
  10.     next->prev = last;
  11. }
这个函数实现的结果是将list领头的这个链表合并到prev和next之间,不包括list这个结点。
  1. static inline void list_splice(const struct list_head *list,
  2.                 struct list_head *head)
  3. {
  4.     if (!list_empty(list))
  5.         __list_splice(list, head, head->next);
  6. }
将list所指链的内容加到head和head->next之间(类似于头插法)。
  1. static inline void list_splice_tail(struct list_head *list,
  2.                 struct list_head *head)
  3. {
  4.     if (!list_empty(list))
  5.         __list_splice(list, head->prev, head);
  6. }
将list所指链的内容加到head->prev和head(类似于尾插法),插入之后,head->prev将会是原来的list->prev,这点需要注意。
  1. static inline void list_splice_init(struct list_head *list,
  2.                  struct list_head *head)
  3. {
  4.     if (!list_empty(list)) {
  5.         __list_splice(list, head, head->next);
  6.         INIT_LIST_HEAD(list);
  7.     }
  8. }
将list所指链的内容加到head和head->next之间(类似于头插法),完了之后,将list初始化为一个空链表。
  1. static inline void list_splice_tail_init(struct list_head *list,
  2.                      struct list_head *head)
  3. {
  4.     if (!list_empty(list)) {
  5.         __list_splice(list, head->prev, head);
  6.         INIT_LIST_HEAD(list);
  7.     }
  8. }
将list所指链的内容加到head->prev和head(类似于尾插法),插入之后,head->prev将会是原来的list->prev,这点需要注意,完了之后,将list初始化为一个空链表。

阅读(1368) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~