静态链表
静态链表是用数组模拟动态链表。
静态链表结构描述
首先，静态链表使用数组来模拟动态链表。
数组存放一个节点对象，对象包括数据与和游标域两个属性。
在这个数组中，第一个元素用来指示第一个可用节点的位置，最后一个元素用来指示第一个包含元素的节点（相当于头节点）。
也可以理解为，数组中存放了两个节点，一个是备用节点（存放数组中的空位置），头节点的下表是[0]；另一个是已用节点（存放数组中包含元素的位置），头节点的下表是[数组长度-1]。
数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表的头节点作用，当整个链表为空时，则为0，表示无指向。如图3-12-2所示
现在如果我们需要在“乙”和“丁”之间插入一个值为“丙”的元素，只需要将“乙”的cur改为7，表示下一位是“丙”，并将“丙”的cur改为3，表示下一位是丁。如图3-12-3所示。
现在如果我们删除了第一个元素“甲”，表示现在“甲”这个位置空出来了，如果未来有新人要来则优先考虑这里，所以删除的位置成为第一个优先空位，即首元素的cur为1， 第一个元素位置的cur改为8，而下标为8的位置cur改为9，最后元素位置的cur改为2，如图3-12-4所示。
代码实现
下面的实现代码中，可用链表（备用链表）的头节点的Next域为已用链表的头节点时（及数组首元素.Next=尾元素的下标）即为可用链表已满。因为在代码实现中，初始化时每个节点的.Next域都是他的下一个元素的下标，所以当遍历到可用链表的最后一个链表元素时，他的.Next域就是最后一个数组元素。
Node类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test2
{
class Node<T>
{
T data; //数据
int next; //下一个的游标
public T Data { get => data; set => data = value; }
public int Next { get => next; set => next = value; }
//构造器
public Node()
{
Data = default(T);
Next = 0;
}
}
}
StaticLink类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test2
{
class StaticLink<T>
{
Node<T>[] lst;
int length = 0;
public int Length { get => length; set => length = value; }
internal Node<T>[] Lst { get => lst; set => lst = value; }
/// <summary>
/// 构造器
/// </summary>
/// <param name="len"></param>
public StaticLink(int len)
{
len = len + 2;
Lst = new Node<T>[len]; //数组第一个和最后一个不能存数据，所以补上两个
for (int j = 0; j < len; j++)
{
Lst[j] = new Node<T>();
Lst[j].Next = j + 1;
}
Lst[len - 1].Next = 0;
}
/// <summary>
/// 申请一个节点，获取第一个可用节点位置
/// </summary>
/// <returns></returns>
int malloc()
{
int i = Lst[0].Next; //获取备用头节点中存放的下一个可用节点位置。
//当申请的节点位置和最后一个节点位置相同时，说明可用链表已经分配完毕。
if (i != Lst.Length - 1)
{
++Length;//更新链表长度
return i;
}
else { Console.WriteLine("链表已满"); return 0; }
}
/// <summary>
///归还一个节点到备用链表上
/// </summary>
/// <param name="pos">要删除的节点的前驱位置</param>
void free(int pos)
{
int c = Lst[pos].Next; //要删除的节点
//删除首节点
if (pos == 0)
{
Lst[Lst.Length - 1].Next = Lst[1].Next;
Lst[1].Next = Lst[0].Next; //更新可用链表
Lst[0].Next = 1; //更新可用链表头节点
}
//删除节点
else
Lst[pos].Next = Lst[c].Next;
--Length;
}
/// <summary>
/// 在链表尾部添加一个元素
/// </summary>
/// <param name="value"></param>
public void Append(T value)
{
int pos = malloc(); //获取第一个可用节点位置
//如果节点可用
if (pos > 0)
{
//遍历已用链表，挂载新节点
int k = Lst[Lst.Length - 1].Next;
while (Lst[k].Next != 0)
{
k = Lst[k].Next;
}
Lst[k].Next = pos;
Lst[0].Next = Lst[pos].Next;//更新备用链表头节点
Lst[pos].Next = 0; //更新已用链表结尾
//添加节点数据
Lst[pos].Data = value;
//仅在第一次附加时更新已用链表的头节点
if (Length == 0)
{
//Console.WriteLine("已用"+i);
Lst[Lst.Length - 1].Next = pos;//更新已用链表头节点
}
}
}
/// <summary>
/// 在指定位置后插入一个元素
/// </summary>
/// <param name="value">插入元素的值</param>
/// <param name="i">插入位置</param>
public void Insert(T value, int i)
{
if (i > Length)
{
Console.WriteLine("位置不正确或链表为空");
return;
}
int k = malloc();
if (k > 0)
{
Lst[k].Data = value; //在新申请的节点中填充数据
int j = Lst[Lst.Length-1].Next;
//遍历查找位置
for (int n = 0; n < i - 1; n++)
{
j = Lst[j].Next;
}
Lst[0].Next = Lst[k].Next; //更新可用链表首节点
Lst[k].Next = Lst[j].Next; ; //更新已用链表结尾
Lst[j].Next = k; //挂载节点
}
}
/// <summary>
/// 删除指定位置的元素
/// </summary>
/// <param name="i">元素在链表中的位置</param>
public void Delete(int pos)
{
//pos = pos + 1;
if (pos > Length)
{
Console.WriteLine("位置不正确或链表为空");
return;
}
//删除首节点
if (pos == 1)
{
free(0);
return;
}
//遍历要删除节点的前驱
int k = Lst[Lst.Length - 1].Next;
Console.WriteLine("k1:" +k);
for (int i = 0; i < pos - 2; i++)
{
k = Lst[k].Next;
}
Console.WriteLine("k:" + k);
free(k);
}
}
}
Program类
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace test2
{
class Program
{
static void Main(string[] args)
{
StaticLink<string> link = new StaticLink<string>(5);
link.Append("123");
link.Append("456");
link.Append("789");
//link.Insert("asd", 2);
link.Delete(1);
Console.WriteLine("---数组打印");
for (int j = 0; j < link.Lst.Length; j++)
{
Console.WriteLine(j + ":" + link.Lst[j].Data + ":" + link.Lst[j].Next);
}
Console.WriteLine("---链表打印");
int i = link.Lst[link.Lst.Length - 1].Next;
while (i != 0)
{
Console.WriteLine(link.Lst[i].Data);
i = link.Lst[i].Next;
}
}
}
}
网友评论