我是所有这些 c++ 编程的初学者，我想最后一次尝试以获得帮助。我必须创建一个名为 add_aa(str) 的方法，它按字母升序添加 str。这涉及使用链表和从文本文件中读取。在文本文件中，有以下内容：aa hi dd hi。这就是文本文件中的全部内容。在 main.cpp 文件中，这里有一段代码可以输出到 str：
if( cmds.first == "aa" ) // add alphabetically
{
lst.add_aa( cmds.second );
}
使用此代码，从文本文件中读取，hi 将被输出并分配给 str。我正在尝试编写执行此操作的方法，但我想不出任何东西。另外，这是我应该收到的输出以清除问题。
到目前为止，我的代码只是：
inline void LList:: add_aa(const string _str)
{
cout << "\tp = " << std::hex << p << std::dec << '\n';
}
哦，天哪，我们进入了 C++“链表教程”，上次你问我时我说它是不切实际的。
但也许我有时间写它。
我会先给自己泡点茶，然后分小批发布，一次一个。
一个基本的单链表由节点组成，其中每个节点都包含一个指向列表中下一个节点的指针，例如称为next。按照惯例next==0 表示列表的结尾。所以，让我们创建这样一个简单的列表，遍历它（这里只是显示内容），并通过释放节点进行清理：
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
node->next = first; // After this `node` points to the new first node.
first = node; // Now `first` also points to the new first node.
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
对于最后的清理，重要的是按正确的顺序做事，以免访问已删除的节点。访问已删除的节点可能会起作用。但是，由于墨菲定律，它会在以后失败，在事情应该起作用的绝对最关键的时间点上。
输出：
0 114 101 119 111 108 102 110 111 111 109
这些是 ASCII 字符代码，包括字符串的终止零。
注意数字的顺序！:-)
与直接使用数组相比，链表的主要优点是插入新节点需要恒定的时间。在直接使用数组的情况下，插入新项必须将所有项移动到它之后（或之前），这需要与数组大小成正比的时间。但是，请注意（1）查找插入点的时间通常被强制为线性列表大小，而它可以是数组的对数，以及（2）通过使用称为“插入间隙”或“光标间隙”的技术” 对于数组来说，插入一个项目也可以是恒定的时间（以一些轻微的成本）。
为了在升序位置插入一个数字，对于基本列表，您需要一个指向插入点之前节点的指针，以便next可以更新该节点以指向新节点。
由于基本列表在第一个节点之前没有这样的节点，因此在列表开头插入成为一种丑陋的特殊情况，如下所示：
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t* p = first;
node_t* p_node_before = 0;
while( p != 0 && p->value < ch )
{
p_node_before = p;
p = p->next;
}
if( p_node_before == 0 )
{
// Insert at start of list, just like in the first program.
node->next = first; // After this `node` points to the new first node.
first = node; // Now `first` also points to the new first node.
}
else
{
// Insert within the list or at the end of the list.
node->next = p_node_before->next;
p_node_before->next = node;
}
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
输出：
0 101 102 108 109 110 111 111 111 114 119
请注意，由于搜索插入位置，每次插入平均花费的时间与列表的最终长度成正比，因此总的来说这是二次时间，O(n 2 )。这是一个简单的插入排序。我希望我没有引入任何错误！:-)
减少基本列表开头插入混乱的一种方法是注意您实际上只需要访问next插入点之前的节点字段。
您不需要访问插入点之前的完整节点。
所以你可以只用一个指向指针的next指针。即指向指针的指针。对于列表的开头，first指针变量可以很好地服务，就好像它是next之前某个节点中的字段一样，所以最初指针指向指针可以只指向first指针（嗯），然后它可以移动在next指针上，像这样：
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* first = 0;
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t** p_next_before = &first;
while( *p_next_before != 0 )
{
node_t* const next_node = *p_next_before;
if( next_node->value >= ch )
{
break;
}
p_next_before = &next_node->next;
}
// Insert at start of list, just like in the first program.
node->next = *p_next_before; // After this `node` points to the new first node.
*p_next_before = node; // Now ... also points to the new first node.
}
// Display it
for( node_t* p = first; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
输出还是
0 101 102 108 109 110 111 111 111 114 119
应该是这样。
起初，我直接在while循环头中编写了带有相当长的延续条件的代码。但是遵循应该命名几乎所有东西的规则，我将其中的一部分移到循环内，然后加上一个break语句。所以这就是声明的原因break：支持名称next_node。
在 C++ 中，指向指针的指针有时表示为指向指针的引用。例如，从基本列表中取消链接节点的函数可能采用引用指针参数，而不是 C 风格的指针指针。我发现它更干净，当它适用时。
指针对指针的替代方法是在第一个实节点之前引入一个虚拟节点。那么即使是一个空列表也有一个物理节点，即虚拟节点。虚拟节点通常称为头节点。
在编译器完成对机器代码的转换和优化之后，使用头节点的代码可能与使用指针到指针技术的代码相同，只是头节点涉及更多的分配，并且需要更多的时间房间比单个指针变量。但不同之处在于人们如何看待代码，如何理解它。从概念上讲，拥有头节点与使用指针对指针技术非常不同——例如，如果您绘制列表结构，那么带有头节点的列表看起来与没有此类节点的列表明显不同。
无论如何，代码：
#include <iostream>
using namespace std;
struct node_t
{
node_t* next;
int value;
node_t( int const v = 0 )
: next( 0 ), value( v )
{}
};
int main()
{
char const blah[] = "moonflower";
node_t* header_node = new node_t();
// Create the list.
for( auto ch : blah )
{
node_t* node = new node_t( ch );
// Find the insertion point.
node_t* p_before = header_node;
while( p_before->next != 0 && p_before->next->value < ch )
{
p_before = p_before->next;
}
// Insert at start of list, just like in the first program.
node->next = p_before->next; // After this `node` points to the new first node.
p_before->next = node; // Now ... also points to the new first node.
}
// Display it
for( node_t* p = header_node->next; p != 0; p = p->next )
{
cout << p->value << " ";
}
cout << endl;
// Delete the list
auto& first = header_node; // Just a renaming for clarity.
while( first != 0 )
{
node_t* const doomed = first;
first = first->next;
delete doomed;
}
}
和以前一样，输出仍然是
0 101 102 108 109 110 111 111 111 114 119
应该是这样。