论坛 › 【编程】编程圣殿 › 请高手帮我看看错在哪里啦 ！谢谢谢谢！

天边 发表于 2009-4-10 21:58

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

题目：：假设有两个按元素值递增有序排列的线性表
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 发表于 2009-4-10 22:04

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

zaijzhgh 发表于 2009-4-10 23:24

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

天边 发表于 2009-4-11 00:51

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

zaijzhgh 发表于 2009-4-11 09:40

可以先将链表反序之后在链接。[/b]
#include <iostream.h>
#include<stdlib.h>

struct LinkList
{
    int m_value;
    LinkList *next;
};
void Union(LinkList *lc, LinkList *la, LinkList *lb);

int main()
{
    LinkList arraya, arrayb;
        for(int i = 0; i < 5; i++)
        {
                arraya.m_value = i;
                arrayb.m_value = i + 1;
                if (i == 4)
                {
                        arraya.next = NULL;
                        arrayb.next = NULL;
                }
                else
                {
                        arraya.next = &arraya;
                        arrayb.next = &arrayb;
                }
        }



    LinkList *la = arraya;
    LinkList *lb = arrayb;
        LinkList *tmp;
        LinkList *head = (LinkList*)malloc(sizeof(LinkList));
        head->m_value = 100;
        head->next = NULL;
        Union(head, la, lb);
   
    free(head);
       
    return 0;
}


void Union(LinkList *lc, LinkList *la, LinkList *lb)
{
        struct LinkList *p, *q;
        struct LinkList *head;

        //由于链表la和链表lb是递增的，而要求lc是递减的，所以需要先
        //将la和lb反序才能符合要求
       
        //将la链表反转
        if(la->next == NULL || la->next->next == NULL)
                ;
        else
        {
                p = la->next;
                q = p->next;
                p->next = la;
                la->next = NULL;
                while (q != NULL)
            {
              la = p;
              p = q;
              q = q->next;
              p->next = la;
            }
            la = p;
        }
       
       
       
        //将lb链表反转
        if(lb->next == NULL || lb->next->next == NULL)
        ;
        else
        {
                p = lb->next;
                q = p->next;
                p->next = lb;
                lb->next = NULL;
                while (q != NULL)
            {
              lb = p;
              p= q;
              q = q->next;
              p->next = lb;
            }
            lb = p;
   
        }

        //逐个对比
        head = lc;
        while(la && lb)
        {
                if(la->m_value >= lb->m_value)
                {
                        lc->next = la;
                        la = la->next;       
                }
                else
                {
                        lc->next = lb;
                        lb = lb->next;
                }
                lc = lc->next;       
        }
        //接上剩余的链表元素
        if(la)
                lc->next = la;
        if(lb)
                lc->next = lb;

        lc = head->next;
        //this is only for test
        while (lc != NULL)
    {
      cout<<"lc->m_value:"<<lc->m_value<<endl;
      lc = lc->next;
    }
}

iptton 发表于 2009-4-11 11:02

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

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

jhui163 发表于 2009-4-11 20:26

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

jhui163 发表于 2009-4-11 20:27

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 发表于 2009-4-11 20:30

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

天边 发表于 2009-4-12 13:14

谢谢 谢谢大家！

kylewong 发表于 2009-6-27 17:35

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

查看完整版本: 请高手帮我看看错在哪里啦 ！谢谢谢谢！