線性表
線性表是線性結(jié)構(gòu)的抽象，線性結(jié)構(gòu)的特點(diǎn)是結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系。
數(shù)據(jù)元素之間的位置關(guān)系是一個(gè)接一個(gè)的排列：
.除第一個(gè)位置的數(shù)據(jù)元素外，其他數(shù)據(jù)元素位置的前面都只有一個(gè)數(shù)據(jù)元素。
.除最后一個(gè)位置的外，其他數(shù)據(jù)元素位置的后面都只有一個(gè)元素。
線性表通常表示為：L=(D,R)
D是數(shù)據(jù)元素的有限集合
R是數(shù)據(jù)元素之間關(guān)系的有限集合
線性表的基本操作：
復(fù)制代碼 代碼如下:
public interface IListDST> {
int GetLength(); //求長(zhǎng)度
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); //按值查找
}
順序表
順序表是線性表的順序存儲(chǔ)(Sequence Storage)，是指在內(nèi)存中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素(Sequence List)，具有隨機(jī)存取的特點(diǎn)。
w: 每個(gè)數(shù)據(jù)元素占w個(gè)存儲(chǔ)單元
A1:順序表的基地址(Base Address)
Loc(Ai)=Loc(A1)+(i-1)*w 1=i=n
為了理解順序表，閃電學(xué)習(xí)了這樣一個(gè)例題，有興趣的朋友可以在自己的機(jī)器上寫一下。
有數(shù)據(jù)類型為整型的順序表La和Lb，其數(shù)據(jù)元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)表Lc，要求Lc中數(shù)據(jù)元素也按升序排列。
算法思路：
依次掃描La和Lb的數(shù)據(jù)元素，比較La和Lb當(dāng)前數(shù)據(jù)元素的值，將較小值的數(shù)據(jù)元素賦給Lc，如此直到一個(gè)順序表被掃描完，然后將未完的那個(gè)順序表中余下的數(shù)據(jù)元素賦給Lc即可。Lc的容量要能夠容納La和Lb兩個(gè)表相加的長(zhǎng)度。
思路圖示：
復(fù)制代碼 代碼如下:
public class SeqListT> : IListDST> {
private int maxsize; //順序表的容量
private T[] data; //數(shù)組，用于存儲(chǔ)順序表中的數(shù)據(jù)元素
private int last; //指示順序表最后一個(gè)元素的位置
//構(gòu)造器
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; }
}
//最后一個(gè)元素的位置屬性
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;
}
//求順序表的長(zhǎng)度
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個(gè)數(shù)據(jù)元素位置插入一個(gè)數(shù)據(jù)元素
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個(gè)數(shù)據(jù)元素
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個(gè)數(shù)據(jù)元素
public T GetElement(int i)
{
if (IsEmpty() || (i 1) || (i > last + 1))
return default(T);
return data[i-1];
}
//在順序表中查找值為value的數(shù)據(jù)元素
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;
}
}
復(fù)制代碼 代碼如下:
public class GenericList
{
public GenericList()
{ }
public SeqListint> Merge(SeqListint> La, SeqListint> Lb)
{
SeqListint> Lc = new SeqListint>(La.Maxsize+Lb.Maxsize);
int i = 0;
int j = 0;
int k = 0;
//兩個(gè)表中元素都不為空
while ((i = (La.GetLength() - 1)) (j = (Lb.GetLength() - 1)))
{
if (La[i] Lb[j])
Lc.Append(La[i++]);
else
Lc.Append(Lb[j++]);
}
//a表中還有數(shù)據(jù)元素
while (i = (La.GetLength() - 1))
Lc.Append(La[i++]);
//b表中還有數(shù)據(jù)元素
while (j = (Lb.GetLength() - 1))
Lc.Append(Lb[j++]);
return Lc;
}
}
客戶端代碼：
復(fù)制代碼 代碼如下:
static void Main(string[] args)
{
SeqListint> sl1 = new SeqListint>(4);
sl1.Append(1);
sl1.Append(3);
sl1.Append(4);
sl1.Append(7);
SeqListint> sl2 = new SeqListint>(6);
sl2.Append(2);
sl2.Append(5);
sl2.Append(6);
sl2.Append(8);
sl2.Append(11);
sl2.Append(14);
GenericList gl = new GenericList();
SeqListint> sl3 = gl.Merge(sl1, sl2);
Console.WriteLine("length:" + sl3.GetLength());
for (int i = 0; i sl3.GetLength(); i++)
{
Console.WriteLine(i + ":" + sl3[i]);
}
}
好了，下一次學(xué)習(xí)鏈表。
作者：LevinLee
您可能感興趣的文章:- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘二 線性結(jié)構(gòu)
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的建立實(shí)例
- Python常見數(shù)據(jù)結(jié)構(gòu)詳解
- python實(shí)現(xiàn)bitmap數(shù)據(jù)結(jié)構(gòu)詳解
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)樹和二叉樹簡(jiǎn)介
- Python中列表、字典、元組、集合數(shù)據(jù)結(jié)構(gòu)整理
- Python實(shí)現(xiàn)基本線性數(shù)據(jù)結(jié)構(gòu)
