菜单

澳门金沙网投平台Linux内核部件分析

2019年1月23日 - 金沙编程资讯

 

list_entry紧要用于从list节点查找其内嵌在的结构。比如定义一个结构struct
A{ struct list_head list; };
若是知道结构中链表的地点ptrList,就足以从ptrList进而获取整个结构的地址(即一切结构的指针)
struct A *ptrA = list_entry(ptrList, struct A, list);

目录:
  1. 链表
  2. 二叉树
  3. 哈希表
  4. 概括算法
  5. 架构

8.3.2  广度优先搜索遍历

图的广度优先搜索遍历算法是一个分层遍历的长河,和二叉树的广度优先搜索遍历类同。它从图的某一顶点Vi启程,访问此顶点后,依次访问Vi的依次未曾访问过的邻接点,然后分别从这几个邻接点出发,直至图中有所已有已被访问的极端的邻接点都被访问到。对于图8.15所示的无向连通图,若顶点Vi为初叶访问的巅峰,则广度优先搜索遍历顶点访问顺序是:V1 → V2 → V3 → V4 → V5 → V6 → V7 → V8。遍历进程如图8.16的所示。

澳门金沙网投平台 1
 

和二叉树的广度优先搜索遍历类似,图的广度优先搜索遍历也急需借助队列来形成,例8.3演示了那一个进度。

【例8-3 
BFSTraverse.cs】广度优先搜索遍历

打开【例8-2 
DFSTraverse.cs】,在AdjacencyList<T>类中添加以下代码后,将文件另存为BFSTraverse.cs。

54      public void BFSTraverse() //广度优先遍历
55      {
56          InitVisited(); //将visited标志全体置为false
57          BFS(items[0]); //从第三个极点开端遍历
58      }
59      private void BFS(Vertex<T> v) //使用队列举行广度优先遍历
60      {   //创立一个行列
61          Queue<Vertex<T>> queue = new Queue<Vertex<T>>();
62          Console.Write(v.data + ” “); //访问
63          v.visited = true; //设置访问标志
64          queue.Enqueue(v); //进队
65          while (queue.Count > 0) //只要队不为空就循环
66          {
67              Vertex<T> w = queue.Dequeue();
68              Node node = w.firstEdge;
69              while (node != null) //访问此顶点的有所邻接点
70              {   //假设邻接点未被访问,则递归访问它的边
71                  if (!node.adjvex.visited)
72                  {
73                      Console.Write(node.adjvex.data + ” “); //访问
74                      node.adjvex.visited = true; //设置访问标志
75                      queue.Enqueue(node.adjvex); //进队
76                  }
77                  node = node.next; //访问下一个邻接点
78              }
79          }
80      }

 

【例8-3 
Demo8-3.cs】广度优先搜索遍历测试

using System;
class Demo8_3
{
    static void Main(string[] args)
    {
        AdjacencyList<string> a = new AdjacencyList<string>();
        a.AddVertex(“V1”);
        a.AddVertex(“V2”);
        a.AddVertex(“V3”);
        a.AddVertex(“V4”);
        a.AddVertex(“V5”);
        a.AddVertex(“V6”);
        a.AddVertex(“V7”);
        a.AddVertex(“V8”);
        a.AddEdge(“V1”, “V2”);
        a.AddEdge(“V1”, “V3”);
        a.AddEdge(“V2”, “V4”);
        a.AddEdge(“V2”, “V5”);
        a.AddEdge(“V3”, “V6”);
        a.AddEdge(“V3”, “V7”);
        a.AddEdge(“V4”, “V8”);
        a.AddEdge(“V5”, “V8”);
        a.AddEdge(“V6”, “V8”);
        a.AddEdge(“V7”, “V8”);
        a.BFSTraverse(); //广度优先搜索遍历
    }
}

 

运作结果:

 

V1 V2 V3 V4 V5 V6 V7
V8

 

运行结果请参照图8.16展开剖析。

