数据结构--线性表

线性结构是最简单最直接的数据关系，数据元素之间一一对应。

线性表的概念

线性表是由n个类型相同数据元素的有限序列。

线性表的特点：

同一性：线性表是由同类数据元素组成的，每一个a必须是同一数据对象

有穷性：线性表是由有限个数据元素组成，表长度就是表中数据元素的个数

有序性：线性表中相邻数据元素之间存在着序偶关系

抽象数据类型的使用：

由于抽象数据类型定义了相应模型上的基本 运算集，可如同使用整形类型的加减乘除运算集合一样，只要列出线性表抽象数据类型LinearList 就可以直接使用其上的基本运算集

抽象数据类型的使用：

抽象数据类型一经定义，就可以多次使用
在实际问题中可利用线性表抽象数据类型的9种基本运算的组合实现对线性表进行合并、分拆、排序等多种需求。

1、线性结构的特点

线性结构是最简单、最基本的结构，数据元素间是一一对应关系。

2、线性表定义

是由n个数据元素的有限序列。除第一个和最后一个元素以外，其余的每个元素都只有唯一的直接前驱和直接后继。

3、线性表抽象数据类型定义

线性表ADT包括抽象数据类型的名称及数据元素、结构关系、基本操作集合三部分。

线性表的顺序存储结构

节点顺序存，节点线性化

类型和变量的区别：
例如：两室一厅就是一个类型的定义，是一个类型是一个规格，这样301,302 这种门牌号都可以使具有这种规格的空间，这就是变量。

自定义类型定义了一种规格，如顺序表的数据类型定义SeqList

typedef  struct
{
    ElemType elem[MAXSIZE]   //线性表占用的数组空间
    int last;                //线性表的最后一个元素在数组中的位置下标

}SeqList;

(2)变量是规格类型的具体空间,两种定义方式

• 将L定义为 Seql list:类型的变量,如 Seqlist L 将顺序表定义为一个变量。使用的时候我们
  可通过属性访问方式L.elem[i-1]访问顺序表中序号为i的元素ai。

• 将L定义为指向 Seqlist类型的指针变量,如 SeqList *L 可通过指针访问方式L->elem[i-1]访问顺序表中序号为i的元素ai。

类型是一种规格的定义，而变量是一种空间的定义。

线性表的基本运算

增删改查

在上面的定义中，我们通过一个结构体，进行了一个简单线性表的定义，我们在C语言或者C++z中可以通过一个结构体来进行定义，在Java中没有结构体，我么可以通过一个类来进行线性表的表示。

使用Java语言先定义一个线性表 ，然后我们再定义其中的基本操作

Java JDK中有ArrayList和LinkedList两个类很好的实现了顺序存储和链式存储。因此学习数据结构的最好方式是去研究JDK源码。

我们可以看一下Java中ArrayList和LinkedList的区别：

1. ArrayList和LinkedList可想从名字分析，它们一个是Array(动态数组)的数据结构，一个是Link(链表)的数据结构，此外，它们两个都是对List接口的实现。ArrayList是数组队列，相当于动态数组；LinkedList为双向链表结构，也可当作堆栈、队列、双端队列

2. 当随机访问List时（get和set操作），ArrayList比LinkedList的效率更高，因为LinkedList是线性的数据存储方式，所以需要移动指针从前往后依次查找。

3. 当对数据进行增加和删除的操作时(add和remove操作)，LinkedList比ArrayList的效率更高，因为ArrayList是数组，所以在其中进行增删操作时，会对操作点之后所有数据的下标索引造成影响，需要进行数据的移动。

4. 从利用效率来看，ArrayList自由性较低，因为它需要手动的设置固定大小的容量，但是它的使用比较方便，只需要创建，然后添加数据，通过调用下标进行使用；而LinkedList自由性较高，能够动态的随数据量的变化而变化，但是它不便于使用。

