線性表(List)
線性表是最基本、最簡單、也是最常用的一種數據結構。線性表中數據元素之間的關系是一對一的關系,
即除了第一個和最後一個數據元素之外,其它數據元素都是首尾相接的。線性表的邏輯結構簡單,便於
實現和操作。因此,線性表這種數據結構在實際應用中是廣泛采用的一種數據結構。線性表是一種常用
的數據結構,本章介紹線性表及其順序存儲,並對棧和隊列及它們的順序實現給出了詳細的設計描述。
在實際應用中,線性表都是以棧、隊列、字符串、數組等特殊線性表的形式來使用的。由於這些特殊線
性表都具有各自的特性,因此,掌握這些特殊線性表的特性,對於數據運算的可靠性和提高操作效率都
是至關重要的。
線性表是一個線性結構,它是一個含有n≥0個結點的有限序列,對於其中的結點,有且僅有一個開始結
點沒有前驅但有一個後繼結點,有且僅有一個終端結點沒有後繼但有一個前驅結點,其它的結點都有且
僅有一個前驅和一個後繼結點。一般地,一個線性表可以表示成一個線性序列:k1,k2,…,kn,其中k1是
開始結點,kn是終端結點。n就是線性表的長度,當n=0時的線性表就是一個空表。平時我們都看到很多
線性表的實例,如1-100就是一個線性表,表示為(1,2,3,...,100),一個數組或一個數據庫的表也是一
個線性表。注意:線性表是一個數據元素的有序(次序)集
線性結構的基本特征為:
1.集合中必存在唯一的一個“第一元素”;
2.集合中必存在唯一的一個 “最後元素” ;
3.除最後一個元素之外,均有 唯一的後繼(後件);
4.除第一個元素之外,均有 唯一的前驅(前件)。
線性表的接口如下所示:
線性表的基本操作
1、求長度:GetLength()
初始條件:線性表存在;
操作結果:返回線性表中所有數據元素的個數。
2、清空操作:Clear()
初始條件:線性表存在且有數據元素;
操作結果:從線性表中清除所有數據元素,線性表為空。
3、判斷線性表是否為空:IsEmpty()
初始條件:線性表存在;
操作結果:如果線性表為空返回true,否則返回false。
4、附加操作:Append(T item)
初始條件:線性表存在且未滿;
操作結果:將值為item的新元素添加到表的末尾。
5、插入操作:Insert(T item, int i)
初始條件:線性表存在,插入位置正確()(1≤i≤n+1,n為插入前的表長)。
6 、刪除操作: Delete(int i)
初始條件:線性表存在並且線性表不為空。
7、取元素: GetElem(int i)
初始條件:線性表存在並且線性表不為空。
8、按值查找:Locate(T value)
初始條件:線性表存在並且線性表不為空。
線性表具有如下的結構特點:(需要參加這門課程考試的朋友要注意下面二點)
1.均勻性:雖然不同數據表的數據元素可以是各種各樣的,但對於同一線性表的各數據元素必定具有相同的數所類 長度。
2.有序性:各數據元素在線性表中的位置只取決於它們的序與,數據元素之前的相對位置是線性的,即存在唯一的“第一個“和“最後一個“的數據
元素,除了第一個和最後一個外,其它元素前面均只有一個數據元素直接前趨和後面均只有一個數據元素(直接後繼)。
在實現線性表數據元素的存儲方面,一般可用順序存儲結構和鏈式存儲結構兩種方法。鏈式存儲結構將在本網站線性鏈表中介紹,本章主要介紹用數
組實現線性表數據元素的順序存儲及其應用。另外棧.隊列和串也是線性表的特殊情況,又稱為受限的線性結構。
順序表
順序表是在計算機內存中以數組的形式保存的線性表,是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。
線性表采用順序存儲的方式存儲就稱之為順序表。順序表是將表中的結點依次存放在計算機內存中一組地址連
續的存儲單元中。將表中元素一個接一個的存入一組連續的存儲單元中,這種存儲結構是順序結構。采用順序
存儲結構的線性表簡稱為“ 順序表”。順序表的存儲特點是:只要確定了起始位置,表中任一元素的地址都通
過下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤i≤n 其中,L是元素占用存儲單元的長度。
如順序表的每個結點占用len個內存單元,用location (ki)表示順序表中第i個結點ki所占內存空間的第1個單元的地址。
則有如下的關系:
location (ki+1) = location (ki) +len
location (ki) = location(k1) + (i-1)len
存儲結構要體現數據的邏輯結構,順序表的存儲結構中,內存中物理地址相鄰的結點一定具有順序表中的邏輯關系。
構造線性表的類:
public interface IListDS<T>
{
int GetLength();
void Clear();
bool IsEmpty();
bool IsFull();
void Append(T item);
void Insert(T item, int i);
T Delete(int i);
T GetElem(int i);
string Locate(T value);
}
public class TList<T> : IListDS<T>
{
private T[] _list;
private int _len;
private int _lastOne;
public T this[int length]
{
get { return _list[length]; }
set { _list[length] = value; }
}
public