0

我正在尝试开发用于遍历表示我的应用程序中歌曲列表的数据结构的算法。

该列表包含我已经播放的所有歌曲（我的播放历史）和我将播放的其他歌曲。

Something like this (example):
  • H 歌 1
  • H 歌 2
  • H 歌 3

  • H 歌 4

  • 当前播放歌曲

  • 队列5中的Q歌

  • 队列6中的Q歌
  • 队列7中的Q歌
  • 队列8中的Q歌

我需要实现“上一个”和“下一个”按钮，这样我就可以在我的播放列表中移动。

每次播放歌曲时，它都会存储在历史记录中。

我需要有效的算法（不需要代码，只需要想法或伪代码）来解决用户播放歌曲时的所有用例。

例如，一种情况可能是：

在历史中有歌曲 1、2 和 3。现在我们播放歌曲 4，之后历史状态为 1、2、3 和 4。假设我们单击“上一个”按钮再次播放之前播放的歌曲。现在历史状态是 1、2、3、4 和 3（歌曲 3 在歌曲 4 之前播放）。再次单击“上一个”按钮，然后新的历史状态为 1、2、3、4、3 和 2。

现在假设我们单击队列中的某些歌曲，例如歌曲 6。历史状态为 1、2、3、4、3、2 和 6。现在单击“上一个”按钮应该播放歌曲 2 并将该歌曲添加到顶部历史（状态：1,2,3,4,3,2,6,2））。

如果我可以开发某种数据结构来保持我的历史状态简洁，并且如果查看历史的顶部总是会给我上一首歌，那就太好了。

因此，此数据结构不适用于该问题。它使历史状态保持简洁，但我不知道如何简单地遍历历史。

如果我更改数据结构，也许遍历算法会更简单，但是如何完成这两个请求（具有简洁的历史信息并有可能简单地获取以前播放的歌曲）？

非常感谢所有在这次讨论中做出贡献的人。很高兴现在我需要http://starvibes.com上的音乐播放器算法，这在我看来将是“下一件大事”。

4

3 回答 3

1

拥有 2 个列表绝对听起来像是要走的路 - 你的历史列表和你的主列表。

您还需要一个迭代器进入历史列表。每当您单击上一个或下一个时，您都会递减或递增该迭代器并获取该迭代器的值。如果您单击一首新歌曲，请将迭代器重置到列表的后面（最近播放的歌曲）。

每当一首歌曲开始播放时，将其添加到历史列表中（无论它是新歌还是您单击了下一首或上一首）。

您的示例：（^表示迭代器的位置）

Command   History
--------------------------------
          1, 2, 3
                ^
Play 4
          1, 2, 3, 4
                   ^
Previous
          1, 2, 3, 4, 3
                ^
Previous
          1, 2, 3, 4, 3, 2
             ^
Play 6
          1, 2, 3, 4, 3, 2, 6
                            ^
Previous
          1, 2, 3, 4, 3, 2, 6, 2
                         ^

当我想到像 Winamp 这样的东西时，你有一个列表而不是一个队列（这意味着你可以选择任何歌曲来播放，之后它将从那里继续播放）（除了它也有一个单独的队列，但那在旁边观点）...

除非您使用随机播放模式，否则您可能还希望在主列表中添加一个迭代器，这将指示最新的新歌曲（即手动选择的最后一首歌曲或单击next历史列表末尾的时间）。

这将允许您在单击next历史列表末尾的时间后，转到主列表中的下一首歌曲。

于 2013-08-29T15:35:47.173 回答
0

我只会索引所有的歌曲。

然后存储当前歌曲和最后一首歌的值。

这将导致遍历大量歌曲时的 O(1) 速度。比链接列表好得多。

例如 next() 和 previous() 将只是一个简单的 ++ 和 -- 在当前歌曲索引上。as last 将只存储最后一首歌曲的索引。

看起来很简单。

插入 - 添加新歌曲（++songlistsize）；O(1)

删除 - for(i = index; i < songlistsize; i++) songindex[i]--; 0(n)

move - 交换歌曲索引。O(1)

于 2013-08-29T19:51:14.330 回答
0

您可以创建自己的数据结构，灵感来自 LinkedList，例如，其中每个元素都知道下一个和前一个元素。

在此结构中存储您的历史记录、当前元素，然后是下一个元素。当用户播放一首新歌曲时，您应该能够将其快速插入列表中。

然后跟踪当前（播放条目）当用户单击上一个时，播放 currentEntry.previous() 当用户单击下一个时，播放 currentEntry.next()

当用户选择其他歌曲时，将歌曲插入 currentEntry 和 currentEntry.next() 之间，然后播放...

干杯

于 2013-08-29T19:37:35.387 回答