数据结构次课线性表A.pptVIP

数据结构课程的内容 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例 2.1 线性表的逻辑结构 例1 分析一副扑克的点数组成的英文表 (2，3，4，…，J，Q，K，A） 练：判断下列叙述的正误： 1. 线性表的逻辑结构定义是唯一的，不依赖于计算机。 2. 线性结构反映结点间的逻辑关系是一对一的。 3. 一维数组是线性表，但二维或N维数组不是。 4. “同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。 2.2 线性表的顺序表示和实现 2.2.1 顺序表的表示 用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。 线性表的顺序存储结构示意图 线性表顺序存储特点： 1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）： 设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC(ai) = LOC(a1) + L *（i-1） LOC(ai+1) = LOC(ai)+L 例1 一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的起始地址是９８，则Ｍ[３]的起始地址是 2.2.2 顺序表的实现（或操作） 2.2.3 顺序表的运算效率分析 算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 移动元素的个数取决于插入或删除元素的位置. 讨论2：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为： f(n) = 假定在表中任意位置插入、删除元素都是等概率的， 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n ，则： 顺序表小结 顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.3 线性表的链式表示和实现 2.3.1 链表的表示 例1 画出26 个英文字母表的链式存储结构。 与链式存储有关的术语： 4、头指针、头结点和首元结点 示意图如下： 例： * 每课一贴： 两个人在森林里，遇到了一只大老虎。A就赶紧从背后取下一双更轻便的运动鞋换上。B急死了，骂道：“你干嘛呢，再换鞋也跑不过老虎啊！” A说：“我只要跑得比你快就好了。”二十一世纪，没有危机感是最大的危机。即使是电信，银行，保险，甚至是公务员这些我们以为非常稳定和有保障的职业，也会面临许多的变数。更多的老虎来临时，我们有没有准备好自己的跑鞋？ (2，3，4，…，J，Q，K，A） ： ： ： ： ： 2001级通信012班 18 男 杨 扬 2001011810360 2001级通信011班 18 女 石文娟 2001011810284 2001级电信017班 18 男 周 刚 2001011810260 2001级电信016班 18 女 管春燕 2001011810205 班级 年龄 性别 姓名 学号 生活实例： 简言之，线性结构反映结点间的逻辑关系是 一对一(1:1) 的 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个元素外，集合中的每个数据元素均只有一个前驱 除最后一个元素外，集合中的每个数据元素均只有一个后继 若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , ……, an） 线性结构的定义： （逻辑、存储和运算） 线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是--- 线性表 第2章 （a1, a2, … ai-1，ai, ai＋1 ，…, an） 2.1.1 线性表的定义：用数据元素的有限序列表示 n=0时称为 数据元素 线性起点 ai的直接前趋 ai的直接后继 下标，是元素的序号，表示元素在表中的位置 n为元素总个数，即表长 空表 线性终点 例2 分析学生情况登记表 数据元素都是记录