丨4/7一2/5丨一丨3/5一7/9丨十丨2/9一3/7丨?

本文由作者“阿宝哥”分享,原题“你不知道的 WebSocket”,有修订和改动。

本文将从基本概念、技术原理、常见易错常识、动手实践等多个方面入手,万字长文,带你一起全方位探索 WebSocket 技术。

阅读完本文,你将了解以下内容:

3)了解 WebSocket 的握手协议和数据帧格式、掩码算法等相关知识;
4)了解 WebSocket 与http、长轮询、socket等的关系,理清常识性的理解错误;
5)了解如何实现一个支持发送普通文本的 WebSocket 服务器。

  • 即时通讯/推送技术开发交流5群: [推荐]
  • 移动端IM开发入门文章:《新手入门一篇就够:从零开发移动端IM》

早期,很多网站为了实现推送技术,所用的技术都是轮询(也叫短轮询)。轮询是指由浏览器每隔一段时间向服务器发出 HTTP 请求,然后服务器返回最新的数据给客户端。

常见的轮询方式分为轮询与长轮询,它们的区别如下图所示:

为了更加直观感受轮询与长轮询之间的区别,我们来看一下具体的代码:

这种传统的模式带来很明显的缺点,即浏览器需要不断的向服务器发出请求,然而 HTTP 请求与响应可能会包含较长的头部,其中真正有效的数据可能只是很小的一部分,所以这样会消耗很多带宽资源。

PS:关于短轮询、长轮询技术的前世今身,可以详细读这两篇:《新手入门贴:史上最全Web端即时通讯技术原理详解》、《Web端即时通讯技术盘点:短轮询、Comet、Websocket、SSE》。

比较新的轮询技术是 Comet。这种技术虽然可以实现双向通信,但仍然需要反复发出请求。而且在 Comet 中普遍采用的 HTTP 长连接也会消耗服务器资源。

在这种情况下,HTML5 定义了 WebSocket 协议,能更好的节省服务器资源和带宽,并且能够更实时地进行通讯。

  • 2)若运行在 TLS 之上时,默认使用 443 端口。

WebSocket 使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据。在 WebSocket API 中,浏览器和服务器只需要完成一次握手,两者之间就可以创建持久性的连接,并进行双向数据传输。

介绍完轮询和 WebSocket 的相关内容之后,接下来用一张图看一下 XHR Polling(短轮询) 与 WebSocket 之间的区别。

  • 1)较少的控制开销:在连接创建后,服务器和客户端之间交换数据时,用于协议控制的数据包头部相对较小;
  • 2)更强的实时性:由于协议是全双工的,所以服务器可以随时主动给客户端下发数据。相对于 HTTP 请求需要等待客户端发起请求服务端才能响应,延迟明显更少;
  • 3)保持连接状态:与 HTTP 不同的是,WebSocket 需要先创建连接,这就使得其成为一种有状态的协议,之后通信时可以省略部分状态信息;
  • 4)更好的二进制支持:WebSocket 定义了二进制帧,相对 HTTP,可以更轻松地处理二进制内容;
  • 5)可以支持扩展:WebSocket 定义了扩展,用户可以扩展协议、实现部分自定义的子协议。

由于 WebSocket 拥有上述的优点,所以它被广泛地应用在即时通讯/IM、实时音视频、在线教育和游戏等领域。

对于前端开发者来说,要想使用 WebSocket 提供的强大能力,就必须先掌握 WebSocket API,下面带大家一起来认识一下 WebSocket API。

PS:如果你想要更浅显的WebSocket入门教程,可以先读这篇《新手快速入门:WebSocket简明教程》后,再回来继续学习。

在介绍 WebSocket API 之前,我们先来了解一下它的兼容性:

由上图可知:目前主流的 Web 浏览器都支持 WebSocket,所以我们可以在大多数项目中放心地使用它。

在浏览器中要使用 WebSocket 提供的能力,我们就必须先创建 WebSocket 对象,该对象提供了用于创建和管理 WebSocket 连接,以及可以通过该连接发送和接收数据的 API。

接下来我们将从以下四个方面来介绍 WebSocket API:

接下来我们从 WebSocket 的构造函数入手开始学习。

PS:如果你想要更浅显的WebSocket入门教程,可以先读这篇《新手快速入门:WebSocket简明教程》后,再回来继续学习。

2)protocols(可选):一个协议字符串或者一个包含协议字符串的数组。

针对第2)点:这些字符串用于指定子协议,这样单个服务器可以实现多个 WebSocket 子协议。

比如:你可能希望一台服务器能够根据指定的协议(protocol)处理不同类型的交互。如果不指定协议字符串,则假定为空字符串。

使用WebSocket 构造函数时,当尝试连接的端口被阻止时,会抛出 SECURITY_ERR 异常。

PS:有关WebSocket构造函数的更详细说明,可以参见官方API文档。

每个属性的具体含义如下:

1)binaryType:使用二进制的数据类型连接;
2)bufferedAmount(只读):未发送至服务器的字节数;
3)extensions(只读):服务器选择的扩展;
4)onclose:用于指定连接关闭后的回调函数;
5)onerror:用于指定连接失败后的回调函数;
6)onmessage:用于指定当从服务器接受到信息时的回调函数;
7)onopen:用于指定连接成功后的回调函数;
8)protocol(只读):用于返回服务器端选中的子协议的名字;

- OPEN — 已经连接并且可以通讯,对应的值为 1; - CLOSING — 连接正在关闭,对应的值为 2; - CLOSED — 连接已关闭或者没有连接成功,对应的值为 3

