第2章线性表 2.1线性结构的特点《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 第二章 线性表 6学科网 WWW.ZXXK.CON 数据结构课程的内容 线性结构（线性表、栈、队、串、数组） 逻辑结构 树结构 非线性结构 图结构 逻辑结构唯一 颜序结构 链式结构 数据结构 物理（存储）结构 存储结构不唯一 索引结构 散列结构 插入运算 删除运算 运算的实现依赖于 数据运算 修改运算 存储结构 查找运算 排序运算 6 学科网 WWW.ZXXK.CON 线性结构的特点： 对于非空的线性表，有且仅有一个开始结点和一 个终端结点；开始结点没有直接前趋，有且仅有一个 直接后继；终端结点没有直接后继，有且仅有一个直 接前趋；其余任何结点有且仅有一个直接前趋和一个 直接后继。 非空线性表可表示为：（a1,a2,.y an 6 学科网 -a 简言之，线性结构反映结点间的逻辑关系是一对一的 线性结构包括线性表、堆栈、队列、字符串、数组 等等，其中，最简单、最常用的本章所介绍的线性 表 区 6学科网 WWW.ZXXK.CON 本章主要内容 2.1线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3线性表的链式表示和实现 2.4应用举例 6学科网 WWW.ZXXK.CON 2.1线性表的逻辑结构 1.线性表的定义：是n个数据元素的有限序列 (a3a29…ai-1,ai, ai+1,... 数据元素 开始结点 ai的直接前趋 ai的直接后继 终结点 下标，是元素的 n为元素总个 序号，表示元素 n=0时称为空表 数，即表长 在表中的位置 6学科网 WWW.ZXXK.CON 例1分析26个英文字母组成的英文表 （A,B,C,D, 数据元素都是字母，元素间关系是线性关系 例2分析学生情况登记表 学号 姓名 性别 年龄 班级 2001011810205 于春梅 女 18 2001级电信016班 2001011810260 何仕鹏 男 18 2001级电信017班 2001011810284 王爽 女 18 2001级通信011班 2001011810360 王亚武 男 18 2001级通信012班 数据元素都是记录，：元素间关系是线性关系 注意：同一线性表中的元素必定具有相同特性 6学科网 WWW.ZXXK.CO 线性表的基本运算有( 抽象数据描述) (1) 置空表SETNULL(L) 运算结果是将线性表L置成空表。 (2)求长度LENGTH(L) 运算结果是线性表L中的结点个 数。 (3)取结点GET(L,i 当1<=i<=LENGTH(L)时，结 果是表L中的第个结点。 (4)定位LOCATE(L,X) 当线性表L中存在一个值为x的 结点时，结果是该结点的位置；若表L中存在多个值为x的结点 则返回首次找到的结点位置；若表L中不存在值为x的结点，则 返回一个特殊值表示值为x的结点不存在。 (5)插入INSERT(L,x,i)在线性表L的第i个位置插入 一个值为x的新结点。这里1<=i<=n+1,n是原表L的长 度。 (6) 删除DELETE(L,i)删除线性表L的第i个结点。这里1 <=i<=n,n是原表L的长度。 6学科网 上述是线性表抽象数据类型的定义，其中只是一些基本操祚， 更复杂的如：将两个有序线性表合并成一个有序线性表等。复杂 的操作可用基本操作实现。 void MergeList(List la,List Ib,List &lc) SETNULL(Ic); i=j=1;k=0; la_len=LENGTH(la);Ib_len=LENGTH(Ib); while(i<=la_len &j<=lb_len) ai=GET(la,i);bj=GET(Ib,j); if(ai<=bj) INSERT(Ic,ai,++k);i++;} else INSERT(Ic,bj,++k);j++;} } 6学科网 WWW.ZXXK.CO while(i<=la_len) { ai=GET(la,i++); INSERT(Ic,ai,++k); } while(i<=lb_len) { bj=GET(Ib,j++); INSERT(Ic,bj,++k); }