下面使用Java实现一个顺序表

首先定义一个线性表，并定义线性表中的插入删除的相关的操作。

package com.shunxubiao;

/***
 * 
 * @author lei
 *
 */
public class MyArrayList {
	
	//定义一个用来保存数据的数组
	private Object arr[];	
	//定义一个空数组，用来初始化空数组
	private Object[] DEFAULT_EMPTY = {};
	//数组的初始容量，我们可以参照ArrayList源码，数组的初始容量为10
	private  static final int DEFAULT_SIZE = 10;
	//数组的大小,也就是数组的最大容量
	private int maxSize;
	//定义线性表的大小，线性表的当前个数
	private int size;
	
	//带参构造方法，提供能构造指定容量的空列表
	
	public MyArrayList(int inittalSize){
		if (inittalSize > 0) {
			this.arr = new Object[inittalSize];
			this.maxSize = inittalSize;
		}else if (inittalSize == 0) {
			this.arr = DEFAULT_EMPTY;
		}else {
			throw new IllegalArgumentException("不能为负，非法容量"+inittalSize);
		}
	}
	
	//空参构造，用来初始化一个空数组
	public MyArrayList(){
		this.arr = DEFAULT_EMPTY;
	}
	   
	
}

   
   //往线性表中指定位置插入数据
//在指定位置插入元素，首先就是需要判断插入位置是否正确，然后判断数组长度是否越界，
//如果已经满了我们需要重新增加数组的长度，一般是增加1.5倍长度，ArrayList JDK源码中也是增加1.5倍的数组长度。
//然后移动数组元素，空出需要插入的位置，最后把数据插入到数组中。


   //在数组的指定位置插入元素。
public void insert(int i,Object elem){
	//首先判断数组插入的位置是否合法
	if (i < 0) {
		new IllegalArgumentException("插入位置不合法");
	}
	if(i > size){
		new IllegalArgumentException("插入位置越界，当前数组的大小为："+size);
	}
	
	Object oldArr[];
	Object newArr[];//用来存放扩容后的容量
	//如果当前线性表中数组为满的，需要增加数组的存储空间
	if (i == maxSize) {		
		oldArr = arr;			
		newArr = new MyArrayList[(int) (maxSize*1.5)];
		//把旧数组中的元素赋值到新的数组中
		for (int j = 0; j < newArr.length; j++) {
			newArr[j] = oldArr[j];
		}			
		maxSize = (int) (maxSize*1.5);
		arr = newArr;
	}
	
	//如果插入的位置是最后一个元素，不需要移动元素
	if (i == size) {
		arr[i] = elem;
		size++;
		return;
	}
	
	//如果插入的不是最后一个位置，需要移动元素，先移动位置，空出带插入位置元素
	for (int j = size;j > i;j--) {
		arr[j] = arr[j-1];
	}
	//移动完之后，插入元素
	arr[i] = elem;
	size++;
	
	//查看数组中的元素
	for (int j = 0; j < arr.length; j++) {
		System.out.print("  " +arr[j]);
	}
	
}

时间复杂度分析：

最好情况：在线性表的末尾插入，（i = size）元素后移的语句将不再执行，时间复杂度为O(1)

最坏情况：在表头插入，（即i=0）元素后移的语句将执行n次，时间复杂度为O(n)

平均情况：n/2

因此，线性表插入算法的时间复杂度为O(n)

   
   //移除指定位置的元素
public void remove(int i,Object elem){
	//首先判断移除的位置时候合法
	if (i < 0) {
		new IllegalArgumentException("插入位置为负，不合法");
	}
	if (i > size) {
		new IllegalArgumentException("移除位置超越数组长度，当前长度为："+size);
	}
	
	//判断是否是移动的最后一个元素，如果是最后一个元素不需要移动元素
	if (i == size-1) {
		arr[i] = null;
		size--;
		return;
	}
	
	//一般情况的处理
	arr[i] = null;
	//移动元素
	for (int j=i; j<size-1;j++) {
		arr[j] = arr[j+1];
	}
	arr[size-1]=null;//最后一个元素为空
	size--;
	
	//查看数组中的元素
	if (arr != null) {
           System.out.println("");
           for (int j = 0; j < arr.length; j++) {
               System.out.print(" " + arr[j]);
           }
       }
	
}