1.广泛方法分为迭代和递归,迭代是从头到尾,递归是从尾到头
2.装置多少个指针,old和new,每一项添加在new的末尾,新链表头指针指向新的链表头
3.old->next无法一贯指向new,而是应该安装一个临时指针tmp,指向old->next指向的地方空间,保存原链表数据,然后old->next指向new,new往前挪动到old处new=old,最后old=tmp取回数据
while(old!=null){
  tmp=old->next
  old->next=new
  new=old
  old=tmp
}

  1. #define list_for_each(pos, head) \
      
  2.     for (pos = (head)->next; prefetch(pos->next), pos != (head); \  
  3.             pos = pos->next)  
5. 架构

8.2 图的贮存结构

图的储存结构除了要存储图中逐一顶点的自家的音信外,同时还要存储顶点与终端之间的具有涉及(边的音信),因而,图的结构相比较复杂,很为难数据元素在存储区中的物理地点来表示元素之间的关系,但也正是出于其擅自的性状,故物理表示方法很多。常用的图的贮存结构有邻接矩阵、邻接表、十字链表和毗邻多重表。

<?php
class Node{
        public $data;
        public $next;
}
//头插法创建一个链表
$linkList=new Node();
$linkList->next=null;//头结点
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";//创建新结点$node
        $node->next=$linkList->next;//$node->next指向头结点->next
        $linkList->next=$node;//头结点->next指向$node
}

var_dump($linkList);


function ReverseList($pHead){
        $old=$pHead->next;//跳过头结点
        $new=null;
        $tmp=null;
        //反转过程
        while($old!=null){
                $tmp=$old->next;
                $old->next=$new;
                $new=$old;
                $old=$tmp;
        }   
        //给新链表加个头结点
        $newHead=new Node();
        $newHead->next=$new;
        var_dump($newHead);
}
ReverseList($linkList);

object(Node)#1 (2) {
  ["data"]=>
  NULL
  ["next"]=>
  object(Node)#11 (2) {
    ["data"]=>
    string(5) "aaa10"
    ["next"]=>
    object(Node)#10 (2) {
      ["data"]=>
      string(4) "aaa9"
      ["next"]=>
      object(Node)#9 (2) {
        ["data"]=>
        string(4) "aaa8"
        ["next"]=>
        object(Node)#8 (2) {
          ["data"]=>
          string(4) "aaa7"
          ["next"]=>
          object(Node)#7 (2) {
            ["data"]=>
            string(4) "aaa6"
            ["next"]=>
            object(Node)#6 (2) {
              ["data"]=>
              string(4) "aaa5"
              ["next"]=>
              object(Node)#5 (2) {
                ["data"]=>
                string(4) "aaa4"
                ["next"]=>
                object(Node)#4 (2) {
                  ["data"]=>
                  string(4) "aaa3"
                  ["next"]=>
                  object(Node)#3 (2) {
                    ["data"]=>
                    string(4) "aaa2"
                    ["next"]=>
                    object(Node)#2 (2) {
                      ["data"]=>
                      string(4) "aaa1"
                      ["next"]=>
                      NULL
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
object(Node)#12 (2) {
  ["data"]=>
  NULL
  ["next"]=>
  object(Node)#2 (2) {
    ["data"]=>
    string(4) "aaa1"
    ["next"]=>
    object(Node)#3 (2) {
      ["data"]=>
      string(4) "aaa2"
      ["next"]=>
      object(Node)#4 (2) {
        ["data"]=>
        string(4) "aaa3"
        ["next"]=>
        object(Node)#5 (2) {
          ["data"]=>
          string(4) "aaa4"
          ["next"]=>
          object(Node)#6 (2) {
            ["data"]=>
            string(4) "aaa5"
            ["next"]=>
            object(Node)#7 (2) {
              ["data"]=>
              string(4) "aaa6"
              ["next"]=>
              object(Node)#8 (2) {
                ["data"]=>
                string(4) "aaa7"
                ["next"]=>
                object(Node)#9 (2) {
                  ["data"]=>
                  string(4) "aaa8"
                  ["next"]=>
                  object(Node)#10 (2) {
                    ["data"]=>
                    string(4) "aaa9"
                    ["next"]=>
                    object(Node)#11 (2) {
                      ["data"]=>
                      string(5) "aaa10"
                      ["next"]=>
                      NULL
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

