第二章 线性表 线性表 顺序表 单链表 线性表的物理实现 循环链表 双向链表 单链表的变化形式 多项式 链表的应用
1 第二章 线性表 线性表 顺序表 单链表 循环链表 双向链表 多项式 线性表的物理实现 单链表的变化形式 链表的应用
第二章 线性表 §2.1线性表 定义 n（≥0)个表项的有限序列 L=（a1,42,3am） -a是表项，n是表长度。 一第一个表项是表头，最后一个是表尾 2
2 第二章 线性表 §2.1 线性表 • 定义 n（ 0）个表项的有限序列 L =（a1 , a2 , …, an） – ai是表项，n是表长度。 – 第一个表项是表头，最后一个是表尾
线性表的特点 为简单起见，假定表中元素的数据类型 相同 线性表中，结点和结点间的关系是一对 一的 有序表和无序表 6 线性表的存储方式 顺序存储方式一 顺序表 链表存储方式一链表 3
• 线性表的特点 –为简单起见，假定表中元素的数据类型 相同 – 线性表中，结点和结点间的关系是一对 一的 – 有序表和无序表 • 线性表的存储方式 –顺序存储方式 —— 顺序表 – 链表存储方式 —— 链表 a1 a2 a3 a4 a5 a6 3
§2.2顺序表 顺序表可用一维数组实现 i 时 ,i>0时 2 5 7 8 9 35 27 4918 60 54 77 83 41 02 -i*l LOC(i)=LOC(i-1)+1=a+i* 4
§2.2 顺序表 顺序表可用一维数组实现 − + = = ( ) , 0 时 α , 0 时 ( ) LOC i l i i LOC i 1 LOC ( i ) = LOC ( i -1 ) + l =α+ i*l 4
顺序表的定义 -将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 -各表项的逻辑顺序与物理顺序一致 -对各个表项可以顺序访问，也可以随机访问 5
顺序表的定义 - 将线性表中的元素相继存放在一个连续的存 储空间中 顺序表的特点 - 各表项的逻辑顺序与物理顺序一致 - 对各个表项可以顺序访问，也可以随机访问 5