第二章线性表

第二章线性表Tag内容描述：<p>1、1 2.3 线性表的链接存储结构及实现 静态存储分配：在编译时为变量分配内存，并且一 经分配就始终占有固定的存储单元，直到该变量退出 其作用域。 动态存储分配：在程序的运行期间根据实际需要随时 申请内存，并在不需要时释放。C+中动态存储分配是 通过指针实现的。 2 静态存储分配 顺序表事先确定容量 链 表动态存储分配 运行时分配空间 n链式存储分配的特点： 根据线性表的长度动态的申请存储空间，以解决 顺序存储中存在的存储空间难以确定的问题。 n链式存储结构的实现 单链表 双向链表 循环链表等 3 单链表：线性表的链接存储结构之。</p><p>2、线性结构的定义： 若结构是非空有限集，则有且仅有一个开始结点和一个 终端结点，并且所有结点都最多只有一个直接前趋和一个直 接后继。 可表示为：（a1 , a2 , , an） 简言之，线性结构反映结点间的逻辑关系是 的。 特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是- 线性表线性表 一对一 (1:1) 1 第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储结构线性表的顺。</p><p>3、数据结构 第二章 线性表 重庆一中 葛静 1 数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的 数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性 表应用举例。 2.1线性表的定义及基本操作 2.1.1 定义：线性表(Linear List)是若干数据元素的一个线性序列，记为： L=(a1,ai-1aiai+1an) 其中：L为表名，ai(1in)为数据元素；n为表长，n0 时，L为非空表，否则 为空表。 2.1.2 线性表的逻辑结构和特征 线性表L可用二元组形式描述： L= (D,R) 数据元素集合: D=ai | aidatatype ,i=1,2, n ,n0 关系集合: R= | 。</p><p>4、第2章 线性表 第1章介绍了几种基本逻辑结构：线性结构、 树形结构和图结构。线性结构是最简单、最基本 的数据结构，本章讨论线性表的基本概念、存储 结构以及相关运算。 主要内容： 线性表的基本概念 线性表的顺序存储结构及实现 线性表的链表存储结构及实现 线性表的应用 1 2.1 线性表的基本概念 现实中存在大量线性表的实例。例如： 大写英文字母表：(A,B,C,Y,Z)； 一周中7天(星期一，星期二，星期日)； MP3播放器中的若干个歌曲的目录。怎样查 找自己喜欢的歌曲？怎样输入新的曲目？删 除过时曲目？这就是本节所研究的内容：线 性表及。</p><p>5、第二章 线性表 * 线性结构的基本特征为: 1集合中必存在唯一的一个“第一元素” ； 2集合中必存在唯一的一个 “最后元素” ； 3除最后元素在外，均有 唯一的后继； 4除第一元素之外，均有 唯一的前驱。 线性结构 是一个数据元素的有序（次序）集合。 线性表是一种最简单的线性结构 2.1 线性表的类型定义 2.3 线性表类型的链式表示和实现 2.4 一元多项式的表示及相加 2.2 线性表类型的顺序表示和实现 本章主要内容： 二、线性表的抽象数据类型表示(教材P19) ADT List ADT List 数据对象： 数据关系： 基本操作： D=ai | aiElemSet, i=1,2,n,。</p><p>6、每课一贴： 两个人在森林里，遇到了一只大老虎。A就赶 紧从背后取下一双更轻便的运动鞋换上。B急死了 ，骂道：“你干嘛呢，再换鞋也跑不过老虎啊！” A说：“我只要跑得比你快就好了。”二十一世纪， 没有危机感是最大的危机。即使是电信，银行，保 险，甚至是公务员这些我们以为非常稳定和有保障 的职业，也会面临许多的变数。更多的老虎来临时 ，我们有没有准备好自己的跑鞋？ 1 数据结构课程的内容 2 (2，3，4，J，Q，K ，A） 学号姓名性别年龄班级 2001011810205管春燕女 182001级电信016班 2001011810260周 刚男 182001级电信017班 2。</p><p>7、线性结构包括线性表、栈、队列、串、数组和广义表。其特线性结构包括线性表、栈、队列、串、数组和广义表。其特 点是：在数据元素的非空有限集合中点是：在数据元素的非空有限集合中 存在惟一的一个被称作存在惟一的一个被称作 “第一个第一个” ” 的的数据元素；数据元素； 存在惟一的一个被称存在惟一的一个被称作作 “ “最后一个最后一个” ” 的数据元的数据元素；素； 除第一个数据元素之外，集合中的每个数据元素均只有一个除第一个数据元素之外，集合中的每个数据元素均只有一个 前驱；前驱； 除最后一个数据元素之外，集合中的。</p><p>8、第二章 线性表一 名词解释1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现6. 建表 7.字符串 8.串 9.顺序串 10.链串二、填空题1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________或______。对任意一对相邻结点ai、ai1(1<=i<n),ai称为ai1的直接______ai1称为ai的直接______。2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。3.线性。</p><p>9、第2章 线性表及其应用第2章 线性表及其应用本章学习要点掌握线性表的逻辑结构及相关概念。掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。熟练掌握顺序表和链表上各种基本操作的实现过程。灵活运用顺序表和链表的特点解决实际应用问题。线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基。</p><p>10、1 第第 2 章章自测卷答案自测卷答案姓名姓名班级班级 题号题号一一二二三三四四五五六六七七总分总分 题分题分1310101071040100 得分得分 一、填空（每空一、填空（每空 1 分，共分，共 13 分）分） 1. 【严题集 2.2】在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数 与 表长和该元素在表中的位置有关。 2. 线性表中结点的集合是线性表中结点的集合是 有限有限的，结点间的关系是的，结点间的关系是一对一一对一的。的。 3. 向一个长度为向一个长度为 n 的向量的第的向量的第 i 个元素个元素(1in+1)之前插。</p><p>11、第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,线性表,线性结构是一个数据元素的有序（次序）集。 线性结构的特点： 存在唯一的一个被称做“第一个”的数据元素； 存在唯一的一个被称做“最后一个”的数据元素； 除第一个之外，集合中的每个数据元素均只有一个前驱； 除最后一个之外，集合中每个数据元素均只有一个后继。,2.1 线性表的类型定义,线性表（Liner List）：n（ 0）个数据元素的有限序列，记作（a1, ai-1, ai, ai+1, an）；其中ai是表中数据元素，n是。</p><p>12、线性结构的特点： K1 K2 K3 Kn 在数据元素的非空有限集中， （1）存在唯一的一个被称为“第一个”的数据元素； （2）存在唯一的一个被称为“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个“直接前驱”； （4）除最后一个之外，集合中的每个数据元素均只有一个“直接后继”； 常用的线性结构：线性表、堆栈、队列、串等,第二章 线性表,本章主要内容： 线性表的概念（逻辑结构） 线性表的顺序存储结构（顺序表） 线性表的链接存储结构（链表） 单链表 静态链表 循环链表 双向链表 线性表的应用（Josephus问题。</p><p>13、线性表是一种最简单的线性结构,第二章 线性表,线性结构的基本特征:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素”,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是 一个数据元素的有序集,2.1 线性表类型的定义,2.3 线性表类型的实现 链式映象,2.4 一元多项式的表示,2.2 线性表类型的实现 顺序映象,2.1 线性表的类型定义,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。,数据。</p><p>14、第2章线性表2.1 知识点分析1线性表的定义线性表是具有相同数据类型的n（n=0）个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an)其中n为表长， n0 时称为空表。在线性表中相邻元素之间存在着顺序关系。对于元素ai 而言，ai-1 称为 ai 的直接前驱，ai+1 称为 ai 的直接后继。也就是说：（1）有且仅有一个开始结点（a1），它没有直接前驱；（2）有且仅有一个终端结点（an），它没有直接后继；（3） 除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。 2顺序表顺序表是线性表的顺序存储，是指在内。</p><p>15、第二章 线性表,线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,2.1 线性表的类型定义（P18-19） 定义：一个线性表是n个数据元素的有限序列,例 英文字母表（A,B,C,Z)是一个线性表,特征：（P19） 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 i为数据元素ai在线性表中的位序,2.2 线性表的顺序存。</p><p>16、第二章 线性表,线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继,2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列,例 英文字母表（A,B,C,Z)是一个线性表,特征： 元素个数n表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项,2.2 线性表的顺序存储结构 顺序表： 定义：。</p>