资源描述：
《数据结构c语言版 第2章 线性表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表学习导读线性表（Linearlist）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；其他的每一个数据元素均有一个唯一的直接前驱和一个唯一的直接后继数据元素。通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。1.线性表的逻辑结构2.线性表的顺序存储结构3.线性表的链式存储结构4.一元多项式的表示及相加6学时学习目标与重点◆理解线性表的概念、特点和逻辑结构特性；◆掌握顺序表的定义与操作实现；◆掌握单链表的定
2、义、插入与删除算法及综合应用；◆了解循环链表的定义和特点；◆了解双向链表的定义和特点以及相关操作的实现。2.1线性表的逻辑结构线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；再如，某公司2003年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12(个月)的线性表，其中的每一个月的数值就是一个数据元素。职工编号姓名基本工资岗位工资奖金应发工资扣款实发工资1201
3、张强154030020010402020201301周敏15002002009002018801202徐黎155030020010503020201105黄振1530250200980201960┇┇┇┇┇┇┇┇图2-1职工工资表矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。综上所述，一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。如果n>0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元
4、素，ai（0≤i≤n-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2，…，ai-1，ai，ai+1，…，an-1）抽象数据类型线性表的定义如下：(见严蔚敏书P19ADTList)ADTList{数据对象:D={ai
5、ai∈ElemSet,i=0,1,2,…，n-1n≥0}ElemSet为某一数据对象集；n为线性表的长度。数据关系:R={6、i-1，ai>
7、ai-1，ai∈D,i=1,2,…，n-1}线性表的基本操作：1．InitList(&L)初始化：构造一个空的线性表L。2.DestroyList(&L)销毁：销毁一个业已存在的线性表L。3.ClearList(&L)清空：将一业已存在的线性表L重置为空表。4.ListEmpty(L)判表空：若L为空表，则返回TRUE；否则返回FALSE。5．ListLength(L)求长度：对给定的线性表L，返回线性表L的数据元素的个数。6．GetElem(L,I,&e)对给定的线性表L，取第i个数据元素。0≤i≤Length(L)-1）
8、，用e返回L中第i个数据元素的值。7.LocateElem(L,e,compare())定位返回L中第一个与e满足关系compare()的数据元素的位序,若这种数据元素不存在,则返回0。8.PriorElem(L,cur_e,&pre_e)求前驱：若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。NextElem(L,cur_e,&next_e)求后继若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。ListInsert(&L,i,
9、e)插入在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e)删除删除L的第i个数据元素,并用e返回其值,L的长度减1。ListTraverse(L,visit())遍历对给定的线性表L，依次输出L的每一个数据元素。Copy(L,C)复制将给定的线性表L复制到线性表C中。14.Merge(A,B,C)合并将给定的线性表A和B合并为线性表C。}ADTList更复杂的运算:一表拆成二表、求两表的共同元素等。算法2-1将所有在线性表Lb中但不在La表中的数据元素插入到La中。（见125个算法）时间复杂性为：O
10、（La表长*Lb表长）算法2-2已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。（见125
