西交《数据结构》faq（二）

西交《数据结构》FAQ（二）
第二章 线性表
1、线性表的定义？
n个数据元素的有限序列（a1,a2,….,an） 。
DS  = （D，R ）    LIST = （D，R），
D={ai∣ai∈数据对象集，i∈1..n ，n (0 } 元素
R={<ai-1, ai >∣ai-1, ai∈D，i∈2..n }关系
元素：是相同特性的数据对象
关系：是顺序排列的位置次序
2、线性表的特性有哪些？请举例说明。
线性关系 满足以下4点：
（1）有一个头结点， 无前驱（a1）；
（2）有一个尾结点，无后继（an）；
（3）ak（1<k<n ）在ak－1之后，即ak为ak－1的后继；
（4）ak在ak＋1之前，即ak为ak＋1的前驱。
线性、有序——具线性序
例：项链、铁锁链，排队买火车票，单线联系
3、请详细叙述线性表的ADT定义。
ADT  List {
数据对象：D＝{ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 }
数据关系：R={<ai-1, ai >∣ai-1, ai∈D，i∈2..n }
4、线性表的基本操作有哪些？
{结构初始化}
{销毁结构}
{引用型操作}
{加工型操作}
} ADT  List
{结构初始化}
InitList( &L )
操作结果：构造一个空的线性表 L 。
{销毁结构}
DestroyList( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L 。
{引用型操作}
( ListEmpty( L )
初始条件：线性表L已存在。
操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE
( ListLength( L )
初始条件：线性表 L 已存在。
操作结果：返回 L 中元素个数。
( PriorElem( L, cur_e, &pre_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义。
( NextElem( L, cur_e, &next_e )初始条件：线性表 L 已存在。操作结果：若 cur_e 是 L 中的数据元素，则用 next_e 返回它的后继，否则操作失败，next_e 无定义。
(GetElem( L, i, &e )初始条件：线性表 L 已存在，1≤i≤LengthList(L)。操作结果：用 e 返回 L 中第 i 个元素的值。
( LocateElem( L, e, compare( ) )初始条件：线性表 L 已存在，compare( ) 是元素判定函数。
操作结果：返回 L 中第1个与 e 满足关系compare( )的元素的位序。若这样的元素不存在，则返回值为0。
( ListTraverse(L, visit( ))初始条件：线性表 L 已存在，visit( ) 为元素的访问函数。操作结果：依次对 L 的每个元素调用函数visit( )。一旦 visit( ) 失败，则操作失败。
{加工型操作}
( ClearList( &L )
初始条件：线性表 L 已存在。
操作结果：将 L 重置为空表。
( ListInsert( &L, i, e )初始条件：线性表 L 已存在，1≤i≤LengthList(L)+1。操作结果：在 L 的第 i 个元素之前插入新的元素e，L的长度增1。
( ListDelete( &L, i, &e )
初始条件：线性表 L 已存在且非空，1≤i≤LengthList(L)。
操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 的长度减1。
5、关于线性表的基本操作，应注意哪些问题？
1）某数据结构上的基本操作，不是它的全部操作，而是一些常用的基本的操作运算，而每一个基本操作在实现时也可能根据不同的存储结构派生出一系列相关的运算来。
如插入运算，也可能是将新元素ｘ插入到适当位置上等等。
2）不可能也没有必要全部定义出它的运算集，读者掌握了某一数据结构上的基本运算后，其它的运算可以通过基本运算来实现，也可以直接去实现。
3）在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法，而算法的实现只有在存储结构确立之后。
6、将表中x元换成y元的操作顺序是怎样的？
操作顺序
①找到x
②记住位置
③删去x
④插入y于对应位
利用已知的ADT操作
d=LocateElem(L,x,compare( ))
ListDelete(&L,d,&e)
ListInsert(&L,d,y)
7、已知集合 A 和 B，求两个集合的并集，使 A＝A∪B。
从集合的观点看：只要对集合 B 中的所有元素一个一个地检查，看看在集合 A 中是否存在相同元素，若不存在，则将该元素插入到集合 A，否则舍弃之。
假设，以线性表 LA 和 LB 分别表示集合 A 和 B
对线性表作如下操作：扩大线性表 LA，将存在于线性表 LB 中而不存在于线性表LA 中的数据元素插入到线性表 LA 中去。
步骤：① 顺序取Lb表中元素 ② 依值在La中进行查访; ③ 若不存在，则插入之。
GetElement( Lb, i, e );LocateElem( La, e, equal ) ListInsert( La, n+1,e )
void  union (List &La, List Lb)  {
La_len=ListLength (La) ; Lb_len=ListLength (Lb);
for ( i=1; i<=Lb_len; i++ ){
GetElement (Lb, i, e) ;
if (!LocateElem(La,e,equal)) ListInsert (La,++La_len,e);
}
}//union 本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986