C语言递归算法倒置链表 出错 求高手解答 给点意见

C语言递归算法倒置链表 出错 求高手解答 给点意见,第1张

倒置链表么?哥们你考研呢吧,

应该是这样的:

最慢的最2 的就是 数长度,付给一个数组,数据交换,重新建立个链表。

一般算法最脑残的就是 用栈,先把所有节点进栈,然后出栈,先出来的指向后出来的 ,这个变个花样就是递归了首汪竖

常规想法是下面这样:

链表分成有头结点的链表和无头结点的链表两种

不管怎样,将要转置的链表处理成只含第一节点的带头结点的链表l1 以及 一个无头节点陵镇的包含该链表剩余节点的链表l2。然后,按照顺序将l2上的节点依次取下,插入到L1的头结点和其第一个节点之间,即将从L2取下的节点作为第一个节点插入到L1中;者大

下面是参考代码:

typedef char DataType

typedef struct node{

DataType data

struct node *next

}ListNode

typedef ListNode * LinkList

ListNode *p

LinkList head

LinkList ReverseList(LinkList head)

{

ListNode *p,*q//设置两个临时指针变量

if(head->next&&head->next->next)

{//当链表不是空表或者单节点时

p=head->next

q=p->next

p->next=null//将开始节点变为终端节点

while(q)

{

p=q

q=q->next

p->next=head->next

head->next=p

}

return (head)

}

return (head)

}

大概情况就是这样了,为了点分不容易啊

递归的话就是

链表 转置函数(链表 b)

{链表 temp;

节点 node;

if(b->next)

temp=b->next

node=b

temp=转置函数(temp);

temp->next=b

return b;//代码好久不写差不多忘光了大概就是 将第一个节点取下,转置剩余链表,再把最后一个节点放在转置链表最后

}

(1)LISP具有和图灵机相同的(也就是理论上最高的)计算能力

在计算机科学的可计算理论中,人们已经证明递归函数和图灵机具有相同的(也就是理论上最高的)计算能力,通常指的是自然数集上的递归函数。这个结论对符号集上的递归函数也成立。J.McCarthy在LISP中设计了一套符号处理函数,它们具有符号集上的递归函数的计算能力,因此原则上可以解决人工智能中的任何符号处理问题。

(2)数据类型的唯一性,程序与数旦巧据的一致性

LISP的数据类型和句法结构简单,甚至简单到具有唯一性和一致性:其数据和程序的表现形式是一样的, 都是用S-表达式一种形式.基本的数据结构是表(表是S-表达式的特例)。

(3)数据和程序的 等价性

LISP的数据和程序不仅类型一致,而且作用也等价;

即:程序可作为数据被处理,数据也可作为程序来执行。

(4)LISP一切功能由函数来实现,程序的运行就是求值;

LISP程序的通常形式是一串函数定义,其后跟着一串带有参数的函数调用,函数之间的关系只是在调用执行时才体现出来。

(5)LISP语言的控制结构以递归为主;

大多数语言使用的控制结构是以循环为主的,有的程序语言允许递归,而LISP以递归形式为主。递归是LISP能力的源泉。当然现在LISP也有循环结构和迭代。

(6)原子可以有任意多个值(特性值);

LISP非常重要的一个特点是每个文字原子可以加许多特性,每个特性有一个特性表及对应的特性值。由于原子的多值性给使用者带来很多方便,给问题表示带来好处,使LISP很好用。

(7)LISP具有表的结构形式和规模的灵活性,不必预先设定;

(8)具有收集无用单元的功能。

//--------------------------------------------------------------------

prolog语言

(1)WHAT型语言;

Prolog 由程序设计的“How to do the Job”向 “What you want to do”前进一步。用户只要说明已知事实是什么,定义规则(说明对象间的关系),再告诉要解决的问题是什么(询问)就行了,不必告诉计算机如何链猛一步一步做,问题的求解是通过Prolog的内部机制自动生成。

(2) 基于一阶谓词逻辑,既有坚实的理论基础,又有较强的表现能力;

Prolog的文法简单,描述能力强,更接近于自然语言,程序易写易读,程序量小。

(3) Prolog自动实现模式匹配(合一功能),自动回溯,这两种是人工智能系统中常用的基本 *** 作;

