第3章 線性表的單鏈表c#實現---《大話數據結構》讀書筆記
2012-01-11 17:02 海不是藍 閱讀(1462) 評論(1) 收藏 舉報線性表的鏈式存儲結構(單鏈表)
定義
為了表示每個數據元素ai與其直接后繼數據元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼的信息(即直接后繼的存儲位置)。把存儲數據元素信息的域稱為數據域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱作指針鏈，這兩部分信息組成數據元素ai的存儲映象，稱為結點(Node)。
n個結點(ai的存儲映像)鏈結成為一個鏈表，即為線性表(ai,a2,…,an)的鏈式存儲結構，因為此鏈表的每一個結點中只包含一個指針域，所以叫做單鏈表。
鏈表中第一個結點的存儲位置叫做頭指針。
單鏈表的讀取
從頭開始找，當i=1的時候，就直接取出數據了。當i=n的時候，需要遍歷n-1次，如果位置n-1的結點的next指針不是null，那么就找到了。最壞的時間復雜度為O(n)。
單鏈表的優勢在于插入和刪除。但是查找就是雞肋了。
單鏈表的插入
假設存儲元素e的結點為s，要實現結點p，p->next和s之間的邏輯關系的變化，只需要將結點s插入到結點p和p->next之間即可。讓p的后繼結點改成s的后繼結點，然后把結點s變成p的后繼結點。
單鏈表的刪除
設存儲元素ai的結點為q，要實現講結點q刪除單鏈表的操作，其實就是將它的前繼結點的指針繞過，指向它的后繼結點即可。
單鏈表的刪除和插入的時間復雜度都是O(n)，
清空操作
清空操作是指清除單鏈表中的所有結點，使單鏈表為空。這里設置head=null。然后等待垃圾回收器進行回收。這里不需要我們自己去處理。而順序表的清空只是設置一個索引=-1，但是數組的空間還是在，只是外部無法訪問元素。
單鏈表結構與順序存儲結構的優缺點
|
存儲分配方式 |
時間性能 |
空間性能 |
|
*順序表的存儲結構用一段連續的存儲單元依次存儲線性表的數據元素。 *單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的元素 |
*查找 順序存儲結構O(1) 單鏈表O(n) *插入和刪除 順序存儲結構O(n) 單鏈表O(1) |
*順序表需要預分配存儲空間 *單鏈表不需要預分配存儲空間 |
c#代碼
class Program
{
static void Main(string[] args)
{
Console.WriteLine("------添加3個節點------");
LinkList<Test> list = new LinkList<Test>();
list.Append(new Test("aaa", 1));
list.Append(new Test("bbb", 2));
list.Append(new Test("ccc", 3));
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------在第2個節點前插入1個節點------");
list.Insert(new Test("aaa1", 11), 2);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------在第3個節點后插入1個節點------");
list.InsertPost(new Test("bbb1", 222), 3);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------刪除第4個節點------");
list.Delete(4);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------獲取第3個節點------");
Test t = list.GetElem(3);
Console.WriteLine("name={0} age={1}", t.Name, t.Age);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------查找------");
Console.WriteLine("位置：{0}", list.Locate(new Test("bbb", 2)));
Console.WriteLine("name={0} age={1}", t.Name, t.Age);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------清空單鏈表------");
list.Clear();
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.Read();
}
static void Show(Node<Test> node)
{
Node<Test> p = node;
while (p.Data != null)
{
Console.WriteLine("name:{0} age:{1}", p.Data.Name, p.Data.Age);
if (p.Next == null)
break;
else
p = p.Next;
}
}
}
public class Test
{
public Test(string name, UInt16 age)
{
this.name = name;
this.age = age;
}
private string name;
public string Name
{
get { return name; }
set { name = value; }
}
private UInt16 age;
public UInt16 Age
{
get { return age; }
set { age = value; }
}
//重寫Equals，判斷對象的相等性而不是同一性
public override bool Equals(object obj)
{
if (obj == null)
return false;
if (this.GetType() != obj.GetType())
return false;
Test obj1 = (Test)obj;
if (obj1.Age != this.Age || obj1.Name != this.Name)
return false;
return true;
}
}
public class Node<T>
{
private T data;//數據域
private Node<T> next;//引用域
//構造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
//構造器(頭結點)
public Node(Node<T> p)
{
next = p;
}
//構造器(尾結點)
public Node(T val)
{
data = val;
next = null;
}
//構造器
public Node()
{
data = default(T);
next = null;
}
//數據域屬性
public T Data
{
get { return data; }
set { data = value; }
}
//引用域屬性
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
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 LinkList<T> : IListDS<T>
{
private Node<T> head;
//頭引用屬性
public Node<T> Head
{
get { return head; }
set { head = value; }
}
//構造器
public LinkList()
{
head = null;
}
//求單鏈表的長度
public Int32 GetLength()
{
Node<T> p = head;
Int32 len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
//清空單鏈表
public void Clear()
{
head = null;
}
//判斷單鏈表是否為空
public bool IsEmpty()
{
if (head == null)
{ return true; }
else
{ return false; }
}
//在單鏈表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head == null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
//在單鏈表的第i個節點的位置前插入一個節點
public void Insert(T item, Int32 i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
Node<T> p = head;
Node<T> r = new Node<T>();
Int32 j = 1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
}
//在單鏈表的第i個節點的位置后插入一個值為item的節點
public void InsertPost(T item, Int32 i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
Int32 j = 1;
while (p != null && j < i)
{
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}
//刪除單鏈表的第i個節點
public T Delete(Int32 i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error");
return default(T);
}
Node<T> q = new Node<T>();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
Int32 j = 1;
while (p.Next != null && j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The node is not exist");
return default(T);
}
}
//獲取單鏈表的第i個數據元素
public T GetElem(Int32 i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
Int32 j = 1;
while (p.Next != null && j < i)
{
++j;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The node is not exist");
return default(T);
}
}
//在單鏈表中查找值為value的節點
public Int32 Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty");
return -1;
}
Node<T> p = new Node<T>();
p = head;
Int32 i = 1;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
++i;
}
return i;
}
}
{
static void Main(string[] args)
{
Console.WriteLine("------添加3個節點------");
LinkList<Test> list = new LinkList<Test>();
list.Append(new Test("aaa", 1));
list.Append(new Test("bbb", 2));
list.Append(new Test("ccc", 3));
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------在第2個節點前插入1個節點------");
list.Insert(new Test("aaa1", 11), 2);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------在第3個節點后插入1個節點------");
list.InsertPost(new Test("bbb1", 222), 3);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------刪除第4個節點------");
list.Delete(4);
Show(list.Head);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------獲取第3個節點------");
Test t = list.GetElem(3);
Console.WriteLine("name={0} age={1}", t.Name, t.Age);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------查找------");
Console.WriteLine("位置：{0}", list.Locate(new Test("bbb", 2)));
Console.WriteLine("name={0} age={1}", t.Name, t.Age);
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.WriteLine("------清空單鏈表------");
list.Clear();
Console.WriteLine("長度：{0}", list.GetLength());
Console.WriteLine("判斷單鏈表是否為空:{0}", list.IsEmpty());
Console.Read();
}
static void Show(Node<Test> node)
{
Node<Test> p = node;
while (p.Data != null)
{
Console.WriteLine("name:{0} age:{1}", p.Data.Name, p.Data.Age);
if (p.Next == null)
break;
else
p = p.Next;
}
}
}
public class Test
{
public Test(string name, UInt16 age)
{
this.name = name;
this.age = age;
}
private string name;
public string Name
{
get { return name; }
set { name = value; }
}
private UInt16 age;
public UInt16 Age
{
get { return age; }
set { age = value; }
}
//重寫Equals，判斷對象的相等性而不是同一性
public override bool Equals(object obj)
{
if (obj == null)
return false;
if (this.GetType() != obj.GetType())
return false;
Test obj1 = (Test)obj;
if (obj1.Age != this.Age || obj1.Name != this.Name)
return false;
return true;
}
}
public class Node<T>
{
private T data;//數據域
private Node<T> next;//引用域
//構造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
//構造器(頭結點)
public Node(Node<T> p)
{
next = p;
}
//構造器(尾結點)
public Node(T val)
{
data = val;
next = null;
}
//構造器
public Node()
{
data = default(T);
next = null;
}
//數據域屬性
public T Data
{
get { return data; }
set { data = value; }
}
//引用域屬性
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
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 LinkList<T> : IListDS<T>
{
private Node<T> head;
//頭引用屬性
public Node<T> Head
{
get { return head; }
set { head = value; }
}
//構造器
public LinkList()
{
head = null;
}
//求單鏈表的長度
public Int32 GetLength()
{
Node<T> p = head;
Int32 len = 0;
while (p != null)
{
++len;
p = p.Next;
}
return len;
}
//清空單鏈表
public void Clear()
{
head = null;
}
//判斷單鏈表是否為空
public bool IsEmpty()
{
if (head == null)
{ return true; }
else
{ return false; }
}
//在單鏈表的末尾添加新元素
public void Append(T item)
{
Node<T> q = new Node<T>(item);
Node<T> p = new Node<T>();
if (head == null)
{
head = q;
return;
}
p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
//在單鏈表的第i個節點的位置前插入一個節點
public void Insert(T item, Int32 i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head;
head = q;
return;
}
Node<T> p = head;
Node<T> r = new Node<T>();
Int32 j = 1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
}
//在單鏈表的第i個節點的位置后插入一個值為item的節點
public void InsertPost(T item, Int32 i)
{
if (IsEmpty() || i < 1)
{
Console.WriteLine("List is empty or Position is error");
return;
}
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = head.Next;
head.Next = q;
return;
}
Node<T> p = head;
Int32 j = 1;
while (p != null && j < i)
{
p = p.Next;
++j;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}
//刪除單鏈表的第i個節點
public T Delete(Int32 i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error");
return default(T);
}
Node<T> q = new Node<T>();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node<T> p = head;
Int32 j = 1;
while (p.Next != null && j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The node is not exist");
return default(T);
}
}
//獲取單鏈表的第i個數據元素
public T GetElem(Int32 i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty");
return default(T);
}
Node<T> p = new Node<T>();
p = head;
Int32 j = 1;
while (p.Next != null && j < i)
{
++j;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The node is not exist");
return default(T);
}
}
//在單鏈表中查找值為value的節點
public Int32 Locate(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty");
return -1;
}
Node<T> p = new Node<T>();
p = head;
Int32 i = 1;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
++i;
}
return i;
}
}
浙公網安備 33010602011771號