第2章 线性表 (数据结构教程PPT课件)

《第2章 线性表 (数据结构教程PPT课件)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、教学目的了解线性表逻辑结构的基本特征;掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用C语言描述它们的类型定义；掌握顺序表的基本操作的算法；掌握链表的建立及其基本操作的算法；能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及使用场合.第2章线性表诚昊工作室教学重点﹑难点掌握顺序表的基本操作:查找、插入、删除。在掌握链表的建立与遍历的基础上，能够实现链表的基本操作：插入与删除、查找。第2章线性表教学内容2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4线性表的应用举例第2章线性表2.1线性表的逻辑结构2.1

2、.1线性表的定义线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,...,ai-1,ai,ai+1,...,an)其中：L为线性表名称，习惯用大写书写；ai为组成该线性表的数据元素，习惯用小写书写；特点：除了a1，an外，ai（2<=i<=n-1)都有一个前驱和后继。（ai-1，ai+1）。例如：26个英文字母。线性表中数据元素的个数被称为线性表的长度，当n=0时，线性表为空，又称为空线性表。举例La=（34，89，765，12，90，-34，22）数据元素类型为int。Ls=(Hello,World,China,Welco

3、me)数据元素类型为string。Lb=(book1,book2,...,book100)数据元素类型为下列所示的结构类型：structbookinfo{intNo;//图书编号char*name;//图书名称char*auther;//作者名称...;}2.1.2线性表的基本操作线性表初始化：Init_List(L)求线性表的长度：Length_List(L)取表元：Get_List(L,i)按值查找：Locate_List(L,x)插入操作：Insert_List(L,i,x)删除操作：Delete_List(L,i)2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构线性

4、表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：其中，L为每个数据元素所占据的存储单元数目。相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L顺序存储结构的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；图2-1线性表顺序存储结构示意图（2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每

5、个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。在C语言中，实现线性表的顺序存储结构的类型定义#defineMAXSIZE100//线性表的最大长度typedefstruct{datatypedata[MAXSIZE];intlast;}SeqList;2.2.2典型操作的算法实现初始化线性表LSeqList*init_SeqList(){SeqList*L;L=malloc(sizeof(SeqList));L->last=-1;returnL;}2.在数组a第i个数据元素之（ai-1）前插入数据元素Xinsert(in

6、ta[],intn,inti,intx){intj;for(j=n-1;j>=i-1;j--)a[j+1]=a[j];/*结点移动*/a[i-1]=x;/*新元素插入*/n++;/*修改长度*/}3.在数组a中检索（查找）值为X的数据元素intlocate(inta[],intn,intx){inti;i=0;while((i<=n-1)&&(a[i]!=x))i++;if(i<=n-1)return(i);/*返回的是存储位置*/elsereturn(0);}}4.删除数组a第i个数据元素（ai-1）delete(inta[],intn,inti){intj;for(j=i;j<=

7、n;j++)a[j-1]=a[j];/*结点移动*/n--;/*修改长度*/}顺序表的插入：在表中第4个元素之前插入“21”。顺序表中插入元素图顺序表中删除元素顺序表的删除：删除第5个元素，插入算法的分析假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作