第二章线性表 令线性表 令顺序表 令链表 令顺序表与链表的比较
第二章 线性表 ❖ 线性表 ❖ 顺序表 ❖ 链表 ❖ 顺序表与链表的比较
线性表 定义:n(≥0)个数据元素的有限序列,记作 19 ●●● 19iui+19。9un 其中,;是表中数据元素,n是表长度。 特点 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外,其他每一个元素有一个且仅 有一个直接前驱。 除最后一个元素外,其他每一个元素有 个且仅有一个直接后继
线性表 定义： n（0）个数据元素的有限序列，记作 （a1 , …ai-1 , ai , ai+1 ,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: ◼ 同一线性表中元素具有相同特性。 ◼ 相邻数据元素之间存在序偶关系。 ◼ 除第一个元素外，其他每一个元素有一个且仅 有一个直接前驱。 ◼ 除最后一个元素外，其他每一个元素有 一个且仅有一个直接后继
顶序表 定义:将线性表中的元素相继存放在一 个连续的存储空间中 存储结构:数组。 特点:线性表的顺序存储方式。 存取方式:顺序存取 顺序存储结构示意图 012345 458990674078
顺序表 定义：将线性表中的元素相继存放在一 个连续的存储空间中。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取 顺序存储结构示意图 45 89 90 67 40 78 0 1 2 3 4 5
顺序表的存储方式 LOC(a+d=loc(ai)+(i-1)L LOC(a =Loc(a)+(i-1)Z ●●●●●● ●●● aa+ a+(i-17 a+(m-D)“ile
顺序表的存储方式： LOC(a i+1) = LOC( a i )+(i-1)*l LOC(a i ) = LOC(a1 )+(i-1)*l a1 a2 … a i … … … an 1 2 … i … … … n a a+l … a+(i-1)*l … … … a+(n-1)*l idle
顺序表( Seqlist)的类型定义 define listsize00/最大允许长度 typedef int ListData typedef struct t ListData*data;/存储空间基址 int length;当前元素个数
顺序表（SeqList）的类型定义 #define ListSize 100 //最大允许长度 typedef int ListData; typedef struct { ListData * data; //存储空间基址 int length; //当前元素个数 }