c++如何从链表中随机挑选项目

Question

我正在试验一个游戏程序。我试图有一个随机数量的项目产生。代码将多次生成相同的项。我可以设置一系列开关语句，让玩家浏览多个搜索区域，从而在每个区域获得一个新的随机道具，但我想知道如何处理我在这里做错的地方。没有什么比错误更能帮助人学习了。

我使用了一个结构体，一个链表，一个类和指针。

//genItem.h
#pragma once
struct item
{
    char itemName[50];
    int itemDamage;
    int itemStability;
    item* Next;
};
class genItem
{
public:
    genItem(void);
    ~genItem(void);
    int count();
    int add_item(item* currentItem);
    void generate_item(int d2, int s2);
    item *Head;
    item *Retrieve(int pos);
private:
    int size;
    int damage;
    int stability;
};
//genItem.cpp
#include <iostream>
#include "genItem.h"
#include <stdio.h> // NEED THIS FOR NULL TO WORK
#include <ctime>
using namespace std;
genItem::genItem(void)
    :size(0), Head(NULL)
{
}

genItem::~genItem(void)
{
}
int genItem::count()
{
    return size;
}
int genItem::add_item(item *thisItem)
{
    item *itemObject = new item;
    itemObject = thisItem;
    itemObject -> Next = Head;
    Head = itemObject;
    return size++;
}
item *genItem::Retrieve(int position)
{
    item *current = Head;
    for (int i = count() -1; i > position && current != NULL; i--)
    {
        current = current -> Next;
    }
    return current;
}
void genItem::generate_item(int d2, int s2)
{
    genItem *listItems = new genItem();
    item *listItem;
    srand (time(0));    
    int rn = 0;
    int total_in_cat = 10;
    int cat_item = 0;
    int rand_dam = rand();
    int rand_sta = rand();
    int per = rand();
    int base_d2 = 10;
    int base_s2 = 10;
    int rand_dam2 = rand();
    int rand_sta2 = rand();
    cat_item = per % total_in_cat;
    d2 = (rand_dam2 % base_d2) +2;
    s2 = (rand_sta2 % base_s2) + 2;
        if (rn == 0) // mushrooms
        {
            if(cat_item == 0)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "an earthball mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 1)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a devil's bolete mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 2)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a rotting jack o'lantern mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 3)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a fly agaric mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 4)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a poison pie mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 5)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a mature deathcap mushroom");
                listItem -> itemDamage = 50;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 6)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a shaggy inkcap mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 7)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a bleeding milkcap mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 8)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a velvet shank mushroom");
                listItem -> itemDamage = d2;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
            else if (cat_item == 9)
            {
                listItem = new item;
                strcpy_s(listItem -> itemName, "a destroying angel mushroom");
                listItem -> itemDamage = 100;
                listItem -> itemStability = s2;
                listItems -> add_item(listItem);
            }
        } //end group 0
    damage = d2;
    stability = s2;
    int j = rand();
    for (int j =0; j <= 3; j++)
    {
        cout << "tJ equals: " << j << endl;
    for (int i =0; i < listItems -> count(); i++)
        {   
            item *found = listItems -> Retrieve(i);
            cout << "tYou have found " << found -> itemName << "." << endl;
            cout << "tIt has a damage rating of " << found -> itemDamage;
            cout << " and a stability rating of " << found -> itemStability << "."<< endl;
            cout << endl;
        }
    }
}
//main.cpp
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <ctime>
#include "genItem.h"
using namespace std;
int main()
{   
genItem *findItem = new genItem;
int d2 = 0;
int s2 = 0;
findItem ->generate_item(d2, s2);
cout << "t"; system("pause");
return 0;
}

Answer 1

现在你发布了更多的源代码，我可以给你更多的信息，但这将是一个很长的一个。这也是一个非常局部化的问题，所以我将尽可能广泛地回答这个问题，以便这个答案对更多人有用，而不仅仅是你。

<标题> 普遍问题

首先，让我们来解决你的主要问题——只显示一种项目而不是几种不同的项目。实际上，这可以简单地通过调试程序来解决——甚至手动调试，例如。跟踪，程序运行的位置。

