图的遍历,简单询问数据结构与算法

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
}

在linux内核中,有一种通用的双向循环链表,构成了各个队列的底子。链表的协会定义和连锁函数均在include/linux/list.h中,下边就来周详的牵线这一链表的各类API。

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

 

<?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
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
  1. struct list_head {  
  2.     struct list_head *next, *prev;  
  3. };  
1. 链表

链表的结构
链表最宗旨的协会是在各种节点保存数据和到下一个节点的地点,在终极一个节点保存一个非正规的完成标记。别的在一个永恒的岗位保存指向第四个节点的指针,有的时候也会同时储存指向最终一个节点的指针。不过也能够提前把一个节点的岗位别的保存起来,然后直接访问。当然假诺只是访问数据就没须要了,不如在链表上囤积指向实际多少的指针。那样一般是为了访问链表中的下一个要么前一个节点。
优势:可以摆平数组链表要求事先驾驭数码大小的缺陷,链表结构可以充裕利用统计机内存空间,达成灵活的内存动态管理。链表最明确的益处就是,常规数组排列关联项目标方法恐怕分歧于这么些数据项目在回想体或磁盘上相继,数据的存取往往要在区其余排列顺序中改换。而链表是一种自己提示数据类型,因为它包蕴指向另一个一如既往档次的数据的指针(链接),同时,链表允许插入和移除表上任意地点上的节点。
劣势:链表由于扩展了结点的指针域,空间开发相比较大;别的,链表失去了数组随机读取的长处,一般查找一个节点的时候要求从第三个节点开头每一回访问下一个节点,一贯访问到须求的岗位。

单向链表
链表中最简便易行的一种是单向链表,
一个单向链表的节点被分成四个部分。它涵盖三个域,一个音信域和一个指针域。第三个部分保存或者呈现关于节点的音讯,第一个部分存储下一个节点的地点,而结尾一个节点则针对一个空值。单向链表只可向一个主旋律遍历。

双向链表
双向链表其实是单链表的改正,当我们对单链表进行操作时,有时你要对某个结点的直白后驱进行操作时,又不可以不从表头发轫查找。那是由单链表结点的结构所界定的。因为单链表每个结点唯有一个囤积间接后继结点地址的链域,那么能无法定义一个既有囤积直接后继结点地址的链域,又有囤积直接前驱结点地址的链域的这么一个双链域结点结构吧?那就是双向链表。
在双向链表中,结点除含有数据域外,还有多少个链域,一个囤积直接后继结点地址,一般称之为右链域(当此“连接”为最后一个“连接”时,指向空值或者空列表);一个储存间接后驱结点地址,一般称之为左链域(当此“连接”为第二个“连接”时,指向空值或者空列表)。

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

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

其他连锁
链表的提出重点在于:顺序存储中的插入和删除的时间复杂度是线性时间的,而链表的操作则可以是常数时间的复杂度。
链表的插入与删除操作顺序:
插入操作处理顺序:中间节点的逻辑,后节点逻辑,前节点逻辑。
删去操作的拍卖顺序:前节点逻辑,后节点逻辑,中间节点逻辑。

8.2 图的仓储结构

图的蕴藏结构除了要存储图中逐条顶点的自家的新闻外,同时还要存储顶点与终点之间的具有涉及(边的新闻),因而,图的构造相比较复杂,很为难数据元素在存储区中的物理地方来代表元素之间的涉及,但也正是出于其自由的风味,故物理表示方法很多。常用的图的蕴藏结构有邻接矩阵、邻接表、十字链表和毗邻多重表。

 

那是链表的因素结构。因为是循环链表,表头和表中节点都是这一结构。有prev和next五个指针,分别指向链表中前一节点和后一节点。

2. 二叉树

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

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)。

 

www.5929.com 1
 

图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_HEAD_INIT(name) { &(name), &(name) }
      
  2.   
  3. #define LIST_HEAD(name) \   
  4.     struct list_head name = LIST_HEAD_INIT(name)  
  5.   
  6. static inline void INIT_LIST_HEAD(struct list_head *list)  
  7. {  
  8.     list->next = list;  
  9.     list->prev = list;  
  10. }  