10)url(只读):返回值为当构造函数创建 WebSocket 实例对象时 URL 的绝对路径。

2)send(data):该方法将需要通过 WebSocket 链接传输至服务器的数据排入队列,并根据所需要传输的数据的大小来增加 bufferedAmount 的值 。若数据无法传输(比如数据需要缓存而缓冲区已满)时,套接字会自行关闭。

4.6 代码实践:发送普通文本

在以上示例中:我们在页面上创建了两个 textarea,分别用于存放 待发送的数据 和 服务器返回的数据。当用户输入完待发送的文本之后,点击 发送 按钮时会把输入的文本发送到服务端,而服务端成功接收到消息之后,会把收到的消息原封不动地回传到客户端。

为了更加直观地理解上述的数据交互过程,我们使用 Chrome 浏览器的开发者工具来看一下相应的过程。

以上示例对应的完整代码如下所示:

 // 监听连接成功事件

以上代码成功运行后,通过 Chrome 开发者工具,我们可以看到对应的数据交互过程。

下面以发送 Blob 对象为例,来介绍一下如何发送二进制数据。

Blob(Binary Large Object)表示二进制类型的大对象。在数据库管理系统中,将二进制数据存储为一个单一个体的集合。Blob 通常是影像、声音或多媒体文件。在 JavaScript 中 Blob 类型的对象表示不可变的类似文件对象的原始数据。

对 Blob 感兴趣的小伙伴,可以阅读 《你不知道的 Blob》这篇文章。

4.7 代码实践:发送二进制数据

在以上示例中,我们在页面上创建了两个 textarea,分别用于存放 待发送的数据 和 服务器返回的数据。

当用户输入完待发送的文本之后,点击 发送 按钮时,我们会先获取输入的文本并把文本包装成 Blob 对象然后发送到服务端,而服务端成功接收到消息之后,会把收到的消息原封不动地回传到客户端。

当浏览器接收到新消息后,如果是文本数据,会自动将其转换成 DOMString 对象,如果是二进制数据或 Blob 对象,会直接将其转交给应用,由应用自身来根据返回的数据类型进行相应的处理。

当客户端接收到服务端返回的消息之后,会判断返回的数据类型,如果是 Blob 类型的话,会调用 Blob 对象的 text() 方法,获取 Blob 对象中保存的 UTF-8 格式的内容,然后把对应的文本内容保存到 接收的数据 对应的 textarea 文本框中。

同样,我们使用 Chrome 浏览器的开发者工具来看一下相应的过程:

通过上图我们可以很明显地看到,当使用发送 Blob 对象时,Data 栏位的信息显示的是 Binary Message,而对于发送普通文本来说,Data 栏位的信息是直接显示发送的文本消息。

以上示例对应的完整代码如下所示:

 // 监听连接成功事件

可能有一些小伙伴了解完 WebSocket API 之后,觉得还不够过瘾。下面将带大家来实现一个支持发送普通文本的 WebSocket 服务器。

在介绍如何手写 WebSocket 服务器前,我们需要了解一下 WebSocket 连接的生命周期。

从上图可知:在使用 WebSocket 实现全双工通信之前,客户端与服务器之间需要先进行握手(Handshake),在完成握手之后才能开始进行数据的双向通信。

握手是在通信电路创建之后,信息传输开始之前。

握手用于达成参数,如:

握手有助于不同结构的系统或设备在通信信道中连接,而不需要人为设置参数。

既然握手是 WebSocket 连接生命周期的第一个环节,接下来我们就先来分析 WebSocket 的握手协议。

WebSocket 协议属于应用层协议,它依赖于传输层的 TCP 协议。WebSocket 通过 HTTP/1.1 协议的 101 状态码进行握手。为了创建 WebSocket 连接,需要通过浏览器发出请求,之后服务器进行回应,这个过程通常称为 “握手”(Handshaking)。

利用 HTTP 完成握手有几个好处:

1)首先:让 WebSocket 与现有 HTTP 基础设施兼容——使得 WebSocket 服务器可以运行在 80 和 443 端口上,这通常是对客户端唯一开放的端口;
2)其次:让我们可以重用并扩展 HTTP 的 Upgrade 流,为其添加自定义的 WebSocket 首部,以完成协商。

下面我们以前面已经演示过的发送普通文本的例子为例,来具体分析一下握手过程。

5.2.1)客户端请求:

备注:已忽略部分 HTTP 请求头。

针对上述请求中的字段说明如下:

4)Sec-WebSocket-Key:是随机的字符串,服务器端会用这些数据来构造出一个 SHA-1 的信息摘要;
5)Sec-WebSocket-Extensions:用于协商本次连接要使用的 WebSocket 扩展:客户端发送支持的扩展,服务器通过返回相同的首部确认自己支持一个或多个扩展;
6)Origin:字段是可选的,通常用来表示在浏览器中发起此 WebSocket 连接所在的页面,类似于 Referer。但是,与 Referer 不同的是,Origin 只包含了协议和主机名称。

5.2.2)服务端响应:

备注:已忽略部分 HTTP 响应头。

针对上述响应中的字段说明如下:

② 设置 Connection 头的值为 “Upgrade” 来指示这是一个升级请求(HTTP 协议提供了一种特殊的机制,这一机制允许将一个已建立的连接升级成新的、不相容的协议);
③ Upgrade 头指定一项或多项协议名,按优先级排序,以逗号分隔。这里表示升级为 WebSocket 协议;
④ 签名的键值验证协议支持。

