资源描述：
《数据结构课件CD 第02章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章 线性表数据结构主讲教师：周时阳本章主要介绍线性表，它属于线性结构。讨论线性表的逻辑结构、逻辑结构上定义的运算、物理结构、逻辑结构与物理结构对应关系、运算的实现算法与效率分析。重点研究线性表的两类物理结构和主要运算的实现算法及其效率分析，并讨论两类物理结构优缺点。提出了最好复杂度、最坏复杂度和平均复杂度及其一般的分析方法。内容摘要2重点讲解2.1线性表的定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加小结32.1.1逻辑结构定义及术语线性表是数据元素的有限集，且具有下列3个特点
2、：（1）存在唯一的一个数据元素仅有一个直接后继；（2）存在唯一的数据元素仅有一个直接前驱；（3）其余的数据元素均有唯一的直接前驱和唯一的直接后继。讨论：①线性表概念是指数据的逻辑结构，即为数据逻辑结构的基本型之一“线性结构”。因为定义中讲的“数据元素有限集”即为数据逻辑结构（D，S）中的数据集D；定义中讲的“具有的3个特点”就是数据逻辑结构（D，S）中的关系集S的一种“关系”。目录2.1线性表的定义4②线性表既是一个结构类型概念，又是一个具体结构的概念。实质上，凡是符合上述3个特点（即“关系”）的数据集，统称线性表。具体线
3、性表是由表名加以标识，如：线性表L1、线性表L2等等。③表长——线性表还有数据元素的个数叫线性表的长度，简称表长。④空表——具有零个数据元素的线性表称为空线性表，简称空表。空表表长为0。⑤序号——对线性表所有元素，赋予一个序号。序号为I的数据元素，称为第I个数据元素。赋予序号方法是：ⅰ）赋予具有特点（1）的数据元素的序号为1；ⅱ）如果某数据元素序号为I,则其直接后继的序号为I+1。5集合法L=(D,{R})，其中D={a1,a2,…,ai-1,ai,ai+1,…,an-1,an}R={,…,
4、,,…,}2.1.2逻辑结构表示方法图形法向量法L:(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)a1a2ai-1aiai+1an……L:特别地，空表的表示:L=(,)集合法L：图形法L:()向量法62.1.3基本运算定义（1）创建表IntiaList(&L)（2）销毁表DestroyList(&L)（3）置空表ClearList(&L)（4）判空表ListEmpty(L)（5）求表长ListLength(L)（6）获得数据元素GetElem(L，i，&e)（7）查
5、找数据元素LocatElem(L，e，compare())（8）获得前驱PriorElem(L，cur_e，&pre_e)（9）获得后继NextElem(L，cur_e，&next_e)各种基本比较(如：＞、＜和＝等)及其组合比较7（10）插入数据元素ListInsert(&L，i，e)注：1≤i≤ListLength(L)+1（11）删除数据元素ListDelete(&L，i，&e)注：1≤i≤ListLength(L)（12）表遍历ListTrabverse(L，visit())a1a2ai-1aiai+1an……L:
6、a1a2ai-1eaian……L:插入a1a2ai-1ai+1ai+2an……L:删除a1a2ai-1aiai+1an……L:8通过上述基本、常见的运算，可以完成其它一些复杂运算的实现。例2-1两个线性表LA和LB分别表示两个集合A和B，试给出实现A＝A∪B运算的算法。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,
7、equal))ListInsert(La,++la_len,e);}}9例2-2两个线性表LA和LB中的数据元素按“值”非递减排列，试给出实现LC＝merge(LA,LB)运算的算法。算法思想：LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：()LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2)LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2，3)10LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2，3)LA
8、：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2，3，5)LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2，3，5，6)LA：(3，5，8，11)LB：(2，6，8，9，11，15，20)LC：(2，3，5，6，8)11LA：(3，5，8，11)L
