资源描述：
《数据结构线性表学习.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第二章线性表存在唯一的头元素存在唯一的尾元素除头元素外，每个元素均有一个直接前驱除尾元素外，每个元素均有一个直接后继线性结构的特点OOOOO线性头尾12345§2.1线性表的定义1.线性表的语言定义线性表是n个数据元素的有限序列。例:英文字母表(A，B，C，……，Z)线性表中的数据元素也可以由若干个数据项构成。这时，数据元素称为记录，含有大量记录的线性表又称为文件。例:学生情况登记表姓名学号性别年龄班级王晓林790631男21计90陈红790632女22计902.线性表的形式定义其中：a1是头元素，an是尾元素，ai是第i个元素，ai-1是ai的直接前驱，ai+1是a
2、i的直接后继。线性表可以表示为n个数据元素的有限序列:(a1，…，ai-1，ai，ai+1，…，an)n为线性表的长度(可根据需要增长或缩短)，n=0时为空表i为数据元素ai在线性表中的位序3.抽象数据类型线性表List的定义InitList(&L)操作结果:构造一个空的线性表L。数据对象:D={ai
3、ai∈ElemSet，i=1,2,…,n,n≥0}数据关系:R1={
4、ai-1,ai∈D，i=2,…,n}基本操作:ADTList{}ADTListDestroyList(&L)操作结果:销毁线性表L。初始条件:线性表L已存在。…例2-1：用线性表完成
5、集合的并运算，A=A∪B若：A={1，3，8}B={2，3，6，9}则：A=A∪B{1，3，8，2，6，9}voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}执行过程：La_len=3Lb_len=4i=1,e=2,La中没有2，La_len=4，将2插到第4个位置即：A={1，3，8，2}--
6、--------------------------------------------i=2,e=3,La中有3，返回位序为2if条件不满足，3不插入----------------------------------------------i=3,e=6,La中没有6，La_len=5，将6插到第5个位置即：A={1，3，8，2，6}----------------------------------------------i=4,e=9,La中没有9，La_len=6，将9插到第6个位置即：A={1，3，8，2，6，9}例2-2：已知线性表LA、LB为有序表，将
7、LA、LB归并为一个新线性表LC，且保持其有序性若：LA=(1，3，8)LB=(2，3，6，9，12，15)则：LC=(1，2，3，3，6，8，9，12，15)138LA23691215LBLC12336812159voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len))//LA、LB均非空{GetElem(La,i,ai);GetElem(Lb,j,bj)
8、;if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len)//LA非空{GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len)//LB非空{GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}算法2.2归并两个有序的线性表§2.2线性表的顺序表示和实现线性表的顺序表示:用一组地址连续的存储单元依次存储线性表的数据元素。LOC(a1)LOC(ai)a1a2ai
9、an……存储地址内存状态设每个元素需占用l个存储单元LOC(ai)表示元素ai的存储地址LOC(a1)是第一个数据元素a1的存储地址，也是整个线性表的起始地址lLOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)×l顺序存储结构的线性表称为顺序表顺序表的特点：表中相邻元素ai和ai+1赋以相邻的存储位置LOC(ai)和LOC(ai+1)即：以元素在计算机内“物理位置相邻”来表示元素间的逻辑关系只要确定了存储线性表的起始位置，线性表中任一元素都可以随机存取。线性表顺序存储结构表示#defineLIST_INIT_SIZE10
