清华大学：《数据结构》课程教材PPT教学课件（C语言版）第二章 线性表

第二章线性表 21线性表的类型定义 ·22线性表的顺序表示和实现 23线性表的链式表示和实现 2.3.1线性链表 232循环链表 233双向链表 24一元多项式的表示及相加

第二章 线性表 • 2.1 线性表的类型定义 • 2.2 线性表的顺序表示和实现 • 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加

2.1线性表的逻辑结构 线性表( Linear List):由n(n三0)个数据元素(结点)a1, a2,∴an组成的有限序列。其中数据元素的个数n定 义为表的长度。当n=0时称为空表,常常将非空的线 性表(n>0记作: 2 数据元素之间的关系是: ai-1领先于a,a领先于ai+1 称a;-1是a的直接前驱元素;ai1是a的直接后继元素 除a1外,每个元素有且仅有一个直接前驱元素, 除an外,每个元素有且仅有一个直接后继元素。 线性表中数据元素的个数n(n>=0)称为线性表的长度, 当n=0时,称为空表

• 2.1 线性表的逻辑结构 • 线性表(Linear List) ：由n(n≧0)个数据元素(结点)a1， a2， …an组成的有限序列。其中数据元素的个数n定 义为表的长度。当n=0时称为空表，常常将非空的线 性表(n>0)记作： (a1，a2，…an ) 数据元素之间的关系是： ai-1领先于ai，ai领先于ai+1。 称ai-1是ai的直接前驱 元素；ai+1是ai的直接后继 元素。 除a1外，每个元素有且仅有一个直接前驱元素， 除an外，每个元素有且仅有一个直接后继元素。 线性表中数据元素的个数n(n>=0)称为线性表的长度， 当n=0时，称为空表

这里的数据元素a(1至in)只是一个抽象的 符号,其具体含义在不同的情况下可以不同 例1、26个英文字母组成的字母表 (A, B, C Z) 例2、某校从1978年到1983年各种型号的计 算机拥有量的变化情况。 (6,17,28,50,92,188) 例3、一副扑克的点数 (2,3,4,…,J,Q,K,A)

这里的数据元素ai (1≦i≦n)只是一个抽象的 符号，其具体含义在不同的情况下可以不同。 •例1、26个英文字母组成的字母表 （A，B，C、…、Z） •例2、某校从1978年到1983年各种型号的计 算机拥有量的变化情况。 （6，17，28，50，92，188） •例3、一副扑克的点数 • （2，3，4，…，J，Q，K，A）

例、学生健康情况登记表如下 姓名学 性别年龄健康情况 王小林790631男18健康 陈红790632女20一般 刘建平790633男 21 健康 张立立790634男 神经衰弱

例4、学生健康情况登记表如下： 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……

从以上例子可看出线性表的逻辑特征是: 在非空的线性表,有且仅有一个开始结点a1 它没有直接前趋,而仅有一个直接后继a2; >有且仅有一个终端结点an,它没有直接后继, 而仅有一个直接前趋an1i; >其余的内部结点a(2至in-1)都有且仅有一个直 接前趋a和一个直接后继a计1 线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的,而运算的 具体实现则是在存储结构上进行的 抽象数据类型的定义为:P19

从以上例子可看出线性表的逻辑特征是： ➢ 在非空的线性表，有且仅有一个开始结点a1， 它没有直接前趋，而仅有一个直接后继a2； ➢ 有且仅有一个终端结点an，它没有直接后继， 而仅有一个直接前趋a n-1； ➢ 其余的内部结点ai (2≦i≦n-1)都有且仅有一个直 接前趋a i-1和一个直接后继a i+1。 线性表是一种典型的线性结构。 • 数据的运算是定义在逻辑结构上的，而运算的 具体实现则是在存储结构上进行的。 • 抽象数据类型的定义为：P19

算法2.1 例2-1利用两个线性表LA和LB分别表示两个集合A和B 现要求一个新的集合A=A∪B。 void union list &La, List Lb)i La len=listlength (La) Lb len=listlength(Lb) for(F=1; K =lb len; I++) getelem(b, I, e) if (!locateelem(la, e, equal) listinsert(la, ++la en, e)

算法2.1 • 例2-1 利用两个线性表LA和LB分别表示两个集合A和B， 现要求一个新的集合A=A∪B。 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); if (!locateelem(la,e,equal)) listinsert(la,++la_en,e) } }

算法2.2 例2-2已知线性表LA和线性表LB中的数 据元素按值非递减有序排列,现要求 LA和LB归并为一个新的线性表LC,且LC 中的元素仍按值非递减有序排列 此问题的算法如下 void mergelist(list la, list Ib, list &lc) initlist(lc) I==1;k=0; la len=listlength (la) Ib len=listlength(b)

• 算法2.2 • 例2-2 巳知线性表LA和线性表LB中的数 据元素按值非递减有序排列，现要求将 LA和LB归并为一个新的线性表LC，且LC 中的元素仍按值非递减有序排列。 • 此问题的算法如下： void mergelist(list la，list lb，list &lc) { initlist(lc); I=j=1;k=0; la_len=listlength(la); lb_len=listlength(lb);

while((=la len)&&g<=lb len)) i getelem(la, I, ai) getelem(lb,j, bj) ifai<=bi) flistinsert(Ic, ++k, ai); ++I; else flistinsert(Ic,++k, bj: ++; 3 while(=la len) i getelem((la, I++, ai) listinsert(Ic, ++k, ai)

while((I<=la_len)&&(j<=lb_len)) { getelem(la，I，ai); getelem(lb，j，bj); if(ai<=bj) {listinsert(lc，++k，ai);++I;} else {listinsert(lc，++k，bj);++j;} } while(I<=la_len) { getelem((la，I++，ai); listinsert(lc，++k，ai); }

while(<=lb len) getelem((b,j++, bj) listinsert(lc, ++k, bi)

while(j<=lb_len) { getelem((lb，j++，bj); listinsert(lc，++k，bi); } }

22线性表的顺序存储结构 221线性表 把线性表的结点按逻辑顺序依次存放在一组 地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。 假设线性表的每个元素需占用1个存储单元, 并以所占的第一个单元的存储地址作为数据元素 的存储位置。则线性表中第i+1个数据元素的存 储位置LOC(a)和第讠个数据元素的存储位置 LOCa;)之间满足下列关系: LOC(a i +1=LOC(a+ 线性表的第个数据元素a1的存储位置为 LOC(a=LOC(a1)+(-1)*1

• 2.2 线性表的顺序存储结构 • 2.2.1 线性表 把线性表的结点按逻辑顺序依次存放在一组 地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。 假设线性表的每个元素需占用l个存储单元， 并以所占的第一个单元的存储地址作为数据元素 的存储位置。则线性表中第i+1个数据元素的存 储位置LOC( a i+1)和第i个数据元素的存储位置 LOC(a i )之间满足下列关系： LOC(a i+1)=LOC(a i )+l 线性表的第i个数据元素ai的存储位置为： LOC(ai )=LOC(a1 )+(i-1)*l