| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3772 人关注过本帖
标题:链表逆置,有没有更容易理解的算法。
只看楼主 加入收藏
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 
楼主给出的算法是很基本的链表逆置算法,如果说不好理解的话,我教楼主一个方法。
拿一张纸和一只笔,在纸上任意写一个链表,每个节点之间最好隔开点,然后用给出的算法来逐步处理这个链表,并将步骤标在纸上,这样就很容易理解这个算法了,有时候也可以用这个方法来检验某个算法是否正确。对于后面那个比较难懂的算法,也可以用这个方法。

我的征途是星辰大海
2006-07-23 11:21
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 
以下是引用starrysky在2006-7-23 11:13:16的发言:

这种算法可读性的确差了点,不太容易理解,但好处也是很明显的,它只使用了一个单位的空间(p)就将链表给逆置了。

如果结点很多..相对效率来说

多分配两个int型..简直是大巫见小巫了.

PS:俺是被迫才灌水的

[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-07-24 20:07
starrysky
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:华中科技大学EI -T0405
等 级:版主
威 望:11
帖 子:602
专家分:1
注 册:2005-9-12
收藏
得分:0 


如果别人要求算法的空间复杂度为1呢?

这个算法主要就是从空间复杂度方面考虑的嘛。不然谁会去写个时间复杂度超高的算法呢?

我的征途是星辰大海
2006-07-25 16:28
SunShining
Rank: 7Rank: 7Rank: 7
等 级:贵宾
威 望:31
帖 子:2215
专家分:0
注 册:2006-2-17
收藏
得分:0 

对了..那个东东是你写的吗..值得表扬哦

PS:你写的那个什么论呢...还没完事呢?


[glow=255,violet,2]闭关修炼ing...[/glow] [FLASH=360,180]http://www./chinaren.swf[/FLASH]
2006-07-25 17:30
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
以下是引用SunShining在2006-7-22 20:30:19的发言:

不好意思.刚回来

1.head->1->2->3->4->NULL

2.head->1->2->3->NULL
4->3

3.head->1->2->NULL
4->3->2

4.head->1->NULL
4->3->2->1

最后.p = tail;
p为head tail为 结点4 也就是尾结点

不知道我说明白没有..不明白再给你解释吧

谢谢SunShining版主,当天回去也分析了下,现在已经明白了。


2006-07-26 16:59
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
收藏
得分:0 
以下是引用starrysky在2006-7-23 11:21:51的发言:
楼主给出的算法是很基本的链表逆置算法,如果说不好理解的话,我教楼主一个方法。
拿一张纸和一只笔,在纸上任意写一个链表,每个节点之间最好隔开点,然后用给出的算法来逐步处理这个链表,并将步骤标在纸上,这样就很容易理解这个算法了,有时候也可以用这个方法来检验某个算法是否正确。对于后面那个比较难懂的算法,也可以用这个方法。

一楼的算法,用纸和笔是能够分析的很清楚,但是自己写起来有难度啊(特别是循环结束的条件),是不是C语言没学扎实啊?


2006-07-26 17:04
fp151
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2010-12-21
收藏
得分:0 
程序代码:
void LinkList_re(LinkList *&L)//链表的就地逆置;为简化算法,假设表长大于2
{

 

 LinkList *p,*q,*s;

 p=L->next;q=p->next;s=q->next;p->next=NULL;
  while(s->next)
  {
    q->next=p;p=q;
    q=s;s=s->next; //把L的元素逐个插入新表表头
  }
  q->next=p;s->next=q;L->next=s;
}
2010-12-22 23:17
快速回复:链表逆置,有没有更容易理解的算法。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017946 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved