复习课1上海交通大学继续教育学院ppt课件.ppt

数据结构学位考复习课 1 主要内容 1 第一部分概述2 第二部分线性表 栈 队列 第一部分 数据结构与算法的基本概念 考核内容及要求 理解算法 算法正确性 复杂性的概念 了解算法的时间与空间复杂性级别 重点掌握数据类型 数据结构和表示 实现的概念 掌握抽象数据类型的说明 高级语言对抽象数据类型的支持 基本概念和术语 数据 Data 数据元素 DataElement 数据的基本单位 计算机中通常作为一个整体来考虑 如一棵树中的一个结点 一个图中的一个结点 一个数据元素可以有若干个数据项 DataItem 组成 数据对象 DataObject 性质相同的数据元素的集合数据结构 数据元素之间的关系 结构四种基本结构集合线性结构树形结构图状结构 网状结构数据结构的形式定义 一个二元组 Data Structure D S 其中 D是数据元素的集合 S是D上的关系集合 数据的逻辑 物理 存储 结构逻辑结构 数据元素之间的逻辑关系物理结构 数据元素在计算机中的存储方法 表现和实现 数据结构的分类 按照逻辑结构的不同分为 集合 线性结构 树状结构 网状结构按照物理结构的不同分为 顺序结构 利用在存储器中的物理关系来表示逻辑关系 链式结构 用在存储器中附加指针的方式来表示逻辑关系 算法 对特定问题求解步骤的一种描述 是指令的有序序列算法的五个特性 有穷性 确定性 可行性 输入 输出算法设计的要求 时间复杂度 空间复杂度 时间复杂度 算法执行时间随规模增长而增长的趋势T n O f n f n 算法规模 T n 称算法复杂度估算办法 以算法中重复执行的次数作为算法时间复杂度的依据 三种最常见时间复杂度 O 1 常量级O n 线性级O n2 平方级 算法的空间复杂度S n O f n 算法执行过程中所需的最大空间估算方法 输入数据所占空间 程序所占空间 辅助变量所占空间 第二部分线性表 栈 队列 考核内容及要求 熟练掌握顺序分配 链接分配的表示及实现方法 熟练掌握各种链表 单链 双链 多链 循环链表 理解栈 队列 双向队列的顺序 链式表示及其算法复杂度分析 熟练掌握表达式计算原理 1 线性表的顺序表示和实现 线性表的存储结构 顺序存储 链接存储顺序存储 用一组地址连续的存储单元依次存储线性表的数据元素 顺序表的特点 1 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系 即线性表的逻辑结构于存储结构 物理结构 一致 2 在访问线性表时 可以利用上述给出的数学公式 快速计算任何一个数据元素的存储地址 即访问每个数据元素所花费的时间相等 3 这种存取元素的方法被称为随机存取法 使用这种存取方法的存储结构被称为随机存储结构 表示方法 在高级语言中 用一维数组表示 表示方法 constLIST INIT SIZE 100 表初始分配空间constLISTINCREMENT 10 空间分配增量typedefstruct ElemType elem 存储空间intlength 当前长度intlistsize 当前存储容量intLISTINCREMENT 可增加存储空间 SqList 注意 1 数组指针elem指示线性表的基地址 length 线性表的当前长度 2 C语言数组的下标从0开始 即数组中的第i个元素为L elem i 1 2 线性表的链式表示和实现 顺序表的局限 插入 删除时要移动大量的元素 耗费大量时间 链式表示 用一组任意的存储单元存储线性表存储单元不要求连续 物理结构不反应逻辑结构不可以随机存取 但插入和删除方便需要两个域 一个表示数据本身 一个表示数据元素间的先后关联 一个结点 结点中表示关联的部分为指针域 内部存放指针或链 n个结点链接成一个链表 线性链表 线性链表的物理存储结构 Zhao Qian Sun Li Zhou Wu Zheng Wang 线性链表 单链表 的定义 typedefstructLNode ElemTypedata structLnode next Lnode LinkList 带头结点的链表 循环链表 循环链表 线性表的另一种链式存储结构 特点 从表的任何位置出发 都可以找到其他结点 操作与单链表的差别 判断表尾的条件 P next H 空表 循环链表 双向链表 每一个结点有两个指针域 一个指向直接后继 另一个指向直接前驱 双向链表存储结构 typedefstructDuLNode ElemTypedata structDuLNode prior structDuLNode next DuLNode DuLinkList 双向循环链表 2个结点的双向循环链表 空的双向循环链表 3 栈的表示和实现 栈的表示 1 顺序栈 栈的顺序存储 2 链栈 栈的动态存储 顺序栈的表示和实现顺序表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize SqStack 其中stacksize表示栈当前可以使用的最大容量 base为栈底 top为栈顶 栈顶指针指向栈顶元素的下一个位置 即下次压栈时元素所放的位置 顺序栈的结构 top指向压栈时下一个元素将要存放的位置 top减一指向弹栈时下一个元素的取值位置 栈空的条件 top base栈满的条件 top base stacksize top 链栈的结构和表示 定义栈结构Typedefstructstack node elemtypedata structstack node next STKPTR STKPTR stk 问 在这里为什么没有用到top指针 这样对栈结构的定义有否影响 栈顶 栈底 4 队列的表示和实现链式队列typedefstructQnode QElemTypedata structQnode next Qnode QueuePtr typedefstruct QueuePtrfront QueuePtrrear LinkQueue 课堂练习 链队列的操作入对列 出队列 链队列结构 顺序队列 defineMAXQSIZE100typedefstruct QElemType base intfront intrear SqQueue 其中base为连续空间首地址 front为队首 rear为队尾 为什么用循环队列来实现顺序队列 front 空队 C 满队 D E C front 非空非满队2 D rear rear front 顺序队列的结构 循环队列 空队 初始化队列时 两个指针rear front 0入队 队尾插入元素 尾指针rear后移出队 队头删除元素 头指针front后移 循环队列 实现循环队列的操作 关键问题1 rear和front指针后移 Q rear 1 modMAXSIZE Q front 1 modMAXSIZE Q rear指向入队时下一个元素的存放位置Q front指向出队时下一个元素的存放位置 关键问题2 出队时 判断空队Q rear Q front 入队时 判断满队 Q rear 1 modMAXSIZE Q front 空队列 满队列 典型例题 1 顺序表中逻辑上相邻的元素物理位置相邻 单链表中逻辑上相邻的元素物理位置相邻 2 已知P为单链表中的非首尾结点 在P结点后插入S结点的语句为 3 在单链表中 指针P所指的节点为最后一个节点的条件是 4 设head指向单链表的表头 p指向单链表的表尾结点 则执行p next head后 该单链表构成 P next NULL 循环链表 也 不一定 S next P next P next S 2 5画出执行下列各行语句后各指针及链表的示意图L LinkList malloc sizeof LNode P L for i 1 inext LinkList malloc sizeof LNode P P next P data i 2 1 P next NULL for i 4 i 1 i Ins LinkLIst L i 1 i 2 for i 1 i 3 i Del LinkList L i 2 8已知P结点是双向链表的中间结点 试写出下列操作的语句序列 1 在P结点后插入s结点 2 在P结点前插入s结点 3 删除P结点的直接后继结点 4 删除P结点的直接前驱结点 5 删除P结点 S next P next S prior P p next prior S P next S 2 S next P S prior P prior p prior next S P prior S 3 R P next P next R next R next prior R prior free R 4 R P prior P prior R prior R prior next R next free R 5 P prior next P next P next prior P prior free R 设rear是指向非空带头节点的单循环链表的尾指针 则写出删除表首结点的操作的语句序列 答案 P rear next next Rear next next p next Free P 2 33已知一个线性链表表示的线性表中含有三类字符的数据元素 如字母 数字 和其他 试编写算法将该线性链表分割为三个循环链表 其中每个循环链表表示的线性表中均只含一类字符 要求 充分用原来的存储空间 问题 如果要求建立3个单链表 也利用原来的存储空间 StatusD S 2 33 LinkList 使Lb为循环链表 2 22单链表的就地逆置 利用原来的存储空间 StatusD S 2 22 LinkList 答案 q next L next L next q 算法设计题 顺序表 defineLIST INIT SIZE100 defineLISTINCREMENT10typedefstruct ElemType elem intlength intlistsize SqList 单链表typedefstructLnode ElemTypedata StructLnode next Lnode LinkList 线性表类型定义 4 2 19 已知线性单链表中的元素以值递增有序排列 试写一个高效的算法 删除表中所有介于 mink maxk 的元素 mink maxk h o 查找第一个大于mink的结点P next P while P next datanext StatusLL DEL LinkList LL DEL mink maxk h o 5 2 24 假设有两个按值递增有序排列的单链表A和B 编写算法归并A和B成C 使得C是按值递减有序排列 允许有值重复的结点 并且C利用A B原来的结点空间 StatusUNIT A B LinkListC next s UNIT A B 栈与队列的相关习题 1 栈与线性表的差别2 队列与栈两种数据类型的相同点和差异3 3 4 分析以下算法的功能 SElemType为int Statusalgo1 StackS intI n A 255 n 0 while StackEmpty S n Pop S A n for i 1 i n i Push S A i 栈与队列 算法功能 将栈S中的元素逆置 2 Statusalgo2 StackS inte StackT intd InitStack T while StackEmpty S Pop S d if d e Push T d while StackEmpty T Pop T d Push S d 算法功能 删除栈S中与e相等的元素 4 3 13 简述下列算法的功能voidalgo3 Queue 算法功能 将队列Q中的元素逆置 类型定义 顺序栈 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base SElemType top intstacksize SqStack 算法设计题 顺序循环队列 defineMAXQSIZE100 typedefstruct QElemType base intfront intrear SqQueue 3 15假设以顺序存储结构实现一个双向栈 即在一维数组的存储空间中存在着两个栈 它们的栈底分别设在数组的两个端点 试编写实现这两个双向栈的操作的算法 初始化inistack tws 入栈push tws i x 出栈pop tws i 并讨论按过程或函数设计这些操作算法各有什么优缺点 分析 Length 100 Typedefstruct datatypedata Length inttop1 top2 Twins 初始化 还有最后一个存储空间 栈的一般状态 Pop twinstws inti ifi 0iftop1 0ERRORelsetop1 returntws data top1 ifi 1ifERRORelse top2 Length 1 top2 returntws data top2 5 3 17 试写一个算法 识别依次读入的一个以 为结束符的字符序列是否形如 序列1 序列2 模式的字符序列 其中序列1和序列2中都不含字符 且序列2是序列1的逆序列 如 a b b a 分析 算法中采用何种数据类型 线性表 栈 队列 a 初始化一个栈S b 依次读入字符 并压栈c 当字符为 时 依次读下面的字符 并与出栈元素比较 有一个不相等 则ERRORd 字符结束时 栈空 则OK 否则ERROR intsymmetry 使用栈 对读入的字符在 symmetry 6 3 28 假设以带头结点的循环链表表示队列 并且只设一个指针指向队尾元素结点 不设头指针 编写相应的队列初始化 入队和出队