2.1线性表及其逻辑结构 2.基本运算 A NetlIst(U):初始化线性表:构造一个空的线性 表 e Destroylist(:销毁线性表:释放线性表L占 用的内存空间。 A Listempty(L:判线性表是否为空表:着L为 空表则返回真否则返回假 e Listlengthe(D:求线性表的长度:返回L中元素 个数。 Displist(:输出线性表:当线性表L不为空时 ,顺序显示L中各结点的值域
6 2.1线性表及其逻辑结构 2.基本运算 InitList(L): 初始化线性表：构造一个空的线性 表L DestroyList(L): 销毁线性表：释放线性表L占 用的内存空间。 ListEmpty(L): 判线性表是否为空表: 若L为 空表,则返回真,否则返回假 ListLength(L): 求线性表的长度: 返回L中元素 个数。 DispList(L): 输出线性表: 当线性表L不为空时 ,顺序显示L中各结点的值域
2.1线性表及其逻辑结构 GetElem(L,i,e):求线性表L中指定位置的某个数据 元素:用c返回L中第i(1 <is ListLength()个元素的 值 Locateelem(L,e):定位查找:返回L由第1△值城与e 相等的位序。若这样的元素不有想一想:这些运 s ListInser.,:插入数算已经实现了吗 isListLength(个元素之前细入mm素e L的长度增1。 e ListDelete((删除数据元素:删除L中的第i (1 <i<ListLength个元素,并用e返回其值,L的 长度减1
7 2.1线性表及其逻辑结构 GetElem(L,i,e):求线性表L中指定位置的某个数据 元素:用e返回L中第 i （1≤i≤ ListLength(L))个元素的 值。 ListDelete(L,i,e) : 删除数据元素：删除L中的第i （ 1≤i≤ListLength(L))个元素，并用e返回其值，L的 长度减1。 LocateElem(L,e): 定位查找: 返回L中第1个值域与e 相等的位序。若这样的元素不存在,则返回值为0。 ListInsert(L,i,e): 插入数据元素：在L的第i( 1≤i≤ListLength(L)+1)个元素之前插入新的元素e， L的长度增1。 想一想：这些运 算已经实现了吗？
21线性表及其逻辑结构 对上述的运算的两点说明: 这些运算是在逻辑结构上定义的操作。只给 出这些运算的功能是“做什么”,至于“如 何做”等实现细节,只有待确定了存储结构 之后才考虑。 cR这些运算仅是基本运算集,基于基本运算可 进行复杂的运算,即通过基本运算可派生出 复杂的运算
8 ❖对上述的运算的两点说明： 这些运算是在逻辑结构上定义的操作。只给 出这些运算的功能是“做什么”，至于“如 何做”等实现细节，只有待确定了存储结构 之后才考虑。 这些运算仅是基本运算集，基于基本运算可 进行复杂的运算，即通过基本运算可派生出 复杂的运算。 2.1线性表及其逻辑结构
∠21线性表及其逻辑结构 例21有一个线性表L=(a’;e,"a,;d,b”),求以 下基本运算的执行结果 Listlength(L)=5 Listempty (L)=0 GetElem(L, 3, e)e=a Locateelem(L, 'a)=1 ListInsert(L,4,e”)L=(“a’;e’;a’,‘e’,d’b”) Listdelete(L,3)L=(a’,c’,e’,d”,b”)
9 例2.1 有一个线性表L=(‘a’,‘c’,‘a’,‘d’,‘b’),求以 下基本运算的执行结果 ListLength(L) ListEmpty(L) GetElem(L,3,e) LocateElem(L,‘a’) ListInsert(L,4,‘e’) ListDelete(L,3) =5 =0 e=‘a’ =1 L=(‘a’,‘c’,‘a’, ‘e’,‘d’,‘b’) L=(‘a’,‘c’, ‘e’,‘d’,‘b’) 2.1线性表及其逻辑结构
2.1线性表及其逻辑结构 例22求两个集合的并,即C=AUB 分析:设A、B分别由两个线性表LA和LB表示,要 求将LA和LB合并后的DE放入到线性表LC中。 算法思想: ①初始化LC; ②将LA中所有元素复制到LC中 ③依次从LB中取出一个DE ④判断LC中是否存在; ⑤若不存在,则插入到LC中 10
10 2.1线性表及其逻辑结构 例2.2 求两个集合的并，即C=A∪B 分析：设A、B分别由两个线性表LA和LB表示，要 求将LA和LB合并后的DE放入到线性表LC中。 算法思想： ①初始化LC； ②将LA中所有元素复制到LC中； ③依次从LB中取出一个DE； ④判断LC中是否存在； ⑤若不存在，则插入到LC中