c++ - 双链循环表c++

Question

我想为我正在制作的小游戏创建双向循环列表。我希望它成为一个列表，因为它在添加和删除新元素时提供了速度。如果我想使用动态表，任何类型的添加/删除操作都需要我重写整个表，这会严重降低程序速度(至少从我的理解来看)。该解决方案的唯一问题是，我并不完全理解如何做这样的列表；)

struct parts{
    char name;
    parts *next, *prev;
    parts *connected;
};

void add_part(struct parts **head, struct parts **tail, char name) 
{
    struct parts *a;
    a = (struct parts*)malloc(sizeof(struct parts));
    a->name = name;
    if ((*head) == NULL && (*tail) == NULL)
    {
        *head = a;
        *tail = a;
        a->next = NULL;
        a->prev = NULL;
    }
    else
    {
        a->next = *head;
        a->prev = NULL;
    }
}

void display(parts *head) {
    parts *temp = head;
    while (temp != NULL){
        cout << temp->name << endl;
        temp = temp->next;
    }
}

int main ()
{
    char names[] = "ABCDEFGHIJKLMNOPRSTUWXYZ";
    segmenty *head = NULL;
    segmenty *tail = NULL;
    int count_parts;
    cin >>count_parts;

    for (int i=0; i < count_parts && i<24; i++){
        add_part(&head, &tail, names[i]);
    }
    display(head);
    return 0;
}

我希望用户能够做的是输入他想要的元素数量，然后我想用字母表中的字母命名每个元素并将它们放入我的列表中，以便每个元素都连接到元素在它之前和之后，tail 连接到 head(我希望列表是循环的)。不幸的是，我的指针技能有点缺乏...... *connected 是我想用于当前在地面上的元素的指针(只有一个元素可以一次接触地面)用于删除或添加新元素等用途，例如如果元素命中陷阱，我想删除那个特定元素，而不是任何其他元素。

Answer 1

除非您必须练习和展示指针技能，否则请查看此处描述的 std::list 容器:std::list - cppreference.com .从根本上说，struct parts 和所有指针操作都将消失。 std::list 容器可以声明为每个元素存储一个 char。它还为您完成所有指针操作和内务处理。 connected 指针在 std::list 代码示例之后讨论。

如果在测试存储单个 char 后发现字符串更好，则修改声明 std::list 的 typedef 行以包含 std::string 代替。

对删除函数的引用:std::list::remove, remove_if .

插入函数引用:std::list::insert .这里不演示插入，但是有八种不同的重载版本。

四种时间复杂度恒定的方法:
1.添加到列表的前端或末尾，使用:std::list::push_front和 std::list::push_back .
2. 从前面或后面删除单个元素:std::list::pop_front和 std::list::pop_back .

示例声明和简单操作如下。为清楚起见，std::list 如下所示，但 std:: 不是编译和构建所必需的(例如，using namespace std;存在):

#include <list>
#include <iostream>
using namespace std;

//
// Other headers as needed, then a sample main...
//
main (int argc, char * argv[])
{
    const int ciNamesMax = 26;
    char names[ciNamesMax] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 
                              'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 
                              'U', 'V', 'W', 'X', 'Y', 'Z' };


    typedef std::list <char> tdCharNames;
    tdCharNames theNames(names, names + ciNamesMax);


    //
    // Print the list contents with zero modifications to the elements
    //
    cout << "The doubly linked list of chars contains the following values.";
    cout << endl;
    int j = 1;
    for (tdCharNames::iterator i = theNames.begin(); i != theNames.end(); i++) 
    {
       cout << "Element " << j << " is: " << (*i) << endl;
       j++;
    }

    //
    // Use the built-in remove function in two different ways to demonstrate
    // ease of removing an element or elements.
    //
    theNames.remove('B');

    //
    // Note that the C++11 lambda function is used as the predicate to 
    // remove the 'G' and 'P' elements.
    //
    theNames.remove_if( [](char c) { return (c == 'G' || c == 'P'); } );
    j = 1;
    for (tdCharNames::iterator i = theNames.begin(); i != theNames.end(); i++) 
    {
       cout << "Element " << j << " is: " << (*i) << endl;
       j++;
    }

} // end main

上面 struct parts 内的 connected 指针将成为一个声明的单个 char 变量，其值是必要的(例如，来自用户的输入)和 cin)。然后 connected 变量将被传递给 std::list::remove 函数。例如，这是一个代码片段:

char connected;
cout << "Enter the ground location (A-Z): ";
cin >> connected;

//
// Other logic, user messages, error checking, and so on.
// Then, call the std::list::remove method as desired.
//
theNames.remove(connected);

切换到存储 std::string 的示例:

const int ciNamesMax = 26;
std::string names[ciNamesMax] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", 
                                 "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", 
                                 "U", "V", "W", "X", "Y", "Z" };


//
// May want to modify the typedef name to better indicate std::string.
// Leaving the typedef as before to demonstrate the simplicity of changing
// the element type being stored.  Keep in mind that the lambda and other 
// logic looking for a char may be affected.  It is up to the reader to test
// and adjust the implementation accordingly.
//
typedef std::list <std::string> tdCharNames;
tdCharNames theNames(names, names + ciNamesMax);