算法初级（三）——线性表

以你之姓@ 2023-03-13 09:18 18阅读 0赞

概念：  
线性表是由n(n  ≥ \\geq ≥ 0)个数据元素所构成的有限序列，通常表示为（ a 0 a\_0 a0, a 1 a\_1 a1, a 2 a\_2 a2, a 3 a\_3 a3… a n − 1 a\_\{n-1\} an−1）,其中下标i标识数据元素在线性表中的序列号，n为线性表长（n=0为空表）。对于同一个线性表，其每一个数据元素的值虽然不同但是却具有相同的数据类型，同时数据元素之间具有一种线性的或“一对一”的逻辑关系，即：

*  第一个数据元素没有前驱，这个数据元素称为开始结点；
 *  最后一个数据元素没有后继，这个数据元素称为终端节点；
 *  除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和后继。

图示：  
![在这里插入图片描述][20200512212919724.png]  
线性表结构简单，一般来说有以下几种主要操作：

1.  置空操作clear()
2.  判空操作isEmpty()
3.  获取长度length()
4.  获取元素get(i)
5.  插入元素insert(index,object)
6.  删除操作remove(i)
7.  查找操作indexOf(i)
8.  输出display()

用java的抽象数据类型写下代码：

interface IList{ 
    	public void clear();
    	public boolean isEmpty();
    	public int length();
    	public Object get(int i);
    	public void insert(int index,Object object);
    	public void remove(int i);
    	public void indexOf(Object object);
    	public void display();
    }

加上实现方法：

interface IList { 
    	public void clear();
    
    	public boolean isEmpty();
    
    	public int length();
    
    	public Object get(int i) throws Exception;
    
    	public void insert(int index, Object object) throws Exception;
    
    	public void remove(int i) throws Exception;
    
    	public int indexOf(Object object);
    
    	public void display();
    }
    
    public class MyList implements IList { 
    	private Object[] listElem;// 线性表的存储空间
    	private int curLen;// 线性表当前长度
    
    	public MyList(int maxSize) { 
    		listElem = new Object[maxSize];// 分配大小为maxSize的存储单元
    		curLen = 0;// 置顺序表的当前长度为0
    	}
    
    	@Override
    	public void clear() { 
    		// 置顺序表当前的长度为0
    		curLen = 0;// 置顺序表的当前长度为0，这里没有释放内存，把listElem == null
    	}
    
    	@Override
    	public boolean isEmpty() { 
    		return curLen == 0;
    	}
    
    	@Override
    	public int length() { 
    		return curLen;
    	}
    
    	@Override
    	public Object get(int i) throws Exception { 
    		if (i < 0 || i > curLen - 1)
    			throw new Exception("下标异常");
    		return listElem[i];
    	}
    
    	@Override
    	public void insert(int index, Object object) throws Exception { 
    		if (curLen == listElem.length)
    			throw new Exception("顺序表已满");
    		if (index < 0 || index > curLen)
    			throw new Exception("插入位置不合法");
    		for (int i = curLen; i > index; i--) { 
    			listElem[i] = listElem[i - 1];
    		}
    		listElem[index] = object;
    		curLen++;
    	}
    
    	@Override
    	public void remove(int index) throws Exception { 
    		if (index < 0 || index > curLen)
    			throw new Exception("删除位置不合法");
    		for (int i = index; i < curLen - 1; i++) { 
    			listElem[i] = listElem[i + 1];
    		}
    		curLen--;
    	}
    
    	@Override
    	public int indexOf(Object object) { 
    		int j = 0;
    		while (j < curLen && !listElem[j].equals(object))
    			j++;
    		if (j < curLen)
    			return j;
    		else
    			return -1;
    	}
    
    	@Override
    	public void display() { 
    		for (int i = 0; i < listElem.length; i++) { 
    			System.out.println(listElem);
    		}
    	}
    
    }

先到这，告辞！

[20200512212919724.png]: /images/20230312/2012ff7456ee43e39c86db29d131a7a6.png