数据结构：数组与线性表.ppt

数据结构 数组与线性表 第二章数组与线性表 数组 数组是由一些单元组成的 每个单元对应着一组下标值和一个数组元素 n维数组的每个单元对应n个下标值 数组元素可以是基本数据类型 如整型 实型 字符型等 也可以是有多个数据项的一种结构 同一数组中各个元素必须是同一数据类型 每个数组元素都占有相同数量的存储单元 才能用下标来唯一的确定数组中的元素 第二章数组与线性表 数组的顺序存储结构 在计算机中 表示数组是采用一组连续的存储单元顺序地存储各数组元素 可以用下标值随机的访问该数组的任意一个元素 计算数组元素存储地址的公式称为寻址公式 设数组为A 每个数组元素占s个存储单元 一旦定义了它的维数和各维的上 下界 就可以得到计算数组元素地址的寻址公式 第二章数组与线性表 1 一维数组寻址公式 对于一维数组 若其下标的下界为LB 上界为UB 第一元素 其下标为LB 的地址为Loc LB 下标为i的数组元素A i 的地址为Loc i 则计算Loc i 的寻址公式为 Loc i Loc LB i LB s在C语言中 数组下标的下界为0 则数组中任意一元素A i 的寻址公式为 Loc i Loc 0 i s0 i n 1 第二章数组与线性表 2 二维数组寻址公式 在C语言中 采用矩阵元素以行为主存储 即同一行的元素连续存放 存储完一行再存储下一行 设二维数组A m n m n分别表示数组的行和列 用Loc i j 表示数组元素A i j 的地址 每个单元占用s个存储单元 则寻址公式为 Loc i j Loc 0 0 i n j s0 i m 1 0 j n 1 第二章数组与线性表 定义一A 2 3 数组 对应的矩阵如下 数组元素A 1 2 其下标i 1 j 2 故它前面已经有i 1行 每行有3个元素 另外本行有j 2个元素 所以在元素A 1 2 之前 本数组已有5个元素 第二章数组与线性表 已知数组A中 每个元素A I J 在存贮时要占3个字节 设I从1变化到8 J从1变化到10 分配内存时是从地址SA开始连续按行存贮分配的 试问 A 5 8 的起始地址为A SA 141B SA 180C SA 222D SA 225 第二章数组与线性表 在编程时 使用任一种高级语言 不一定是C 如果需要从磁盘文件中输入一个很大的二维数组 例如1000 1000的double型数组 按行读 即外层循环是关于行的 与按列读 即外层循环是关于列的 相比 在输入效率上 A 没有区别B 按行读的方式要高一些C 按列读的方式要高一些D 取决于数组的存储方式 第二章数组与线性表 3 三维数组寻址公式 三维数组A m n p 可分解为p个m n的二维数组 按行为主存储的数组元素A i j k 的寻址公式为 Loc i j k Loc 0 0 0 i n p j p k s0 i m 1 0 j n 1 0 p p 1对于更多维的数组 数组元素在内存中的存储可以此类推 第二章数组与线性表 线性表 LinearList 线性表是由有限数目的相同类型数据元素组成的序列 表中的数据元素 除了第一个和最后一个以外 都有一个且只有一个前驱元素 同时也都有一个且只有一个后继元素 第一个元素只有一个后继元素而无前驱元素 最后一个元素只有一个前驱元素而无后继元素 线性表的元素个数n称为这个表的长度 当n 0时 这个表叫做空表 第二章数组与线性表 线性表在计算机内存中采用各元素顺序存储的方式 如果已知线性表第一个元素的地址和每个元素占用的存储单元数 由任一元素的序号就可以计算出该元素在内存中的地址 在编程时以一维数组表示线性表最简单 用的也最普遍 第二章数组与线性表 线性表的运算 对于给定的线性表 可进行如下的基本运算 1 求线性表的长度n 2 在第i个数据元素前面插入一个新的数据元素 3 删除第i个数据元素 4 存取或更新线性表第i个元素 5 将两个或两个以上的线性表合并成一个线性表 6 将一个线性表拆成多个线性表 7 将线性表中各数据元素按某个域值 如关键字 递增或递减的顺序重新排列 8 在线性表中查找满足某种条件的数据元素 第二章数组与线性表 1 数据元素的插入 insert 设用一个一维数组A n 表示此线性表 原来有m个元素 m n 元素值已给定 规定数组的下标从1开始 即这里数据元素对应的数组下标从1到n 要求在第i个元素前插入一个新数据元素 值为G 因原线性表的数据元素是连续排列的 中间没有空单元 所以第i个元素及其后面的各元素均需向后移动一个单元位置 这样才能将G插入到i位置 且元素总数由m增加为 m 1 第二章数组与线性表 插入函数 voidinsert A intn m i G intj if in 1 printf i值错 n else for j m j i j A j 1 A j 将第i个元素及其后面的元素后移 A i G m 线性表长度加1 第二章数组与线性表 插入函数分析 在循环语句中 当i 1时 须循环m次 表示元素插入线性表头的前面 则原线性表中m个元素均须向后移动一个单元 这是最不利的情况 当i m 1时 则循环一次也不进行 这时元素直接插入到线性表尾的后面 所以线性表的所有m个元素均不移动 这是最好的情况 第二章数组与线性表 2 数据元素的删除 Delete 设用一个一维数组A n 表示此线性表 原来有n个元素 元素值已给定 要求删除第i个数据元素 由于线性表元素在数组中必须连续排列 中间不能有空单元 故将此元素删除后 它后面的所有元素都需要向前移动一个单元 且数据元素总数由原来的n减少到n 1 第二章数组与线性表 删除函数 voiddelete A intn i intj if in printf i值错 n else for j i j n j A j A j 1 n 第二章数组与线性表 删除函数分析 在循环语句中 当i 1时 需循环 n 1 次 这是要删除线性表表头元素 是最不利的情况 当i n时 则循环一次也不执行 只是将元素数目n比原来减少一个 而第n个数据元素不必再考虑 其余的各单元的元素均维持不变 这是最好的情况 第二章数组与线性表 3 算法的时间复杂性 可以用数据元素的移动次数来度量这两个算法的时间复杂性 插入时 最少循环0次 最多循环n次 如i的各种取值概率相同 则平均循环次数为n 2 删除时最少的循环次数为0次 最多为n 1次 当i取值概率相同时 平均循环次数为 n 1 2 用数量级的形式表示线性表插入 删除运算的时间复杂性均为O n 数据结构 链表 第三章链表 链表 知识点单链表的结点形式 组织方法和特点单链表的基本运算和相应的算法循环链表的组织方法和基本运算算法双链表的结点形式 组织方法和特点双链表的基本运算和相应的算法顺序表与链表比较 各自的优 缺点链表的应用用十字链表表示稀疏矩阵 第三章链表 难点双链表插入 删除运算的算法利用链接结构的特点设计有效算法 解决与链表结构相关的应用问题要求熟练掌握以下内容 单链表的结构特点 基本运算并能设计简单算法循环链表的结构特点 基本运算并能设计简单算法双链表的结构特点 基本运算并能设计简单算法了解以下内容 用十字链表表示稀疏矩阵链接堆栈 链接队列的应用以及一元多项式加法的应用实例 第三章链表 第三章目录 3 1单链表及其运算3 2循环链表与双向链表3 3链表应用举例3 4表示稀疏矩阵的十字链表3 5应用举例及分析小结习题与练习 第三章链表 3 1 1单链表 1 结点 在链式存储结构中 结点不仅存放数据元素的值 还附加一个指针 链 用来指向该结点的直接后继结点 其中 data部分称为数据域 用于存储线性表的一个元素 next部分称为指针域或链域 用于存放一个指针 即存放该结点的直接后继结点的地址 第三章链表 2 单链表 所有结点通过指针的链接而构成的线性表称为单链表 线性表 a1 a2 an 的单链表可直观地画成 head是单链表的头指针 指向开始结点a1 an是终端结点 其指针域为空 不指向任何结点 一个单链表由头指针head唯一标识和确定 因此 可用头指针来命名单链表 第三章链表 单链表的特点 链表中每个结点只包含一个指针域 整个链表的存取必须从头指针head开始进行 头指针表示链表中第一个结点的存储位置 第三章链表 3 单链表的类型定义 假设线性表中数据元素的类型为datatype 单链表的类型定义如下 structnode datatypedata structnode next ListNode typedefListNode linklist 一个结点是由两个域data和next组成的记录 data是结点的数据域 next是结点的链域 第三章链表 4 指针的概念 假设p是一个pointer类型 应正确区分指针型变量 指针 指针所指的结点和结点的内容这四个密切相关的不同概念 p的值 如果有的话 是一个指针 即是一个所指结点的地址 该指针 若不是NULL 指向的某个node型结点用 p来标识 结点 p是由两个域组成的记录 这两个域分别用p data域和p next域来标识 它们各有自己的值 p data的值是一个数据元素 p next的值是一个指针 第三章链表 3 1 2单链表的基本运算 1 遍历 Traversal 根据已给的表头指针 按由前向后的次序访问单链表的各个结点 在实际应用中遍历是对单链表的最基本运算 例如 当要打印或显示出各个结点的数值域值 计算单链表的长度 即结点数目 或寻找某一个结点时都需要遍历单链表 假设head是单链表的头指针 计算一个已建立好的单链表的结点个数的算法如下 第三章链表 计算结点个数算法 intlength node head 求表head的长度 intcount 0 计数器置初值 node p head p指向头结点 while p NULL p p next count return count 返回表长值 第三章链表 算法分析 此算法的关键是while循环语句 开始时p指针指向头结点 每一循环都修改指针值 让它指向下一个结点 同时将计数链表长度的变量count加1 这样每循环一次就向后推移一个结点 直到p所指结点 p的链域值为NULL为止 空指针NULL起标志的作用 若无此标志 尾结点链域的值为 无定义 上述算法中的while语句在做最后一次判断时将出现 运行错 这是应予避免的 第三章链表 2 插入 所谓插入是指在单链表中第i个结点 i 0 之后插入一个元素为x的结点 实现插入算法主要完成三个基本操作 1 在单链表上找到插入位置 即找到第i个结点 可以用遍历的方法 即从表头起顺次访问单链表的结点 直至找到第i个结点 2 生成一个以x为值的新结点 可通过C的库函数malloc size 来产生 3 将新结点链入单链表中 需要改变相关结点的指针 如下面的图所示 第三章链表 假设指针p指向单链表中的第i个结点 指针s指向已生成的新结点 链入新结点的操作如下 将新结点 s的链域指向结点 p的后继结点 即s next p next 将结点 p的链域指向新结点 即p next s 第三章链表 插入算法 voidinsert node head inti x node s p intj s node malloc sizeof node 生成新结点 s data x if i 0 如果i 0 则将s所指结点插入到表头 s next NULL head s else p head j 1 查找第i个结点 由p所指向 第三章链表 插入算法续 while p NULL 第三章链表 3 删除 当需要从单链表上删除结点时 就要通过删除运算来完成 删除单链表上一个其值为x的结点的主要操作是 1 用遍历的方法在单链表上找到该结点 2 从单链表上删除该结点 欲从单链表上删除一个结点 需修改该结点的前一个结点的指针 如下面的图所示 第三章链表 假设指针q指向待删除结点的前一个结点 指针p指向要删除的结点 删除该结点的操作如下 将该结点的前一个结点 q的链域指向 p的后继结点 即q next p next 第三章链表 删除算法 voiddelete node head intx node p q if head NULL printf 链表下溢 n 判空 if head data x 如表头结点值等于x p head head head next free p else q head 从第二个结点开始查找 p head next 第三章链表 删除算法续 while p NULL 返回 第三章链表 3 2 1循环链表 循环链表 circularlinkedlist 是一种首尾相接的链表 将单链表表尾结点原来的空指针改为指向表头结点 就成为循环链表 循环链表并不多占存储单元 但从循环链表的任一个结点出发都可以访问到此链表的每一个结点 因为当访问到表尾结点后又能返回到头结点 第三章链表 1 带头指针的循环链表 通常在循环链表的表头结点前面再加一个空结点 也叫空表头结点 表空时空表头结点的指针指向其本身 如下面的图所示为空循环链表 空表头结点除指针以外的数据域是没有用的 但为了将此结点与一般结点相区别 常常是将其赋以一个特别的数据 以与一般结点相区别 第三章链表 思考 在循环链表和单链表中 当需要从头到尾扫描整个链表时 如何判断已经到达表尾了 两者有什么差异 第三章链表 2 带尾指针的循环链表 另一种方法是不设头指针而改设尾指针 这样无论是找头结点还是尾结点都很方便 因为尾结点由尾指针rear来指示 则头结点的位置是rear next next 第三章链表 3 2 2双链表 双向链表中每个结点除了有向后指针外 还有指向其前一个结点的指针 这样形成的链表中有两条不同方向的链 因此从某一结点均可向两个方向访问 双链表的结点形式为 其中链域prior和next分别指向本结点的直接前趋和直接后继结点 第三章链表 如果循环链表的结点再采用双向指针 就成为双向循环链表 第三章链表 双链表较单链表虽然要多占用一些存储单元 但对其插入和删除操作以及查找结点的前趋和后继都非常方便 双链表结构是一种对称结构 设指针p指向双链表的某一结点 则双链表的对称性可用下式来表示 p p prior next p next prior即结点 p的地址既存放在其前趋结点 p prior 的后继指针域中 又存放在它的后继结点 p next 的前趋指针域中 第三章链表 1 双链表的插入 设要在p所指结点的前面插入一个新结点 q 则需要修改4个指针 q prior p prior q next p p prior next q p prior q 第三章链表 2 双链表的删除 设p指向待删除的结点 则删除该结点步骤为 p prior next p next p next prior p prior 这两个语句的执行顺序可以颠倒 执行这两个语句之后 可调用free p 将 p结点释放 返回 第三章链表 例1 有一个单链表L 至少有一个结点 其头结点指针为head 编写一个函数将L逆置 即最后一个结点变成第1个结点 原来倒数第二个结点变成第二个结点 如此等等 解 本题采用的算法是 从头到尾遍历单链表L 并设置3个附加指针p q r p指向当前处理的结点 q指向p的下一个结点 r指向q的下一个结点 q r的作用是为了防止倒置指针时 下一个结点的丢失而设置的 有了这三个指针 就可以方便地实现指针的倒置 最后将第一个结点的next域置为NULL 并将头指针指向最后一个结点 这样达到了本题的要求 第三章链表 例3 1算法 voidinvert node head node p q r p head q p next while q NULL 没有后继时停止 r q next q next p p q q r head next NULL head p 第三章链表 例2 有两个循环单链表 头指针分为head1和head2 编写函数将链表head2链接到链表head1之后 链接后的链表仍保持是循环链表的形式 解 先分别找到两个链表的表尾 将head2放入链表head1的表尾 将两个链表链接起来 然后将head1放入原head2链表的表尾 构成新的循环链表 第三章链表 例3 2算法 link node head1 head2 node p q p head1 while p next head1 p p next q head2 while q next head2 q q next p next head2 q next head1 第三章链表 例3 给出在双链表中第i个结点 i 0 之后插入一个元素为x的结点的函数 解 在前面双链表一节中 已经给出了在一个结点之前插入一个新结点的方法 在一个结点之后插入一个新结点的思想与前面是一样的 第三章链表 例3 3算法 voidinsert dnode head inti x dnode s p intj s dnode malloc sizeof dnode 建立一个待插入的结点 由s指向 s data x if i 0 如i 0 将s所指结点插入到表头后返回 s next head head prior s head s 第三章链表 例3 3算法续 else p head 查找第i个结点 由p指向 j 1 while p NULL if p NULL 若查找成功 把s插入到p之后 if p next NULL 若p是最后一个结点 则直接把s结点链入 第三章链表 例3 3算法续 p next s s next NULL s prior p else s next p next p