数据结构.doc

1、二叉树 两种存储结构的优缺点顺序存储可能会浪费空间(在非完全二叉树的时候)，但是读取某个指定的节点的时候效率比较高 O(0)链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低 O(nlogn)编写一个程序，要求能完成排序和查找，分别使用链表，数组和二叉树等数据结构，比较各种方法的优缺点。思路很简单，根放在 0 位置，以后假定当前位置是 i，那么左子结点在 2i+1，右子结点在 2i+2。比如根的左子结点在 1，右子结点在 2。结点 1 的左子结点在 3，右子结点在 4。定义一种空值表示没有子结点，比如 empty。假定一个结点由 3 个成员组成： value, le

2、ft, right数组假定是全局的，如果不是可以作为参数传送。递归实现比较简单：void btree2array(node, index)if(node = NULL)arrayindex = empty;arrayindex = node-value;btree2array(node-left, index * 2 + 1);btree2array(node-right, index * 2 + 2);5.1.5.1 树的基本概念树是一个或多个结点组成的有限集合 T，有一个特定的结点称为树的根结点，其余的结点被分成 m（m0）个不相交的集合 T1、 T2、 、Tm，每一个集合本身又是一棵树，

3、被称为这个根结点的子树。图 5.11 所示是一棵具有 10 个结点的树，结点 A 为树的根结点，除 A 之外的其余结点分为 3 个不相交的集合 T1=B，E ，F 、T2=C，G 和 T3=D，H ，I ，J ，形成了结点 A 的 3棵子树，T1、T2 和 T3 本身也分别是一棵树。例如，子树 T1的根结点为 B，其余结点又分为两个不相交的集合E和F ，它们形成了子树 T1 的根结点 B 的两棵子树。图 5.11 一棵具有 10 个结点的树树的基本术语有：孩子、双亲、兄弟：树中某结点的各子树的根称为该结点的孩子；相应地该结点称为其孩子的双亲；具有相同双亲的结点互称为兄弟。图 5.11 中，结点

4、 B、C、D 都是结点 A 的孩子，结点 A 是结点 B 的双亲，也是结点 C、D 的双亲，结点 B、C、D 互为兄弟。结点的度：一个结点所拥有的子树的个数称为该结点的度。图 5.11 中，结点 A 的度为 3，结点 B 的度为 2，结点 E 的度为0。叶结点、分支结点：度为 0 的结点称为叶结点，或者称为终端结点；度不为 0 的结点称为分支结点，或者称为非终端结点。图 5.11 中，结点 A、B、C、D 为分支结点，结点E、F、G、H、I、J 为叶结点。结点的层数：规定树的根结点的层数为 1，其他任何结点的层数等于它的双亲结点的层数加 1。图 5.11 中，结点 A 的层数为 1，结点 B、

5、C、D 的层数为 2，结点 E、F、G、H、I、J 的层数为 3。树的深度：一棵树的叶结点的最大层数称为树的深度。图5.11 所示的树的深度为 3。Hash 算法hash 算 法 的 意 义 在 于 提 供 了 一 种 快 速 存 取 数 据 的 方 法 ,它 用 一 种 算 法 建 立 键 值 与 真实 值 之 间 的 对 应 关 系 ,(每 一 个 真 实 值 只 能 有 一 个 键 值 ,但 是 一 个 键 值 可 以 对 应 多 个 真 实值 ),这 样 可 以 快 速 在 数 组 等 数 据 结 构 中 存 取 数 据 . 例 如 : /HashTable.h template cl

6、ass HashTable public : HashTable( int count ) ; void put( T* t ,int key ) ; T* get( int key ) ; private : T* tArray ; /HashTable.cpp template HashTable:HashTable( int count ) tArray = new T*count ; template void HashTable:put( T* t , int key ) this-tArray key = t ; template T* HashTable:get( int key

7、 ) return this-tArray key ; 这 样 ,我 们 只 要 知 道 key 值 ,就 可 以 快 速 存 取 T 类 型 的 数 据 ,而 不 用 像 在 链 表 等 数 据结 构 中 查 找 一 样 , 要 找 来 找 去 的 . 至 于 key 值 ,一 般 都 是 用 某 种 算 法 (所 谓 的 Hash 算法 )算 出 来 的 .例 如 :字 符 串 的 Hash 算 法 , char* value = “hello“; int key = (27* (int)h+27)* (int)e) + 27) * (int)l) + 27) * (int)l +27)

