|
上文對數(shù)據(jù)結(jié)構(gòu)與算法，有了一個簡單的概述與介紹，這篇文章，我們介紹一中典型數(shù)據(jù)結(jié)構(gòu)——線性結(jié)構(gòu)。
什么是線性結(jié)構(gòu)，線性結(jié)構(gòu)是最簡單、最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。線性表是線性結(jié)構(gòu)的抽象(Abstract)， 線性結(jié)構(gòu)的特點(diǎn)是結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的線性關(guān)系。 這
種一對一的關(guān)系指的是數(shù)據(jù)元素之間的位置關(guān)系，即： （1）除第一個位置的數(shù)據(jù)元素外，其它數(shù)據(jù)元素位置的前面都只有一個數(shù)據(jù)元素； （2）除最后一個位置的數(shù)據(jù)元素外，其它數(shù)據(jù)元素位置的后面都只有一個元素。也就是說，數(shù)據(jù)元素是一個接一個的排列。因此，可以把線性結(jié)構(gòu)想象為一種數(shù)據(jù)元素序列的數(shù)據(jù)結(jié)構(gòu)。
線性結(jié)構(gòu)(List)是由 n(n≥0)個相同類型的數(shù)據(jù)元素構(gòu)成的有限序列。對于這個定義應(yīng)該注意兩個概念：一是“有限” ，指的是線性表中的數(shù)據(jù)元素的個數(shù)是有限的，線性表中的每一個數(shù)據(jù)元素都有自己的位置(Position)。本書不討論數(shù)據(jù)元素個數(shù)無限的線性表。二是“相同類型” ，指的是線性表中的數(shù)據(jù)元素都屬于同一種類型。這體現(xiàn)在我們常用的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組，泛型等等他們都是線性結(jié)構(gòu)的。
他們之間的關(guān)系 是：線性表的形式化定義為：線性表(List)簡記為 L，是一個二元組， L = (D, R) 其中：D 是數(shù)據(jù)元素的有限集合。 R 是數(shù)據(jù)元素之間關(guān)系的有限集合。
線性結(jié)構(gòu)的基本操作如下：
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 GetElem(int i); //取表元
int Locate(T value); //按值查找
}
這里為什么是IListDS是與。net自帶IList相區(qū)別。對每個方法解釋如下：
1、求長度：GetLength()
初始條件：線性表存在；
操作結(jié)果：返回線性表中所有數(shù)據(jù)元素的個數(shù)。
2、清空操作：Clear()
初始條件：線性表存在且有數(shù)據(jù)元素；
操作結(jié)果：從線性表中清除所有數(shù)據(jù)元素，線性表為空。
3、判斷線性表是否為空：IsEmpty()
初始條件：線性表存在；
操作結(jié)果：如果線性表為空返回 true，否則返回 false。
4、附加操作：Append(T item)
初始條件：線性表存在且未滿；
操作結(jié)果：將值為 item 的新元素添加到表的末尾。
5、插入操作：Insert(T item, int i)
初始條件：線性表存在，插入位置正確()(1≤i≤n+1,n 為插入前的表長)。
操作結(jié)果：在線性表的第 i 個位置上插入一個值為 item 的新元素，這樣使得原序號為 i,i+1,…,n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2,…,n+1，插入后表長=原表長+1。
6、刪除操作：Delete(int i)
初始條件：線性表存在且不為空，刪除位置正確(1≤i≤n,n 為刪除前的表長)。
操作結(jié)果：在線性表中刪除序號為 i 的數(shù)據(jù)元素，返回刪除后的數(shù)據(jù)元素。刪除后使原序號為 i+1,i+2,…,n 的數(shù)據(jù)元素的序號變?yōu)?i,i+1,…,n-1，刪除后表長=原表長-1。
7、取表元：GetElem(int i)
初始條件：線性表存在，所取數(shù)據(jù)元素位置正確（1≤i≤n，n 為線性表的表長） ； 操作結(jié)果：返回線性表中第 i 個數(shù)據(jù)元素。
8、按值查找：Locate(T value)
初始條件：線性表存在。
操作結(jié)果：在線性表中查找值為 value 的數(shù)據(jù)元素，其結(jié)果返回在線性表中首次出現(xiàn)的值為 value 的數(shù)據(jù)元素的序號，稱為查找成功；否則，在線性表中未找到值為 value 的數(shù)據(jù)元素，返回一個特殊值表示查找失敗。
先看最簡單的線性結(jié)構(gòu)——順序表
什么是順序表，線性結(jié)構(gòu)的順序存儲是指在內(nèi)存中用一塊地址連續(xù)的空間依次存放線性表的數(shù)據(jù)元素，用這種方式存儲的線性就叫順序表(Sequence List)。
順序表儲存結(jié)構(gòu)如圖所示
假設(shè)順序表中的每個數(shù)據(jù)元素占w個存儲單元， 設(shè)第i個數(shù)據(jù)元素的存儲地址為Loc(ai)，則有： Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n 式中的Loc(a1)表示第一個數(shù)據(jù)元素a1的存儲地址，也是順序表的起始存儲地址，稱為順序表的基地址(Base Address). 這里我們舉個例子吧，比如你去酒店的時候，知道101號房間的基準(zhǔn)的位置，你要去111號房間，你知道每個房間之間的距離是5，那里只需要前進(jìn)50米。順序表的地址運(yùn)算就這么簡單。
而順序表是繼承與線性結(jié)構(gòu)，他的源代碼又是這個樣子的。
public class SeqList<T> : IListDS<T> {
private int maxsize; //順序表的容量 順序表的最大容量
private T[] data; //數(shù)組，用于存儲順序表中的數(shù)據(jù)元素 用于存儲順序表的結(jié)構(gòu)
private int last; //指示順序表最后一個元素的位置
//索引器
public T this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}
//最后一個數(shù)據(jù)元素位置屬性
public int Last
{
get
{
return last;
}
}
//容量屬性
public int Maxsize
{
get
{
return maxsize;
}
set
{
maxsize = value;
}
}
//構(gòu)造器 進(jìn)行函數(shù)初始化工作
public SeqList(int size)
{
data = new T[size];
maxsize = size;
last = -1;
}
//求順序表的長度
public int GetLength()
{
return last+1;
}
//清空順序表
//清除順序表中的數(shù)據(jù)元素是使順序表為空，此時，last 等于-1。
public void Clear()
{
last = -1;
}
//判斷順序表是否為空
//如果順序表的 last 為-1，則順序表為空，返回 true，否則返回 false。
public bool IsEmpty()
{
if (last == -1)
{
return true;
}
else
{
return false;
}
}
//判斷順序表是否為滿
//如果順序表為滿，last 等于 maxsize-1，則返回 true，否則返回 false。
public bool IsFull()
{
if (last == maxsize-1)
{
return true;
}
else
{
return false;
}
}
//附加操作是在順序表未滿的情況下，在表的末端添加一個新元素，然后使順序表的last加1。
//在順序表的末尾添加新元素
public void Append(T item)
{
if(IsFull())
{
Console.WriteLine("List is full");
return;
}
data[++last] = item;
}
//順序表的插入是指在順序表的第i個位置插入一個值為item的新元素， 插入后使 原 表 長 為 n 的 表 (a1,a2, … ,ai-1,ai,ai+1, … ,an) 成 為 表 長 為 n+1 的 表(a1,a2,…,ai-1,item,ai,ai+1,…,an)。i的取值范圍為 1≤i≤n+1，i為n+1 時，表示在順序表的末尾插入數(shù)據(jù)元素。 順序表上插入一個數(shù)據(jù)元素的步驟如下：
//（1）判斷順序表是否已滿和插入的位置是否正確，表滿或插入的位置不正確不能插入；
//（2）如果表未滿和插入的位置正確，則將an～ai依次向后移動，為新的數(shù)據(jù)元素空出位置。在算法中用循環(huán)來實現(xiàn)；
//（3）將新的數(shù)據(jù)元素插入到空出的第 i 個位置上；
//（4）修改 last（相當(dāng)于修改表長） ，使它仍指向順序表的最后一個數(shù)據(jù)元素。
//在順序表的第i個數(shù)據(jù)元素的位置插入一個數(shù)據(jù)元素
public void Insert(T item, int i)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}
if(i<1 | i>last+2)
{
Console.WriteLine("Position is error!");
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;
}
算法的時間復(fù)雜度分析：順序表上的插入操作，時間主要消耗在數(shù)據(jù)的移動上， 在第i個位置插入一個元素， 從ai到an都要向后移動一個位置， 共需要移動n-i+1
個元素，而i的取值范圍為 1≤i≤n+1，當(dāng)i等于 1 時，需要移動的元素個數(shù)最多，為n個；當(dāng)i為n+1 時，不需要移動元素。設(shè)在第i個位置做插入的概率為pi，則平
均移動數(shù)據(jù)元素的次數(shù)為n/2。這說明：在順序表上做插入操作平均需要移動表中一半的數(shù)據(jù)元素，所以，插入操作的時間復(fù)雜度為O（n） 。
//順序表的刪除操作是指將表中第i個數(shù)據(jù)元素從順序表中刪除， 刪除后使原表長 為 n 的 表 (a1,a2, … ,ai-1,ai, ai+1, … ,an) 變 為 表 長 為 n-1的 表(a1,a2,…,ai-1,ai+1,…,an)。i的取值范圍為 1≤i≤n，i為n時，表示刪除順序表末尾的數(shù)據(jù)元素。
順序表上刪除一個數(shù)據(jù)元素的步驟如下：
（1）判斷順序表是否為空和刪除的位置是否正確，表空或刪除的位置不正
確不能刪除；
（2）如果表未空和刪除的位置正確，則將ai+1～an依次向前移動。在算法中
用循環(huán)來實現(xiàn)；
（3）修改 last（相當(dāng)于修改表長） ，使它仍指向順序表的最后一個元素。
//刪除順序表的第i個數(shù)據(jù)元素
public T Delete(int i)
{
T tmp = default(T);
if (IsEmpty())
{
Console.WriteLine("List is empty");
return tmp;
}
if (i < 1 | i > last+1)
{
Console.WriteLine("Position is error!");
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;
}
算法的時間復(fù)雜度分析：順序表上的刪除操作與插入操作一樣，時間主要消耗在數(shù)據(jù)的移動上。在第i個位置刪除一個元素，從ai+1到an都要向前移動一個位置，共需要移動n-i個元素，而i的取值范圍為 1≤i≤n，當(dāng)i等于 1 時，需要移動的元素個數(shù)最多，為n-1 個；當(dāng)i為n時，不需要移動元素。設(shè)在第i個位置做刪除的概率為pi，則平均移動數(shù)據(jù)元素的次數(shù)為(n-1)/2。這說明在順序表上做刪除操作平均需要移動表中一半的數(shù)據(jù)元素，所以，刪除操作的時間復(fù)雜度為O（n） 。
//取表元運(yùn)算是返回順序表中第 i 個數(shù)據(jù)元素，i 的取值范圍是 1≤i≤last+1。由于表是隨機(jī)存取的，所以，如果 i 的取值正確，則取表元運(yùn)算的時間復(fù)雜度為O（1） 。
//獲得順序表的第i個數(shù)據(jù)元素
public T GetElem(int i)
{
if (IsEmpty() | | (i<1) | | (i>last+1))
{
Console.WriteLine("List is empty or Position is error!");
return default(T);
}
return data[i-1];
}
//順序表中的按值查找是指在表中查找滿足給定值的數(shù)據(jù)元素。 在順序表中完成該運(yùn)算最簡單的方法是：從第一個元素起依次與給定值比較，如果找到，則返回在順序表中首次出現(xiàn)與給定值相等的數(shù)據(jù)元素的序號，稱為查找成功；否則，在順序表中沒有與給定值匹配的數(shù)據(jù)元素，返回一個特殊值表示查找失敗。
//在順序表中查找值為value的數(shù)據(jù)元素
public int Locate(T value)
{
if(IsEmpty())
{
Console.WriteLine("List is Empty!");
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ù)雜度分析：順序表中的按值查找的主要運(yùn)算是比較，比較的次數(shù)與給定值在表中的位置和表長有關(guān)。當(dāng)給定值與第一個數(shù)據(jù)元素相等時，比較次數(shù)為 1；而當(dāng)給定值與最后一個元素相等時，比較次數(shù)為 n。所以，平均比較次數(shù)為(n+1)/2，時間復(fù)雜度為 O（n） 。
如：已知順序表 L，寫一算法將其倒置，即實現(xiàn)如圖 2.4 所示的操作，其中(a)為倒置前，(b)為倒置后。
我思考的思路就是以所在的中間數(shù)進(jìn)行前后調(diào)換。相應(yīng)的源代碼如下：
public void ReversSeqList(SeqList<int> L)
{
int tmp = 0;
int len = L.GetLength();
for (int i = 0; i<= len/2; ++i)
{
tmp = L[i];
L[i] = L[len - i];
L[len - i] = tmp;
}
}
該算法只是對順序表中的數(shù)據(jù)元素順序掃描一遍即完成了倒置， 所以時間復(fù)雜度為 O(n)。其中運(yùn)行效果如圖所示：
還譬如，我就我開發(fā)親身經(jīng)歷而言 在俄羅斯方塊這個項目中，我的順序結(jié)構(gòu)用的確實很多譬如初始化過程中。
// 初始化形狀集合，共七種形狀
_pieces = new List<PieceBase> { new I(), new L(), new I2(), new L2(), new N(), new N2(), new O(), new T() };
// 初始化方塊容器（用 Block 對象填滿整個容器）
Container = new Block[_rows, _columns];
for (int i = 0; i < _rows; i++)
{
for (int j = 0; j < _columns; j++)
{
var block = new Block();
block.Top = i * block.rectangle.ActualHeight;
block.Left = j * block.rectangle.ActualWidth;
block.Color = null;
Container[i, j] = block;
}
}
// 初始化下一個形狀的容器（用 Block 對象將其填滿）
NextContainer = new Block[4, 4];
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
var block = new Block();
block.Top = i * block.rectangle.ActualHeight;
block.Left = j * block.rectangle.ActualWidth;
block.Color = null;
NextContainer[i, j] = block;
}
}
// 創(chuàng)建一個新的形狀
CreatePiece();
// 呈現(xiàn)當(dāng)前創(chuàng)建出的形狀
AddPiece(0, 0);
// Timer 用于定時向下移動形狀
_timer = new DispatcherTimer();
_timer.Interval = TimeSpan.FromMilliseconds(_initSpeed);
_timer.Tick += _timer_Tick;
GameStatus = GameStatus.Ready;
你看看我用的初始化方塊容器，這個容器是二維數(shù)組，這就是一種明顯的順序表。將他top位置，left位置賦值，進(jìn)行一系列初始化工作。這就等同于順序表初始化操作。這個算法的復(fù)雜度為O（n2）。
本文中，我們討論了什么是線性結(jié)構(gòu)，線性結(jié)構(gòu)有哪些特點(diǎn)，并且詳細(xì)介紹了一個最簡單線性結(jié)構(gòu)順序表，并且通過源代碼對她進(jìn)行一些列的分析，最后還舉了兩個例子，讓我們更好的理解順序表。
|
