《算法与数据结构(实践)》

辽宁省高等教育 实践考试 软件技术 应用本科 专业 实 验 报 告 书 课程名称 助学单位 姓 名 准考证号 成 绩 二 一一 年 四 月 1 实验一 顺序表的应用 一 实验目的一 实验目的 1 会定义线性表的顺序存储类型 2 熟悉 C 程序的基本结构 掌握程序中的用户头文件 实现文件和主文件之间的相互关 系及各自作用 3 熟悉对线性表的一些基本操作和具体的函数定义 4 熟悉 C 操作环境的使用以及多文件的输入 编辑 调试和运行的全过程 二 实验内容二 实验内容 该程序的功能是对元素类型为整型的顺序存储的线性表进行一些操作 该程序包含三 个文件 一个为头文件 用来存储定义的线性表结构类型以及对线性表进行的各种操作的 函数声明 第二个为线性表操作的实现文件 用来存储每一种线性表操作的具体函数定义 第三种为主文件 用来定义线性表和调用线性表的一些操作 实现对给定线性表的具体运 算 整个程序如下 头文件头文件 linearlist1 hlinearlist1 h typedef int ElemType struct LinearList ElemType list 存线性表元素 int size 存线性表长度 int MaxSize 存 list 数组长度 void InitList LinearList void ClearList LinearList int ListSize LinearList bool ListEmpty LinearList bool ListFull LinearList void TraverList LinearList bool FindList LinearList bool UpdateList LinearList bool InsertList LinearList bool DeleteList LinearList void OrderOutputList LinearList 实现文件实现文件 linearlist1 cpplinearlist1 cpp include include include linearlist1 h void InitList LinearList if L list cerr Memory allocation failure ENDL exit 1 L size 0 L MaxSize ms 2 void ClearList LinearList int ListSize LinearList bool ListEmpty LinearList bool ListFull LinearList void TraverList LinearList i cout L list i cout ENDL bool FindList LinearList i if L list i item item L list i return true return false bool UpdateList LinearList i if L list i item L list i item return true return false bool InsertList LinearList if mark 0 for int i L size 1 i 0 i L list i 1 L list i L list 0 item else if mark 0 L list L size item 3 else for int i 0 i if item for int j L size 1 j i j L list j 1 L list j L list i item L size return true bool DeleteList LinearList if mark 0 item L list 0 for int i 1 i L list i 1 L list i else if mark 0 item L list L size 1 else for int i 0 i if L list i item break if i L size return false else item L list i for int j i 1 j L list j 1 L list j L size return true void OrderOutputList LinearList int i k for i 0 i b i i for i 1 i k i 1 for int j i j if mark 1 b i 1 b k b k x for i 0 i cout L LIST B I SPAN cout ENDL 主文件主文件 listmain1 cpplistmain1 cpp include 4 const int ML 10 include linearlist1 h void main LinearList a InitList a ML int i ElemType x cout 从键盘输入 5 个整数 for i 0 i x InsertList a x 1 cout x InsertList a x 1 cin x InsertList a x 1 TraverList a OrderOutputList a 1 OrderOutputList a 0 LinearList b InitList b ML for i 0 i InsertList b a list i 0 TraverList b if DeleteList a x 1 cout Delete success ENDL else cout Delete fail ENDL if DeleteList a x 1 cout Delete success ENDL else cout Delete fail ENDL cout x if DeleteList a x 0 cout Delete success ENDL else cout Delete fail ENDL TraverList a 三 实验步骤三 实验步骤 1 进入 MICROSOFT VISUAL C 6 0 2 在主菜单上选择 文件 新建 3 出现 新建 对话框 选择 工程 页面框 并选中 Win32 Console Application 类型 为该类工程取一名字 TEST1 依次按 确定 完成 按钮 4 再次进入 新建 对话框 选择 文件 页面框 并选中 C C Header File 类型 为该类文件取一名字 linearlist1linearlist1 按 确定 5 出现该程序的输入窗口 输入 linearlist1 hlinearlist1 h 文件内容 并保存 6 再次进入 新建 对话框 选择 文件 页面框 并选中 C Source File 类型 为该类文件取一名字 linearlist1linearlist1 按 确定 7 出现该程序的输入窗口 输入 linearlist1 cpplinearlist1 cpp 文件内容 并保存 8 再次进入 新建 对话框 选择 文件 页面框 并选中 C Source File 类型 为该类文件取一名字 listmain1listmain1 按 确定 5 9 出现该程序的输入窗口 输入 listmain1 cpplistmain1 cpp 文件内容 并保存 10 在主菜单上选择 编译 编译 listmain1 cpplistmain1 cpp 然后对出现的各种错误进行改正 直到编译成功 即出现 0 errors 11 在主菜单上选择 编译 构件 test exe 然后对出现的各种错误进行改正 直 到链接成功 12 在主菜单上选择 编译 执行 test exe 13 出现运行窗口 提示 从键盘输入 5 个整数 输入 5 10 2 8 20 14 提示 从键盘输入 2 个整数 输入 3 15 15 显示出下列几行结果 15 3 5 10 2 8 20 2 3 5 8 10 15 20 20 15 10 8 5 3 2 2 3 5 8 10 15 20 Delete success Delete success 分析 第 1 行是线性表 a 中元素原来的序列 第 2 行是 a 中的升序序列 第 3 行 是 a 中的降序序列 第 4 行是线性表 b 中元素的序列 第 5 行是在 a 中成功删除 表头的提示 第 6 行是在 a 中成功删除表尾的提示 16 提示 从键盘上输入一个待删除的整数 输入 8 17 显示出下列 2 行结果 Delete success 3 5 10 2 分析 第 1 行是成功删除 8 后的提示 第 2 行是表 a 中的当前元素 总结 程序执行结果构符合主文件的设计和语句 6 实验二 链表的应用 一 一 实验目的实验目的 1 熟悉 C 语言的上机环境 掌握 C 语言的基本结构 2 会定义线性表的链式存储结构 3 熟悉对链表的一些基本操作和具体的函数定义 4 本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理 二 实验内容实验内容 1 创建和销毁链表存储结构 要求达到 熟练掌握 层次 2 实现链表的基本操作 要求达到 熟练掌握 层次 3 链表的简单应用 要求达到 基本掌握 层次 现假设链表结点仅含一个数据域和一个指针域 数据域是为了描述通讯者的 相关信息 定义通讯者的结点类型 typedef struct char num 5 编号 char name 9 姓名 char sex 3 性别 char phone 13 电话 char addr 31 地址 DataType 因此 线性表的链式存储结构定义如下 typedef struct node 结点类型定义 DataType data 结点数据域 struct node next 结点指针域 ListNode typedef ListNode LinkList ListNode p 定义一个指向结点的指针变量 LinkList head 定义指向单链表的头指针 这里的 LinkList 和 ListNode 是不同名字的同一指针类型 取不同的名是为了在概念 上更明确 特别值得注意的是指针变量和指针指向的变量 结点变量 这两个概念 指针 变量要么为空 Null 不指向任何结点 要么其值为非空 即它的值是一个结点的存储地 址 指针变量所指向的结点并没有具体说明 而是在程序执行过程中 需要存储结点时才 产生 它是通过 C 语言的标准函数 malloc 实现的 例如 给指针变量 p 分配一个结点的地 址 p ListNode malloc sizeof ListNode 该语句的功能是申请分配一个类型为 ListNode 的结点的地址空间 并将其首地址存入指针变量 p 中 当结点不需要时可以用标 准函数 free p 释放结点的存储空间 这时 p 为空值 Null 为了验证算法 本章的设计分为两个实验 其一是通讯录的管理 包括单通讯录链表 的建立 通讯者的插入 通讯者的删除 通讯者的查询以及通讯录表的输出等 其二是利 用单循环链表解决约瑟夫游戏生者与死者的选择问题 通讯录管理 为了实现通讯录管理的几种操作功能 首先设计一个含有多个菜单的主控菜 单程序 然后再为这些菜单配上相应功能 三 三 实验步骤实验步骤 1 主控菜单设计要求 1 菜单内容 程序运行后 给出 6 个菜单项的内容和输入提示 1 通讯录链表的建立 7 2 通讯者结点的插入 3 通讯者结点的查询 4 通讯者结点的删除 5 通讯录链表的输出 6 退出管理系统 2 设计要求 使用数字 0 5 来选择菜单项 其它输入不起作用 完整程序清单 主控菜单处理测试程序 main2 c include stdio h include string h include stdlib h typedef struct 通讯录结点类型 char num 5 编号 char name 9 姓名 char sex 3 性别 char phone 13 电话 char addr 31 地址 DataType typedef struct node 结点类型定义 DataType data 结点数据域 struct node next 结点指针域 ListNode typedef ListNode LinkList LinkList head ListNode p 函数说明 int menu select LinkList CreateList void Void InsertNode LinkList head ListNode p ListNode ListFind LinkList head Void DelNode LinkList head Void PrintList LinkList head 主函数 void main for switch menu select case 1 printf n printf 通 讯 录 链 表 的 建 立 n printf n head CreateList break case 2 printf n printf 通 讯 者 信 息 的 添 加 n printf n printf 编号 4 姓名 8 性别 3 电话 11 地址 31 n 8 printf n p ListNode malloc sizeof ListNode 申请新结点 scanf s s s s s p data num p data name p data sex p data phone p data addr InsertNode head p break case 3 printf n printf 通 讯 录 信 息 的 查 询 n printf n p ListFind head if p NULL printf 编号 姓 名 性别 联系电话 地址 n printf n printf s s s s s n p data num p data name p data sex p data phone p data addr printf n else printf 没有查到要查询的通讯者 n break case 4 printf n printf 通 讯 录 信 息 的 删 除 n printf n DelNode head 删除结点 break case 5 printf n printf 通 讯 录 链 表 的 输 出 n printf n printList head break case 0 printf t 再 见 n return 菜单选择函数程序 int menu select int sn printf 通讯录管理系统 n printf n printf 1 通讯链表的建立 n printf 2 通讯者结点的插入 n printf 3 通讯者结点的查询 n printf 4 通讯者结点的删除 n 9 printf 5 通讯录链表的输出 n printf 0 退出管理系统 n printf n printf 请 选 择 0 5 for scanf d if sn5 printf n t 输入错误 重选 0 5 else break return sn LinkList CreateList void 尾插法建立带头结点的通讯录链表算法 LinkList head ListNode malloc sizeof ListNode 申请头结点 ListNode p rear int flag 0 结束标志置 0 rear head 尾指针初始指向头结点 while flag 0 p ListNode malloc sizeof ListNode 申新结点 printf 编号 4 姓名 8 性别 电话 11 地址 31 n printf n scanf s s s s s p data num p data name p data sex p data phone p data addr rear next p 新结点连接到尾结点之后 rear p 尾指针指向新结点 printf 结束建表吗 1 0 scanf d rear next NULL 终端结点指针置空 return head 返回链表头指针 void InsertNode LinkList head ListNode p ListNode p1 p2 p1 head p2 p1 next while p2 NULL p2 指向表的下一个结点 p1 next p 插入 p 所指向的结点 p next p2 连接表中剩余的结点 有序通讯录链表的查找 10 ListNode ListFind LinkList head 有序通讯录链表上的查找 ListNode p char num 5 char name 9 int xz printf n printf 1 按编号查询 n printf 2 按姓名查询 n printf n printf 请 选 择 p head next 假定通讯 录表带头结点 scanf d if xz 1 printf 请输入要查找者的编号 scanf s num while p if p NULL strcmp p data num num 0 p NULL 没有查到要查找的通讯者 else if xz 2 printf 请输入要查找者的姓名 scanf s name while p return p void DelNode LinkList head char jx ListNode p q P ListFind head 调用查找函数 if p NULL printf 没有查到要删除的通讯者 n return printf 真的要删除该结点吗 y n scanf c if jx y jx Y q head while q NULL q next p next 删除结点 free p 释放被删结点空间 printf 通讯者已被删除 n 11 void printList LinkList head ListNode p p head next printf 编号 姓 名 性别 联系电话 地址 n printf n while p NULL printf s s s s s n p data num p data name p data sex p data phone p data addr printf n p p next 后移一个结点 12 实验 3 栈和队列的应用 一 实验目的一 实验目的 1 熟练掌握栈和队列的结构 以及这两种数据结构的特点 2 能够在两种存储结构上实现栈的基本运算 特别注意栈满和栈空的判断条件及描 述方法 3 熟练掌握链队列和循环队列的基本运算 并特别注意队列满和队列空的判断条件 和描述方法 二 实验内容二 实验内容 计算表达式的值 以字符序列的形式从终端输入语法正确的 不含变量的整数表达式 利用课堂讲授时给出的算符优先关系 实现对算术四则混合运算表达式的求值 只考虑运 算数为一位整数 0 9 的情况 三 三 实验步骤实验步骤 1 1 理解栈的基本工作原理 2 仔细分析实验内容 给出其算法和流程图 3 用 C 语言实现该算法 4 给出测试数据 并分析其结果 5 在实验报告册上写出实验过程 2 1 设置运算符栈和运算数栈辅助分析算符优先关系 2 在读入表达式的字符序列的同时 完成运算符和运算数的识别处理 以及相应的 运算 3 在识别出运算数的同时 要将其字符序列形式转换成整数形式 4 在程序的适当位置输出运算符栈 运算数栈 输入字符和主要操作的内容 以帮 助你分析程序 3 测试数据 8 1 2 3 4 88 1 3 1024 8 16 1024 8 16 22 3 8 2 3 3 3 8 9 9 2 5 3 2 4 3 6 4 选做题 1 假设一个算术表达式中包含零对到多对圆括弧 括弧对之间允许嵌套但不允许交 叉 编写一个算法并上机实现 判断输入的表达式是否正确配对 2 用栈实现一般表达式 即中缀表达式 到后缀表达式的转换 3 某银行有一个客户办理业务站 在单位时间内随机地有客户到达 设每位客户的 业务办理时间是某个范围内的随机值 设只有一个窗口 一位业务人员 要求程序模拟统 计在设定时间内 业务人员的总空闲时间和客户的平均等待时间 假定模拟数据已按客户 到达的先后顺序依次存于某个正文数据文件中 对应每位客户有两个数据 到达时间和需 要办理业务的时间 13 实验 4 树和二叉树的应用 一 实验目的一 实验目的 1 熟练掌握树的基本概念 二叉树的基本操作及在链式存储结构上的实现 2 重点掌握二叉树的生成 遍历及求深度等算法 3 掌握二叉树的线索化及线索二叉树的遍历算法 掌握赫夫曼树的含义及其应用 4 掌握运用递归方式描述算法及编写递归 C 程序的方法 提高算法分析和程序设计 能力 二 实验内容二 实验内容 Huffman 编 译码器 利用 Huffman 编码进行通信可以大大提高信道利用率 缩短信 息传输时间 降低传输成本 但是 这要求在发送端通过一个编码系统对待传数据预先编 码 在接受端将传来的数据编码进行译码 复原 对于有些信道 每端都需要一个完整 的编 译码系统 试为这样的信息收发站编写一个 Huffman 的编 译码系统 三 三 实验步骤实验步骤 1 1 理解 Huffman 树的基本工作原理 2 仔细分析实验内容 给出其算法和流程图 3 用 C 语言实现该算法 4 给出测试数据 并分析其结果 5 在实验报告册上写出实验过程 2 实验帮助 一个完整的系统应具有以下功能 1 初始化 从键盘读入 n 个字符 以及它们的权值 建立 Huffman 树 具体算法 可参见教材算法 2 编码 根据建立的 Huffman 树 求每个字符的 Huffman 编码 对给定的待编码字 符序列进行编码 3 译码 利用已经建立好的 Huffman 树 对上面的编码结果译码 译码的过程是分 解电文中的字符串 从根结点出发 按字符 0 和 1 确定找左孩子或右孩子 直至叶结点 便求得该子串相应的字符 4 打印 Huffman 树 3 测试数据 1 根据运行提示 依次输入待编码的字符个数和这些字符 以及每个字符的权值 输入 4 个字符 a b c 和 d 及 4 个对应的权值 7 5 2 和 4 输出 a 0 b 10 c 110 d 111 3 读者可根据运行提示 自行指定数据 观察程序的运行结果 14 实验 5 图的应用 一 实验目的一 实验目的 1 掌握图的邻接矩阵和邻接表两种存储方法 2 掌握有关图的操作算法并用高级语言实现 3 熟悉图的构造算法 了解实际问题的求解效率与采用何种存储结构与算法有着密切 联系 4 掌握图的两种搜索路径的遍历算法 5 掌握求图的最小生成树的普里姆算法和克鲁斯卡尔算法 二 实验内容二 实验内容 1 创建给定图的存储结构 从邻接表和邻接矩阵两种存储方式中选择一种 2 对所创建的图进行深度和广度优先搜索遍历 给出遍历过程中的顶点序列 3 求图的最小生成树 按构造顺序输出边的序列 两种方法都要求 3 编写一个主函数 将上面函数连在一起 构成一个完整程序 4 将实验源程序调试并运行 三 实验步骤三 实验步骤 所建立的图为 1 4 3 2 5 6 7 10 25 15 30 20 50 45 35 用邻接表存储结构时 所创建的单链表以结点的从小到大排列 注意标志数组 visited n 1 的定义和赋值 将顶点 1 作为起点 实验结果 输入输出结果截图 15 图 图的操作 实验总结 通过本次实验 我更好地掌握了图的相关操作 能够熟练地进行图的建立 遍历 在编写程序时 遇到很多不大明白的地方 在得到同学们的鼎力相助后 基本解 决了这些问题 16 实验六 散列表的应用 一 实验目的一 实验目的 1 复习 C 中的全局变量的概念 2 学习图的邻接矩阵和邻接表两种存储方式 3 学习图的两种遍历方法和求图的最小生成树的方法 二 实验内容实验内容 1 散列表存储结构的创建和销毁 2 实现散列表的基本操作 如插入 删除和查找等 3 解决散列冲突方法的应用 如开放地址法和链地址法等 三 实验步骤实验步骤 1 散列表存储结构的创建和销毁 要求达到 熟练掌握 层次 2 实现散列表的基本操作 要求达到 熟练掌握 层次 3 解决散列冲突方法的应用 要求达到 基本掌握 层次 散列表的冲突现象 1 冲突 两个不同的关键字 由于散列函数值相同 因而被映射到同一表位置上 该现象称为 冲突 Collision 或碰撞 发生冲突的两个关键字称为该散列函数的同义词 Synonym 2 安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突 要做到这一点必须满足两个条件 其一是 U m 其二是选择合适的散列函数 这只适用于 U 较小 且关键字均事先已知的情况 此时 经过精心设计散列函数 h 有可能完全避免冲突 3 冲突不可能完全避免 通常情况下 h 是一个压缩映像 虽然 K m 但 U m 故无论怎样设计 h 也不可能 完全避免冲突 因此 只能在设计 h 时尽可能使冲突最少 同时还需要确定解决冲突的方 法 使发生冲突的同义词能够存储到表中 4 影响冲突的因素 冲突的频繁程度除了与 h 相关外 还与表的填满程度相关 设 m 和 n 分别表示表长和 表中填人的结点数 则将 n m 定义为散列表的装填因子 Load Factor 越大 表越满 冲突的机会也越大 通常取 1 处理冲突的方法 通常有两类方法处理冲突 开放定址 Open Addressing 法和拉链 Chaining 法 前者 是将所有结点均存放在散列表 T 0 m 1 中 后者通常是将互为同义词的结点链成一个单链 表 而将此链表的头指针放在散列表 T 0 m 1 中 开放定址法 1 开放地址法解决冲突的方法 用开放定址法解决冲突的做法是 当冲突发生时 使用某种探查 亦称探测 技术在散列 表中形成一个探查 测 序列 沿此序列逐个单元地查找 直到找到给定的关键字 或者碰 到一个开放的地址 即该地址单元为空 为止 若要插入 在探查到开放的地址 则可将待 插入的新结点存人该地址单元 查找时探查到开放的地址则表明表中无待查的关键字 即查找失败 注意 用开放定址法建立散列表时 建表前须将表中所有单元 更严格地说 是指单元中存储的 关键字 置空 空单元的表示与具体的应用相关 总之 应该用一个不会出现的关键字来表示空单元 2 开放地址法的一般形式 17 开放定址法的一般形式为 h i h key d i m 1 i m 1 其中 h key 为散列函数 d i 为增量序列 m 为表长 h key 是初始的探查位置 后续的探查位置依次是 h l h 2 h m 1 即 h key h l h 2 h m 1 形成了一个探查序列 若令开放地址一般形式的 i 从 0 开始 并令 d 0 0 则 h 0 h key 则有 h i h key d i m 0 i m 1 探查序列可简记为 h i 0 i m 1 3 开放地址法堆装填因子的要求 开放定址法要求散列表的装填因子 l 实用中取 为 0 5 到 0 9 之间的某个值为宜 4 形成探测序列的方法 按照形成探查序列的方法不同 可将开放定址法区分为线性探查法 二次探查法 双重 散列法等 拉链法 1 拉链法解决冲突的方法 拉链法解决冲突的做法是 将所有关键字为同义词的结点链接在同一个单链表中 若选 定的散列表长度为 m 则可将散列表定义为一个由 m 个头指针组成的指针数组 T 0 m 1 凡是散列地址为 i 的结点 均插入到以 T i 为头指针的单链表中 T 中各分量的初值均应 为空指针 在拉链法中 装填因子 可以大于 1 但一般均取 1 2 拉链法的优点 与开放定址法相比 拉链法有如下几个优点 1 拉链法处理冲突简单 且无堆积现象 即非同义词决不会发生冲突 因此平均查找长度较短 2 由于拉链法中各链表上的结点空 间是动态申请的 故它更适合于造表前无法确定表长的情况 3 开放定址法为减少冲突 要求装填因子 较小 故当结点规模较大时会浪费很多空间 而拉链法中可取 1 且 结点较大时 拉链法中增加的指针域可忽略不计 因此节省空间 4 在用拉链法构造的散 列表中 删除结点的操作易于实现 只要简单地删去链表上相应的结点即可 而对开放地 址法构造的散列表 删除结点不能简单地将被删结点的空间置为空 否则将截断在它之后 填人散列表的同义词结点的查找路径 这是因为各种开放地址法中 空地址单元 即开放地 址 都是查找失败的条件 因此在用开放地址法处理冲突的散列表上执行删除操作 只能在 被删结点上做删除标记 而不能真正删除结点 3 拉链法的缺点 拉链法的缺点是 指针需要额外的空间 故当结点规模较小时 开放定址法较为节省空 间 而若将节省的指针空间用来扩大散列表的规模 可使装填因子变小 这又减少了开放 定址法中的冲突 从而提高平均查找速度 散列函数的构造方法 1 散列函数的选择有两条标准 简单和均匀 简单指散列函数的计算简单快速 均匀指对于关键字集合中的任一关键字 散列函数 能以等概率将其映射到表空间的任何一个位置上 也就是说 散列函数能将子集 K 随机均 匀地分布在表的地址集 0 1 m 1 上 以使冲突最小化 2 常用散列函数 为简单起见 假定关键字是定义在自然数集合上 其它关键字可以转换到自然数集合上 1 平方取中法 具体方法 先通过求关键字的平方值扩大相近数的差别 然后根据表长度取中间的几位 数作为散列函数值 又因为一个乘积的中间几位数和乘数的每一位都相关 所以由此产生 的散列地址较为均匀 2 除余法 该方法是最为简单常用的一种方法 它是以表长 m 来除关键字 取其余数作为散列地址 即 h key key m 该方法的关键是选取 m 选取的 m 应使得散列函数值尽可能与关键字 18 的各位相关 m 最好为素数 3 相乘取整法 该方法包括两个步骤 首先用关键字 key 乘上某个常数 A 0 A 1 并抽取出 key A 的 小数部分 然后用 m 乘以该小数后取整 4 随机数法 选择一个随机函数 取关键字的随机函数值为它的散列地址 即 h key random key 其 中 random 为伪随机函数 但要保证函数值是在 0 到 m 1 之间 5 数字分析法 设有 n 个 d 位数 每一位可能有 r 种不同的符号 这 r 种不同的符号在各位上出现的频 率不一定相同 可能在某些位上分布均匀些 每种符号出现的几率均等 在某些位上分布不 均匀 只有某几种符号经常出现 可根据散列表的大小 选取其中各种符号分布均匀的若 干位作为散列地址 6 基数转换法 将关键码值看成另一种进制的数再转换成原来进制的数 然后选其中几位作为散列地址 7 折叠法 有时关键码所含的位数很多 采用平方取中法计算太复杂 则可将关键码分割成位数相同 的几部分 最后一部分的位数可以不同 然后取这几部分的叠加和 舍去进位 作为散 列地址 这方法称为折叠法 8 ELFhash 字符串散列函数 ELFhash 函数在 UNIX 系统 V 版本 4 中的 可执行链接格式 Executable and Linking Format 即 ELF 中会用到 ELF 文件格式用于存储可执行文件与目标文件 ELFhash 函 数是对字符串的散列 它对于长字符串和短字符串都很有效 字符串中每个字符都有同样 的作用 它巧妙地对字符的 ASCII 编码值进行计算 ELFhash 函数对于能够比较均匀地把 字符串分布在散列表中 五 散列表上的运算 散列表上的运算有查找 插入和删除 其中主要是查找 这是因为散列表的目的主要 是用于快速查找 且插入和删除均要用到查找操作 1 散列表类型说明 define NIL 1 空结点标记依赖于关键字类型 本节假定关键字均为非负整数 define M 997 表长度依赖于应用 但一般应根据 确定 m 为一素数 typedef struct 散列表结点类型 KeyType key InfoType otherinfo 此类依赖于应用 NodeType typedef NodeType HashTable m 散列表类型 2 基于开放地址法的查找算法 散列表的查找过程和建表过程相似 假设给定的值为 K 根据建表时设定的散列函数 h 计算出散列地址 h K 若表中该地址单元为空 则查找失败 否则将该地址中的结点与 给定值 K 比较 若相等则查找成功 否则按建表时设定的处理冲突的方法找下一个地址 如此反复下去 直到某个地址单元为空 查找失败 或者关键字比较相等 查找成功 为止 3 基于开放地址法的插入及建表 建表时首先要将表中各结点的关键字清空 使其地址为开放的 然后调用插入算法将给 定的关键字序列依次插入表中 插入算法首先调用查找算法 若在表中找到待插入的关键 字或表已满 则插入失败 若在表中找到一个开放地址 则将待插入的结点插入其中 即 插入成功 4 删除 基于开放定址法的散列表不宜执行散列表的删除操作 若必须在散列表中删除结点 则 19 不能将被删结点的关键字置为 NIL 而应该将其置为特定的标记 DELETED 因此须对查找操 作做相应的修改 使之探查到此标记时继续探查下去 同时也要修改插人操作 使其探查 到 DELETED 标记时 将相应的表单元视为一个空单元 将新结点插入其中 这样做无疑增 加了时间开销 并且查找时间不再依赖于装填因子 因此 当必须对散列表做删除结点的 操作时 一般是用拉链法来解决冲突 5 性能分析 插入和删除的时间均取决于查找 故下面只分析查找操作的时间性能 虽然散列表在关键字和存储位置之间建立了对应关系 理想情况是无须关键字的比较就 可找到待查关键字 但是由于冲突的存在 散列表的查找过程仍是一个和关键字比较的过 程 不过散列表的平均查找长度比顺序查找 二分查找等完全依赖于关键字比较的查找要 小得多 1 查找成功的 ASL 散列表上的查找优于顺序查找和二分查找 2 查找不成功的 ASL 对于不成功的查找 顺序查找和二分查找所需进行的关键字比较次数仅取决于表长 而 散列查找所需进行的关键字比较次数和待查结点有关 因此 在等概率情况下 也可将散 列表在查找不成功时的平均查找长度 定义为查找不成功时对关键字需要执行的平均比较 次数 注意 由同一个散列函数 不同的解决冲突方法构造的散列表 其平均查找长度是不相同的 散列表的平均查找长度不是结点个数 n 的函数 而是装填因子 的函数 因此在设 计散列表时可选择 以控制散列表的平均查找 长度 的取值越小 产生冲突的机会就小 但 过小 空间的浪费就过多 只要 选 择合适 散列表上的平均查找长度就是一个常数 即散列表上查找的平均时间为 O 1 散列法与其他查找方法的区别 除散列法外 其他查找方法有共同特征为 均是建立在比较关键字的基础上 其中顺序查 找是对无序集合的查找 每次关键字的比较结果为 或 两种可能 其平均时间为 O n 其余的查找均是对有序集合的查找 每次关键字的比较有 三种可能 且每次 比较后均能缩小下次的查找范围 故查找速度更快 其平均时间为 O lgn 而散列法是根 据关键字直接求出地址的查找方法 其查找的期望时间为 O 1 20 实验 7 排序的应用 一 实验目的一 实验目的 1 掌握插入排序的应用 学习直接插入排序 有序表排序等 2 掌握交换排序的应用 如冒泡排序 快速排序等 3 学习选择排序的应用 如直接选择排序 堆排序等 4 学习归并排序的应用 如二路归并排序等 二 实验要求二 实验要求 1 熟练掌握插入排序的应用 能进行直接插入排序 有序表排序等 2 对交换排序达到熟练掌握的程度 会进行冒泡排序 快速排序 3 运用选择排序 进行直接选择排序 堆排序 4 综合运用排序方法 能解决基本排序 三 实验步骤三 实验步骤 1 直接插入排序 直接插入排序 straight insertion sort 的作法是 每次从无序表中取出第一个元素 把它插入到有序表的合适位置 使有序表仍然有 序 第一趟比较前两个数 然后把第二个数按大小插入到有序表中 第二趟把第三个数 据与前两个数从后向前扫描 把第三个数按大小插入到有序表中 依次进行下去 进行 了 n 1 趟扫描以后就完成了整个排序过程 直接插入排序属于稳定的排序 时间复杂性为o n 2 空间复杂度为 O 1 直接插入排序是由两层嵌套循环组成的 外层循环标识并决定待比较的数值 内层 循环为待比较数值确定其最终位置 直接插入排序是将待比较的数值与它的前一个数值 进行比较 所以外层循环是从第二个数值开始的 当前一数值比待比较数值大的情况下 继续循环比较 直到找到比待比较数值小的并将待比较数值置入其后一位置 结束该次 循环 值得注意的是 我们必需用一个存储空间来保存当前待比较的数值 因为当一趟比较 完成时 我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸 牌的过程 插入排序的基本方法是 每步将一个待排序的记录按其关键字的大小插到前面 已经排序的序列中的适当位置 直到全部记录插入完毕为止 序序列列 初始序列 i 1 46 58 15 45 90 18 10 62 i 2 46 58 15 45 90 18 10 62 i 3 15 46 58 45 90 18 10 62 i 4 15 45 46 58 90 18 10 62 i 5 15 45 46 58 90 18 10 62 i 6 15 18 45 46 58 90 10 62 21 i 7 10 15 18 45 46 58 90 62 i 8 10 15 18 45 46 58 62 90 C C 代码实现直接插入排序 for i 1 i 0 j a j a j 1 a j temp Java 代码实现直接插入排序 public class MainTest public static void main String args int a 46 58 15 45 90 18 10 62 int n a length int i j for i 0 i 0 j a j a j 1 a j temp for i 0 i a i 1 Then 若是递减 改为 a i a i 1 temp a i 22 a i a i 1 a i 1 temp bSwap True End If Next If bSwap False Then Exit For End If Next For Each c In a Debug Print c Next End Sub 3 归归并并排排序序 归并排序是建立在归并操作上的一种有效的 排序算法 该算法是采用 分治法 Divide and Conquer 的一个非常典型的应用 将已有序的子序列合并 得到完全有序的序列 即先使每个子序列有序 再使子序 列段间有序 若将两个有序表合并成一个有序表 称为2 路归并 归并操作 归并操作 merge 也叫归并算法 指的是将两个已经排序的序列合并成一个序列的 操作 如 设有数列 6 202 100 301 38 8 1 初始状态 6 202 100 301 38 8 1 比较次数 i 1 6 202 100 301 8 38 1 3 i 2 6 100 202 301 1 8 38 4 i 3 1 6 8 38 100 202 301 4 总计 11 次 算法描述 归并操作的工作原理如下 申请空间 使其大小为两个已经排序序列之和 该空间用来存放合并后的序列 设定两个指针 最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素 选择相对小的元素放入到合并空间 并移动指针到下 一位置 重复步骤 3 直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 示例代码 示例代码为 C 语言 输入参数中 需要排序的 数组为 array 起始索引为 first 终止索引为 last 调用完成后 array 中从 first 到 last 处于升序排列 void MergeSort int array int first int last int mid 0 if first last mid first last 2 MergeSort array first mid MergeSort array mid 1 last Merge array first mid last 23 以下示例代码实现了归并操作 array 是元素序列 其中从索引 p 开始到 q 位 置 按照升序排列 同时 从 q 1 到 r 也已经按照升序排列 merge 函数将把这两 个已经排序好的子序列合并成一个排序序列 结果放到array 中 0 p q r subarray array p q and array q 1 r are already sorted the merge function merges the two sub arrays into one sorted array void Merge int array int p int q int r int i k int begin1 end1 begin2 end2 int temp int malloc r p 1 sizeof int begin1 p end1 q begin2 q 1 end2 r k 0 while begin1 end1 begin1 else temp k array begin2 begin2 k while begin1 end1 temp k array begin1 while begin2 end2 temp k array begin2 for i 0 i r p 1 i array p i temp i free temp 24 实验 8 典型算法的应用 一 实验目的一 实验目的 1 掌握分治算法的应用 学习静态二分查找 顺序统计和二叉排序树等 2 掌握贪心算法的应用 如会议日程安排 0 1 背包问题等 3 学习动态规划算法的应用 如最长公共子序列 关键路径等 4 学习回溯与分支限界算法的应用 如迷宫问题 旅行售货员问题等 二 实验要求二 实验要求 1 基本掌握分治算法的应用 熟练进行静态二分查找 顺序统计和二叉排序树等 2 对贪心算法达到基本掌握的程度 会进行会议日程安排 3 运用动态规划算法 进行最长公共子序列和关键路径的查找 4 综合运用算法知识 能解决迷宫问题等等 三 实验步骤三 实验步骤 1 分治算法 静态二分查找 基基本本思思想想 当我们求解某些问题时 由于这些问题要处理的数据相当多 或求解过程相当复杂 使得直接求解法在时间上相当长 或者根本无法直接求出 对于这类问题 我们往往先 把它分解成几个子问题 找到求出这几个子问题的解法后 再找到合适的方法 把它们 组合成求整个问题的解法 如果这些子问题还较大 难以解决 可以再把它们分成几个 更小的子问题 以此类推 直至可以直接求出解为止 这就是分治策略的基本思想 二二分分