list_splice_tail只是在集合链表时插入的地方差别。list_splice是把本来list链表中的节点全加到head链表的头顶,而list_splice_tail则是把原本list链表中的节点全加到head链表的尾部。

2. 二叉树

树是一种相比紧要的数据结构,更加是二叉树。二叉树是一种新鲜的树,在二叉树中每个节点最多有多少个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序无法随意颠倒。二叉树是递归定义的,由此,与二叉树有关的题目基本都得以用递归思想解决,当然有些题目非递归解法也相应领悟,如非递归遍历节点等等

8.2.2 邻接表表示法

图的邻接矩阵存储方法跟树的男女链表示法相近似,是一种顺序分配和链式分配相结合的积存结构。邻接表由表头结点和表结点两有些构成,其中图中种种终端均对应一个存储在数组中的表头结点。如那一个表头结点所对应的终极存在相邻顶点,则把相邻顶点依次存放于表头结点所针对的单向链表中。如图8.12所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行仓储也会冒出数量冗余,表头结点A所指链表中设有一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点。

澳门金沙网投平台 2
 

有向图的邻接表有出边表和入边表(又称逆邻接表)之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点;入边表的表结点存放的则是指向表头结点的某个头顶点。如图8.13所示,图(b)和(c)分别为有向图(a)的出边表和入边表。

澳门金沙网投平台 3
 

以上所谈论的邻接表所表示的都是不带权的图,即使要代表带权图,可以在表结点中加进一个存放权的字段,其作用如图8.14所示。

澳门金沙网投平台 4
 

【注意】:寓目图8.14方可窥见,当删除存储表头结点的数组中的某一元素,有可能使部分表头结点索引号的转移,从而导致周边修改表结点的事态暴发。可以在表结点中直接存放指向表头结点的指针以缓解那一个问题(在链表中存放类实例即是存放指针,但必需要保障表头结点是类而不是结构体)。在实际上创立邻接表时,甚至可以利用链表代替数组存放表头结点或选拔种种表存代替链表存放表结点。对所学的数据结构知识应当依据真实情形及所采用语言的风味灵活运用,切不可东施效颦。

【例8-1 
AdjacencyList.cs】图的邻接表存储结构

using System;
using System.Collections.Generic;
public class AdjacencyList<T>
{
    List<Vertex<T>> items; //图的终点集合
    public AdjacencyList() : this(10) { } //构造方法
    public AdjacencyList(int capacity) //指定容量的构造方法
    {
        items = new List<Vertex<T>>(capacity);
    }
    public void AddVertex(T item) //添加一个巅峰
    {   //不容许插入重复值
        if (Contains(item))
        {
            throw new ArgumentException(“插入了再次顶点!”);
        }
        items.Add(new Vertex<T>(item));
    }
    public void AddEdge(T from, T to) //添加无向边
    {
        Vertex<T> fromVer = Find(from); //找到起头顶点
        if (fromVer == null)
        {
            throw new ArgumentException(“头顶点并不存在!”);
        }
        Vertex<T> toVer = Find(to); //找到为止顶点
        if (toVer == null)
        {
            throw new ArgumentException(“尾顶点并不存在!”);
        }
        //无向边的八个顶峰都需记上边音信
        AddDirectedEdge(fromVer, toVer);
        AddDirectedEdge(toVer, fromVer);
    }
    public bool Contains(T item) //查找图中是不是带有某项
    {
        foreach (Vertex<T> v in items)
        {
            if (v.data.Equals(item))
            {
                return true;
            }
        }
        return false;
    }
    private Vertex<T> Find(T item) //查找指定项并赶回
    {
        foreach (Vertex<T> v in items)
        {
            if (v.data.Equals(item))
            {
                return v;
            }
        }
        return null;
    }
    //添加有向边
    private void AddDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer)
    {
        if (fromVer.firstEdge == null) //无邻接点时
        {
            fromVer.firstEdge = new Node(toVer);
        }
        else
        {
            Node tmp, node = fromVer.firstEdge;
            do
            {   //检查是否添加了双重边
                if (node.adjvex.data.Equals(toVer.data))
                {
                    throw new ArgumentException(“添加了再次的边!”);
                }
                tmp = node;
                node = node.next;
            } while (node != null);
            tmp.next = new Node(toVer); //添加到链表未尾
        }
    }
    public override string ToString() //仅用于测试
    {   //打印每个节点和它的邻接点
        string s = string.Empty;
        foreach (Vertex<T> v in items)
        {
            s += v.data.ToString() + “:”;
            if (v.firstEdge != null)
            {
                Node tmp = v.firstEdge;
                while (tmp != null)
                {
                    s += tmp.adjvex.data.ToString();
                    tmp = tmp.next;
                }
            }
            s += “\r\n”;
        }
        return s;
    }
    //嵌套类,表示链表中的表结点
    public class Node
    {
        public Vertex<T> adjvex; //邻接点域
        public Node next; //下一个邻接点指针域
        public Node(Vertex<T> value)
        {
            adjvex = value;
        }
    }
    //嵌套类,表示存放于数组中的表头结点
    public class Vertex<TValue>
    {
        public TValue data; //数据
        public Node firstEdge; //邻接点链表头指针
        public Boolean visited; //访问标志,遍历时使用
        public Vertex(电视alue value) //构造方法
        {
            data = value;
        }
    }
}

 

