资源描述：
《-线性表ppt课件》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第二章线性表1【学习目标】了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。【重点和难点】链表。熟练掌握链表的操作对以后各章的学习将有很大帮助。2什么是线性结构？简单地说，线性结构是一个数据元素的有序集合。它有四个基本特征：1．集合中必存在唯一的一
2、个"第一元素"；没有"前驱"2．集合中必存在唯一的一个"最后元素"；没有"后继"3．除最后元素之外，其它数据元素均有唯一的"直接后继"；4．除第一元素之外，其它数据元素均有唯一的"直接前驱"。课前回顾32.1线性表的逻辑定义2.1.1线性表的定义什么是线性表？具有相同数据类型的n个数据元素的有限序列。L＝(a1,a2,...,ai,...,an)表长:序列中数据元素的个数n；n=0——空表若ai是第i个数据元素，称i为ai在线性表中的位序。Linear_list=(D,R)D＝{aiai∈datatype,i=1,2,...,n,
3、n≥0}R＝{ai-1,ai∈D,i=2,...,n}42.1线性表的逻辑定义2.1.2线性表的基本操作基本操作：1.线性表初始化：Init_List(L)初始条件：线性表L不存在。操作结果：构造一个空的线性表L。2.求线性表的长度：Length_List(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。3.取表元：Get_List(L,i)初始条件：线性表L已存在，1≤i≤Length_List(L)。操作结果：返回L中第i个元素的值或地址。52.1线性表的逻辑定义2.1.2线性表的基本操作4.按值查
4、找：Locate_List(L,x)初始条件：线性表L已存在，x是给定的一个数据元素。操作结果：返回L中第一个值为x的数据元素的位序或地址。若这样的元素不存在，则返回-1。5.插入操作：Insert_List(L,i,x)初始条件：线性表L已存在，1≤i≤Length_List(L)+1。操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。6.删除操作：Delete_List(L,i)初始条件：线性表L已存在且非空，1≤i≤Length_List(L)。操作结果：删除L的第i个元素，L的长度减1。62.2线性表的顺序存储及
5、操作实现2.2.2顺序表中基本操作的实现intLength_List(SeqListL){return(L->last＋1);}datatypeGet_List(SeqListL,intpos){returnL->data[pos-1];}92.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现重点讨论:一、初始化操作二、元素定位操作三、插入元素操作四、删除元素操作102.2线性表的顺序存储及操作实现2.2.2顺序表中基本操作的实现函数名:malloc功 能:内存分配函数用 法:voidmalloc(unsignedsi
6、ze);返回值：指针，指向长度为size的存储空间；若分配失败，返回NULL。11一、初始化操作SeqListinit_SeqList(){SeqListL;L=malloc(sizeof(SeqList));L->last=-1;returnL;}时间复杂度为：O(1)12二、按值查找若顺序表中存在和给定值相等的数据元素，就返回第一个满足条件元素的在线性表中的位置，以-1返回值表示不存在这样的数据元素。intLocation_SeqList(SeqListL,datatypex){inti=0;//数组下标从0开始while(i
7、<=L->last&&L->data[i]!=x)i++;//依次进行判定if(i>L->last)return-1;//下标超出范围，不存在elsereturni;//返回的是数组下标}时间复杂度为：O(n)13三、插入元素操作按定义，在线性表的第i个元素之前插入一个元素x，使得线性表(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,x,ai,…,an)逻辑结构的变换：(1)改变了表中ai-1,ai元素之间的关系，使改变为和(2)表长增101ii+1i+2n-1MAX
8、-1a1a2…ai-1aiai+1…an…01ii+1i+2nMAX-1a1a2…ai-1xai…an…线性表中数据元素的插入前后如下图所示14在线性表L中第i个数据元素之前插入数据元素XintInsert_SeqList(SeqListL，int
