数据结构 线性表的逻辑特征是: 在非空的线性表中,有且仅有一个开始结点a1, 它没有直接前趋,而仅有一个直接后继a2;有 且仅有一个终端结点an,它没有直接后继,而 仅有一个直接前趋an-1;其余的内部结点 a(2≤i≤n-1)都有且仅有一个直接前趋a; 和一个直接后继a+1 结论:线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的,而运算的具 体实现则是在存储结构上进行的。 线性表的抽象数据类型的定义:P19
数据结构 tjm
数据结构 例2-1利用两个线性表LA和LB分别表示两个集合A 和B(即线性表中的数据元素即为集合中的成员), 现要求一个新的集合A=AUB void union (List &La, List Lb) La_len=ListLength (Lai Lb_len=ListLength ( Lb) for(i=1;i<=Lb len;i++) GetElem (Lb,i, e); if(! LocateElem (La,e, equal) ListInsert(la,++La len,e)
数据结构 tjm
数据结构 打展1:利用两个线性表LA和LB分别表示两个集合 A和B,现要求一个新的集合A=A∩B。 void JiHeJiao(list &La, List Lb) La len=ListLength La) Lb_len=ListLength (Lb) for (i=1;i<=La len;i++) GetElem (La,i, e); if(! Locate Elem(Lb, e, equaD)) i ListDelete(la,i, e)i ii--La len; r t r
数据结构 tjm
数据结构 例2-2已知线性表LA和线性表LB中的数据元素按 值非递减有序排列,现要求将LA和LB归并为 个新的线性表LC,且LC中的元素仍按值非递减 有序排列。此问题的算法如下: void Mergelist(List La, List Lb, List &lc) InitList(Lc); i=j=1:k=0 La_ len=ListLength (La) Lb_len=ListLength (Lb)i while((i<=La_len) &&<=Lb_len))
数据结构 tjm
数据结构 GetElem(La, i, aD);getElem (Lb, j, bji if(ai<=b]) RListInsert(Lc,++k, ai;++i;y else i ListInsert(LC,++k, b]i++jry while (i<=La len) GetElem ((La, i++, ai; ListInsert(Lc, ++k, ai;y while<=Lb len) GetElem((Lb,j++, b]) ListInsert(Lc,++k, b]i3 }
数据结构 tjm