引言（重点）：

1.线性表的概述

2.线性表的抽象数据类型描述

3.线性表的实现方式

4.线性表的具体实现

5.每种具体实现的分析

1、什么是线性表？
线性表（Linear List）：由同类型元素构成有序序列的线性结构。

特征：
1.表中元素个数称为线性表的长度
2.线性表没有元素时，称为空表
3.表起始位置称表头，表结束位置称为表尾
4.在一个元素的前面的元素叫前驱元素，在一个元素后面的元素叫后继元素。

2、线性表的抽象数据类型描述

List MakeEmpty():初始化一个空线性表L;
ElementType FindKth( int K, List L ):根据位序K,返回相应元素 ;
int Find( ElementType X, List L ):在线性表L中查找X的第一次出现位置;
void Insert( ElementType X, int i, List L):在位序i前插入一个新元素X;
void Delete( int i, List L ):删除指定位序i的元素;
int Length( List L ):返回线性表L的长度n。

注意：由于线性表的数据元素之间具有顺序关系，可以为每个元素约定一个序号，因此线性表提供对指定序号元素进行操作的方法。

线性表接口LList：

3、主要实现方式：顺序存储实现和链式存储实现。

4.顺序存储实现——顺序表

5、线性表的顺序存储实现说明
1）.线性表的顺序存储结构：

a1.其数据的存储顺序和逻辑的顺序一样。
（注意：顺序表和数组的关系，一般顺序表需要数组来实现，顺序表的长度需要小于等于数组的长度）

a2.每个元素都有存储地址，设a0的存储地址是Loc（a0），每个元素占用c字节，则ai的存储地址为Loc（ai)=Loc(a0)+i*c
(注意：1、顺序表元素ai的存储地址是它在线性表中位置i的线性函数，与线性表长度无关
2、计算一个元素地址所需的时间是一个常量，与元素位置i无关（即任何一个元素的元素复杂度都为O（l））。
）
a3.顺序表是一种随机存储结构（就是存储的顺序可以跟物理顺序不一样，虽然他们排列的时候一样）。
（注意：顺序表通常是采用数组存储数据元素的，而数组只能赋值，取值操作，不能直接插入等等）

2）.顺序表类（线性表是实在的类，且有几个，我们这边研究的是SepList类，因为其是唯一一个顺序表类。）
假设SepList类表示顺序表，其需要声明实现线性表接口LList，和一般类似于SepList类中有两个私有成员变量element，和len。
elements是一个存放线性表元素的一维数组，元素类型为T，len表示线性表长度，len<=element.length。
（注意：约定线性表中数据元素不能是空对象）



3）.顺序表的插入操作
c1.插入操作的原理：在顺序表元素ai位置上插入元素x，首先必须将元素a0，a1，...，a n-1向后移动，空出一个位置，然后将x插入。
（注意：如果数据已满，再插入的话会数据溢出，解决这个问题的方法是申请一个更大容器的数组
并复制全部的数组元素，这样就扩充了顺序表的容量。）

c2：插入和扩充代码例子：
需要用的方法为：insert（int，T）：在第i个位置上加元素x
append（T）：在顺序表最后插入x对象

public void insert(int i,T x)
{ //插入x作为第i个元素，不能插入null

if(x==null){
return;}//不能添加null

if（this.len==element.length) //如果数组已满，则扩充顺序表容量
{
Object[] a=this.element; //a也引用elements数组，目的就是为了让下面数组增量的时候可以使用其他符号，
//不用this.element.length,从而混淆了我们思路和在后面的步骤中还需要利用原本的信息（包括元素和长度等）。

this.element=new Object[a.length*2] ； //重新申请一个容量更大的数组

for（int j=0;j<a.length;j++）{ //复制数组元素
this.element[j]=a[j]; }


if（i<0) {
i=0; 
}//下标过小，把他调成第一位

if（i>this.len){
i=this.len; }//下标过大，把他调到线性表的最后一位

for（int j=this.len-1;j>=i;j--){ //元素后移，平均移动len/2（注意：往里面移动，从小到大，往外面移动，从大到小）
this.element[j+1]=this.element[j];
}

this.element[i]=x; //把对象x放在指定i的位置上

this.len++;//线性表的长度加1.
}

public void append(T x){
insert(this.len,x);
}//在顺序表最后插入x对象

4）：顺序表的删除操作：
d1.原理：将我们要制定的元素之后一个一个元素往前挪，之后最后一个元素等于null。

d2：删除操作代码例子：
方法：remove（int）
removeAll（）//删除所有的元素
public T remove(int i) //删除角标为i的元素，若操作成功返回被删除元素（对象），否则返回null
{
if(this.len==0||i<0||i>=this.len){
return null; }

T old=(T)this.element[i];//保存被删除元素，以便返回

for（int j=i;j<this.len-1;j++){ //元素前移，平均移动len/2（注意：往里面移动，从小到大，往外面移动，从大到小）
this.element[j]=this.element[j+1];
}

this.element[this.len-1]=null; 
this.len--;
return old;
}

public void removeAll{ this.len=0;} //删除顺序表所有元素