AdjacencyList<T>类应用泛型已毕了图的邻接表存储结构。它涵盖多少个里面类,Vertex<Tvalue>类(109~118行代码)用于表示一个表头结点,Node类(99~107)则用来表示表结点,其中存放着邻接点新闻,用来代表表头结点的某条边。多少个Node用next指针相连形成一个单链表,表头指针为Vertex类的firstEdge成员,表头结点所代表的终点的所有边的新闻均隐含在链表内,其结构如图8.12所示。所差距之处在于:

l         Vertex类中蕴藏了一个visited成员,它的效益是在图遍历时标识当前节点是或不是被访问过,那点在稍后会讲到。

l         邻接点指针域adjvex间接针对某个表头结点,而不是表头结点在数组中的索引。

AdjacencyList<T>类中行使了一个泛型List代替数组来保存表头结点音信(第5行代码),从而不再考虑数组存储空间不够的气象时有暴发,简化了操作。

出于一条无向边的新闻须要在边的五个顶峰分别存储新闻,即添加多少个有向边,所以58~78行代码的私房方法AddDirectedEdge()方法用于添加一个有向边。新的邻接点新闻即可以加上到链表的尾部也足以添加到底部,添加到链表尾部可以简化操作,但考虑到要反省是不是添加了双重边,需求遍历整个链表,所以最后把邻接点音讯添加到链表底部。

【例8-1 
Demo8-1.cs】图的邻接表存储结构测试

using System;
class Demo8_1
{
    static void Main(string[] args)
    {
        AdjacencyList<char> a = new AdjacencyList<char>();
        //添加顶点
        a.AddVertex(‘A’);
        a.AddVertex(‘B’);
        a.AddVertex(‘C’);
        a.AddVertex(‘D’);
        //添加边
        a.AddEdge(‘A’, ‘B’);
        a.AddEdge(‘A’, ‘C’);
        a.AddEdge(‘A’, ‘D’);
        a.AddEdge(‘B’, ‘D’);
        Console.WriteLine(a.ToString());
    }
}

运作结果:
 

A:BCD

B:AD

C:A

D:AB

 

本例存储的表如图8.12所示,结果中,冒号后面的是表头结点,冒号后面的是链表中的表结点。

list_for_each_entry_safe
也是逐三回历链表上节点嵌套的构造。只是加了去除节点的护卫。

1. 链表

