2.1.2 线性表类型的应用

例题 例2-3 判别两个集合是否相等。

　　两个集合相等的充分必要条件是它们具有相同的元素。当以线性表表示集合时，两个线性表的长度应该相等，且表中所有数据元素都能一一对应，但相同的数据元素在各自的线性表中的"位序"不一定相同。
　　由此，"判别两个线性表中的数据元素是否完全相同"的算法的基本思想为：首先判别两者的表长是否相等；在表长相等的前提下，如果对于一个表中的所有元素，都能在另一个表中找到和它相等的元素的话，便可得到"两个线性表表示的集合相等"的结论；反之，只要有一个元素在另一个表中不能找到相等元素时，便可得出"不等"的结论。
　
  



  思考题 这个算法是否在任何情况下都正确，会不会有例外的情况？
 
  程序段　算法2.3
　　bool isEqual(List LA, List LB)
　 {
　　// 若线性表 LA 和 LB 不仅长度相等，且所含数据元素也相同，
　　// 则返回 TRUE，否则返回 FALSE。
　　La_len = Listlength(LA);
　　Lb_len = Listlength(LB);
 
  思考题 如果"集合"中的元素不能保证都相异，那么这个问题的算法应如何写？
 
  　　if ( La_len != Lb_len ) return FALSE; // 两表的长度不等
　　else
　　{
　　　i = 1; found = TRUE;
　　　while ( i<= La_len && found )
　　　{
　　　　GetElem( LA, i, e );　　　　　　　　　// 取得 LA 中一个元素
　　　　if ( LocateElem(LB, e, equal( ) )
　　　　　i++; 　　　　　　　　　　　　　　　　 // 依次处理下一个
　　　　else found = FALSE;　　　 　　　　　 // LB中没有和该元素相同的元素
　　　} // while
　　　return found;
　　} // else
　} // isEqual 		  　　两个线性表的长度不等说明所表示的两个集合的大小不同。


　　退出 while 循环可能有两种情况：一是因i>La_len，说明LA中所有数据元素都能在LB中找到对应元素，由于循环中没有对变量 found 赋值，则循环结束时 found 的值仍为 TRUE；二是因found=FALSE，则是因为对 LA 中某个元素，没有在 LB 中找到对应元素，found 被赋值为 FALSE。由此 while 循环结束时变量 found 的值即为 else 情况下的变量值。