8、* 27 ) + (int)o ; Hash 函 数 处 理 流程 Hash， 一 般 翻 译 做 “散 列 “， 也 有 直 接 音 译 为 “哈 希 “的 ， 就 是 把 任 意 长 度 的 输 入 （ 又叫 做 预 映 射 ， pre-image） ， 通 过 散 列 算 法 ， 变 换 成 固 定 长 度 的 输 出 ， 该 输 出 就 是 散 列值 。 这 种 转 换 是 一 种 压 缩 映 射 ， 也 就 是 ， 散 列 值 的 空 间 通 常 远 小 于 输 入 的 空 间 ， 不 同 的输 入 可 能 会 散 列 成 相 同 的 输 出 ， 而 不 可 能 从 散 列 值 来

9、唯 一 的 确 定 输 入 值 。 简 单 的 说 就 是一 种 将 任 意 内 容 的 输 入 转 换 成 相 同 长 度 输 出 的 加 密 方 式 .Hash，一般翻译做“ 散列”，也有直接音译为“哈希“ 的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M) ，其中 H( )-单向散列函数，M-任意长度明文，h- 固定长度散列值。 在信息安全领域中应用的 Ha

10、sh 算法，还需要满足其他关键特性： 第一当然是单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的 M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的 Hash 又被称为“消息摘要(message digest)“，就是要求能方便的将“消息“进行 “摘要“，但在“摘要“ 中无法得到比“摘要“本身更多的关于“消息“的信息。 第二是抗冲突性(collision-resistant)，即在统计上无法产生 2 个散列值相同的预映射。第三是映射分布均匀性和差分分布均匀性，散列结果中，

11、为 0 的 bit 和为 1 的 bit ，其总数应该大致相等；MD5 和 SHA1 可以说是目前应用最广泛的 Hash 算法，而它们都是以 MD4 为基础设计的。零拷贝零 拷 贝 （ zero-copy） 是 实 现 主 机 或 路 由 器 等 设 备 高 速 网 络 接 口 的 主 要 技 术 。 零 拷 贝技 术 通 过 减 少 或 消 除 关 键 通 信 路 径 影 响 速 率 的 操 作 ， 降 低 数 据 传 输 的 操 作 系 统 开 销 和 协议 处 理 开 销 ， 从 而 有 效 提 高 通 信 性 能 ， 实 现 高 速 数 据 传 输 。 零 拷 贝 技 术 可 以 减

12、少 数 据 拷 贝 和 共 享 总 线 操 作 的 次 数 ， 消 除 通 信 数 据 在 存 储 器 之 间不 必 要 的 中 间 拷 贝 过 程 ， 有 效 地 提 高 通 信 效 率 ， 是 设 计 高 速 接 口 通 道 、 实 现 高 速 服 务 器和 路 由 器 的 关 键 技 术 之 一 。 数 据 拷 贝 受 制 于 传 统 的 操 作 系 统 或 通 信 协 议 ， 限 制 了 通 信 性能 。 采 用 零 拷 贝 技 术 ， 通 过 减 少 数 据 拷 贝 次 数 ， 简 化 协 议 处 理 的 层 次 ， 在 应 用 和 网 络 间提 供 更 快 的 数 据 通 路 ，

13、可 以 有 效 地 降 低 通 信 延 迟 ， 增 加 网 络 吞 吐 率 。 零 拷 贝 技 术 的 研 究 主 要 针 对 以 下 两 个 方 面 ： (1) 创 建 有 效 的 用 户 级 通 信 接 口 ， 即应 用 程 序 直 接 将 数 据 从 通 信 接 口 发 送 出 去 或 接 收 进 来 ， 消 除 系 统 内 核 中 不 必 要 的 拷贝 过 程 ； (2) 路 由 器 的 入 端 到 出 端 的 直 接 数 据 传 输 ， 即 接 收 的 报 文 只 经 过 一 次 存 储 器 缓冲 ， 而 缓 冲 队 列 中 的 报 文 经 过 必 要 的 控 制 信 息 处 理 后

