数据结构:静态链表(编程技巧)



链表的元素用数组存储, 用数组的下标模拟指针。

一、理解

在这里插入图片描述
如果有些程序设计语言没有指针类型,如何实现链表?
在这里插入图片描述
  在使用指针类型实现链表时,我们很容易就可以直接在内存中新建一块地址用于创建下一个结点,在逻辑上,我们好像链表是顺序的一样,我们根本不用管他们在内存中是如何存储的,直接“顺序”地遍历即可。
  我们用静态链表,使用数组存储元素和下标,也可以实现逻辑上是顺序的。实际上,我们只需要用数组模拟指针,我们在创建一个新结点时,只需要找到一块“空地”即可创建成功,我们在保证data不动的情况下,直接修改next数组就能实现指针的变换,即一旦创建成功数据的值就存在一个固定的位置,而是通过改变“存指针的数组”来改变指向。我们也不需要去考虑到底存在哪,逻辑上一样可以想象成和普通链表一样的。可以模拟为:

int new_place=find_empty();//找到空地(伪代码) 
data[new_place]=new_data;//利用空地“创建新节点”并赋值
next[last_place]=new_place;//链表中最后一个结点指向该结点
next[new_place]=-1;//新建结点指向为-1

  同理,实现双向循环静态链表,使用left和right数组的下标就可以实现两个左右指针。当然我们可以将其合并为一个结构体,由于空间的局部性,它们可能会被同时使用因此用结构体可能更快:

struct node{
	int data;
	int next;
};
node[new_place].data=new_data;
node[last_place].next=new_place;
node[new_place].next=-1;//新建结点指向为-1

  在图论的邻接表中使用非常明显(链式前向星)可跳过这一段:

while(cin>>Vertex>>edge>>cos){//假定输入都是正确的,没有重边
    //为了复杂化,我们先找到边链表的最后一个结点
    int adj=head[Vertex];
    if(adj!=-1)
        while(next[adj]!=-1){
            adj=next[adj];
        }
    /*创建一个新结点 其之后无指向即next=-1*/
    VerName.push_back(edge);
    next.push_back(-1);
    cost.push_back(cos);
    /*-adj为Vertex边链表的最后一个元素-*/
    if(adj!=-1)
        next[adj]=next.size()-1;//VerName.size()-1、cost.size()-1均可 就是指向最后一个嘛。
    if(adj==-1){//只可能是顶点还没有边
        head[Vertex]=next.size()-1;
    }
}

不过最终需要通过具体语义来实现。

二、静态链表

  静态链表是一种在数组上模拟链表操作的数据结构,它利用数组的索引来代替指针,以此来实现链表的节点间的连接。静态链表特别适合在不支持指针的环境中使用,或者当内存空间非常有限且不允许动态分配内存时的场景。

2.1、结构定义

静态链表通常通过结构体数组来实现。每个结构体元素至少包含两个部分:

  • 数据域:存储链表节点的数据。
  • 游标(或称为next索引):存储下一个节点的索引位置。

在C++中,静态链表的节点可以这样定义:

struct Node {
    int data; // 数据域
    int next; // 游标,存储下一个元素的索引
};

2.2、静态链表的初始化

静态链表的初始化涉及到设置一个固定大小的数组,并初始化next索引。一般会有一个特殊的头节点(head),其next索引指向链表的第一个元素,如果链表为空,则指向-1或链表的末尾标识。

2.3、操作

静态链表的基本操作与普通链表类似,包括插入、删除和查找等,但操作方式通过数组索引来实现。

  • 插入操作:在指定位置插入一个新的节点,需要修改该位置前一个节点的next值指向新节点,新节点的next值指向原先该位置的节点。
  • 删除操作:删除指定位置的节点,需要修改该位置前一个节点的next值,让它直接指向被删除节点的下一个节点。
  • 查找操作:从头节点开始,逐个跟随next索引遍历直到找到目标节点。

2.4、示例

假设我们有一个静态链表来存储整数,可以这样表示:

Node nodes[MAX_SIZE]; // 静态链表的数组表示
int head = -1; // 初始化头节点的next索引为-1,表示链表为空

2.5、优点

  • 空间利用率高:在连续的内存空间中模拟链表,避免了指针的额外空间消耗。
  • 适用于静态存储管理:当内存分配不允许使用动态分配时,静态链表是一种有效的选择。

2.6、缺点

  • 固定大小:静态链表的最大大小在编译时就确定了,这限制了其动态扩展的能力。
  • 操作复杂度:与动态链表相比,静态链表在插入和删除操作时可能需要更多的步骤来更新索引。

静态链表是一种特殊场景下的解决方案,它展示了数据结构在不同约束下的灵活应用。在现代编程实践中,由于动态内存管理的广泛支持,静态链表的使用场景相对较少,但理解其原理对学习数据结构的基本概念非常有帮助。

三、例题

例题:有若干个盒子,从左至右依次编号为
1,2,3,…,n。可执行以下指令(保证X不等于Y):
➢L X Y表示把盒子X移动到盒子Y左边(如果X
已在Y左边,则忽略该指令)。
➢R X Y表示把盒子X移动到盒子Y右边(如果X
已在Y右边,则忽略该指令)。

这里使用双向循环链表来实现。

vector<int> data(n+1);//留出一个头结点
vector<int> left(n+1);
vector<int> right(n+1);
for(int i=1;i<=n;++i){
    data[i]=i;//创建结点并赋值    
    if(i!=1)
        left[i]=i-1;//初始化左指针指向前一个结点(用下标模拟指针)
    else left[i]=n;
    if(i!=n)
        right[i]=i+1;//初始化左指针指向后一个结点(用下标模拟指针)
    else right[i]=1;
}
while(cin>>Direct>>x>y){//x和y虽然是盒子编号,但是data[x]就是盒子x,所以left[x]就是盒子x左边指向的盒子
    if(Direct=='L'||Direct=='R')
    if(Direct=='L'){
        while(right[x]!=y){//右边指向的盒子不等于y  1--2--1--2
            right[left[x]]=right[x];
            left[right[x]]=left[x];
            left[x]=right[x];
            right[x]=right[left[x]];
            left[right[x]]=x;
            right[left[x]]=x;
        }
    }else{
        while(left[x]!=y){
            right[left[x]]=right[x];
            left[right[x]]=left[x];
            right[x]=left[x];
            left[x]=left[left[x]];
            right[left[x]]=x;
            left[right[x]]=x;
        }
    }
}
int i=1;
while(i!=-1){
    cout<<"盒子编号:"<<data[i]<<endl;
    i=right[i];
}

相关推荐

  1. 数据结构

    2024-04-02 14:12:06       18 阅读

最近更新

  1. leetcode705-Design HashSet

    2024-04-02 14:12:06       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-02 14:12:06       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-02 14:12:06       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-02 14:12:06       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-02 14:12:06       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-02 14:12:06       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

    2024-04-02 14:12:06       7 阅读

热门阅读

  1. ES6中的Map与Set

    2024-04-02 14:12:06       3 阅读
  2. C语言中向函数中传递函数指针的方法

    2024-04-02 14:12:06       4 阅读
  3. 简单设计模式讲解

    2024-04-02 14:12:06       4 阅读
  4. C++命名空间详解

    2024-04-02 14:12:06       4 阅读
  5. 【Ubuntu】可配置环境变量位置

    2024-04-02 14:12:06       5 阅读