第二章线性表 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