数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
算法为有基本运算及规定的运算顺序所构成的完整的解题步骤。
算法基于数据结构，数据结构是算法的基础。
算法评价标准：运行时间，占用空间。
线性表
线性表是最简单的，最基本，最常用的数据结构。
线性表接口定义
public interface IListDS<T>{
int GetLength();//求长度
void Clear();//清空操作
bool IsEmpty();//判断线性表是否为空
void Add(T item);//附加操作
void Insert(T item,int i);//插入操作
T Delete(int i);//删除操作
T GetElem(int i);//取表元
T this[int index]{get;}定义一个索引器获取元素
int Loccate(T value);//按值查找
}
线性表的实现方式
顺序表，单链表
双向链表，循环链表
顺序表
在计算机内，保存线性表最简单、最自然的方式，就是把表中的元素一个接一个地放进顺序的存储单元，这就是线性表的顺序存储(Sequence
Storage)。线性表的顺序存储是指在内存中用一块地址连续的空间依次存放线性表的数据元素，用这种方式存储的线性表叫顺序表(Sequence List)
//定义一个泛型顺序表类
public class SeqList<T>:IListDS<T>
{
//字段
private int maxsize; //顺序表的最大容量
private T[] data; //用于存储顺序表中数据元素的一维数组
private int last; //指定顺序表中u字后一个数据元素的位置
//基本操作
//索引器
public T this[int index]
{
get { return data[index]; }
set{ data[index]=value; }
}
//最后一个元素的位置属性
public int Last
{
get{ return last; }
}
//最大容量属性
public int Maxsize
{
get{ return maxszie; }
set{ maxsize=valule; }
}
//构造方法
public SeqList(int size)
{
data = new T[size];
maxsize=size;
last=-1;
}
//求表中元素的个数
public int GetLength()
{
return last + 1; //最后一个元素索引值+1
}
//清空元素
public int GetLength()
{
last = -1; //设置最后一个元素位置为-1在逻辑上清空元素，但在内存中并未清除
}
//判断是否为空表
public bool IsEmpty()
{
if(last == -1){retrun true;}
else{return false;}
}
//判断表中元素是否已填满
public bool IsFull()
{
if(last == maxsize - 1){return true;}
else{ return false; }
}
//在表的尾部追加元素
public bool Append(T item)
{
//判断表中数据是否已填满
if(IsFull()){ Console.WriteLine("顺序表中的数据元素已填满，无法继续执行追加操作")； return false; }
else{data[++last] = item; //先使最后位置递增1，以符合追加操作后的最后元素
retrun true;}
}
//在表的位置i插入一个元素
public bool Insert(T item , int i)
{
//判断表中数据是否已填满
if(IsFull()){ Console.WriteLine("顺序表中的数据元素已填满，无法继续执行插入操作"); return false;}
else{
//判断用户指定的插入位置是否合理
if(i<1 || i>last + 2){Console.WriteLine("插入元素的位置不正确，无法执行操作")； return false;}
else if(i == last +2){ data[last +1]=item; last++;}
//执行一般插入操作
else{
//先将位置i起所有元素向后拷贝
for(int j = last;j>=i-1;j--){data[j+1]=data[j];}
//将新的元素赋给位置i
data[i-1]=item;
last++;
//这里之所以使用i-1因为位置i的索引值为i-1
//这里计数从1开始，而索引计数从0开始
}
return true;
}
}
//删除表中位置i的位置
public T Delete(int i)
{
//定义要返回的元素，并赋初值
T tmp=default(T);
//判断是否为空表
if(IsEmpty()){Console.WriteLine("顺序表中不存在数据元素，无法执行删除操作，");}
//判断用户指定的插入位置是否合理
else if(i<1 || i>last +1){Console.WriteLine("删除元素的位置不正确，无法执行删除操作");}
//判断用户是否操作最后一个元素（无需进行元素移动）
else if(i==last + 1){tmp =data[last--];}//FIXME
执行一般操作
else{
tmp =data[i-1];
//向前移动元素
for(int j=i;j<last;j++) { data[j]=data[j+1];}
last --;
}
//返回被操作的元素（或默认值）
return tmp;
}
//获取表中位置i的元素
public T GetElem(int i)
{
//定义要返回的元素，并赋初值
T tmp = default(T);
//判断是否为空表
if(IsEmpty()) { Console.WriteLine("获取元素的位置不正确，无法执行操作");}
//执行获取操作
else{tmp = data[i-1];}
//返回被获取的元素（或默认值）
return tmp;
}
//在表中查找值为value的元素
public int Locate(T value)
{
//定义要返回的索引，-1表示未找到或查找失败
int i;
//判断表是否为空表
if(IsEmpty()) { Console.WriteLine("顺序表中不存在数据元素，无法执行查找操作"); i=-1; }
else{
//开始查找元素
for(i=0;i<=last;i++){
//判断当前元素是否与value匹配
if(value.Equals(data[i])){ //判断元素与value匹配，直接跳出循环 break;}
}
//判断查找索引是否超出表的最大索引值
if(i>last){ i = -1;}
}
//返回查找到的索引（或默认值）
return i;
}
//对应首括号
}
网友评论