设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › C\C++交流 › 链表翻转初稿
返回列表 发新帖
查看: 2329|回复: 15

[技术交流] 链表翻转初稿

[复制链接]
wp231957
发表于 2022-5-8 12:09:40 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x 
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

int main()
{
        struct Node * node1; 
        struct Node * node2; 
        struct Node * node3; 
        struct Node * node4; 
        struct Node * node5; 
        struct Node * pmove; 
        node1=(struct Node*)malloc(sizeof(struct Node*));
        node2=(struct Node*)malloc(sizeof(struct Node*));
        node3=(struct Node*)malloc(sizeof(struct Node*));
        node4=(struct Node*)malloc(sizeof(struct Node*));
        node5=(struct Node*)malloc(sizeof(struct Node*));
        node1->data=1;
        node1->next=node2;
        node2->data=2;
        node2->next=node3;
        node3->data=3;
        node3->next=node4;
        node4->data=4;
        node4->next=node5;
        node5->data=5;
        node5->next=NULL;
        //输出原始链表
        pmove=node1;
        while (pmove)
        {
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        //为了翻转链表，我们需要四个指针
        struct Node * cur; 
        struct Node * next; 
        struct Node * pre;   //还有一个是入口指针，前面有的
        //1节点
        pre=cur=node1;
        next=cur->next;
        cur->next=0;
        //2节点
        cur=next;
        next=cur->next;
        cur->next=pre;
        pre=cur;
        //3节点
        cur=next;
        next=cur->next;
        cur->next=pre;
        pre=cur;
        //4节点
        cur=next;
        next=cur->next;
        cur->next=pre;
        pre=cur;
        //5节点
        cur=next;
        next=cur->next;
        cur->next=pre;
        pre=cur;
       //输出翻转后链表
        pmove=cur;
        while (pmove)
        {
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        return 0;
}

/*
附效果图:
   PS D:\001> ./w1
   1     2     3     4     5  
   5     4     3     2     1
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

wp231957
 楼主| 发表于 2022-5-8 13:05:12 | 显示全部楼层
第二稿：
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

int main()
{
        struct Node * node1; 
        struct Node * head; 
        head=(struct Node*)malloc(sizeof(struct Node*));
        head->data=0;
        head->next=NULL;
        //初始化链表 ，貌似这个是头插法吧
        for(int x=0;x<10;x++)
        {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=head;
                head=node1;
        }
        //输出原始链表
        struct Node *  pmove=head;
        while (pmove)
        {
             if(pmove->next==NULL) break;
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        //为了翻转链表，我们需要四个指针
        struct Node * cur; 
        struct Node * next; 
        struct Node * pre;   //还有一个是入口指针，前面有的
        
        pre=cur=head;
        next=cur->next;
        cur->next=0;
        while(1)
        {
                cur=next;
                next=cur->next;
                cur->next=pre;
                pre=cur;
                if (next==NULL) break;
        } 
       //输出翻转后链表
        pmove=cur->next;
        while (pmove)
        {
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        return 0;
}

/*
输出案例：
PS D:\001> ./w1
   9     8     7     6     5     4     3     2     1     0  
   0     1     2     3     4     5     6     7     8     9
PS D:\001> 
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

wp231957
 楼主| 发表于 2022-5-8 13:29:36 | 显示全部楼层
wp231957 发表于 2022-5-8 13:05
第二稿：

这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

int main()
{
        struct Node * node1; 
        struct Node * head; 
        head=(struct Node*)malloc(sizeof(struct Node*));
        head->data=0;
        head->next=NULL;
        struct Node *  pmove=head;
        struct Node *  head2=head;
        //初始化链表 ，准备使用尾插法
        for(int x=0;x<10;x++)
        {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=NULL;
                head->next=node1;
                head=node1;
        }
        //输出原始链表
        pmove=pmove->next;
        while (pmove)
        {
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        //为了翻转链表，我们需要四个指针
        struct Node * cur; 
        struct Node * next; 
        struct Node * pre;   //还有一个是入口指针，前面有的
        
        pre=cur=head2;
        next=cur->next;
        cur->next=0;
        while(1)
        {
                cur=next;
                next=cur->next;
                cur->next=pre;
                pre=cur;
                if (next==NULL) break;
        } 
       //输出翻转后链表
        pmove=cur;
        while (pmove)
        {
             if(pmove->next==NULL) break;
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        return 0;
}

/*
输出案例：
PS D:\001> ./w1
   0     1     2     3     4     5     6     7     8     9  
   9     8     7     6     5     4     3     2     1     0
PS D:\001>
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

wp231957
 楼主| 发表于 2022-5-9 16:19:49 | 显示全部楼层
wp231957 发表于 2022-5-8 13:29
这个版本用了尾插法，和头插法区别还是蛮大的（不像有些资料上说的没啥区别）

半途翻转链表（不够完美，但是终于依靠自己的代码  能翻了）
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

int main()
{
        struct Node * node1;
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node*));
        head->data=0;
        head->next=NULL;
        //初始化链表 ，貌似这个是头插法吧
        for(int x=0;x<10;x++)
        {
                node1=(struct Node*)malloc(sizeof(struct Node*));
                node1->data=x;
                node1->next=head;
                head=node1;
        }
        //输出原始链表
        struct Node *  pmove=head;
        while (pmove)
        {
                if(pmove->next==NULL) break;
                printf("%4d  ",pmove->data);
                pmove=pmove->next;
        }
        printf("\n");
        //获取出口节点和入口节点
        struct Node * ennode=NULL; 
        struct Node * exitnode=NULL; 
        pmove=node1;
        int i=1;
        while (pmove)
        {
                if(i==3-1) ennode=pmove;   //要在3节点翻转 这里应该减一
                if(i==6)   exitnode=pmove;
                pmove=pmove->next;
                i++;
        }
        //半途翻转链表
        struct Node * cur; 
        struct Node * next; 
        struct Node * pre;   
        //入口节点
        cur=ennode;  //此处ennode=node2
        pre=next=ennode->next;   //此处需要保存真正的入口地址
        cur->next=exitnode;     //跳转到需要翻转的首节点
        //入口节点下一节点
        cur=next;
        next=next->next;
        cur->next=exitnode->next;   //跳转不需翻转的节点
        pre=cur;
        while(1)
        {
                cur=next;
                next=next->next;
                cur->next=pre;
                pre=cur;
                if (cur==exitnode) break;
        }
        //输出翻转后链表
        pmove=head;
        while (pmove)
        {
                if(pmove->next==NULL) break;
                printf("%4d  ",pmove->data);
                pmove=pmove->next;
        }
        printf("\n");
        return 0;
}

/*
附效果图:
 PS D:\001> ./w1
   9     8     7     6     5     4     3     2     1     0  
   9     8     4     5     6     7     3     2     1     0
PS D:\001> 
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-10 10:37:32 | 显示全部楼层
wp231957 发表于 2022-5-9 16:19
半途翻转链表（不够完美，但是终于依靠自己的代码  能翻了）

这里有个单链表循环链表的样例：
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    struct Node * tmp=NULL;
    for(int x=10;x<20;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node*));
        node1->data=x;
        if(x==10) tmp=node1;
        node1->next=head;
        head=node1;
    }
    tmp->next=head;      //构成循环链表，同时绕过头节点
    return head;
}

int main()
{
        struct Node * node1;
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node*));
        head->data=0;
        head->next=NULL;
        //输出原始链表
        struct Node *  pmove=init_link(head);
        int i=0;
        while (pmove)
        {
                if(pmove->next==NULL) break;
                printf("%4d  ",pmove->data);
                pmove=pmove->next;
                i++;
                if(i>15) break;     //为了测试循环的效果  我们选择了进行16次循环 看一下效果
        }
        printf("\n");
      
        return 0;
}

/*
附效果图:
 PS D:\001> ./w3
  19    18    17    16    15    14    13    12    11    10    19    18    17    16    15    14  
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-10 10:41:22 | 显示全部楼层
wp231957 发表于 2022-5-10 10:37
这里有个单链表循环链表的样例：

不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    struct Node * tmp=NULL;
    for(int x=10;x<20;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node*));
        node1->data=x;
        if(x==10) tmp=node1;
        node1->next=head;
        head=node1;
    }
    tmp->next=head;      //构成循环链表，同时绕过头节点
    return head;
}

int main()
{
        struct Node * node1;
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node*));
        head->data=0;
        head->next=NULL;
        //输出原始链表
        struct Node *  pmove=init_link(head);
        struct Node * tmp=pmove;
        while (pmove)
        {
                printf("%4d  ",pmove->data);
                if(pmove->next==tmp) break;     //这里是循环链表的遍历退出条件
                pmove=pmove->next;
        }
        printf("\n");
      
        return 0;
}

/*
附效果图:
 PS D:\001> ./w3
  19    18    17    16    15    14    13    12    11    10  
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-10 13:19:18 | 显示全部楼层
wp231957 发表于 2022-5-10 10:41
不知道循环链表有啥用，估计是为了双循环链表打基础吧，看一下他的遍历退出条件

前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间
#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node));
        node1->data=x;
        node1->next=head;
        head=node1;
    }
    return head;
}

//带头节点的 头插法
struct Node * init_link2(struct Node * s)
{
    struct Node * head=s;
    for(int x=100;x<110;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node));
        node1->data=x;
        node1->next=head;
        head=node1;
    }
    return head;
}


int main()
{
        struct Node * node1;
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node));
        head->data=0;
        head->next=NULL;
        //输出原始链表
        struct Node *  pmove=init_link(head);
        struct Node *  ins_ennode=NULL;
        struct Node *  ins_exitnode=NULL;
        int i=1;
        struct Node *  hhead=pmove;
        while (pmove)
        {
               // printf("%4d  ",pmove->data);
                if(pmove->next==NULL) break;     
                if(i==3)
                {
                    ins_ennode=pmove;             //保存链表断开后的指针
                    ins_exitnode=pmove->next;     //保存链表断开后的指针
                    break;
                }
                i++;
                pmove=pmove->next;
        }
        struct Node * head2;
        head2=(struct Node*)malloc(sizeof(struct Node));
        head2->data=0;
        head2->next=NULL;
        struct Node *  pmove2=init_link2(head2);
        struct Node *  sec_head=pmove2;
        while (pmove2)
        {
             //printf("%4d  ",pmove2->data);
             if(pmove2->next->next==NULL)    //把头节点绕出去
             break;     
             pmove2=pmove2->next;
        }
        struct Node *  sec_tail=pmove2;
        //下面我们要做得就是把第二个链表插入第一个链表的第三个节点的后面
        ins_ennode->next=sec_head;
        sec_tail->next=ins_exitnode;
        //遍历插入链表后的链表 并输出
        while (hhead)
        {
                if(hhead->next==NULL) break;     
                printf("%4d  ",hhead->data);
                hhead=hhead->next;
        }
        return 0;
}

/*
附效果图:
PS D:\001> ./w3
  19    18    17   109   108   107   106   105   104   103   102   101   100    16    15    14    13    12    11    10  
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-5-11 09:47:23 | 显示全部楼层
本帖最后由 jhq999 于 2022-5-11 09:51 编辑
wp231957 发表于 2022-5-10 13:19
前面都错了，也不改了，就那么地吧

这个版，功能是把一个链表插入另一个链表中间

#include <stdio.h>
#include <malloc.h>

struct Node
{
        int data;
        struct Node *next;
};

//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node));
        node1->data=x;
        node1->next=head;
        head=node1;
    }
    return head;
}


int main()
{
        struct Node * node1;
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node));
        head->data=0;
        head->next=NULL;
        //输出原始链表
        head=init_link(head);
        struct Node* p=head,*t=NULL;
        while (p)
        {
                
                printf("%4d  ",p->data);
                p=p->next;
        }

        printf("\n");
        p=t;
        while (head)
        {
                        t=head->next;
                        head->next=p;
                        p=head;
                        head=t;
        }
        head=p;
        while (p)
        {
                
                printf("%4d  ",p->data);
                p=p->next;

        }
        while (head)
        {
                        t=head->next;
                        free(head);
                        head=t;
        }
        return 0;
}
19    18    17    16    15    14    13    12    11    10     0
   0    10    11    12    13    14    15    16    17    18    19
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-11 09:52:02 From FishC Mobile | 显示全部楼层
jhq999 发表于 2022-5-11 09:47

谢谢，我现在用不了电脑，我狠好奇，你另一个链表在哪里？？？
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-11 09:52:54 From FishC Mobile | 显示全部楼层
jhq999 发表于 2022-5-11 09:47

你这是倒序！
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-11 09:54:30 From FishC Mobile | 显示全部楼层
jhq999 发表于 2022-5-11 09:47

能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-5-11 12:02:35 | 显示全部楼层
本帖最后由 jhq999 于 2022-5-11 12:12 编辑
wp231957 发表于 2022-5-11 09:54
能帮忙写一段冒泡排序吗，？？我一直好奇，究竟是排指针啊，还是移动数据呢


不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-11 12:19:12 From FishC Mobile | 显示全部楼层
jhq999 发表于 2022-5-11 12:02
不是链表反转吗，怎么还需要排序？
排序的话，感觉最好交换数据

翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

jhq999
发表于 2022-5-11 12:55:05 | 显示全部楼层
本帖最后由 jhq999 于 2022-5-11 16:24 编辑
wp231957 发表于 2022-5-11 12:19
翻转思路已经清晰了，就不用再研究了
你的思路我还需要研究一下

struct Node *end=NULL,*q;//////////没测试只是个思路
                for (p=head; p->next; p=p->next)
                {
                        for (q=head;q->next!=end;q=q->next)
                        {
                                if (q->data>q->next->data)
                                {
                                        Node t=*q;
                                        q->data=q->next->data;
                                        q->next->data=t.data;
                                }
                        }
                        end=q;
                }
指针太麻烦了
        
                struct Node list;        
                list.next=head;
                
                while(1)
                {
                        int flag=1;
                        for (prv=&list,q=list.next;q->next!=end;prv=q,q=q->next)
                        {
                                if (q->data>q->next->data)
                                {
                                        flag=0;
                                        prv->next=q->next;
                                        q->next=prv->next->next;
                                        prv->next->next=q;
                                        q=prv->next;

                                }
                        }
                        //if (q!=list.next->next)
                        if(flag)
                        {
                                head=list.next;
                                break;
                        }
                        end=q;
                }
                head=list.next;

评分

参与人数 1鱼币 +8 收起 理由
wp231957 + 8 表示感谢

查看全部评分

想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-11 17:11:56 | 显示全部楼层
jhq999 发表于 2022-5-11 12:55
指针太麻烦了

成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <stdlib.h>

struct Node
{
        int data;
        struct Node *next;
};


//带头节点的 头插法
struct Node * init_link(struct Node * s)
{
    srand((int)time(NULL));
    struct Node * head=s;
    for(int x=10;x<20;x++)
    {
        struct Node * node1=NULL;
        node1=(struct Node*)malloc(sizeof(struct Node));
        node1->data=rand()%10000;
        node1->next=head;
        head=node1;
    }
    return head;
}


int main()
{
        struct Node * head;
        head=(struct Node*)malloc(sizeof(struct Node));
        head->data=0;
        head->next=NULL;
        head=init_link(head);
        //输出原始链表
        struct Node *pmove=head;
        while (pmove)
        {
             if(pmove->next==NULL) break;     
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        printf("\n");
        //准备排序
        struct Node *end=NULL,*q,*p;
        for (p=head; p->next; p=p->next)
        {
                for (q=head;q->next!=end;q=q->next)
                {
                        if (q->data>q->next->data)
                        {
                                int  t=q->data;
                                q->data=q->next->data;
                                q->next->data=t;
                        }
                }
                end=q;
        }
        //输出排序后链表                
        pmove=head->next;
        while (pmove)
        {
             printf("%4d  ",pmove->data);
             pmove=pmove->next;
        }
        return 0;
}

/*
样例输出:
PS D:\001> ./w4
8227  9821  3215   548  4427  2807   119  6152  7995  7628  
 119   548  2807  3215  4427  6152  7628  7995  8227  9821
*/
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

wp231957
 楼主| 发表于 2022-5-13 15:18:26 | 显示全部楼层
wp231957 发表于 2022-5-11 17:11
成功了，成功了，谢谢，那个交换指针的方案，我还是不要研究了（估计我研究不了）

如果仅仅是为了逆序输出一个链表  还可以更简单些：
void reverse_link(struct Node * head)
{
    //这里正常是if(head==NULL) return;  这里我们使用带头节点的链表，所以把头节点绕过去
    if(head->next==NULL) return;  
    reverse_link(head->next);
    printf("%8d",head->data);
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-31 03:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表