1.單鏈表的定義和由來:
鏈表是用一組地址可能連續也可能不連續的存儲單元來存儲線性表中的數據元素,在存儲數據元素時,除了要存儲數據元素本身之外,還要存儲與它相鄰的數據元素的地址信息,這兩部分組成了線性表中一個數據元素的映像,稱之為"結點",存儲數據元素本身的部分稱之為:數據域,存儲相鄰數據元素地址的部分稱之為:地址域,所有節點通過地址域鏈接起來,像一個鏈條,故用此種方式存儲的線性表稱之為:鏈表.如果節點的地址域只存儲了數據元素的直接后繼的存儲地址,則稱這種鏈表為:單鏈表.
與數序表相比,鏈表由于是通過存儲后繼結點地址的方式來體現線性關系的,向鏈表中插入,刪除數據元素要比順序表要快(因為順序表對數據元素的插入和刪除操作時,大部分情況下,要對數據元素在存儲單元中做移動);但是查找鏈表中的數據元素要比順序表中的查找要慢,因為查找鏈表中的數據元素,需要遍歷鏈表(而順序表由于每個元素與第一個元素的地址相對固定,所以只要知道第一個數據元素的地址和數據元素的數據類型,很快就會直接定位到要查找的數據元素).
結點:
2.單鏈表的實現:
2.1結點:
Node
public class Node<T>
{
private T _data;
public T Data
{
get { return _data; }
set { _data = value; }
}
private Node<T> _next;
public Node<T> Next
{
get { return _next; }
set { _next = value; }
}
public Node()
{
_data = default(T);
_next = null;
}
public Node(T data)
{
_data = data;
_next = null;
}
public Node(Node<T> next)
{
_next = next;
}
}2.2單鏈表:
SepLinkedList
public class SepLinkedList<T>
{
private Node<T> _head;
///
/// 頭指針
///
public Node<T> Head
{
get { return _head; }
set { _head = value; }
}
///
/// 獲取單鏈表長度
///
///
public int GetLength()
{
Node<T> p = _head;
int length = 0;
while (p != null)
{
length++;
p = p.Next;
}
return length;
}
///
/// 清空單鏈表
///
public void Clear()
{
_head = null;
}
public bool IsEmpty()
{
if (_head == null)
{
return true;
}
else
{
return false;
}
}
///
/// 附件數據元素
///
///
public void Append(T item)
{
Node<T> p = new Node<T>();
Node<T> q = new Node<T>(item);
if (_head == null)
{
_head = q;
return;
}
p = _head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
///
/// 刪除第i個數據元素
///
///
///
public T Delete(int i)
{
Node<T> q = new Node<T>();
if (i == 1)
{
q = _head;
_head = _head.Next;
return q.Data;
}
Node<T> p = _head;
int 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("該位置不存在結點");
return default(T);
}
}
///
/// 在第i個位置前插入數據元素
///
///
///
public void Insert(T item, int i)
{
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>();
int j=1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next = q;
}
}
///
/// 在第i個位置后插入一個數據元素
///
///
///
public void InsertPost(T item, int i)
{
Node<T> p = _head;
int j = 1;
//找第i個元素
while (p.Next != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p.Next;
p.Next = q;
}
}
///
/// 取表元
///
///
///
public T GetElem(int i)
{
if (IsEmpty())
{
Console.WriteLine("鏈表為空");
return default(T);
}
Node<T> p = new Node<T>();
p = _head;
int j = 1;
while (p.Next != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("未找到該序號的結點");
return default(T);
}
}
///
/// 按值查找數據元素
///
///
///
public int Locate(T item)
{
if (IsEmpty())
{
Console.WriteLine("鏈表為空");
return -1;
}
Node<T> p = new Node<T>();
p = _head;
int i = 1;
while ( p != null && !item.Equals(p.Data))
{
p = p.Next;
i++;
}
if (p != null)
{
return i;
}
else
{
Console.WriteLine("單鏈表中不存在指定數據元素");
return -1;
}
}
}
2.2.1插入數據元素的圖示:
2.2.2刪除數據元素的圖示:
2.2.3 單鏈表的建立:
第一種方式:(采用從尾部加入結點的方式)
CreateLinkedList
///
/// 建立單鏈表
///
///
static SepLinkedList<int> CreateLinkedList()
{
SepLinkedList<int> result = new SepLinkedList<int>();
Node<int> r = new Node<int>();
r = result.Head;
int elem = Int32.Parse(Console.ReadLine());
while (elem != -1)//以-1做為結束標志
{
Node<int> p = new Node<int>(elem);
if (result.Head == null)
{
result.Head = p;
}
else
{
r.Next = p;//加入鏈表
}
r = p; //記下最后一個結點
elem = Int32.Parse(Console.ReadLine());
}
if (r != null)
{
r.Next = null;//最后一個節點地址域置空
}
return result;
}
第二種方式:(采用在頭部加入結點的方式)
CreateLinkedList
static SepLinkedList<int> CreateSepLinkedList()
{
SepLinkedList<int> result = new SepLinkedList<int>();
int d = Int32.Parse(Console.ReadLine());
while (d != -1)
{
Node<int> elem = new Node<int>(d);
elem.Next = result.Head;
result.Head = elem;
d = Int32.Parse(Console.ReadLine());
}
return result;
}
2.2.4關于單鏈表的操作:
Code
/// <summary>
/// 將整形順序表A中大于零的元素放入順序表B中,把小于零的數據元素放入順序表C中
/// 算法思想:遍歷單鏈表la,依次讀取數據元素與0比較,將小于0的數據元素放入lc,將大于0的放入lb
/// </summary>
/// <param name="la"></param>
static void PurgeToTwo(SepLinkedList<int> la,SepLinkedList<int> lb,SepLinkedList<int> lc)
{
Node<int> p = la.Head;
while (p != null)
{
if (p.Data > 0)
lb.Append(p.Data);
else
lc.Append(p.Data);
p = p.Next;
}
}
/// <summary>
/// 取單鏈表中最小值
/// 算法思想:去取最大值相反
/// </summary>
/// <param name="la"></param>
/// <returns></returns>
static int GetMin(SepLinkedList<int> la)
{
Node<int> p = la.Head;
Node<int> temp = p;
while (p.Next != null)
{
p = p.Next;
if (temp.Data > p.Data)
{
temp = p;
}
}
return temp.Data;
}
/// <summary>
/// 取單鏈表中最大值
/// 算法思想:取鏈表中的第一個數據元素,然后讓這個元素與剩下的元素比較,將兩者較小者存入結果中
/// </summary>
/// <param name="la"></param>
/// <returns></returns>
static int GetMax(SepLinkedList<int> la)
{
Node<int> p = la.Head;
Node<int> temp = p;
while (p.Next != null)
{
p = p.Next;
if (temp.Data < p.Data)
{
temp = p;
}
}
return temp.Data;
}
設一順序表(單鏈表)中的元素值遞增有序,將元素x插入到表中適當的位置,
//并保持順序表(單鏈表)的有序性
//分析時間復雜度
static void Insert(SepLinkedList<int> la, int x)
{
Node<int> p = la.Head;
Node<int> q = new Node<int>();
Node<int> temp = new Node<int>(x);
if (x < p.Data) //小于第一個元素
{
temp.Next = la.Head;
la.Head = temp;
}
while (p.Next != null)
{
q = p;
p = p.Next;
if (q.Data <= x && x <= p.Data)
{
temp.Next = p;
q.Next = temp;
return;
}
}
if (p != null)
{
p.Next = temp;
}
}
/// <summary>
/// 提取單鏈表中不重復的數據元素
/// </summary>
/// <param name="l"></param>
/// <returns></returns>
static SepLinkedList<int> Purge(SepLinkedList<int> l)
{
SepLinkedList<int> result = new SepLinkedList<int>();
Node<int> p = l.Head;
Node<int> q = new Node<int>();
Node<int> s = new Node<int>();
//將第一個元素加入結果鏈表
s = p;
p = p.Next;
s.Next = null;
result.Head = s;
while (p != null)
{
s = p;
p = p.Next;
q = result.Head;
while (q != null && q.Data != s.Data)
{
q = q.Next;
}
if (q == null)
{
s.Next = result.Head;
result.Head = s;
}
}
return result;
}
/// <summary>
/// 將兩個存儲整型數據元素升序排列的單鏈表合并,并保持升序
/// 算法思想:將la中的每個元素與lb的元素依次比較,并將每次比較中的小者加入結果鏈表中,最后將剩余的數據元素加入結果鏈表中
/// </summary>
/// <param name="la"></param>
/// <param name="lb"></param>
/// <returns></returns>
static SepLinkedList<int> Merge(SepLinkedList<int> la, SepLinkedList<int> lb)
{
Node<int> p = la.Head;
Node<int> q = lb.Head;
int temp = 0;
SepLinkedList<int> result = new SepLinkedList<int>();
while (p != null && q != null)
{
if (p.Data < q.Data)
{
temp = p.Data;
p = p.Next;
}
else
{
temp = q.Data;
q = q.Next;
}
}
result.Append(temp);
if (p == null)
{
p = q;
}
while (p != null)
{
temp = p.Data;
result.Append(temp);
p = p.Next;
}
return result;
}
留言列表
