数据结构实验一线性表的顺序存储结构

实验一线性表的顺序存储结构 一.实验的目的要求: 1.掌握顺序存储结构的特点。 2.掌握顺序存储结构的常见算法。 二.实验内容: 1.建立一个接口,定义一些常用的基本方法; 2.用类实现该接口的基本方法: a.依次插入数据元素,建立顺序表; b.按指定位置查找在该顺序表中查找某一元素; c.按指定位置删除该顺序表中的某一元素; d.实现该顺序表的遍历; 3.定义客户类来调用接口中的方法; 三.实验程序 1.实验:线性表的顺序存储结构可以通过插入、删除、替换、查找等方法实现随机存取。其优点在于:数据之间逻辑相邻,物理相邻,可随机存储任一数据元素,存储空间较紧凑。但是其缺点在于:每次插入或者删除数据元素都需要移动大量数据,且顺序存储结构需要事先分配好内存空间,有可能不需要那么多内存空间而造成内存空间损失,也有可能内存空间分配不够,造成数据缺失。 2.数据结构:利用线性表的顺序存储结构可以实现数据之间逻辑相邻,物理相邻,可随机存储任一数据,存储空间较紧凑。 3.算法设计: a.插入元素时,先判断表是否已满,若未满则最后一个元素往后一个位置,其他元素也依次向后移动一个位置,然后找到那个空位赋值为所要插入的元素,最后表的长度加一。 b.删除元素时,先找到所要删除元素的位置,然后后一位的元素往前覆盖,后面的元素也依次往前移动一位,最后表的长度减一。 c.替换元素时,先找到需要替换的元素的位置,然后将所要替换的元素赋值给该元素,表的长度不变。 d.查找是否包含元素时,将该元素从表头开始依次与表中的元素做对比。 4.程序运行实例: public class ClientList { public static void main(String[] args) { testList(); } public static void testList() { ListInterface runnerList=new Alist(); runnerList.add("16"); runnerList.add("4"); runnerList.add("33"); runnerList.add("27"); runnerList.replace(3,5); //runnerList.clear(); //runnerList.contains(5); runnerList.display(); } } 5.实习:线性表是一个抽象数据类型(ADT),由同种类型的数据有序排列构成,客户只能通过ADT线性表上定义的操作来修改或者访问数据元素。线性表上的方法对客户是不可见的,因为ADT线性表将数据和操作封装起来,客户可以使用它,但不需要知道实现的细节,即不需要知道ADT线性表做了什么。通过线性表的顺序存储可以实现对数据的随机存取,但是每次插入或者删除数据元素都需要移动大量数据,且顺序存储结构需要事先分配好内存空间,有可能不需要那么多内存空间而造成内存空间损失,也有可能内存空间分配不够,造成数据缺失。 6.源程序: a.线性表接口 public interface ListInterface { public boolean add(T newEntry); //往线性表的末尾插入新元素 public boolean add(int newPosition,T newEntry); //将newEntry插入到线性表中位置newPosition public T remove(int givenPosition); //从线性表中删除指定位置为givenPosition的元素 public void clear(); //删除表中所有元素 public boolean replace(int givenPosition,T newEntry); //以newEntry替换位置为givenPosition的元素 public T getEntry(int givenPosition); //检索线性表中位置为givenPosition的元素 public boolean contains(T anEntry); //确定线性表是否含有一个给定的元素anEntry public int getLength(); //获得线性表中当前包含的元素个数 public boolean isEmpty(); //确定线性表是否为空 public boolean isFull(); //确定线性表是否为满 public void display(); //按照元素在线性表中的顺序显示线性表中的所有元素,每行一个元素 } b.实现类 public class Alist implements ListInterface{ private T[] entry; private int length; private static final int MAX_SIZE=50; public Alist() { this(MAX_SIZE); } public Alist(int maxSize) { length=0; entry=(T[])new Object[maxSize]; } public boolean add(T newEntry) { boolean isSuccessful=true; if(!isFull()) { entry[length]=newEntry; length++; } else isSuccessful=false; return isSuccessful; } public boolean add(int newPosition, T newEntry) { boolean isSuccessful=true; if(!isFull()&&(newPosition>=1)&&(newPosition<=length+1)) { makeRoom(newPosition); entry[newPosition-1]=newEntry; length++; } else isSuccessful=false; return isSuccessful; } private void makeRoom(int newPosition) { f or(int index=length;index>=newPosition;index--) entry[index]=entry[index-1]; } public T remove(int givenPosition) { T result=null; if((givenPosition>=1)&&(givenPosition<=length)) { assert !isEmpty(); result=entry[givenPosition-1]; if(givenPosition=1)&&(givenPosition0;index--) remove(index); } public boolean replace(int givenPosition,T newEntry) { boolean isSuccessful=true; if((givenPosition>=1)&&(givenPosition<=length)) entry[givenPosition-1]=newEntry; else isSuccessful=false; return isSuccessful; } public T getEntry(int givenPosition) { T result=null; if((givenPosition>=1)&&(givenPosition<=length)) { assert !isEmpty(); result=entry[givenPosition-1]; } return result; } public boolean contains(T anEntry) { boolean found=false; for(int index=0;!found&&(index