请高手帮我看看错在哪里啦 ！谢谢谢谢！

天边

题目：：假设有两个按元素值递增有序排列的线性表
A和B，均以单链表作存储结构，请编写算法将A表和B表
归并成一个按元素值递减有序（即非递增有序，允许表
中含有值相同的元素）排列的线性表C， 并要求利用原
表（即A表和B表）的结点空间构造C表。
实现下列函数：
void Union(LinkList &lc, LinkList la, LinkList lb);
/* 依题意，利用la和lb原表的结点空间构造lc表 */
单链表类型定义如下：
typedef struct LNode{
    ElemType      data;
    struct LNode *next;
} LNode, *LinkList;


我的程序：
void Union(LinkList &lc, LinkList &la, LinkList &lb)
{   struct LNode *pa,*pb,*p;
    pa=la->next; //用ha的头结点作为hc的头结点
    pb=lb->next;
    la->next=NULL;
    lc=la;
    while(pa||pb)
      { if(pa->data<=pb->data||pa)
          {p=pa;
           pa=pa->next;
           p->next=lc->next;
           lc->next=p;
          }
        else
          {p=pb;
           pb=pb->next;
           p->next=lc->next;
           lc->next=p;
          }
      }
           
}
但是结果不对 我改了很久很多次都运行结果不对  我现在还弄不懂出错在哪里 麻烦大家啦！

gdut_A

呵呵呵~~~~~
不懂得路过，顺便帮你顶起啦~

zaijzhgh

LZ,咋你将la->next = NULL;了？

天边

o 不这样做的话就不能从一开始把  lc->next=p; 而且la->已经赋给pa  应该没关系吧

zaijzhgh

可以先将链表反序之后在链接。[/b]

1. 
   
2. #include <iostream.h>
   
3. #include<stdlib.h>
   
4. 
   
5. struct LinkList
   
6. {
   
7.     int m_value;
   
8.     LinkList *next;
   
9. };
   
10. void Union(LinkList *lc, LinkList *la, LinkList *lb);
    
11. 
    
12. int main()
    
13. {
    
14.     LinkList arraya[5], arrayb[5];
    
15.         for(int i = 0; i < 5; i++)
    
16.         {
    
17.                 arraya[i].m_value = i;
    
18.                 arrayb[i].m_value = i + 1;
    
19.                 if (i == 4)
    
20.                 {
    
21.                         arraya[i].next = NULL;
    
22.                         arrayb[i].next = NULL;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         arraya[i].next = &arraya[i+1];
    
27.                         arrayb[i].next = &arrayb[i+1];
    
28.                 }
    
29.         }
    
30. 
    
31. 
    
32. 
    
33.     LinkList *la = arraya;
    
34.     LinkList *lb = arrayb;
    
35.         LinkList *tmp;
    
36.         LinkList *head = (LinkList*)malloc(sizeof(LinkList));
    
37.         head->m_value = 100;
    
38.         head->next = NULL;
    
39.         Union(head, la, lb);
    
40.    
    
41.     free(head);
    
42.        
    
43.     return 0;
    
44. }
    
45. 
    
46. 
    
47. void Union(LinkList *lc, LinkList *la, LinkList *lb)
    
48. {
    
49.         struct LinkList *p, *q;
    
50.         struct LinkList *head;
    
51. 
    
52.         //由于链表la和链表lb是递增的，而要求lc是递减的，所以需要先
    
53.         //将la和lb反序才能符合要求
    
54.          
    
55.         //将la链表反转
    
56.         if(la->next == NULL || la->next->next == NULL)
    
57.                 ;
    
58.         else
    
59.         {
    
60.                 p = la->next;
    
61.                 q = p->next;
    
62.                 p->next = la;
    
63.                 la->next = NULL;
    
64.                 while (q != NULL)
    
65.             {
    
66.                 la = p;
    
67.                 p = q;
    
68.                 q = q->next;
    
69.                 p->next = la;
    
70.             }
    
71.             la = p;
    
72.         }
    
73.        
    
74.        
    
75.        
    
76.         //将lb链表反转
    
77.         if(lb->next == NULL || lb->next->next == NULL)
    
78.         ;
    
79.         else
    
80.         {
    
81.                 p = lb->next;
    
82.                 q = p->next;
    
83.                 p->next = lb;
    
84.                 lb->next = NULL;
    
85.                 while (q != NULL)
    
86.             {
    
87.                 lb = p;
    
88.                 p= q;
    
89.                 q = q->next;
    
90.                 p->next = lb;
    
91.             }
    
92.             lb = p;
    
93.    
    
94.         }
    
95. 
    
96.         //逐个对比
    
97.         head = lc;
    
98.         while(la && lb)
    
99.         {
    
100.                 if(la->m_value >= lb->m_value)
     
101.                 {
     
102.                         lc->next = la;
     
103.                         la = la->next;       
     
104.                 }
     
105.                 else
     
106.                 {
     
107.                         lc->next = lb;
     
108.                         lb = lb->next;
     
109.                 }
     
110.                 lc = lc->next;       
     
111.         }
     
112.         //接上剩余的链表元素
     
113.         if(la)
     
114.                 lc->next = la;
     
115.         if(lb)
     
116.                 lc->next = lb;
     
117. 
     
118.         lc = head->next;
     
119.         //this is only for test
     
120.         while (lc != NULL)
     
121.     {
     
122.         cout<<"lc->m_value:"<<lc->m_value<<endl;
     
123.         lc = lc->next;
     
124.     }
     
125. }
     

复制代码

iptton

la->next = NULL; 破坏了原表数据了

刚开始做这种题时最好能用笔在纸上把你的算法一步一步地画一画(当然如果你熟练了就不必要多此一举了)

jhui163

lz的想法不够全面哦，你没有将pa和pb为空的情况考虑好，我用你的想法重新写了一点，就成功了，

jhui163

void Union(LinkList &lc, LinkList &la, LinkList &lb)
{   struct LNode *pa,*pb,*p;
    pa=la->next; //用la的头结点作为lc的头结点
     pb=lb->next;
    la->next=NULL;
    lc=la;
    while(pa||pb)
      { if(pa==0)
          {p=pb;
           pb=pb->next;
           p->next=lc->next;
           lc->next=p;
          }
       else if(pb==0)
          {p=pa;
           pa=pa->next;
           p->next=lc->next;
           lc->next=p;
          }
        else if(pa->data<=pb->data&&pa)
          {p=pa;
           pa=pa->next;
           p->next=lc->next;
           lc->next=p;
          }
        else
          {p=pb;
           pb=pb->next;
           p->next=lc->next;
           lc->next=p;
          }
      }
           
}

jhui163

你可以将你的if和else的括号内容又编写为一个函数，那么你的主函数就看起来可读性高了。你学的课程应该跟我的一样。这是 数据结构 2.24 4级的难度题，。。。

天边

谢谢 谢谢大家！

kylewong

好像很多公司笔试的时候出过这类型的题~！