1、第 2章 线性表 2.1 线性表的概念及运算 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 一元多项式的表示及相加 2.1 线性表的概念及运算4. 线性表的逻辑结构 1. 线性表的定义 一个线性表是具有 n个数据元素的有限序列。记为 (a1, , a i-1 , ai , ai+1 , , an)2. 线性表的长度 线性表中元素的个数 n (n=0), n=0时 ,称为空表。3. 位序 ai是第 i个元素，称 i为数据元素 ai在线性表中的位序 。例子： l英文字母表 (A, B, , Z) ；l车辆登记表 。5. 线性表的特点 l同一性：线性表由同类数据元素组成，每一个 ai必
2、须属于同一数据对象。 l有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。 l有序性：线性表中相邻数据元素之间存在着序偶关系 。 6. 线性表的基本运算l 初始化 InitList（ 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); O(ListLength(La)ListLength(Lb)练习 2：两个线性表 LA和 LB中的数据元素按值非递减有序排列，现将 LA和 LB归并为一个新
3、的线性表， LC中的数据元素仍按值非递减有序排列。LA = (3, 5, 8, 11)LB = (2, 6, 8, 9, 11, 15, 20)LC = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) void MergeList( List La, List Lb, List La_len = ListLength(La); Lb_len = ListLength(Lb);i=j=1; k=0;while( (i=La_len) GetElem(Lb, j, b);if(a=b) ListInsert(Lc, +k, a); +i; else ListInsert
4、(Lc, +k, b); +j; while(i=La_len)GetElem(La, i+, a); ListInsert(Lc, +k, a);while(j=Lb_len) GetElem(Lb, j+, b); ListInsert(Lc, +k, b); O(ListLength(La)+ListLength(Lb)例， La = ( 3, 5, 8 )Lb = ( 2, 6, 8, 9, 15 )构造 Lc = ( 2, 3, 5, 6, 8, 8, 9, 15 )358La268Lb915Lci j 2首先， La_len = 3； Lb_len = 5；3ji5i6j88i j9j15j算法结束！2.2 线性表的顺序表示和实现1. 顺序表： 按顺序存储方式构造的线性表。
