第二章线性表 线性表 顺序表 链表 顺序表与链表的比较
◼ 线性表 ◼ 顺序表 ◼ 链表 ◼ 顺序表与链表的比较
线性表( Linear list) 线性表的定义和特点 ◆定义n(≥0)个数据元素的有限 序列,记作 1929·。·9un a;是表中数据元素,n是表长度 遍历逐项访问: 从前向后从后向前
线性表 (Linear List) ◼ 线性表的定义和特点 ◆ 定义 n（ 0）个数据元素的有限 序列，记作 （a1 , a2 , …, an） ai 是表中数据元素，n 是表长度。 ◆ 遍历 逐项访问： 从前向后 从后向前
线性表的特点 除第一个元素外,其他每一个元素 有一个且仅有一个直接前驱。 除最后一个元素外,其他每一个元 素有一个且仅有一个直接后继
线性表的特点 ◼ 除第一个元素外，其他每一个元素 有一个且仅有一个直接前驱。 ◼ 除最后一个元素外，其他每一个元 素有一个且仅有一个直接后继。 a1 a2 a3 a4 a5 a6
顺序表( Sequential List 顺序表的定义和特点 ◆定义将线性表中的元素相继存放 在一个连续的存储空间中。 ◆可利用一维数组描述存储结构 ◆特点线性表的顺序存储方式 ◆遍历顺序访问,可以随机存取 012345 data253457164809
顺序表 (Sequential List) ◼ 顺序表的定义和特点 ◆ 定义 将线性表中的元素相继存放 在一个连续的存储空间中。 ◆ 可利用一维数组描述存储结构 ◆ 特点 线性表的顺序存储方式 ◆ 遍历 顺序访问, 可以随机存取 25 34 57 16 48 09 0 1 2 3 4 5 data
顺序表的连续存储方式 LOC(= LOC(i-1)+l=a+il 0123456789 a3527 49 18605477834102 a+i i=0 LOC( LOC(i-1)+=a+i*L,i>0
顺序表的连续存储方式 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9 l l l l l l l l l l LOC(i) = LOC(i-1)+l = a+i*l LOC(i) = LOC(i-1)+l = a+i*l, i > 0 a, i = 0 a+i*l a
顺序表( Seqlist)的定义 define listsize100/最大允许长度 ypedef int ListData; typedef struct i ListData data://存储数组 int length; ∥/当前元素个数 3 SeqList;
顺序表(SeqList)的定义 #define ListSize 100 //最大允许长度 typedef int ListData; typedef struct { ListData * data; //存储数组 int length; //当前元素个数 } SeqList;
顺序表基本运算的实现 构造一个空的顺序表 void InitList( SeqList &l)i L data=( ListData *)malloc Listsize* sizeof listData )); if (L data=- NULL) printf(存储分配失败!n”); exit (1); Llength=0
顺序表基本运算的实现 ◼ 构造一个空的顺序表 void InitList ( SeqList & L ) { L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0; }
求表的长度 int Length( SeqList &l)i return L length; a提取函数:在表中提取第i个元素的值 ListData GetData( Seqlist &l, int 1)( if (i>=0 &&i< L length return Ldatai; printf(“参数i不合理!n”); else ∥/在出错情况。函数返回值不能用!
◼ 求表的长度 int Length ( SeqList & L ) { return L.length; } ◼ 提取函数：在表中提取第 i 个元素的值 ListData GetData ( SeqList &L, int i ) { if ( i >= 0 && i < L.length ) return L.data[i]; else printf ( “参数 i 不合理！\n” ); } //在出错情况，函数返回值不能用！
按值查找:在顺序表中从头查找结点值 等于给定值x的结点 int Find( SeqList &L, ListDatax)i inti=0 while(i<Llength & Ldatai]=x) 1++; if(1< Llength )return i else return-l
◼ 按值查找：在顺序表中从头查找结点值 等于给定值 x 的结点 int Find ( SeqList &L, ListData x ) { int i = 0; while ( i < L.length && L.data[i] != x ) i++; if ( i < L.length ) return i; else return -1; }
顺序查找图示 012345 data253457164809 查找16i 253457164809 253457164809 it 253457164809 计查找成功
顺序查找图示 25 34 57 16 48 09 0 1 2 3 4 5 data 查找 16 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 25 34 57 16 48 09 i 查找成功