線性表(List)是一種線性結構。其特點是數據元素直線的線性關系。
1.線性表抽象類定義
public abstract class AbsList implements Iterable，List{
protected int length;
abstract public T get(int i); //返回第i(i≥0)個元素
abstract public boolean set(int i, T x); //設置第i個元素值為x
//查找，返回首次出現的關鍵字為key元素
abstract public int indexOf(int begin,int end,T o);
abstract public void add(int i, T x); //插入x作為第i個元素
abstract public void clear();
abstract public T remove(int i); //刪除第i個元素并返回被刪除對象
abstract public Iterator iterator();//返回一個迭代器
public boolean isEmpty(){ return length==0;} //判斷線性表是否空
public int length(){ return length;} //返回線性表長度
public void add(T x){ add(length,x); } //在線性表最后插入x元素
public void append(T x){ add(length,x); }
public int indexOf(T o){
return indexOf(0,length,o);
}
public int indexOf(int begin,T o){
return indexOf(begin,length,o);
}
public T remove(T o){ //刪除第i個元素并返回被刪除對象
return remove(indexOf(o));
}
}
1.1初始化：
public Seqlist(int initlen){//initlen初始化容量
if(initlen<0) initlen = 16;
length = 0;
incrementSize = 0;
data = new Object[initlen];
}
//默認構造函數
public Seqlist(){
this(16);
}
//用數組elem初始化順序表
public Seqlist(T[] elem){
length = elem.length;
incrementSize = 0;
data=Arrays.copyOf(elem,length);//將elem全部存入data
}
1.2容量管理
public void setCapacity(int newsize){
data=Arrays.copyOf(data,newsize);
}
//獲取順序表的最大容量
public int getCapacity(){
return data.length;
}
public void setIncr(inc){
incrementSize=inc;
}
//內部使用，順序表自動擴容
private void grow(){
int newsize=data.length+incrementSize;
data=Arrays.copyOf(data.newsize);
}
1.3數據存取
public T get(int i)
{
if(i<0 || i>length - 1)
return null;
return (T)data[i];
}
public boolean set(int i,T x)
{
if(i<0 || i>length - 1)
return false;
else
{
data[i] = x;
return true;
}
}
1.4指定位置插入元素
public void add(int i,T x)
{
if(length == data.length)
grow();
if(i<0)
i = 0;
if(i>length)
i = length;
for(int j=length-1;j>=i;j--)
data[j+1] = data[j];
data[i] = x;
length++;
}
public void add(T x)
{
if(length == data.length)
grow();
data[length] = x;
length++;
}
1.5刪除順序表元素
//刪除下標為i的元素
public T remove(int i)
{
if(i<0 || i>length -1)
throw new IndexOutOfBoundsException("下標越界 i="+i);
T olddata = (T)data[i];
for(int j=i;j
data[j] = data[j+1];
data[--length] = null;
return olddata;
}
//刪除值為o的元素
public T remove(T o)
{
int i =indexOf(o);
return remove(i);
}
//清空順序表
public void clear()
{
for(int i=0;i
remove(i);
}
1.6查找值為o的數據元素的下標,使用順序查找算法
//注意：我們許可查到的是null
public int indexOf(T o)
{
if(o == null)
{
for(int i=0;i
if(data[i] == null)
return i;
}
else
{
for(int i=0;i
if(compare(o,(T)data[i]) == 0)
return i;
}
return -1;
}
1.7順序表中元素有序插入與插入排序
//T數據元素比較方法
protected int compare(T a,T b)
{
if(a instanceof Comparable && b instanceof Comparable)
return ((Comparable) a).compareTo((Comparable)b);
else
return ((String)a).compareTo((String)b);
}
instanceof運算符的前一個操作數是一個引用類型變量，后一個操作數是一個類(接口)，用于判斷前面的對象是否是后面的類，或子類、實現類的實例。若是，返回true；反之，返回false。
如果a,b均是comparable容器已實現的類型，則用comparable直接比較。
否則，轉換為string類比較
//內部使用，有序地插入x
privated void insertOrder(int end,T x)
{
if(length == data.length)
grow();
int k;
for(k=end-1;k>=0;k--)
{
if(compare(x,(T)data[k])<0)
data[k+1] = data[k];
else
break;
}
data[k+1]=x;
}
public void addSort(T x)
{
insertOrder(length,x);
length++;
}
//順序表排序算法
public void sort()
{
for(int i=0;i
insertOrder(i,(T)data[i]);
}
addSort時間復雜度為O(n) sort為
1.8順序表轉換為數組
public Object[] toArray()
{
return Arrays.copyOf(this.data, this.length);
}
public T[] toArray (T[] a)
{
if(a.length
//創建一個與數組a運行類型相同的新數組,長度可以是0
return (T[])Arrays.copyOf(this.data, this.length,a.getClass());
System.arraycopy(this.data, 0, a, 0, this.length);
if(a.length > this.length)
a[length] = null;
return a;
}
1.9順序表轉換為字符串
public String toString()
{
StringBuilder strb = new StringBuilder();
strb = strb.append("(");
for(int i=0;i
{
strb = strb.append(data[i].toString()+",");
}
strb=strb.append(data[length-1]+")");
String s = new String(strb);
strb=null;
return s;
}
2單鏈表的定義及其應用
2.1單鏈表的概念
單鏈表是一個用指向后繼元素的指針將具有線性關系的節點鏈接起來，最后一個節點的后繼指針為空指針。
節點：
class Lnode{
public T data;
public Lnode next;
}
由于節點類由data、next兩部分組成，沒有Comparable中數據類型的實現。故需改寫Comparable中的方法。
節點類新增、改寫幾個方法：equals,comparaTo,toString
public class Lnode implements Comparable> {
public T data;
public Lnode next;
public Lnode(T key){
data = key;
next = null;
}
public Lnode(T key,Lnode next){
data = key;
this.next = next;
}
//重寫的三個方法
public boolean equals (Object e){
@SuppressWarnings("unchecked")
Lnode node =(Lnode)e;
return data.equals(node.data);
}
@SuppressWarnings("unchecked")
public int compareTo(Lnode e) {
Comparable x;
if(data instanceof Comparable){
x = (Comparable)data;
return (int)x.compareTo(e.data);
}
else throw new ClassCastException("類型無法比較");
}
public String toString(){
return data.toString();
}
｝
單鏈表的定義(部分)：
public class LinkList extends AbsList implements Iterable {
Lnode first,last;//頭指針與尾指針
Iterator itr = null;//指向當前節點迭代器的指針
public LinkList(){
first = last = null; length = 0;
this.itr = new LinkIterator();
}
public LinkList(int i){
first = last = null; length = 0;
if(i!=-1)
this.itr = new LinkIterator();
}
private int compare(Lnode a,Lnode b)
{
return a.compareTo(b);
}
public void clear()
{
first=last=null;
length=0;
}
public void removeAll()
{
clear();
}
//...
｝
2.2單鏈表如何存取數據
首先用getNode(i)獲取編號為i節點的引用。
鏈表getNode(i)時間復雜度為O(n)。注意，在順序表中，復雜度為O(1)
獲得引用后，用get(i)取得data值,set(i,x)修改i號節點的值。
protected Lnode getNode(int i)//getNode(i)獲取編號為i節點的引用
{
if(i<0 || i>length-1)
return null;
if(i==0)
return first;
Lnode p= first;
int j=0;
while(p!=null&&j
{
p=p.next;
j++;
}
return p;
}
public T get(int i)//從引用中獲取值
{
Lnode p=getNode(i);
if(p==null)
return null;
else
return p.data;
}
public boolean set(int i,T x)//在引用中修改值
{
Lnode p=getNode(i);
if(p==null)
return false;
else
{
p.data = x;
return true;
}
}
2.3向鏈表中插入元素
s=new Lnode(x)
s是指向新結點的引用變量，x是被插入的值。
分四種情況討論：
1.向空鏈表插入一個新節點
if(first==null){
first = s;//直接將first指向s即可
last = s;
}
2.在鏈表頭結點之前插入新節點
s.next = first; first=s;
3.在鏈表中間插入新節
s.next = p.next; p.next=s;
思考，兩條語句能否調換位置？ 答：不能，p.next=s,此時s未確定,p指向未知位置。
4.在鏈表尾部插入新節點
last.next=s; last=s;
完整的鏈表插入算法:
//注意:i是邏輯位置
public void add(int i,T x)
{
Lnodep,s;
int j = i-1;
s=new Lnode(x,null);
if(first==null||length==0)//1.向空鏈表插入一個新節點
{
first = s; last = s;
}
else if(j<0)//2.在鏈表頭結點之前插入新節點
{
s.next = first; first = s;
}
else if(j>length-1)//4.在鏈表尾部插入新節點
{
last.next =s; last = s;
}
else //3.在鏈表中間插入新節
{
p=getNode(j);
s.next=p.next;
p.next=s;
}
length++;
}
//實際開發中,為方便使用,增加的函數
//重載add
public void add(T key){
add(length,key);
}
public void addBack(T key)
{
add(length,key);
}
public void addFront(T key)
{
add(0,key);
}
2.4刪除鏈表節點
分三種情況處理：
1.刪除的是空鏈表(first==null)
鏈表為空,此時刪除非法。
2.被刪除的是頭結點(i=0)
first = first.next;//即可實現
實際開發中,可能需要被刪除的值,故：
p=first;
first = first.next;
return p.data;
3.被刪除的節點在中間
q.next = p
return p.data
得知要刪除的節點p后,如何準確找到指針q的位置呢
q=getNode(i-1);
完整的刪除算法如下：
public T remove(int i)
{
Lnode p=removeNode(i);
if(p!=null)
return p.data;
else
return null;
}
//刪除邏輯第i節點,返回節點類型
protected Lnode removeNode(int i)
{
Lnode p,q;
if(first == null) return null;//1.刪除的是空鏈表(first==null)
if(i==0)//2.被刪除的是頭結點(i=0)
{
p = first; first = first.next; length--;
return p;
}
if(i>=1&&i<=length-1)//3.被刪除的節點在中間
{
q=getNode(i-1);
p = q.next;
q.next = p.next;
if(p==last)last = q;
length--;
return p;
}
return null;
}
2.5查找節點
//在begin-end中查找節點
public int indexOf(int begin,int end,T key)
{
Lnodep = getNode(begin);
int i = begin;
while(p!=null&i
{
if(p.data.equals(key)) return i;
p = p.next;
i++;
}
return i;
}
//在全鏈表中查找節點
public T search(T key)
{
Lnode p = getNode(0);
while(p!=null)
{
if(p.data.equals(key)) return p.data;
p = p.next;
}
return null;
}
//是否存在值為key的節點
public boolean contains(T key)
{
if(indexOf(key)==-1)
return false;
else
return true;
}
2.5向鏈表中插入有序節點
分四種情況討論
1.鏈表為空
first = s;first.next = null;
2.插入節點s的值小于頭結點
s.next=first;
first=s;//first 指向新節點
3.插入節點s值大于尾節點
last.next=s;
last=s;
4.插入節點處于中間位置
p1=p2=first;
while(p2.next!=null){
if(p1.datas.data){
將節點插入到p1之后;
break;
}else{
p1=p2;p2=p2.next;
}
}
單鏈表有序插入算法:
public void addSort(T x)
{
Lnode s=new Lnode(x,null);
insertOrder(s);
}
//核心算法
public void insertOrder(Lnode s)
{
Lnode p1,p2;
length++;
if(first==null)//鏈表為空
{
first=s;
last=first;
return;
}
if(compare(s,first)<0)//插入到頭結點以前
{
s.next=first;
first=s;
return;
}
if(compare(s,last)>=0)//插入到尾節點
{
last.next=first;
last=s;
return;
}
//插入到中央
p2=first;
p1=p2;
while(p2!=null)
{
if(compare(s,p2)>0)//第一次執行必然s>p2
{
p1=p2;
p2=p2.next;
}
else break;
}
s.next=p2;
p1.next=s;
return;
}
2.6鏈表排序
單鏈表的插入排序示例：
public void sort()
{
LinkList s1=new LinkList();//有序鏈表
Lnode p;
p=this.getNode(0);//取出無序鏈表的頭結點,this是調用這個方法的鏈表
while(p!=null)
{
s1.insertOrder(p);
p=this.getNode(0);
}
this.first=s1.first;
this.last=s1.last;
this.length=s1.length;
}
總結:1.若是要在單鏈表中插入、刪除一個節點，必須知道其前驅結點。
2.單鏈表不具有按序號隨機處理的特點,只能從頭指針一個一個順序進行。
2.7鏈表轉換為字符組/數組
public String toString(Lnode first)
{
String s;
Lnode p;
p =first; s="(";
while(p!=null)
{
s=s+p.data.toString();
p = p.next;
}
return s= s+")\n";
}
public Object[] toArrays()
{
Object[] a=new Object[length];
Lnode p=first;
for(int i=0;i
{
a[i] = p.data;
p=p.next;
}
return a;
}
3.循環鏈表與雙向鏈表
3.1單循環鏈表
具有單鏈表的特征,無需增加額外存儲空間,對鏈表的處理更加靈活,整個鏈表構成一個環, 可以遍歷已經訪問過的元素。
在建立循環鏈表時,必須使最后一個節點的指針指向表頭節點,而不是null。
在判斷是否到表尾是.first==rear,而不是后繼結點為null。
3.2雙向鏈表
class DoubleNode(){
public int data;
public DoubleNode prior;
public DoubleNode next;
}
1.雙鏈表的插入運算
s= new DoubleNode;
s.data=e;
s.next=p.next;
p.next.prior=s;
p.next=s;
s.prior=p;//一定要注意順序
2.雙鏈表的刪除運算
直接斷開節點間鏈接關系
刪除s：
s.prior.next = s.next;
s.next.prior = s.prior;
4.額外補充：順序表與鏈表的比較
一、順序表的特點是邏輯上相鄰的數據元素，物理位置相鄰，
并且，順序表的存儲空間需要預先分配。
它的優點是：
(1)方法簡單，各種高級語言中都有數組，易實現。
(2)不用為表示節點間的邏輯關系而增加額外的存儲開銷。
(3)順序表具有按元素序號隨機訪問的特點。
缺點：
(1)在順序表中做插入、刪除操作時，平均移動表中的一半元素，因此對n較大的順序表效率低。
(2)需要預先分配足夠大的存儲空間(難以估計)，估計過大，可能會導致順序表后部大量閑置；
預先分配過小，又會造成溢出。
二、在鏈表中邏輯上相鄰的數據元素，物理存儲位置不一定相鄰，它使用**指針實現元素之間的
邏輯關系。并且，鏈表的存儲空間是動態分配**的。
鏈表的最大特點是：
插入、刪除運算方便。
缺點：
(1)要占用額外的存儲空間存儲元素之間的關系，存儲密度降低。
存儲密度是指一個節點中數據元素所占的存儲單元和整個節點所占的存儲單元之比。
(2)鏈表不是一種隨機存儲結構，不能隨機存取元素。
三、順序表與鏈表的優缺點切好相反，那么在實踐應用中怎樣選取存儲結構呢？
通常有以下幾點考慮：
(1)“MaxSize”分配，動態？靜態？
當對線性表的長度或存儲規模難以估計時，不宜采用順序表。
當線性表的長度變化不大而且事先容易確定其大小時，為節省存儲空間，
則采用順序表作為存儲結構比較適宜。
(2)基于運算的考慮(時間)
順序存儲是一種隨機存取的結構，而鏈表則是一種順序存取結構，
如果頻繁按序號訪問數據元素，顯然順表優于鏈表。
如果頻繁增刪，顯然鏈表優于順表。
(3)基于環境的考慮(語言)
順序表容易實現，任何高級語言中都有數組類型；
鏈表的操作是基于指針的。相對來講前者簡單些，也用戶考慮的一個因素。
總結： 通常“較穩定”的線性表，即主要操作是查找操作的線性表，適于選擇順序存儲；
而頻繁做插入刪除運算的(即動態性比較強)的線性表適宜選擇鏈式存儲。
不得轉載。
起點)
)
加密解密)