链表的布局
链表最主题的构造是在各种节点保存数据和到下一个节点的地点,在终极一个节点保存一个例外的甘休标记。别的在一个固定的地方保存指向第二个节点的指针,有的时候也会同时储存指向最终一个节点的指针。但是也可以提前把一个节点的职位其余保存起来,然后径直访问。当然若是只是访问数据就没须要了,不如在链表上囤积指向实际多少的指针。这样一般是为着访问链表中的下一个要么前一个节点。
优势:可以打败数组链表必要事先精晓数据大小的欠缺,链表结构得以丰盛利用统计机内存空间,完毕灵活的内存动态管理。链表最显然的好处就是,常规数组排列关联项目标方法恐怕差异于那个数量项目在记念体或磁盘上相继,数据的存取往往要在差别的排列顺序中改换。而链表是一种自我提示数据类型,因为它包括指向另一个平等类其他数量的指针(链接),同时,链表允许插入和移除表上任意地方上的节点。
逆风局:链表由于增添了结点的指针域,空间开发相比较大;此外,链表失去了数组随机读取的长处,一般查找一个节点的时候必要从首个节点开头每一回访问下一个节点,一贯访问到需求的职位。

单向链表
链表中最简单易行的一种是单向链表,
一个单向链表的节点被分为三个部分。它富含多个域,一个音信域和一个指针域。第二个部分保存仍旧展现关于节点的音信,第三个部分存储下一个节点的地址,而最终一个节点则指向一个空值。单向链表只可向一个样子遍历。

双向链表
双向链表其实是单链表的修正,当咱们对单链表举行操作时,有时你要对某个结点的直白四驱进行操作时,又必须从表头初步查找。那是由单链表结点的构造所界定的。因为单链表每个结点唯有一个仓储直接后继结点地址的链域,那么能不可能定义一个既有囤积直接后继结点地址的链域,又有囤积直接后驱结点地址的链域的如此一个双链域结点结构吧?那就是双向链表。
在双向链表中,结点除含有数据域外,还有八个链域,一个囤积直接后继结点地址,一般称之为右链域(当此“连接”为最终一个“连接”时,指向空值或者空列表);一个储存间接前驱结点地址,一般称之为左链域(当此“连接”为第三个“连接”时,指向空值或者空列表)。

循环链表
循环链表是与单向链表一样,是一种链式的囤积结构,所例外的是,循环链表的最终一个结点的指针是指向该循环链表的首个结点或者表头结点,从而组合一个环形的链。
循环链表的运算与单链表的运算基本一致。所例外的有以下几点:
1、在确立一个循环链表时,必须使其最终一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种意况还使用于在最终一个结点后插入一个新的结点。
2、在认清是不是到表尾时,是判断该结点链域的值是或不是是表头结点,当链域值等于表头指针时,表达已到表尾。而非象单链表那样判断链域值是不是为NULL。

块状链表
块状链表本身是一个链表,不过链表储存的并不是形似的数额,而是由那么些数据整合的顺序表。每一个块状链表的节点,也就是顺序表,可以被誉为一个块。
块状链表另一个风味是对峙于常常链表来说节省外存,因为不用保存指向每一个数目节点的指针。

其它相关
链表的提议紧要在于:顺序存储中的插入和删除的年月复杂度是线性时间的,而链表的操作则可以是常数时间的复杂度。
链表的插入与删除操作顺序:
安插操作处理顺序:中间节点的逻辑,后节点逻辑,前节点逻辑。
删去操作的处理顺序:前节点逻辑,后节点逻辑,中间节点逻辑。

8.3.3  非连通图的遍历

上述啄磨的图的两种遍历方法都是对峙于无向连通图的,它们都是从一个极端出发就能访问到图中的所有终端。若无向图是非连通图,则只能访问到开头点所在连通分量中的所有终端,其他连接分量中的顶点是不容许访问到的(如图8.17所示)。为此必要从其他种种连通分量中甄选早先点,分别开展遍历,才可以访问到图中的所有终端,否则不可能访问到所有终端。为此如出一辙要求再选伊始点,继续展开遍历,直到图中的所有终端都被访问过得了。

澳门金沙网投平台 5
 

