数据结构(Java版) 线性表的实现与应用完整版.doc

实 验 报 告 课程名称 数据结构 实验项目 线性表的实现及应用 实验仪器 PC机一台 学 院_____ 专 业 班级/学号 姓名 实验日期 成 绩 指导教师 北京信息科技大学 信息管理学院 （数据结构课程上机）实验报告 专业: 班级: 学号: 姓名: 成绩: 实验名称 线性表的实现及应用 实验地点 实验时间 实验目的： 理解用顺序表实现线性表的特点；熟练掌握顺序表的基本操作；学会利用顺序表解决实际应用问题。 熟练掌握单链表的使用；理解用链表实现线性表的特点；了解链表的多种形式；学会利用单链表解决实际应用问题。 实验要求： 学时为8学时； 能在机器上正确、调试运行程序； 本实验需提交实验报告； 实验报告文件命名方法：数据结构实验_信管16xx_学号_姓名.doc。 实验内容和步骤： 第一部分 顺序表的实现与应用 （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();//返回顺序表所有元素的描述字符串，形式为“（，）” } 要求：实现后应编写代码段对每个基本操作做测试。 （2）顺序表的简单应用 运用基本操作编写算法删除第i个开始的k个元素。 编写高效算法删除第i个开始的k个元素。 将两个顺序表合并为一个顺序表（表中元素有序）； 若两个元素按值递增有序排列的顺序表A和B，且同一表中的元素值各不相同。试构造一个顺序表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列； （3）利用顺序表解决约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求：输出出列次序。 第二部分 单链表的实现与应用 （4）基于单链表实现线性表的以下基本操作（不需要建立接口，直接建立带头结点的单链表类）： 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); //查找，返回首次出现