资源描述：
《数据结构 第2章线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表学习导读线性表（Linearlist）是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；其他的每一个数据元素均有一个唯一的直接前驱和一个唯一的直接后继数据元素。通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。1.线性表的逻辑结构2.线性表的顺序存储结构3.线性表的链式存储结构4.一元多项式的表示及相加6学时2.1线性表的逻辑结构线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在
2、不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；再如，某公司2003年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12(个月)的线性表，其中的每一个月的数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，图2-1的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一
3、个记录，每个记录包含八个数据项：职工号、姓名、基本工资……。职工编号姓名基本工资岗位工资奖金应发工资扣款实发工资1201张强154030020010402020201301周敏15002002009002018801202徐黎155030020010503020201105黄振1530250200980201960┇┇┇┇┇┇┇┇图2-1职工工资表矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。综上所述，一个线性
4、表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。如果n>0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，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)ADTLi
5、st{数据对象:D={ai
6、ai∈ElemSet,i=0,1,2,…，n-1n≥1}数据关系:R={
7、ai-1，ai∈D,i=1,2,…，n-1Elemset为某一数据对象集；n为线性表的长度。线性表的基本操作：1．InitList(&L)初始化：构造一个空的线性表L。2.DestroyList(&L)销毁：销毁一个业已存在的线性表L。3.ClearList(&L)清空：将一业已存在的线性表L重置为空表。4.ListEmpty(L)判表空：若L为空表，则返回TRUE；否则返回FALSE。5．ListLeng
8、th(L)求长度：对给定的线性表L，返回线性表L的数据元素的个数。6．GetElem(L,i,&e)对给定的线性表L，取第i个数据元素。0≤i≤Length(L)-1），用e返回L中第i个数据元素的值。或GetElem(L,I)，1≤i≤Length(L)，正确返回值，否则出错。LocateElem(L,e)e为线性表中的同型元素，定位返回L中第一个与e满足相等关系数据元素的位序,若这种数据元素不存在,则返回0。PriorElem(L,cur_e,&pre_e)求前驱：若cur_e是L的数据元素,且不是第一个,则用pre_e
9、返回它的前驱,否则操作失败,pre_e无定义。或PriorElem(L，e)求前驱：e是L表中同质元素，求出e的前驱元素并用e返回其值。若有值，函数返回真，否则返回假。9.NextElem(L,cur_e,&next_e)求后继若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。或用NextElem(L，e)求后继：e是L表中同质元素求出e的后继元素并用e返回其值。若有值，函数返回真，否则返回假。10.ListInsert(&L,i,e)插入在L中第i个位置之前插入新的
10、数据元素e,L的长度加1。 11.ListDelete(&L,i,&e)删除删除L的第i个数据元素,并用e返回其值,L的长度减1。（i的选择要合法）12.ListTraverse(L,visit())遍历对给定的线性表L，依次输出L的每一个数据元素。（不允许重复）13.Copy(L,C)复