上例的代码只需对DFSTraverse()方法和BFSTraverse()方法稍作修改,便可以遍历非连通图。

 public void DFSTraverse() //深度优先遍历
    {
        InitVisited(); //将visited标志全体置为false
        foreach (Vertex<T> v in items)
        {
            if (!v.visited) //若是未被访问
            {
                DFS(v); //深度优先遍历
            }
        }
    }
    public void BFSTraverse() //广度优先遍历
    {
        InitVisited(); //将visited标志全部置为false
        foreach (Vertex<T> v in items)
        {
            if (!v.visited) //即使未被访问
            {
                BFS(v); //广度优先遍历
            }
        }
    }

list_for_each循环遍历链表中的每个节点,从链表尾部的首先个节点,一直到链表底部。中间的prefetch是为着利用阳台特色增加速度链表遍历,在一些平台下定义为空,可以忽略。

4. 简短算法

二分查找-递归方法
二分查找-非递归方法
冒泡排序

- (void)testBuble
{
    int temp;
    int array[8] = {1,24,56,34,67,78,324,43};
    for (int i = 0; i<8-1; i++) {
        for (int j = 0; j<8-1-i; j++) {
            if(array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }

        }
    }
    for (int i = 0; i<8; i++) {
        NSLog(@"%d",array[i]);
    }


    quickSort(array,0,7);

}

快速排序

//快速排序  调用方法  quickSort(a,0,n);  θ(nlogn)
void quickSort (int a[] , int low , int high)
{
    if (high < low + 2)
        return;
    int start = low;
    int end = high;
    int temp;

    while (start < end)
    {
        while ( ++start < high && a[start] <= a[low]);//找到第一个比a[low]数值大的位子start

        while ( --end  > low  && a[end]  >= a[low]);//找到第一个比a[low]数值小的位子end

        //进行到此,a[end] < a[low] < a[start],但是物理位置上还是low < start < end,因此接下来交换a[start]和a[end],于是[low,start]这个区间里面全部比a[low]小的,[end,hight]这个区间里面全部都是比a[low]大的

        if (start < end)
        {
            temp = a[start];
            a[start]=a[end];
            a[end]=temp;
        }
        //在GCC编译器下,该写法无法达到交换的目的,a[start] ^= a[end] ^= a[start] ^= a[end];编译器的问题
    }
    //进行到此,[low,end]区间里面的数都比a[low]小的,[end,higt]区间里面都是比a[low]大的,把a[low]放到中间即可

    //在GCC编译器下,该写法无法达到交换的目的,a[low] ^= a[end] ^= a[low] ^= a[end];编译器的问题

    temp = a[low];
    a[low]=a[end];
    a[end]=temp;

    //现在就分成了3段了,由最初的a[low]枢纽分开的
//    quickSort(a, low, end);
    quickSort(a, start, high);
    for (int i = 0; i<8; i++) {
        printf("\n%d\n",a[i]);
    }
}

8.3.1  深度优先搜索遍历

图的纵深优先搜索遍历类似于二叉树的深度优先搜索遍历。其主导思维如下:假定以图中某个顶点Vi为落脚点,首先走访出发点,然后选用一个Vi的未访问过的邻接点Vj,以Vj为新的落脚点继续拓展深度优先搜索,直至图中拥有终端都被访问过。显著,那是一个递归的查找进程。

现以图8.15为例表明深度优先搜索进度。假定V1是观点,首先访问V1。因V1有多少个邻接点V2、V3均末被访问过,可以选择V2作为新的着眼点,访问V2之后,再找V2的末访问过的邻接点。同V2分界的有V1、V4和V5,其中V1已被访问过,而V4、V5从没被访问过,可以拔取V4作为新的角度。重复上述搜索进度,继续依次访问V8、V5 。访问V5之后,由于与V5相邻的巅峰均已被访问过,搜索退回到V8,访问V8的另一个邻接点V6。接下来依次访问V3和V7,最终取得的的终极的造访系列为:V1 → V2 → V4 → V8 → V5 → V6 → V3 → V7

澳门金沙网投平台 6

 

上面依照上一节创制的邻接表存储结构充裕深度优先搜索遍历代码。

【例8-2 
DFSTraverse.cs】深度优先搜索遍历