要开发一个 WebSocket 服务器,首先我们需要先实现握手功能。这里我使用 Node.js 内置的 http 模块来创建一个 HTTP 服务器。

在以上代码中:我们首先引入了 http 模块,然后通过调用该模块的 createServer() 方法创建一个 HTTP 服务器,接着我们监听 upgrade 事件,每次服务器响应升级请求时就会触发该事件。由于我们的服务器只支持升级到 WebSocket 协议,所以如果客户端请求升级的协议非 WebSocket 协议,我们将会返回 “400 Bad Request”。

上述的过程看起来好像有点繁琐,其实利用 Node.js 内置的 crypto 模块,几行代码就可以搞定了。

开发完握手功能之后,我们可以使用前面的示例来测试一下该功能。待服务器启动之后,我们只要对 “发送普通文本” 示例,做简单地调整,即把先前的 URL 地址替换成 ws://localhost:8888,就可以进行功能验证。

感兴趣的小伙们可以试试看,以下是我的本地运行后的结果:

从上图可知:我们实现的握手功能已经可以正常工作了。那么握手有没有可能失败呢?答案是肯定的。比如网络问题、服务器异常或 Sec-WebSocket-Accept 的值不正确。

此时,浏览器的控制台会输出以下异常信息:

如果你的 WebSocket 服务器要支持子协议的话,你可以参考以下代码进行子协议的处理,这里就不继续展开介绍了。

好的,WebSocket 握手协议相关的内容基本已经介绍完了。下一步我们来介绍开发消息通信功能需要了解的一些基础知识。

在 WebSocket 协议中,数据是通过一系列数据帧来进行传输的。

为了避免由于网络中介(例如一些拦截代理)或者一些安全问题,客户端必须在它发送到服务器的所有帧中添加掩码。服务端收到没有添加掩码的数据帧以后,必须立即关闭连接。

5.4.1)数据帧格式:

要实现消息通信,我们就必须了解 WebSocket 数据帧的格式:

可能有一些小伙伴看到上面的内容之后,就开始有点 “懵逼” 了。

下面我们来结合实际的数据帧来进一步分析一下:

在上图中:简单分析了 “发送普通文本” 示例对应的数据帧格式。这里我们来进一步介绍一下 Payload length,因为在后面开发数据解析功能的时候,需要用到该知识点。

Payload length 表示以字节为单位的 “有效负载数据” 长度。

1)如果值为 0-125,那么就表示负载数据的长度;
2)如果是 126,那么接下来的 2 个字节解释为 16 位的无符号整形作为负载数据的长度;
3)如果是 127,那么接下来的 8 个字节解释为一个 64 位的无符号整形(最高位的 bit 必须为 0)作为负载数据的长度。

备注:多字节长度量以网络字节顺序表示,有效负载长度是指 “扩展数据” + “应用数据” 的长度。“扩展数据” 的长度可能为 0,那么有效负载长度就是 “应用数据” 的长度。

另外:除非协商过扩展,否则 “扩展数据” 长度为 0 字节。在握手协议中,任何扩展都必须指定 “扩展数据” 的长度,这个长度如何进行计算,以及这个扩展如何使用。如果存在扩展,那么这个 “扩展数据” 包含在总的有效负载长度中。

PS:关于数据帧格式的详细讲解,可以深入读读以下几篇:

《WebSocket从入门到精通,半小时就够!》
《理论联系实际:从零理解WebSocket的通信原理、协议格式、安全性》

5.4.2)掩码算法:

掩码字段是一个由客户端随机选择的 32 位的值。掩码值必须是不可被预测的。因此,掩码必须来自强大的熵源(entropy),并且给定的掩码不能让服务器或者代理能够很容易的预测到后续帧。掩码的不可预测性对于预防恶意应用的作者在网上暴露相关的字节数据至关重要。

掩码不影响数据荷载的长度,对数据进行掩码操作和对数据进行反掩码操作所涉及的步骤是相同的。

掩码、反掩码操作都采用如下算法:

为了让小伙伴们能够更好的理解上面掩码的计算过程,我们来对示例中 “我是阿宝哥” 数据进行掩码操作。

这里 “我是阿宝哥” 对应的 UTF-8 编码如下所示:

根据上面的算法,我们可以这样进行掩码运算:

以上代码成功运行后,控制台会输出以下结果:

在 WebSocket 协议中,数据掩码的作用是增强协议的安全性。但数据掩码并不是为了保护数据本身,因为算法本身是公开的,运算也不复杂。

那么为什么还要引入数据掩码呢?引入数据掩码是为了防止早期版本的协议中存在的代理缓存污染攻击等问题。

了解完 WebSocket 掩码算法和数据掩码的作用之后,我们再来介绍一下数据分片的概念。

5.4.3)数据分片:

WebSocket 的每条消息可能被切分成多个数据帧。当 WebSocket 的接收方收到一个数据帧时,会根据 FIN 的值来判断,是否已经收到消息的最后一个数据帧。

利用 FIN 和 Opcode,我们就可以跨帧发送消息。

操作码告诉了帧应该做什么:

1)如果是 0x1,有效载荷就是文本;
2)如果是 0x2,有效载荷就是二进制数据;
3)如果是 0x0,则该帧是一个延续帧(这意味着服务器应该将帧的有效负载连接到从该客户机接收到的最后一个帧)。

为了让大家能够更好地理解上述的内容,我们来看一个来自 MDN 上的示例:

