线性表 解析ppt课件.ppt

《线性表 解析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构深圳大学计算机与软件学院白鉴聪1第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示和实现2上节复习数据、数据元素、数据对象、数据结构的概念，P4四种数据结构：集合、线性、树形、图状数据的物理结构和逻辑结构，P6抽象数据类型用（D，S，P）三元组表示数据对象、数据关系、基本操作算法是对特定问题求解步骤的一种描述，是一有限长的操作序列算法特性：有穷性、确定性、可行性、输入和输出算法评价因素：正确性、可读性、健壮性、时空性时间复杂度和空间复杂度3写出以下代码的时间复杂度for(i=1;i

2、,y)函数表示x的y次幂a=a+100;b.for(i=1;i<=n;i++)for(j=1;j<=i;j++)a=a+1;c.i=s=k=1;while(k<=s){if(i<=n){i++;s*=i;}k++;}练习42.1线性表的类型定义线性表概念线性表是n个数据元素的有限序列线性数据结构的特点数据同一性，同一个线性表的数据属同一类数据对象顺序性，数据之间存在序偶关系(a1,a2,…ai-1,ai,ai+1,…an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的长度52.2线性表的类型定义线性表概念数据同一性线性表中的元素具有相同的特性，属于同一数据对象，如：26个字母

3、的字母表:(A,B,C,D,…,Z)近期每天的平均温度:(30℃,28℃,29℃,…)62.1线性表的类型定义线性表概念数据的顺序性存在惟一的一个被称作“第一个”的数据元素(如“１”)存在惟一的一个被称作“最后一个”的数据元素(如“６”)除第一个元素外，每个数据元素均只有一个前驱除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”,“2”的next是“3”)12345672.1线性表的类型定义线性表的ADT定义ADTList{数据对象：数据元素同属一个集合数据关系：序偶关系基本操作：Init创建、Destroy销毁、Clear清空、Empty是否为空、Leng

4、th取表长度、Get取表元素、Locate查找元素Prior取元素前驱、Next取元素后继Insert插入元素、Delete删除元素Traverse遍历表}82.2顺序表顺序表概念顺序表是线性表的顺序表示，用一组地址连续的存储单元依次存储线性表的数据元素ABCDE…YZbb+1b+2b+3b+4…b+24b+2592.2顺序表顺序表的数据位置顺序表数据元素的位置：LOC(ai)=LOC(ai-1)+lLOC(ai)=LOC(a1)+(i-1)*ll表示元素占用的内存单元数a1a2…ai………an12…i………nbb+l…b+(i-1)*l………b+(n-1)*lidle102.2顺序表顺序表

5、的定义采用C语言中动态分配的一维数组表示顺序表#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量Typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(元素数)}Sqlist;112.2顺序表顺序表的创建StatusInitList_Sq(Sqlist&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)ex

6、it(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;};//InitList_Sq122.2顺序表顺序表的插入给出插入的队列对象、位置、数据在顺序表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素操作包括后移、插入、长度+1例如在第3个元素与第4个元素之间插入新元素e，需要将最后元素n至第4元素(共7-4+1)都向后移一位置，长度加1253457164809630123456725345750164809635050插入ei=401234567132.2顺序表

7、顺序表的插入StatusListInsert_Sq(Sqlist&L,inti,ElemType&e){if(i<1

8、

9、i>L.length+1)returnERROR;if(L.length>=L.listsize){newbase=realloc(L,L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=n