实验一——链式结构实现线性表

北京邮电大学信息与通信工程学院 第 1 页 数据结构实验报告 实验名称 实验一 链式结构实现线性表 学生姓名 班 级 班内序号 学 号 日 期 1 实验要求 实验目的 通过选择下面四个题目之一进行实现 掌握如下内容 熟悉 C 语言的基本编程方法 掌握集成编译环境的调试方法 学习指针 模板类 异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容 根据线性表的抽象数据类型的定义 选择下面任一种链式结构实现线性表 并完成线性表 的基本功能 线性表存储结构 五选一 1 带头结点的单链表 2 不带头结点的单链表 3 循环链表 4 双链表 5 静态链表 线性表的基本功能 构造 使用头插法 尾插法两种方法 1 插入 要求建立的链表按照关键字从小到大有序 2 删除 3 查找 4 获取链表长度 5 销毁 北京邮电大学信息与通信工程学院 第 2 页 6 其他 可自行定义 编写测试 main 函数测试线性表的正确性 2 程序分析 2 1 存储结构 存储结构 顺序表 2 2 关键算法分析 头插法示意图 算法步骤 堆中建立新结点 S next 指向 front next front next 指向 s Node s new Node s data a i s next front next front next s 时间复杂度 O n 尾插法 算法步骤 堆中建立新结点 Node s new Node 将新结点加入到链表中 r next front next 修改尾指针 r s 按值查找结点示意图 北京邮电大学信息与通信工程学院 第 3 页 定位计数和定位指针 1 int i 1 Node p p front next 比较 P 指向的元素是否与检索值相同 2 if p while p if p data n cout 元素序号 i next i else throw 空链表 时间复杂度 O n 插入操作 算法步骤 堆中建立新结点 Node s new Node 将新结点插入到要插入位置后一节点 p 的后面 将后一结点数 据写入 s P 指向 s 在 p 中写入新的值 s data p data s next p next p next s p data x 时间复杂度 O 1 北京邮电大学信息与通信工程学院 第 4 页 删除结点示意图 x p q 删除结点示意图 算法步骤 从第一个结点开始 查找第 i 1 个元素 设为 p 指向该结点 设 q 指向第 i 个元素 q p next 摘链 即将 q 元素从链表中摘除 p next q next 保存 q 元素的数据 x q data 释放 q 元素 delete q 说明 如果算法比较复杂 可以将多句代码合成一个步骤进行说明 比如也 可以这样写 从第一个结点开始 查找第 i 1 个元素 设为 p 指向该结点 设 q 指向第 i 个元素 q p next 摘链 即将 q 元素从链表中摘除 p next q next x q data delete q 时间复杂度 O n 2 3 其他 程序代码 include using namespace std template struct Node T data struct Node next template class LinkList 北京邮电大学信息与通信工程学院 第 5 页 public LinkList front new Node front next NULL LinkList T a int n LinkList Node Get int i Node Locate int n Node s void Insert int i T x T Delete int i int GetLength void Print private Node front template LinkList LinkList T a int n 头插法 front new Node front next NULL for int i n 1 i 0 i Node s new Node s data a i s next front next front next s template LinkList LinkList T a int n 尾插法 front new Node Node r front for inti 0 i n i Node s new Node s data a i r next s r s r next NULL 北京邮电大学信息与通信工程学院 第 6 页 template LinkList LinkList 析构函数 Node p front while p front p p p next delete front template Node LinkList Get int i Node p front next int j 1 while p j return p template Node LinkList Locate int n Node s int i 1 Node p p front next if p while p if p data n cout 元素序号 i next i else throw 空链表 北京邮电大学信息与通信工程学院 第 7 页 while p return p t 0 if p next Locate n p next else return NULL template void LinkList Insert int i T x Node p Get i if p Node s new Node s data p data s next p next p next s p data x else throw 输入有误 template T LinkList Delete int i Node p front if i 1 p Get i 1 Node q p next p next q next T x q data delete q return x template int LinkList GetLength 北京邮电大学信息与通信工程学院 第 8 页 int i 0 Node p front next if p i p p next return i template void LinkList Print Node p front next if front next while p cout data next cout endl else throw 该表没有元素 void main int x y int a 6 1 2 3 4 5 6 LinkList L a 6 L Print cout x y L Insert x y L Print cout x L Delete x L Print cout x cout data endl cout x L Locate x NULL cout L GetLength 3 程序运行结果 测试主函数流程 流程图如图所示 开始 打印序列 是否退出 结束 是 输入插入的位置和数值 打印修改后序列 输入删除的位置 打印修改后序列 输入查找的关键值 打印查找关键值的位置 北京邮电大学信息与通信工程学院 第 10 页 1 测试条件 初始序列为 1 2 3 4 5 6 插入位置 1 数值 6 是删除元素序号 3 查找元素序号 2 查找元素 6 2 测试结论 初始序列为 1 2 3 4 5 6 插入位置 1 数值 6 后序列 6 1 2 3 4 5 6 是删除元素序号 3 后序列 6 1 3 4 5 6 查找元素序号 2 后查找到序号 2 所对应元素为 1 查找元素 6