线性表

线性表：零个或多个元素的有限序列；

线性表.jpg

线性表的顺序存储结构

线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。

package dataStructure;
//线性表顺序存储结构
public class SeqList<T>{
    public static int MAXSIZE = 20; //存储空间初始分配量
    private int length; //线性表当前长度
    private T[] data; //数组存储数据元素
    
    @SuppressWarnings("unchecked")
![Uploading 线性表_425942.jpg . . .]
    public SeqList(){
        data = (T[]) new Object[MAXSIZE];
    }
    //获取第i个元素
    public T getElem(int i){
        if(i<1 || i>getLength()){
            return null;
        }else{
            return data[i-1];
        }
    }
    
    //在位置i插入元素e
    public boolean ListInsert(int i,T e){
        //若顺序表已满
        if(getLength() == MAXSIZE){
            return false;
        }
        //i不在范围内
        if(i<1 || i>getLength()+1){
            return false;
        }else{
            //插入位置不在表尾
            if(i<getLength()){
                for(int j= getLength()-1;j>=i-1;j--){
                    data[j+1] = data[j];
                }
            }
            data[i-1] = e;
            setLength(getLength() + 1);
            return true;
        }
    }
    
    //删除第i个元素
    public T ListDelete(int i){
        //若表为空
        if(getLength() == 0){
            return null;
        }
        if(i<1 || i>getLength()){
            return null;
        }else{
            T e = data[i-1];
            //若不是最后一个
            if(i<getLength()){
                for(int j=i-1;j<getLength();j++){
                    data[j] = data[j+1];
                }
            }
            setLength(getLength() - 1);
            return e;
        }
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

测试代码：

package dataStructure;  
  
import java.util.Random;  
  
public class SeqListTest {  
    final int MAX = 25;  
    Random r = new Random();  
    SeqList<Integer> seqList;  
      
    public SeqListTest() {  
        initSeqList();  
    }  
      
    //创建一个线性表顺序存储结构  
    public void initSeqList() {  
  
        seqList = new SeqList<Integer>();  
//      int length = (int) Math.random();   //只能产生0.0 - 1.0之间的double随机数  
        int length = Math.abs(r.nextInt(MAX));  //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值    
        System.out.println("产生的数组长度为 ：" + length);  
          
        if(length > SeqList.MAXSIZE) {  
            System.out.println("该长度不合法");  
        }  
          
        for (int i = 1; i <= length; i++) {  //为生成的数组赋值，同时也测试了插入值的方法  
            int j =r.nextInt(MAX);  
            System.out.print(j + " ");  
              
            if(!seqList.ListInsert(i, j)) {  
                System.exit(0);   
            }  
        }  
        System.out.println("\n原始数组是 ：");  
        display(seqList);  
    }  
      
    //测试删除方法  
    public void deleteElem() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n\n删除的位置是：" + i);  
        Integer deleteNumber = seqList.ListDelete(i);  
          
        if( deleteNumber == null) {  
            System.exit(0);  
        } else {  
            System.out.println("删除的元素是 ： " + deleteNumber);  
            System.out.println("删除元素后数组是 ：");  
            display(seqList);  
        }  
    }  
      
    //测试随机插入方法  
    public void insertByRandom() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n\n随机插入位置是 ：" + i);  
        int elem = r.nextInt(MAX);  
        System.out.println("随机插入数据是 ：" + elem);  
        seqList.ListInsert(i, elem);  
        System.out.println("随机插入数据后数组是 ：");  
        display(seqList);  
    }  
      
    //数据展示  
    public  void display(SeqList seqList) {  
        for (int i = 1; i <= seqList.getLength(); i++) {  
              
            if(seqList.getElem(i) != null) {  
                System.out.print(seqList.getElem(i) + " ");  
            }  
              
        }  
        System.out.println("数组的长度为 ：" + seqList.getLength());  
    }  
      
    //获取元素  
    public void getElem() {  
        int i = r.nextInt(MAX);  
        System.out.println("\n获取位置为 ：" + i);  
        System.out.println("获取到的元素为 : " + seqList.getElem(i));  
          
          
    }  
      
    public static void main(String[] args) {  
        SeqListTest s = new SeqListTest();  
        s.insertByRandom();  
        s.deleteElem();  
        s.getElem();  
    }  
} 

顺序存储优点：
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
2.对于存，读数据时时间复杂度都是O(1)。

