データ構造問題010:秩序化された単一チェーンテーブルの交差(ANSI C)

テーマ:2つの非減衰秩序の単一チェーンテーブルを設置し、アルゴリズムを編纂して両者の交差(チェーンテーブルの形式で保存)を求め、交差中の要素が増加秩序を維持することを要求する.
解析:この問題の鍵は、隣接する重複要素をスキップすることです.

/*
 * Intersection of two non-descending linked lists.
 *
 * fduan, Dec. 28, 2011.
 */
void intersection( link_list lst_a, link_list lst_b, link_list * lst_i )
{
	node_ptr pa = lst_a->next, pb = lst_b->next, s = NULL, p = NULL;
	int e1, e2;

	init_llist( lst_i );
	p = *lst_i;

	while( pa != NULL && pb != NULL )
	{
		if( pa->data < pb->data )
			pa = pa->next;
		else if( pa->data > pb->data )
			pb = pb->next;
		else
		{
			s = ( node_ptr )malloc( sizeof( node ) );
			s->data = pa->data;
			s->next = NULL;
			p->next = s;
			p = s;
			
			e1 = pa->data; 
			e2 = pb->data;
			
			pa = pa->next;
			pb = pb->next;

			while( pa != NULL && pa->data == e1 )
				pa = pa->next;

			while( pb != NULL && pb->data == e2 )
				pb = pb->next;
		}
	}
}