天津大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第二章 线性表

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

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

线性表 定义: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; //当前元素个数 }

顺序表基本运算 n初始化 void Initlist( Seqlist &l)i L data=( ListData *)malloc ListSize x sizeof( ListData )) if (L data== NULL)( printf(“存储分配失败!m”); exit( 1); Length= 0

顺序表基本运算 ◼ 初始化 void InitList ( SeqList & L ) { L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0; }

按值查找:找x在表中的位置,若查找成功 返回表项的位置,否则返回1 int Find( seqlist &l, listData x) inti=0 while (i< llength & ldatail=X) i++; if(i< Llength )return i else return -1

▪ 按值查找：找x在表中的位置，若查找成功， 返回表项的位置，否则返回-1 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; }

按值查找:判断x是否在表中 int IsIn( seqlist &l, listDatax) i inti=0, found=0; while(i< llength &&! found if(L data!=x)i++; else found=l return found

按值查找：判断x是否在表中 int IsIn ( SeqList &L, ListData x ) { int i = 0, found=0; while ( i < L.length &&!found ) if(L.data[i] != x ) i++; else found=1; return found; }

n求表的长度 int Length( seq list &l)& return Llength 提取函数:在表中提取第i个元素的值 ListData GetData( seqlist &l, int i if(i>=0 &&i< Llength return Ldatai print(“参数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 Next Seqlist &l, listData x)i int i=Find(x) if (i>0&& i0&& i< Llength )return i-1 else return -1

▪ 按值查找：寻找x的后继 int Next ( SeqList &L, ListData x ) { int i = Find(x); if ( i >0 && i 0 && i < L.length ) return i-1; else return -1; }