顺序存储缺点：
1.插入和删除操作需要移动大量元素，时间复杂度为O(n)。
2.线性表长度变化较大时，无法确定存储空间的容量。

线性表的链式存储结构（单链表）

线性表的链式存储结构：用一组任意的存储单元存储线性表的数据元素。存储单元可以是连续的也可以是不连续的。

• 头指针：若有头结点，则指向头结点；否则是指向第一个结点。无论链表是否为空，头指针都不为空。
• 头结点：为了操作的方便而设立，在第一个元素之前。头结点的数据域不存储任何信息，指针指向第一个结点。若线性表为空，头结点的指针域为空。
• 最后一个结点指针为null

package dataStructure;
//链表中的结点node
public class Node<T>{
    private T data; // 数据域
    private Node<T> next;//指针域
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }
}

package dataStructure;

public class LinkList<T>{
    private Node<T> head;//头结点
    private int length;//链表的长度
    
    public LinkList(Node<T> head) {  
        this.head = head;  
    }  
    
    //获取第i个元素
    public T getElem(int i){
        int j = 1;
        Node<T> n = head.getNext();//第一个元素
        //得到第i个结点
        while(n!=null && j<i){
            n = n.getNext();
            j++;
        }
        if(n == null || j>i){
            return null;
        }else{
            return n.getData();
        }
        
    }
    
    //在位置i之后插入e
    public boolean ListInsert(int i,T e){
        int j = 1;
        Node<T> n = head;
        //若为第一次插入
        if(head == null && i==1){
            head = new Node<T>();
            head.setData(null);
            Node<T> first = new Node<T>();
            first.setData(e);
            head.setNext(first);
            length++;
            return true;
        }else{
            //得到第i个结点
            while(n!=null && j<i){
                n = n.getNext();
                j++;
            }
            if(n == null || j>i){
                return false;
            }else{
                Node<T> s = new Node<T>();
                s.setData(e);
                s.setNext(n.getNext());
                n.setNext(s);
                length++;
                return true;
            }
        }
        
    }
    
    //删除位置i
    public T ListDelete(int i){
        int j = 1;
        Node<T> n = head.getNext();
        //得到第i-1个结点
        while(n!=null && j<i-1){
            n = n.getNext();
            j++;
        }
        if(n == null || j>i-1){
            return null;
        }else{
            T e = n.getNext().getData();
            n.setNext(n.getNext().getNext());
            length--;
            return e;
        }
        
    }
    
    public Node<T> getHead() {
        return head;
    }
    public void setHead(Node<T> head) {
        this.head = head;
    }
    public int getLength() {
        return length;
    }
    public void setLength(int length) {
        this.length = length;
    }
}

测试代码：

package dataStructure;

import java.util.Random;

public class LinkListTest {
    final int MAX = 25;
    Random r = new Random();
    LinkList<Integer> linkList;
    
    public LinkListTest() {
        initSeqList();
    }
    
    //创建一个线性表顺序存储结构
    public void initSeqList() {
        linkList = new LinkList<Integer>(null);
        int length = Math.abs(r.nextInt(MAX));  //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值  
        System.out.println("产生的链表长度为 ：" + length);
        
        for (int i = 1; i <= length; i++) { //为生成的链表赋值，同时也测试了插入值的方法
            int j =r.nextInt(MAX);
            System.out.print(j + " ");
            
            if(!linkList.ListInsert(i, j)) {
                System.exit(0); 
            }
        }
        System.out.println("\n原始链表是 ：");
        display(linkList);
    }
    
    //测试删除方法
    public void deleteElem() {
        int i = r.nextInt(MAX);
        System.out.println("\n\n删除的位置是：" + i);
        Integer deleteNumber = linkList.ListDelete(i);
        
        if( deleteNumber == null) {
            System.exit(0);
        } else {
            System.out.println("删除的元素是 ： " + deleteNumber);
            System.out.println("删除元素后链表是 ：");
            display(linkList);
        }
    }
    
    //测试随机插入方法
    public void insertByRandom() {
        int i = r.nextInt(MAX);
        System.out.println("\n\n随机插入位置是 ：" + i);
        int elem = r.nextInt(MAX);
        System.out.println("随机插入数据是 ：" + elem);
        linkList.ListInsert(i, elem);
        System.out.println("随机插入数据后链表是 ：");
        display(linkList);
    }
    
