实现个算法,懒得手写链表,于是用C++的forward_list,没有next()方法感觉很不好使,比如一个对单向链表的最简单功能要求:
input:
1 2 5 3 4
output:
1->2->5->3->4
相当于仅仅实现了插入、遍历2个功能(当然遍历功能稍微修改就是销毁链表了)
用纯C写了份测试代码
/* 基本数据结构的定义以及函数的声明 */
typedef int ElemType;
typedef struct Node
{
ElemType elem;
struct Node* next;
} Node, * NodePtr, **ForwardList;
NodePtr createNode(ElemType x);
void showList(ForwardList lst);
void destroyList(ForwardList lst);
// 创建元素为x的节点并插入到节点where后面
// 若where为NULL, 则插入到链表lst的首部作为首节点
// 返回新节点的指针
NodePtr insertAfterNode(NodePtr where, ElemType x,
ForwardList lst);
/* 链表相关函数的具体实现 */
NodePtr createNode(ElemType x)
{
NodePtr pNode = (NodePtr) malloc(sizeof(Node));
if (pNode == NULL) {
perror("malloc");
exit(1);
}
pNode->elem = x;
pNode->next = NULL;
return pNode;
}
NodePtr insertAfterNode(const NodePtr where,
ElemType x, ForwardList lst)
{
NodePtr pNode = createNode(x);
if (where == NULL) {
*lst = pNode;
} else {
pNode->next = where->next;
where->next = pNode;
}
return pNode;
}
void showList(ForwardList lst)
{
printf("显示链表: ");
NodePtr curr = *lst;
while (curr->next != NULL) {
printf("%d->", curr->elem);
curr = curr->next;
}
printf("%d\n", curr->elem);
}
void destroyList(ForwardList lst)
{
printf("销毁链表: ");
NodePtr curr = *lst;
while (curr != NULL) {
NodePtr next = curr->next;
printf("%d ", curr->elem);
free(curr);
curr = next;
}
printf("\n");
}
/* 测试代码 */
int main()
{
NodePtr head = NULL;
initListFromStdin(&head);
showList(&head);
destroyList(&head);
return 0;
}
三个部分都是写在一份代码里(forward_list.c)的,测试结果如下
$ ls
data.in forward_list.c
$ cat data.in
1 2 5 3 4
$ gcc forward_list.c -std=c99
$ ./a.out <data.in
显示链表: 1->2->5->3->4
销毁链表: 1 2 5 3 4
由于是不需要考虑周全的C代码,所以很多C++的一些工程性的技巧不需考虑,比如模板、const,说起来之前没把C代码封装成函数的时候就曾经导致链表的头节点被修改,最后销毁链表时,遍历后头节点直接指向了最后一个节点,导致前4个节点都没被销毁。如果合理地使用const,在编译期就能检查出来。
嘛,其实这么一写下来,C++的forward_list版本也就写出来了,毕竟我的链表插入函数就是模仿forward_list的,但是写出来有点别扭。因为需要遍历到倒数第2个节点停止,最后代码如下
#include <cstdio>
#include <forward_list>
using namespace std;
// 取得前向迭代器it的下一个迭代器
template <typename FwIter>
FwIter nextIter(FwIter it)
{
return ++it;
}
int main()
{
forward_list<int> lst;
int x;
for (auto it = lst.before_begin();
fscanf(stdin, "%d", &x) == 1;
)
{
it = lst.emplace_after(it, x);
}
// 按照a0->a1->...->an的格式输出
auto it = lst.begin();
while (nextIter(it) != lst.end())
{
printf("%d->", *it++);
}
printf("%d\n", *it);
return 0;
}
既然C++不提供next()函数那就只有手写一个,因为迭代器传参数时拷贝了一份,所以nextIter()直接返回++it并不会对原迭代器进行修改,而是修改的原迭代器的拷贝。
注意一点就是,在顺序插入构建链表时需要记录链表最后一个节点,跟我的C代码实现风格一致(好吧其实我本来就是仿STL实现的)。
那么初始值就是before_begin()而不是begin(),因为空链表不存在begin(),确切的说空链表的初始节点为NULL。
测试代码,这里_M_node是glibc++的forward_list迭代器底层实现部分,并不是跨平台代码。迭代器相当于把节点地址进行了一层封装,而_M_node则是节点地址。
#include <forward_list>
#include <stdio.h>
int main()
{
std::forward_list<int> lst;
printf("begin()地址: %p\n", lst.begin()._M_node);
printf("before_begin()地址: %p\n", lst.before_begin()._M_node);
return 0;
}
结果如下:
$ g++ test.cc -std=c++11
$ ./a.out
begin()地址: (nil)
before_begin()地址: 0x7fffb0896b60
原文链接: https://www.cnblogs.com/Harley-Quinn/p/7231927.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/257418
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!