精华内容
下载资源
问答
  • 我们对数据结构的理解达到了什么层次?我们需要达到的层次是什么? 第0层次:“数据结构是什么?” 第0层次是指对数据结构一无所知。我们从来没有听说过数据结构,从来没有注意到对数据进行合理的组织能够大幅度...

    我们对数据结构的理解达到了什么层次?我们需要达到的层次是什么?

    第0层次:“数据结构是什么?”

    第0层次是指对数据结构一无所知。我们从来没有听说过数据结构,从来没有注意到对数据进行合理的组织能够大幅度提升程序的运行效率。

    第1层次:“我听说过散列表,虽然不太明白,但感觉它很强大。”

    第1层次是鸡尾酒会[2]水平的认识度。在达到这个层次后,我们至少讨论过基本的数据结构。我们听说过一些像搜索树和散列表这样的基本数据结构,或许还注意到它们所支持的一些操作。但是,在程序中使用它们或者在技术面试中熟练分析它们仍然非常困难。

    第2层次:“这个问题看来需要用堆才能搞定。”

    在进入第2层次后,我们开始进入状态。我们已经熟练地掌握了数据结构的基础知识,可以在程序中熟练地使用各种数据结构,并对哪种类型的数据结构适用于哪种类型的编程任务有着良好的感觉。

    第3层次:“我只用自己手工定制的数据结构。”

    第3层次是最高级的层次,适合专家级程序员和计算机科学家,他们已经不满足仅仅以客户的身份使用现有的数据结构的实现。在进入这个层次之后,我们对基本数据结构的所有细节了如指掌,对它们的实现方式也是烂熟于心。

    最大的提升空间就是提升到第2层次。大多数程序员总会在某个时刻需要以客户的身份使用基本的数据结构,如堆、搜索树和散列表。《算法详解(卷1)》第4章至卷2第6章的主要目标是帮助读者把数据结构的理解能力提升到这个层次,并把注意力集中在它们所支持的操作以及它们的标准应用上。大多数现代编程语言的标准库提供了这些数据结构,我们可以在程序中便捷地使用它们。

    高级程序员有时候需要从头实现某种数据结构的自定义版本。第4-12章都包含一个关于这些数据结构的典型实现的小节。这些小节适合那些希望把自己对数据结构的理解提升到第3层次的读者。

    《算法详解(卷1)》第4章至卷2第6章到底有哪些内容?

    • 主方法

    本章讨论决定递归算法的运行时间的“黑盒”方法,并讨论递归算法的一些关键特性,然后推导出算法的运行时间上界。这种“主方法”适用于读者所看到的绝大多数分治算法,包括Karatsuba的整数相乘算法(第1.3节)和Strassen的矩阵相乘算法(第3.3节)[1]。本章还将描述算法研究中一个更通用的理论:对新奇的算法思路进行适当的评估常常需要不直观的数学分析。

    在第4.1节介绍了递归过程之后,我们将在第4.2节提供主方法的正式定义,并观察它的6个应用例子(第4.3节)。第4.4节讨论了主方法的证明,着重强调它的3种著名情况背后的含义。这个证明非常优雅地建立在第1.5节对MergeSort算法分析的基础之上。

    • 快速排序(QuickSort

    本章讨论快速排序(QuickSort)。如果要排个“算法名人堂”,快速排序应该能够第一批入选。在高级层次上地描述了该算法的工作原理之后(第5.1节),我们讨论怎样在线性时间内根据一个“基准(pivot)元素”对数组进行划分(第5.2节),并讨论如何选择良好的基准元素(第5.3节)。第5.4节讨论了随机化的QuickSort,第5.5节证明了它对n个元素的数组进行排序的渐进性平均运行时间为O(nlogn)。第5.6节证明不会有任何“基于比较”的排序算法能够比O(nlogn)更快,从而为排序的讨论画上了一个完美的句号。

    • 线性时间级的选择

    本章研究选择问题,它的目的是在一个未排序的数组中寻找第i小的元素。如果使用排序方法,很容易在O(n log n)时间内解决这个问题,但是我们想要做得更好。

    第6.1节描述了一种极端实用的随机化算法,它的精神与随机化的QuickSort非常相似,但它的平均运行时间达到了线性时间。第6.2节提供了这个算法的优雅分析,有一种很好的方法可以按照简单的掷硬币试验来推进这个算法,证明它具有线性时间期望值。

    倾向于理论的读者可能会疑惑怎么可能在不借助随机化的情况下在线性时间内解决选择问题。第6.3节描述了该问题的一种著名的确定性算法,参与该算法的图灵奖得主多于我所知道的其他任何算法的。它是一种确定性的算法(即不允许使用随机化),建立在一种独特的“中位的中位元素”思路之上,以保证选择了良好的基准元素。第6.4节证明了它的线性时间上界,这可不是个简单的任务!

    本章假设读者已经熟悉第5.2节的可以在线性时间内围绕一个基准元素对数组进行划分的Partition子程序,并对基准元素的好坏具有良好的直觉。

    • 图的基础知识免费

    本章将会简单地介绍图的概念、图的用途以及计算机程序中常见的图表示形式。接下来的两章将深入讨论一些著名的与图有关的实用算法。

    • 图的搜索及其应用

    本章讨论与图的搜索及其应用有关的基础知识。本章讨论的内容有一个特点,就是我们将要讨论的所有算法都具有令人惊叹的高速度(具有较小常数因子的线性时间),但它们的工作方式并不是特别容易理解。本章的重点——只用两遍深度优先的搜索就完成了有向图的强连通分量的计算(见2.6节),生动地描述了高速的算法往往需要我们对问题的结构具有深刻的洞察力。

    本章首先是概述内容(见2.1节),描述了一些为什么要关注图的搜索的原因,并描述了在不进行任何冗余工作的前提下对图进行搜索的一种通用策略。本节还对两种重要的搜索策略——宽度优先的搜索(BFS)和深度优先的搜索(DFS)——进行了高层次的描述。2.2节和2.3节详细描述了BFS,包括它在最短路径计算和无向图的连通分量的计算方面的应用。2.4节和2.5节深入探讨了DFS,并讨论了如何用它计算有向无环图的拓扑顺序(相当于在遵循优先级约束的前提下对任务进行序列化)。2.6节使用DFS在线性时间内计算有向图的强连通分量。2.7节解释了为什么这种快速图元可用于对Web的结构进行探索。

    • Dijkstra最短路径算法

    Dijkstra最短路径算法[1]。这个算法适用于边的长度均不为负数的有向图,它计算从一个起始顶点到其他所有顶点的最短路径的长度。在正式定义这个问题(3.1节)之后,我们讲解这个算法(3.2节)以及它的正确性证明(3.3节),然后介绍一个简单直接的实现(3.4节)。在第4章中,我们将看到这种算法的一种令人惊叹的快速实现,它充分利用了堆这种数据结构。

    • 堆数据结构

    本书剩余的3章分别讨论3种极为重要并且广泛使用的数据结构:堆、搜索树和散列表。我们的目标是了解这些数据结构所支持的操作(以及它们的运行时间),并通过应用实例培养读者识别哪种数据结构适用于哪种类型问题的能力。另外,我们还可以对它们的幕后实现方式有所了解。我们首先讨论堆,这种数据结构可以帮助我们实现最小值或最大值的快速计算。

    • 搜索树

    与堆相似,搜索树也是一种存储一个不断变化的与键相关联的对象(可能还有大量其他数据)集合的数据结构。它维护它所存储的对象的整体顺序,并支持比堆更丰富的操作集合,其代价就是需要更多的额外空间,并且有些操作的运行速度比堆更慢一些。在讨论“为什么(应用)”和“怎么样(可选的实现细节)”之前,我们首先讨论“什么(即支持的操作)”。

    • 散列表和布隆过滤器

    在本书的最后一章,我们讨论一种极其实用并且被广泛使用的数据结构,即散列表(又称散列映射)。与堆和搜索树相似,散列表维护一组不断变化的与键相关联的对象(每个对象可能还包含许多其他数据)。与堆和搜索树不同,散列表并不维护与顺序有关的信息。散列表的存在意义是因为它支持超级快速的搜索,在这种场合下又称为查找。散列表可以告诉我们数据结构中是否存在某个对象,并且真的能够做到极端快速(远远快于堆或搜索树)。与往常一样,我们首先讨论散列表所支持的操作(见6.1节),然后讨论它的应用(见6.1节)以及一些可选的实现细节(见6.3节和6.4节)。6.5节和与6.6节讨论了布隆过滤器,它与散列表相似,它需要的空间更少,但付出的代价是偶尔会出现错误。

    选择正确的数据结构

    在软件的主要部分中,经常会用到数据结构。因此,对于严谨的程序员而言,知道在什么时候以及怎样使用数据结构是一项重要的基本技巧。数据结构的存在意义是它可以对数据进行组织,使我们可以快速、实用地访问数据。我们已经看到了数据结构的一些例子。2.2节介绍的用于实现线性时间的宽度优先的搜索的队列数据结构采用了线性形式组织数据,可以实现在常数级时间内从队列的头部删除对象或者在队列的尾部添加对象。2.4节介绍了在深度优先的搜索的迭代性实现中起到重要作用的堆栈数据结构,它允许我们在常数级时间内在堆栈的头部添加或删除对象。

    我们可以使用的数据结构还有很多。在本系列图书中,我们将看到堆、二叉搜索树、散列表、布隆过滤器以及并查集(union-find,详见本系列图书的卷3)。为什么要列出这几个看上去颇为复杂的例子呢?因为不同的数据结构支持不同的操作集合,所以它们适用于不同类型的编程任务。例如,宽度优先的搜索和深度优先的搜索具有不同的需求,分别由两种不同的数据结构满足。Dijkstra最短路径算法的快速实现(见4.4节)还有一些不同的需求,需要使用更为复杂的堆数据结构。

    不同的数据结构的利弊是什么?我们应该怎样在程序中选择具体的数据结构呢?一般而言,一种数据结构所支持的操作越多,这些操作的速度也就越慢,它们所需要的空间开销也就越大。爱因斯坦的这句名言恰如其分地说明了这一点:“尽可能让事情变得简单,但不能过于简单。”

    在实现一个程序时,重要的是认真考虑它需要频繁执行的操作。例如,我们是不是只关心一些对象是否存储在一个数据结构中?或者还需要以一种特殊的方式对它们进行排序?一旦理解了程序的需要,我们就可以遵循精简原则,选择一种支持所有必要的操作同时又没有太多不必要操作的数据结构。

    精简原则
    选择能够支持应用程序所需要的所有操作的最简单数据结构。
    展开全文
  • 互联网的分层次结构

    千次阅读 2020-12-12 09:36:35
    互联网的分层次结构 生活中几个常用的网络概念 速率 比特(bit)是通信中信息量的单位,一个比特就是二进制数字中的一个1或0.网络中的速率也就是数据的传送速率,是指连接到计算机网络上的主机在数字信道上传送数据...

    互联网的分层次结构

    生活中几个常用的网络概念

    速率

    比特(bit)是通信中信息量的单位,一个比特就是二进制数字中的一个1或0.网络中的速率也就是数据的传送速率,是指连接到计算机网络上的主机在数字信道上传送数据的速率,也称数据率或比特率,单位为b/s(比特/秒,有时也写作bps).数据率较高时,可用kb/s(k=103)。Mb/s(M=106)或Gb/s(G=10^9)表示。在计算机网络中,通常把最高数据率称为带宽。

    带宽

    “带宽”(bandwidth)有以下两种不同的意义:

    1. 带宽本来是指某个信号具有的频带宽度。信号的带宽是指该信号所包含的各种不同频率成分所占据的频率范围。这种意义的带宽的单位是赫(或千赫、兆赫、吉赫等。)
    2. 在计算机网络中,带宽用来表示网络中某信道传送数据的能力,因此网络带宽表示在单位时间内网络中的某信道所能通过的“最高数据率。”这种意义的带宽的单位就是数据率党的单位:bit/s,即比特每秒。

    时延

    时延(delay或latency)是指数据(一个报文或分组)从网络(或链路)的一端传送到另一端所需的时间。时延又可以分为以下四种:

    1.发送时延。
    发送时延(transmission delay)是主机或路由器发送数据帧所需要的时间。
    2. 传播时延。
    传播时延(propagation delay)是电磁波在信道中传播一定的距离需要花费的时间。传播时延发生在机器外部的传输媒体上,信号传送的距离越远,传播时延越大。
    3. 处理时延。
    处理时延是主机或路由器在收到分组对分组进行去头去尾,差错检错,所花费的时间。
    4.排队时延。
    分组在进入路由器要等待路由器确认了转发接口后,在输出队列中排队等待转发。排队时延的长短取决于网络当时的通信量。

    计算机网络体系结构

    两个系统中实体间的通信是一个很复杂的过程,为了降低协议设计和调试过程的复杂性,也为了便于对网络进行研究、实现和维护,促进标准化工作,通常对计算机网络的体系结构以分层的方式进行建模。分层的目的是将庞大而复杂的问题转化为易于研究和处理的局部问题。

    计算机网络协议、服务的概念

    在计算机网络中要做到有条不紊地交换数据,就必须遵守一些事先约好的规则。这些为进行网络中的数据交换而建立的规则、标准或约定称为**网络协议(network Protocol)。**网络协议由语法、语义和同步三部分组成。语法规定了传输数据的格式;语义规定了所要完成的功能,即需要发出何种控制信息、完成何种动作及做出何种应答;同步规定了执行各种操作的条件、时序关系等。

    在协议的控制下,两个对等实体间的通信是的本层能够向上一层提供服务。要实现本层协议,还需要使用下面一层所提供的的服务。

    协议是水平的,但服务是垂直的。服务是指下层为紧邻的上层提供的功能调用,它是垂直的。对等实体在协议的控制下,使得本层能为上一层提供服务,但要实现本层协议还要使用下一层所提供的的服务。计算机网络提供以下三种方式的服务:

    面向连接服务于无连接服务
    在面向连接服务中,通信双方先建立连接,分配资源,再进行数据传输,数据传输完成后释放连接和所占用的资源。TCP就是一种面向连接服务的协议。
    在无连接服务中,通信双方不需要事先建立连接也不要释放连接,需要发送数据时直接发送。这种服务常被描述为“尽最大努力交付”(Best-Effort-Delivery),它是一种不可靠的服务。IP、UDP、就是无连接服务。

    可靠服务和不可靠服务
    可靠服务是指网络具有纠错、检错、应答机制,能保证数据正确、可靠地传送到目的地。
    不可靠服务是指网络只是尽量正确、可靠地传送,而不能保证数据正确、可靠地传送到目的地,是一种尽力而为的服务。

    有应答服务和无应答服务
    有应答服务是指接收方在收到数据后向发送方给出相应的应答。文件传输服务就是一种有应答服务。
    无应答服务是指接收方收到数据后不自动给出应答。例如,对于www服务,客户端收到服务器发送的页面文件后不给出应答。

    OSI参考模型和TCP/IP模型

    OSI参考模型。国际标准化组织ISO与1997年提出了一个试图使各种计算机在世界范围内互连成网的标准框架,即著名的开放系统互连基本参考模型OSI/RM(Open System Interconnection Reference Model),简称OSI。
    在这里插入图片描述

    OSI参考模型

    OSI有七层,自下而上依次为物理层、数据链层、网络层、传输层、会话层、表示层、应用层。下三层统称为通信子网,负责联网完成数据传输功能。上三层统称为资源子网,它相当于计算机系统,完成数据处理功能。最中间的传输层承上启下。

    TCP/IP模型。

    ARPA在研究ARPAnet时提出了TCP/IP模型,模型从低到高依次为网络接口层、网际层、传输层和应用层。由于基于TCP/IP的互联网抢先在全球大范围成功运行,所以得到最广泛应用的并不是法律上的国际标准OSI,而TCP/IP模型也被称为事实上的国际标准。在这里插入图片描述

    在学习计算机网络时,我们往往采用折中的方法,采用一种五层模型结构,即我们所熟知的物理层、数据链路层、网络层、传输层和应用层。

    (1) 应用层(application layer)
    应用层是体系结构中的最高层。应用层的任务是通过应用进程间的交互来完成特定网络应用。应用层协议定义的是应用进程间通信和交互的规则。对于不同的网络应用需要有不同的应用层协议。在互联网中的应用层协议很多,如域名系统DNS,支持万维网应用的HTTP协议,支持电子邮件的SMTP协议,等等。应用层交互的数据单元称为报文(message)。
    (2) 运输层(transport layer)
    运输层的任务就是负责向两台主机中进程之间的通信提供通用的数据传输服务>应用进程利用该服务传送应用层报文。
    运输层主要使用以下两种协议:
    传输控制协议TCP (Transmission Control Protocol)——提供面向连接的、可靠的数
    据传输服务,其数据传输的单位是报文段(segment)。
    用户数据报协议 UDP (User Datagram Protocol)——提供无连接的、尽最大努力(best-effort)的数据传输服务(不保证数据传输的可靠性),其数据传输的单位是用户数据报。
    (3)网络层(network layer)
    网络层负责为分组交换网上的不同主机提供通信服务。在发送数据时,网络层把运输层产生的报文段或用户数据报封装成分组或包进行传送。在TCP/IP体系中,由于网络层使用IP协议,因此分组也叫IP数据报,或前称为数据报。
    无论在哪一层传送的数据单元,都可笼统地用“分组”来表示。
    网络层的另一个往务最是要选择合适的路由,使源主机运输层所传下来的分组,能物通过网络中的路由器找到目的主机。
    (4) 数据链路层(data link layer)
    数据链路层常简称为链路层,在两个相邻结点之间传送数据时,数据链路层将网络层交下来的IP数据报组装成帧(framing),在两个相邻结点间的链路上传送帧(frame)。每一帧包括数据和必要的控制信息(如同步信息、地址信息、差错控制等)。
    在接收数据时,控制信息使接收端能够知道一个帧从哪个比特开始和到哪个比特结束。这样,数据链路层在收到一个帧后,就可从中提取出数据部分,上交给网络层。
    控制信息还使接收端能够检测到所收到的帧中有无差错。
    (5)物理层(physical layer)
    在物理层上所传数据的单位是比特。因此物理层要考虑用多大的电压代表“1”或“0”,以及接收方如何别出发送方所发送的比特。当然,解释比特代表的意思,就不是物理层的任务。请注意,传输介质,如双绞线、同轴电缆、光缆、无线信道等,并不属于物理层而是在理层协议的下面。因此也有人把物理层下面的物理媒体当作第0层。

    展开全文
  • 一、驱动程序层次结构   在《Windows...   要想详细解释驱动程序的层次结构,以我现在的水平可能还没那个能力,但或许能通过文字的形式让自己多一分认识。   1.再看DriverEntr

    一、驱动程序层次结构

     

    在《Windows驱动开发详解》的第四章简单介绍了一下驱动程序的层次结构,但介绍得不清不楚,反复看了几遍,仍然是一分清楚,九分糊涂。为此,花了几个小时来查阅相关资料,最后分别参考《Windows驱动开发详解》和《Windows操作系统原理第2版》,才算有了个初步的认识。

     

    要想详细解释驱动程序的层次结构,以我现在的水平可能还没那个能力,但或许能通过文字的形式让自己多一分认识。

     

    1.再看DriverEntry和HelloDDKDispatchRoutine函数

    要想理解驱动程序的层次结构,还得再来看看第一个驱动程序的大致流程。我们知道,驱动程序的入口函数是DriverEntry,而在DriverEntry函数中,对DRIVER_OBJECT结构体进行了初始化。其中MajorFunction成员是用来设置IRP对应的派遣函数,这样使用该驱动程序进行不同的I/O请求时,就会相应相应的派遣函数。下面是DriverEntry函数中对MajorFunction成员的初始化设置:

     

    pDriverObject->MajorFunction[IRP_MJ_CREATE] = ( PDRIVER_DISPATCH ) HelloDDKDispatchRoutine;
    pDriverObject->MajorFunction[IRP_MJ_CLOSE] = ( PDRIVER_DISPATCH ) HelloDDKDispatchRoutine;
    pDriverObject->MajorFunction[IRP_MJ_WRITE] = ( PDRIVER_DISPATCH ) HelloDDKDispatchRoutine;
    pDriverObject->MajorFunction[IRP_MJ_READ] = ( PDRIVER_DISPATCH ) HelloDDKDispatchRoutine;

     

    通过以上的初始化,在不同的处理不同的IRP时就会响应相应的派遣函数,接着我们就可以来看看这个传说中的派遣函数是什么样的了:

     

    NTSTATUS HelloDDKDispatchRoutine( IN PDEVICE_OBJECT pDevObj, IN PIRP pIrp )
    {
            KdPrint( ( "Enter HelloDDKDispatchRoutine!/n" ) );
            NTSTATUS status = STATUS_SUCCESS;

     

           //完成IRP
           pIrp->IoStatus.Status = status;
           pIrp->IoStatus.Information = 0;
           IoCompleteRequest( pIrp, IO_NO_INCREMENT );
           KdPrint( ( "Leave HelloDDKDispatchRoutine!/n" ) );

           return status;
    }

     

    函数体很简单,而在这个函数中,有一个很重要的结构体,那就是函数参数中的PIRP结构体。PIRP是一个很复杂的结构体,在以上这个派遣函数中,只用到了其中的一个结构体成员。那这个结构体中到底包含了些什么数据呢?这个很重要!

     

    2.PIRP结构体

     

    参考《Windows操作系统原理 9.2.4》中的解释,该结构体主要包含IRP请求类型、用户缓冲区首地址、用户请求数据的长度等信息,除此之外还包括这个IRP请求的处理结构,比如以上代码中的“ pIrp->IoStatus.Status = status;”。

     

    PIRP结构体有十多个成员,可以把该结构体分为两个部分:固定部分和一个I/O堆栈单元。其中固定部分主要包含一些IRP请求的基本信息,对于这一部分暂且略过。重中之重是I/O堆栈单元,因为我需要通过了解这一部分来弄清驱动程序的层次结构。

     

    3.IO_STACK_LOCATION结构体(I/O堆栈单元)

    I/O堆栈单元由IO_STACK_LOCATION定义,每一个堆栈单元都对应一个设备对象。我们知道,在一个驱动程序中,可以创建一个或多个设备对象,而这些设备对象都对应着一个IO_STACK_LOCATION结构体,而在驱动程序中的多个设备对象,而这些设备对象之间的关系为水平层次关系。好,到此可以理解驱动程序中的水平层次结构了,但还有一个垂直层次的结构需要理解。

    还得再说说IO_STACK_LOCATION这个结构体,从wdm.h中看了下这个结构体的定义,不看不知道,居然有几十个成员。还是到《Windows操作系统原理》中看看几个重要成员的作用吧:

    typedef struct _IO_STACK_LOCATION {

    UCHAR MajorFunction;
    UCHAR MinorFunction;
    UCHAR Flags;
    UCHAR Control;

    union Parameters;

    PDEVICE_OBJECT DeviceObject;

    PFILE_OBJECT FileObject;

    PIO_COMPLETION_ROUTINE CompletionRoutine;

    PVOID Context;

    通过以上的整理,发现之前所说的几十个成员都是Parameters联合中的,这就好说了,现在一个一个的来了解这些成员的作用,还是回到《Windows操作系统原理》中。

    MajorFuncion是该IRP的主要功能,它指出了I/O请求的操作类型。

    MinorFunction是该IRP的副功能,这个参数在《Windows驱动开发详解》中没作详解的解释,我也就先不作了解。

    parameters是多个结构体的联合,再到wdm.h中看了看,忽然明白了什么,原来这个联合中的每一个结构体,都包含了每一个IRP类型的数据,可以看看IRP_MJ_CREATE这个IRP相应的结构体定义:

    struct {
                PIO_SECURITY_CONTEXT SecurityContext;
                ULONG Options;
                USHORT POINTER_ALIGNMENT FileAttributes;
                USHORT ShareAccess;
                ULONG POINTER_ALIGNMENT EaLength;
            } Create;

    这个结构体中具体的数据就先不管了,至少已经知道parameters中存放的是些什么数据。

    DeviceObject是当前IRP对应的设备对象的地址。

    FileObject是指向与一个I/O请求有关的文件对象地址。对这个参数没什么认识,先略过。

    CompletionRoutine是一个I/O完成例程的地址。该地址是由与这个堆栈单元对应的驱动程序的更上一层驱动程序设置的,驱动程序不要直接设置这个域。这段文字是直接抄《Windows操作系统原理》上的,不太理解。

    Context。是一个任意的与上下文相关的值,将作为参数传递给完成例程。

    在《Windows操作系统原理》中没有对Flags和Control这两个参数作介绍。

    通过以上的整理,对于PIRP的数据结构虽然不能清楚认识,但至少也有了一定的理解。之所以要熟PIRP的数据结构,是因为要了解IO_STACK_LOCATION这个结构体,而了解IO_STACK_LOCATION结构体的目的是为了明白驱动程序的层次结构。

    4.入正题,了解驱动程序的层次结构

    前面已经说到,每个驱动程序中的多个设备对象的关系是水平层次关系,而在了解了IO_STACK_LOCATION结构体后,就要说说驱动程序中的垂直层次结构了。

    在认识垂直层次结构之前,还得先了解几个概念:

    FiDO(Filter Device Object) 过滤器设备对象
    FDO(Functional Device Object) 功能设备对象
    PDO(Physical Device Object) 物理设备对象

    要了解垂直层次结构,情况就变得复杂多了,这涉及到Windows操作系统原理,我对这方面的认识很少。

    “设备的创建顺序是,先创建底层PDO,再创建高层FDO,这也是设备堆栈的生长方向,即从底层设备到高层设备。在PDO和FDO中夹杂着各种过滤驱动。每层的设备对象由不同的驱动程序所创建,或者说每层的设备对应着不同的驱动程序。有的驱动程序是系统自带的,有的是需要程序员编写。底层设备对象寻找上一层的设备对象,是依靠底层设备对象的AttachedDevice来寻找的,如果某一设备的AttachedDevice为空,说明已经到了设备堆栈的顶部。”

    以上是引用《Windows驱动开发详解》中第四章中的一段话,对于这段话,我对其中的过滤驱动不太了解,但已经知道了PDO、FDO和FiDO之间的关系。其中PDO处于最底层,FDO在PDO的上面,而在FDO的上面和下面分别有不同的PiDO,来看看《Windows驱动开发详解》中对于这种垂直层次关系的图示:


    5.对层次结构的总结

    在对PDO、FDO和FiDO有了一些了解后,又再翻看了一下《Windows操作系统原理》中的相关内容,最后对驱动程序又有了一些了解。

    一个硬件设备至少有两个驱动程序,一个是PDO驱动,即总线驱动程序;一个是FDO驱动,即功能设备驱动。总线驱动程序负责硬件与计算机的连接;功能设备驱动负责初始化I/O操作,处理I/O操作完成时所产生的中断事件,而HelloDDK就属于功能设备驱动。而FiDO驱动又分为底层过滤器驱动和高层过滤器驱动,也许在以后对文件过滤驱动的学习中会明白这一概念。

    展开全文
  • 数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述  已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。 输入  输入数据组,第一行是一个整数t ...

    数据结构实验之求二叉树后序遍历和层次遍历

    Time Limit: 1000MS Memory limit: 65536K

    题目描述

     已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。

    输入

     输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据。每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列。

    输出

    每组第一行输出二叉树的后序遍历序列,第二行输出二叉树的层次遍历序列

    示例输入

    2
    abdegcf
    dbgeafc
    xnliu
    lnixu

    示例输出

    dgebfca
    abcdefg
    linux
    xnuli


    前序遍历也叫先序遍历。前序遍历有一个特点,第一个节点为二叉树的根节点,根据这个根节点可以在中序序列中找到根节点的左右子树。
    例如:一个二叉树前序序列是:a b d e g c f,中序序列是:d b g e a f c,则根据前序序列第一个数据为a,在中序序列中可以看出此二叉树的
    左子树为:d b g e ,右子树为:f c ,此时就可以用递归解决了,前序序列指针往后移动一个位置即为左子树的根节点,前序序列指针往后移动左子树节点个数加一个位置即为
    右子树的根节点的位置。下面为具体的代码实现:
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node//此处不解释
    {
        char data;
        struct node *lchild,*rchild;
    }node,*nodeptr;
    
    
    char xian[55],zhong[55];//定义两个全局数组
    //xian[]为前序序列,zhong[]为中序序列
    
    struct node *Creat(char *xian,char *zhong,int n)
    {//根据前序遍历和中序遍历建立二叉树,n为二叉树包含节点个数
        struct node *T;
        int k;
        char *p;
        if(n<=0)return NULL;//当其包含结点数为0,返回
        T=(struct node *)malloc(sizeof(struct node));
        T->data=*xian;
        for(p=zhong;p<zhong+n;p++)
        {
            if(*xian==*p)
                break;
        }
        k=p-zhong;
        T->lchild=Creat(xian+1,zhong,k);
        T->rchild=Creat(xian+k+1,p+1,n-k-1);
        return T;
    }
    
    
    int treelevel(struct node *T,int level)
    {//层次遍历输出函数
        if(!T||level<0)
            return 0;
        if(level==0)
        {
            printf("%c",T->data);
            return 1;
        }
        return treelevel(T->lchild,level-1)+treelevel(T->rchild,level-1);
    }
    
    
    void level1(struct node *T)
    {//二叉树层次控制函数
        int i=0;
        for(i=0;;i++)
        {
            if(!treelevel(T,i))
                break;
        }
    }
    
    
    void lrd(struct node *T)
    {//后序遍历输出函数
        if(T)
        {
            lrd(T->lchild);
            lrd(T->rchild);
            printf("%c",T->data);
        }
    }
    
    
    int main()
    {
        int n,i;
        struct node *T;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%s",xian);
            scanf("%s",zhong);
            i=strlen(zhong);
            T=Creat(xian,zhong,i);
            lrd(T);
            printf("\n");
            level1(T);
            printf("\n");
        }
        return 0;
    }

    下面为本人画出的前几步的运行步骤:

    水平有限,不喜勿喷,原创辛苦,转载请注明出处*>_<*
    展开全文
  • 更详细的数据可以向下钻取到的层次结构中的下级节点的可视化。 考虑一个例子层次的客户联络层次“,用于限定电信呼叫中心接收电话。   图1:客户联络层次 BW)" src="http://hi.csdn.net/attachment/20
  • 数据结构的作用

    千次阅读 2012-01-03 22:46:48
    为什么计算机的孩子要学好数据结构数据结构课程介绍: 《数据结构》是计算机科学课程体系中核心课程之首,作为学科的专业基础课,具有承上启下的重要作用。对应于学科 中问题求解的理论、抽象和设计的方法论...
  • 提高JAVA水平从这里开始2--数据结构篇(二叉树)[转来的]JAVA小猪Java (2003-04-22 17:09:24) -------------------------------------------------------------------------------- 上次用一个小程序讲解了链表,这里...
  • R语言使用层次聚类处理数据

    万次阅读 2017-06-11 15:11:48
    凝聚层次聚类说明层次聚类可以分成凝聚(agglomerative,自底向上)和分裂(divisive,自顶向下)两种方法来构建聚类层次,但不管采用那种算法,算法都需要距离的相似性度量来判断对数据究竟是采取合并还是分裂处理。
  • 数据结构化和半结构化的区别

    千次阅读 2018-09-14 23:09:53
    相对于结构数据(即行数据,存储在数据库里,可以用二维表结构来逻辑表达实现的数据)而言,不方便用数据库二维逻辑表来表现的数据即称为非结构数据,包括所有格式的办公文档、文本、图片、XML、HTML、各类报表...
  • 数据结构》60’ 一、栈(stack)、队列(Queue)、向量(Vector) 1、链表 带哨兵节点链表了解清楚 链表要会写,会分析。各种链表。 2、栈 LIFO(last in first out)先存进去的数据,最后被取出来,进出顺序...
  • 关于数据结构学习方法

    千次阅读 2011-12-13 16:14:55
    在网上搜集到的数据结构学习方法,请同学们参考。   谈数据结构学习方法(转帖) 我在这里只是谈谈自己的学习体会现在咱们学的的数据结构是C++版本的 所以C++的一些基础知识应该先看会 尤其是指针那一部分 很多...
  • 数据结构(廿一) -- C语言版 -- 图 - 图的基本概念

    千次阅读 多人点赞 2020-07-26 20:08:00
    在树形结构中 ,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中个元素(即其孩子节点)相关 但只能和上一层中一个元素(即其双亲节点) 相关,而在图形结构中,结点之间的关系可以是任意...
  •  相对于结构数据(即行数据,存储在数据库里,可以用二维表结构来逻辑表达实现的数据)而言,不方便用数据库二维逻辑表来表现的数据即称为非结构数据,包括所有格式的办公文档、文本、图片、XML、HTML、各类...
  • 数据结构中的英文及算法缩写

    千次阅读 多人点赞 2018-12-04 21:18:06
    最近在复习数据结构,经常会遇到很英文及其缩写,它们分布不同,意义不同,有时也就很难记忆,在此我将其整理出来,方便记忆和使用,也希望对大家有所帮助。 第一章 算法分析 ADT: O(n): T(b): f(n): 第2章...
  • 第8章 数据结构

    千次阅读 2014-09-29 00:11:11
    算法的设计依赖于数据的逻辑结构,算法的实现依赖于数据的存储结构,所以数据结构选择得好环,对程序的质量影响甚大。掌握基本的数据结构知识,是程序设计水平提高的必要条件。算法和数据结构也是面试中的必考题型。
  • 【OpevCV数据结构归总】

    千次阅读 2011-10-19 20:09:02
    OpenCV里面用到了很图像相关的数据结构,熟练掌握它们是学习图像的基础。 1、IplImage IplImage IplImage IPL 图像头 typedef struct _IplImage { int nSize; /* IplImage大小 */ ...
  • 数据结构(c语言版)总结

    千次阅读 2013-06-13 17:05:59
    1. 数据结构的4中基本类型 1、集合 2、线性结构 3、树形结构 4、图、网状结构 2. 结构定义中的关系描述是数据元素之间的逻辑关系,因此叫逻辑结构 3. 数据存储结构:顺序存储结构、链式存储结构 (有顺序映像和...
  • JDK容器与并发—数据结构

    千次阅读 2016-04-20 17:21:59
    若想提高编程水平,一种方式就是看优秀框架的源码,JDK的源码就是一个很好例子,顺便也熟悉一下经常用到的类。在了解过程中,可以了解其框架设计方式,为什么要这样设计。先看看list 的UML类图:
  • 软件设计有三个要素:流程、功能方法和数据结构 一 设计流程要点 功能方法考虑性能,流程方法考虑设计模式。 1. 愿景 你需要做个什么东西,要做到什么水平。 2. 边界 你需要干什么,什么你不用干,什么你不能干。 3....
  • 写在前面作为前端开发者而言,可能不会像后端开发那样遇到很的算法和数据结构问题,但是不论是做前端、 服务端还是客户端, 任何一个程序员都会开始面对更加复杂的问题, 这个时候算法和数据结构知识就变得不可或...
  • 数据处理的关键层次架构

    万次阅读 2016-04-01 16:30:30
    图1、大数据处理的关键架构层 以下是对上图中各架构层的说明 一、数据存储层 宽泛地讲,据对一致性(consistency)要求的强弱不同,分布式数据存储策略,可分为ACID和BASE两大阵营。ACID是指数据库事务具有的四...
  • 数据结构与算法——排序算法篇

    千次阅读 2012-05-16 17:25:33
    其实很的情况下,是否使用排序是一个重要的策略问题。很早以前人们使用排序,多数情况下是希望能够使用二分查找在logn的时间内取得想要的数据。乱序的情况下,只能使用顺序查找,需要n的时间才能够完成,平均情况...
  • 相对于结构数据(即行数据,存储在数据库里,可以用二维表结构来逻辑表达实现的数据)而言,不方便用数据库二维逻辑表来表现的数据即称为非结构数据,包括所有格式的办公文档、文本、图片、XML、HTML、各类报表...
  • 本来计划要写Android内存优化的,觉得有必要在此之前介绍一下Java虚拟机的相关知识,Java虚拟机也并不是三言两语能够介绍完的,因此开了Java虚拟机系列,这一篇文章我们来学习Java虚拟机的结构原理与运行时数据区域...
  • 本文中没有涉及到很的相关理论知识,也没有做深入的了解,所以,您如果是想要系统的学习、想要学习关于理论的知识等,那么本文可能并不合适您。 本文中所有设计的代码均通过测试,并且在功能性方面均实现应有的...
  • 选择一个排序算法时,除算法的时空效率外,下列因素中,还需要考虑的是 知识点:排序算法 解析:数据的规模,数据的存储方式,算法的稳定性,数据的初始状态都需要考虑,选D 8.现有长度为11且初始为空的散列表HT,...
  • OpenCV的序列数据结构

    千次阅读 2013-05-31 15:28:05
    序列是内存存储器中可以存储的一种对象.序列是某种结构的链表.OpenCV中,序列可以存储多种不同的结构.你可以将序列想象为许多编程语言中都存在的容器类或容器类模版...数据结构seq数据结构如下#define CV_TREE_NODE_FIE
  • 数据结构算法题汇总

    千次阅读 2019-04-13 19:40:07
    3. 算法一般都可以用哪几种控制结构组合而成? 答案:顺序、选择、循环。 4. 算法的时间复杂度是指? 答案:算法执行过程中所需要的基本运算次数。 5. 算法的空间复杂度是指? 答案:执行过程中所需要的存储空间。...
  • 数据结构与算法(12)——树(一)

    千次阅读 2007-09-27 17:35:00
    数据结构与算法12——树(一) 一、树的基本概念树型数据结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。它描述了客观世界中事物之间的层次关系,树在计算机领域内也有广泛的应用,如在编译程序中,可用...
  •  live当年参加ACM的时候,主攻DP和初等数论, 队友攻计算几何和数据结构,另外一个队友思考Trickle  在有限的训练时间内,让整个团队的实力得到一个最大化的提升。  * 每次解题都要计时和统计提交次数 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,105
精华内容 34,842
关键字:

多水平层次结构数据