    //数据展示
    public  void display(LinkList<Integer> linkList) {
        Node<Integer> node = linkList.getHead();
        while(node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println("链表的长度为 ：" + linkList.getLength());
    }
    
    //获取元素
    public void getElem() {
        int i = r.nextInt(MAX);
        System.out.println("\n获取位置为 ：" + i);
        System.out.println("获取到的元素为 : " + linkList.getElem(i));
        
        
    }
    
    public static void main(String[] args) {
        LinkListTest s = new LinkListTest();
        s.insertByRandom();
        s.deleteElem();
        s.getElem();
    }
}

虽然已上所有链表的操作时间复杂度都为O(n),但如果在第i个位置插入10个结点这种操作，对于顺序存储结构是每次插入都要移动n-i个点，每次都是O(n)。但对于链式存储结构，只要在第一次通过O(n)找到位置i，那么接下来插如的操作时间复杂度都是O(1)。
因此，对于插入或删除数据越频繁的操作，单链表的效率优势越明显。

• 单链表的整表创建

package dataStructure;

public class CreateLinkList {
    // 头插法创建长度为n的链表
    public static LinkList<Integer> createListHead(int n) {
        Node<Integer> head = new Node<Integer>();
        LinkList<Integer> list = new LinkList<Integer>(head);
        int j = 1;
        // 将新结点插入到头结点与前一新结点之间
        while (j <= n) {
            Node<Integer> p = new Node<Integer>();
            p.setData((int) (Math.random() * 25));
            System.out.println(p.getData());
            p.setNext(head.getNext());
            head.setNext(p);
            j++;
        }
        return list;

    }

    // 尾插法创建长度为n的链表
    public static LinkList<Integer> createListTail(int n) {
        Node<Integer> head = new Node<Integer>();
        LinkList<Integer> list = new LinkList<Integer>(head);
        int j = 1;
        // 将结点插入到最后
        while (j <= n) {
            Node<Integer> p = new Node<Integer>();
            p.setData((int) (Math.random() * 25));
            System.out.println(p.getData());
            head.setNext(p);
            head = p;
            j++;
        }
        return list;
    }

    // 数据展示
    public static void display(LinkList<Integer> linkList) {
        Node<Integer> node = linkList.getHead();
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
    }

    public static void main(String args[]) {
        display(createListHead(7));
    }
}

• 单链表的整表删除

//整表删除
    public void clearList(){
        Node<T> p = head;
        Node<T> q = new Node<T>();
        while(q != null){
            q = p.getNext();
            if(q!=null){
                p.setNext(q.getNext());
                length--;
            }
            
        }
    }

比较两种存储方式

Paste_Image.png

• 若线性表要频繁查找，很少进行插入和删除，宜使用顺序存储结构。反之宜用单链表结构。
• 当线性表中的元素个数变动较大或根本不知道有多大时，最好使用单链表。而如果事先知道线性表的大致长度，则考虑使用顺序结构。

静态链表

静态链表：用数组描述的链表。
每一个数组的元素有两个数据域：数据域与指针域（游标）。

package dataStructure.StaticLinkList;

public class Node<T>{
    private T data;//数据域
    private int cur;//指针域
    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public int getCur() {
        return cur;
    }
    public void setCur(int cur) {
        this.cur = cur;
    }
}

一般数组的第一个元素和最后一个元素会被作为特殊元素处理，不存数据。
通常把未被使用的数据元素成为备用链表。

• 数组的第一个元素的cur用来存放备用链表的第一个结点的下标。（即第一个没有数据的下标）
• 数组的最后一个元素的cur用来存放第一个有数值的元素的下标，相当于单链表中的头结点作用。

package dataStructure.StaticLinkList;

@SuppressWarnings("unchecked")
public class StaticLinkList<T> {
    public static int MAXSIZE = 20;
    private Node<T>[] list;
    private int length;
    
    public StaticLinkList(){
        this.list = new Node[MAXSIZE];
    }
    // 初始化链表
    public void initList() {
        for (int i = 0; i < MAXSIZE; i++) {
            Node<T> n = new Node<T>();
            n.setCur(i+1);
            list[i] = n;
        }
        
        // 目前静态链表为空，因此最后一个元素的cur为0
        list[MAXSIZE-1].setCur(0);
    }

