2.4.2 有序表的基本操作 有序表类型的基本操作和线性表类型中定义的基本操作基本相同,但由于 LocateElem 中函数参数 compare 的类型不同,(在有序表中,元素相互比较的结果将产生三种结果:"小于"、"等于"和"大于"),则该函数的定义和实现的算法也就和线性表中的不同。 |
||||
LocateElem( L, e, &q, int(*compare)(ElemType,ElemType)
) 初始条件:有序表L已存在,compare为有序判定函数。 操作结果:若有序表L中存在元素 e,则 q 指示L中第一个值为 e 的元素的位置,并返回函数值TRUE;否则 q 指示第一个大于 e 的元素的前驱的位置,并返回函数值 FALSE。 此外,在有序表中进行"插入"操作时必须保持表的有序性。也就是说,在有序表中进行插入时首先要查找插入位置,显然,上述函数返回的位置即为插入位置,即应插入在 q 指示的元素之后。 |
例如在有序表 (12,23,45,45,56,67,78,89)中查询e=45的结果为,q指向前一个"45"所在的位置,查询e=65的结果为,q指向"56"的位置,即"67"的前驱。 |