5）.对于顺序表类说明
a.SepList<T>类声明泛型类，类型形式参数T代表线性表元素的数据类型，且T必须是类，不可以是int等等类型 
b.成员变量必须是私有权限
c.默认构造方法（没有构造函数的时候按照其数据类型系统自动初始化）
d.可自动扩充容量（当插入一个元素时，如果数组elements已满，为了能使插入操作正常运行，insert()方法创建一个容量是原数组
2倍的新数组，并将原数组中的元素复制到新数组中）
e.指定元素序号不正确时的操作处理：
e1：方法返回错误信息
e2：抛出异常
（注意：一个空对象调用方法的时候java会抛出空对样异常NullPointerException。）

6）.顺序表操作的效率分析：顺序表的静态特性很好，动态特性很差。
说明：a.顺序表元素的物理存储顺序直接反映线性表元素的逻辑顺序，顺序表是一种随机存取结构。
（顺序表实现了线性表抽象数据类型所要求的基本操作，不仅存取元素ai的时间复杂度是
o（l），而且获得ai的前驱元素和后继元素的时间复杂度也是o（l））
b.插入和删除操作效率低。
（怎么说？b1:每插入或删除一个元素，可能需要移动大量元素，其平均移动次数是顺序表长度的一半。
b2:数组容量不可以更改，存在因容量小造成数据溢出或因容量过大造成内存资源浪费的问题。
）

7）.顺序表的的浅拷贝和深拷贝
a.顺序表的浅拷贝：复制成员变量的值。
注意：浅拷贝构造方法复制数组引用，使得两个对象的elements变量只拥有一个数组，但是在修改，插入，删除
等操作结果不是相互影响的。比如说，a对象删除了第三个数，但b对象他不会知道这个数是被删除的，还
认为它存在，如果输出就会产生错误。
实现：SeqList<String> listb=new SeqList<String>(lista) ; //浅拷贝构造方法

b.顺序表的深拷贝
b1.概念:就是不仅要复制对象的所有基本类型成员变量值，还要重新申请应用类型变量占用的动态存储空间，并复制其中所有对象，这种复制方式称为深拷贝。

b2.代码表现：
public SeqList(SeqList<T> list) //深拷贝方法
{
this.len=list.len;
this.element=new Object[list.element.length]; //申请一个数组
for(int i=0;i<list.element.length;i++) { //复制数组元素，o（n）

this.element[i]=list.element[i]; //对象应用，没有创建新对象；
}
}

b3.关于两者对象的元素改变之间的相互影响：listb.elements申请新的数组空间，使得listb.elements和listb.elements分别引用
一个数组，进行插入，删除等操作，两者不会相互影响。但是由于对象赋值是
引用赋值，导致lista.elements和listb.elements两个数组对应元素引用相同实例，修改其中某个
实例，将同时改变另一个数组元素引用的该实例。
（同一个数组，一个对象改变了，另外对象不知，多个数组，同个实例，其实例改变了，
其余数组的实例也会改变）

8）.比较顺序表是否相等的方法
a.相等需要判断的条件：1先长度相等 2里面的元素相等
b.代码例子：
public boolean equals(Object obj)
{
if(this==obj)
return true;

if(obj instanceof Seqlist)
{
SeqList<T> list=(SeqList<T>)obj;
if(this.length()==list.length())
{
for(int i=0;i<this.length();i++) //比较实际长度的元素，而非数组容量
if(!(this.get(i).equals(list.get(i)))){ //运行时多态
return false; }
return true;
}
}
return false;
}

9）.线性表的应用————使用顺序表类SeqList求解约瑟夫环问题

约瑟夫环运作如下：
1、一群人围在一起坐成环状（如：N）
2、从某个编号开始报数（如：K）
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数
4、一直循环，直到所有人出列，约瑟夫环结束

下面是使用顺序表类SeqList求解约瑟夫环问题的代码：
[java] view plain copy print?
package com.clarck.datastructure.linear; 

/** 
* 使用顺序表类SeqList求解约瑟夫环问题。 
* 
* @author clarck 
* 
*/ 
public class Josephus { 
/** 
* 创建约瑟夫环并求解 
* 
* @param number 
* 参数指定环长度 
* @param start 
* 起始位置 
* @param distance 
* 计数 
*/ 
public Josephus(int number, int start, int distance) { 
// 这是应用，所以先建立表格，并往里面传数据。 
SeqList<String> list = new SeqList<String>(number); 
for (int i = 0; i < number; i++) { 
list.append((char) (‘A‘ + i) + ""); 
} 
System.out 
.print("约瑟夫环(" + number + "," + start + "," + distance + ")，"); 
System.out.println(list.toString());

//之后就是对数据的处理。

int i = start; 
while (list.length() > 1) { 
// 计数按循环规律变化，顺序表可看作是环形结构 
i = (i + distance - 1) % list.length(); 
// 删除指定位置对象 
System.out.print("删除" + list.remove(i).toString() + "，"); 
System.out.println(list.toString()); 
} 
System.out.println("被赦免者是" + list.get(0).toString()); 
} 

public static void main(String args[]) { 
new Josephus(5, 0, 2); 
} 
} 

运行结果如下：
[plain] view plain copy print?
约瑟夫环(5,0,2)，(A, B, C, D, E) 
删除B，(A, C, D, E) 
删除D，(A, C, E) 
删除A，(C, E) 
删除E，(C) 
被赦免者是C

线性表—顺序表