链表递归算法
㈠ 如何用递归方法求链表的长度
int size() {
return size(first);
}
int size(Entry e) {
if (e == null) return 0;
return 1 + size(e.next);
}
差不多思路就是这样，当然要看你的链表具体是怎么样的
package cn.uestc.fz;
class Node{
int data;
Node next;
public Node(int data,Node next){
this.data=data;
this.next=next;
}
}
public class LinkedList {
Node head;
public void add(Node node){
if(head==null)
head=node;
else{
Node p=head;
while(p.next!=null)
p=p.next;
p.next=node;
}
}
public int length(){
return this.length(head);
}
public int length(Node node){
if(node==null)
return 0;
else if(node.next==null)
return 1;
else
return 1+this.length(node.next);
}
public void printList(){
Node p=head;
while(p!=null){
System.out.print(p.data+"->");
p=p.next;
}
System.out.println();
}
public static void main(String args[]){
LinkedList list = new LinkedList();
list.add(new Node(1,null));
list.add(new Node(2,null));
list.add(new Node(3,null));
list.add(new Node(4,null));
list.add(new Node(5,null));
list.add(new Node(6,null));
list.printList();
System.out.println(list.length());
}
}
刚写的。
㈢ 单链表 递归算法
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
用递归的方法创建单链表（整形数字）
并且判断单链表是否递增有序
求单链表的最大值
*/
//结点
struct Node
{
int data;
Node *pNext;
};
//递归创建单链表
int MaxNodeNumber = 10;
void CreateList(Node **pWork)
{
static int Count = 0;
(*pWork) = new Node();
(*pWork)->data = rand();//使用随机数 判断非递增
//(*pWork)->data = Count;//使用序号 判断递增
(*pWork)->pNext = NULL;
Count++;
if ( Count < MaxNodeNumber )
{
CreateList(&((*pWork)->pNext));
}
return;
}
//输出链表
void PrintList(Node *pWork)
{
printf("Head->");
while ( pWork != NULL )
{
printf("[%d]->",pWork->data);
pWork = pWork->pNext;
}
printf("NULL\n");
}
//递归删除单链表
void DestroyList(Node *pWork)
{
if ( NULL != pWork )
{
if ( pWork->pNext != NULL )
{
DestroyList(pWork->pNext);
}
delete pWork;
pWork = NULL;
}
}
//递归判断单链表是否递增有序
bool TestIsAscending(Node *pWork)
{
//中间结点
if ( pWork != NULL && pWork->pNext != NULL)
{
bool Current = pWork->data < pWork->pNext->data;
return Current && TestIsAscending(pWork->pNext);
}
else
{
return true;
}
}
//递归求最大值
int GetMaxValue(Node *pWork)
{
if ( pWork != NULL && pWork->pNext != NULL )
{
int MaxNextValue = GetMaxValue(pWork->pNext);
if ( pWork->data > MaxNextValue )
{
return pWork->data;
}
else
{
return MaxNextValue;
}
}
else if ( pWork->pNext == NULL )
{
return pWork->data;
}
}
void main(void)
{
Node *pHead = NULL;
srand(time(NULL));
CreateList(&pHead);
PrintList(pHead);
if ( TestIsAscending(pHead) )
{
printf("是递增\n");
}
else
{
printf("不是递增\n");
}
printf("最大值为 = %d\n",GetMaxValue(pHead));
DestroyList(pHead);
fflush(stdin);
getchar();
}
㈣ c语言 倒置链表的递归方法
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}node,*Linklist;
Linklist create_linklist(Linklist &L,int n)
{ //建立有头结点的链表
L=(Linklist)malloc(sizeof(node));
L->next=NULL;
Linklist p;
int i;
for(i=1;i<=n;i++)
{
p=(Linklist)malloc(sizeof(node));
p->data=rand()%100;
p->next=L->next;
L->next=p;
}
return L;
}
Linklist reserve_fei(Linklist L,int n)
{ //非递归算法
Linklist head,pre,bef;
head=L;
pre=L;
bef=L;
while(pre->next)
{
pre=pre->next;
}
int i;
for(i=1;i<n;i++)
{
bef=L;
while(bef->next->next)
{
bef=bef->next;
}
pre->next=head->next;
head->next=pre;
head=pre;
pre=bef;
pre->next=NULL;
}
return L;
}
void reserve_digui(Linklist L,int n)
{ //递归的，但我写错了，不知道该怎么写。。。求助~~
Linklist head=L,pre;
if(n==0)
return ;
else
{
reserve_digui(L->next,n-1);
}
printf("%d ",L->data);
}
int main()
{
int n;
scanf("%d",&n);
Linklist L,L1,L2,q;
L=create_linklist(L,n);
printf("原链表为:\n");
q=L->next;
while(q)
{
printf("%d ",q->data);
q=q->next;
}
printf("\n不用递归的结果是:\n");
L1=reserve_fei(L,n);
q=L1->next;
while(q)
{
printf("%d ",q->data);
q=q->next;
}
printf("\n");
printf("用递归的结果是:\n");
reserve_digui(L->next,n);
return 0;
}
看了lz的程序，感觉lz没有理解递归的精髓……
㈤ 求链表中最大元素的值 数据结构递归算法
//p为单链表头指针 int max=p->item; p=p->next; while（p！=NULL） { if(p->item>max) max=p->item; } return max;
㈥ C语言反转链表的递归算法
可以用IF判断语句
如果不符合你的要求就
停止调用。
㈦ 求单链表的长度的递归算法（C语言格式）
求单链表的长度函数名为linklistlength
单链表用结构体linklist表示
int linklistlength(linklist *head)
{
if(!head) return 0;
return linklistlength(linklist *head->next)+1;
}
㈧ 设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：
给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE 12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p) printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍历循环
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p) printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
㈨ 递归逆序单链表 算法
递归时,head分别用 head head1,head2 ...headn-1, headn来表示(共n+1)个节点
rHead = rev( head->next ); 此句的递归一直将参数传进来的
List * head 递归到 headn 然后判断
else if( !headn->next )
{
return headn;
}
将返回值给rHead,此时rHead指向链尾,由于在此次返回,故此次没有执行最后的else的那部分的语句,返回上一级即是 headn-1 那一级,继续执行
下面的 headn-1->next->next = headn-1;
headn-1->next = NULL; //此两句将最后两个逆序连接,
return rHead; //之后返回rHead比上一层的rHead即是执行
rHead = rev( head->next )赋值,因为递归的
口都是在这里的,如果说好理解点也可以将rHead
来编号
同理
在返回rHead后,继续执行
headn-2->next->next = headn-2;
headn-2->next = NULL;
return rHead;
.....
一直到 head时 即是原链表的第一个节点,在对其head->next = NULL,
后,此时以 rHead 所指向的节点为链头的逆序链表就形成拉.
由于不能画图,故描述得可能还是有点乱吧,不过,一句话,最好的理解就是你将递归时,head分别用 head head1,head2 ...headn-1, headn来编号表示就好理解的拉,对于 rHead 最好也标号