第二章线性表 令线性表 冷顺序表 令链表 冷顺序表与链表的比较
第二章 线性表 ❖ 线性表 ❖ 顺序表 ❖ 链表 ❖ 顺序表与链表的比较
线性表 定义:n(≥0)个数据元素的有限序列,记作 ●●● ai-1, ais ai+1g..,an 其中;是表中数据元素,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计1)=LOC(a;)+(i-1)“ LOC(a)=LOC(a1)+(1-1) 2 ●●● ●。● ●●● ●。●● a, a aa+ a+(i-1) a+(m-1)“ille
顺序表的存储方式： 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 listsize100/最大允许长度 typedef int ListData typedef struct ListData x data;/存储空间基址 int length /当前元素个数
顺序表（SeqList）的类型定义 #define ListSize 100 //最大允许长度 typedef int ListData; typedef struct { ListData * data; //存储空间基址 int length; //当前元素个数 }
顺序表基本运算 ■初始化 void InitList( Seqlist &l)i L data=( ListData *)malloc Listsize sizeof ListData)) if(L data== NULL)( printf(“存储分配失败!n”); exit (1); Llengt th=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( seq list &l, listData x)t inti=0 while(i< length & ldata!=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, listData x) int i=0 9 found=0 while(i< L length &&e 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; }
求表的长度 int Length( Seqlist &l) return Llength 提取函数:在表中提取第个元素的值 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)& int i= Find(x); if (i>0 && i< Llength )return i+1 else return -1 寻找x的前驱 int Next( Seq list &l, listData xt int i= Find (x); if(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; }
