小弟刚刚自学数据结构,有一处不明,请高人指点一二, 谢谢 先

我用的书是李春保<数据结构考研指导>的,这个人应该很有名气啊,不过我觉得这本书好像有些错误,不知道是不是我水平太差 ,:(
有个数据结构的题目,"有两个带头节点的循环单链表ha和hb,设计一个算法将它们首尾合并成一个带头结点的循环单链表hc,要求不改变单链表HA和hb占用的存储空间,
给的答案如下,但是下面的程序用到了malloc函数,不就是申请新的存储空间么? 
请问一下 ,下面 用/*/ 号的句子是不是已经申请了新的存储空间了?该程序符合题目的要求么? 

[解]
按题意,本例要求复制ha和hb的结点并按顺序生成hc,其过程是首先创建hc头结点,再用p遍历ha的结点,边遍历边复制生成结点*s,将*s链接到hc之后,对hb进行同样的操作,算法如下
slink *link(slink *ha,slink *hc,slink *hb)

 {  
   slink *hc ,*p,*s,*rc;
   hc-(slink*)malloc(sizeof(slink)); 
  rc=hc;
  p=ha->next;
  while(p!=ha)
   { s= (slink*) malloc(sizeof(slink));   /***********/
     s->data=p->data;
     rc->next=s;
     rs=s;
}
p=hb->next;
while(p!-hb)
{
   s=(slink*)malloc(size(slink);    /****************/
   s->data=p->data;
   rc->next=s;
   rs=s;
}
  rc->next=hc;
  return  hc;

}

14 个解决方案

#1

动态申请一个块空间，然后把头指针赋给S,指向头节点！

#2

我知道是动态申请空间,但问题在于是否满足题目要求的"不改变单链表HA和hb占用的存储空间"么? 
谢谢

#3

我觉得只要申请一个hc的头节点然后修改ha、hb尾节点的next指针的指向就可以了，不用另外申请所有的节点空间

#4

楼上的.我只是想问问 啊.用了malloc 函数.是否申请了新的内存空间,也就是说,没有满足题目要求的"不改变单链表HA和hb占用的存储空间" 晕啊. 这个问题我觉得我问的应该很清楚吧 .

#5

应该是重新申请了新的内存空间，新建了循环单链表hc。但它也确实没改变ha、hb的存储空间啊，如果调用了该函数，ha、hb无任何变化啊。如果申请一个hc的头节点然后修改ha、hb尾节点的next指针，则ha、hb便在该函数中发生了改变

#6

申请了新的内存空间
<>
"改变单链表HA和hb占用的存储空间"

#7

回复人： rtdb(东临碣石) ( ) 信誉：100  2004-07-16 14:05:00  得分: 0  
 
 
   申请了新的内存空间
<>
"改变单链表HA和hb占用的存储空间"

  
 



可否说明  why?

#8

呵呵，对不起哦，我想错了。其实，仔细想想，这道题的意思不就是要另外建一个链表，元素值是A+++B，同时对A和B不做任何动作！
申请新的内存空间是不会改变HA和HB已经占用的存储空间的。HC每申请一个新节点后，将HA或HB中对应节点的值付给它，HC新节点的next指针的指向随之改变，但是对HA、HB没有进行改动：元素值、元素指针都没变，也没有给它们申请新的存储空间，所以，它们占用的存储空间也就没有变化。

#9

开辟的是指针接点吧，只是让指针的指向发生改变，而实际的地址没变吧，具体的也说不清楚，你可以先把原来链表的内存地址输出来，生成新的后再输出看看是不是改变了！

#10

听了各位的解释,尤其是 hdmykun(心铃儿动) 的.我好像明白了一些了.程序中生成一个新的指针指向原来存贮数据的内存空间,只是存贮指针的存贮结构变化了.但是数据的存贮结构没有变化.而题目只是要求数据结构不发生变化,对于指针的结构,却不做要求,不知道我的理解是不是正确的. 谢谢.

#11

HA、HB的节点的指针指向也没有变
打个比方：甲乙两个人，甲的手指着乙，我们顺着甲的手指就看到了乙；这时又来了一个人丙，他的手也指着乙，我们同样顺着他的手可以找到乙；乙呢，我们没有让他变化，同时，甲也没有变化，他的手还是指着乙，我们还是可以顺着甲的手找到乙的。
注意，这个比方只是帮助理解指针，不是针对你上面的程序，你的程序只是对新申请的hc的节点付值、修改hc的指针，并没有对ha、hb操作

#12

谢谢.似乎有些了解了

#13

我想再问一下,程序中可否不用新定义一个s结点呢?
比如 while(p!=ha)  
     {  s=  (slink*)  malloc(sizeof(slink));      /***********/  
         s->data=p->data;  
         rc->next=s;  
         rs=s;  
}  
改为while(p!=ha)  
     {  
        rc->next=p;       
         rc=p;
         p=p->next;         
}  

反正hc的头指针是没有变的 最后返回HC的头指针就可以了.这样写,有错误么? 谢谢

#14

但是,ha和hb的尾节点的next指针的指向是要改变的,这是循环链表,你想想看,这样就不符合题目要求了