3. 哈希表

散列表(Hash table,也叫哈希表),是根据重大码值(Key
value)而直白进行访问的数据结构。也就是说,它经过把重大码值映射到表中一个任务来走访记录,以加速查找的快慢。那一个映射函数叫做散列函数,存放记录的数组叫做散列表。
给定表M,存在函数f(key),对轻易给定的紧要字值key,代入函数后若能取得包蕴该重大字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash)
函数

8.2.2 邻接表表示法

图的邻接矩阵存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的储存结构。邻接表由表头结点和表结点两片段组成,其中图中每个终端均对应一个仓储在数组中的表头结点。如这几个表头结点所对应的巅峰存在相邻顶点,则把附近顶点依次存放于表头结点所指向的单向链表中。如图8.12所示,表结点存放的是邻接顶点在数组中的索引。对于无向图来说,使用邻接表进行仓储也会现出数量冗余,表头结点A所指链表中存在一个指向C的表结点的还要,表头结点C所指链表也会存在一个指向A的表结点。

www.5929.com 2
 

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

www.5929.com 3
 

如上所谈论的邻接表所代表的都是不带权的图,要是要表示带权图,可以在表结点中扩大一个存放权的字段,其意义如图8.14所示。

www.5929.com 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所示,结果中,冒号前边的是表头结点,冒号前面的是链表中的表结点。

在开首化的时候,链表头的prev和next都是指向自身的。

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 图的遍历

和树的遍历类似,在此,大家期望从图中某一顶点出发访遍图中其余顶点,且使每一个巅峰仅被访问一次,这一进程就叫做图的遍历(TraversingGraph)。若是只访问图的极限而不关切边的音讯,那么图的遍历格外差不离,使用一个foreach语句遍历存放顶点音讯的数组即可。但借使为了落到实处特定算法,就需求依照边的音讯按照一定顺序举行遍历。图的遍历算法是求解图的连通性难题、拓扑排序和求关键路径等算法的根基。

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

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

  1. static inline void __list_add(struct list_head *new,  
  2.                   struct list_head *prev,  
  3.                   struct list_head *next)  
  4. {  
  5.     next->prev = new;  
  6.     new->next = next;  
  7.     new->prev = prev;  
  8.     prev->next = new;  
  9. }  
  10.   
  11. static inline void list_add(struct list_head *newstruct list_head *head)  
  12. {  
  13.     __list_add(new, head, head->next);  
  14. }  
  15.   
  16. static inline void list_add_tail(struct list_head *newstruct list_head *head)  
  17. {  
  18.     __list_add(new, head->prev, head);  
  19. }  
5. 架构

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

www.5929.com 5

 

上面遵照上一节创设的邻接表存储结构丰盛深度优先搜索遍历代码。

【例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所作的分析。

双向循环链表的落到实处,很少有例外情形,基本都可以用公家的法子来处理。那里无论是加第二个节点,如故别的的节点,使用的点子都同一。

8.3.2  广度优先搜索遍历

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

www.5929.com 6
 

和二叉树的广度优先搜索遍历类似,图的广度优先搜索遍历也必要依靠队列来成功,例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); //进队
www.5929.com,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进展辨析。

除此以外,链表API落到实处时大概都是分为两层:一层外部的,如list_add、list_add_tail,用来驱除一些例外意况,调用内部贯彻;一层是中间的,函数名前会加双下划线,如__list_add,往往是多少个操作公共的部分,或者免除例外后的兑现。

8.3.3  非连通图的遍历

上述研商的图的三种遍历方法都是相持于无向连通图的,它们都是从一个巅峰出发就能访问到图中的所有终端。若无向图是非连通图,则只好访问到起始点所在连通分量中的所有终端,其余连接分量中的顶点是不容许访问到的(如图8.17所示)。为此必要从其余种种连通分量中挑选先导点,分别进行遍历,才可以访问到图中的所有终端,否则不可以访问到独具终端。为此如出一辙要求再选开始点,继续拓展遍历,直到图中的所有终端都被访问过得了。

www.5929.com 7
 