时间复杂度分析：

最好情况：在线性表的末尾移除，（i = size）元素后移的语句将不再执行，时间复杂度为O(1)

最坏情况：在表头移除，（即i=0）元素后移的语句将执行n次，时间复杂度为O(n)

平均情况：n-1/2

因此，线性表插入算法的时间复杂度为O(n)

//清空数据
public void clear() {
if (arr != null) {
for (int i = 0; i < size; i++) {
arrs[i] = null;
}
}
size = 0;
}

上面是最一种线性表的操作，下面再看一下线性表中对两个顺序表的合并操作。

【编写算法】:有两个顺序表LA和LB,其元素均为递增有序排列,编写算法,将两个有序表合并成一个递增有序的顺序表LC

【算法思路】

• 1)初始化:LC为空表,设LC表的指示器k=0

• 设两个指示器i,j分别指向表LA和LB的当前位置,初值均为0。

• 2)比较循环:将LA.elem[]和LB.elem[]两元素进行比较,较小元素放入表LC中,且该表的指示器和G表的指示器k均加1移向下一个位置。如此下去,直到LA或LB表中一个表处理完毕为止。都是当前位置的元素做比较。

• 3)复制循环:将未处理完的表中剩余元素通过循环逐一复制到LC表中。

【算法分析】由于两个待归并的表LA、LB本身就是有序表,且表LC的建立采用的是尾插法建表,插入时不需要移动元素,所以算法的时间复杂度O(LA->last+LB->last)

上面的代码，我们依旧使用Java进行实现。

我们首先定义一个线性表的结构，也就是定义一个线性表的类，线性表中定义一个数组然后定义一个指向数组最后一个元素的变量，提供该类的初始化有参构造方法。

SeqList.java

package com.hebing;

public class SeqList {
	
	public int[] array1;
	public int last;	
	
	public SeqList(int[] array1) {
		this.array1=array1;
		if(array1!=null) {//判断是否为空
			last=array1.length;
		}
	}   
}

然后写线性表的合并方法，定义一个合并的类，我们按照上面的算法思路实现这个合并类。定义一个空表C 用来存放合并后的类。然后对表A和表B中的元素依次判断放到表C中。

Combine.java

package com.hebing;

public class Combine {
	
	public void Combine(SeqList A,SeqList B,SeqList C) {
		int a=0,b=0,c=0;
		
		while(a<A.last&&b<B.last) {
			if(A.array1[a]<B.array1[b]) {
				C.array1[c++]=A.array1[a++];
			}else {
				C.array1[c++]=B.array1[b++];
			}
		}
		
		while(a<A.last) {
			C.array1[c++]=A.array1[a++];
		}
		
		
		while(b<B.last) {
			C.array1[c++]=B.array1[b++];
		}
		C.last=c;
	}
	
}

测试方法：

package com.hebing;

import java.util.ArrayList;

public class test {
	
	public static void main(String[] args) {
		SeqList a = new SeqList(new int[] { 5,6,9 ,11}); 
		SeqList b = new SeqList(new int[] { 2,8,10}); 
		SeqList c = new SeqList(new int[a.array1.length + b.array1.length]);
		
		Combine cob=new Combine();
		cob.Combine(a, b, c);
		
		  for(int i=0;i<c.array1.length;i++) {
			  System.out.print(c.array1[i]+" ");
		  }
		  		  
		  
	}

}

线性表的链式存储

上面学习的顺序存储结构是：一组连续单元依次存放表中各个元素
顺序存储结构的特点：便于随机存取，不适合动态的变化。

