數據構造簡明備忘錄 線性表。本站提示廣大學習愛好者：（數據構造簡明備忘錄 線性表）文章只能為提供參考，不一定能成為您想要的結果。以下是數據構造簡明備忘錄 線性表正文
線性表
線性表是線性構造的籠統，線性構造的特色是構造中的數據元素之間存在一對一的線性關系。
數據元素之間的地位關系是一個接一個的分列：
.除第一個地位的數據元素外，其他數據元素地位的後面都只要一個數據元素。
.除最初一個地位的外，其他數據元素地位的前面都只要一個元素。
線性表平日表現為：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
