太原理工大学软件学院数据结构-第二章 - 图文

intLocateElem_Sq(SqList L, ElemType e,Status(*compare)(ElemType, ElemType)) {

//在顺序表中查询第一个满足判定条件的数据元素，//若存在，则返回它的位序，否则返回0

i = 1; //i 的初值为第1 元素的位序p = L.elem;//p 的初值为第1 元素的存储位置while(i <= L.length &&

!(*compare)(*p++, e))(*compare)(*p++, e)++i;

if(i <= L.length) returni;else return0;

算法的时间复杂度为：

}// LocateElem_SqO( ListLength(L) )

线性表操作

ListInsert(&L, i, e)的实现：

首先分析:

插入元素时，

线性表的逻辑结构发生什么变化？

(a1, …, ai-1, ai, …, an) 改变为

(a1, …,ai-1, e, ai, …, an)

,

a1a2…ai-1ai…ana1a2…ai-1eai…an表的长度增加StatusListInsert_Sq(SqList &L, int i, ElemType e) {//在顺序表L的第i 个元素之前插入新的元素e,// i 的合法范围为1≤i≤L.length+1

……

q = &(L.elem[i-1]); // q 指示插入位置for(p = &(L.elem[L.length-1]); p >= q; --p)

*(p+1) = *p; // 插入位置及之后的元素右移*q = e; // 插入e

++L.length; // 表长增1return OK;算法时间复杂度为:}// ListInsert_Sq

O( ListLength(L) )