数据结构线性表的实现和应用.docx

完美 WORD 完美 WORD 格式 专业整理知识分享 专业整理 知识分享 实 验 报 告 课程名称 数据结构 实验项目 线性表的实现及应用 实验仪器 PC 机一台 学 院 专 业 班级/学号姓名 实验日期成 绩 指导教师 京信息科技大学 信息管学院 （数据结构课程上机）实验报告 实验名称线性表的实现及应用实验地点实验时间1.实验目的：（1）解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会用顺序表解决实际应用问题。（2）熟练掌握单链表的使用；解用链表实现线性表的特点；解链表的多种形式；学会用单链表解决实际应用问题。2.实验要求：（1）学时为 实验名称 线性表的实现及应用 实验地点 实验时间 1.实验目的： （1） 解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学 会用顺序表解决实际应用问题。 （2） 熟练掌握单链表的使用；解用链表实现线性表的特点；解链表 的多种形式；学会用单链表解决实际应用问题。 2.实验要求： （1） 学时为 8 学时； （2） 能在机器上正确、调试运程序； （3） 本实验需提交实验报告； （4） 实验报告文件命名方法：数据结构实验_信管 16xx_学号_姓名.doc。 3.实验内容和步骤： 第一部分 顺序表的实现与应用 （1）基于顺序表实现线性表的以下基本操作： public interface LListT { //线性表接口，泛型参数 T 表示数据元素的数据类型 boolean isEmpty(); //判断线性表是否空int size(); //返回线性表长 T get(int i); //返回第 i（i≥0）个元素void set(int i, T x); //设置第 i 个元素值为 x void insert(int i, T x); //插入 x 作为第 i 个元素void insert(T x); //在线性表最后插入 x 元素 T remove(int i); //删除第 i 个元素并返回被删除对 象 int search(T key); //查找，返回首次出现的关键字为 key 的元素的位序 void removeAll(); //删除线性表所有元素 public String toString();//返回顺序表所有元素的描述字符，形式为“（，） } 要求：实现后应编写代码段对每个基本操作做测试。 顺序表的简单应用 运用基本操作编写算法删除第 i 个开始的 k 个元素。 编写高效算法删除第 i 个开始的 k 个元素。 将两个顺序表合并为一个顺序表（表中元素有序）； 两个元素按值递增有序排的顺序表 A 和 B，且同一表中的元素值各相同。试构造一个顺序表 C，其元素为A 和 B 中元素的交集，且表C 中的元素也按值递增有序排； 用顺序表解决约瑟夫环问题：已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆桌周围。从编号为k 的人开始报数，数到m 的那个人出；他的下一个人又从 1 开始报数，数到m 的那个人又出；依此规重复下去，直到 圆桌周围的人全部出。要求：输出出次序。 第二部分 单链表的实现与应用 基于单链表实现线性表的以下基本操作（需要建接口，直接建带头结点的单链表类）： ADT ListT { boolean isEmpty(); //判断线性表是否空int size(); //返回线性表长 T get(int i); //返回第 i（i≥0）个元 素 void set(int i, T x); //设置第 i 个元素值为 x NodeT insert(int i, T x); //插入 x 作为第 i 个元素NodeT insert(T x); //在线性表最后插入 x 元素 T remove(int i); //删除第 i 个元素并返回被删除 对象 void removeAll(); //删除线性表所有元素 NodeT search(T key); //查找，返回首次出现的关键字为key 元素 public String toString(); //返回顺序表所有元素的描述字符 ，形式为“ （，） } 要求：实现后应编写代码段对每个基本操作做测试。 实现单链表的子类排序单链表，覆盖单链表如下方法： void set(int i, T x); //设置第 i 个元素值为 x NodeT insert(int i, T x); //插入 x 作为第 i 个元素 NodeT insert(T x); //在线性表最后插入 x 元素 NodeT search(T key); //查找，返回首次出现的关键字为 key 元素 基于排序单链表实现线性表的以下综合应用： 删除第 i 个开始的 k 个元素。 删除递增有序单链表中所有值大于