开拓【例8-1 
AdjacencyList.cs】,在AdjacencyList<T>类中添加以下代码后,将文件另存为DFSTraverse.cs。

35      public void DFSTraverse() //深度优先遍历
36      {
37          InitVisited(); //将visited标志全体置为false
38          DFS(items[0]); //从第二个顶峰开端遍历
39      }
40      private void DFS(Vertex<T> v) //使用递归举行深度优先遍历
41      {
42          v.visited = true; //将访问标志设为true
43          Console.Write(v.data + ” “); //访问
44          Node node = v.firstEdge;
45          while (node != null) //访问此顶点的持有邻接点
46          {   //如果邻接点未被访问,则递归访问它的边
47              if (!node.adjvex.visited)
48              {
49                  DFS(node.adjvex); //递归
50              }
51              node = node.next; //访问下一个邻接点
52          }
53      }

98      private void InitVisited() //初始化visited标志
99      {
100         foreach (Vertex<T> v in items)
101         {
102             v.visited = false; //全体置为false
103         }
104     }

 

【例8-2 
Demo8-2.cs】深度优先搜索遍历测试

using System;
class Demo8_2
{
    static void Main(string[] args)
    {
        AdjacencyList<string> a = new AdjacencyList<string>();
        a.AddVertex(“V1”);
        a.AddVertex(“V2”);
        a.AddVertex(“V3”);
        a.AddVertex(“V4”);
        a.AddVertex(“V5”);
        a.AddVertex(“V6”);
        a.AddVertex(“V7”);
        a.AddVertex(“V8”);
        a.AddEdge(“V1”, “V2”);
        a.AddEdge(“V1”, “V3”);
        a.AddEdge(“V2”, “V4”);
        a.AddEdge(“V2”, “V5”);
        a.AddEdge(“V3”, “V6”);
        a.AddEdge(“V3”, “V7”);
        a.AddEdge(“V4”, “V8”);
        a.AddEdge(“V5”, “V8”);
        a.AddEdge(“V6”, “V8”);
        a.AddEdge(“V7”, “V8”);
        a.DFSTraverse();
    }
}

 

运转结果:

 

V1 V2 V4 V8 V5 V6 V3
V7

 

本例参照图8-15拓展设计,运行进程请参考对图8-15所作的辨析。

  1. static inline void list_replace(struct list_head *old,  
  2.                 struct list_head *new)  
  3. {  
  4.     new->next = old->next;  
  5.     new->next->prev = new;  
  6.     new->prev = old->prev;  
  7.     new->prev->next = new;  
  8. }  
  9.   
  10. static inline void list_replace_init(struct list_head *old,  
  11.                     struct list_head *new)  
  12. {  
  13.     list_replace(old, new);  
  14.     INIT_LIST_HEAD(old);  
  15. }  
3. 哈希表

散列表(Hash table,也叫哈希表),是依照重点码值(Key
value)而直白举办访问的数据结构。也就是说,它经过把重大码值映射到表中一个职位来拜会记录,以加速查找的进程。那些映射函数叫做散列函数,存放记录的数组叫做散列表。
给定表M,存在函数f(key),对轻易给定的要害字值key,代入函数后若能收获包含该重大字的记录在表中的地方,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash)
函数

8.3 图的遍历

和树的遍历类似,在此,我们期待从图中某一顶点出发访遍图中其它顶点,且使每一个极端仅被访问三遍,这一历程就叫做图的遍历(TraversingGraph)。若是只访问图的终极而不关心边的音讯,那么图的遍历至极简易,使用一个foreach语句遍历存放顶点音讯的数组即可。但若是为了完毕特定算法,就须要按照边的新闻根据一定顺序举行遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的底子。

图的遍历要比树的遍历复杂得多,由于图的任一顶点都可能和其它顶点相邻接,故在拜访了某顶点之后,可能顺着某条边又走访到了已走访过的终极,由此,在图的遍历进程中,必须记录每个访问过的终点,以免同一个极限被访问很多次。为此给顶点附设访问标志visited,其初值为false,一旦某个顶点被访问,则其visited标志置为true。