*** main.cpp, 17 ***
findItem ->generate_item(d2, s2);
(...)
*** getItem.cpp, 49 ***
int rn = 0;
...
int cat_item = 0;
...
    if (rn == 0) // mushrooms
    {
        if(cat_item == 0)
        {
            listItem = new item;
            strcpy_s(listItem -> itemName, "an earthball mushroom");
            listItem -> itemDamage = d2;
            listItem -> itemStability = s2;
            listItems -> add_item(listItem);
        }
...
*** getItem.cpp, 148 - continuing ***
damage = d2;
stability = s2;
int j = rand();
for (int j =0; j <= 3; j++)
{
    cout << "tJ equals: " << j << endl;
for (int i =0; i < listItems -> count(); i++)
    {   
        item *found = listItems -> Retrieve(i);
        cout << "tYou have found " << found -> itemName << "." << endl;
        cout << "tIt has a damage rating of " << found -> itemDamage;
        cout << " and a stability rating of " << found -> itemStability << "."<< endl;
        cout << endl;
    }
}

下面是程序在我指定的行中所做的:

• 调用findItem -> generateItem;
• 设置rn为0,cat_item为0
• 基于rn和cat_item添加单项到列表
• 尝试显示列表中的随机元素，但由于getItem:: reveve内部的复杂条件，它总是返回Head(它是列表中唯一的元素)。

在循环中不向list中添加元素，因此只显示一个元素也就不足为奇了。

<标题> 建筑问题

在这种情况下，使用列表是一个糟糕的主意。您需要通过索引轻松访问元素，在这种情况下，std::vector会更好(更快，更易于维护和使用)。阅读更多关于c++ 11中不同数据结构的用法。

• 你有一些严重的问题在你的genItem类。它看起来像一个存储所有可用项的存储库，但随后您在其中做了一些非常可疑的事情，例如:

  void genItem::generate_item(int d2, int s2)
  {
      genItem *listItems = new genItem();
  

  (在这种情况下)在自身内部创建类实例是没有意义的。如果genItem应该作为项目的容器/存储库，您应该在main.cpp中实例化它(或者负责这个对象的生命周期的人)并在那里使用它。打印指令看起来也像在与编译器的战斗中留下的硬核调试代码。

你的代码是可恢复的，但这将需要很多工作，我将留给你。阅读更多语法/实现问题。

语法/实现问题

• 你分配对象并留下它们:看起来你在Java或c#中编写后转向c++。例如:

  int main()
  {   
      genItem *findItem = new genItem;
      int d2 = 0;
      int s2 = 0;
      findItem ->generate_item(d2, s2);
      cout << "t"; system("pause");
      return 0;
  }
  

  您实例化genItem，在findItem变量中存储指向其实例的指针，但然后就不管它了。以这种方式留下的活动对象被认为是内存泄漏:没有人会为您释放内存，这个对象将一直保持活动，直到您的程序终止，即使您不再需要它。请注意，您在许多地方都编写了这样的代码。

• 命名不清楚。d2, s2是什么?为什么是d, s ?为什么是2 ?此时磁盘空间非常便宜，没有理由将变量名保持得如此简短和非描述性。给它们适当的名称(我猜，在这个例子中，它们应该被命名为:newDamage和newStability或类似的
)

• 你的代码太复杂了。这个循环:

  item *genItem::Retrieve(int position)
  {
      item *current = Head;
      for (int i = count() -1; i > position && current != NULL; i--)
      {
          current = current -> Next;
      }
      return current;
  }
  

  可以这样写(例如):

  item *genItem::Retrieve(int position)
  {
      item * result = Head;
      while (result != nullptr && position > 0)
      {
          result = result->Next;
          position--;
      }
      return result;
  }
  

  第二个版本做了同样的事情(实际上它工作正确，与你的方法相反)，并且比第一个版本可读性更好。

• 不要用C写:

  genItem::~genItem(void)
  

  在c++中是有效的，但首选的版本是:

  getItem::~getItem()
  

• 尽量不要使用特定于平台的解决方案，例如:系统("暂停");您的程序可能不允许运行外部命令或程序，并将崩溃-尽管事实上，您运行外部命令来执行如此简单的任务。如果您想阻止程序退出，请使用其他解决方案，如getchar(或查找SO，如何立即停止程序退出)。

<标题> 简单例子

这里有一个例子，你的问题可能会更容易解决:

#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
class Item
{
public:
    std::string Name;
    int Damage;
    int Stability;
    Item(std::string newName, int newDamage, int newStability)
        : Name(newName), Damage(newDamage), Stability(newStability)
    {
    }
};
class ItemRepository
{
private:
    std::vector<Item> items;
public:
    ItemRepository()
    {
        Item item1("Mushroom", 10, 20);
        items.push_back(item1);
        Item item2("Rock", 100, 30);
        items.push_back(item2);
        Item item3("Piece of paper", 5, 2);
        items.push_back(item3);
    }
    const Item & GetRandomItem()
    {
        int index = rand() % items.size();
        return items[index];
    }
};
int main()
{   
    ItemRepository itemRepo;
    for (int i = 0; i < 10; i++)
    {
        const Item & item = itemRepo.GetRandomItem();
        std::cout << item.Name << ", Damage: " << 
            item.Damage << ", Stability: " << 
            item.Stability << "n";
    }
    getchar();
}

Answer 2

其他人已经指出链表可能是不合适的-理论上它可能是一个合适的选择，但(1)对于冒险游戏来说这似乎不太可能，(2)无论如何这似乎都是过早的优化。

然而，您可以从链表中随机选择n个项目，在单遍中，每个项目以相同的概率出现。你需要提前知道有多少项，所以如果你不知道，在你选择之前，你需要额外的一轮来计算总数。

对于第一个项目，您可以很容易地确定该项目被包含的概率- n/N，其中n是您想要的项目数量，N是列表中的项目数量。因此，在此基础上选择是否包含或排除该条目。

对于列表的其余部分，您要么仍然需要n项，要么需要n-1项，在剩余的N-1项中。这是相同的基本问题，只是列表更短。所以递归。因为这是尾部递归，所以它作为循环也可以很好地工作。

直觉可能暗示概率是错误的——第二个项目的概率不应该取决于第一个项目是否被选中——但在这种情况下直觉是错误的。算一算，这是完美的。为了让您放心，在选择第一个项目之前，请考虑第二个项目被选中的概率。

第一项要么被选中，要么不被选中。如果第一个被选中，第二个被选中的概率是(n-1)/(n-1)。如果第一个项目没有被选中，第二个项目被选中的概率是n/(n -1)。所以我们有…

P2 = (n/N)(n-1/N-1) + ((N-n)/N)(n/N-1)
   = (n^2 - n)/(N^2 - N) + (nN - n^2)/(N^2 - N)
   = (nN - n)/(N^2 - N)
   = n(N-1)/(N^2 - N)
   = n/N        because N^2 - N = N(N-1)

类似的逻辑适用于列表中的所有位置，只要它实际上是可能的(例如n <= N)。

我相信这是一个有名的算法，有名字，但我现在不记得名字了