分享和关爱由此萌生,测试的人生会像流水和氧气 ,逐渐逐渐染绿了山河,染蓝了天空,萌生了飞鸟鱼虫,遍地都是生命。这是寒武纪带给我们的这份喜悦和希望。

发布新日志

  • 算法学习之第三篇——有序链表的集合的并操作

    2014-09-07 22:51:02

    void unionSet(DISJSETS * S1,DISJSETS * S2)
    {
    EleNode *p = S1 -> head -> next, *q = S2 -> head -> next,
    *t = S1 -> head ;
    while (p!= NULL && q!= NULL)
    {
    if (p->ele ==q->ele)//如果P表的元素和q表的元素的值一致
    {
    t-> next= p; p=p->next;q=q->next;//确定t之后链接的是p,p因为当前的数值是有效的所以向后移动一位,q因为当前的是和p一致的,所以向后移动一位,p和q同时开始考察后面的数据。
    }
    else if (p->ele < q->ele)//如果此时p的值小于q的值
    {
    t->next = p; p= p ->next; //这时候,需要考虑p,p也参与了最终的链表,确定t之后链接的是p,p向后移动一位。

    }
    else{ //如果此时q的值小于p的值。

    t->next = (EleNode *)malloc(sizeof(EleNode));//因为,总是考虑小的一部分,所以此时,应该考虑q的值,而需要将q的值参与到p的链表之中,所以需要新建一个节点,以放入q的那个值,同时确定t-〉next是到达那个节点的。
    t->next->ele = q->ele; q= q->next;
    //确定新的节点放入的是q的值,然后q向后移动一位,以考察后面的q。
    }
    t=t->next;
    //t向后移动一位,到达当前的,新的节点。下次t->next 就是存放下一轮的新节点。
    }
    if (p!=NULL)//如果最后,还有p剩下来

    t->next = p;//因为p本来就是有序的,将多余的p放入t->next;

    else{//如果最后q剩下来
    while (q!=NULL)
    {t->next = (EleNode *)malloc(sizeof(EleNode));
    t->next ->ele = q-> ele; t= t->next;
    q= q->next;
    }//新建节点,将t->next放入q的当前值,t向后移动,q向后移动,一直到q为NULL就截止。
    t->next = NULL;
    最后将t->next置为NULL

    }


    ****************
    现在我想举一个例子来做一下这个算法。
    S1:head 123456
    S2:head 456789
    t = S1->head
    t->next = 1; p=2;t=1;
    t->next = 2; p=3;t=2;
    t->next = 3; p=4;t=3;
    t->next = 4; p=5;q=5;t=4;
    t->next = 5; p=6;q=6;t=5;
    t->next = 6; p=null;q=7;t=6;
    t->next = 7; t=7; q=8;
    t->next = 8; t=8; q=9;
    t->next = 9; t=9; q=null;
    t->next = NULL;

    结果就是
    123456789

    就好像,t是一个敲定的值,而q和p是试探的值,所以t总是慢一拍,等到确定了q还是p之后,才会确定t。

    而且总是取p q中小的一个值,谁小取谁,也许这就是一种规律。

    因为已经是有序的,所以一开始看哪个比较小,小的就“放行”,因此一开始,
    S1 链表的1 2 3 都被“放行”,到达4 的时候,发现p和q都含有 4,所以 p和q的“4”都要“放行“,随之 p和 q的 ”456“都”放行“了,此时,S1表的数值都”放行“完毕,剩下的是,S2表的数值,就链接在最后。


  • 算法学习之第二篇——顺序查找

    2014-09-02 21:22:31

    typedef struct{
    KeyType key;
    infoType otherinfo;
    }NodeType;

    typedef NodeType SeqList[n+1];

    int SeqSearch(Seqlist R, KeyType K)
    {
    int i;
    R[0].key=K;
    for(i=n;R[i].key != K; i--);
    return i;
    }
    从后面往前面查找,如果没有查找到,则返回的是0,也就是第一个值,因为第一个值总是K。


  • 算法学习之第一篇——二分查找

    2014-09-02 20:34:08

       现在我主要针对2本书,《数据结构》,《算法基础》来细细品味一个又一个算法。

    二分查找

    typedef struct{
    KeyType key;
    infoType otherinfo;
    }NodeType;

    typedef NodeType SeqList[n+1];

    int BinSearch(SeqList R, KeyType K)
    {
    int low = 1 ,high = n, mid;
    while(low<high)
    {mid = (low + high)/2;
    if(R[mid].key == K) return mid;
    if(R[mid].key>K)
    high = mid -1;
    else
    low = mid +1 ;
    }
    return 0;
    }
    在一串数字(一个已经排好顺序的数组)中,确定中间的一个数字。
    如果要查找的数字比中间的大,那么就在中间的数字以后的区域中查找;
    如果要查找的数字和处于中间的数字是一样大的,那么就返回这个数字。

    比如
    44 55 66 88 99
    寻找88

    首先确定是在 88 99 之间寻找
    然后 然后它们中间的数就是88
    于是就等于要查找的数字。

Open Toolbar