在以上示例中:客户端向服务器发送了两条消息,第一个消息在单个帧中发送,而第二个消息跨三个帧发送。

其中:第一个消息是一个完整的消息(FIN=1 且 opcode != 0x0),因此服务器可以根据需要进行处理或响应。而第二个消息是文本消息(opcode=0x1)且 FIN=0,表示消息还没发送完成,还有后续的数据帧。该消息的所有剩余部分都用延续帧(opcode=0x0)发送,消息的最终帧用 FIN=1 标记。

好的,简单介绍了数据分片的相关内容。接下来,我们来开始实现消息通信功能。

5.5 实现消息通信功能
笔者把实现消息通信功能,分解为消息解析与消息响应两个子功能,下面我们分别来介绍如何实现这两个子功能。

5.5.1)消息解析:

利用消息通信基础环节中介绍的相关知识,我实现了一个 parseMessage 函数,用来解析客户端传过来的 WebSocket 数据帧。

出于简单考虑,这里只处理文本帧,具体代码如下所示:

// 右移7位取首位,1位,表示是否是最后一帧数据 // 取出操作码,低四位 * %x0:表示一个延续帧。当 Opcode 为 0 时,表示本次数据传输采用了数据分片,当前收到的数据帧为其中一个数据分片; * %x3-7:保留的操作代码,用于后续定义的非控制帧; * %x8:表示连接断开; * %x9:表示这是一个心跳请求(ping); * %xA:表示这是一个心跳响应(pong); * %xB-F:保留的操作代码,用于后续定义的控制帧。 // 目前只处理文本帧 // MASK: 1位,表示是否使用了掩码,在发送给服务端的数据帧里必须使用掩码,而服务端返回时不需要掩码 // 如果这个值在0-125之间,则后面的4个字节(32位)就应该被直接识别成掩码; // 如果这个值是126,则后面两个字节(16位)内容应该,被识别成一个16位的二进制数表示数据内容大小; // 如果这个值是127,则后面的8个字节(64位)内容应该被识别成一个64位的二进制数表示数据内容大小 // 开始读取后面的payload,与掩码计算,得到原来的字节内容

更新完成之后,我们重新启动服务器,然后继续使用 “发送普通文本” 的示例来测试消息解析功能。

以下发送 “我是阿宝哥” 文本消息后,WebSocket 服务器输出的信息:

通过观察以上的输出信息,我们的 WebSocket 服务器已经可以成功解析客户端发送包含普通文本的数据帧,下一步我们来实现消息响应的功能。

5.5.2)消息响应:

要把数据返回给客户端,我们的 WebSocket 服务器也得按照 WebSocket 数据帧的格式来封装数据。

该函数的具体代码如下:

// 目前只支持小于65535字节的负载 // 设置数据帧首字节,设置opcode为1,表示文本帧 // 如果payloadLength为126,则后面两个字节(16位)内容应该,被识别成一个16位的二进制数表示数据内容大小

到这里,我们的 WebSocket 服务器已经开发完成了,接下来我们来完整验证一下它的功能。

从上图中可知:以上开发的简易版 WebSocket 服务器已经可以正常处理普通文本消息了。

最后我们来看一下完整的代码。

res.end("大家好,我是阿宝哥。感谢你阅读“你不知道的WebSocket”"); // 返回握手请求的响应信息
  • %x0:表示一个延续帧。当 Opcode 为 0 时,表示本次数据传输采用了数据分片,当前收到的数据帧为其中一个数据分片;
  • %x3-7:保留的操作代码,用于后续定义的非控制帧;
  • %x8:表示连接断开;
  • %x9:表示这是一个心跳请求(ping);
  • %xA:表示这是一个心跳响应(pong);
  • %xB-F:保留的操作代码,用于后续定义的控制帧。
// 目前只处理文本帧
// MASK: 1位,表示是否使用了掩码,在发送给服务端的数据帧里必须使用掩码,而服务端返回时不需要掩码
// 如果这个值在0-125之间,则后面的4个字节(32位)就应该被直接识别成掩码;
// 如果这个值是126,则后面两个字节(16位)内容应该,被识别成一个16位的二进制数表示数据内容大小; // 如果这个值是127,则后面的8个字节(64位)内容应该被识别成一个64位的二进制数表示数据内容大小
// 开始读取后面的payload,与掩码计算,得到原来的字节内容

其实服务器向浏览器推送信息,除了使用 WebSocket 技术之外,还可以使用 SSE(Server-Sent Events)。它让服务器可以向客户端流式发送文本消息,比如服务器上生成的实时消息。

为实现这个目标,SSE 设计了两个组件:浏览器中的 EventSource API 和新的 “事件流” 数据格式(text/event-stream)。其中,EventSource 可以让客户端以 DOM 事件的形式接收到服务器推送的通知,而新数据格式则用于交付每一次数据更新。

实际上:SSE 提供的是一个高效、跨浏览器的 XHR 流实现,消息交付只使用一个长 HTTP 连接。然而,与我们自己实现 XHR 流不同,浏览器会帮我们管理连接、 解析消息,从而让我们只关注业务逻辑。篇幅有限,关于 SSE 的更多细节,就不展开介绍了,对 SSE 感兴趣的小伙伴可以自行阅读以下几篇:

《SSE技术详解:一种全新的HTML5服务器推送事件技术》
《网页端IM通信技术快速入门:短轮询、长轮询、SSE、WebSocket》

6、WebSocket学习过程中的易错常识

当然,WebSocket与HTTP的关系显然不是这三两句话可以说的清,有兴趣的读者可以详读下面这两篇:

长轮询就是:客户端发起一个请求,服务器收到客户端发来的请求后,服务器端不会直接进行响应,而是先将这个请求挂起,然后判断请求的数据是否有更新。如果有更新,则进行响应,如果一直没有数据,则等待一定的时间后才返回。

长轮询的本质还是基于 HTTP 协议,它仍然是一个一问一答(请求 — 响应)的模式。而 WebSocket 在握手成功后,就是全双工的 TCP 通道,数据可以主动从服务端发送到客户端。

要理解WebSocket 与长轮询的区别,需要深刻理解长轮询的技术原理,以下3篇中有关长轮询的技术介绍建议深入阅读:

《Comet技术详解:基于HTTP长连接的Web端实时通信技术》
《新手入门贴:史上最全Web端即时通讯技术原理详解》
《网页端IM通信技术快速入门:短轮询、长轮询、SSE、WebSocket》
网络中的接收和发送数据都是使用 Socket 进行实现。但是如果此套接字已经断开,那发送数据和接收数据的时候就一定会有问题。

可是如何判断这个套接字是否还可以使用呢?这个就需要在系统中创建心跳机制。

所谓 “心跳” 就是定时发送一个自定义的结构体(心跳包或心跳帧),让对方知道自己 “在线”,以确保链接的有效性。

而所谓的心跳包就是客户端定时发送简单的信息给服务器端告诉它我还在而已。代码就是每隔几分钟发送一个固定信息给服务端,服务端收到后回复一个固定信息,如果服务端几分钟内没有收到客户端信息则视客户端断开。

1)心跳 Ping 帧包含的操作码是 0x9:如果收到了一个心跳 Ping 帧,那么终端必须发送一个心跳 Pong 帧作为回应,除非已经收到了一个关闭帧。否则终端应该尽快回复 Pong 帧;
2)心跳 Pong 帧包含的操作码是 0xA:作为回应发送的 Pong 帧必须完整携带 Ping 帧中传递过来的 “应用数据” 字段。
针对第2)点:如果终端收到一个 Ping 帧但是没有发送 Pong 帧来回应之前的 Ping 帧,那么终端可以选择仅为最近处理的 Ping 帧发送 Pong 帧。此外,可以自动发送一个 Pong 帧,这用作单向心跳。

PS:这里有篇WebSocket心跳方面的IM实战总结文章,有兴趣可以阅读《Web端即时通讯实践干货:如何让你的WebSocket断网重连更快速?》。

网络上的两个程序通过一个双向的通信连接实现数据的交换,这个连接的一端称为一个 Socket(套接字),因此建立网络通信连接至少要一对端口号。

Socket 本质:是对 TCP/IP 协议栈的封装,它提供了一个针对 TCP 或者 UDP 编程的接口,并不是另一种协议。通过 Socket,你可以使用 TCP/IP 协议。

百度百科上关于Socket的描述是这样:

Socket 的英文原义是“孔”或“插座”:作为 BSD UNIX 的进程通信机制,取后一种意思。通常也称作”套接字“,用于描述IP地址和端口,是一个通信链的句柄,可以用来实现不同虚拟机或不同计算机之间的通信。
在Internet 上的主机一般运行了多个服务软件,同时提供几种服务。每种服务都打开一个Socket,并绑定到一个端口上,不同的端口对应于不同的服务。Socket 正如其英文原义那样,像一个多孔插座。一台主机犹如布满各种插座的房间,每个插座有一个编号,有的插座提供 220 伏交流电, 有的提供 110 伏交流电,有的则提供有线电视节目。 客户软件将插头插到不同编号的插座,就可以得到不同的服务。

关于 Socket,可以总结以下几点:

1)它可以实现底层通信,几乎所有的应用层都是通过 socket 进行通信的;
2)对 TCP/IP 协议进行封装,便于应用层协议调用,属于二者之间的中间抽象层;
3)TCP/IP 协议族中,传输层存在两种通用协议: TCP、UDP,两种协议不同,因为不同参数的 socket 实现过程也不一样。

下图说明了面向连接的协议的套接字 API 的客户端/服务器关系:

本文已同步发布于“即时通讯技术圈”公众号。
}

2.4 算法和数据结构

解析:首先需要理解"后进先出",其实也可以称之为"先进后出",先进入的元素被压在栈底,栈底的元素要出栈则上层的元素必须全部都出栈,元素 A 要出栈,则必须元素 B先出栈,所以元素 B 的出栈要在 A 之前,所以选 C。

解析:算法的表示可以有多种形式,如文字说明(自然语言)、流程图表示、伪代码(一种介于自然语言和程序设计语言之间的文字和符号表达工具)和程序设计语言等。

解析:算法的设计一般采用由粗到细、由抽象到具体的逐步求精的方法。选项D错误

①、确定性:算法的每一条指令必须有确切的定义,无二义性。

②、有穷性:是指算法必须在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。

③、可行性:算法中的描述在计算机中能执行,且在有穷时间内完成。

④、至少有一个(1个或多个)输出,但是可以没有(0个或多个)输入

根据以上选项A和选项C错误

算法的表示(描述工具):自然语言描述、流程图、程序设计语言、伪代码。选项B正确。

解析:解决问题的算法有很多,可以使用多种语言求解同一问题,那问题的结果必相同,否则算法就不能满足相关条件。

解析:描述算法的可以是流程图、自然语言、伪代码,也可以是程序设计语言。