14、 ， 直 接 传 送 到 输 出 端 口 发 送 出 去 ，实 现 报 文 快 速 转 发 。 一 般 来 说 , 认 为 从 网 卡 到 用 户 空 间 的 系 统 调 用 会 经 历 两 次 或 者 两 次 半 的 copy 过程 . zero copy 就 是 要 消 除 这 些 copy 过 程 . 从 网 卡 的 ring-buffer 到 software packets 的 copy 可 以 通 过 直 接 DMA 数 据 到software packet 完 成 . 所 谓 半 次 copy 可 以 有 hardware checksum offload 来 解 决 . 最 后

15、 的 内 核 空 间 到 用 户 空 间 的 copy 还 存 在 问 题 , 最 近 提 出 的 比 较 好 的 方 案 是IOAT2 技 术 , 可 以 直 接 做 Host memeory 对 Host memroy 的 DMA. 也 看 到 有 人 使 用 把 DMA 的 buffer 直 接 map 到 用 户 空 间 的 解 决 方 案 , 但 这 个 对 用户 空 间 的 程 序 不 是 透 明 的 , 不 具 备 普 遍 意 义 .Linux的 进 程 间 通 信 （ IPC， InterProcess Communication） 通 信 方 法 有 管 道 、 消 息 队

16、列 、信 号 量 、 共 享 内 存 、 套 接 口 等 管 道 包 括 三 种 :1)普 通 管 道 PIPE, 通 常 有 种 限 制 ,一 是 半 双 工 ,只 能 单 向传 输 ;二 是 只 能 在 父 子 进 程 间 使 用 . 2)流 管 道 s_pipe: 去 除 了 第 一 种 限 制 ,可 以 双 向 传 输 . 3)命 名 管 道 :name_pipe, 去 除 了 第 二 种 限 制 ,可 以 在 许 多 并不 相 关 的 进 程 之 间 进 行 通 讯 .管 道 的 使 用 方 法 ? 答 : 主 要 有 下 面 几 种 方 法 : 1)pipe, 创 建 一 个 管

17、道 ,返 回 2 个 管 道描 述 符 .通 常 用 于 父 子 进 程 之 间 通 讯 . 2)popen, pclose: 这 种 方 式 只 返 回一 个 管 道 描 述 符 ,常 用 于 通 信 另 一 方 是 stdin or stdout; 3)mkpipe: 命 名管 道 , 在 许 多 进 程 之 间 进 行 交 互 .FAQ3: 管 道 与 系 统 IPC 之 间 的 优 劣 比 较 ? 答 : 管 道 : 优 点 是 所 有 的 UNIX 实 现 都 支 持 , 并 且 在 最 后 一 个 访 问 管 道的 进 程 终 止 后 ,管 道 就 被 完 全 删 除 ;缺 陷 是

18、 管 道 只 允 许 单 向 传 输 或 者 用 于 父 子进 程 之 间 . 系 统 IPC: 优 点 是 功 能 强 大 ,能 在 毫 不 相 关 进 程 之 间 进 行 通 讯 ; 缺 陷 是关 键 字 KEY_T 使 用 了 内 核 标 识 ,占 用 了 内 核 资 源 ,而 且 只 能 被 显 式 删 除 ,而 且不 能 使 用 SOCKET 的 一 些 机 制 ,例 如 select,epoll 等 . FAQ4: WINDOS 进 程 间 通 信 与 LINUX 进 程 间 通 信 的 关 系 ? 答 : 事 实 上 ,WINDOS 的 进 程 通 信 大 部 分 移 植 于 U

19、NIX, WINDOS 的 剪 贴 板 ,文件 映 射 等 都 可 从 UNIX 进 程 通 信 的 共 享 存 储 中 找 到 影 子 . FAQ5: 进 程 间 通 信 与 线 程 间 通 信 之 间 的 关 系 ? 答 : 因 为 WINDOWS 运 行 的 实 体 是 线 程 , 狭 义 上 的 进 程 间 通 信 其 实 是指 分 属 于 不 同 进 程 的 线 程 之 间 的 通 讯 .而 单 个 进 程 之 间 的 线 程 同 步 问 题 可 归并 为 一 种 特 殊 的 进 程 通 信 .它 要 用 到 内 核 支 持 的 系 统 调 用 来 保 持 线 程 之 间 同步 .

