北京邮电大学自动化学院：《数据结构》第二章 线性表

第二章线性表 线性结构的特点:在数据元素中的非空有限集中 ●(1)存在唯一的一个被称作“第一”的数据元素; (2)存在唯一的一个被称作“最后一个”的数据元 素 (3)除第一个外,集合中的每一个数据元素均只有 一个前驱; (4)除最后一个外,集合中的每一个数据元素均只 有一个后继。 北京邮电大学自动化学院

北京邮电大学自动化学院 1 ⚫ 线性结构的特点：在数据元素中的非空有限集中 ⚫ （1）存在唯一的一个被称作“第一”的数据元素； ⚫ （2）存在唯一的一个被称作“最后一个”的数据元 素； ⚫ （3）除第一个外，集合中的每一个数据元素均只有 一个前驱； ⚫ （4）除最后一个外，集合中的每一个数据元素均只 有一个后继。 第二章 线性表

21线性表的类型定义 1、线性表 ●线性表 Linear list):一个线性表是n个数据元素的 有限序列。例如: 例1、26个英文字母组成的字母表 (A,B,C、∴、Z) 例2、某校从1999年到2003年各种型号的计算机拥 有量的变化情况。 ●(6,17,28,50,92,188) 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 1、线性表 ⚫ 线性表(Linear List) ：一个线性表是n个数据元素的 有限序列。例如： ⚫ 例1、26个英文字母组成的字母表 ⚫（A，B，C、…、Z） ⚫ 例2、某校从1999年到2003年各种型号的计算机拥 有量的变化情况。 ⚫（6，17，28，50，92，188） 2.1 线性表的类型定义

1、线性表 ●在稍复杂的线性表中,一个数据元素可以由若干个数据项组 成。在这种情况下,常把数据元素称为记录,含有大量记录的 线性表又称为文件。 ●例3、学生健康情况登记表如下: 姓名 学号 性别 年龄 健康情况 王小林 790631 18 健康 陈红 790632 20 一般 刘建平 790633 男女男男 21 健康 张立立 790634 神经衰弱 北京邮电大学自动化学院

北京邮电大学自动化学院 3 ⚫ 在稍复杂的线性表中，一个数据元素可以由若干个数据项组 成。在这种情况下，常把数据元素称为记录，含有大量记录的 线性表又称为文件。 ⚫ 例3、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……. 1、线性表

1、线性表 综合上述三个例子可见,线性表中的数据元素可以是各种各样 的,但同一线性表中的元素必定具有相同特征,即属同一数据 对象,相邻数据元素之间存在着序偶关系。若将线性表记为: i+myan ·则表中a领先于a,a领先于a H19 称a1是a的直接前驱元 素,a1是a1的直接后继元素 当i=1,2,,n-时,a有且仅有一个直接后继,当i2,3,…,n 时,a有且仅有一个直接前驱。 线性表中的元素的个数n(n≥0)定义为线性表的长度,n=0时 称为空表。 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 ⚫ 综合上述三个例子可见，线性表中的数据元素可以是各种各样 的，但同一线性表中的元素必定具有相同特征，即属同一数据 对象，相邻数据元素之间存在着序偶关系。若将线性表记为： ⚫ (a1，…,a i-1，ai，a i+1…,an ) ⚫ 则表中ai-1领先于ai，ai领先于ai+1 ，称ai-1是ai的直接前驱元 素，ai+1是ai的直接后继元素。 ⚫ 当i=1,2,…,n-1时，ai有且仅有一个直接后继，当i=2,3,…,n 时， ai有且仅有一个直接前驱。 ⚫ 线性表中的元素的个数n(n  0)定义为线性表的长度，n=0时 称为空表。 1、线性表

