鏈表遞歸演算法
㈠ 如何用遞歸方法求鏈表的長度
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 最好也標號