- 线性表的定义
- 线性表的基本运算
- 线性表的存储之顺序存储
- 定义线性表
- 添加元素
- 查找元素
- 删除元素
- 打印线性表
- 实现的完整代码
- 测试一下
- 线性表的逻辑特征：
- ①有且仅有一个称为开始元素的a1，她没有前趋，仅有一个后继结点a2；
- ②有且仅有一个称为终端元素的an,他没有后继，只有一个直接前驱a(n-1)；
- ③其余元素ai(2≤i≤n-1)称为内部元素，他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1)。
- 线性表初始化
- 求表长
- 按索引值查找元素
- 按值查找
- 插入元素
- 删除
定义线性表线性表顺序存储的定义：线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组连续的存储单元里，用这种方式存储的线性表称为顺序表。
- 定义线性表的默认空间大小，定义一个数组，定义数组的长度，初始化一个size用来保存里面元素的个数。
private final Integer ListSize=100;
private Integer Len;
private Object[] list;
private Integer size=0;
public SeqList(){
Len = ListSize;
this.list = new Object[Len];
size++;
}
- 初始化线性表
- 把线性表里面的元素全部置空
public void clear(){
for (int i = 0; i < size; i++) {
list[i]=null;
}
size=0;
}
添加元素
- 这里采用尾插法，即每次默认将元素放在最后面
public void insert(T element , int index){
if(index>=Len || index<0){
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
}
Capacity(size+1);
//将添加元素的元素往后移一位
for (int i = size-2; i >= index-1; i--) {
list[i+1]=list[i];
}
list[index-1]=element;
size++;
}
public void add(T element){
insert(element,size);
}
查找元素
- 这个模块分为按索引值查找，和按元素值查找
public T getNode(int index){
return (T)list[index-1];
}
public int LocateNode(T t){
for(int i=0;i
删除元素
- 删除元素，又分为删除指定元素，和删除最后一个元素
public T delete(int index){
if(!OutIndex(index)){
throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内！");
}
for (int i = index-1; i < size-1; i++) {
list[i]=list[i+1];
}
list[size-1]=null;
size--;
return (T) list;
}
public T remove(){
return delete(size-1);
}
打印线性表
- 打印线性表，其实就是重写一个toString方法，将线性表打印出来
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
if(isEmpty()){
return "[]";
}
else {
sb.append("[");
for (int i = 0; i < size-1; i++) {
int a=0;
if(list[i]!=null){
sb.append(list[ i ]);
}
else {
break;
}
sb.append(",");
}
sb.append("]");
sb.deleteCharAt(sb.indexOf(",]"));
}
return sb.toString();
}
实现的完整代码
class SeqList{
private final Integer ListSize=100;
private Integer Len;
private Object[] list;
private Integer size=0;
public SeqList(){
Len = ListSize;
this.list = new Object[Len];
size++;
}
public SeqList(int length){
Len = length;
list = new Object[Len];
size++;
}
public int getLen(){
return Len;
}
public int getSize(){
return size;
}
public int getIndex(T element){
for (int i = 0; i < size; i++) {
if(list[i].equals(element)){
return i;
}
}
return -1;
}
private boolean OutIndex(int index){
//return size==Len;//不扩容的话，可以这样写，但是怕扩容
if(index>size || index<0){
return false;
}
else {
return true;
}
}
private T getElement(int index){
if(!OutIndex(index)){
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
}
return (T)list[index];
}
private T Capacity(int capacity){
if(capacity=Len || index<0){
throw new IndexOutOfBoundsException("输入的索引值超过了线性表的范围");
}
Capacity(size+1);
//将添加元素的元素往后移一位
for (int i = size-2; i >= index-1; i--) {
list[i+1]=list[i];
// System.out.println("i="+i);
}
list[index-1]=element;
size++;
}
public void add(T element){
insert(element,size);
}
public boolean isEmpty(){
return size==0;
}
public T delete(int index){
if(!OutIndex(index)){
throw new IndexOutOfBoundsException("删除位置不在线性表的索引范围内！");
}
for (int i = index-1; i < size-1; i++) {
list[i]=list[i+1];
}
list[size-1]=null;
size--;
return (T) list;
}
public T remove(){
return delete(size-1);
}
public void clear(){
for (int i = 0; i < size; i++) {
list[i]=null;
}
size=0;
}
public T getNode(int index){
return (T)list[index-1];
}
public int LocateNode(T t){
for(int i=0;i
测试一下
- 测试代码
public static void main(String[] args) {
SeqList seqList = new SeqList();
//添加一个元素
seqList.add("pier");
seqList.add("真好看");
seqList.add("90度点头");
System.out.println("添加后的线性表为nt"+seqList.toString());
seqList.insert("pipi",1);
System.out.println("在位置1的地方添加元素后的线性表为nt"+seqList.toString());
seqList.delete(1);
System.out.println("删除第二个元素后的线性表为nt"+seqList.toString());
System.out.println("pier时第"+seqList.LocateNode("pier")+"个元素");
System.out.println("第1个元素是"+seqList.getNode(1)+"。");
}
- 运行结果
