链表逆置，有没有更容易理解的算法。 - 编程论坛

#2

穆扬2006-07-22 17:42

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#3

菜鸟上路2006-07-22 18:08

以下是引用穆扬在2006-7-22 17:42:15的发言：

这个可以吗?
没有返回值
而且形参的类型是struct LNode *

可能吗？

可以啊，在WIN-TC下可以，至于形参的类型是struct LNode *，只是在结构体定义中少写了typedef而已。您有更易懂的算法吗？

#4

穆扬2006-07-22 18:16

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#5

SunShining2006-07-22 18:22

template<typename Name1>
void slist<Name1>::reverse()
{
strlist<Name1> *ptr=_front,*prev=0;

_front=_end;
_end=ptr;

while(ptr!=_front){
strlist<Name1> *tem=ptr->next();
ptr->next(prev);
prev=ptr;
ptr=tem;
}
_front->next(prev);
}

这是昨天拿C++写的一个链表逆转的类
_front是头指针 _end是尾指针
ptr->next(prev) 看成 ptr->next=prev;就可以了

PS:他写的是带表头结点的链表吧..我没细看,应该是吧

#6

菜鸟上路2006-07-22 18:24

以下是引用穆扬在2006-7-22 18:16:19的发言：

我看不可能
理由是,链表的head没有改变,何谈逆置?

您运行一下不就可以了吗，如果没环境的话，可以参考 https://www.bc-cn.net/bbs/dispbbs.asp?BoardID=179&ID=69113&star=100##

#7

菜鸟上路2006-07-22 18:27

以下是引用SunShining在2006-7-22 18:22:26的发言：
template<typename Name1>
void slist<Name1>::reverse()
{
strlist<Name1> *ptr=_front,*prev=0;

_front=_end;
_end=ptr;

while(ptr!=_front){
strlist<Name1> *tem=ptr->next();
ptr->next(prev);
prev=ptr;
ptr=tem;
}
_front->next(prev);
}

这是昨天拿C++写的一个链表逆转的类
_front是头指针 _end是尾指针
ptr->next(prev) 看成 ptr->next=prev;就可以了

PS:他写的是带表头结点的链表吧..我没细看,应该是吧

这个是C++的，有点看不懂，斑竹可以改成C的吗？
PS：是啊

#8

SunShining2006-07-22 18:32

void reverse(struct list *_front,struct list *_end)// _front为头指针,_end为尾指针
{
struct list *ptr=_front,*prev=0;

_front=_end;
_end=ptr;

while(ptr!=_front){
struct list *tem=ptr->next; //如果运行不可以通过..把定义放到函数开始处
ptr->next=prev;
prev=ptr;
ptr=tem;
}
_front->next=prev;
}

#9

穆扬2006-07-22 18:39

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#10

菜鸟上路2006-07-22 18:41

以下是引用SunShining在2006-7-22 18:32:49的发言：
void reverse(struct list *_front,struct list *_end)// _front为头指针,_end为尾指针
{
struct list *ptr=_front,*prev=0;

_front=_end;
_end=ptr;

while(ptr!=_front){
struct list *tem=ptr->next; //如果运行不可以通过..把定义放到函数开始处
ptr->next=prev;
prev=ptr;
ptr=tem;
}
_front->next=prev;
}

谢了，不过这个跟一楼的想法有点类似，不过循环条件容易理解了。

#11

SunShining2006-07-22 18:43

我没细看你的就直接发上来了

哈哈猜到应该是类似的了

#12

菜鸟上路2006-07-22 18:46

#include<stdio.h>

#include<malloc.h>

#include<conio.h>

typedef struct Node

{

char data;

struct Node *next;

}Node,*NodePtr;

void main()

{

NodePtr head = (Node *)malloc(sizeof(Node));//头结点

NodePtr tail;//尾节点

head->next = NULL;

NodePtr p;

p = head ;

printf("*********************单链表逆置***********************\n");

/*初始化程序，建立单链表，从字母a到z的链表，有头结点*/

printf("正在初始化..\n");

for(int i=0;i<26 ;i++)

{

p->next = (Node *)malloc(sizeof(Node));

p = p->next;

p->data = 'a'+i;

}

p->next = NULL;

tail = p;

p = head;

while(p->next)

{

p=p->next;

printf("%c",p->data);

}

printf("\n任意键继续...\n");

getch();

while(head->next) //判断是否以及转置完毕

{

p=head; //初始化定位指针p的位置

while(p->next->next) //查找最后一个尚未转置的指针

p=p->next; //移动指针

p->next->next=p; //将最后的指针逆置

p->next=NULL; //添加尾部的标记

}

printf("\n逆置完成，结果如下\n");

p = tail;

while(p->next)

{

printf("%c",p->data);

p=p->next;

}

getch();

}
这是starrysky写的，其中红字好像不是注释的意思

#13

菜鸟上路2006-07-22 18:48

以下是引用SunShining在2006-7-22 18:43:14的发言：
我没细看你的就直接发上来了

哈哈猜到应该是类似的了

呵呵，这也没什么的

#14

SunShining2006-07-22 18:54

typedef struct Node

{

char data;

struct Node *next;

}Node,*NodePtr;

我一见这种写法就蒙...

#15

菜鸟上路2006-07-22 18:58

以下是引用SunShining在2006-7-22 18:54:43的发言：

typedef struct Node

{

char data;

struct Node *next;

}Node,*NodePtr;

我一见这种写法就蒙...

为什么蒙啊？那您就不用看那个了，直接看逆置那里吧
while(head->next) //判断是否以及转置完毕

