北京师范大学《数据结构——C语言描述》教学课件：第二章 线性表

第二章线性表 线性表 顺序表 链表 顺序表与链表的比较

◼ 线性表 ◼ 顺序表 ◼ 链表 ◼ 顺序表与链表的比较

线性表( 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)+=a+il 0123456789 a35274918605477834102 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 s 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 Llength a提取函数:在表中提取第i个元素的值 ListData GetData( Seqlist &l, int 1)( if (i>=0 &&i<Llength return Ldatai; else printf(参数i不合理!Ⅶn”); ∥/在出错情况。函数返回值不能用!

◼ 求表的长度 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(1< Llength & L data1=x) 1++; if (i<Llength )return i; else return -1

◼ 按值查找：在顺序表中从头查找结点值 等于给定值 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 查找成功