图的遍历方法有三种:一种是深度优先搜索遍历(Depth-First Search 简称DFS);另一种是广度优先搜索遍历(Breadth_First Search
简称BFS)。

  1. #define list_for_each_entry_continue(pos, head, member)         \
      
  2.     for (pos = list_entry(pos->member.next, typeof(*pos), member);   \  
  3.          prefetch(pos->member.next), &pos->member != (head);  \  
  4.          pos = list_entry(pos->member.next, typeof(*pos), member))  

8.2.1  邻接矩阵表示法

对此一个所有n个顶点的图,可以使用n*n的矩阵(二维数组)来表示它们间的分界关系。图8.10和图8.11中,矩阵A(i,j)=1表示图中留存一条边(Vi,Vj),而A(i,j)=0代表图中不设有边(Vi,Vj)。实际编程时,当图为不带权图时,可以在二维数组中存放bool值,A(i,j)=true表示存在边(Vi,Vj),A(i,j)=false表示不存在边(Vi,Vj);当图带权值时,则足以一贯在二维数组中存放权值,A(i,j)=null表示不设有边(Vi,Vj)。

 

澳门金沙网投平台 7
 

图8.10所示的是无向图的邻接矩阵表示法,可以洞察到,矩阵延对角线对称,即A(i,j)= A(j,i)。无向图邻接矩阵的第i行或第i列非零元素的个数其实就是第i个顶峰的度。那代表无向图邻接矩阵存在一定的数据冗余。

图8.11所示的是有向图邻接矩阵表示法,矩阵并不延对角线对称,A(i,j)=1表示顶点Vi邻接到顶点Vj;A(j,i)=1则象征顶点Vi交界自顶点Vj。两者并不象无向图邻接矩阵那样表示一致的意味。有向图邻接矩阵的第i行非零元素的个数其实就是第i个顶峰的出度,而第i列非零元素的个数是第i个顶峰的入度,即第i个极点的度是第i行和第i列非零元素个数之和。

由于存在n个顶点的图须求n2个数组元素举行仓储,当图为稀疏图时,使用邻接矩阵存储方法将出现多量零元素,照成极大地空间浪费,那时应该运用邻接表表示法存储图中的数据。

  1. #define list_for_each_entry_safe(pos, n, head, member)          \
      
  2.     for (pos = list_entry((head)->next, typeof(*pos), member),   \  
  3.         n = list_entry(pos->member.next, typeof(*pos), member);  \  
  4.          &pos->member != (head);                     \  
  5.          pos = n, n = list_entry(n->member.next, typeof(*n), member))  

 

  1. static inline int list_is_singular(const struct list_head *head)  
  2. {  
  3.     return !list_empty(head) && (head->next == head->prev);  
  4. }  

双向循环链表的贯彻,很少有例外情况,基本都足以用公家的章程来处理。那里无论是加第三个节点,依旧其余的节点,使用的措施都同样。

list_splice的机能和list_cut_position正相反,它合并八个链表。list_splice把list链表中的节点出席head链表中。在实际操作从前,要先判断list链表是不是为空。它保险调用__list_splice时list链表中足足有一个节点可以被合并到head链表中。

__list_for_each与list_for_each没什么不相同,只是少了prefetch的内容,达成上越来越简单易懂。

list_replace是将链表中一个节点old,替换为另一个节点new。从落到实处来看,即便old所在地链表唯有old一个节点,new也可以成功替换,那就是双向循环链表可怕的通用之处。

list_move的职能是把list节点从原链表中去除,并参与新的链表head中。

list_for_each_entry_safe_reverse
是从pos的前一个布局指针开始,逆序遍历链表上的结构指针,同时加了节点删除爱抚。

  1. static inline int list_empty(const struct list_head *head)  
  2. {  
  3.     return head->next == head;  
  4. }  
  5.   
  6. static inline int list_empty_careful(const struct list_head *head)  
  7. {  
  8.     struct list_head *next = head->next;  
  9.     return (next == head) && (next == head->prev);  
  10. }  

list_splice_init
除了落成list_splice的效益,还把变空了的list链表头重新最先化。

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图