线性表的java实现（数组，链表）
程序员文章站
2022-06-06 20:37:42
...
package com.nobody.list;
/** ADT线性表接口
* 线性表的元素位置从1开始
*/
public interface ListInterface{
/** Task:往线性表的末尾插入新元素
* @param newEntry 做为新元素插入的对象
* @return 如果插入成功则返回true,否则返回false
*/
public boolean add(Object newEntry);
/** Task:往线性表的指定位置插入一个新元素，原本位于该位置及之后的元素各向后移动一个位置，线性表的大小增1.
* @param newPosition 线性表新元素插入的位置，1 <= newPosition && getLength()+1 >= newPosition
* @param newEntry 作为新元素插入的对象
* @return 如果插入成功则返回true,否则返回false
*/
public boolean add(int newPosition, Object newEntry);
/** Task:从线性表中删除指定位置的元素,原本位于该位置之后的元素各向前移动一个位置，线性表的大小减1
* @param givenPosition 删除元素的指定位置，1 <= givenPosition && getLength() >= givenPosition
* @return 如果删除成功则返回被删除的元素，否则返回 null
*/
public Object remove(int givenPosition);
/** Task: 从线性表中删除所有元素
*/
public void clear();
/** Task: 从线性表中替换指定位置的元素
* @param givenPosition 元素替换的指定位置，1 <= givenPosition && getLength() >= givenPosition
* @param newEntry 用以替换givenPosition元素的对象
* @return 如果替换成功则返回true，如果线性表为空或者givenPosition位置非法则返回false
*/
public boolean replace(int givenPosition, Object newEntry);
/** Task: 从线性表的指定位置获取元素（对象的引用）
* @param givenPosition 元素的索引位置，1 <= givenPosition && getLength() >= givenPosition
* @return 如果索引成功则返回元素，否则返回null
*/
public Object getEntry(int givenPosition);
/** Task: 判断线性表中是否含有给定的元素
* @param anEntry 表示待查元素的对象
* @return 如果线性表中存在anEntry则返回true,否则返回false
*/
public boolean contains(Object anEntry);
/** Task: 获取线性表的长度
* @return 返回线性表当前所含元素的个数
*/
public int getLength();
/** Task: 判断线性表是否为空
* @return 如果为空则返回true,否则返回false
*/
public boolean isEmpty();
/** Task: 判断线性表是否已满
* @return 如果线性表已满则返回true,否则返回false
*/
public boolean isFull();
/** Task: 按元素在线性表中的顺序，显示全部的元素
*/
public void display();
}
package com.nobody.list.imp;
import com.nobody.list.ListInterface;
/** 使用定长数组实现ADT线性表 */
public class AList implements ListInterface{
private Object[] entry; //线性表元素数组
private int length; //线性表当前元素的个数
private static final int MAX_SIZE = 50; //线性表的最大长度
public AList(){
entry = new Object[MAX_SIZE];
length = 0;
}
public AList(int maxSize){
entry = new Object[maxSize];
length = 0;
}
public boolean add(Object newEntry){ //在线性表末尾插入对象
boolean result = false;
if(!isFull()){
entry[this.length] = newEntry;
this.length++;
result = true;
}
return result;
}
public boolean add(int newPosition, Object newEntry){ //在指定位置插入对象
boolean result = false;
if(!isFull() && newPosition >= 1 && newPosition <= this.length + 1){
makeRoom(newPosition);
entry[newPosition - 1] = newEntry;
this.length++;
result = true;
}
return result;
}
public Object remove(int givenPosition){ //删除指定位置对象，并返回该对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
result = entry[givenPosition - 1];
removeGap(givenPosition);
this.length--;
}
return result;
}
public void clear(){ //清空线性表
this.length = 0;
}
public boolean replace(int givenPosition, Object newEntry){ //替换指定位置对象
boolean result = false;
if(givenPosition >= 1 && givenPosition <= this.length){
entry[givenPosition - 1] = newEntry;
result = true;
}
return result;
}
public Object getEntry(int givenPosition){ //获取指定位置对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
result = entry[givenPosition - 1];
}
return result;
}
public boolean contains(Object anEntry){ //判断线性表中是否存在anEntry
boolean result = false;
for(int i = 0; i < this.length; i++){
if(anEntry.equals(entry[i])){
result = true;
break;
}
}
return result;
}
public int getLength(){ //获取当前线性表长度
return this.length;
}
public boolean isEmpty(){ //判断线性表是否为空
return this.length == 0;
}
public boolean isFull(){ //判断线性表是否已满
return this.length == entry.length;
}
public void display(){ //显示所有对象
for(int index = 0; index < this.length; index++){
System.out.println(entry[index]);
}
}
/** Task: 在线性表的指定位置(newPosition)插入元素时，newPosition及其之后的
* 元素各向后移动一个位置,为新元素的插入腾出空间
* @param newPosition 新元素的插入位置
*/
private void makeRoom(int newPosition){
if(newPosition <= this.length){
for(int i = this.length; i >= newPosition; i--){
entry[i] = entry[i - 1];
}
}
}
/** Task: 在线性表的指定位置(givenPosition)删除该元素之后，newPosition位置
* 之后的元素各向前移动一个位置，填满空缺的位置
* @param givenPosition 元素删除的位置
*/
private void removeGap(int givenPosition){
for(int i = givenPosition; i < this.length; i++){
entry[i - 1] = entry[i];
}
}
}
package com.nobody.list.imp;
import com.nobody.list.ListInterface;
/** 使用动态扩展数组实现ADT线性表 */
public class ArraysList implements ListInterface{
private Object[] entry; //线性表元素数组
private int length; //线性表当前元素的个数
private static final int MAX_SIZE = 50; //线性表无参初始化最初的最大长度
public ArraysList(){
entry = new Object[MAX_SIZE];
length = 0;
}
public ArraysList(int maxSize){
entry = new Object[maxSize];
length = 0;
}
public boolean add(Object newEntry){ //在线性表末尾插入对象
if(isFull()){
doubleArray();
}
entry[this.length] = newEntry;
this.length++;
return true;
}
public boolean add(int newPosition, Object newEntry){ //在指定位置插入对象
boolean result = false;
if(isFull()){
doubleArray();
}
if(newPosition >= 1 && newPosition <= this.length + 1){
makeRoom(newPosition);
entry[newPosition - 1] = newEntry;
this.length++;
result = true;
}
return result;
}
public Object remove(int givenPosition){ //删除指定位置对象，并返回该对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
result = entry[givenPosition - 1];
removeGap(givenPosition);
this.length--;
}
return result;
}
public void clear(){ //清空线性表
this.length = 0;
}
public boolean replace(int givenPosition, Object newEntry){ //替换指定位置对象
boolean result = false;
if(givenPosition >= 1 && givenPosition <= this.length){
entry[givenPosition - 1] = newEntry;
result = true;
}
return result;
}
public Object getEntry(int givenPosition){ //获取指定位置对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
result = entry[givenPosition - 1];
}
return result;
}
public boolean contains(Object anEntry){ //判断线性表中是否存在anEntry
boolean result = false;
for(int i = 0; i < this.length; i++){
if(anEntry.equals(entry[i])){
result = true;
break;
}
}
return result;
}
public int getLength(){ //获取当前线性表长度
return this.length;
}
public boolean isEmpty(){ //判断线性表是否为空
return this.length == 0;
}
public boolean isFull(){ //判断线性表是否已满
return this.length == entry.length;
}
public void display(){ //显示所有对象
for(int index = 0; index < this.length; index++){
System.out.println(entry[index]);
}
}
/** Task: 在线性表的指定位置(newPosition)插入元素时，newPosition及其之后的
* 元素各向后移动一个位置,为新元素的插入腾出空间
* @param newPosition 新元素的插入位置
*/
private void makeRoom(int newPosition){
if(newPosition <= this.length){
for(int i = this.length; i >= newPosition; i--){
entry[i] = entry[i - 1];
}
}
}
/** Task: 在线性表的指定位置(givenPosition)删除该元素之后，newPosition位置
* 之后的元素各向前移动一个位置，填满空缺的位置
* @param givenPosition 元素删除的位置
*/
private void removeGap(int givenPosition){
for(int i = givenPosition; i < this.length; i++){
entry[i - 1] = entry[i];
}
}
/** Task: 当线性表已存满时，调用该方法双倍扩充线性表(扩充数组)
*/
private void doubleArray(){
Object[] oldEntry = entry;
entry = new Object[2 * oldEntry.length];
for(int i = 0; i < oldEntry.length; i++){
entry[i] = oldEntry[i];
}
}
}
package com.nobody.list.imp;
import com.nobody.list.ListInterface;
import java.util.Vector;
/** 使用向量实现ADT线性表 */
public class VectorList implements ListInterface{
private Vector<Object> entry;
public VectorList(){
entry = new Vector<Object>();
}
public VectorList(int initiaSize){
entry = new Vector<Object>(initiaSize);
}
//@SuppressWarnings("unchecked")
public boolean add(Object newEntry){ //在线性表末尾添加一个对象
entry.addElement(newEntry);
return true;
}
//@SuppressWarnings("unchecked")
public boolean add(int newPosition, Object newEntry){ //在指定位置插入对象
boolean result = true;
if(newPosition >= 1 && newPosition <= entry.size()+1){
entry.insertElementAt(newEntry, newPosition-1);
} else{
result = false;
}
return result;
}
public Object remove(int givenPosition){ //删除指定位置对象，并返回该对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= entry.size()){
result = entry.elementAt(givenPosition-1);
entry.removeElementAt(givenPosition-1);
}
return result;
}
public void clear(){ //清空线性表
entry.removeAllElements();
}
//@SuppressWarnings("unchecked")
public boolean replace(int givenPosition, Object newEntry){ //替换指定位置对象
boolean result = false;
if(givenPosition >= 1 && givenPosition <= entry.size()){
entry.setElementAt(newEntry, givenPosition-1);
result = true;
}
return result;
}
public Object getEntry(int givenPosition){ //获取指定位置对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= entry.size()){
result = entry.elementAt(givenPosition-1);
}
return result;
}
public boolean contains(Object anEntry){ //判断线性表中是否存在anEntry
boolean result = false;
for(int i = 0; i < entry.size(); i++){
if(anEntry.equals(entry.elementAt(i))){
result = true;
break;
}
}
return result;
}
public int getLength(){ //获取当前线性表长度
return entry.size();
}
public boolean isEmpty(){ //判断线性表是否为空
return entry.isEmpty();
}
public boolean isFull(){ //判断线性表是否已满
return false;
}
public void display(){ //显示所有对象
System.out.println(entry.toString());
}
}
package com.nobody.list.imp;
import com.nobody.list.ListInterface;
import com.nobody.list.imp.linkedsListNode.Node;
/** 使用链表实现ADT线性表 */
public class LinkedsList implements ListInterface{
private Node firstNode; //引用链表第一个节点
private Node lastNode; //引用链表最后一个节点
private int length; //链表长度
public LinkedsList(){
clear();
}
public boolean add(Object newEntry){ //在线性表末尾插入对象
Node newNode = new Node(newEntry);
if(isEmpty()){ //线性表为空时
this.firstNode = newNode;
}else{
this.lastNode.setNext(newNode);
}
this.lastNode = newNode;
this.length++;
return true;
}
public boolean add(int newPosition, Object newEntry){ //在指定位置插入对象
boolean result = false;
if(newPosition >= 1 && newPosition <= this.length+1){
Node newNode = new Node(newEntry);
if(newPosition == 1){ //插入首部
newNode.setNext(this.firstNode);
this.firstNode = newNode;
if(this.length == 0){
this.lastNode = newNode;
}
} else if(newPosition == this.length+1){ //插入尾部
this.lastNode.setNext(newNode);
this.lastNode = newNode;
} else{ //插入任意两节点之间
Node nodeBefore = getNodeAt(newPosition-1);
Node nodeAfter = nodeBefore.getNext();
nodeBefore.setNext(newNode);
newNode.setNext(nodeAfter);
}
this.length++;
result = true;
}
return result;
}
public Object remove(int givenPosition){ //删除指定位置对象，并返回该对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
if(givenPosition == this.length){ //删除末尾节点
result = this.lastNode.getData();
this.lastNode = getNodeAt(givenPosition-1);
if(this.length == 1){ //如果链表只有一个节点
this.firstNode = null;
}
} else if(givenPosition == 1){ //删除首部节点
result = this.firstNode.getData();
this.firstNode = this.firstNode.getNext();
} else{ //删除任意两节点之间的节点
Node nodeBefore = getNodeAt(givenPosition-1);
Node nodeRemoveTo = nodeBefore.getNext();
Node nodeAfter = nodeRemoveTo.getNext();
nodeBefore.setNext(nodeAfter);
result = nodeRemoveTo.getData();
}
this.length--;
}
return result;
}
public void clear(){ //清空线性表
this.length = 0;
this.firstNode = null;
this.lastNode = null;
}
public boolean replace(int givenPosition, Object newEntry){ //替换指定位置对象
boolean result = false;
if(givenPosition >= 1 && givenPosition <= this.length){
if(givenPosition == this.length){ //替换末尾节点存放的数据对象
this.lastNode.setData(newEntry);
} else{
getNodeAt(givenPosition).setData(newEntry);
}
result = true;
}
return result;
}
public Object getEntry(int givenPosition){ //获取指定位置对象
Object result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
if(givenPosition == this.length){
result = this.lastNode.getData();
} else{
result = getNodeAt(givenPosition).getData();
}
}
return result;
}
public boolean contains(Object anEntry){ //判断线性表中是否存在anEntry
boolean result = false;
Node node = this.firstNode;
while(!result && node != null){
result = anEntry.equals(node.getData());
node = node.getNext();
}
return result;
}
public int getLength(){ //获取当前线性表长度
return this.length;
}
public boolean isEmpty(){ //判断线性表是否为空
return this.length == 0;
}
public boolean isFull(){ //判断线性表是否已满
return false;
}
public void display(){ //显示所有对象
Node node = this.firstNode;
for(int index = 1; index <= this.length; index++){
System.out.println(node.getData());
node = node.getNext();
}
}
/** Task: 获取链表中指定位置的节点对象
* @param givenPosition 指定位置
* @return 返回指定位置的节点对象
*/
private Node getNodeAt(int givenPosition){
Node result = null;
if(givenPosition >= 1 && givenPosition <= this.length){
result = this.firstNode;
for(int i = 1; i < givenPosition; i++){
result = result.getNext();
}
}
return result;
}
}
package com.nobody.list.imp.linkedsListNode;
/** 链表中的节点类 */
public class Node{
private Object data; //数据部分
private Node next; //链接下一个节点
public Node(Object data){
this.data = data;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public void setData(Object data){
this.data = data;
}
public Object getData(){
return this.data;
}
public void setNext(Node next){
this.next = next;
}
public Node getNext(){
return this.next;
}
}
package com.nobody.entry;
//import java.lang.*;
/** 姓名类
*/
public class Name{
private String first; //名
private String last; //姓氏
public Name(){
}
public Name(String first, String last){
this.first = first;
this.last = last;
}
public void setFirst(String first){
this.first = first;
}
public String getFirst(){
return this.first;
}
public void setLast(String last){
this.last = last;
}
public String getLast(){
return this.last;
}
public void setName(String first, String last){
this.setFirst(first);
this.setLast(last);
}
public void giveLastNameTo(Name name){ //将参数中的name对象的姓氏，修改成与调用者name对象的姓氏相同
name.setLast(this.last);
}
public String toString(){
return this.first + " " + this.last;
}
public boolean equals(Object obj){ //比较两个Name对象是否相同，相同则返回true,否则返回false;
boolean result = false;
if(obj instanceof Name){
Name name = (Name)obj;
String firstName = name.getFirst();
String lastName = name.getLast();
result = first.equals(firstName) && last.equals(lastName);
}
return result;
}
}
package com.nobody.entry;
/** 参赛者类
*/
public class Contestants{
private int id; //参赛号
private Name name; //参赛者姓名
public Contestants(){
}
public Contestants(int id, Name name){
this.id = id;
this.name = name;
}
public void setContestants(int id, Name name){
setId(id);
setName(name);
}
public void setId(int id){
this.id = id;
}
public int getId(){
return this.id;
}
public void setName(Name name){
this.name = name;
}
public Name getName(){
return this.name;
}
public String toString(){
return this.id + "号 " + name.toString();
}
public boolean equals(Object object){
boolean result = false;
if(object instanceof Contestants){
Contestants c = (Contestants)object;
result = this.id == c.getId() && this.name.equals(c.getName());
}
return result;
}
// public static void main(String[] args){
// Name n = new Name();
// Contestants s = new Contestants("2", n);
// System.out.println(s.toString());
// }
}
package com.nobody;
import com.nobody.list.*;
import com.nobody.list.imp.*;
import com.nobody.entry.*;
/* 客户类：测试线性表功能 */
public class Client{
public static void main(String[] args){
testList(new AList()); //测试AList类
testArraysList(); //测试ArraysList类
testList(new VectorList()); //测试VectorList类
testList(new LinkedsList()); //测试LinkedsList类
}
private static void displayList(ListInterface list){ //打印输出线性表对象
for(int i = 1; i <= list.getLength(); i++){
System.out.println("第" + i + "名是" + list.getEntry(i));
}
}
/** 举行一场赛跑比赛，使用线性表记录参赛人员到达终点的顺序并显示
* 主要用于测试AList类
*/
private static void testList(ListInterface list){
// ListInterface nameList = getNameList();
ListInterface runnerList = list; //创建线性表
Contestants[] c = new Contestants[]{ //创建参赛者对象
new Contestants(2, new Name("Artest", "Ron")),
new Contestants(4, new Name("Baker", "Vin")),
new Contestants(1, new Name("Bell", "Raja")),
new Contestants(3, new Name("Butler", "Jackie")),
new Contestants(5, new Name("Carter", "Vince")),
};
for(int i = 1; i <= c.length; i++){
runnerList.add(c[i - 1]); //添加线性表元素
}
displayList(runnerList); //显示
Contestants cs = new Contestants(6, new Name("Cook", "Brian"));
if(!runnerList.add(1, cs)){
System.out.println("\n插入失败");
} else{
System.out.println("\n在线性表1号位置插入元素成功");
displayList(runnerList);
}
Contestants con = (Contestants)runnerList.remove(2); //删除线性表2号元素，并返回2号元素
if(cs == null){
System.out.println("\n删除2号元素失败");
} else{
System.out.println("\n2号元素删除成功");
displayList(runnerList);
}
if(!runnerList.replace(5, con)){ //替换
System.out.println("\n替换5号元素失败");
} else{
System.out.println("\n5号元素替换成功");
displayList(runnerList);
}
if(runnerList.contains(cs)){ //判断线性表是否存在cs对象
System.out.println("\n线性表中存在" + cs);
} else{
System.out.println("\n线性表中不存在该对象");
}
}
private static void testArraysList(){ //测试ArraysList类实现的线性表是否可扩展
ListInterface runnerList = new ArraysList(2);
runnerList.add("3");
runnerList.add("2");
runnerList.add("5");
runnerList.add("1");
runnerList.add("4");
runnerList.display();
}
}上一篇： 队列详解
下一篇： 花盆种菜应该注意什么？种什么菜比较好？