第3章 線性表的順序存儲c#實現---《大話數據結構》讀書筆記
2012-01-04 23:22 海不是藍 閱讀(1093) 評論(5) 收藏 舉報線性表的定義
線性表(List)：零個或多個數據元素的有限序對。
強調:
1. 線性表是有限的。
2. 元素之間是有順序的。
3. 若存在多個元素，則第一個元素無前驅，最后一個元素無后繼。
4. 其他每個元素都有且只有一個前驅和后繼。
數學語言定義
若線性表記為(a1,…ai-1,ai,ai+1,…,an)，則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。當i=1,2,…，n-1時，ai有且僅有一個直接后繼，當i=2,3,…n時，ai有且僅有一個直接前驅。
線性表元素的個數n(n>=0)定義為線性表的長度，當n=0時，稱為空表。
線性表的順序存儲結構
順序存儲的定義
線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。
|
a1 |
a2 |
…… |
ai-1 |
ai |
…… |
an |
順序表至少需要3個屬性
1. 存儲空間：一個一維數組，它的存儲位置就是存儲空間的存儲位置。
2. 線性表的最大存儲容量：數組長度MaxSize。
3. 線性表的當前長度:length。
注意
這里有2個概念：“數組的長度”和“線性表的長度“需要區分下
數組的長度是存放線性表的存儲空間的長度，存儲分配以后這個量是不變的。
線性表的長度是線性表中數據元素的個數，隨著線性表的插入和刪除等操作的進行，這個量是變化的。
地址的計算方法
存儲器中每個存儲單元都有自己的編號，這個編號稱為地址。
假設線性表的每個元素占用c個存儲單元，那么線性表中第i+1個數據元素的存儲位置和i個數據元素的存儲位置滿足下列關系(LOC表示獲得存儲位置的函數)。
LOC(ai+1)=LOC(ai)+c;
LOC(ai)=LOC(a1)+(i-1)*c;
--------------------------代碼------------------------------
class Program
{
static void Main(string[] args)
{
try
{
SeqList<string> list = newSeqList<string>(5);
Console.WriteLine("IsEmpty={0}", list.IsEmpty());
Console.WriteLine("插入3個元素");
list[0] = "a";
list[1] = "b";
list[2] = "c";
Console.WriteLine("IsEmpty={0}", list.IsEmpty());
ShowList(list);
Console.WriteLine("----------------------------------");
Console.WriteLine("刪除第2個元素");
string str = list.Delete(2);
Console.WriteLine("被刪除的元素是{0}", str);
ShowList(list);
Console.WriteLine("----------------------------------");
Console.WriteLine("附加一個元素d");
list.Append("d");
Console.WriteLine("list長度={0} list最后一個元素索引是={1}", list.GetLength(), list.Last);
ShowList(list);
Console.WriteLine("----------------------------------");
Console.WriteLine("刪除第一個元素a，然后在第2個位置插入e");
list.Delete(1);
list.Insert("e", 2);
ShowList(list);
Console.WriteLine("----------------------------------");
Console.WriteLine("按值查找c");
Console.WriteLine("找到值={0},{0}的索引是={1}", list[list.Locate("c")], list.Locate("c"));
Console.WriteLine("----------------------------------");
Console.WriteLine("獲取第二個元素={0}", list.GetElem(2));
Console.WriteLine("----------------------------------");
Console.WriteLine("清空list");
list.Clear();//這里只是設置了順序表的可訪問的空間為0
ShowList(list);
Console.WriteLine("list長度={0} list最后一個元素索引是={1} list IsEmpty={2}", list.GetLength(), list.Last, list.IsEmpty());
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
Console.Read();
}
static void ShowList(SeqList<string> list)
{
for (Int32 i = 0; i < list.GetLength(); i++)
Console.WriteLine(list[i]);
}
}
public interface IListDS<T>
{
Int32 GetLength();//求長度
void Clear();//清空操作
bool IsEmpty();//判斷線性表是否為空
void Append(T item);//附加操作
void Insert(T item, Int32 i);//插入操作
T Delete(Int32 i);//刪除操作
T GetElem(Int32 i);///獲取表元
Int32 Locate(T value);//按值查找
}
public class SeqList<T> : IListDS<T>
{
private Int32 maxsize;//順序表的容量
private T[] data;//數組，用于存儲順序表中的數據元素
private Int32 last;//指示順序表最后一個元素的位置
//索引器
public T this[Int32 index]
{
get
{
if (index < 0 || index > last)
throw new IndexOutOfRangeException("索引超出了數組界限");
return data[index];
}
set
{
if (index < 0 || index > maxsize - 1)
throw new IndexOutOfRangeException("索引超出了數組界限");
data[index] = value;
last++;
}
}
//最后一個數據元素的位置屬性
public Int32 Last
{
get { return last; }
}
//容量屬性
public Int32 Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
//構造器
public SeqList(Int32 size)
{
data = new T[size];
maxsize = size;
last = -1;
}
//求順序表的長度
public Int32 GetLength()
{
return last + 1;
}
//清空順序表
public void Clear()
{
last = -1;
}
//判斷順序表是否為空
public bool IsEmpty()
{
return last == -1 ? true : false;
}
//判斷順序表是否為滿
public bool IsFull()
{
return last == maxsize - 1 ? true : false;
}
//在順序表的末尾添加新元素
public void Append(T item)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}
data[++last] = item;
}
//在順序表的第i個數據元素的位置插入一個數據元素
public void Insert(T item, Int32 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 (Int32 j = last; j >= i - 1; --j)
{
data[j + 1] = data[j];
}
data[i - 1] = item;
}
++last;
}
//刪除順序表的第i個數據元素
public T Delete(Int32 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;
}
else
{
tmp = data[i - 1];
for (Int32 j = i - 1; j < last; ++j)
{
data[j] = data[j + 1];
}
}
--last;
return tmp;
}
//獲取順序表的第i個數據元素
public T GetElem(Int32 i)
{
if (IsEmpty() || (i < 1) || (i > last + 1))
{
Console.WriteLine("List is empty or Position is error");
returndefault(T);
}
return data[i - 1];
}
//在順序表中查找值為value的數據元素
public Int32 Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is empty");
return -1;
}
Int32 i = 0;
for (i = 0; i <= last; ++i)
{
if (value.Equals(data[i]))
break;
}
if (i > last)
return -1;
return i;
}
}
-----------------------------------------------------
時間復雜度分析
Int32 GetLength();//求長度
時間復雜度為O(1)，這里就是固定的執行last + 1。
void Clear();//清空操作
時間復雜度為O(1)，這里就是固定的執行last = -1;
bool IsEmpty();//判斷線性表是否為空
時間復雜度為O(1)
void Append(T item);//附加操作
時間復雜度為O(1)
void Insert(T item, Int32 i);//插入操作
當插入的節點在線性表的最后，那么就是添加一個元素，所以時間復雜度是O(1)。
當插入節點在線性表的開頭，那么被插入節點的后續都要向后移動。
所以時間復雜度為O(n)
T Delete(Int32 i);//刪除操作
當刪除節點在線性表的最后，時間復雜度為O(1)
當刪除節點在線性表的開頭，那么被刪除節點的后續都要向前移動。
所以時間復雜度為O(n)
T GetElem(Int32 i);//獲取表元
這個快，直接索引數組的元素，時間復雜度為O(1)
Int32 Locate(T value);//按值查找
最壞的情況就是一個for循環，把線性表的元素都循環對比一次，時間復雜度為O(n)
--------------------------------------------------------------------------------
運行截圖
浙公網安備 33010602011771號