{

p=head; //初始化定位指针p的位置

while(p->next->next) //查找最后一个尚未转置的指针

p=p->next; //移动指针

p->next->next=p; //将最后的指针逆置

p->next=NULL; //添加尾部的标记

}

#16

SunShining2006-07-22 19:11

啊..这种算法我以前见过..

忘了是不是见的那小子写的..

就是逐步逆转..不过我个人认为这种方法效率并不好

而且可读性比较差

#17

菜鸟上路2006-07-22 19:18

while(head->next) //判断是否以及转置完毕

{

p=head; //初始化定位指针p的位置

while(p->next->next) //查找最后一个尚未转置的指针

p=p->next; //移动指针

p->next->next=p; //将最后的指针逆置

p->next=NULL; //添加尾部的标记

}
那您能解释下红字的意思吗？是怎样逐步转置的啊？

#18

SunShining2006-07-22 20:30

不好意思.刚回来

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 也就是尾结点

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

#19

SunShining2006-07-22 20:33

那红字部分只是查找尾结点(当然.在这里不可以称为尾结点.应该是next=NULL的结点)的前一个结点

并不是逆转..所谓转那步是

p->next->next=p; //将最后的指针逆置

p->next=NULL; //添加尾部的标记

最后再转头结点.

#20

穆扬2006-07-22 23:56

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#21

SunShining2006-07-23 09:27

你怎么晓得我太极好..

俺记得这"还我PP拳"向来都是你的专利,对了.你还会损人无边的"打狗嘴法"呢

你不出嘴俺才觉得奇怪呢

俺只是太懒..根本就没仔细看过主贴的程序.

这么好的差使还是您来吧

#22

SunShining2006-07-23 09:29

以下是引用SunShining在2006-7-22 18:43:14的发言：
我没细看你的

不知道XXX哪个不看跟贴..就乱灌水

俺在这可是斑竹..小心喽

#23

穆扬2006-07-23 09:34

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#24

SunShining2006-07-23 09:40

俺不看主贴总比某人灌水要对楼主尊重多了吧

斑竹就是可以阻止某只羊灌水的

#25

穆扬2006-07-23 09:43

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#26

SunShining2006-07-23 09:47

俺就是王伦.何如?

所以地痞无赖俺也见多了,没这东西俺还不适应呢

PS:各位不好意思..这贴先不删..留着给大家看看吧

#27

穆扬2006-07-23 09:49

提示: 作者被禁止或删除内容自动屏蔽，只有管理员可见

#28

SunShining2006-07-23 09:57

随你怎么说..俺都接受..这样你会好受点吧

还有..俺承认那贴俺删的的确错误..真应该留下让大家看看

看看您这张 "打狗嘴法" 是如何的八面玲珑.百无禁忌的

哎..被你抓了这个把柄真不好.可是.你的要公交车线路这招实在是高.

俺有机会真得向你学习

#29

starrysky2006-07-23 11:05

以下是引用SunShining在2006-7-22 19:11:02的发言：
啊..这种算法我以前见过..

忘了是不是见的那小子写的..

就是逐步逆转..不过我个人认为这种方法效率并不好

而且可读性比较差

谁是‘见的那小子’啊？不会是在说我吧？！
SunShining你小子整天灌水，也不怕水灌多了把你家给淹了。

[此贴子已经被作者于2006-7-23 11:27:44编辑过]

#30

starrysky2006-07-23 11:13

以下是引用菜鸟上路在2006-7-22 18:58:52的发言：

为什么蒙啊？那您就不用看那个了，直接看逆置那里吧
while(head->next) //判断是否以及转置完毕

{

p=head; //初始化定位指针p的位置

while(p->next->next) //查找最后一个尚未转置的指针

p=p->next; //移动指针

p->next->next=p; //将最后的指针逆置

p->next=NULL; //添加尾部的标记

}

这种算法可读性的确差了点，不太容易理解，但好处也是很明显的，它只使用了一个单位的空间（p）就将链表给逆置了。而楼主给出的算法需要使用3个单位的空间（p，q，s）。
红色的部分是我觉得非常关键的部分。

[此贴子已经被作者于2006-7-23 11:25:06编辑过]

#31

starrysky2006-07-23 11:21

楼主给出的算法是很基本的链表逆置算法，如果说不好理解的话，我教楼主一个方法。
拿一张纸和一只笔，在纸上任意写一个链表，每个节点之间最好隔开点，然后用给出的算法来逐步处理这个链表，并将步骤标在纸上，这样就很容易理解这个算法了，有时候也可以用这个方法来检验某个算法是否正确。对于后面那个比较难懂的算法，也可以用这个方法。

#32

SunShining2006-07-24 20:07

以下是引用starrysky在2006-7-23 11:13:16的发言：

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

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

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

PS:俺是被迫才灌水的

#33

starrysky2006-07-25 16:28

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

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

#34

SunShining2006-07-25 17:30

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

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

#35

菜鸟上路2006-07-26 16:59

以下是引用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版主，当天回去也分析了下，现在已经明白了。

#36

菜鸟上路2006-07-26 17:04

以下是引用starrysky在2006-7-23 11:21:51的发言：
楼主给出的算法是很基本的链表逆置算法，如果说不好理解的话，我教楼主一个方法。
拿一张纸和一只笔，在纸上任意写一个链表，每个节点之间最好隔开点，然后用给出的算法来逐步处理这个链表，并将步骤标在纸上，这样就很容易理解这个算法了，有时候也可以用这个方法来检验某个算法是否正确。对于后面那个比较难懂的算法，也可以用这个方法。

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

#37

fp1512010-12-22 23:17

程序代码：

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;
}