數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合魂角。
算法為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟剩胁。
算法基于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)疫稿。
算法評(píng)價(jià)標(biāo)準(zhǔn)：運(yùn)行時(shí)間蟋定，占用空間粉臊。
線(xiàn)性表
線(xiàn)性表是最簡(jiǎn)單的，最基本溢吻，最常用的數(shù)據(jù)結(jié)構(gòu)维费。
線(xiàn)性表接口定義
public interface IListDS<T>{
int GetLength();//求長(zhǎng)度
void Clear();//清空操作
bool IsEmpty();//判斷線(xiàn)性表是否為空
void Add(T item);//附加操作
void Insert(T item,int i);//插入操作
T Delete(int i);//刪除操作
T GetElem(int i);//取表元
T this[int index]{get;}定義一個(gè)索引器獲取元素
int Loccate(T value);//按值查找
}
線(xiàn)性表的實(shí)現(xiàn)方式
順序表果元，單鏈表
雙向鏈表促王，循環(huán)鏈表
順序表
在計(jì)算機(jī)內(nèi)，保存線(xiàn)性表最簡(jiǎn)單而晒、最自然的方式蝇狼，就是把表中的元素一個(gè)接一個(gè)地放進(jìn)順序的存儲(chǔ)單元，這就是線(xiàn)性表的順序存儲(chǔ)(Sequence
Storage)倡怎。線(xiàn)性表的順序存儲(chǔ)是指在內(nèi)存中用一塊地址連續(xù)的空間依次存放線(xiàn)性表的數(shù)據(jù)元素迅耘，用這種方式存儲(chǔ)的線(xiàn)性表叫順序表(Sequence List)
//定義一個(gè)泛型順序表類(lèi)
public class SeqList<T>:IListDS<T>
{
//字段
private int maxsize; //順序表的最大容量
private T[] data; //用于存儲(chǔ)順序表中數(shù)據(jù)元素的一維數(shù)組
private int last; //指定順序表中u字后一個(gè)數(shù)據(jù)元素的位置
//基本操作
? ? //索引器
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 maxszie; }
set{ maxsize=valule; }
}
//構(gòu)造方法
public SeqList(int size)
{
data = new T[size];
maxsize=size;
last=-1;
}
//求表中元素的個(gè)數(shù)
public int GetLength()
{
return last? + 1; //最后一個(gè)元素索引值+1
}
//清空元素
public int GetLength()
{
last = -1; //設(shè)置最后一個(gè)元素位置為-1在邏輯上清空元素贱枣，但在內(nèi)存中并未清除
}
//判斷是否為空表
public bool IsEmpty()
{
if(last == -1){retrun true;}
else{return false;}
}
//判斷表中元素是否已填滿(mǎn)
public bool IsFull()
{
if(last == maxsize - 1){return true;}
else{ return false; }
}
//在表的尾部追加元素
public bool Append(T item)
{
//判斷表中數(shù)據(jù)是否已填滿(mǎn)
if(IsFull()){? Console.WriteLine("順序表中的數(shù)據(jù)元素已填滿(mǎn)，無(wú)法繼續(xù)執(zhí)行追加操作")颤专； return false; }
else{data[++last] = item;? //先使最后位置遞增1纽哥，以符合追加操作后的最后元素
? retrun true;}
}
//在表的位置i插入一個(gè)元素
public bool Insert(T item , int i)
{
//判斷表中數(shù)據(jù)是否已填滿(mǎn)
if(IsFull()){ Console.WriteLine("順序表中的數(shù)據(jù)元素已填滿(mǎn)，無(wú)法繼續(xù)執(zhí)行插入操作");? return false;}
else{
//判斷用戶(hù)指定的插入位置是否合理
if(i<1 || i>last + 2){Console.WriteLine("插入元素的位置不正確栖秕，無(wú)法執(zhí)行操作")春塌； return false;}
else if(i == last +2){? data[last +1]=item; last++;}
//執(zhí)行一般插入操作
else{
//先將位置i起所有元素向后拷貝
for(int j = last;j>=i-1;j--){data[j+1]=data[j];}
//將新的元素賦給位置i
data[i-1]=item;
last++;
//這里之所以使用i-1因?yàn)槲恢胕的索引值為i-1
//這里計(jì)數(shù)從1開(kāi)始，而索引計(jì)數(shù)從0開(kāi)始
? ? ? ? }
return true;
}
}
//刪除表中位置i的位置
public T Delete(int i)
{
//定義要返回的元素簇捍，并賦初值
T tmp=default(T);
//判斷是否為空表
if(IsEmpty()){Console.WriteLine("順序表中不存在數(shù)據(jù)元素只壳，無(wú)法執(zhí)行刪除操作，");}
//判斷用戶(hù)指定的插入位置是否合理
else if(i<1 || i>last +1){Console.WriteLine("刪除元素的位置不正確暑塑，無(wú)法執(zhí)行刪除操作");}
//判斷用戶(hù)是否操作最后一個(gè)元素（無(wú)需進(jìn)行元素移動(dòng)）
else if(i==last + 1){tmp =data[last--];}//FIXME
執(zhí)行一般操作
else{
tmp =data[i-1];
//向前移動(dòng)元素
for(int j=i;j<last;j++)? { data[j]=data[j+1];}
last --;
? ? ? ? }
//返回被操作的元素（或默認(rèn)值）
return tmp;
}
//獲取表中位置i的元素
public T GetElem(int i)
{
//定義要返回的元素吼句，并賦初值
T tmp = default(T);
//判斷是否為空表
if(IsEmpty()) { Console.WriteLine("獲取元素的位置不正確，無(wú)法執(zhí)行操作");}
//執(zhí)行獲取操作
else{tmp = data[i-1];}
//返回被獲取的元素（或默認(rèn)值）
return tmp;
}
//在表中查找值為value的元素
public int Locate(T value)
{
//定義要返回的索引事格，-1表示未找到或查找失敗
int i;
//判斷表是否為空表
if(IsEmpty()) { Console.WriteLine("順序表中不存在數(shù)據(jù)元素惕艳，無(wú)法執(zhí)行查找操作");? i=-1; ? }
else{
//開(kāi)始查找元素
for(i=0;i<=last;i++){
//判斷當(dāng)前元素是否與value匹配
if(value.Equals(data[i])){? //判斷元素與value匹配，直接跳出循環(huán) ? ? ? ? ? ? ? ?? break;}
? ? ? ? ? ? ? ? ? ? ? ? ? ?? }
//判斷查找索引是否超出表的最大索引值
if(i>last){ i = -1;}
? ?? }
//返回查找到的索引（或默認(rèn)值）
return i;
}
//對(duì)應(yīng)首括號(hào)
}