    // 在第i个元素位置插入e
    public boolean ListInsert(int i, T e) {
        //创建链表
        if((length == 0 && i ==1)|| i == length+1){
            list[i].setData(e);
            list[MAXSIZE-1].setCur(1);
            length++;
            return true;
        }
        if (i < 1 || i > length) {
            return false;
        }
        // 首先取得备用链表第一个结点的下标：
        int cur = list[0].getCur();
        // 同时改变第一个元素的cur，因为刚取出来的cur要被使用了，不再是备用链表的第一个结点了
        list[0].setCur(list[cur].getCur());

        list[cur].setData(e);

        int k = MAXSIZE-1;
        // 此时取出来的k为第i-1个元素的下标
        for (int j = 1; j <= i - 1; j++) {
            k = list[k].getCur();
        }
        // 第i个元素的下标
        int insert = list[k].getCur();
        list[k].setCur(cur);
        list[cur].setCur(insert);
        length++;
        return true;
    }

    // 删除第i个元素
    public T ListDelete(int i) {
        if (i < 1 || i > length) {
            return null;
        }
        int k = MAXSIZE-1;
        // 此时取出来的k为第i-1个元素的下标
        for (int j = 0; j < i - 1; j++) {
            k = list[k].getCur();
        }
        //第i个元素下标：
        int del = list[k].getCur();
        T e = list[del].getData();
        list[k].setCur(list[del].getCur());
        //更改第一个元素的cur与要删除元素的cur，因为要删除的元素变成了备用链表的第一个元素
        list[del].setCur(list[0].getCur());
        list[0].setCur(del);
        length--;
        return e;
        
    }

    //展示数据
    public void display(){
        int k = list[MAXSIZE-1].getCur();
        for(int i=1;i<=length;i++){
            T e = list[k].getData();
            k = list[k].getCur();
            System.out.print(e + " ");
        }
        System.out.println("链表的长度为 ：" + getLength());
    }
    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

    public Node<T>[] getList() {
        return list;
    }

    public void setList(Node<T>[] list) {
        this.list = list;
    }

}

测试代码：

package dataStructure.StaticLinkList;

import java.util.Random;

public class StaticLinkListTest {
    StaticLinkList<Integer> sllist = new StaticLinkList<Integer>();

    // 用随机数初始化一个长度为n的静态链表
    public void init(int n) {
        sllist.initList();
        for (int i = 1; i <= n; i++) {
            sllist.ListInsert(i, (int) (Math.random() * 25));
        }
        display(sllist);
    }

    // 测试删除方法
    public void deleteElem() {
        int i = (int) (Math.random() * sllist.getLength());
        System.out.println("\n\n删除的位置是：" + i);
        Integer deleteNumber = sllist.ListDelete(i);

        if (deleteNumber == null) {
            System.exit(0);
        } else {
            System.out.println("删除的元素是 ： " + deleteNumber);
            System.out.println("删除元素后链表是 ：");
            display(sllist);
        }
    }

    // 测试随机插入方法
    public void insertByRandom() {
        int i = (int) (Math.random() * sllist.getLength());
        System.out.println("\n\n随机插入位置是 ：" + i);
        int elem = (int) (Math.random() * 20);
        System.out.println("随机插入数据是 ：" + elem);
        sllist.ListInsert(i, elem);
        System.out.println("随机插入数据后链表是 ：");
        display(sllist);
    }

    // 展示list
    public void display(StaticLinkList<Integer> sslist) {
        sslist.display();
    }

    public static void main(String[] args) {
        StaticLinkListTest s = new StaticLinkListTest();
        s.init(8);
        s.deleteElem();
        s.insertByRandom();
    }

}

• 静态链表优点：
  在插入和删除时，只需改变游标而无需移动元素。
• 静态链表缺点：
  没有解决连续存储分配内存空间难以确定的问题；
  失去了顺序存储结构随机存取的特性。

循环链表

将单链表中的终端节点的指针由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表为循环链表。

循环链表解决了从任何一个结点出发从而遍历到所有结点的问题。

循环链表与单链表的主要差异：循环的判断条件，单链表是判断p.next是否为空，循环列表则判断p.next是否为头结点。

在单链表中，在访问尾结点时需要O(n)的时间。但如果在循环链表中不使用头指针，而是使用尾指针rear，则访问第一个结点和最后一个结点都是O(1)。

双向链表

在单链表的每个结点中，都有一个前驱指针指向其前驱结点。所以双向链表中的结点都有两个指针域，一个指向后继，一个指向前驱。

双向链表使得之前查前驱结点的时间复杂度由O(n)变为O(1)。

但双向链表在插入和删除时都需更改两个指针。