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