第3章线性表 ◆线性表及逻辑结构 ◆线性表的顺序存储 ◆线性表的链式存储 ◆链式存储结构的应用
第3章 线性表 线性表及逻辑结构 线性表的顺序存储 线性表的链式存储 链式存储结构的应用
线性表及逻辑结构 线性表:由n(n>0)个性质相同的数据元素组成的有限序列。 线性表的长度即为线性表中元素的个数n(0),当 n=0时,称该线性表为空表 线性表举例: 英文字母表就是一个线性表: (A, B, C ◎我国的省、市、自治区,可以组成一个线性表 (北京,天津,上海, ,宁夏,台湾)
线性表及逻辑结构 线性表：由n(n>0)个性质相同的数据元素组成的有限序列。 线性表的长度即为线性表中元素的个数n(0)，当 n＝0时，称该线性表为空表。 线性表举例： 英文字母表就是一个线性表： (A, B, C,······, Z) 我国的省、市、自治区，可以组成一个线性表： (北京, 天津, 上海,······, 宁夏, 台湾）
线性表的有关概念 ●位序在一个非空表 中的每个数据元素都有一个确定的位置,如a1是第 个数据元素,an是最后一个数据元素,a1是第个数据 元素,称i为数据元素a1在线性表中的位序。 前驱/后继元素:若将线性表记为:(a1,,ai-1 ai,ai+1,…,an),则表中ai-1先于ai,a先于ai+1 就称ai-1是ai的直接前驱元素,ai+1是a的直接后继 元素。 注意: 除第一个元素a1元素以外,每一个数据元素有且 仅有一个前趋元素。 o除最后一个元素以外,每个数据元素有且仅有 个后继元素
线性表的有关概念 位序:在一个非空表 (a1 ，a2 ，…，ai，…，an-1 ，an ) 中的每个数据元素都有一个确定的位置，如a1是第一 个数据元素，an是最后一个数据元素，ai是第i个数据 元素，称i为数据元素ai在线性表中的位序。 前驱/后继元素：若将线性表记为：(a1, ..., ai-1 , ai , ai+1 , ..., an )，则表中ai-1先于ai，ai先于ai+1， 就称ai-1是ai的直接前驱元素，ai+1是ai的直接后继 元素。 注意： 除第一个元素a1元素以外，每一个数据元素有且 仅有一个前趋元素。 除最后一个元素以外，每个数据元素有且仅有一 个后继元素
有头线性表的运算 ●初始化:创建一个空的线性表L ●计数:求线性表L的长度。 ●存取:存取第i个数据元素。 ●插入:在第个数据元素之前,插入一个新的数据元 素;或在第个元素后,插入一个新的数据元素
有关线性表的运算 初始化：创建一个空的线性表L。 计数：求线性表L的长度。 存取：存取第i个数据元素。 插入：在第i个数据元素之前，插入一个新的数据元 素；或在第i个元素后，插入一个新的数据元素
●删除:删去第个数据元素。 ●归并:把两个或两个以上的线性表合并在一起,形成 个新的线性表。 ●分拆:把一个线性表拆成两个或多个线性表。 ●查找:按某个特定的值查找线性表中的某个元素。 ●排序:对线性表中的某个元素按某个数据项的值递增 (或递减)的顺序进行重新排序
删除：删去第i个数据元素。 归并：把两个或两个以上的线性表合并在一起，形成 一个新的线性表。 分拆：把一个线性表拆成两个或多个线性表。 查找：按某个特定的值查找线性表中的某个元素。 排序：对线性表中的某个元素按某个数据项的值递增 （或递减）的顺序进行重新排序
根据实例给出线性表归并的算法 ●实例3-1:已知线性表LA和LB中的数据元素按值非递减有 序排列,现要求将LA和LB归并为一个新的线性表 LC← LAULE,且LC中的数据元素仍按值非递减有序排列。 设 LA=(1,5,7,15) LB=(3,6,8,913,15,17 则 LC=(1,3,5,6,7,8,9,13,15,15,17)
根据实例给出线性表归并的算法 实例3-1：已知线性表LA和LB中的数据元素按值非递减有 序排列，现要求将LA和LB归并为一个新的线性表 LC←LA∪LB，且LC中的数据元素仍按值非递减有序排列。 设 LA＝（1，5，7，15） LB＝（3，6，8，9，13，15，17） 则 LC＝（1，3，5，6，7，8，9，13，15，15，17）
●算法思想: o设LC为空表。 将LA或LB中的元素逐个插入到LC中即可 ●具体方法:为使LC中元素按值非递减有序排列,可设 两个指针和分别指向LA和LB中某个元素,若设i当前 所指的元素为a,j前所指的元素为b,则当前应插入 到LC中的元素c为 b >b C=t aa=b a ●算法的时间复杂度为 O(ListLength(La+ListLength(Lb)
设LC为空表。 将LA或LB中的元素逐个插入到LC中即可。 具体方法：为使LC中元素按值非递减有序排列，可设 两个指针i和j分别指向LA和LB中某个元素，若设i当前 所指的元素为a，j当前所指的元素为b，则当前应插入 到LC中的元素c为： 算法的时间复杂度为： O(ListLength(La)+ListLength(Lb)) 算法思想：
●归并算法 Void MergeList (List*La, List*Lb, List *LC) Initlist(Lc);/*构造一个空的线性表Lc*/ i=j=1;k=0;/*指针和初始值为1* La_len=listlength (La); Lb_len=ListLength (Lb); while ((i=La_len)&&(j<=Lb_1en) {/*La和Lb均非空*/ GetElem (La, i, ai) GetElem(Lb, j, bj); if (ai <bj) ListInsert (Lc, ++k, ai)i 十1 }/*将La中的元素插入到表Lc中*
归并算法 Void MergeList（List *La， List *Lb， List *LC） { InitList（Lc）； /*构造一个空的线性表Lc*/ i=j=1；k=0； /*指针i和j初始值为1*/ La_len=ListLength（La）； Lb_len=ListLength（Lb）； while（（i<=La_len）＆＆（j＜=Lb_1en） { /* La和Lb均非空*/ GetElem（La，i，ai）； GetElem（Lb，j，bj）； if （ai ＜bj） { Listlnsert（Lc，++k，ai）； ++i； } /*将La中的元素插入到表Lc中*/
se ifai=bj) (Listlnsert(Lc, ++k, bj)i ++i; ++j else (ListInsert (Lc, ++k, bj) ++j; l While(i<=La len) /*如果表La没有取完,则将表La中的所剩元素插入到表lc中* GetElem (La, i++,ai) ListInsert (Lc,++k, ai)i While (j<=Lb_len) GetElem (Lb, j++, bj)i istInsert (Lc, ++k, bj)i *MergeList
else if (ai = bj ) { Listlnsert（Lc，++k，bj）；++i；++j;} else { Listlnsert（Lc，++k，bj）；++j;} } While（i <＝La_len） { /*如果表La没有取完，则将表La中的所剩元素插入到表lc中*/ GetElem（La，i++,ai）； Listlnsert（Lc，++k，ai）； } While（j＜＝Lb_len） { GetElem（Lb，j++，bj）； Listlnsert（Lc，++k，bj）； } }/*MergeList*/
实例3-2:利用线性表的基本运算来实现清除线性表LA 中多余的重复结点,生成一个新的表LB。如有表 LA=(2,3,4,3,56,7,4,8,9) 存在多余的重复结点,则 LB=(2,3,425,6,7,8,9) 利用算法实现。 算法思想:从表LA的第一个结点i=1开始,逐个检查结 点以后的位置为k的任一元素,若两点相同,则从表LA 中将位置k上数据元素删除掉,当遍历了i后面的所有元 素后,i就成为表LA中无重复的结点,然后将后移动 个位置。重复上述过程,直到移到表LA的最后一个 元素为止。 算法的时间复杂度:(n-1)+(n-2)+(n-3)+…+1,即0n
实例3-2：利用线性表的基本运算来实现清除线性表LA 中多余的重复结点，生成一个新的表LB。如有表 LA=(2,3,4,3,5,6,7,4,8,9) 存在多余的重复结点，则 LB=(2,3,4,5,6,7,8,9) 利用算法实现。 算法思想：从表LA的第一个结点i=1开始，逐个检查结 点i以后的位置为k的任一元素，若两点相同，则从表LA 中将位置k上数据元素删除掉，当遍历了i后面的所有元 素后，i就成为表LA中无重复的结点，然后将i向后移动 一个位置。重复上述过程，直到i移到表LA的最后一个 元素为止。 算法的时间复杂度：(n-1)+(n-2)+(n-3)+…..+1,即