资源描述：
《《数据结构线性表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表陈守孔孟佳娜陈卓本章目录2.1线性表的类型定义2.1.1线性表的概念2.1.2线性表的抽象数据类型2.2线性表的顺序表示和实现2.2.1线性表的顺序表示2.2.2顺序表上基本运算的实现2.3线性表的链式表示和实现2.3.1单链表的表示2.3.2单链表操作的实现2.4线性表实现方法的比较2.5循环链表2.6双链表2.7静态链表（*2.8算法设计举例）2主要内容知识点线性表的定义顺序表单链表双链表静态链表重点难点顺序表操作的实现单链表操作的实现顺序表和链表操作时间复杂度的分析静态链表3线性结构在数据元素的非空的有限集合中：存在唯一的一
2、个被称为“第一个”的数据元素；存在唯一的一个被称为“最后一个”的数据元素；除第一个元素外，集合中每个元素都有且仅有一个前驱；除最后一个元素外，集合中每个元素都有且仅有一个后继；4线性表(LinearList)定义定义：n个具有相同特性的数据元素组成的有限序列；表示：{a1,…,ai-1,ai,ai+1,…,an}ai必须具有相同特性，即属于同一数据对象ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素数据元素ai在线性表中有确定的位置i，i称为位序线性表中数据元素的个数n称为线性表的长度,n=0时，线性表称为空表5抽象数据类型定义AD
3、TList{数据对象：D={ai
4、ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R={
5、ai,ai-1∈D,i=2,…,n}基本操作：ListInit(L)；ListLength(L)；ListGet(L,i);ListLocate(L,x);ListClear(L);ListEmpty(L)；ListPrior(L,e)；ListNext(L,e)；ListInsert(L,i,e);ListDelete(L,i);}ADTList6例如2.1遍历线性表LListTraverse(ListL，visit())
6、{//遍历线性表if(ListEmpty(L))printf(“空表”);elsefor(i=1;i<=ListLength(L);i++)visit(ListGet(L,i))；}7例2.2合并线性表ListListMerge(ListLa,ListLb){//La和Lb是两个非递减有序的线性表，将线性表La和Lb合并成一个新的线性表Lc，Lc也非递减有序。ListInit(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=L
7、b_len))//La和Lb均非空{ai=ListGet(La,i);bj=ListGet(Lb,j);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}（接下页）8（接上页）while(i<=La_len){//Lb已空，将La表的剩余部分复制到新表ai=ListGet(La,i++);ListInsert(Lc,++k,ai);}while(j<=Lb_len){//La已空，将Lb表的剩余部分复制到新表bj=ListGet(Lb,j++);Lis
8、tInsert(Lc,++k,bj);}return(Lc);}//ListMerge例2.2合并线性表9逻辑结构是本质通过上面两个例子可以看出：逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构10线性表的顺序表示和实现线性表的顺序表示:线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。设a１的存储
9、地址为Loc(a１)，每个数据元素占L个存储单元，则第i个数据元素的地址为：Loc(ai)=Loc(a1)+(i-1)*L1≤i≤n01i-1in-1MAXSIZE-1a1a2…ai…an…dataai-1ai+1顺序存储结构的线性表的类型定义如下：#defineMAXSIZE100∥顺序表的最大容量typedefstruct{ElemTypedata[MAXSIZE];∥存放线性表的数组intlast;∥last是线性表的长度}SeqList;11顺序表上基本运算的实现(1)SeqListSeqListInit(SeqListL){//构造
10、一个空的顺序表L.length=0;//初始化顺序表为空表returnL;}顺序表的初始化:12顺序表上基本运算的实现(2)插入运算:在第i个位置，插入元素e思想：
