数据结构第2章线性表-(2).ppt

目录2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加线性表的定义线性表(LinearList)：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。当n=0时，称为空表。当n0时，将非空的线性表记作：(a1，a2，…an)a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。线性表的定义a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱;ai+1，ai+2，…an都是ai(1≦i≦n-1)的后继，其中ai+1是ai的直接后继。线性表的逻辑结构线性表中的数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。线性表中的结点可以是单值元素(每个元素只有一个数据项)。例1:26个英文字母组成的字母表：(A，B，C、…、Z）线性表的逻辑结构例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188）例3：一副扑克的点数(2，3，4，…，J，Q，K，A)线性表的逻辑结构例4：某校2001级同学的基本情况：{(‘2001414101’，‘张里户’，‘男’，06/24/1983)，(‘2001414102’，‘张化司’，‘男’08/12/1984)……(‘2001414102’，‘李利辣’，‘女’，08/12/1984)} 线性表的逻辑结构若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。对线性表的数据元素可以访问、插入和删除。线性表的抽象数据类型定义ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}数据关系：R={ai-1,ai|ai-1,ai∈D,i=2,3,…,n}基本操作：InitList(L)操作结果：构造一个空的线性表L；线性表的抽象数据类型定义ListLength(L)初始条件：线性表L已存在；操作结果：若L为空表，则返回TRUE，否则返回FALSE；….GetElem(L,i,e)初始条件：线性表L已存在，1≦i≦ListLength(L)；操作结果：用e返回L中第i个数据元素的值；ListInsert(L,i,e)初始条件：线性表L已存在，1≦i≦ListLength(L)；操作结果：在线性表L中的第i个位置插入元素e；….}ADTList目录2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示和相加线性表的顺序存储结构顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。顺序存储的线性表的特点：线性表的逻辑顺序与物理顺序一致;数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。线性表的顺序存储结构线性表的顺序存储结构在具体的机器环境下：设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l线性表的顺序存储结构在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。线性表的顺序存储结构#defineOK1#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintStatus;typedefintElemType;typedefstruct{