资源描述：
《数据结构 第2章 线性表 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法第二讲：线性表（一）内容提要线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构（单链表）04/10/20212什么叫线性表？04/10/20213线性表的定义和基本操作线性表的定义线性表是由n(n≥0)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称
2、为空线性表。04/10/20214线性表的结构分析（a1,a2,…ai-1，ai,ai＋1，…,an）n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点04/10/20215线性表特性线性表中元素之间的关系是线性关系：存在唯一的第一个元素；存在唯一的最后一个元素；除第一个元素之外，每个元素均只有一个直接前驱；除最后一个元素之外，每个元素均只有一个直接后继。04/10/20216现实生活中的线性表【思考】下列哪些关系属于线
3、性关系呢？家族的亲戚关系？同学之间的友谊？恋人之间的爱情？班级同学的名册？食堂窗口前排队？自习教室里占座？04/10/20217线性表中的元素类型（１）原子类型：如整数、字符等。（２）结构类型：如表示一个学生信息的数据元素，包含学号、姓名、性别等数据项。04/10/20218线性表举例La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welcome)数据元素类型为string。Lb=(book1,book2,...
4、,book100)数据元素类型为下列所示的结构类型：structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}04/10/20219抽象数据类型线性表定义ADTList{数据对象：D={ai
5、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R={
6、ai,ai+1∈D,i=1,2,...,n,n≥0}}基本操作：InitList(&L)//初始化操作，建立一个空的线性表LDestroyList(
7、&L)//销毁已存在的线性表LClearList(&L)//将线性表清空ListInsert(&L,i,e)//在线性表L中第i个位置插入新元素eListDelete(&L,i,&e)//删除线性表L中第i个位置元素，并用e返回其值IsEmpty(L)//若线性表为空，返回true，否则返回falseListLength(L)//返回线性表L的元素个数LocateElem(L,e)//将线性表L中查找与给定值e相等的元素，若成功返回该//元素在表中的序号，否则返回0GetElem(L,i,&e)//
8、将线性表L中的第i个位置元素返回给e}ADTList改进型操作引用型操作04/10/202110实现两个线性集合的并集/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/voidListUnion(List&La,ListLb){intLa_len,Lb_len,i;ElemTypee;/*声明与La和Lb相同的数据元素e*/La_len=ListLength(La);/*求线性表的长度*/Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetE
9、lem(Lb,i,e);/*取Lb中第i个数据元素赋给e*/if(!LocateElem(La,e))/*La中不存在和e相同数据元素*/ListInsert(La,++La_len,e);/*插入*/}}04/10/202111线性表怎么在计算机里存储？04/10/202112内容提要线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构（单链表）04/10/202113线性表的顺序存储结构用一组连续的存储单元依次存储线性表中的每个数据元素。a1a2aiai+1an内容地址元素在表中的位序
10、12ii+1nLb=LOC(a1)b=b+Lb=b+(i-1)Lb=b+(n-1)Lb=b+(maxLen-1)L空闲区【注意】L为每个数据元素占据的存储单元数目；LOC(ai)为数据元素ai的地址则LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L04/10/202114线性表的顺序存储结构例题【例】一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98
