线性表.ppt

1 第2章线性表 2 1线性表的逻辑结构2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 4应用举例 2 例1 两个链表的归并 教材P31例 例2 一元多项式的计算 教材P39 43 例3 试用C或类C语言编写一个高效算法 将一循环单链表就地逆置 微软亚洲研究院去年来华科大招聘的笔试题 操作前 a1 a2 ai 1 ai ai 1 an 操作后 an ai 1 ai ai 1 a2 a1 3 分析 要想让an指向an 1 a2指向a1 一般有两种算法 替换法 扫描a1 an 将每个ai 1的指针域送入ai 1的指针域 实际上是链栈的概念 操作后 an ai 1 ai ai 1 a2 a1 思路 后继变前驱 思路 头部变尾部 插入法 扫描a1 an 将每个ai插入到链表首部即可 4 p head next 有头结点if p head q p next p next head p q 处理a1while p head 循环单链表 q p next 保存原后继p next head next head next p p q 准备处理下一结点 q head p head next 有头结点while p head 循环单链表 r p next p next q 前驱变后继q p p r 准备处理下一结点head next q 以an为首 替换法的核心语句 插入法的核心语句 请上机验证并分析效率 5 就地逆置程序段的改进 主程序被降到8行 因为对空表的检测可以不要 q head Next 有头结点pCur q Next q Next List head 第一结点处理while pCur List head 空表或只有一个结点均会跳过 q pCur Next 保存原后继pCur Next head Next head Next pCur pCur q 6 例4 试用C或类C语言编写一高效算法 将一顺序存储的线性表 设元素均为整型量 中所有零元素向表尾集中 其他元素则顺序向表头方向集中 深圳华为公司去年来华科大招聘面试题 常见做法 从前往后扫描 见到0元素则与尾部非0元素互换 从后往前扫描 见到0元素则后面元素统统前移 从前往后扫描 见到0元素先计数 再将后续的一个非0元素前移 全部扫完后再把后续部分 长度为0元素的个数 清0 a1 a2 ai 1 ai ai 1 an 7 解 voidSortA sqlist 表的后部补0return ok SortA 若表完全不空 也要移动n次 8 解 voidSortA sqlist 表的后部补0return ok 若考虑表完全非空的情况 则程序要变长很多 9 例5 若某种高级语言没有指针类型 能否实现链式存储和运算 如何实现 答 能 虽然链表通常用动态级联方式存储 但也可以用一片连续空间 一维数组 实现链式存储 这种方式称为静态链表 具体实现方法 定义一个结构型数组 每个元素都含有数据域和指示域 就可以完全描述链表 指示域就相当于动态链表中的指针 指示域也常称为 游标 10 动态链表样式 静态链表样式 数组中每个元素都至少有两个分量 属于结构型数组 常用于无指针类型的高级语言中 11 静态单链表的类型定义如下 defineMAXSIZE1000 预分配最大的元素个数 连续空间typedefstruct ElemTypedata 数据域intcur 指示域 component SLinkList MAXSIZE 这是一维结构型数组 前例1 软考题 L 23 17 47 05 31 若此分量定义为指针型 属于动态链表 题目中是指针 若此分量定义为整型 通常存放下标 则属于静态链表 12 前例2 一线性表S ZHAO QIAN SUN LI ZHOU WU 用静态链表如何表示 教材P32例题 data 0123456 1000 cur 说明1 假设S为SLinkList型变量 则S MAXSIZE 为一个静态链表 S 0 cur则表示第1个结点在数组中的位置 说明2 如果数组的第i个分量表示链表的第k个结点 则 S i data表示第k个结点的数据 S i cur表示第k 1个结点 即k的直接后继 的位置 i 头结点 13 说明3 静态链表的插入与删除操作与普通链表一样 不需要移动元素 只需修改指示器就可以了 例如 在线性表S ZHAO QIAN SUN LI ZHOU WU 的QIAN SUN之间插入新元素LIU 可以这样实现 S 7 cur S 3 cur Step2 将QIAN的游标换为新元素LIU的下标 S 3 cur 7 Step1 将QIAN的游标值存入LIU的游标中 头结点 LIU 6 7 7 14 例6 在双向链表中如何实现插入和删除运算 单链表中查找只能从前往后 而不能从后往前查 为了查找方便 提高查找速度 可以在结点上增加一个指针域 用来存结点的直接前驱 这样的链表 称为双向链表 其结点的结构为 typedefstructDuLNode ElemTypedata 数据域structDuLNode prior 前驱指针域structDuLNode next 后继指针域 DuLNode DuLinkList 双向链表类型的定义如下 15 双向链表的插入操作 设p已指向第i元素 请在第i元素前插入元素x ai 1的后继从ai 指针是p 变为x 指针是s s next p p prior next s ai的前驱从ai 1 指针是p prior 变为x 指针是s s prior p prior p prior s 注意 要修改双向指针 指针域的变化 16 指针域的变化 后继方向 ai 1的后继由ai 指针p 变为ai 1 指针p next p prior next p next 前驱方向 ai 1的前驱由ai 指针p 变为ai 1 指针p prior p next prior p prior 双向链表的删除操作 设p指向第i个元素 删除第i个元素 注意 要修改双向指针 17 本章小结 线性结构 包括表 栈 队 数组 的定义和特点 仅一个首 尾结点 其余元素仅一个直接前驱和一个直接后继 2 线性表 逻辑结构 一对一 或 1 1 存储结构 顺序 链式运算 修改 插入 删除 查找和排序另述 3 顺序存储 特征 逻辑上相邻 物理上也相邻 优点 随机查找修改快O 1 缺点 插入 删除慢O n 改进方案 链表存储结构 18 循环链表的特点 从任一结点出发均可找到表中其他结点 双向链表的特点 可方便找到任一结点的前驱 静态链表的特点 不用指针也能实现链式存储和运算 4 链式存储 特征 逻辑上相邻 物理上未必相邻 优点 插入 删除快O 1 缺点 随机查找修改慢O n 5 几种特殊链表的特点 19 讨论1 顺序存储和链式存储的区别和优缺点 顺序存储时 逻辑上相邻的数据元素 其物理存放地址也相邻 顺序存储的优点是存储密度大 存储空间利用率高 缺点是插入或删除元素时不方便 链式存储时 相邻数据元素可随意存放 但所占存储空间分两部分 一部分存放结点值 另一部分存放表示结点间关系的指针 链式存储的优点是插入或删除元素时很方便 使用灵活 缺点是存储密度小 存储空间利用率低 顺序表适宜于做查找这样的静态操作 链表宜于做插入 删除这样的动态操作 若线性表的长度变化不大 且其主要操作是查找 则采用顺序表 若线性表的长度变化较大 且其主要操作是插入 删除操作 则采用链表 20 讨论2 什么是指针 指针的作用 指针 即变量的内存地址 指针主要功能有二 提供了一种快速访问数组单元的途径 使C语言函数可以修改其调用的参数 指针操作符 单目 返回操作数地址 运算符 单目 是对 的补充 返回位于这个地址内的变量之值 例 q m意即 q取地址m中的值 如果数值100存储在内存地址2000中 而这一地址又存在m中 则q 2000 100 讨论3 与指针有关的符号 和 之间有何区别 21 P43程序中 switch cmp a b 的cmp a b 一定是个特殊变量 它的值是一个内存地址 而 1 0 1这三种可能的执行结果会放入该地址中 所存结果再由 cmp来寻址 那么 P42定义为intcmp a b 又怎么理解 意即cmp中地址 指针 存储的是一个整型变量 讨论4 P43程序中 switch cmp a b 的意思 22 例1 第1章自测卷 写出下面C程序段的执行结果 运行结果为 5 120 longintfact n intn longf if n 1 f n fact n 1 elsef 1 return f main intn longy n 5 y fact n printf d ld n n y 此题为递归运算N 一个直接或间接调用自身的函数被称为是递归 recursion 的 什么叫递归 补充 递归概念及算法实现 23 编制递归算法要注意些什么 递归进行是有条件的 一般常把判断语句加在递归语句以前 递归的最底层应该有返回值 以供上层递归的调用 否则会死循环 递归调用需要利用堆栈 参量的初始化应该在递归以前 每次调用要把本次调用的参数和局部变量保存在栈顶 每次从下一层调用返回到上一层调用时 从栈顶恢复本层调用的参数和局部变量的值 24 例2 设正整数a的前驱为PRIOR a 后继为NEXT a 用递归算法计算a b 平常我们可以用循环来实现 但根据本题题意不能用循环 而要用递归 设计要点有二 递归算法的形式化描述 不能无限制递归 一定要有终止条件 a b a b 0 PRIOR a NEXT a a可视为一减计数器 前移过程中不断递减 而b的后移则是不断加1的过程 清华考研题 解 首先要对加法算法进行恰当的描述 肯定不能用简单的加法语句 要考虑如何用给出的两个特定函数来实现a b 思路 若用数轴来描述a b 是两条线段之和 也可以看作是a不断往 0 移动 b不断往相反方向移动的过程 当a移到0时 b指向的位置即为a b 25 有冗余 在递归开始之前判断一次足矣 速度