逻辑上相邻的元素在物理存储位置上也相邻。链式存储结构中，逻辑上相邻的元素在物理存储上不一定相邻。因此设计出结点来对应线性表的元素及元素之间的关系。结点包括两部分 ：结点本身数据信息，元素之间的关联关系。线性表采用链式方式将结点链接起来的存储结构称为链表。

链式存储结构中结点包括两部分不仅包括结点本身信息,还要包括关联关系部分。线性表采用链式方式将结点链接起来的存储结构称为链表。

链式存储结构分为单链表、循环单链表、双向链表和静态链表。

• 从链接方式看,可分为单链表、循环链表和双向链表
• 从实现角度看,可分为动态链表和静态链表。

1. 单链表结构

链表中的结点包括数据域和指针域两个域

数据域data用来存储结点的值

指针域next用来存储结点本身的信息,邻接关系由后继指针指示其位置。

线性链表(单链表):

用一组任意的存储单元存放线性表的结点，每个结点的唯一后继依靠一个结点指针维持。

(这组存储单元可以是连续的也可以是不连续的、甚至是零散的存储在内存的任何位置。即链表结点的逻辑顺序和物理顺序不一定相同。)

• 头指针H指向第一个结点。
• 最后一个结点的指针域为“空”（NULL）

*注意: 链表中头指针，头结点，首结点的关系
链表中头指针指向单链表开始（H）
带头结点的链表中，头指针指向头结点，头结点指向首结点。
无头结点的链表中，头指针指向首结点。
*

单链表的基本运算

链表是一种重要的数据结构，在Java中，HashMap等集合的底层结构都是链表结构。

链表以结点作为存储单元，这些存储单元可以是不连续的。每个结点由两部分组成：存储的数值+前序结点和后序结点的指针。即有前序结点的指针又有后序结点的指针的链表称为双向链表，只包含后续指针的链表为单链表

链表是一种线性表但是并不会按顺序来存储元素

Java中单链表采用Node实体类类标识，其中data为存储的数据，next为下一个节点的指针：

package com.lianbiao;

/**
 * 链表结点的实体类
 *
 */

public class Node {
	Node next = null;//下一个结点
int data;//结点数据

public Node(int data){
this.data = data;
}

}

1. 往链表中插入元素

网链表中插入元素有两种方法，一种是采用头插法。一种是采用尾插法，头插法就是每次网表头插入元素，尾插法就是从表单额末尾依次插入元素。

采用尾插法，必须增加一个节点用来指示链表的末尾节点。

用Java实现尾插法建立链表：

/**链表的根结点*/
   
Node root = null;
       
   /**
    * 链表添加结点:
    * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
    * @param data
    */
   public void addNode(int data){
       Node newNode = new Node(data);
       if(root == null){
           root = newNode;
           return;
       }
       Node temp = root;
       while(temp.next != null){
           temp = temp.next;
       }
       temp.next = newNode;
   }

​

2. 删除链表中的数据

删除链表中的数据，有两种方式进行删除，首先我们可以删除指定位置上的元素。我们还可以按值删除链表中的元素。

首先
按值删除链表中的元素。

删除结点，主要是查找删除结点的前驱结点。然后改变前驱结点的指向就可以了。

  public boolean deleteNodeData(int data){
  	Node curNode = root;
  	
  	if (curNode != null && curNode.data == data) {
	root = curNode.next;
	return true;
}
  	
  	if (curNode != null ) {    		
  		while(curNode.next.data != data){
  			curNode = curNode.next;
  		}    		
  		curNode.next = curNode.next.next;
}
  	
  	return true;
  }

按位置删除链表中的元素

