希望你们都做得很好
我刚刚得到了一个通过使用 singularLinkedList 创建字典的项目，每个节点都必须按排序顺序保存数据(例如，第一个节点保存"A"字符单词，然后在该特定节点中，单词将以排序形式)。
我没有想出任何类型的解决方案，感谢一点帮助
一个有趣的问题。让我看看，我该如何帮助你。
起先。让我们检查和分析您的要求。
- 你需要一个排序的单向链表
- 此外，还需要一个字典，也实现为排序链表
- 每个节点必须将数据(单词的大写字母)作为键 键
- 的关联值再次是单词列表，从键开始
所以，显然我们需要两种数据结构
- 用于保存字符串的单向链表
- 字典，即关联容器，可以保存键和关联的值。在这里，从数字 1 开始的列表
对于设计，我们将首先考虑如何创建单向链接排序列表。通常，单链表由节点组成，包含 2 个主要项目
- 数据(可以是任何内容，包括结构、数组或只是基元数据类型)
- 指向单向链表中下一个节点的"下一个"指针
让我们展示一些带有整数数据的演示列表的简单图片。
Head Pointer: pointer to Node 1
Node 1 data: 10 next-pointer: pointer to Node 2
Node 2 data: 11 next-pointer: pointer to Node 3
Node 3 data: 12 next-pointer: pointer to Node 4
Node 4 data: 13 next-pointer: nullptr (empty, point to nothing)
如您所见。节点的下一个指针指向列表中的下一个节点，因此称为"链表"。而且你总是可以找到任何节点，从头部指针开始，然后跟随所有下一个指针。
节点的简单结构可能如下所示：
// A sorted singly linked list forstd::string + special iterator
class SortedSingleLinkedList {
// Structure of one node
struct Node {
// The data in the dictionay. A std::string
std::string value{};
// Pointer to next node
Node* next{ nullptr };
};
// Start of list
Node* head{ nullptr };
对于普通的非排序列表，向列表中添加元素很简单。我们使用网络数据创建一个新节点。然后，我们检查列表是否为空。意思是，是头指针 == nullptr。在这种情况下，我们将新节点分配给头节点指针。
如果链表中已经有元素，那么我们只需遵循所有下一个指针，直到找到一个 nullptr 并只挂在新节点而不是最后一个 nullptr 中。这很简单。
如果我们想要一个排序列表，那么我们将在正确的位置插入新节点。
我们必须区分 3 种情况：
- 列表为空。然后新节点将成为头节点 新节点数据
- 小于头节点数据。然后，我们将新节点分配给头节点，并将以前的头节点分配给新节点头指针。也很简单。
- 最后但并非最不重要的一点是，我们将通过下一个指针遍历列表并检查数据是否小于下一个数据。在这种情况下，我们需要插入元素。
示例：我们想在下面的列表中插入一个数据为 15 的新节点
Head Pointer: pointer to Node 1
Node 1 data: 10 next-pointer: pointer to Node 2
Node 2 data: 11 next-pointer: pointer to Node 3
Node 3 data: 21 next-pointer: pointer to Node 4
Node 4 data: 22 next-pointer: nullptr (empty, point to nothing)
然后，我们使用下一个指针和下一个数据循环访问列表。如果我们在节点 3 并检查下一个节点(节点 3)，那么我们会发现新节点 (15) 的数据小于下一个节点的数据(注 3，数据 21)。
我们需要在节点 2 后面和节点 3 之前插入新节点。为了实现这一点，我们将节点 2 的下一个指针(之前指向节点 3：new-node->next-pointer = current-node->next pointer
在此之后，我们将新节点的地址分配给当前节点(节点 2)的下一个指针。Node 2->next-pointer = new-node.然后是旧地址
在一个小
Head Pointer: pointer to Node 1
Node-new data: 15 next-pointer: nullptr (empty, point to nothing)
Node 1 data: 10 next-pointer: pointer to Node 2
Node 2 data: 11 next-pointer: pointer to Node 3
Node 3 data: 21 next-pointer: pointer to Node 4
Node 4 data: 22 next-pointer: nullptr (empty, point to nothing)
// Step 1
Node-new data: 15 next-pointer: pointer to Node 3
// Step 2
Node 2 data: 11 next-pointer: pointer to Node-New
// which will result in:
Node 1 data: 10 next-pointer: pointer to Node 2
Node 2 data: 11 next-pointer: pointer to Node-new
Node-new data: 15 next-pointer: pointer to Node 3
Node 3 data: 21 next-pointer: pointer to Node 4
Node 4 data: 22 next-pointer: nullptr (empty, point to nothing)
现在这应该是可以理解的。这可以很容易地实现，如上面的设计所示。示例代码：
// Main function. Insert a new value into the list, but sorted. So, insertion sort
Node* insertSorted(const std::string& value) {
// Create a new node
Node* newNode = new Node({ value });
// If the list is empty
if (head == nullptr) {
// Then now the start of the list will be the new node
head = newNode;
}
else {
// There was already data here. Initialize an iterator pointer
Node* current = head;
// If the new element is smaller than the head element
if ( newNode->value < head->value) {
// Then we nmake the new element the head element
newNode->next = head;
head = newNode;
}
else {
// Iterate over elements and check, if the new element is samller then the next element
while ((current->next != nullptr) and (current->next->value < newNode->value))
current = current->next;
// So, now we found the element, after which we need to insert the new element
newNode->next = current->next;
current->next = newNode;
}
}
return newNode;
}
因此，您现在可以添加许多都很容易的附加功能。喜欢isEmpty()或size()或find.或者，无论您需要什么。
为了更容易地输出和迭代，我为此类添加了完整的迭代器功能，以便能够轻松迭代所有元素，例如在循环中。
接下来是字典。
我们将以与上述基本相同的方式实现字典。因此，也作为单独排序的列表。我们可以重用上面的所有机制，它将以相同的方式工作。
主要区别在于节点中的数据现在由 2 项组成：
- 关键。在我们的例子中，一个角色
- 值，在我们的例子中是上面定义的字符串的单向链接排序列表
我们将字母分配给一个键(我们将使用大写字母作为键)，一个带有单词(字符串)的列表。
为了实现这一点，我们创建了一个特殊的索引运算符，类似于C++的std::map或std::unordered_map运算符。
这将执行以下操作。它将采用括号中给出的索引值[]并搜索(如果列表中存在)。如果它不存在，则创建一个带有键的新条目(括号[]中给出的索引)。并返回对该值的引用，此处为字符串新创建的空排序链表。
如果可以在列表中找到键值，则还会返回对现有值的引用。
因此，无论我们做什么，在使用索引运算符之后，我们将始终引用关联的单向链接排序列表。然后，我们可以在此列表中添加一个新单词(字符串)。这意味着：dictionary[key]将始终返回对SortedSingleLinkedList的引用，为此我们可以调用上述insertSorted(word);函数。
然后整个事情将如下所示：
dictionary[key].insertSorted(word);
这将创建一个新键，或者找到一个现有键，然后返回单词的链表，我们在其中插入一个新单词。
凉。
而且由于我们还向字典类中添加了一个迭代器，因此我们可以轻松地在基于 for 循环的范围内迭代它。
请注意：有经验的用户会立即注意到这两个类几乎 100% 的相似性。实际上，此类类将使用模板功能实现，并随之大幅减小代码大小。
无论如何。让我们暂时使用完整的手写示例代码。请参阅以下许多可能的解决方案之一：
#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <cctype>
// A sorted singly linked list forstd::string + special iterator
class SortedSingleLinkedList {
// Structure of one node
struct Node {
// The data in the dictionay. A std::string
std::string value{};
// Pointer to next node
Node* next{ nullptr };
};
// Start of list
Node* head{ nullptr };
public:
// Destructor will delete all dynamic data, so all nodes
~SortedSingleLinkedList() {
// Start with the head
Node* runningNodePtr = head;
// As long as there are nodes
while (runningNodePtr != nullptr) {
// Get next element pointer
Node* temp = runningNodePtr->next;
// Delete the current element
delete runningNodePtr;
// And continue with next element
runningNodePtr = temp;
}
};
// Main function. Insert a new value into the list, but sorted. So, insertion sort
Node* insertSorted(const std::string& value) {
// Create a new node
Node* newNode = new Node({ value });
// If the list is empty
if (head == nullptr) {
// Then now the start of the list will be the new node
head = newNode;
}
else {
// There was already data here. Initialize an iterator pointer
Node* current = head;
// If the new element is smaller than the head element
if ( newNode->value < head->value) {
// Then we nmake the new element the head element
newNode->next = head;
head = newNode;
}
else {
// Iterate over elements and check, if the new element is samller then the next element
while ((current->next != nullptr) and (current->next->value < newNode->value))
current = current->next;
// So, now we found the element, after which we need to insert the new element
newNode->next = current->next;
current->next = newNode;
}
}
return newNode;
}
// Add iterator properties to class ---------------------------------------------------------------
// Special dereferencing iterator tha will return the data, so the string value, not the node
// Local class for iterator
class iterator {
Node* iter{}; // This will be the iterator
public: // Define alias names necessary for the iterator functionality
using iterator_category = std::input_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = Node*;
using pointer = Node**;
using reference = Node*&;
explicit iterator(Node* i) : iter(i) {}; // Default constructor for the iterator
std::string operator *() const { return (iter == nullptr) ?std::string() : iter->value; } // Dereferencing
iterator& operator ++() { if (iter!=nullptr) iter = iter->next; return *this; } // Pre-Increment
bool operator != (const iterator& other) { return iter != other.iter; } // Comparison
};
// Begin and end function to initiliaze an iterator
iterator begin() const { return iterator(head); }
iterator end() const { return iterator(nullptr); }
};
// -----------------------------------------------------------------------------------------------------------
// -----------------------------------------------------------------------------------------------------------
// -----------------------------------------------------------------------------------------------------------
// A Dictionary, with a key and a value
// Her the valueis again a sorted list with strings
class Dictionary {
// Structur of one node. Contains the key (a character) and the value (a sortedlist with strings)
struct Node {
// The data in the dictionay. The y key
char key{};
// A sorted list with strings
SortedSingleLinkedList value{};
// Pointer to next node
Node* next{ nullptr };
};
// The start of pur linked list
Node* head{ nullptr };
public:
// Destructor will releas previously allocated memory for Nodes
~Dictionary() {
// Start with the head
Node* runningNodePtr = head;
// Iterate over all elements in the List
while (runningNodePtr != nullptr) {
// Get next element
Node* temp = runningNodePtr->next;
// Delete current element
delete runningNodePtr;
// And continue with next element
runningNodePtr = temp;
}
};
// A very special indexoperator that is quite common in associative containers
// It will frost check, if the element given as index is in the list
// If not then a new element for this key will be generated
// In any case, a reference to either the found or the new element will be returned
SortedSingleLinkedList& operator [](const char& key) {
Node* current = head;
while ((current != nullptr) and not (current->key == key)) {
current = current->next;
}
if (current == nullptr)
return insertSorted(key, {})->value;
else
return current->value;
}
// Insert a value sorted by the key into the list
Node* insertSorted(const char& key, const SortedSingleLinkedList& value) {
// Create a new node
Node* newNode = new Node({ key, value });
// If the list was empty, then we simply assign the new node to the head
if (head == nullptr) {
head = newNode;
}
else {
// Iteration variable will start at the head
Node* current = head;
// Special handling of first element. Check, if we need to insert something before the head
if (newNode->key < head->key) {
newNode->next = head;
head = newNode;
}
else {
// Iterate over all elements and check, if our key value is smaller the next key value in the list
while ((current->next != nullptr) and (current->next->key < newNode->key))
current = current->next;
// Insert element in list
newNode->next = current->next;
current->next = newNode;
}
}
return newNode;
}
// Add iterator properties to class ---------------------------------------------------------------
// The dereferencing operator will not return a Node* but a reference to a pair, consisting of the
// key and the value, so, the sorted linked list of strings
// Local class for iterator
class iterator {
Node* iter{}; // This will be the iterator
public: // Define alias names necessary for the iterator functionality
using iterator_category = std::input_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = Node*;
using pointer = Node**;
using reference = Node*&;
explicit iterator(Node* i) : iter(i) {}; // Default constructor for the iterator
std::pair<char&, SortedSingleLinkedList&> operator *() const { return { iter->key, iter->value }; } // Dereferencing
iterator& operator ++() { if (iter != nullptr) iter = iter->next; return *this; } // Pre-Increment
bool operator != (const iterator& other) { return iter != other.iter; } // Comparison
};
// Begin and end function to initiliaze an iterator
iterator begin() const { return iterator(head); }
iterator end() const { return iterator(nullptr); }
};
// Some test string
std::istringstream test{ R"(Wafer chupa chups pudding jelly chocolate cupcake chocolate cake. Candy canes brownie gummies cookie toffee. Sesame snaps
liquorice candy tootsie roll jelly beans. Icing gingerbread apple pie fruitcake jelly-o chocolate cake chocolate chupa chups. Pie gummi bears cookie
fruitcake pastry pudding jelly-o. Tootsie roll ice cream macaroon powder sugar plum powder liquorice. Danish ice cream donut soufflé bonbon halvah
jujubes gummi bears. Brownie tiramisu gingerbread candy canes dessert. Cookie cheesecake cake pastry wafer pie cookie cake. Lollipop chocolate bar
bonbon marzipan pie caramels marzipan. Jelly-o jujubes dessert candy canes tootsie roll croissant. Marzipan pastry pudding lemon drops jelly beans
gingerbread apple pie. Danish muffin gummies candy brownie muffin sweet roll jelly beans. Donut bonbon dessert halvah gummies lemon drops)" };
// -------------------------------------------------------------------------------------------------------------------------------------------------
// Test function / driver code
int main() {
// A dictionary for a key (The capitalize letter of the word and a list of words starting with a letter
Dictionary dictionary;
// Extract all words from the string
std::string word{};
while (test >> word) {
// Wewill use the uppercase first letter of the word as key
char key = char(std::toupper(word[0]));
// FInd or add a key and then insert the word into its value, the sorted list of strings
dictionary[key].insertSorted(word);
}
// Debug output. Show the complete dictionary. Loops are possible because we created iterators
for (const auto& [key, stringList] : dictionary) {
std::cout << "nn" << key << ":n"; // Show the key
for (const std::string s : stringList)
std::cout << s << ' '; // And show the associated words
std::cout << 'n';
}
return 0;
}
使用源代码中显示的输入，我们将得到以下输出：
A:
apple apple
B:
Brownie bar beans beans. beans. bears bears. bonbon bonbon bonbon brownie brownie
C:
Candy Cookie cake cake cake. cake. candy candy candy candy canes canes canes caramels cheesecake chocolate chocolate chocolate chocolate chocolate chupa chupa chups chups. cookie cookie cookie cream cream croissant. cupcake
D:
Danish Danish Donut dessert dessert dessert. donut drops drops
F:
fruitcake fruitcake
G:
gingerbread gingerbread gingerbread gummi gummi gummies gummies gummies
H:
halvah halvah
I:
Icing ice ice
J:
Jelly-o jelly jelly jelly jelly jelly-o jelly-o. jujubes jujubes
L:
Lollipop lemon lemon liquorice liquorice.
M:
Marzipan macaroon marzipan marzipan. muffin muffin
P:
Pie pastry pastry pastry pie pie pie pie. plum powder powder pudding pudding pudding
R:
roll roll roll roll
S:
Sesame snaps soufflé sugar sweet
T:
Tootsie tiramisu toffee. tootsie tootsie
W:
Wafer wafer
我希望我能举一个可以理解的例子