全部答案

2017-07-27 23:18:02

•   内核中链表O
  (1)的添加、删除操作
  Linux内核中标准链表实现上采用的是环形双向链表。链表结构的定义在中，
  struct list_head {
  struct list_head *next, *prev;
  }
  在内核中，链表中的任何一个节点都可以作为头节点，从另外一个角度而言，也就是说，链表中没有头节点。
    
  （1）
  由于是双向链表，所以链表很容易实现向前或向后访问
  （2）
  由于是环形链表，所以我们很容易从任意一个节点开始遍历整个链表
  （3）
  由于是双向环形链表，我们很容易实现O
  (1)的链表添加、删除操作
  链表的插入
  /*
  * Insert a new entry between two known consecutive entries。
    
  *
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
  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;
  }
  已知插入的位置，只需进行四次赋值就可完成链表元素的插入
  双向链表的使用一般支持节点的前向插入和后向插入，通过上述__list_add我们都可以实现，例如，对于特定的头节点struct list_head *head，前向插入可以通过
  __list_add(new, head->prev, head)
  实现，后向插入可以通过
  __list_add(new, head, head->next)
  实现
  链表的删除
  /*
  * Delete a list entry by making the prev/next entries
  * point to each other。
    
  *
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
  static inline void __list_del(struct list_head * prev, struct list_head * next)
  {
  next->prev = prev;
  prev->next = next;
  }
  显然，上述插入和删除操作显然是O
  (1)的。
    
  实际上，对于单项链表，我们也能够实现O
  (1)的插入和删除操作的
  假设单向链表的定义为
  struct list_node {
  int data;
  struct list_node *next;
  }
  对于单向链表，一般为了操作方便，会加上一个链表头，链表头指向链表的第一个元素，当链表头的next指针为0时，链表为空。
    
  对于上述定义的单向链表，我们O
  (1)的插入和删除操作实现如下：
  /*Insert a new node before specified node*/
  static inline void __list_add(struct list_node *new,
  struct list_node *node)
  {
  int tmp = node->data;
  node->data = new->data;
  new->data = tmp;
  new->next = node->next;
  node->next = new;
  }
  前向插入的难点在于单向链表中我们无法以O
  (1)的代价得到当前节点的前一个节点，但如果我们将new和node的内容交换以后，问题变成了在node后向插入一个节点，这个问题就会很简单。
    
  删除操作
  static inline void __list_del(struct list_node *head,
  struct list_node *node)
  {
  if (head == node){
  return;
  }else if (node->next == 0){
  struct list_node *tmp = head;
  while (tmp->next != node){
  tmp = tmp->next;
  }
  tmp->next = 0;
  } else {
  struct list_node *tmp = node->next;
  node->data = tmp->data;
  node->next = tmp->next;
  free_node(tmp);
  }
  }
  上述代码中，当被删除节点不是链表尾节点时，我们只需将被删除节点的后一个节点拷贝到被删除节点，然后释放掉后一个节点即可；当被删除节点是链表尾节点时，由于我们必须重置被删除节点的前一个节点的next指针为空，因此需要从头遍历链表。
    
  删除操作的复杂度分析可以这样来做：假设链表的长度为n，当删除的是第1至n-1个节点时，需要查找n-1次（每个节点各超找一次），当删除的是第n个节点时，需要查找n-1次，所以平均的查找次数为(2*(n-1))/n，可以看出，平均计算复杂度仍然是O
  (1)。
    
  考试大温馨提示：本内容来源于网络，仅代表作者个人观点，与本站立场无关，仅供您学习交流使用。其中可能有部分文章经过多次转载而造成文章内容缺失、错误或文章作者不详等问题，请您谅解。如有侵犯您的权利，请联系我们，本站会立即予以处理。
  编辑特别推荐:
  linuxln命令详解
  nginx关于服务静态文件的配置
  使用expect实现ssh自动交互。
    

  全部
  

  K***

  2017-07-27 23:18:02

  47 6 评论

  分享
  提交评论