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

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

1、第二章线性表信阳师范学院计算机与信息技术学院2021/6/161主要内容2.1线性表概念及基本操作2.2线性表的顺序存储和实现2.3线性表的链式存储和实现2.4一元多项式的表示及相加2021/6/162信阳师范学院计算机与信息技术学院了解线性表逻辑结构的特征；重点掌握线性表的顺序存储结构和链式存储结构；掌握在顺序存储结构下，线性表的基本操作实现的算法；掌握在链式存储结构下，线性表的基本操作实现的算法；比较线性表两类存储结构的不同特点及适用场合。学习要点2021/6/163信阳师范学院计算机与信息技术学院（1）线性表的定义和基本操作。（2）线性表的实现：顺序存储结构；链式存储

2、结构；线性表的应用考研大纲要求及分析1考纲要求2021/6/164数据结构考研辅导本章虽然讨论的是线性表，但涉及的许多问题都具有一定的普遍性。因此，本章是本课程的重点之一，也是其他后续章节的重要基础。换言之，本章是必考内容，而且可能结合后续章节的相关内容出题上。顺序表的运算本质上是对数组进行操作，因此，可能会与排序、查找等内容结合出题。单链表由于结构简单、应用灵活、难度适中，是数据结构各类考试的重要考点，所以一定要深刻理解、熟练掌握、灵活运用。2考纲分析2021/6/165数据结构考研辅导姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林632

3、18888张力63215555...2.1线性表的概念例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。一线性表的逻辑结构电话号码簿是数据元素的有限序列，每一数据元素包括两个数据项，一个是用户姓名，一个是对应的电话号码。线性表是n个类型相同数据元素的有限序列，通常记作（a1,a2,a3,…,an）。2021/6/166信阳师范学院计算机与信息技术学院设A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一线性表同一线性表中的元素必须是同一类型的；称ai-1是ai的直接前驱，ai+1是

4、ai的直接后继；在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；性表中元素的个数n称为线性表的长度，n=0时称为空表；ai是线性表的第i个元素，称i为数据元素ai的位序。说明2021/6/167信阳师范学院计算机与信息技术学院ADTList{数据对象:D={ai

5、aiElemSet,i=1,2,…，n,n>=0}数据关系:R1={

6、ai-1,aiD,i=2,…，n}或：R2={

7、ai,ai+1D,i=1,2,…，n-1}a1

8、ai-1a2顶点：表示数据元素边：表示数据元素间的关系前驱关系后继关系图示表示抽象数据类型线性表的定义如下：aiai+1an2021/6/168信阳师范学院计算机与信息技术学院1初始化操作InitList(&L)操作结果：构造一个空的线性表L。2销毁操作DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。3置空操作ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。4判空操作ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表返回TRUE，否则返回FALSE。基本操作：2021/6/169信阳师范学院计

9、算机与信息技术学院5求表长操作ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。6取元素操作：GetElem(L,i,&e)初始条件：线性表L已存在，1≤i≤ListLength(L)。操作结果：用e返回L中第i个数据元素的值。7查找操作LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回L中第1个与e满足compare()的数据元素的位序。若表中不存在这样的元素，则返回0；2021/6/1610信阳师范学院计算机与信息技术学院8求前驱操作PriorELem(L,cur

10、_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。9求后继操作NextELem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的前驱，否则操作失败，next_e无定义。2021/6/1611信阳师范学院计算机与信息技术学院10插入操作ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤ListLength