【声明】
欢迎转载,但请保留文章原始出处→_→
生命壹号:http://www.VEVb.com/smyhvae/
文章来源:http://www.VEVb.com/smyhvae/p/4758808.html
联系方式:smyhvae@163.com
【正文】
本节内容:
一、线性结构:
如果一个数据元素序列满足:
(1)除第一个和最后一个数据元素外,每个数据元素只有一个前驱数据元素和一个后继数据元素;
(2)第一个数据元素没有前驱数据元素;
(3)最后一个数据元素没有后继数据元素。
则称这样的数据结构为线性结构。
二、线性表抽象数据类型:
1、线性表抽象数据类型的概念:
线性表抽象数据类型主要包括两个方面:既数据集合和该数据集合上的操作集合。
数据集合:
可以表示为a0,a1,a2,...an-1,每个数据元素的数据类型可以是任意的类型。
操作集合包括如下:
1.求元素个数
2.插入
3.删除
4.查找
5.判断是否为空
2、设计线性表抽象数据类型的Java接口:
代码如下:
//线性表接口public interface List { //获得线性表长度 public int size(); //判断线性表是否为空 public boolean isEmpty(); //插入元素 public void insert(int index,Object obj) throws Exception; //删除元素 public void delete(int index) throws Exception; //获取指定位置的元素 public Object get(int index) throws Exception;}
然后我们让子类去实现这个接口就行了。
三、顺序表:(在物理存储结构上连续,大小固定)
1、顺序表的概念:
计算机有两种基本的存储结构(物理存储结构):顺序结构、离散结构。使用顺序结构实现的线性表称为顺序表。如下图所示:
Java内存中,栈内存和堆内存占了很大一部分空间:栈内存的存储是顺序结构,堆内存的存储是离散结构。
2、设计顺序表类:
我们在上面第二段的List接口基础之上,设计一个顺序表:
(1)List.java:(线性表,和上面的第二段中代码一样)
//线性表接口public interface List { //获得线性表长度 public int size(); //判断线性表是否为空 public boolean isEmpty(); //插入元素 public void insert(int index, Object obj) throws Exception; //删除元素 public void delete(int index) throws Exception; //获取指定位置的元素 public Object get(int index) throws Exception;}
(2)SequenceList.java:(核心代码)
1 public class SequenceList implements List { 2 3 //默认的顺序表的最大长度 4 final int defaultSize = 10; 5 //最大长度 6 int maxSize; 7 //当前长度 8 int size; 9 //对象数组10 Object[] listArray;11 12 13 public SequenceList() {14 init(defaultSize);15 }16 17 public SequenceList(int size) {18 init(size);19 }20 21 //顺序表的初始化方法22 PRivate void init(int size) {23 maxSize = size;24 this.size = 0;25 listArray = new Object[size];26 }27 28 @Override29 public void delete(int index) throws Exception {30 // TODO Auto-generated method stub31 if (isEmpty()) {32 throw new Exception("顺序表为空,无法删除!");33 }34 if (index < 0 || index > size - 1) {35 throw new Exception("参数错误!");36 }37 //移动元素38 for (int j = index; j < size - 1; j++) {39 listArray[j] = listArray[j + 1];40 }41 size--;42 }43 44 @Override45 public Object get(int index) throws Exception {46 // TODO Auto-generated method stub47 if (index < 0 || index >= size) {48 throw new Exception("参数错误!");49 }50 return listArray[index];51 }52 53 @Override54 public void insert(int index, Object obj) throws Exception {55 // TODO Auto-generated method stub56 //如果当前线性表已满,那就不允许插入数据57 if (size == maxSize) {58 throw new Exception("顺序表已满,无法插入!");59 }60 //插入位置编号是否合法61 if (index < 0 || index > size) {62 throw new Exception("参数错误!");63 }64 //移动元素65 for (int j = size - 1; j >= index; j--) {66 listArray[j + 1] = listArray[j];67 }68 69 listArray[index] = obj; //不管当前线性表的size是否为零,这句话都能正常执行,即都能正常插入70 size++;71 72 }73 74 @Override75 public boolean isEmpty() {76 // TODO Auto-generated method stub77 return size == 0;78 }79 80 @Override81 public int size() {82 // TODO Auto-generated method stub83 return size;84 }85 }
我们来看一下第54行的插入操作insert()方法:如果需要在index位置插入一个数据,那么index后面的元素就要整体往后移动一位。这里面需要特别注意的是:
插入操作:移动元素时,要从后往前操作,不能从前往后操作,不然元素会被覆盖的。
删除元素:移动元素时,要从前往后操作。
(3)测试类:
public class Test { public static void main(String[] args) { SequenceList list = new SequenceList(20); try { list.insert(0, 100); list.insert(0, 50); list.insert(1, 20); for (int i = 0; i < list.size; i++) { System.out.println("第" + i + "个数为" + list.get(i)); } } catch (Exception e) { e.printStackTrace(); } }}
我们要注意插入的规则是什么,不然会觉得这个顺序表打印输出的顺序很奇怪。
运行效果:
3、顺序表效率分析:
4、顺序表的优缺点:
5、顺序表的应用:
设计一个顺序表,可以保存100个学生的资料,保存以下三个学生的资料,并打印输出。
代码实现:
(1)List.java:
和上面的代码保持不变
(2)SequenceList.java:
和上面的代码保持不变
(3)Students.java:学生类
//学生类public class Students { private String id;// 学号 private String name;// 姓名 private String gender;// 性别 private int age;// 年龄 public Students() { } public Students(String sid, String name, String gender, int age) { this.id = sid; this.name = name; this.gender = gender; this.age = age; } public String getId() { return id; } public void setId(String id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getGender() { return gender; } public void setGender(String gender) { this.gender = gender; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String toString() { return "学号:" + this.getId() + " 姓名:" + this.getName() + " 性别:" + this.getGender() + " 年龄:" + this.getAge(); }}
(4)Test.java:
1 public class Test { 2 3 /** 4 * @param args 5 */ 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 SequenceList list = new SequenceList(100); 9 10 try {11 list.insert(list.size, new Students("S0001", "张三", "男", 18)); //第一个参数list.size代表的是:我每次都是在顺序表的最后一个位置(当前线性表的长度的位置)进行插入操作。这一行里,size是等于012 list.insert(list.size, new Students("S0002", "李四", "男", 19));13 list.insert(list.size, new Students("S0003", "王五", "女", 21));14 15 for (int i = 0; i < list.size; i++) {16 System.out.println(list.get(i));17 }18 19 } catch (Exception ex) {20 ex.printStackTrace();21 }22 }23 24 }
注意第11行的注释:第一个参数list.size代表的是:我每次都是在顺序表的最后一个位置(当前线性表的长度的位置)进行插入操作;这样的话,遍历时才是按照张三、李四、王五的顺序进行输出的。
运行效果:
新闻热点
疑难解答