线性表

线性表是 n 个元素构成的有序序列。对线性表的存储方式通常有数组和链表两种方式。

不管哪种存储方式，线性表基本操作主要有：

• insert(int v, int i ) : 在位序 i 前插入一个新元素 v
• delete( int i ) : 删除指定位序 i 的元素
• listLength() : 返回线性表 L 的长度 n
• find( int v ) : 在线性表 L 中查找 v 的第一次出现位置
• findKth( int K ) : 根据位置 K，返回相应元素

数组

如下主要演示以数组为存储方式的线性表的基本操作。

声明一个线性表的类型

array 主要负责帮助线性表以数组形式存储数据。

public class MyListArray {
    private int[] array;
    private int last;      //最后一个元素所在数组中的下标位置
}

find（查找）

遍历数组 array，查找值并返回值位置。

// 查找   
public int find(int v){
    int i = 0;
    while(i <= last && array[i]!=v)
        i++;
    if(i > last) return -1;   /*如果没有找到，返回 -1*/
    else return i;       /*找到后返回的是存储位置*/
}

insert（插入）

先看一张图：

 /**
     * 插入
     * @param v 要插入的值
     * @param i 要插入的位置
     */
    public void insert(int v, int i){
        int j;
        if(last == array.length-1){  /*表空间已满，不能插入*/
            System.out.println("表满");
            return;
        }

        if(i<1 || i>last+2){   
            System.out.println("位置不合法");
            return;
        }

        for(j = last; j>=i-1; j--)
            array[j+1] = array[j];  /*将 ai~an 倒序向后移动*/   
        array[i-1] = v;             /*新元素插入*/
        last++;                     /*last仍指向最后元素*/
        return;
    }

delete（删除）

先看一直图片：

/**
     * 删除
     * @param i 要删除的元素的位置
     */
    public void delete(int i){
        int j;
        if(i<1 || i>last+1){
            System.out.println("位置不合法");
            return;
        }
        for(j=i; j<=last; j++)
            array[j-1]=array[j];    /*将 ai+1~an 顺序向前移动*/    
        last--;                     /*last仍指向最后元素*/
        return;
    }

单链表

如下主要演示以单链表为存储方式的线性表的基本操作。

声明一个线性表的类型

单链表包含多个结点，每个结点有一个指向后继元素的 next 指针。最后一个结点的 next 指针为 null。

public class MyListNode {
    private int data;          /*当前对象结点所存的数据*/
    private MyListNode next;
    public MyListNode(int data){
        this.data = data;
    }
    public void setData(int data){
        this.data = data;
    }
    public int getData() {
        return data;
    }
    public void setNext(MyListNode next) {
        this.next = next;
    }
    public MyListNode getNext() {
        return next;
    }
}

listLength （线性表长度）

listLength() 函数输出链表长度，主要思路是遍历链表，当 next 指针输出为 null 时遍历结束，用 lenght 记录长度

int listLength(MyListNode headNode){
    int length = 0;
    MyListNode currentNode = headNode;     /*currentNode 指向第一个节点*/
    while(currentNode != null){
        length++;                          
        currentNode = currentNode.getNext();
    }
    return length;
}

find 和 findKth （查找）

遍历整个链表，返回查找到的结点。

/**
 * 按序号查找
 * @param position 序号
 * @param headNode 头节点
 * @return
 */
MyListNode findKth(int position, MyListNode headNode){
    MyListNode currentNode = headNode;
    int i = 1;
    while(currentNode!=null && i<position){
        currentNode = currentNode.getNext();
        i++;
    }
    if(i==position) return currentNode;
    else return null;
}

/**
 * 按值查找
 * @param v 所要查询的值
 * @param headNode 头节点
 * @return
 */
MyListNode find(int v, MyListNode headNode){
    MyListNode currentNode = headNode;
    while(currentNode != null && currentNode.data != v){
        currentNode = currentNode.getNext();
    }
    return currentNode;
}

insert （插入）

插入操作分为以下3种情况：

1）在链表的表头插入一个新结点

• 更新新节点 next 指针，使其指向当前的表头节点
• 更新表头指针的值，使其指向新节点。

2）在链表的表尾后插入一个新节点

• 新结点的 next 指针指向 null
• 最后一个结点的 next 指针指向新结点

3）在链表的中间插入一个新结点，如下操作可以完成

• 如果要在位置3增加一个元素，则需要将指针定位于链表的位置2。假设第二个结点为位置结点，新结点的 next 指针指向位置结点的下一个结点
• 位置结点的 next 指针指向新结点

MyListNode insert(int v, int position, MyListNode headNode){
    MyListNode nodeToInsert;
    if(position==1){                 /*表头插入*/
        nodeToInsert = new MyListNode(v);
        nodeToInsert.setNext(headNode);
        return nodeToInsert;
    }

    MyListNode pre = findKth(position-1, headNode);       /*查找第i-1个节点*/
    if(pre == null){
        System.out.println("参数position错误");
        return null;
    }else{                                 /*表中或者表尾插入*/
        nodeToInsert = new MyListNode(v);
        nodeToInsert.setNext(pre.getNext());
        pre.setNext(nodeToInsert);
        return headNode;
    }
}

delete （删除）

删除操作分为以下3种情况：

1）删除单向链表的第一个结点。

2）删除单向链表的最后一个结点。

3）删除单向链表的中间一个结点。

代码

MyListNode delete(int position, MyListNode headNode){
    if(position == 1){        /*若要删除的是表第一个节点*/
        MyListNode currentNode = headNode.getNext();
        headNode = null;
        return currentNode;
    }       

    MyListNode pre = findKth(position, headNode);   /*查找第i-1个节点*/

    if(pre == null){
        System.out.println("节点不存在");
        return null;
    }else if(pre.getNext() == null){
        System.out.println("节点不存在");
        return null;
    }else{       /*删除的是中间或者最后一个节点*/
        MyListNode currentNode = pre.getNext();
        pre.setNext(currentNode.getNext());
        currentNode = null;
        return headNode;
    }
}