解析:a=a+b→变量 a中存放着a和b的和;b=a-b→变量b中存放着原来a的值;a=a-b→ 变量 a中存放着原来b 的值。

解析:算法是问题求解规则的一种过程描述,可以没有输入,但一定得有输出。

解析:选项 A 正确,此特性为确定性。选项 B 错误,算法具有确定性,一个程序实现的功能可以使用多种算法来完成。选项C 错误,算法具有有穷性,这一点与程序不同。选项 D 错误,算法的输入可以为 0,但输出不能为0。

解析:算法的设计一般采用由粗到细、由抽象到具体的逐步求精的方法。解决一个问题时肯定从大致的方向去考虑解决问题的方法,不可能一开始就从问题的某一个细节开始人手。

解析:数据结构中数据的逻辑结构分为线性结构和非线性结构。二叉树、森林、图都是非线性的逻辑结构。数据处理的效率与数据的逻辑结构和存储结构均相关。数据的逻辑结构与数据的存储无关。

解析:通常算法由设计人员规划完成,而计算机负责其程序编码的执行。

解析:可以不满足"有穷性",在算法中必须要满足有穷性的特点,而程序在运行的过程中有可能会出现"死循环"的现象,一旦出现此种情况,则程序本身无法终止其执行。

解析:程序=算法+数据结构(是由科学家尼克劳斯-沃思提出)。

解析:算法的设计一般采用由粗到细、由抽象到具体的逐步求解的方法。选项B描述有问题。

解析:研究数据结构一般包括三方面:数据的逻辑结构、数据的存储结构,定义在逻辑结构和存储结构上的运算。D选项正确。

解析:算法:可以没有输入,但是必有1个输出。

程序:可以没有输入,也可以没有输出。

算法的表示(描述)工具:流程图、自然语言、伪代码、程序设计语言。

程序可以被计算机执行。

算法不能被计算机直接执行,需要使用程序设计语言实现,编译或解释。

解析:根据栈的入栈和出栈规则“先进后出”,因为ABCDE为依次入栈:

A选项,要想C先出,那么AB肯定需要在C的下面,所以C出之后,D进入,之后再出,B再出,最后A出,所以可以正常入出栈。

B选项,A进A出,后B进B出,再C进D进D出,后E进E出,最后C出。正常出入栈。

C选项,ABCDE入栈,E出,D再出,C出,B出,A出,可以正常出入栈。

D选项,先出C,那么AB肯定需先进,C出之后D进,D出,E进入,E再进入,AB目前在栈内,且B在上面,即B只能先出,A是最后出。所以按选项中给出的出栈次序,并不能正常出入栈。所以该选项不可能的出栈次序。

解析:顺序查找,对线性表不做有序要求,效率最低。

折半查找(二分查找)效率最高,需要线性线有序,非动态。

分块查找效率居中,需要有序,且最好为动态的,是顺序和折半的一种改装算法。

解析:数据的逻辑结构常的结构:集合、线性、树状、网状等。

数据的物理结构常见的存储结构:顺序,链接,索引等;

解析:算法的表示不一定能让计算机理解。程序才是需要被计算机理解的。

解析:图是网状结构,存在多对多节点连接,地图规则可能 会涉及多个地点与多个地点之间的连接。

解析:算法的有穷性是指算法必须在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。

视频讲解(第23题至第26题):

解析:非线性结构:不满足线性结构条件的数据结构。如树、二叉树为非线性结构。

解析:根据二叉树的性质:二叉树【第i(i≥1)层上至多有 个结点。得到【第5层的结点数最多是16。

解析:所谓满二叉树是指这样的一种二叉树:除最后一层外,每层上的所有结点都有两个子结点。这就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的【第K层上有 个结点,且深度为m的满二叉树有 个结点。在满二叉树中,最后一层的结点个数就是叶子结点的个数,本题中深度为5,故叶子结点数为 = =16。本题答案是C。

解析:先遍历左子树、然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。(左-根-右)。首先访问点节A的左子树,点节A左子树的节点B还有子树,所以还要先访问点节B的左子树,即节点D(左),接着访问节点B(根);之后再访问节点E(右),节点A的左子树访问完,接下来访问A(根),接着访问右子树,节点C还有子树,还要继续按照料左-根-右访问;这时要先访问节点F(左),再访问节点C(根),右没有,所以点A的右子树也访问完毕。即DBEAFC。选项B正确。

解析:算法的必要满足条件:

①、确定性:算法的每一条指令必须有确切的定义,无二义性。

②、有穷性:是指算法必须在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。

③、可行性:算法中的描述在计算机中能执行,且在有穷时间内完成。

④、至少有一个(1个或多个)输出,但是可以没有(0个或多个)输入可以看成是拥有足够的情报

解析:队列是指允许在一端进行插入、而在另一端进行删除的线性表。它又称为"先进先出"或"后进后出"的线性表,体现了"先来先服务"的原则。

解析:计算机算法是指解题方案的准确而完整的描述,它有以下几个基本特征:可行性、确定性、有穷性和拥有足够的情报(输入输出情况)。本题答案为C。

解析:栈和队列都是一种特殊的操作受限的线性表,只允许在端点处进行插入和删除。二者的区别是:栈只允许在表的一端进行插入或删除操作,是一种"后进先出"的线性表;而队列只允许在表的一端进行插入操作,在另一端进行删除操作,是一种"先进先出"的线性表。本题答案为C。

解析:本题比较难。在有向图中,若任意两个顶点都连通,则称该图是强连通图,这样的有向图的形状是环状,因而至少应有n条边。比如下图所示。本题答案为C。

