静态链表的实现

发表评论
1,290 views

A+

所属分类：Fly数据结构与算法原创文章

静态链表，其实就是用数组的方式来实现线性表的链式结构

当然的，它的大小也是固定的（要先确定大小）

并不能可以一直增长

它是一些没有指针或者引用这样机制的编程语言

用来实现线性表的链式结构的替代

想法很精粹，所以我来实现一下它

//静态链表
class StaticLink<T>
{
    struct Node {
        public T data;
        public int cur;
    }

    private Node[] _node;
    private int _currentLength = 0;
    private int _maxLength = 24;
    private int _lastSubscript;

//静态链表

class StaticLink<T>

{

struct Node {

public T data;

public int cur;

}

private Node[] _node;

private int _currentLength = 0;

private int _maxLength = 24;

private int _lastSubscript;

这里使用的也是C#语言

这里使用了类来表示静态表

好像有点怪，不果最主要的还是理解它的思想

①这里使用了一个结构体来保存结点的数据与用一个int的变量来保存它下一个元素的数组下表

②声明节点数组，当前长度，最大长度和一个用于保存线性表最后结点的数组下表的变量

//初始化静态链表大小等
public StaticLink() {
    this._node = new Node[this._maxLength];
    this._node[0].cur = 1;//备用链表的头一个
    this._node[this._maxLength - 1].cur = 0;//数据链表的第一个，0表示链表为空
    for (int i = 1; i < this._maxLength - 2; i++) {
        this._node[i].cur = i + 1;
    }
    this._node[this._maxLength - 2].cur = 0;//备用链表结束
    this._lastSubscript = this._maxLength - 1;
}

//自定义静态链表的大小
public StaticLink(int length) {
    if (length > 1) {
        this._maxLength = length+2;  //数组第一个和最后一个为特殊元素
    }
    this._node = new Node[this._maxLength];
    this._node[0].cur = 1;//备用链表的头一个
    this._node[this._maxLength - 1].cur = 0;//数据链表的第一个，0表示链表为空
    for (int i = 1; i < this._maxLength - 2; i++)
    {
        this._node[i].cur = i + 1;
    }
    this._node[this._maxLength - 2].cur = 0;//备用链表结束
    this._lastSubscript = this._maxLength - 1;
}

//初始化静态链表大小等

public StaticLink() {

this._node = new Node[this._maxLength];

this._node[0].cur = 1;//备用链表的头一个

this._node[this._maxLength - 1].cur = 0;//数据链表的第一个，0表示链表为空

for (int i = 1; i < this._maxLength - 2; i++) {

this._node[i].cur = i + 1;

}

this._node[this._maxLength - 2].cur = 0;//备用链表结束

this._lastSubscript = this._maxLength - 1;

}

//自定义静态链表的大小

public StaticLink(int length) {

if (length > 1) {

this._maxLength = length+2; //数组第一个和最后一个为特殊元素

}

this._node = new Node[this._maxLength];

this._node[0].cur = 1;//备用链表的头一个

this._node[this._maxLength - 1].cur = 0;//数据链表的第一个，0表示链表为空

for (int i = 1; i < this._maxLength - 2; i++)

{

this._node[i].cur = i + 1;

}

this._node[this._maxLength - 2].cur = 0;//备用链表结束

this._lastSubscript = this._maxLength - 1;

}

这里是静态链表的构造函数

用于初始化链表

主要的工作有

①确定数组的最大长度，如果没有就是用默认的大小

②使用已知的最大长度，初始化话数组的大小

③第一个0下标数组元素的cur用于保存备用链表的第一个结点，因为新建的链表，所以没有元素，除去0后，所以备用链表的数组下标为1

④数组的最后一个元素的cur用于保存数据元素的第一个结点的数组下标，这里是空链表，所以没有元素，初始化为0，表示为空链表

⑤初始化备用链表一个接一个，上一个数组元素的cur保存下一个元素的数组下标

⑥初始化备用链表的最后一个元素的cur为0表示备用链表结束

⑦初始化最后一个数据元素为特殊结点，这里是为了快速在尾部添加元素的而设立的

//获取指定位置的结点
private int GetNodeByIndex(int index) {
    if (index == 0)
    {
        return this._maxLength - 1;
    }

    if (index < 0 || index > this._currentLength) {
        Console.WriteLine("索引错误！");
        return 0;
    }
            

    int i = 1;
    int subscript = this._node[this._maxLength - 1].cur;
    if (subscript == 0) {
        Console.WriteLine("链表为空！");
        return 0;
    }
    while (i != index && this._node[subscript].cur != 0) {
        subscript = this._node[subscript].cur;
        i++;
    }

    return subscript;
}

//获取指定位置的结点

private int GetNodeByIndex(int index) {

if (index == 0)

{

return this._maxLength - 1;

}

if (index < 0 || index > this._currentLength) {

Console.WriteLine("索引错误！");

return 0;

}

int i = 1;

int subscript = this._node[this._maxLength - 1].cur;

if (subscript == 0) {

Console.WriteLine("链表为空！");

return 0;

}

while (i != index && this._node[subscript].cur != 0) {

subscript = this._node[subscript].cur;

i++;

}

return subscript;

}

很熟悉吧！

线性表我也用了这么一个方法

它是获取到指定位置的结点的数组的下标

就是要这么拗口

①先判断是否等于0，是的话就返回特殊结点（相当于头结点吧）

②判断结点是否在数据域的范围之内，不是就返回错误

③初始化一个int i = 1用于计数，初始化subscript为第一个元素结点的数组下标

④判断subscript是否为0，是的话表示为空链表

⑤用一个while循环找到第index个结点的数组下标

⑥返回这个下标

//取出备用链表的空闲空间
private int GetLeisure() {
    //得到备用链表的第一个结点
    int subscript = this._node[0].cur;
            
    //将备用链表第二个结点变第一个
    this._node[0].cur = this._node[subscript].cur;

    //返回取出的空闲节点
    return subscript;
}

//取出备用链表的空闲空间

private int GetLeisure() {

//得到备用链表的第一个结点

int subscript = this._node[0].cur;

//将备用链表第二个结点变第一个

this._node[0].cur = this._node[subscript].cur;

//返回取出的空闲节点

return subscript;

}

不同于平常的链表了

静态链表其实是两条链

一条用于保存数据，一条为备用链表（就是空闲的地方）

当我们每次插入或添加元素的时候

我们都要先从备用链表中取出一个位置来

当然，删除的时候，空闲出来的结点也要放回到空闲链表中

这里的操作看注释吧！！

//回收空闲的结点
private void BackLeisure(int subScript) {
    this._node[subScript].cur = this._node[0].cur;
    this._node[0].cur = subScript;
}

//回收空闲的结点

private void BackLeisure(int subScript) {

this._node[subScript].cur = this._node[0].cur;

this._node[0].cur = subScript;

}

回收空闲结点就是把它插入到备用链表的第一个

①首先将回收结点的下一个结点cur赋值为当前备用链表的第一个结点的下标

②指定备用链表的第一个结点为回收结点

//增加元素，在链表后面
public bool Add(T element) {

    int addSubscript = this.GetLeisure();
    if (addSubscript == 0) {
        Console.WriteLine("链表已满！");
        return false;
    }

    //找到最后一个元素
    int lastSubscript = this._maxLength - 1;

    while (this._node[lastSubscript].cur != 0) {
        lastSubscript = this._node[lastSubscript].cur;
    }
            

    //添加元素
    this._node[addSubscript].data = element;
    this._node[addSubscript].cur = 0;
    this._node[lastSubscript].cur = addSubscript;
    this._lastSubscript = addSubscript;

    this._currentLength++;

    return true;
}

//增加元素，在链表后面

public bool Add(T element) {

int addSubscript = this.GetLeisure();

if (addSubscript == 0) {

Console.WriteLine("链表已满！");

return false;

}

//找到最后一个元素

int lastSubscript = this._maxLength - 1;

while (this._node[lastSubscript].cur != 0) {

lastSubscript = this._node[lastSubscript].cur;

}

//添加元素

this._node[addSubscript].data = element;

this._node[addSubscript].cur = 0;

this._node[lastSubscript].cur = addSubscript;

this._lastSubscript = addSubscript;

this._currentLength++;

return true;

}

这里是静态链表怎么添加元素

①通过刚才的方法在备用链表中获取一个空闲的位置

②通过while循环找到链表的最后一个结点

③将要插入的数据赋值给新加结点的data

④赋值新加结点的cur为0，表示它准备成为最后一个结点了

⑤将当前最后一个结点的下一个结点cur指定为添加的结点下标

⑥最后指定最后一个结点为添加的结点，用于快速添加

⑦链表的长度+1

如果在头部添加元素的话，使用头结点，就是下标为_maxLength-1

是非常容易的，我这里就不实现了

//快速添加元素，在链表后面
public bool AddQuick(T element) {

    int addSubscript = this.GetLeisure();
    if (addSubscript == 0)
    {
        Console.WriteLine("链表已满！");
        return false;
    }

    //添加元素
    this._node[addSubscript].data = element;
    this._node[addSubscript].cur = 0;
    this._node[this._lastSubscript].cur = addSubscript;
    this._lastSubscript = addSubscript;

    this._currentLength++;

    return true;
}

//快速添加元素，在链表后面

public bool AddQuick(T element) {

int addSubscript = this.GetLeisure();

if (addSubscript == 0)

{

Console.WriteLine("链表已满！");

return false;

}

//添加元素

this._node[addSubscript].data = element;

this._node[addSubscript].cur = 0;

this._node[this._lastSubscript].cur = addSubscript;

this._lastSubscript = addSubscript;

this._currentLength++;

return true;

}

这个是用已经知道了的最后的结点来插入新结点

对比上面的步骤

它就是少了去遍历寻找到最后的结点

使用空间换时间

只要保存最后一个结点的下标

这个效果是非常好的

代码具体步骤可以参考上面的添加

//插入结点
public bool Insert(int index, T element) {
    int preSubscript = this.GetNodeByIndex(index - 1);

    //判断一下index位置的结点是否存在
    if (preSubscript == 0 || this._node[preSubscript].cur == 0) {
        return false;
    }

    int addSubscript = GetLeisure();
    if (addSubscript == 0) {
        Console.WriteLine("链表已满！");
        return false;
    }

    this._node[addSubscript].data = element;
    this._node[addSubscript].cur = this._node[preSubscript].cur;
    this._node[preSubscript].cur = addSubscript;
    this._currentLength++;
    return true;
}

//插入结点

public bool Insert(int index, T element) {

int preSubscript = this.GetNodeByIndex(index - 1);

//判断一下index位置的结点是否存在

if (preSubscript == 0 || this._node[preSubscript].cur == 0) {

return false;

}

int addSubscript = GetLeisure();

if (addSubscript == 0) {

Console.WriteLine("链表已满！");

return false;

}

this._node[addSubscript].data = element;

this._node[addSubscript].cur = this._node[preSubscript].cur;

this._node[preSubscript].cur = addSubscript;

this._currentLength++;

return true;

}

这个是静态链表的插入

①要插入结点就要首先获得插入位置的前一个结点

②判断前一个结点与插入位置结点是否存在

③在备用链表中获取一个可用的空间作为新的结点

④将数据赋值给新结点的data

⑤赋值新加结点的下一个结点cur为被插入结点

⑥将被插入结点的上一个结点的下一个结点cur赋值为新加结点

⑦最后链表的长度+1

//删除指定位置的结点
public bool Delete(int index,ref T element) {
    int preSubscript = this.GetNodeByIndex(index - 1);

    //判断一下index位置的结点是否存在
    if (preSubscript == 0 || this._node[preSubscript].cur == 0) {
        return false;
    }

    int deleteSubscript = this._node[preSubscript].cur;
    element = this._node[deleteSubscript].data;
    this._node[preSubscript].cur = this._node[deleteSubscript].cur;
    this.BackLeisure(deleteSubscript);
    this._currentLength--;
    return true;
}

//删除指定位置的结点

public bool Delete(int index,ref T element) {

int preSubscript = this.GetNodeByIndex(index - 1);

//判断一下index位置的结点是否存在

if (preSubscript == 0 || this._node[preSubscript].cur == 0) {

return false;

}

int deleteSubscript = this._node[preSubscript].cur;

element = this._node[deleteSubscript].data;

this._node[preSubscript].cur = this._node[deleteSubscript].cur;

this.BackLeisure(deleteSubscript);

this._currentLength--;

return true;

}

删除静态链表指定位置的结点

①同样的删除元素也需要获取到被删结点的上一个结点

②同样的也需要判断一下被删结点和被删结点的上一结点是否存在

③通过被删结点的上一个结点获取到被删结点的下标

④取出被删结点的数据赋值给element用于返回

⑤赋值被删结点的下一个结点cur为被删结点的下一个结点

⑥回收被删结点的下标

⑦链表的长度-1

测试

static void TestStaticLink() {
    int element = 0;

    //添加与加满测试
    StaticLink<int> s = new StaticLink<int>(3);
    s.Add(2);
    s.AddQuick(3);
    s.Add(5);
    PrintStaticLink(s, "加满三个元素后：");
    s.AddQuick(6);
    PrintStaticLink(s, "在往满的链表中添加元素：");
    Console.WriteLine();

    //删除元素测试
    PrintStaticLink(s, "删除元素前：");
    s.Delete(2, ref element);
    PrintStaticLink(s, "删除第二个元素后：");
    s.Delete(1, ref element);
    PrintStaticLink(s, "再删除第一个元素后：");
    Console.WriteLine();

    //插入元素测试
    PrintStaticLink(s, "插入元素之前：");
    s.Insert(1, 100);
    PrintStaticLink(s, "在一号前插入100后：");
    s.Insert(2, 200);
    PrintStaticLink(s, "在二号位插入200后：");
    s.Insert(3, 20);
    PrintStaticLink(s, "往已满链表插入元素：");
    Console.WriteLine();

    //索引测试
    s.Insert(5, 2);
    s.Delete(-1, ref element);
    s.Delete(100, ref element);
    s.Insert(-2, 3);
    s.GetElement(100, ref element);

}

static void PrintStaticLink(StaticLink<int> s, string text = "输出：") {
    int data = 0;

    Console.Write(text);
    for (int i = 0; i < s.GetStaticLinkLength(); i++)
    {
        s.GetElement(i + 1, ref data);
        Console.Write(data.ToString() + " ");
    }
    Console.WriteLine();
}

static void TestStaticLink() {

int element = 0;

//添加与加满测试

StaticLink<int> s = new StaticLink<int>(3);

s.Add(2);

s.AddQuick(3);

s.Add(5);

PrintStaticLink(s, "加满三个元素后：");

s.AddQuick(6);

PrintStaticLink(s, "在往满的链表中添加元素：");

Console.WriteLine();

//删除元素测试

PrintStaticLink(s, "删除元素前：");

s.Delete(2, ref element);

PrintStaticLink(s, "删除第二个元素后：");

s.Delete(1, ref element);

PrintStaticLink(s, "再删除第一个元素后：");

Console.WriteLine();

//插入元素测试

PrintStaticLink(s, "插入元素之前：");

s.Insert(1, 100);

PrintStaticLink(s, "在一号前插入100后：");

s.Insert(2, 200);

PrintStaticLink(s, "在二号位插入200后：");

s.Insert(3, 20);

PrintStaticLink(s, "往已满链表插入元素：");

Console.WriteLine();

//索引测试

s.Insert(5, 2);

s.Delete(-1, ref element);

s.Delete(100, ref element);

s.Insert(-2, 3);

s.GetElement(100, ref element);

}

static void PrintStaticLink(StaticLink<int> s, string text = "输出：") {

int data = 0;

Console.Write(text);

for (int i = 0; i < s.GetStaticLinkLength(); i++)

{

s.GetElement(i + 1, ref data);

Console.Write(data.ToString() + " ");

}

Console.WriteLine();

}

结果

发表评论取消回复

登录 注册 找回密码

登录注册找回密码