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

{

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 = 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表的数值，就链接在最后。