解析:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。故本题答案为D。

解析:一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构,其数据处理的效率是不同的。故本题答案为D。

解析:根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件:(1)有且只有一个根结点;(2)每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。有一个以上根结点的数据结构肯定是非线性结构,所以选项A是错误的。循环链表、双向链表是线性结构,所以选项C、D是错误的。

解析:栈是一种先进后出的线性表,栈实际上也是线性表,只不过是一种特殊的线性表,所以选项A、C均不正确。队列是指允许在一端进行插入、而在另一端进行删除的线性表,队列是一种"先进先出"或"后进后出"的线性表,所以选项B也不正确。故本题答案为D。

解析:非线性结构的逻辑特征是一个结点元素可能对应多个直接前件和多个后件。常见的非线性结构有:树(二叉树等),图(网等)。由于二叉树的存储结构中每一个存储结点有两个指针域,因此,二叉树的链式存储结构也称为二叉链表,二叉链表属于非线性结构。故本题答案为A。

解析:根据数据结构中各数据元素之间前后关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件:①有且只有一个根结点;②每个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。本题答案为D。

解析:根据数据结构中各数据元素之间前后关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件:①有且只有一个根结点;②每个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。所以具有两个根结点的数据结构一定是非线性结构。本题答案为D。

解析:本题的考查知识点是线性结构与非线性结构,比较难,略有点超纲。如果一个非空的数据结构有且只有一个根结点,并且每一个结点最多有一个前件,也最多有一个后件,则称该数据结构为线性结构,线性结构又称为线性表。例如双链表和二叉链表的结点都有两个指针域,前者是线性结构,后者是非线性结构。二叉链表中会有两个结点的同一个指针域的值相等即指向父结点。 所以本题答案为B。

解析:本题的考查知识点是线性结构与非线性结构。线性结构用图形表示更加直观,(1,3)图形表示为1->3,(4,1)图形表示为4->1,其余R中的元素图形表示以此类推。线性结构要求有且只有一个根结点,而且每一个结点最多有一个前件,也最多有一个后件。

解析:一个算法必须满足在执行了有限步的操作之后终止,这一特点与程序不同。

解析:队列是一种特殊的线性表,是一种具有先进先出(FIFO)的数据结构。队列中先插入的元素将最先被删除;反之,最后插入的元素将最后被删除。具有线性结构特点的对象还有栈、字符串、数组及广义表等。区分队列与栈的不同。

解析:正确性和算法的复杂度是优先考虑的,其次才会考虑是否可读性、是否健壮性、是否容易调试和测试等。A选项是正确性。C选项是算法的空间复杂度。D选项是算法时间复杂度。

解析:栈和队列都属于线性结构(线性表、字符串、数组以及广义表也属于),栈的特点是后进先出,而队列属于先进先出,A、B 选项中的概念颠倒了。

解析:要理解耦合度和内聚度的概念,首先要搞清楚模块独立性的相关内容,模块只完成系统要求的独立的子功能,并且与其它模块的联系最少并且接口简单,符合信息隐蔽和信息局部化原则,模块间关联和依赖程度尽可能小。衡量模块独立性的标准是耦合度和内聚度。内聚度是衡量同一个模块内部的各个元素彼此结合的紧密程度;耦合度是衡量不同模块彼此间相互依赖的紧密程度。所以在软件设计中应尽量做到高内聚、低耦合。

解析:健壮性是指软件对于规范要求以外的输入情况的处理能力。健壮的系统是指对于规范要求以外的输入能够判断出这个输入不符合规范要求,并能有合理的处理方式。另外健壮性有时也和容错性、可移植性、正确性有交叉的地方。一个软件可以从错误的输入推断出正确合理的输入,这属于容错性量度标准,但是也可以认为这个软件是健壮的。

解析:数据结构:是指由某一数据对象中所有数据成员之间的关系组成的集合。

解析:数据结构相同,但对应的存储结构并不相同。

选项A 正确。数据结构的逻辑结构独立于其存储结构。

选项B 错误。数据结构的存储结构并不独立于该数据结构的逻辑结构。

选项C 错误。逻辑结构的在计算机中的实现方式(存储表示)有多种。

选项D 错误。数据结构有逻辑结构、存储结构和运算组成。

【第1题】答案ABCD

解析:算法的表示(描述工具)

(1)自然语言:算法可以用自然语言来描述,缺点是不够准确。(2)流程图

(3)程序设计语言;(4)伪代码(PDL):介于自然语言和程序设计语言之间的文字和符号表达工具。

【第2题】答案ABCD

解析:评价算法的优劣应考虑的主要因素

(1)算法的复杂度:时间复杂度和空间复杂度

(2)正确性:算法的正确性是评价一个算法优劣的最重要的标准。

(3)可读性(可理解):算法的可读性是指一个算法可供人们阅读的容易程度,算法是否容易理解。

(4)健壮性:健壮性是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性。

【第3题】答案:ABCD

解析:算法的必要满足条件(有些教材称为五大特性,最后一条拆为无输入和至少一输出):

①、确定性:算法的每一条指令必须有确切的定义,无二义性。

②、有穷性:是指算法必须在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。

③、可行性:算法中的描述在计算机中能执行,且在有穷时间内完成。

① 、至少有一个(1个或多个)输出,但是可以没有(0个或多个)输入

【第4题】答案:ABCD

解析:算法的表示(描述工具)

(1)自然语言:算法可以用自然语言来描述,缺点是不够准确。