public boolean deleteNode(int index){
    if(index<1 || index>length()){//待删除结点不存在
        return false;
    }
    if(index == 1){//删除头结点
        root = root.next;
        return true;
    }
    Node preNode = root;
    Node curNode = preNode.next;
    int i = 1;
    while(curNode != null){
        if(i==index){//寻找到待删除结点
            preNode.next = curNode.next;//待删除结点的前结点指向待删除结点的后结点
            return true;
        }
        //当先结点和前结点同时向后移
        preNode = preNode.next;
        curNode = curNode.next;
        i++;
    }
    return true;
}

3. 求单链表的长度操作

在顺序表中,线性表的长度是它的属性,数组定义时就已确定

在单链表中,整个链表由“头指针”来表示,单链表的长度在从头到尾遍历的过程中统计计数得到

【算法思路】采用“数”结点的方法求出单链表的长度。即从“头”开始“数”用指针p依次指向各个结点,一直“数”到最后一个结点(p->nextNUL),从而得到单链表的长度

• 顺链头开始,计数器j初值为0
• 当前指针ρ指向链表L的首元结点 p=L->next
• p依次往后(计数j+)直到表尾(p==NULL)

求表长度的操作就是计算单链表中数据结点的个数，需要从第一个结点开始顺序访问表中的每一个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加1，直到访问出空节点为止。

java代码实现

/**
 * 求链表的长度
 * @return
 */
public int length(){
    int length = 0;
    Node curNode = root;
    while(curNode != null){
        length++;
        curNode = curNode.next;
    }
    return length;
}

4. 输出链表中的数据

/**
 * 打印结点
 */
public void printLink(){
    Node curNode = root;
    while(curNode !=null){
        System.out.print(curNode.data+" ");
        curNode = curNode.next;
    }
    System.out.println();
}

5. 反转链表

在反转指针前一定要保存下个结点的指针

/**
     * 反转链表，在反转指针前一定要保存下个结点的指针
     */
    public void reserveLink(){
        Node curNode = root;//根结点
        Node preNode = null;//前一个结点
        while(curNode != null){
            Node nextNode = curNode.next;//保留下一个结点
            curNode.next = preNode;//指针反转
            preNode = curNode;//前结点后移
            curNode = nextNode;//当前结点后移
        }
        root = preNode;
    }

6. 反向输出链表

反向输出链表有三种方式

• 方式一：先反转链表，再输出链表，需要链表遍历两次
• 方式二：把链表中的数字放入栈中再输出，需要维护额外的栈空间
• 方式三：依据栈的思想，通过递归来实现，就是将先执行的数据压如栈中，再一次出栈

//反转链表
   public void reservePrt(Node node){
       if(node != null){
           reservePrt(node.next);
           System.out.print(node.data+" ");
       }
   }

7. 在不知道头结点的情况下删除指定结点

删除结点的重点在于找出其前结点，使其前结点的指针指向其后结点，即跳过待删除结点，

1、如果待删除的结点是尾结点，由于单链表不知道其前结点，没有办法删除
2、如果删除的结点不是尾结点，则将其该结点的值与下一结点交换，然后该结点的指针指向下一结点的后续结点

public boolean deleteSpecialNode(Node n){
if(n.next == null){
return false;
}else{
//交换结点和其后续结点中的数据
int temp = n.data;
n.data = n.next.data;
n.next.data = temp;
//删除后续结点
n.next = n.next.next;
return true;
}
}

总结：

• 1.单链表主要的有点是，不需要对数据元素的最大个数进行预设，可以无限量地存储数据元素。
• 2.单链表插入和删除时，不需要移动大量的数据元素，可提高效率。

单链表主要的缺点是，每个节点中需要有一个指针，因此单链表的空间利用率略低于顺序表，

循环链表

定义：即首尾相接的链表

结构：尾结点的指针域指向头结点或表的首元结点。

特点：表中所有结点都链接在一个环上

循环单链表和单链表的区别在于，表中最后一个结点不是指向null ，而是改为指向头节点中，从而整个链表形成一个环。