| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1368 人关注过本帖
标题:二路归并,有一步无法理解,希望有明白的指点一下!
只看楼主 加入收藏
wyh416
Rank: 1
等 级:新手上路
帖 子:31
专家分:0
注 册:2020-10-9
结帖率:33.33%
收藏
已结贴  问题点数:16 回复次数:3 
二路归并,有一步无法理解,希望有明白的指点一下!
单链表的二路归并算法:
    已经产生两单链表,要将这两个单链表再不分配新的情况下并入一个新的单链表中,让一个已存在的链表的头结点作为新链表的头结点,在创建一个指针一直指向新链表的尾结点;
    void erlu(SLinkNode *ha,SLinkNode *hb,SLinkNode *hc)
    {
        SLinkNode *pa=ha->next;*pb=hb->next;*tc;
        hc=ha;       //将ha的头节点作为hc的头结点

        tc=hc;       //让tc一直指向hc的尾节点

        free(hb);
这是我从书上抄的一段代码,hc是要二路并入后的链表
      我想问一下这个里面   tc=hc;  让tc指向hc尾节点,为什么可以这样写,感觉怪怪的,不知道怎么理解,希望有理解的给我解释一下,我对于链表的理解是不是有什么遗漏!
搜索更多相关主题的帖子: 单链表 链表 tc 二路归并 结点 
2021-09-26 13:02
自由而无用
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:61
专家分:1456
注 册:2021-8-9
收藏
得分:8 
after the statement tc = hc, insert printf to check out the address of the list pointer(tc)
tc = hc;
printf("tc = %p, hc = %p\n", tc, hc);

good luck!
2021-09-26 13:33
自由而无用
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:61
专家分:1456
注 册:2021-8-9
收藏
得分:0 
another reference:
https://blog.
2021-09-26 13:36
自由而无用
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:61
专家分:1456
注 册:2021-8-9
收藏
得分:0 
//online parser: https://www.bccn.net/run/
程序代码:
#include <stdio.h>
#include <stdlib.h>

#pragma GCC diagnostic ignored "-Wint-conversion"

typedef int ElmeType;

typedef struct node{
    ElmeType data;
    struct node *next;
}SLinkNode, *PSN;

//#define PRINT_ON

//For keeping prototype disusing **L
void InitList(SLinkNode *L)
{
    PSN M;

//#define SET_ADDR(_m) *(int *)(_m)
    //SET_ADDR(L) = (PSN)malloc(sizeof(SLinkNode));
#ifdef PRINT_ON
    //printf("*L = %p\n", L);
#endif
    M = (PSN)malloc(sizeof(SLinkNode));
#define CAST2IDA(_m, _ida) ((PSN)(&(*_m)))->_ida
    CAST2IDA(L, data) = M;
    M->data = 125;
    M->next = NULL;
#ifdef PRINT_ON
    printf("M(*L) = %p\n", M);
    printf("M->data = %d\n", M->data);
    printf("M->next = %p\n", M->next);
    printf("end of %s\n", __func__);
#endif
}

int main(int argc, char *argv[])
{
    SLinkNode *L = (PSN)InitList;

    InitList((PSN)&L);

#ifdef PRINT_ON
    printf("L = %p\n", L);
    printf("L->data = %d\n", L->data);
    printf("L->next = %p\n", L->next);
    printf("end of %s\n", __func__);
#endif
    free(L);

    return 0;
}


output sample:


M(*L) = 0x672010
M->data = 125
M->next = (nil)
end of InitList
L = 0x672010
L->data = 125
L->next = (nil)
end of main

[此贴子已经被作者于2021-9-26 14:53编辑过]

2021-09-26 14:50
自由而无用
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:61
专家分:1456
注 册:2021-8-9
收藏
得分:0 
//online parser: https://www.bccn.net/run/
程序代码:
#include <stdio.h>
#include <stdlib.h>

#pragma GCC diagnostic ignored "-Wint-conversion"

//#define PRINT_ON
#define STATE_POLL 0
#define Trans_real_Arg 0

typedef int ElmeType;
typedef struct node {
    ElmeType data;
    struct node *next;
}SLinkNode, *PSN;

#define stub
#define public typedef
#define class struct
//portable oo-style ??
public class  v {
    unsigned char state;
    PSN addr;
    int vtbl[2];
}vs, *pvs;

static pvs vm;

//bottom layer
void __post_local_address(PSN addr)
{
    vm->addr = addr;
#ifdef PRINT_ON
    printf("addr = %p\n", addr);
    printf("vm->addr = %p\n", vm->addr);
#endif
}

PSN __recv_external_address(void)
{
    return vm->addr;
}

//mid layer
void _register_state_func(int fa)
{
    static int idx = 0;
    
    vm->vtbl[idx++] = fa;
    //boundary alert: state < 0xFF
    vm->state++;
}

int _main(int argc, char **argv)
{
    //BUG_ON
    vm = (pvs)malloc(sizeof(vs));
    //interface register mannually
    _register_state_func(__post_local_address);
    _register_state_func(__recv_external_address);
    
#ifdef PRINT_ON
    printf("vm = %p\n", vm);
    printf("end of %s\n", __func__);
#endif

    return 0;
}

//For keeping prototype disusing **L
void InitList(SLinkNode *L)
{
    PSN M;
    
    M = (PSN)malloc(sizeof(SLinkNode));

#if Trans_real_Arg == 0
typedef int (*ra)(void);
#define RDY_STATE(_s) (_s >> 4) & 0x01
    //Address trunc occurred!!!
    //L = ((ra)(vm->vtbl[STATE_POLL + RDY_STATE(vm->state)]))();
    //no trunc!
    L = __recv_external_address();
#ifdef PRINT_ON
    printf("revc L = %p\n", L);
#endif
#endif//Trans_real_Arg block

//#define SET_ADDR(_m) *(int *)(_m)
    //SET_ADDR(L) = (PSN)malloc(sizeof(SLinkNode));
#define CAST2IDA(_m, _ida) ((PSN)(&(*_m)))->_ida
    CAST2IDA(L, data) = M;
    M->data = 125;
    M->next = NULL;
#ifdef PRINT_ON
    printf("M(*L) = %p\n", M);
    printf("M->data = %d\n", M->data);
    printf("M->next = %p\n", M->next);
    printf("end of %s\n", __func__);
#endif
}

//main branch top layer
int main(int argc, char *argv[])
{
    int i = 1;

    SLinkNode *L = (PSN)InitList;
#ifdef PRINT_ON
    printf("L(addr) = %p\n", &L);
#endif
#define  T_PTR(_p) (void *)(_p)
    _main(1, T_PTR("register callback function"));
#if Trans_real_Arg == 1
    //Transfering real arguments
    InitList((PSN)&L);
#else//Trans_real_Arg block
#define LOWBYTE(_b) (_b) & 0x0f
#define STATE_N(_s) LOWBYTE(_s)
    while (i++ < STATE_N(vm->state)) {
#define RDY_POST(_s) ((_s) >> 4) & 0x01
        if (!RDY_POST(vm->state)) {
typedef void (*pa)(int);
#ifdef PRINT_ON
            //BUG_ON trunc address
            printf("__int64 trunc: &L = %p\n", (PSN)&L);
#endif
            //Address trunc occurred!!!
            //((pa)(vm->vtbl[STATE_POLL + 0]))((PSN)&L);
            //no trunc!
            __post_local_address((PSN)&L);
#define SET_POST(_s) (_s) |= 0x10
            SET_POST(vm->state);
            //Transfering formal arguments ? 2333
            InitList(L);
        } else {
#define bus_stub
            bus_stub;
#define switch_ctx()
            switch_ctx();
        }
    }
#endif//Trans_real_Arg

#ifdef PRINT_ON
    printf("L = %p\n", L);
    printf("L->data = %d\n", L->data);
    printf("L->next = %p\n", L->next);
    printf("end of %s\n", __func__);
#endif
    free(L);

    return 0;
}


output sample:

L(addr) = 0x7ffd15da8860
vm = 0x1dde020
end of _main
__int64 trunc: &L = 0x7ffd15da8860
addr = 0x7ffd15da8860
vm->addr = 0x7ffd15da8860
revc L = 0x7ffd15da8860
M(*L) = 0x1dde040
M->data = 125
M->next = (nil)
end of InitList
L = 0x1dde040
L->data = 125
L->next = (nil)
end of main
2021-09-27 17:20
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:8 
你滴代码没抄全

void erlu(SLinkNode *ha,SLinkNode *hb,SLinkNode *hc)
    {
        SLinkNode *pa=ha->next;*pb=hb->next;*tc;
        hc=ha;       //将ha的头节点作为hc的头结点

        tc=hc;      
        while (tc->next != NULL)
        {
            tc = tc->next;//让tc一直指向hc的尾节点
        }

        tc->next = hb;//连起来了

        free(hb);
2021-09-28 15:57
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
另外说一下,你这函数传参hc是无法改变调用者的实际hc,要么用return返回,要么传参用SLinkNode **。
还有因为未申请新的堆空间,你用free(hb),会将你新串联好的表后半部给回收了,导致异常。
如果书上就是这么写的,建议你赶紧换个书看,这书作者水平太次。
2021-09-28 16:20
diycai
Rank: 8Rank: 8
等 级:贵宾
威 望:19
帖 子:147
专家分:895
注 册:2021-5-18
收藏
得分:0 
#include "stdio.h"
#include "stdlib.h"

typedef struct SLinkNode
{
    int value;
    struct SLinkNode *next;
} SLinkNode;

void erlu(SLinkNode *ha,SLinkNode *hb,SLinkNode **hc)
{
    SLinkNode *tc;
    *hc=ha;       //将ha的头节点作为hc的头结点

    tc=*hc;      
    while (tc->next != NULL)
    {
        tc = tc->next;//让tc一直指向hc的尾节点
    }

    tc->next = hb;//连起来了

//    free(hb);

   
}

void main()
{
    int i;
    SLinkNode *a[8];
    SLinkNode *b[8];
    SLinkNode *c;

    for (i=0; i<8; i++)
    {
        a[i] = (SLinkNode *)malloc(sizeof(SLinkNode));
        a[i]->value = 8-i;
        if (i == 0)
        {
            a[i]->next = 0;
        }
        else
        {
            a[i]->next = a[i-1];
        }

        b[i] = (SLinkNode *)malloc(sizeof(SLinkNode));
        b[i]->value = 16-i;
        if (i == 0)
        {
            b[i]->next = 0;
        }
        else
        {
            b[i]->next = b[i-1];
        }
    }

    erlu(a[7], b[7], &c);

    for (i=0; i<16; i++)
    {
        printf("%d ", c->value);
        c = c->next;
    }
    printf("\n");
}
2021-09-28 16:28
快速回复:二路归并,有一步无法理解,希望有明白的指点一下!
数据加载中...
 
   



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

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