• 数据结构：静态链表（编程技巧）

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

    一、理解

    920f535ed6fb4749aa0ec28c423e3e43.png
    如果有些程序设计语言没有指针类型，如何实现链表？
    d35a05dc4dbc47c7a957df5068a2b4b8.png
            在使用指针类型实现链表时，我们很容易就可以直接在内存中新建一块地址用于创建下一个结点，在逻辑上，我们好像链表是顺序的一样，我们根本不用管他们在内存中是如何存储的，直接“顺序”地遍历即可。
            我们用静态链表，使用数组存储元素和下标，也想实现逻辑上是顺序的。实际上，我们只需要用数组模拟指针，我们在创建一个新结点时，只需要找到一块“空地”即可创建成功，我们在保证data不动的情况下，直接修改next数组就能实现指针的变换，即一旦创建成功数据的值就存在一个固定的位置，而是通过改变“存指针的数组”来改变指向。我们也不需要去考虑到底存在哪，逻辑上一样可以想象成和普通链表一样的。可以模拟为： 
    1. int new_place=find_empty();
    2. data[new_place]=new_data;//利用空地“创建新节点”并赋值
    3. next[last_place]=new_place;//链表中最后一个结点指向该结点
    4. next[new_place]=-1;//新建结点指向为-1

    同理，实现双向循环静态链表，使用left和right数组的下标就可以实现两个左右指针。

    二、例题

    例题：有若干个盒子，从左至右依次编号为
    1,2,3,...,n。可执行以下指令（保证X不等于Y）：
    ➢L X Y表示把盒子X移动到盒子Y左边（如果X
    已在Y左边，则忽略该指令）。
    ➢R X Y表示把盒子X移动到盒子Y右边（如果X
    已在Y右边，则忽略该指令）。
    2c126bf2cd694be6a3314cca95b4ddcc.png
    这里使用双向循环链表来实现。 
    1. vector<int> data(n+1);//留出一个头结点
    2. vector<int> left(n+1);
    3. vector<int> right(n+1);
    4. for(int i=1;i<=n;++i){
    5.     data[i]=i;//创建结点并赋值    
    6.     if(i!=1)
    7.         left[i]=i-1;//初始化左指针指向前一个结点(用下标模拟指针)
    8.     else left[i]=n;
    9.     if(i!=n)
    10.         right[i]=i+1;//初始化左指针指向后一个结点(用下标模拟指针)
    11.     else right[i]=1;
    12. }
    13. while(cin>>Direct>>x>y){//x和y虽然是盒子编号，但是data[x]就是盒子x，所以left[x]就是盒子x左边指向的盒子
    14.     if(Direct=='L'||Direct=='R')
    15.     if(Direct=='L'){
    16.         while(right[x]!=y){//右边指向的盒子不等于y  1--2--1--2
    17.             right[left[x]]=right[x];
    18.             left[right[x]]=left[x];
    19.             left[x]=right[x];
    20.             right[x]=right[left[x]];
    21.             left[right[x]]=x;
    22.             right[left[x]]=x;
    23.         }
    24.     }else{
    25.         while(left[x]!=y){
    26.             right[left[x]]=right[x];
    27.             left[right[x]]=left[x];
    28.             right[x]=left[x];
    29.             left[x]=left[left[x]];
    30.             right[left[x]]=x;
    31.             left[right[x]]=x;
    32.         }
    33.     }
    34. }
    35. int i=1;
    36. while(i!=-1){
    37.     cout<<"盒子编号："<
    38.     i=right[i];
    39. }

     

  • 相关阅读:
    KVM之QEMU Q35仿真程序-尚文网络xUP楠哥
    python基于flask实现swagger在线文档以及接口测试
    Go语言类型与接口的关系
    基于antd Input组件封装最小值和最大值输入，只能输入自然数
    【C#】使用Windows窗体实现链接跳转功能
    Prometheus系列（一）安装
    教你轻松保存视频号里的视频到相册
    解决主机无法通过网络访问虚拟机的问题
    从内核角度看网络包发送流程
    【Docker 那些事儿】如何安全地停止、删除容器
  • 原文地址：https://blog.csdn.net/m0_63997099/article/details/136626124