2、抽象数据类型线性表 ADT Listi 数据对象:={a|an∈ Elem Set,i=1,2,,n,n0} 数据关系:R1={a11a|a1ap∈D,i=2,,n ●基本操作: ● netList(&L) ●操作结果:构造一个空的线性表L。 Destroy List(&L) 初始条件:线性表L已经存在。 ●操作结果:销毁线性表L。 北京邮电大学自动化学院

北京邮电大学自动化学院 5 ⚫ ADT List{ ⚫ 数据对象：={ai |aiElemSet，i=1,2,…,n,n0} ⚫ 数据关系：R1={| ai-1 ,ai ,  D,i=2,…,n} ⚫ 基本操作： ⚫ InitList(&L) ⚫ 操作结果：构造一个空的线性表L。 2、抽象数据类型线性表 ⚫ DestroyList(&L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：销毁线性表L

2、抽象数据类型线性表 ●c| earlist(&"L 初始条件:线性表L已经存在。 操作结果:将L置为空表。 ● ListEmpty(L ●初始条件:线性表L已经存在。 操作结果:若L为空表,则返回TRUE,否则返回 FALSE。 北京邮电大学自动化学院

北京邮电大学自动化学院 6 ⚫ ClearList(&L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：将L置为空表。 2、抽象数据类型线性表 ⚫ ListEmpty(L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：若L为空表，则返回TRUE，否则返回 FALSE

抽象数据类型线性表 ListLength(l) 初始条件:线性表L已经存在。 操作结果:返回L中数据元素个数。 GetElem(L, i, &e) 初始条件:线性表L已经存在, <isListlength(L)。 操作结果:用e返回L中第i个数据元素的值。 o LocateElem (L, e, compare) 初始条件:线性表L已经存在, compare是数据元素判定函数。 操作结果:返回L中第一个与e满足关系 compare的数据元素的 位序。若这样的元素不存在,则返回值为零为 北京邮电大学自动化学院

北京邮电大学自动化学院 7 ⚫ ListLength(L) ⚫ 初始条件：线性表L已经存在。 ⚫ 操作结果：返回L中数据元素个数。 2、抽象数据类型线性表 ⚫ GetElem(L, i, &e) ⚫ 初始条件：线性表L已经存在，iListlength(L)。 ⚫ 操作结果：用e返回L中第i个数据元素的值。 ⚫ LocateElem(L, e, compare()) ⚫ 初始条件:线性表L已经存在,compare是数据元素判定函数。 ⚫ 操作结果：返回L中第一个与e满足关系compare()的数据元素的 位序。若这样的元素不存在，则返回值为零为

2、抽象数据类型线性表 ListInsert(&L, i, e) 初始条件:线性表L已经存在,且1i≤ Listlength(L+1。 操作结果:在L中第个位置之前插入新的数据元素e,L的长度加1 o Listdelte(&L,i, &e) ●初始条件:线性表L已经存在且非空,且1≤i≤ Listlength(L)。 ●操作结果:删除L中的第i个数据元素,并用e返回其值,L的长度 减1。 3 ADT List 北京邮电大学自动化学院

北京邮电大学自动化学院 8 2、抽象数据类型线性表 ⚫ ListInsert(&L ,i ,e) ⚫ 初始条件：线性表L已经存在，且1 i  Listlength(L)＋1。 ⚫ 操作结果:在L中第i个位置之前插入新的数据元素e，L的长度加1 ⚫ Listdelte(&L ,i ,&e) ⚫ 初始条件：线性表L已经存在且非空，且1 i  Listlength(L)。 ⚫ 操作结果:删除L中的第i个数据元素，并用e返回其值，L的长度 减1。 ⚫ … … ⚫ } ADT List

3、例题 例21利用两个线性表LA和LB分别表示两个集合A和B,现要 求一个新的集合A=AUB。只要从线性表LB中依次取得每个数 据元素,并依值在线性表LA中进行査访,若不存在,则插入。 o void union (List &La, List Lb)i La-en= Listlength(La); Lb-en= Listlength(Lb);线性表长 for(i=1; i<=Lb-len; i++)i Getelem(Lb,i,e);/取Lb中的第个i元素赋给e if(! Locate Elem(La, e, equal))Listinsert(La, ++La-en, e) La中不存在和e相同的数据元素,则插入 1 3/union 北京邮电大学自动化学院

北京邮电大学自动化学院 9 ⚫ 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要 求一个新的集合A=A∪B。只要从线性表LB中依次取得每个数 据元素，并依值在线性表LA中进行查访，若不存在，则插入。 ⚫ void union(List &La，List Lb) { ⚫ La-len=Listlength(La); Lb-len=Listlength(Lb);//线性表长 ⚫ for (i=1; i<=Lb-len; i++) { ⚫ GetElem(Lb，i，e);//取Lb 中的第个i元素赋给e ⚫ if(!LocateElem(La, e, equal)) Listinsert(La, ++La-en, e); ⚫ //La中不存在和e相同的数据元素，则插入 ⚫ } }//union 3、例题

3、例题 例2-2已知线性表LA和线性表LB中的数据元素按值非递减有序 排列,现要求将LA和LB归并为一个新的线性表LC,且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) ●从上面的问题要求可知,Lc中的数据元素或是LA中的数据元 素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或 LB中的元素逐个插入到Lc中即可。设两个指针j分别指向LA 和LB中某个元素,设当前所指的元素为a,j当前所指的元素为 b,则当前应插入到Lc中的元素c为 1,当axb时 北京邮电大学自动化学院 10

北京邮电大学自动化学院 10 ⚫ 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序 排列，现要求将LA和LB归并为一个新的线性表LC，且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）      = ，当 时 当 时 b a b a a b c , 3、例题 ⚫ 从上面的问题要求可知，LC中的数据元素或是LA中的数据元 素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或 LB中的元素逐个插入到LC中即可。设两个指针i和 j分别指向LA 和LB中某个元素，设i当前所指的元素为a，j当前所指的元素为 b，则当前应插入到LC中的元素c为