注册 登录
编程论坛 数据结构与算法

各位大神看下我这个算法

hunner5 发布于 2013-10-18 17:01, 509 次点击
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

# define TRUE 1
# define ERROR 0
# define OK 1
# define OVERFLOW -2
# define FALSE 0

typedef struct lnode
{
    int data;
    struct lnode *next;
} *linklist;


int getelem(linklist la,int i,int &e)
{
    linklist p;
    int j=1;
    p=la->next;
    while(p&&j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    e=p->data;
    return OK;
}
void creatlist(linklist &l,int n){

    l=(linklist)malloc(sizeof(lnode));
    l->next=NULL;
    for(int i=n;i>0;--i)   
    {
        linklist p;   
        p=(linklist)malloc(sizeof(lnode));
        scanf("%d",&p->data);
        p->next=l->next;
        l->next=p;
    }

}
int listinsert(linklist &l,int i,int e)
{
    linklist p;
    int j=1;
    p->next=l;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)
        return ERROR;
    linklist s;
    s=(linklist)malloc(sizeof(lnode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}
void Union(linklist &la,linklist lb)//重点就是这个函数
{
    int e,f;
    int k=1,m=1;
    linklist p,b;
    p=la->next;
    while(p)
    {
        p=p->next;
        k++;
    }
    b=lb->next;
    while(b)
    {
        b=b->next;
        m++;
    }   
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=k;i++)
        {
            getelem(la,i,e);
            getelem(lb,j,f);
            if(e==f)
                break;
        }
        if(i>k)
            listinsert(la,i,f);
    }
}
void mergelist(linklist la,linklist lb,linklist &lc)
{
    linklist pa,pb,pc;
    pa=la->next;
    pb=lb->next;
    lc=pc=la;
    while(pa&&pb)
    {
        if(pa->data<=pb->data)
        {
            pc->next=pa;pc=pa;pa=pa->next;
        }
        else
        {
            pc->next=pb;pc=pb;pb=pb->next;
        }
    }
    pc->next=pa?pa:pb;
    free(lb);
}

void main()
{
    linklist la,lb,lc;
    creatlist(la,2);
    creatlist(lb,3);
    Union(la,lb);
    while(la->next)
    {
        printf("2%d",la->next->data);
        la=la->next;
    }
/*    creatlist(la,5);//这一段先不管 只运行UNION函数,每次都被关闭了
    creatlist(lb,5);
    mergelist(la,lb,lc);
    while(lc->next)
    {
        printf("lc=%d",lc->next->data);
        lc=lc->next;
    }
*/
  }
4 回复
#2
yuccn2013-10-18 21:51
调试一下看看?

不过你的联合的算法逻辑不对把,

    for(int j=1;j<=m;j++)
     {
         for(int i=1;i<=k;i++)
         {
             getelem(la,i,e);
             getelem(lb,j,f);
             if(e==f)
                 break;
         }
         if(i>k)
             listinsert(la,i,f);
     }
b的遍历每个元素,每一元素在a中找不到,就插入。这样才是联合把。不过你的联合的想法。我看不懂。为什么每次都是取第i个来比较?
#3
hunner52013-10-20 19:39
回复 2楼 yuccn
我是这样想的,比如
1 2 4 5 7
1 3 5 6 5
先取第二行第一个元素和第一行第一个元素比较,如果相等,那么肯定不插入的吧,第二行的指针就向后移一位,所以break,第一个循环,进入第二个循环,如果不相等的话,进行第二个循环,也就是第一行元素向后移一位,一直比,当全部比完没有一个相等的话, 循环K次,i>k,则插入这个元素,然后第二行向后移一位进行同样操作。
#4
qunxingw2013-10-21 11:48
逻辑应该有问题,当La中插入结点后,该链的长度应该变化。但你的k值却是原长
#5
hunner52013-11-10 17:17
以下是引用qunxingw在2013-10-21 11:48:43的发言:

逻辑应该有问题,当La中插入结点后,该链的长度应该变化。但你的k值却是原长
谢谢,我已经知道哪里的问题了,是插入那个函数出了问题,UNION函数我一步一步检查了,没有错,还是谢谢你!
1