数据结构--线性表之顺序表实现 小鱼儿 2021-08-13 20:24 503阅读 0赞 ### 概述 ### 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。 ### 基本概念 ### * 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型； * 数据元素之间具有一种线性的或“一对一”的逻辑关系。 * 第一个数据元素没有前驱，这个数据元素被称为开始节点； * 最后一个数据元素没有后继，这个数据元素被称为终端节点； * 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。 ### 线性表的抽象数据类型 ### LinearList=(A0, A1, …, An-1) package pers.zhang.linearList; /** * @author zhang * @date 2020/1/13 - 16:28 * 线性表接口，泛型参数T表示数据元素的数据类型 */ public interface LinearList<T> { //判断线性表是否为空 boolean isEmpty(); //返回线性表长度 int length(); //返回第i(i>=0)个元素 T get(int i); //设置第i个元素值为x void set(int i, T x); //插入x作为第i个元素 void insert(int i, T x); //在线性表最后插入x元素 void append(T x); //删除第i个元素并返回被删除的对象 T remove(int i); //删除线性表所有元素 void removeAll(); //查找，返回首次出现的关键字为key的元素 T search(T key); } ### 线性表的顺序表示和实现 ### 线性表的顺序存储结构 ![在这里插入图片描述][20200113164255384.png] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70] 实现 package pers.zhang.linearList; import java.util.Arrays; /** * @author zhang * @date 2020/1/13 - 16:45 * * 顺序表，线性表的顺序表示 */ public class SeqList<T> implements LinearList<T> { //对象数组 private Object[] element; //顺序表长度 private int len; //构造方法，创建容量为size的顺序表 public SeqList(int size){ //若size<0，抛出负数组长度异常NegativeArraySizeException this.element = new Object[size]; this.len = 0; } //默认构造方法，创建一个容量为64的顺序表 public SeqList(){ this(64); } //顺序表拷贝 //浅拷贝构造 // public SeqList(SeqList<T> list){ // this.len = list.len; // this.element = list.element;//数组为引用赋值，两个变量共享一个数组，错误！ // } //深拷贝构造 public SeqList(SeqList<T> list){ if(list == null)//若list为空，抛出异常 throw new NullPointerException(); this.len = list.len; this.element = new Object[list.element.length];//申请一个数组，大小为传入list的数组大小 for(int i = 0; i < list.len; i++)//复制数组元素，O(n) this.element[i] = list.element[i]; //this.element[i] = new T(list.element[i]); 语法错误，因为Java没有提供默认拷贝构造方法 //this.element[i] = new Object(list.element[i]); 语法错，因为Object没有提供拷贝构造方法，且构造方法不能继承 } //深拷贝构造，参数数组指定顺序表初值 public SeqList(T[] element){ this.len = element.length; this.element = new Object[element.length];//申请一个数组，大小为数组长度 for(int i = 0; i < element.length; i++) this.element[i] = element[i]; } //判断顺序表是否为空，若空返回true @Override public boolean isEmpty() { return this.len == 0; } //返回顺序表的长度 @Override public int length() { return this.len; } //返回第i（i>=0）个元素。若i<0或大于表长则返回null @Override public T get(int i) { if(i >= 0 && i < this.len) return (T)this.element[i];//需要强转为T类型，否则编译出错 return null; } //设置第i（i>=0）个元素的值为x。若i<0或大于表长则抛出序号越界异常；若x==null，不操作 @Override public void set(int i, T x) { if(x == null)//不能设置空对象 return; if(i >= 0 && i < this.len) this.element[i] = x; else throw new IndexOutOfBoundsException(i + "");//抛出越界异常 } //返回顺序表所有元素的描述字符串，形式为“（，）”，覆盖Object类的toString()方法 @Override public String toString() { String str = "("; if(this.len > 0) str += this.element[0].toString(); for(int i = 1; i < this.len; i++) str += ", " + this.element[i].toString(); return str +") ";//空表返回（） } //顺序表的插入操作 //插入第i（i>=0）个元素值为x。若x==null，不插入 //若i<0，插入 x作为第0个元素；若i大于表长，插入x作为最后一个元素。 @Override public void insert(int i, T x) { if(x == null) return; if(this.len == element.length){ //若数组已满，则先扩容 Object[] temp = this.element;//temp引用element数组 this.element = new Object[temp.length * 2];//重新申请一个容量*2的数组 for(int j = 0; i < temp.length; j++)//复制数组元素 this.element[j] = temp[j]; } //下标容错 if(i < 0) i = 0; if(i > this.len) i = this.len; //元素后移 for(int j = this.len - 1; j >= i; j--) this.element[j + 1] = this.element[j]; this.element[i] = x; this.len++; } //在顺序表尾部追加数据 @Override public void append(T x) { this.insert(this.len, x); } //顺序表的删除操作 //删除第i(i>=0)个元素，返回被删除的对象。若i<0或i大于表长，不删除，返回null @Override public T remove(int i) { if(this.len == 0 || i < 0 || i >= this.len) return null; //throw new IndexOutOfBoundsException(i + "");抛出越界异常 T old = (T) this.element[i]; for(int j = i; j < this.len - 1; j++)//元素前移，平均移动len/2 this.element[j] = this.element[j + 1]; this.element[this.len - 1] = null;//最后一个设为null this.len--; return old; } //删除所有 @Override public void removeAll() { this.len = 0; } //顺序表比较equals方法 //比较两个顺序表是否相等 @Override public boolean equals(Object obj) { if(this == obj)//同一对象返回true return true; if(obj instanceof SeqList){ //子类对象 SeqList<T> list = (SeqList<T>) obj; if(this.length() == list.length()){ //长度相等 for(int i = 0; i < this.length(); i++)//比较每个元素 if(!(this.get(i).equals(list.get(i)))) return false; return true; } } return false; } //顺序查找关键字为key元素，返回首次出现的元素，若查找不成功返回-1 //key可以只包含关键字数据项，由T类的equals()方法提供比较对象相等的依据 public int indexOf(T key){ if (key != null) for (int i = 0; i < this.len; i++) if (this.element[i].equals(key))//对象采用equals()方法比较是否相等 return i; return -1;//空表、key为空对象或未找到时 } //查找，返回首次出现的关键字为key元素 @Override public T search(T key) { int find = this.indexOf(key); return find == -1 ? null : (T)this.element[find]; } //判断线性表是否包含关键字为key元素 public boolean contain(T key){ return this.indexOf(key) >= 0;//顺序查找结果大于0，则存在该元素 } //删除首次出现的关键字为key元素 public void remove(T key){ this.remove(this.indexOf(key)); } //返回元素key最后出现位置，若未找到返回-1 public int lastIndexOf(T key){ if(key != null){ for(int i = 0; i < this.len - 1; i++) if(this.element[i].equals(key)) return i; } return -1; } //删除所有关键字为key元素 public void removeAll(T key){ if (key != null) { int i = 0; while (i < this.len) if (this.element[i].equals(key)) this.remove(i);//删除元素，this.len减1，i不变 else i++; } } //将首次出现的元素x替换为y，O(n) public void replace(T x, T y){ if (x != null && y != null) { int i = this.indexOf(x);//查找x首次出现位置 if (i != -1) this.element[i] = y; } } //将所有元素x替换为y public void replaceAll(T x, T y){ if (x != null && y != null) for (int i= 0; i < this.len; i++) if (x.equals(this.element[i])) this.element[i] = y; } //获取迭代器 public java.util.Iterator<T> iterator(){ return new SeqIterator(); } //私有内部类，实现迭代器接口 private class SeqIterator implements java.util.Iterator<T>{ int index = -1;//当前元素序号 int succ = 0;//后继元素序号 //若有后继元素，返回true @Override public boolean hasNext() { return this.succ < SeqList.this.len;//SeqList.this.len是外部类当前实例的成员变量 } //返回后继元素，若没有后继元素，返回null @Override public T next() { T value = SeqList.this.get(this.succ);//调用外部类SeqList当前实例的成员方法 if(value != null){ this.index = this.succ++; return value; } throw new java.util.NoSuchElementException();//抛出无此元素异常 } //删除迭代器对象表示的集合当前元素 @Override public void remove() { if(this.index >= 0 && this.index < SeqList.this.len){ SeqList.this.remove(this.index);//调用外部类当前实例的成员方法 SeqList.this.len--;//删除第index个元素，长度SeqList.this.len-1 if(this.succ > 0)//(this.index < this.succ) this.succ--; this.index = -1;//设置不能连续删除 }else{ throw new java.lang.IllegalStateException();//抛出无效状态异常 } } } } 测试： package pers.zhang.linearList; /** * @author zhang * @date 2020/1/13 - 18:13 */ public class SeqList_ex { public static Integer[] random(int n) //返回产生n个随机数的数组 { Integer[] elements = new Integer[n]; for (int i=0; i<n; i++) elements[i] = new Integer((int)(Math.random()*100)); //产生随机数 return elements; } public static void main(String args[]) { //顺序表 /* SeqList<String> lista = new SeqList<String>(4); //执行默认构造方法 for (int i=5; i>=0; i--) lista.insert(i, new String((char)('A'+i)+"")); //扩容 System.out.println("lista: "+lista.toString()); SeqList<String> listb = new SeqList<String>(lista);//执行拷贝构造方法 System.out.println("listb: "+listb.toString()); lista.set(3, new String((char)(lista.get(3).charAt(0)+32)+"")); lista.remove(0); lista.remove(3); lista.remove(10); //序号越界，没删除 System.out.println("lista: "+lista.toString()); System.out.println("listb: "+listb.toString()); //由于拷贝构造方法实现为数组深拷贝，对象浅拷贝，且因Integer是常量对象，new 引用另一个对象， //上述语句结果只能说明两个顺序表对象分别有各自的数组，各数组元素可引用不同对象， //但不能说明引用同一个对象导致的数据修改错误 */ //深拷贝与比较相等 SeqList<Integer> list1 = new SeqList<Integer>(); //空表 System.out.println("list1: "+list1.toString()); SeqList<Integer> list2 = new SeqList<Integer>(); //空表 System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); list1 = new SeqList<Integer>(random(5)); System.out.println("list1: "+list1.toString()); list2 = new SeqList<Integer>(list1); //拷贝构造方法 System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); System.out.println("list1: "+list1.toString()); list2.set(0, new Integer(list1.get(0).intValue()+100)); list2.remove(list2.length()-1); //删除最后一个元素 list2.remove(100); //序号越界，没删除 System.out.println("list2: "+list2.toString()); System.out.println("list1.equals(list2)? "+list1.equals(list2)); } } 结果： 程序运行结果如下： //（1） 浅拷贝 lista: (A, F, B, E, C, D) listb: (A, F, B, E, C, D) lista: (F, B, e, D) Exception in thread "main" java.lang.NullPointerException at SeqList.toString(SeqList.java:55) at SeqList_ex.main(SeqList_ex.java:30) //（2） 深拷贝，不能说明深拷贝的正确性，因String、Integer是最终变量 lista: (A, F, B, E, C, D) listb: (A, F, B, E, C, D) lista: (F, B, e, D) listb: (A, F, B, E, C, D) //深拷贝与比较相等 list1: () list2: () list1.equals(list2)? true list1: (16, 14, 81, 74, 68) list2: (16, 14, 81, 74, 68) list1.equals(list2)? true list1: (16, 14, 81, 74, 68) list2: (116, 14, 81, 74) list1.equals(list2)? false */ /* 泛型类问题讨论: 程序调试情况如下： SinglyLinkedList<Object> list3 = new SinglyLinkedList<Object>(); // SortedSinglyLinkedList<Object> list4 = new SortedSinglyLinkedList<Object>(); //编译错，Object类不能作为E的实际参数，没有实现实现Comparable<E>接口 SortedSinglyLinkedList<Integer> list4 = new SortedSinglyLinkedList<Integer>(); // list4.insert(new Object()); //编译错，参数类型不匹配 [20200113164255384.png]: /images/20210813/d7a40ccc2c1f48dc958f2d72d83e6994.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/03a9d83e240e437497f12d9eda48183b.png
还没有评论，来说两句吧...