《程序编制第2章线性表》由会员分享，可在线阅读，更多相关《程序编制第2章线性表（96页珍藏版）》请在金锄头文库上搜索。
1、线性表是一种最简单的线性结构。线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构是一个数据元素的有序（次序）集,第2章 线性表,2.1 线性表的类型定义,2.3 线性表的链式表示和实现,2.4 一元多项式的表示,2.2 线性表的顺序表示和实现,2.1 线性表的类型定义,线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元
2、素；再如，某公司2000年每月产值表（400，420，500，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，下图的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项：职工号、姓名、基本工资。,矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。
3、 综上所述，一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为
4、线性表的表长; 称 n=0 时的线性表为空表。,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。,InitList( &L ),操作结果：,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList( &L ),初始条件：操作结果：,线性表 L 已存在。,销毁线性表 L。,ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ),NextElem( L, cur_e, &next_e ),GetEl
5、em( L, i, &e ),LocateElem( L, e, compare( ) ),ListTraverse(L, visit( ),引用型操作:,ListEmpty( L ),初始条件：操作结果：,线性表L已存在。,若L为空表，则返回 TRUE，否则FALSE。,（线性表判空）,ListLength( L ),初始条件：操作结果：,线性表L已存在。,返回L中元素个数。,（求线性表的长度）,PriorElem( L, cur_e, &pre_e ),初始条件：操作结果：,线性表L已存在。,若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义
6、。,（求数据元素的前驱）,NextElem( L, cur_e, &next_e ),初始条件：操作结果：,线性表L已存在。,若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。,（求数据元素的后继）,GetElem( L, i, &e ),初始条件：操作结果：,线性表L已存在， 且 1iLengthList(L)。,用 e 返回L中第 i 个元素的值。,（求线性表中某个数据元素）,LocateElem( L, e, compare( ) ),初始条件：操作结果：,线性表L已存在，e为给定值，compare( )是元素判定函数。,返回L中第1
7、个与e满足关系 compare( )的元素的位序。 若这样的元素不存在， 则返回值为0。,（定位函数）,ListTraverse(L, visit( ),初始条件：操作结果：,线性表L已存在， Visit() 为某个访问函数。,依次对L的每个元素调用 函数visit( )。一旦visit( )失败，则操作失败。,（遍历线性表）,加工型操作,ClearList( &L ),PutElem( &L, i, &e ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),ClearList( &L ),初始条件：操作结果：,线性表L已存在。,将L重置为空表。,（线
8、性表置空）,PutElem( &L, i, &e ),初始条件：操作结果：,线性表L已存在， 且 1iLengthList(L) 。,L中第i个元素赋值同e的值。,（改变数据元素的值）,ListInsert( &L, i, e ),初始条件：操作结果：,线性表L已存在，且 1iLengthList(L)+1 。,在L的第i个元素之前插入 新的元素e，L的长度增1。,（插入数据元素）,ListDelete(&L, i, &e),初始条件：操作结果：,线性表L已存在且非空，1iLengthList(L) 。,删除L的第i个元素，并用e返回其值，L的长度减1。,（删除数据元素）,假设:有两个集合 A
9、 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合AAB。,例 2-1,利用上述定义的线性表可以实现其它更复杂的操作,要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,1从线性表LB中依次察看每个数据元素;,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB, i)e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),操作步骤：,GetElem(Lb, i, e)
10、; / 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之,void union(List ,for (i = 1; i = Lb_len; i+) , / union,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,void union(List / unio
11、n,GetElem(Lb, i, e); / 取Lb中第 i 个数据元素赋给 eif (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e);/ La中不存在和 e 相同的数据元素，则插入之,for (i = 1; i = Lb_len; i+) ,InitList(La); / 构造(空的)线性表LA,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered List)。,试改变结构，以有序表表示集合。,例
12、如： 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 &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc,while (i = La_len) ,InitList(Lc); / 构造空的线性表 Lc i = j = 1; k = 0; / La 和 Lb 均非空，i = j = 1 La_len = ListLength(La); Lb_len = ListLength(Lb);,if (ai = bj) / 将 ai
13、 插入到 Lc 中ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中ListInsert(Lc, +k, bj); +j; ,while (i = La_len) / 当La不空时GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时GetElem(Lb, j+, bj);ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素 / merge_list,最简单的一种顺序映象方法是：令 y 的存储位置和 x 的
14、存储位置相邻。,顺序映象, 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。,2.2 线性表的顺序表示和实现,用一组地址连续的存储单元依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,以“存储位置相邻”表示有序对即：LOC(ai) = LOC(ai-1) + C一个数据元素所占存储量,所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai) = LOC(a1) + (i-1)C基地址,顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,#define LIST_INIT_SIZE
15、80 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),线性表的基本操作在顺序表中的实现,InitList(&L) / 结构初始化,LocateElem(L, e, compare() / 查找,ListInsert(&L, i, e) / 插入元素,ListDelete(&L, i) / 删除元素,Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq 算法2.3,算法时间复杂度：,O(1),L.elem = (ElemType*) malloc (LIST_INIT_SIZEsizeof (ElemType); if (!L.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE return OK;,线性表操作ListInsert(&L, i, e)的实现：,首先分析:,插入元素时， 线性表的逻辑结构发生什么变化？,
