1、我們將實現一個順序存儲結構
經典的C語言描述的線性表順序存儲結構通常使用數組來實現的，下面我們也將用數組來實現。我們將實現線性表的增刪改查的功能。
順序存儲結構操作的要點和難點其實就是數組的批量移動。因為在數組描述的順序表中，刪除操作，需要將從待刪除元素的位置之后的所有元素都往前移動一位；而插入操作，需要將待插入元素的位置，包括原先在該位置的元素及其后面的元素都往前移動一位。而實現刪除和插入元素的重點就在于計算出要移動多少元素和從什么位置開始移動。計算要移動多少元素通常用順序表的長度-要移動的位置。從什么位置開始移動，通常由要插入（或刪除）的位置進行一些簡單的計算。具體的實現如下所示。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
public class SqList
{
const int MAX_LENTH = 100; //定義線性表的存儲空間大小
public int Lenth; //線性表的長度,我們將通過線性表的長度判斷線性表是否為空，通過Lenth存取線性表
public int[] data = new int[MAX_LENTH];
public int GetLength() //求長度
{
return this.Lenth;
}
public void Clear()//清空操作
{
//長度設置為0
this.Lenth = 0;
}
public bool IsEmpty()//判斷線性表是否為空
{
//這里通過判斷線性表的長度
return Lenth == 0 ? true : false;
}
/// <summary>
/// 將元素附加到最后一個位置
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
public States Append(int item) //
{
if (this.Lenth + 1 == MAX_LENTH)
{
return States.Fail;
}
data[this.Lenth] = item;
this.Lenth++;
return States.Success;
}
/// <summary>
/// 插入操作
/// </summary>
/// <param name="item">值</param>
/// <param name="i">位置</param>
public States Insert(int item, int index)//插入操作
{
//異常檢查
if (index < 0 || index > this.Lenth) return States.Fail;//檢查插入的位置
if (this.Lenth + 1 > MAX_LENTH) return States.Fail; //檢查數組是否會溢出
//假設線性表中有三個元素0,1,2。當將item=3插入1的位置的時候，1,2各往后移動一位，
//item=3插入到原來1的位置
if (index == this.Lenth)
{
data[this.Lenth] = item;
this.Lenth++;
return States.Success;
}
int move = this.Lenth - index;
int NextPosition;
NextPosition = this.Lenth - 1;
for (int i = 0; i < move; i++)
{ //將index之后的元素全部往后移一位
data[NextPosition + 1] = data[NextPosition];
NextPosition--;
}
data[index] = item;
this.Lenth++;
//將item插入位置
return States.Success;
}
/// <summary>
/// 刪除元素并返回元素的值
/// </summary>
/// <param name="index"></param>
/// <param name="states"></param>
/// <returns></returns>
public int Delete(int index, out States states)//刪除操作
{
//異常檢查
if (index < 0 || index > this.Lenth)
{
states = States.Fail;//檢查插入的位置
return 0;
}
if (this.Lenth == 0)//檢查是否有值可以被刪除
{
states = States.Fail;
return 0;
}
int iDataToDel = data[index];
if (index == this.Lenth - 1) //如果正好是最后一個元素，則不需要移動
{
this.Lenth--;
states = States.Success;
return iDataToDel;
}
int PositionToMove = index + 1;//要開始往前移動的位置
//(1)要移動多少元素
int iMove = this.Lenth - PositionToMove;
//(2)循環移動元素
for (int i = 0; i < iMove; i++)
{
data[PositionToMove - 1 + i] = data[PositionToMove + i];
}
//(3)長度-1
this.Lenth--;
//(4)返回要刪除的元素
states = States.Success;
return iDataToDel;
}
public int GetElem(int i)
{ //取表中的元素
return this.data[i];
}
/// <summary>
/// 返回查找到的第一個位置
/// </summary>
/// <param name="value"></param>
/// <param name="states"></param>
/// <returns></returns>
public int Locate(int value, out States states)
{ //按值查找
for (int i = 0; i < this.Lenth; i++)
{
if (value == data[i])
{
states = States.Success;
return i;
}
}
states = States.Fail;
return 0;
}
}
//定義一個用來指示操作是否成功的枚舉量
public enum States
{
Success,
Fail
}
}
2、使用C#特有的語法來實現經典順序存儲結構
下面，我們將對以上實現的順序存儲線性表用C#特有的語法進行改造。主要的改造如下：
1、使用模板template抽象線性表元素的類型；
2、使用索引器簡化元素的訪問；
3、使用屬性代替特定的方法。
為了保持兩邊方法簽名的一致性，我們利用vs2010中提取接口的功能將相關的方法提取為接口
圖1 提取接口
提取后的接口，如下所示
using System;
namespace DataStructure
{
interface ISqList
{
States Append(int item);
void Clear();
int Delete(int index, out States states);
int GetElem(int i);
int GetLength();
States Insert(int item, int index);
bool IsEmpty();
int Locate(int value, out States states);
}
}
為了讓我們的線性表能夠適應不同的元素類型，我們稍微改變一下接口的聲明。我們所需要做的只是將具體的元素類型使用模板進行填充，如下所示。有變化的部分都用灰色背景進行標識。
using System;
namespace DataStructure
{
interface ISqList<T>
{
States Append(T item);
void Clear();
T Delete(int index, out States states);
T GetElem(int i);
int GetLength();
States Insert(T item, int index);
bool IsEmpty();
int Locate(T value, out States states);
}
}
我們遵循著前面提到的3個改造將經典的順序表改造得更C#，詳見以下代碼
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class AD_Sqlist<T> : ISqList<T>
{
const int MAX_LENTH = 100;//定義線性表的存儲空間大小
public T[] data = new T[MAX_LENTH];
private int lenth;
/// <summary>
/// 線性表的長度
/// </summary>
public int Lenth
{
get { return lenth; }
set { lenth = value; }
}
/// <summary>
/// 判斷線性表是否已滿
/// </summary>
public bool IsFull
{
get
{
if (Lenth + 1 > MAX_LENTH)
{
return true;
}
else
{
return false;
}
}
}
public States Append(T item)
{
if (IsFull == true)
{
return States.Fail;
}
data[this.Lenth] = item;
return States.Success;
}
public void Clear()
{
this.Lenth = 0;
}
public T Delete(int index, out States states)
{
if (Lenth == 0)
{
states = States.Fail;
return default(T);
}
if (index >= this.Lenth)
{
states = States.Fail;
return default(T);
}
//(1)要移動多少位
int move = this.Lenth - 1 - index;
//(2)從哪一位開始移動
int position = index + 1;
T dataToDel = data[index];//將要被刪除的元素
//(3)將所有元素都批量往前移動
for (int i = 0; i < move; i++)
{
data[position - 1] = data[position];
position++;
}
Lenth--;
//(4)返回被刪除的元素
states = States.Success;
return dataToDel;
}
public T GetElem(int i)
{
if (i < 0 || i >= this.Lenth)
{
return default(T);
}
return this.data[i];
}
public T this[int i]
{
get
{
if (i < 0 || i >= this.Lenth)
{
return default(T);
}
return this.data[i];
}
}
public int GetLength()
{
return this.Lenth;
}
public States Insert(T item, int index)
{
//(1)線性表是否已滿
if (IsFull == true)
{
return States.Fail;
}
//(2)插入的位置是否正確
if (index < 0 || index > this.Lenth)
{
return States.Fail;
}
if (index == this.Lenth)
{
data[index] = item;
this.Lenth++;
return States.Success;
}
//(3)將要移動的個數
int move = this.Lenth - 1 - index;
//（4）準備移動的位置
int position = this.Lenth - 1;
//(5)批量移動
for (int i = 0; i <= move; i++)
{
this.data[position + 1] = this.data[position];
position--;
}
this.data[index] = item;
//(6)返回
this.Lenth++;
return States.Success;
}
public bool IsEmpty()
{
if (this.Lenth == 0)
{
return true;
}
else
{
return false;
}
}
public int Locate(T value, out States states)
{
if (IsEmpty() == true)
{
states = States.Fail;
return 0;
}
else
{
for (int i = 0; i < this.Lenth; i++)
{
if (this.data[i].Equals(value))
{
states = States.Success;
return i;
}
}
}
states = States.Fail;
return 0;
}
}
}
文章列表
留言列表