(4)伪代码(PDL):介于自然语言和程序设计语言之间的文字和符号表达工具。

【第5题】答案:ABCD

解析:评价算法的优劣指标(算法的分析,考虑的因素)

算法分析是指对一个算法的运行时间和占用空间做定量的分析,一般计算出相应的数量级,常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度,提高算法的执行效率

(1)正确性:算法的正确性是评价一个算法优劣的最重要的标准。

(2)算法的复杂度:时间复杂度和空间复杂度。

(3)可读性(可理解):算法的可读性是指一个算法可供人们阅读的容易程度,算法是否容易理解。

(4)健壮性:健壮性是指一个算法对不合理数据输入的反应能力和处理能力,也称为容错性。

【第6题】答案:ABC

(1)算法的复杂度:算法效率的度量

(2)算法复杂度分类:时间复杂度和空间复杂度

①、时间复杂度:指执行算法所需要的计算工作量。通常,一个算法所用的时间包括编译时间和运行时间。度量方法是执行算法所需要的基本运算次数。

②、空间复杂度:指执行这个算法所需要的内存空间。包括算法程序所占的空间,输入的初始数据所占的空间,算法执行过程中所需的额外空间。

(3)空间复杂度和时间复杂度并不相关

【第7题】答案:ABCD

【第8题】答案:BCD

解析:线性表及其顺序存储结构

(1)线性表:由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。

(2)在复杂线性表中,由若干项数据元素组成的数据元素称为记录;由多个记录构成的线性表称为文件。

(3)非空线性表的结构特征:

①、有且只有一个根结点a1,它无前件

②、有且只有一个终端结点an,它无后件;

③、除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。

(4)结点个数n称为线性表的长度,当n=0时,称为空表

(5)线性表的顺序存储结构具有以下两个基本特点:

①、线性表中所有元素所占的存储空间是连续的;

②、线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

(6)线性表存储结构实现的举例:

①、数组:有序存储,占有一片连继地址,顺序存储结构的。

②、链表:无序存放的元素关联起来,链式存储结构的。

③、栈:先进后出(限定在一端),链式结构或顺序存储结构。

【第9题】答案:ABC

①、入栈运算,在栈顶位置插入元素;

②、退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);

【第10题】答案:ABCD

解析:)队列是一种特殊的线性表,只允许在表的一端插入,在另一端删除,允许插入的一端是队尾(rear),允许删除的一端为队头(front);当表中没有元素是空队列;队列是一种先进先出的线性表。(FIFO)

(2)队列的存储结构:

①、顺序存储结构:一维数组

②、链式存储:线性链表;

(3)队列的顺序存储结构一般采用循环队列的形式。循环队列s=0表示队列为空;s=1且front=rear表示队满。

①、入队运算:从队尾插入一个元素;

②、退队运算:从队头删除一个元素

解析∶衡量算法的五个特性(或满足条件)分别为∶有穷性、确定性(即无二义性)、可行性、输入及输出(可以没有输入,但一个算法必须有输出,没有输出的算法是毫无意义的)。

解析:算法就是计算机解题的过程,数据结构+算法=程序。

解析:算法中具有有穷性,一个算法总是在执行了有限步的操作后终止,而程序必不一定需要满足这个条件,比如程序中可以出现死循环。

解析:队列是一种特殊的线性表,只允许在表的一端插入,在另一端删除,允许插入的一端是队尾(rear),允许删除的一端为队头(front)。

解析:栈是一种特殊的线性表,只允许在表的一端进行插入和删除的线性表;插入,删除的一端为栈顶,另一端为栈底;当表中没有元素时为空栈。

解析:线性表:由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。

解析:线性结构:栈、队列、双向链表等

①、有且只有一个根结点

②、每个结点最多有一个前件,也最多有一个后件

解析:数据的逻辑结构是对数据元素之间的逻辑关系的描述,与数据的存储无关,是面向问题的,是独立于计算机的。

解析:数据的存储结构也称为数据的物理结构,是数据在计算机中的存放的方式,是面向计算机的,它包括数据元素的存储方式和关系的存储方式。

【第10题】答案:正确

解析:二叉树是一种特殊的树形结构,每个结点最多只有两棵子树,且有左右之分不能互换。

【第1题】答案有穷性

解析:一个算法必须保证执行有限步之后结束,即算法的有穷性,这一点与程序不同,程序不一定需要满足这一点,比如程序可能会进入死循环。

【第2题】答案算法分析

解析:关于算法,需要考虑以下三个方面的问题,即如何确定算法(算法设计)、如何表示算法(算法表示)及如何使算法更加有效(算法分析即算法的复杂度分析)

解析:程序=算法+数据结构(是由科学家尼克劳斯-沃思提出),算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。

【第4题】答案时间空间

解析:如果一个算法所编制的程序要反复运行多次 ,则应重点从时间代价考虑。如果待解决问题的数据量较大,则算法设计应重点考虑空间代价。

【第5题】答案

解析:数据的逻辑结构可以分为∶线性结构和非线性结构。线性结构,线性表、栈、队列,

字符串、数组、广义表。非线性结构,树、二叉树、森林、有向图、无向图。

解析:根据条件是否成立,反复执行一段程序,这是循环结构。

【第7题】答案:入栈运算;退栈运算

①、入栈运算,在栈顶位置插入元素;

②、退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);

③、读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。

【第8题】答案:前序;中序;后序

解析:二叉树遍历:前序、中序和后序

}

我要回帖

更多关于 5/2,7/4,11/8,19/16 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信