C++中递归插入和遍历链表
我们给出了用于形成链表的整数值。任务是首先插入然后使用递归方法遍历单链表。
最后递归添加节点
如果head为NULL→将节点添加到head
否则添加到头部(头部→下一个)
递归遍历节点
如果head为NULL→退出
否则打印(头→下)
例子
输入 -1-2-7-9-10
输出 -链表:1→2→7→9→10→NULL
输入 -12-21-17-94-18
输出 -链表:12→21→17→94→18→NULL
下面程序中使用的方法如下
在这种方法中,我们将使用函数来添加节点并遍历单向链表并递归调用它们以进行下一个输入。
取具有整数和下一个指针SLLNode*的结构SLLNode。
函数addtoEnd(SLLNode*head,intdata)获取指向链表头部的指针和数据部分的整数,并将节点添加到链表的末尾。
如果头指针为NULL则列表为空,现在添加一个新节点并将其设置为头。添加head→next为NULL。返回指向该节点的指针
如果head不为null,则使用head->next=addtoEnd(head->next,data)将节点添加到head→next。
函数traverseList(SLLNode*head)从head开始遍历并打印每个值。
如果head为NULL,则打印NULL并返回。
否则打印数据值并使用traverseList(head->next)遍历下一个。
在主创建列表中使用addtoEnd()并使用打印列表traverseList()。
示例
#include <bits/stdc++.h> using namespace std; struct SLLNode { int data; SLLNode* next; }; SLLNode* addtoEnd(SLLNode* head, int data){ if (head == NULL){ SLLNode *nodex = new SLLNode; nodex->data = data; nodex->next = NULL; return nodex; } else{ head->next = addtoEnd(head->next, data); } return head; } void traverseList(SLLNode* head){ if (head == NULL){ cout <<"NULL"; return; } cout << head->data << " -> "; traverseList(head->next); } int main(){ SLLNode* head1 = NULL; head1 = addtoEnd(head1, 1); head1 = addtoEnd(head1, 8); head1 = addtoEnd(head1, 56); head1 = addtoEnd(head1, 12); head1 = addtoEnd(head1, 34); cout<<"链表是:"<<endl; traverseList(head1); return 0; }输出结果
如果我们运行上面的代码,它将生成以下输出
链表是: 1 -> 8 -> 56 -> 12 -> 34 -> NULL