線性表 

線性表是線性結構的抽象，線性結構的特點是結構中的數據元素之間存在一對一的線性關系。 
數據元素之間的位置關系是一個接一個的排列： 
.除第一個位置的數據元素外，其他數據元素位置的前面都只有一個數據元素。 
.除最后一個位置的外，其他數據元素位置的后面都只有一個元素。 
線性表通常表示為：L=(D,R) 
D是數據元素的有限集合 
R是數據元素之間關系的有限集合 

線性表的基本操作： 

復制代碼代碼如下:

public interface IListDS<T> { 
int GetLength(); //求長度 
void Clear(); //清空 
bool IsEmpty(); //判空 
void Append(T item); //附加 
void Insert(T item, int i); //插入 
T Delete(int i); //刪除 
T GetElement(int i); //取表元素 
int Locate(T value); //按值查找 
} 

順序表 

順序表是線性表的順序存儲(Sequence Storage)，是指在內存中用一塊地址連續的空間依次存放線性表的數據元素(Sequence List)，具有隨機存取的特點。 

w: 每個數據元素占w個存儲單元 
A1:順序表的基地址(Base Address) 
Loc(Ai)=Loc(A1)+(i-1)*w 1<=i<=n 

為了理解順序表，閃電學習了這樣一個例題，有興趣的朋友可以在自己的機器上寫一下。 
有數據類型為整型的順序表La和Lb，其數據元素均按從小到大的升序排列，編寫一個算法將它們合并成一個表Lc，要求Lc中數據元素也按升序排列。 
算法思路： 
依次掃描La和Lb的數據元素，比較La和Lb當前數據元素的值，將較小值的數據元素賦給Lc，如此直到一個順序表被掃描完，然后將未完的那個順序表中余下的數據元素賦給Lc即可。Lc的容量要能夠容納La和Lb兩個表相加的長度。 
思路圖示： 

復制代碼代碼如下:

public class SeqList<T> : IListDS<T> { 
private int maxsize; //順序表的容量 
private T[] data; //數組，用于存儲順序表中的數據元素 
private int last; //指示順序表最后一個元素的位置 

//構造器 
public SeqList(int size) 
{ 
data = new T[size]; 
maxsize = size; 
last = -1; //如果順序表為空，last=-1 
} 
//索引器 
public T this[int index] 
{ 
get { return data[index]; } 
set { data[index] = value; } 
} 
//最后一個元素的位置屬性 
public int Last 
{ 
get { return last; } 
} 
//容量屬性 
public int Maxsize 
{ 
get { return maxsize; } 
set { maxsize = value; } 
} 
//判斷順序表是否為空 
public bool IsEmpty() 
{ 
if (last == -1) 
return true; 
else 
return false; 
} 
//判斷順序表是否為滿 
public bool IsFull() 
{ 
if (last == maxsize - 1) 
return true; 
else 
return false; 
} 
//求順序表的長度 
public int GetLength() 
{ 
return last + 1; 
} 
//清空順序表 
public void Clear() 
{ 
last = -1; 
} 
//在順序表末尾添加新元素 
public void Append(T item) 
{ 
if (IsFull()) 
{ 
Console.WriteLine("List is full."); 
return; 
} 
data[++last] = item; 
} 

//在順序表第i個數據元素位置插入一個數據元素 
public void Insert(T item, int i) 
{ 
if (IsFull()) 
return; 
if (i < 1 || i > last + 2) 
return; 
if (i == last + 2) 
data[last + 1] = item; 
else 
{ 
for (int j = last; j >= i - 1; --j) 
{ 
data[j + 1] = data[j]; 
} 
data[i - 1] = item; 
} 
++last; 
} 
//刪除順序表的第i個數據元素 
public T Delete(int i) 
{ 
T tmp = default(T); 
if (IsEmpty()) 
return tmp; 
if (i < 1 || i > last + 1) 
return tmp; 
if (i == last + 1) 
tmp = data[last--]; 
else 
{ 
tmp = data[i - 1]; 
for (int j = i; j <= last; ++j) 
data[j] = data[j + 1]; 
} 
--last; 
return tmp; 
} 
//獲得順序表的第i個數據元素 
public T GetElement(int i) 
{ 
if (IsEmpty() || (i < 1) || (i > last + 1)) 
return default(T); 
return data[i-1]; 
} 
//在順序表中查找值為value的數據元素 
public int Locate(T value) 
{ 
if (IsEmpty()) 
return -1; 
int i = 0; 
for (i = 0; i <= last; ++i) 
{ 
if (value.Equals(data[i])) 
break; 
} 
if (i > last) 
return -1; 
return i; 
} 
}

復制代碼代碼如下:

public class GenericList 
{ 
public GenericList() 
{ } 
public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb) 
{ 
SeqList<int> Lc = new SeqList<int>(La.Maxsize+Lb.Maxsize); 
int i = 0; 
int j = 0; 
int k = 0; 
//兩個表中元素都不為空 
while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1))) 
{ 
if (La[i] < Lb[j]) 
Lc.Append(La[i++]); 
else 
Lc.Append(Lb[j++]); 
} 
//a表中還有數據元素 
while (i <= (La.GetLength() - 1)) 
Lc.Append(La[i++]); 
//b表中還有數據元素 
while (j <= (Lb.GetLength() - 1)) 
Lc.Append(Lb[j++]); 
return Lc; 
} 
} 

客戶端代碼： 

復制代碼代碼如下:

static void Main(string[] args) 
{ 
SeqList<int> sl1 = new SeqList<int>(4); 
sl1.Append(1); 
sl1.Append(3); 
sl1.Append(4); 
sl1.Append(7); 
SeqList<int> sl2 = new SeqList<int>(6); 
sl2.Append(2); 
sl2.Append(5); 
sl2.Append(6); 
sl2.Append(8); 
sl2.Append(11); 
sl2.Append(14); 
GenericList gl = new GenericList(); 
SeqList<int> sl3 = gl.Merge(sl1, sl2); 
Console.WriteLine("length:" + sl3.GetLength()); 
for (int i = 0; i < sl3.GetLength(); i++) 
{ 
Console.WriteLine(i + ":" + sl3[i]); 
} 
} 

好了，下一次學習鏈表。 
作者：LevinLee