20、通 常 用 到 的 一 些 线 程 同 步 方 法 包 括 :Event, Mutex, 信 号 量 Semaphore, 临 界 区 资 源 等 .1.引 起 创 建 进 程 的 事 件1） 用 户 登 录 。 2） 作 业 调 度 。 3） 提 供 服 务 。 4） 应 用 请 求 。11.进 程 的 调 度 算 法进 程 的 调 度 算 法 包 括 ： FIFO（ First Input First Output 先 进 先 出 法 ） 、 RR（ 时 间 片 轮 转 算 法 ） 、 （ HPF） 最 高 优 先 级 算 法 。进 程 的 定 义进 程 是 一 个 具 有 一 定 独 立

21、 功 能 的 程 序 关 于 某 个 数 据 集 合的 一 次 运 行 活 动 。 它 是 操 作 系 统 动 态 执 行 的 基 本 单 元 ，在 传 统 的 操 作 系 统 中 ， 进 程 既 是 基 本 的 分 配 单 元 ， 也 是基 本 的 执 行 单 元 。进 程 与 线 程 的 关 系通 常 在 一 个 进 程 中 可 以 包 含 若 干 个 线 程 ， 它 们 可 以 利 用 进 程 所 拥 有 的 资 源 。 在 引 入线 程 的 操 作 系 统 中 ， 通 常 都 是 把 进 程 作 为 分 配 资 源 的 基 本 单 位 ， 而 把 线 程 作 为 独 立 运 行和 独

22、立 调 度 的 基 本 单 位 。 由 于 线 程 比 进 程 更 小 ， 基 本 上 不 拥 有 系 统 资 源 ， 故 对 它 的 调 度所 付 出 的 开 销 就 会 小 得 多 ， 能 更 高 效 的 提 高 系 统 内 多 个 程 序 间 并 发 执 行 的 程 度 。 因 而 近 年 来 推 出 的 通 用 操 作 系 统 都 引 入 了 线 程 ， 以 便 进 一 步 提 高 系 统 的 并 发 性 ， 并把 它 视 为 现 代 操 作 系 统 的 一 个 重 要 指 标 。线程线程（thread, 台湾称 执行绪）是“进程“ 中某个单一顺序的控制流。也被称为轻量进程线 程 的

23、好 处引 入 线 程 的 好 处 ： 线 程1 创 建 一 个 新 线 程 花 费 的 时 间 少 。 2 两 个 线 程 的 切 换 时 间 少 。 3 由 于 同 一 个 进 程 内 的 线 程 共 享 内 存 和 文 件 ， 所 以 线 程 之 间 互 相 通 信 必 须 调 用 内 核 。4 线 程 能 独 立 执 行 ， 能 充 分 利 用 和 发 挥 处 理 机 与 外 围 设 备 并 行 工 作 的 能 力 。线 程 调 度 与 优 先 级有 线 程 进 入 了 就 绪 状 态 ， 需 要 有 线 程 调 度 程 序 来 决 定 何 时 执 行 ， 根 据 优 先 级 来 调度

24、。 TCP/IP 的分层如下：应用层传输层网络层网络接口层IP 处在互连网络层。负责提供基本的数据封包传送功能，让每一块数据包都能够到达目的主机（但不检查是否被正确接收）。TCP 与 UDP 在传输层。它提供了节点间的数据传送，应用程序之间的通信服务，主要功能是数据格式化、数据确认和丢失重传等。如传输控制协议（TCP）、用户数据报包议（UDP）等，TCP 和 UDP 给数据包加入传输数据并把它传输到下一层中，这一层负责传送数据，并且确定数据已被送达并接收。TCP 和 UDP 都是建立在 IP 之上的，传输过程如下：发送：1 应用层层将数据传到传输层2 传输层层会自动把数据分成若干的 tcp 包或者 udp 包，分这些包时每个包上都加入 tcp 或 udp 包头（加入端口号等等很多信息）再将些包传给网络层。4 网络层把传来的每个 tcp 包或 udp 包再分成若干个 ip 包，加入 ip 包头（加入本地 ip 地址，目的 ip 地址等等信息），再往下就是网络接口层5 网络接口层就用到物理设备，网卡根据目的 ip 地址查询到 mac 地址，把数据传给接收方。接收：1 接收方的网络接口层向网络层提供 ip 包2 传输层再把这些 ip 包组合起来成为 tcp 或者 udp 包3 网络层把数据再向上返给应用层。