单链表的就地逆序 - 编程论坛

#2

xg56992011-09-13 01:12

建个全局变量 int total 每新建一个链表进行total自加,把自加的值赋给链表中储存这个的变量
有多少个链表total的值就是多少,而且每个链表从小到大都标好了,有了这个变量接着在逆序就简单了吧?

纯属瞎瓣

#3

czsbc2011-09-13 01:51

程序代码：

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int element;
    struct node * next;
}Node,* List;

void CreateList(List &L)
{
    Node * p;
    L=(List)malloc(sizeof(Node));
    L->next=NULL;
    for(int i=0;i<5;i++)
    {
        p=(Node *)malloc(sizeof(Node));
        p->element=i;
        p->next=L->next;
        L->next=p;
    }
}
void PrintList(List L)
{
    Node *p=L->next;
    while(p)
    {
        printf("%d ",p->element);
        p=p->next;
    }
    printf("\n");
}

void ReverseList(List &L)
{
    Node *p,*q;
    p=L->next;
    q=p->next;

    while(p&&q)
    {
        p->next=q->next;
        q->next=L->next;
        L->next=q;
        q=p->next;
    }
}
int main()
{
    List A;
    CreateList(A);
    PrintList(A);
    ReverseList(A);
    PrintList(A);
    return 1;
}

简单写了一个逆序函数，顺带测试代码一起写了。不知道符不符合你的意思。

很久没有用过单链表了,生疏了

。

#4

rjsp2011-09-13 08:17

void reverse( Node*& p )
{
    Node* t = 0;
    for( ; p ; )
    {
        Node* _t = t;
        t = p;
        p = p->next;
        t->next = _t;
    }
    p = t;
}

#5

lucky5635912011-09-13 09:01

直接对称交换数据不就行了

#6

剑飘香2011-09-13 19:51

回复 3楼 czsbc

我自己想了一个逆序的方法，模型是引用你的程序，但是运行时说内存冲突，不知道怎么回事，麻烦帮忙看看
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
    int element;
    struct node * next;
}Node,* List;

void CreateList(List &L)
{
    Node * p;
    L=(List)malloc(sizeof(Node));
    L->next=NULL;
    for(int i=0;i<5;i++)
    {
        p=(Node *)malloc(sizeof(Node));
        p->element=i;
        p->next=L->next;
        L->next=p;
    }
}
void PrintList(List L)
{
    Node *p=L->next;
    while(p)
    {
        printf("%d ",p->element);
        p=p->next;
    }
    printf("\n");
}

void ReverseList(List &L)
{
    Node *p,*q;
    p=L->next;
    q=p;
    while(p&&q){
        L->next=p->next;
        p->next=p->next->next;
        L->next->next=q;
        q=L->next;
        p=p->next;
    }
}
int main()
{
    List A;
    CreateList(A);
    PrintList(A);
    ReverseList(A);
    PrintList(A);
    return 1;
}

#7

pangding2011-09-13 20:56

我看 4楼说的最言简意赅。

head -> a -> b -> c -> null
只要变成
null <- a <- b <- c <- head
就行了，说白了只要让指针反过来就行。

有一点要注意的是，如果先让 b 的指针指向 a 的话，c 的地址就找不找了，所以要用一个辅助指针先记住 c 的位置。

#8

specilize2011-09-14 19:45

回复 4楼 rjsp

看过rjsp写的很多代码，变量的命名都喜欢在前面加个_，像Node* _t这样，不是说这种命名方法一般是给系统用的吗，这样写只是个人爱好，还是有什么端倪啊

#9

pangding2011-09-14 21:35

回复 8楼 specilize

有经验了就可以用这种名字。给变量起名没有什么绝对的规则，但要用心起，起“漂亮”一些。
平价一个人写的代码经常不是从算法角度下手的，而是其它方面。其中主要是看一个程序员的素养和经验。

平时写阅读高质量代码的时候可以多留心记点东西。读得久了，好多东西就熏陶出来。

#10

specilize2011-09-15 13:07

回复 9楼 pangding

有经验就可以用这种命名的意思是不是有了可以防止命名与系统命名相冲突的经验，按版主的意思，好像是说在某些情况下采用这种编程风格更好，那么什么情况下会考虑这种命名方式呢

#11

pangding2011-09-15 18:40

不是。其实根本不怕和系统冲突。名字有覆盖规则的，一般局部的名字会覆盖外层的名字。
我的意思只是说如果你经验不足起不好名字，会让人一眼就看出你水平不高而已。

所谓编程语言，其实和人类语言差不多。
比如你学英语遇到近义词或者同义词，你也许经常想问什么时候用呀？有什么区别呀？但其实总结出来的规律都没什么用。
第一，规律也许只是以偏概全，不是任何时候都适用的，总有例外。第二，你根本不能指望这些规律来措辞，否则你肯定无法与别人交流。

要想地道的说好一门语言，首先的说得自然。但你自然想到的第一个词也许并不地道。这没办法，只有多听多想多感悟，培养语感。
写程序也一样。自己闭门造车地写程序，写出来的也许就是“chingilsh”，没有语法错误的代码不等于高质量的代码。要多读资深程序员的代码，培养“语感”。

就像 4楼的那种写法。就他展示的那一小段就很协调。如果我写，很可能会写出一样的代码。
不过不能认为这么写就对。有的时候有程序有上下文，这么写也可能很糟糕。命名没有绝对的规则，不过有的时候它体现一个人或者一个团队的品味或文化。

#12

specilize2011-09-15 21:14

回复 11楼 pangding

版主的一席话真是既客观又在理，以后会多加注意阅读高质量代码的

#13

剑飘香2011-09-15 23:44

回复 9楼 pangding

那作为一个朝着程序员发展的初学者，到底是应该按照课本上的规矩风格还是有自我风格呢？

#14

pangding2011-09-16 00:27

当然是规矩呀。其实好的程序员也都挺有规矩的。
自我风格也是在规矩的基础上加进来的，有些程序员的代码就挺幽默的，但并不是在乱写。