using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace DataStructure
{
class MySequenceList<T> : MyIList<T>
{
private int MAX;
private T[] data;
private int last;
/// <summary>
/// 构造函数
/// </summary>
/// <param name="max"></param>
public MySequenceList(int max)
{
this.MAX = max;
data = new T[MAX];
last = -1;
}
/// <summary>
/// 判断线性表是否为空
/// 如果顺序表的last为-1，则顺序表为空，返回true，否则返回false。
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (last == -1)
{
return true;
}
else
return false;
}
/// <summary>
/// 附加操作
/// 附加操作是在顺序表未满的情况下，在表的末端添加一个新元素，然后使顺序表的last加1。
/// </summary>
/// <returns>附加是否成功</returns>
public bool Append(T t)
{
if (IsFull())
{
Console.WriteLine("Append Failed.It is Full!");
return false;
}
else
{
last++;
data[last] = t;
return true;
}
}
/// <summary>
/// 判断顺序表是否为满
/// 如果顺序表为满，last等于maxsize-1，则返回true，否则返回false。
/// </summary>
/// <returns></returns>
public bool IsFull()
{
if (last == MAX - 1)
return true;
return false;
}
/// <summary>
/// 求顺序表的长度
/// 由于数组是0基数组，即数组的最小索引为0，所以，顺序表的长度就是数组中最后一个元素的索引last加1。
/// </summary>
/// <returns></returns>
public int GetLength()
{
return last+1;
}
/// <summary>
/// 打印顺序表
/// </summary>
public void PrintSqL()
{
if (IsEmpty())
{
Console.WriteLine("The SquenceList is Empty!");
return;
}
for (int i = 0; i <= last+1; i++)
{
Console.WriteLine(data[i]);
}
}
/// <summary>
/// 清空操作
/// 清除顺序表中的数据元素是使顺序表为空，此时，last等于-1。
/// </summary>
public void Clear()
{
//data = new T[MAX];在教程上没有这一行，但是我认为不对！
data = new T[MAX];
last = -1;
}
/// <summary>
/// 插入操作
/// 顺序表的插入是指在顺序表的第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时，表示在顺序表的末尾插入数据元素。
/// （1）判断顺序表是否已满和插入的位置是否正确，表满或插入的位置不正确不能插入；
/// （2）如果表未满和插入的位置正确，则将an～ai依次向后移动，为新的数据元素空出位置。在算法中用循环来实现；
/// （3）将新的数据元素插入到空出的第i个位置上；
/// （4）修改last（相当于修改表长），使它仍指向顺序表的最后一个数据元素。
/// </summary>
/// <param name="t"></param>
/// <param name="i"></param>
public void Insert(T t,int index)
{
if (IsFull())
{
Console.WriteLine("Insert Failed.It is Full!");
}
else
{
//判断插入的位置是否正确，
// i小于1表示在第1个位置之前插入，
// i大于last+2表示在最后一个元素后面的第2个位置插入。
if (index < 1 || index > last + 2)
{
Console.WriteLine("Insert Failed.Position Error!");
return;
}
//last+1是该表最后一项的index
//last+2相当于加到表尾上面
if (index == last + 2)
{
data[last + 1] = t;
}
else
{
for (int i = last; i >= index - 1; i--)
{
data[i + 1] = data[i];
}
data[index - 1] = t;
}
last++;
}
}
/// <summary>
/// 删除操作
/// 顺序表的删除操作是指将表中第i个数据元素从顺序表中删除，删除后使原表长为n的表(a1,a2,…,ai-1,ai, ai+1,…,an)变为表长为n-1的表(a1,a2,…,ai-1,ai+1,…,an)。i的取值范围为1≤i≤n，i为n时，表示删除顺序表末尾的数据元素。
/// （1）判断顺序表是否为空和删除的位置是否正确，表空或删除的位置不正确不能删除；
/// （2）如果表未空和删除的位置正确，则将ai+1～an依次向前移动。在算法中用循环来实现；
/// （3）修改last（相当于修改表长），使它仍指向顺序表的最后一个元素。
/// </summary>
/// <param name="index">试图删除第几个元素</param>
/// <returns>是否删除成功</returns>
public bool Delete(int index)
{
if (IsEmpty())
{
Console.WriteLine("There is no item to delete!");
return false;
}
//判断删除的位置是否正确
// i小于1表示删除第1个位置之前的元素，
// i大于last+1表示删除最后一个元素后面的第1个位置的元素。
if (index < 1 || index > last + 1)
{
Console.WriteLine("Position is wrong!");
return false;
}
else
{
//同样适用于index=last+1
//相当于data[last]=defautl(T);
for (int i = index - 1; i <= last; i++)
{
data[i] = data[i + 1];
}
last--;
return true;
#region 推荐这样写，更有逻辑一点
////删除的是最后一个元素
//if (i == last + 1)
//{
// tmp = data[last--];
// return tmp;
//}
//else //删除的不是最后一个元素
//{
// //元素移动
// tmp = data[i - 1];
// for (int j = i; j <= last; ++j)
// {
// data[j] = data[j + 1];
// }
//}
#endregion
}
}
/// <summary>
/// 取表元
/// 取表元运算是返回顺序表中第i个数据元素，i的取值范围是1≤i≤last+1。由于表是随机存取的，所以，如果i的取值正确，则取表元运算的时间复杂度为O（1）。
/// </summary>
/// <param name="index">取第几个元素</param>
/// <returns>获得这个元素</returns>
public T GetItem(int index)
{
//象这种表问题，首先要判断是否为空？是否为满？
if (IsEmpty())
{
Console.WriteLine("SquenceList is Empty!No Item to Get!");
//default(T) Obtain default value of type T
return default(T);
}
//然后判断参数的定义域是否符合条件
if (index < 1 || index > last + 1)
{
Console.WriteLine("GetItem Failed!Position Error");
return default(T);
}
else
{
return data[index-1];
}
}
/// <summary>
/// 按值查找
/// 顺序表中的按值查找是指在表中查找满足给定值的数据元素。在顺序表中完成该运算最简单的方法是：从第一个元素起依次与给定值比较，如果找到，则返回在顺序表中首次出现与给定值相等的数据元素的序号，称为查找成功；否则，在顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。
/// </summary>
/// <returns>1.若能找到，返回第几个找到的2.否则返回-1</returns>
public int FindValueIndex(T t)
{
if (IsEmpty())
{
Console.WriteLine("list is Empty");
return -1;
}
for (int i = 0; i <= last; i++)
{
if (data[i].Equals(t))
{
return i+1;
}
}
return -1;
}
}
}