1、线性表的两个应用
1.1 线性表的合并
将两个无序的线性表La和Lb合并成一个新的线性表，要求新的线性表中不能出现重复的元素。
La = {7,5,3,11}; Lb = {2,6,3};
算法步骤和伪代码如下所示：
依次取出Lb中的每个元素，执行下述操作： 1、在La中查找该元素 2、若元素在La中找不到，则将其插入到La的最后
void union(List &La, List &Lb) { LaLen = GetLength(La); //获取链表La的长度 LbLen = GetLength(Lb); //获取链表Lb的长度 for(int i = 0; i < LbLen; ++i) { Elem tVal = GetElem(Lb, i); //获取Lb索引为i的元素Elem if(!LocateElem(La, tVal)) //检查tVal是否已经存在于La中 ListInsert(La, tVal); //若不重复，则插入到La的尾部 } }
算法的时间复杂度为： O(LaLen∗LbLen)
1.2 有序表的合并
将两个数据元素已经排好序的非递减有序线性表La和Lb合并为一个新的线性表，新的线性表中的元素不能有重复且数据元素仍按照非递减的顺序排列。
La = {1,7,8}; Lb = {2,4,6,8,10,11};
算法步骤和伪代码如下所示：
1、首先创建一个空表Lc 2、依次从La或者Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变成空表为 止。 3、将La和Lb中的非空表剩余结点插入到Lc表的最后。
1.2.1 用顺序表实现有序表合并
void MergeList(List &La, List &Lb, list &Lc) {//双指针法合并有序顺序链表，同时去重 int pa = 0, pb = 0; //指向La和Lb表的第一个元素的两个指针 int pc = 0; //指向新表Lc的第一个元素的指针 Lc.length = La.length + Lb.length; //获得新表的最大长度 Lc.elem = new ElemType[Lc.length]; //为新表分配新的数组空间 while(pa < La.length && pb < Lb.length) { if(La[pa] < Lb[pb]) //当前La表中的元素更小 Lc[pc++] = La[pa++]; else if(La[pa] == Lb[pb]) //当前La表中的元素和Lb表中的元素同样大小 { Lc[pc++] = La[pa++]; ++pb; } else //当前Lb表中的元素更小 Lc[pc++] = Lb[pb++]; } while(pa < La.length) Lc[pc++] = La[pa++];//插入La表剩余的元素 while(pb < Lb.length) Lc[pc++] = Lb[pb++];//插入Lb表剩余的元素 }
算法的时间复杂度为：O(La.length+Lb.length)
算法的空间复杂度为：O(La.length+Lb.length)
1.2.2 用链表实现有序表的合并
void MergeList(List &La, List &Lb, List &Lc) {//双指针法合并两个有序链表，添加去重，默认原链表中没有重复元素 list *pa = La->next, *pb = Lb->next; //记录链表La和Lb的首元结点的位置 pc = Lc = La; //将La的头结点作为Lc的头结点 while(pa && pb) { if(pa->data < pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else if(pa->date==pb->data) { pc->next = pa; pc = pa; pa = pa->next; list *t = pb; pb= pb->next; delete t; } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa?pa:pb; delete Lb; }
算法的时间复杂度为：O(La.length+Lb.length)
算法的空间复杂度为： O(1)
2、案例分析与实现
2.1 图书管理系统
线性表中每一个数据元素都是一个复杂的结构类型，可以用类或者结构体来定义，类中的成员项包括图书编号，书名，价格，存档日期，是否可以借阅等等。
图书管理系统的实现可以用顺序表来实现，
也可以用链表来实现：
当系统中的图书的数量变化不大，同时不需要频繁对图书进行插入或者删除操作，但需要快速查找某个或者某些图书的信息，则使用线性表实现更好；若需要进行频繁的插入和删除操作，则使用链式存储结构更加合理。
系统的结构类型和和表的类型定义示例如下所示：
struct Book { char id[20]; //ISBN char name[50]; //name int price; //定价 }; /*顺序表定义*/ class SqList { Book *elem; int length; }; /*链表定义*/ class LNode { Book data; LNode *next; };
