时间戳

首页 > 解决方案 > 如何遍历双向链表（环）的每个 SECOND 元素？

c++ - 如何遍历双向链表（环）的每个 SECOND 元素？

问题描述

RING——线性数据结构，其中终点指向结构的起点。它也称为循环缓冲区、循环队列或循环缓冲区。

我有一个函数要写。它的目的是从原始 RING 生成另一个 RING 结构，但它的长度已定义，问题是它必须是原始 RING 的每个 SECOND 元素。

例子：

原环= 1,2,3,4,5

函数 newRing 被调用：newRing (originalRing, nRing, len1=5)

nRing=1,3,5,2,4

（解释：'1' 是 RING 的第一个元素。每秒意味着我取 3、5 ......但这是 RING，所以它像 1,2,3,4,5,1,2,3， 4,5,... 函数说 nRing 的长度必须为 5，所以我接下来取每个元素：2,4。最后它给出 1,3,5,2,4)

我正在使用迭代器（我必须，学校项目）。

iterator i1 = nRing.begin(); //--- .begin() points to the 'beginning' of the Ring
if (originalRing.isEmpty()){ //---whether originalRing is empty or not
  return false;}

if (originalRing.length()==1){ //--- if originalRing no. of elements is 1, returns that Ring
  return originalRing;
}
if (len1<=0) //--- doesnt make sense
{return false;}

if(!i1.isNULL()) //--- checks whether iterator is null
    {
        for(int i = 0; i < len1; i++)
        {
            nRing.insertLast(i1.getKey()); //insert the element to the end of the Ring
            i1++;

        }
    }

所以在这里，我要问的是 i1++ --- 它一个一个地迭代元素。

我的问题是如何使用定义为每个第二个元素附加的迭代器来定义一个循环？

标签： c++iteratordoubly-linked-list

解决方案

你可以std::stable_partition用来做这个。它将划分环形缓冲区中的元素，以便 lambda 返回 true 的元素位于返回 false 的元素之前。您可以创建一个有状态/可变 lambda 来为每次迭代切换真/假。

#include <iostream>
#include <vector>    // std::vector
#include <algorithm> // std::stable_partition

int main() {
    std::vector<int> RING = {1, 2, 3, 4, 5};
    for(const auto& v : RING) std::cout << v << " ";
    std::cout << "\n";

    for(int i = 0; i < 4; ++i) {

        std::stable_partition( RING.begin(), RING.end(),
            [toggle = false](const auto&) mutable {
                return toggle ^= true; // false becomes true and vice-a-versa
            }
        );

        for(const auto& v : RING) std::cout << v << " ";
        std::cout << "\n";
    }
}

输出：

1 2 3 4 5
1 3 5 2 4
1 5 4 3 2
1 4 2 5 3
1 2 3 4 5

推荐阅读