(4)内部的回溯能力及不确定性使Prolog对同一个问题可给出多个解;

Prolog具有不确定的原因有二个:①过程性的不确定性:Prolog谓词调用是用模式匹配方式、自顶向下的深度优先搜索自动回溯策略,当变元值不满足谓词时产生回溯,求得变元之另一棚迟桥值,如此下去直到谓词为真;②变元特性的不确定性:系指谓词中变元既可用来作输入变元又可作输出变元的这种性质。变元特性的非确定性引起提问方式的多样性,增强了交互能力(会话能力)。过程的不确定性和变元特性的不确定性,这是传统程序设计语言以及另一种AI语言LISP所不具备的智能特性。

(5)Prolog的数据和程序的统一,Prolog提供了一种统一的数据结构--项(term),用来构造数据和程序。数据和程序并没有明显区别,同样存在数据库中。并且提供了修改数据库的指令ADDCL和DELCL,在程序执行中,可以自行修改数据、改变控制,因而可以编制能自行修改程序和数据的程序,为实现某些智能提供了方便;

(6)递归是Prolog语言的重要特点之一。

缺点:

(1)在编译系统实现问题上,在执行效率低问题上,在系统开销大的问题上,Prolog遇到了比LISP更大的困难

由于深度优先算法,由于控制机制具有普遍性,由于递归和自动回溯,Prolog程序中间变量过多严重浪费内存,对具体的问题不免有多余的回溯,因而浪费了较多的机器时间和空间,降低了效率。

(2) 大型的Prolog程序调试不容易;

Prolog算法都是深度优先搜索和自动回溯,在程序执行过程中细节由系统内部掌握,减少了人设计控制的工作。但反过来,用户很难或根本无法控制算法的细节,对程序控制的唯一途径是通过“cut” *** 作(但cut影响了prolog的完备性)。因此大型prolog程序比LISP程序调试困难得多。

(3) Prolog的“not”是“失败的not”,不是逻辑否定,只有在封闭世界假设基础上才能认为是逻辑否定。Prolog对量词的处理也不够。它视所有规则前面有对规则中所有变元的全称量词,而视询问公式前有对询问中变元的存在量词。但实际应用中封闭世界假设不一定合适。

(4) Prolog是描述笥语言,处理的是关系,因而在过程性控制方面局限性较大。

但目前不少国家已经实现了Prolog和LISP语言之间或它们与传统语言之间的转换软件接口。所以在过程控制方面也有推广使用Prolog的,例如PC-Prolog。又如,POPLOG是LISP、PROLOG和POP-11的混合物,其中允许这三种语言写的程序互相调用。也有以一种程序设计风范为主、引进并兼顾另一种风范的,例如LOGLISP(以LISP结构为基础,加进逻辑程序成分的)。

如果递归函数只能在堆栈上传递元素,而不是通过堆栈本身传递指针,我们假定应用于函数参数+函数的空间之和不超过K元素。然后函数的每个调用相加为O(k,2)逆对的最大值,最敬昌终结果需要一个O(n - 2)逆对。所以最小复杂度是O(n?2).

当然,有一点点陪乱的元素是可复制的证据。但我不认为复制是没有意义的,因为我们只考虑堆栈结尾处栈中元素的位置。

开始验证

我认为在堆栈上构建链表是可能的,其原理如下:堆栈为s={ 1, 2, 3,4, 5 }。然后每次递归,都可以d出一个(顺序为54321),而每个递归结构都列出了头- >5 - >4 - >3 - >2 - >1,然后S是空的,你可以直接从头部把所有的值推回来。

第二步

题目愿意是不要用递归堆栈空间作为程序使用的空间,否则没有解决方案,应该是很明显亮乱扒的吗?见“程序员选择100个问题(39)-反向线[数据结构]。巧妙的方法是使用递归堆栈空间从原始堆栈d出中保存元素,并避免额外的O(n)数组。解的时间复杂度为o(n·2)。

最后一步

倒置堆栈:1。顶部= POP()2。倒堆。将顶部插入堆栈的下部,如何将它插入堆栈的底部?这是另一种递归吗?

觉得这个问题大脑崩溃了,我的文化水平是不够的,答不出来,你要不要另请高明的好?


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/8261964.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-04-14
下一篇 2023-04-14

发表评论

登录后才能评论

评论列表(0条)

保存