数据结构oj

链表

提纯

记录一下我踩的坑吧…真够蠢的

1. 没加abs，因为题目是绝对值…
2. 删除元素以后pos应该–，或者删除的时候pos不++，传参的时候传pos+1
3. 拿一个指针记录上一次的位置！
4. 把其它题目adt复制过来了，忘了原题是个循环链表…
5. new出来的数组没有初始化0…

template<class ElemType>
void Delete_Equal_Node( LinkList<ElemType> &A, int N )
{
    int *arr = new int[N+1];
    for(int i = 0; i < N; ++i)
        arr[i] = 0;
    LinkNode<ElemType> *p = A.GetHead()->next, *t;
    int pos = 0;
    while(p)
    {
        p = p->next;
    }
    p = A.GetHead()->next;
    while(p)
    {
        if(!arr[abs(p->data)])
        {
            arr[abs(p->data)] = 1;
            t = p;
            pos++;

        }else
        {
            p = t;
            A.ListDelete(pos+1);
        }
        p = p->next;

    }
}

有序归并

当b比a长的时候，要把b接在a后边，还要注意b本身也要提纯。。

void Merge_L_Order( LinkList<ElemType> &A, LinkList<ElemType> &B )
{
    LinkNode<ElemType> *pa = A.GetHead()->next, *pb = B.GetHead()->next, *t1=A.GetHead(), *t2;
    int pos = 1;
    while(pa)
    {
        if(!pb)
            break;
        if(pb->data < pa->data)
        {

            t2 = pb->next;
            A.ListInsertNode(t1, pb);
            pa = pb;
            pb = t2;

        }else if(pb->data == pa->data)
        {
            t2 = pb->next;
            delete pb;
            pb = t2;
        }else
        {
            pos ++;
            t1 = pa;
            pa = pa->next;
        }
    }
    if(pb)
        A.GetTail()->next = pb;
    while(pb && pb->next)
    {
        if(pb->next->data == pb->data)
        {
            t1 = pb->next;
            pb->next = t1->next;
            delete t1;
        }else
        {
            pb = pb->next;
        }
    }
    if(pb)
        A.SetTail(pb);
    delete B.GetHead();
    B.GetTail()->next = NULL;
}