上例的代码只需对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); //广度优先遍历
            }
        }
    }

  1. static inline void __list_del(struct list_head * prev, struct list_head * next)  
  2. {  
  3.     next->prev = prev;  
  4.     prev->next = next;  
  5. }  
  6.   
  7. static inline void list_del(struct list_head *entry)  
  8. {  
  9.     __list_del(entry->prev, entry->next);  
  10.     entry->next = LIST_POISON1;  
  11.     entry->prev = LIST_POISON2;  
  12. }  
  13.   
  14. static inline void list_del_init(struct list_head *entry)  
  15. {  
  16.     __list_del(entry->prev, entry->next);  
  17.     INIT_LIST_HEAD(entry);  
  18. }  

list_del是链表中节点的删除。之所以在调用__list_del后又把被删除元素的next、prev指向特殊的LIST_POSITION1和LIST_POSITION2,是为着调节未定义的指针。

list_del_init则是剔除节点后,随即把节点中指针再度起初化,那种删除格局越来越实用。

  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. }  

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

list_replace_init将被替换的old随即又先导化。

  1. static inline void list_move(struct list_head *list, struct list_head *head)  
  2. {  
  3.     __list_del(list->prev, list->next);  
  4.     list_add(list, head);  
  5. }  
  6.   
  7. static inline void list_move_tail(struct list_head *list,  
  8.                   struct list_head *head)  
  9. {  
  10.     __list_del(list->prev, list->next);  
  11.     list_add_tail(list, head);  
  12. }  

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

list_move_tail只在进入新链表时与list_move有所分歧,list_move是加到head之后的链表尾部,而list_move_tail是加到head从前的链表尾部。

  1. static inline int list_is_last(const struct list_head *list,  
  2.                 const struct list_head *head)  
  3. {  
  4.     return list->next == head;  
  5. }  

list_is_last 判断list是或不是处于head链表的尾巴。

  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_empty 判断head链表是或不是为空,为空的意思就是唯有一个链表头head。

list_empty_careful 同样是判断head链表是不是为空,只是检查更为严谨。

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

list_is_singular
判断head中是不是唯有一个节点,即除链表头head外只有一个节点。

  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. }  
  12.   
  13. static inline void list_cut_position(struct list_head *list,  
  14.         struct list_head *head, struct list_head *entry)  
  15. {  
  16.     if (list_empty(head))  
  17.         return;  
  18.     if (list_is_singular(head) &&  
  19.         (head->next != entry && head != entry))  
  20.         return;  
  21.     if (entry == head)  
  22.         INIT_LIST_HEAD(list);  
  23.     else  
  24.         __list_cut_position(list, head, entry);  
  25. }  

list_cut_position
用于把head链表分为两个部分。从head->next一直到entry被从head链表中删去,加入新的链表list。新链表list应该是空的,或者原来的节点都可以被忽略掉。能够看来,list_cut_position中革除了一部分奇怪处境,保险调用__list_cut_position时至少有一个元素会被投入新链表。

  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.   
  8.     first->prev = prev;  
  9.     prev->next = first;  
  10.   
  11.     last->next = next;  
  12.     next->prev = last;  
  13. }  
  14.   
  15. static inline void list_splice(const struct list_head *list,  
  16.                 struct list_head *head)  
  17. {  
  18.     if (!list_empty(list))  
  19.         __list_splice(list, head, head->next);  
  20. }  
  21.   
  22. static inline void list_splice_tail(struct list_head *list,  
  23.                 struct list_head *head)  
  24. {  
  25.     if (!list_empty(list))  
  26.         __list_splice(list, head->prev, head);  
  27. }  

list_splice的效率和list_cut_position正相反,它合并几个链表。list_splice把list链表中的节点参与head链表中。在实际操作往日,要先判断list链表是不是为空。它保险调用__list_splice时list链表中最少有一个节点可以被联合到head链表中。

