数据结构考研线性表

1.1   线性表的逻辑结构：

例一：有两个集合A和B分别用两个线性表La和Lb表示，即：线性表中的数据元素即为集合中的成员；
分析：上述问题演绎为：要求对线性表作如下操作：
扩大线性表La,将存于线性表Lb中而不存与线性表La中的数据元素插入到La中去。

线性集合A和B的合并：

A：把B中的元素加入A中

首先： Len_Lb = ListbLength(Lb);(Len_La = ListLength(La))取得线性表Lb的长度，为下面跳出循环设置条件

循环遍历Lb中的元素，利用getElem(Lb,i,e){返回第i个元素的值e} , 将e和La中的元素比较：

若La中的元素无与之相同的，if(!LocateElem(La, e, equal()));则：InsertElem(&La,Len_La++,e);把元素插入La表的集合

循环执行Len_Lb次;for（int i = 1; i <= Len_Lb; i++）

void union(List &La, List Lb){
La_len = ListLength(La); //求线性表长度
Lb_len = ListLength(Lb);

for(int i = 1; i <= Lb_len; i++){
GetElem(Lb, i, e); //取Lb第i个数据元素
if(!LocateElem(La, e, equal())) //La中不存在和e相同的数据元素，则插入
ListInsert(&La, ++La_len, e);
}
}

例二：归并两个“其数据元素按值非递减有序排列”的有序表La和Lb，

求得有序表Lc也具有同样特性
分析：两个非递减有序排列表La和Lb，即为：
La: 1, 2, 3, 5, 6
Lb: 2, 3, 4
Lc: 1, 2, 2, 3, 3, 4, 5, 6

基本操作：初始化Lc为空表，分别从La和Lb取得当前元素ai和bj,
若ai<bj,则插入Lc。重复上述操作，直至La或Lb取完；
再将La或Lb中剩余的元素复制到Lc中

void MergeList(&Lc, La, Lb){
InitList(Lc);//构造空的线性表Lc
La_len = ListLength(La);
Lb_len = ListLength(Lb);
int i = j = 1, k = 0;
while((i <= La_en)&&(j <= Lb_len)){ //La和Lb均不为空
GetElem(La, i, ai);
GetElem(Lb, j, bj);
if(ai < bj)
ListInsert(Lc, ++k, ai);
++i;
else{
ListInsert(Lc, ++K, bj);
++j;
}
}
while(i <= La_len){
GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai);
}