list_splice_tail只是在统一链表时插入的职分分歧。list_splice是把原先list链表中的节点全加到head链表的头顶,而list_splice_tail则是把本来list链表中的节点全加到head链表的尾部。

  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. }  
  9.   
  10. static inline void list_splice_tail_init(struct list_head *list,  
  11.                      struct list_head *head)  
  12. {  
  13.     if (!list_empty(list)) {  
  14.         __list_splice(list, head->prev, head);  
  15.         INIT_LIST_HEAD(list);  
  16.     }  
  17. }  

list_splice_init
除了完结list_splice的成效,还把变空了的list链表头重新伊始化。

list_splice_tail_init
除了完毕list_splice_tail的效应,还吧变空了得list链表头重新伊始化。

list操作的API大概如以上所列,包涵链表节点添加与删除、节点从一个链表转移到另一个链表、链表中一个节点被替换为另一个节点、链表的联结与拆分、查看链表当前是或不是为空或者唯有一个节点。接下来,是操作链表遍历时的一些宏,大家也简要介绍一下。

  1. #define list_entry(ptr, type, member) \
      
  2.     container_of(ptr, type, member)  

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

那种地点翻译的技巧是linux的拿手好戏,container_of随地可见,只是链表节点多被封装在更复杂的社团中,使用专门的list_entry定义也是为了使用方便。

  1. #define list_first_entry(ptr, type, member) \
      
  2.     list_entry((ptr)->next, type, member)  

list_first_entry是将ptr看完一个链表的链表头,取出其中第二个节点对应的构造地址。使用list_first_entry是应有限帮助链表中至少有一个节点。

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

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

  1. #define __list_for_each(pos, head) \
      
  2.     for (pos = (head)->next; pos != (head); pos = pos->next)  

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

  1. #define list_for_each_prev(pos, head) \
      
  2.     for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \  
  3.             pos = pos->prev)  

list_for_each_prev与list_for_each的遍历顺序相反,从链表尾逆向遍历到链表头。

  1. #define list_for_each_safe(pos, n, head) \
      
  2.     for (pos = (head)->next, n = pos->next; pos != (head); \  
  3.         pos = n, n = pos->next)  

list_for_each_safe
也是链表顺序遍历,只是尤其安全。即便在遍历进度中,当前节点从链表中除去,也不会影响链表的遍历。参数上急需加一个暂存的链表节点指针n。

  1. #define list_for_each_prev_safe(pos, n, head) \
      
  2.     for (pos = (head)->prev, n = pos->prev; \  
  3.          prefetch(pos->prev), pos != (head); \  
  4.          pos = n, n = pos->prev)  

list_for_each_prev_safe
与list_for_each_prev同样是链表逆序遍历,只是加了链表节点删除爱戴。

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

list_for_each_entry不是遍历链表节点,而是遍历链表节点所嵌套进的构造。这几个达成上比较复杂,但可以等价于list_for_each加上list_entry的组合。

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

list_for_each_entry_reverse
是逆序遍历链表节点所嵌套进的构造,等价于list_for_each_prev加上list_etnry的组合。

  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))  

list_for_each_entry_continue也是遍历链表上的节点嵌套的构造。只是不要从链表头早先,而是从社团指针的下一个布局先河,平素到链表尾部。

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

list_for_each_entry_continue_reverse
是逆序遍历链表上的节点嵌套的结构。只是不要从链表尾开首,而是从构造指针的前一个构造起首,一向到链表尾部。

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

list_for_each_entry_from
是从此时此刻布局指针pos伊始,顺序遍历链表上的协会指针。

  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))  

list_for_each_entry_safe
也是各种遍历链表上节点嵌套的构造。只是加了删减节点的保险。

  1. #define list_for_each_entry_safe_continue(pos, n, head, member)         \
      
  2.     for (pos = list_entry(pos->member.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))  

list_for_each_entry_safe_continue
是从pos的下一个构造指针开首,顺序遍历链表上的组织指针,同时加了节点删除爱戴。

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

list_for_each_entry_safe_from
是从pos初步,顺序遍历链表上的社团指针,同时加了节点删除爱抚。 

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

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

至此截至,大家介绍了linux中双向循环链表的结构、所有的操作函数和遍历宏定义。相信之后在linux代码中相见链表的利用,不会再陌生。

www.5929.com 8

Leave a Comment.