数据结构教程第2章线性表ppt课件.ppt

第二章线性表 Chapter2LinearList 1 数据结构课程 涉及数学 计算机硬件和软件数据结构定义 指相互有关联的数据元素的集合 用D S D R 表示数据结构内容 数据的逻辑结构 存储结构和运算算法效率指标 时间效率和空间效率 要点回顾 2 逻辑结构唯一 存储结构不唯一 运算的实现依赖于存储结构 3 线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构 单链表 应用实例 本章内容 4 若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前趋和一个直接后继 可表示为 a0 a1 an 1 线性结构的定义 线性结构的特点 只有一个首结点和一个尾结点 除首尾结点外 其他结点只有一个直接前驱和一个直接后继 线性结构包括线性表 堆栈 队列 字符串 数组等等 其中 最典型最常用的是 5 a0 a1 ai 1 ai ai 1 an 1 2 1线性表的逻辑结构 1 线性表的定义 用数据元素的有限序列表示 n 0时称为 数据元素 线性起点 首结点 ai的直接前趋 ai的直接后继 下标 是元素的序号 表示元素在表中的位置 空表 线性终点 尾结点 n为元素总个数 即表长 6 例1分析26个英文字母组成的英文表 A B C D Z 例2分析学生情况登记表 每个数据元素由5个数据项组成 元素之间的关系是线性的 数据元素都是字母 元素之间的关系是线性的 同一线性表中的元素必定具有相同特性 7 2 线性表的基本操作Initiate L 初始化操作 建立一个空线性表L Length L 求表长 求给定线性表L中数据元素的个数 Get L i 读取元素 读取线性表L中第i个数据元素 Insert L i x 前插 在线性表L中第i个数据元素ai之前插入一个新的数据元素x Delete L i x 删除 删除线性表L中第i个的数据元素 并将其保存在x中 Locate L x 定位函数 返回线性表L中元素值等于x的数据元素ai的序号i 8 2 2线性表的顺序存储结构 顺序表 一 顺序表用一组地址连续的存储单元存储线性表的各个数据元素 称作线性表的顺序存储结构 简称顺序表 顺序表的特点 1 逻辑上相邻的数据元素 其物理上也相邻 2 若已知表中首元素在存储器中的位置 则其他元素存放位置亦可求出 利用数组下标 参见存储结构示意图 9 线性表的顺序存储结构示意图 每个元素占K字节 10 一个线性表 数据元素M下标的范围是 到 每个数据元素用相邻的 个字节存储 设存结点 的第一个字节的地址是98 则 的第一个字节的地址是 113 例1 因此 LOC M 3 98 5 3 113 解 地址计算通式为 LOC ai LOC a0 L i 11 用c语言定义顺序表 defineMaxlen100typedefstruct charname 10 charsex 3 intage elemtype elemtypeList Maxlen intnum 0 定义数据类型 定义顺序表 顺序表的长度 顺序表最大长度 12 typedefstruct elemtypeList Maxlen intnum SeqList L num L List 0 L List 1 L List 2 L List Maxlen 1 SeqLista SeqList L a num a List 0 用c语言定义顺序表 13 二 顺序表的基本操作 1 初始化ListInitiate L voidListInitiate SeqList L L num 0 num表示顺序表的长度 或结点个数 14 2 求表长ListLength L intListLength SeqListL returnL num 3 取数据元素ListGet L i x intListGet SeqListL inti elemtype x if iL num 1 printf ERROR n return0 else x L List i return1 15 4 插入 在第i个 0 i num 数据元素之前插入一个新的数据元素x a0 a1 ai 1 01 i 1ii 1 n 1 Maxlen 1 an 1 ai 1 ai x 16 i位置非法 开始 n 1至i位置的元素依次后移 N Y N Y 前插算法流程图 是否满足0 i num num Maxlen是否成立 for j num j i j a j 1 a j a i x num 注意 n表示数据元素的个数 num是线性表的长度 增强健壮性 17 intListInsert SeqList L inti elemtypex intj if iL num printf error n return0 if L num Maxlen printf overflow n return0 for j L num 1 j i j L list j 1 L List j L List i x L num L num 1 return1 判断i是否合法 判断表是否已满 若i合法 元素后移 将元素x存放在i位置 当前数据元素下标加1 用c语言描述插入算法 18 该算法的时间复杂度 Eis 插入一个元素所需平均移动次数 则因此 该算法的时间复杂度为O n 19 5 删除 删除第i个 0 i num 1 数据元素 并将其保存在x中 a0 a1 ai 1 01 i 1ii 1 n 1 Maxlen 1 an 1 ai 1 ai ai 20 删除算法流程图 位置非法 N Y 表空 Y for j i 1 j num 1 j a j 1 a j num 判断num 0是否成立 是否满足0 i num 1 N 21 用c语言描述删除算法 intListDelete SeqList L inti elemtype x intj if L numL num 1 printf nthepositionisinvalid return0 else x L list i for j i 1 jnum 1 j L list j 1 L list j L num return1 删除顺序表L中的第i个元素 并将其保存在x中 判断表是否为空 若i合法 元素依次前移 表长减1 判断i值是否合法 22 该算法的时间复杂度 Edl 删除一个元素所需平均移动次数因此 该算法的时间复杂度为O n 23 算法时间主要耗费在移动元素的操作上 因此计算时间复杂度的基本操作 最深层语句频度 T n O 移动元素次数 平均时间复杂度T n O n 移动元素的个数取决于插入或删除元素的位置 顺序表时间效率分析 顺序表的空间复杂度S n O 1 没有占用辅助空间 顺序表空间效率分析 24 三 顺序存储结构的特点 顺序表的优点 无需为表示数据元素间的逻辑关系而增加额外的存储空间可以方便地随机存取表中的任一数据元素顺序表的缺点 插入和删除运算不方便 需要移动大量的数据元素 由于要求占用连续的存储空间 存储分配只能预先进行 作业 编写顺序表的删除操作算法ListDeleteMore L x 要求删除线性表L中所有等于x的数据元素 如何克服顺序表的这些缺点呢 25 第二章线性表 线性结构的特点 仅有一个首 尾结点 除首 尾结点外 其余元素都仅有一个直接前驱和一个直接后继 2 线性表 逻辑结构 一对一 或1 1存储结构 顺序存储 链式存储 3 顺序表 特征 逻辑上相邻 物理上一定相邻优点 随机查找快缺点 插入 删除慢 O n 需要预先知道线性表的长度 26 单链表基本概念单链表基本操作 线性表的链式存储结构 链表 27 单链表的基本概念 线性表链式存储结构的一种 用一组不一定连续的存储单元来存放数据元素 数据域 指针域 结点 头指针 空指针 a0 1475 130A a1 10CB 1475 a2 10CB 数据元素的逻辑顺序是通过链表中的指针连接次序来实现的 28 结点 数据域 指针域 typedefstructNode DataTypedata structNode next SLNode 2 3 1单链表的存储结构 29 不带头结点的单链表 不带头结点的空单链表 head NULL 头指针 首元结点 带头结点的单链表 带头结点的空单链表 head next NULL 头指针 头结点 首元结点 30 何谓头指针 头结点和首元结点 头指针是指向链表中第一个结点 或为头结点或为首元结点 的指针 单链表可由一个头指针唯一确定 头结点是在链表的首元结点之前附设的一个结点 数据域内只放空表标志和表长等信息 首元结点是指链表中存储线性表第一个数据元素a0的结点 首元结点 a0 31 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其头指针的值是多少 例 答 头指针是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 31 头指针的值是31 32 上例链表的逻辑结构示意图有以下两种形式 区别 无头结点 有头结点 33 相关知识 动态内存分配 设计人员根据具体问题的具体需要 在程序运行时再具体确定数组的个数或占用内存单元的大小 从而在程序运行时具体确定所需要的内存单元空间 malloc 函数 free 函数 头文件malloc h include 34 malloc 函数 free 函数 函数原型 void malloc unsignedsize 函数功能 用于向系统动态申请size个字节的内存单元空间 函数返回值为所申请的内存空间首地址 函数原型 voidfree void p 函数功能 用于释放动态分配的内存空间 sizeof运算符 sizeof 已定义的数据类型 功能 返回括号中给出的已定义数据类型占用的字节个数 MemoryAllocation 如 sizeof int 35 例如 定义结构体类型typedefstructnodetype intdata structnodetype next SLNode p SLNode malloc sizeof SLNode SLNode p p malloc sizeof SLNode 强制类型转换 36 1 指针后移操作p p next 1475 2 指向指针的指针SLNode h 130A h h 1000 h 1000 一级指针 二级指针 37 intListInitiate SLNode head if head SLNode malloc sizeof SLNode NULL return0 head next NULL return1 1 初始化 2 3 2单链表的操作实现 12EF head head NULL main SLNode h ListInitiate 头结点 12EF 38 2 求当前数据元素个数 intListLength SLNode head SLNode p head intsize 0 while p next NULL p p next size returnsize 39 3 取元素 寻找到第i个结点ai并返回该结点的数据元素 p p next j while p next NULL j i x p data 40 intListGet SLNode head inti DataType x SLNode p intj 0 p head while p next NULL 找第i个结点 判断是否找到该结点 将数据元素值赋给 x 41 步骤 1 找插入位置 指针p指向ai的前一个结点 即ai 1 2 申请新结点s 将其数据域的值置为x 3 插入 1 s结点指针域指向ai结点2 ai 1结点的指针域指向s结点 2 3 1 3 2 4 插入运算 在ai 0 i n 之前插入一个数据元素x 不可以 3 1 和 3 2 可不可以交换 为什么 42 p p next j while p next NULL j i 1 x p next s 1614 10CB s next p next s data x s SLNode malloc sizeof SLNode 43 intListInsert SLNode head inti DataTypex SLNode p s intj p head j 1 while p next NULL 用c语言实现的单链表插入算法 定义变量并初始化 搜索表 寻找ai 1结点 44 if j i 1 printf n插入位置不合理 return0 if s SLNode malloc sizeof SLNode NULL return0 s data x s next p next p next s return1 插入位置不合理 判断是否申请到新结点 将该结点插入到ai结点之前 45 要点回顾 线性表的链式存储 链表 单链表结点 数据域 指针域 单链表的初始化 插入 删除 头插法及尾插法创建单链表 46 intListInsert SLNode head inti DataTypex SLNode p s intj p head j 1 while p next NULL 用c语言实现的单链表插入算法 定义变量并初始化 搜索表 寻找ai 1结点 47 if j i 1 printf n插入位置不合理 return0 if s SLNode malloc sizeof SLNode NULL return0 s data x s next p next p next s return1 插入位置不合理 判断是否申请到新结点 将该结点插入到ai结点之前 48 5 单链表的删除 删除第i 0 i n 1 个结点 1500 s p next p next s next free s p p next j while p next NULL p next next NULL j i 1 49 ListDelete SLNode head inti DataType x SLNode p s intj p head j 0 while p next NULL 用c语言实现的单链表删除算法 定义变量并初始化 搜索表 寻找ai 1结点 50 if j i 1 printf n删除位置不合理 return0 s p next x s data p next p next next free s return1 删除位置不合理 将ai结点删除 释放s结点空间 51 作业 编写单链表的删除操作算法ListDeleteMore L x 要求删除线性表L中所有等于x的数据元素 52 6 单链表的创建 尾接法 130A 1475 for j 0 jdata a j s next NULL p next s p s 53 开始 N Y 尾接法创建单链表流程图 54 intCreatL1 SLNode h DataTypea intn SLNode p s inti j i ListInitiate h if i 0 return0 p h for j 0 jdata a j s next NULL p next s p s return1 55 a0 NULL 130A a1 130A 1475 for j 0 jdata a j s next h next h next s 6 单链表的创建 头插法 56 开始 N Y 头插法创建单链表流程图 57 intCreatL2 SLNode h DataTypea intn SLNode s inti j i ListInitiate h if i 0 return0 for j 0 jdata a j s next h next h next s return1 58 2 3 5循环单链表 非空表 空表 head next head 59 2 3 6双向循环链表 typedefstructNode DataTypedata structNode prior next DLNode 60 讨论 线性表逻辑结构特点是 只有一个首结点和尾结点 除首尾结点外其他结点只有一个直接前驱和一个直接后继 简言之 线性结构反映结点间的逻辑关系是一对一 1 1 的 问1 线性表的逻辑结构特点是什么 其顺序存储结构和链式存储结构的特点分别是什么 答 顺序存储时 相邻数据元素的存放地址也相邻 逻辑结构与物理结构统一 要求内存中可用存储单元的地址必须是连续的 链式存储时 相邻数据元素可随意存放 但所占存储空间分两部分 一部分存放结点值 另一部分存放表示结点间关系的指针 61 顺序存储的优点是存储密度大 1 存储空间利用率高 缺点是插入或删除元素时不方便 链式存储的优点是插入或删除元素时很方便 使用灵活 缺点是存储密度小 1 存储空间利用率低 答 问2 顺序存储和链式存储各有哪些优缺点 事实上 链表插入 删除运算的快捷是以空间代价来换取时间 讨论 62 顺序表适宜于做查找这样的静态操作 链表宜于做插入 删除这样的动态操作 若线性表的长度变化不大 且其主要操作是查找 则采用顺序表 若线性表的长度变化较大 且其主要操作是插入 删除操作 则采用链表 答 问3 如何选择顺序存储还是链式存储 讨论 63 64 应用实例1 删除顺序表la中所有值为x的数据元素 设顺序表的数据结构定义为 defineMAX100typedefintDataType typedefstruct DataTypeList MAX intnum 最后一个数据元素的下标 SeqList 65 voidDeleteSeqList SeqList la DataTypex intj k for j 0 jnum j if la List j x for k j knum k la List k la List k 1 la num j 66 删除顺序表a中第i i 0 个元素起的k个元素 defineMAX100typedefintDataType typedefstruct DataTypeList MAX intnum 最后一个数据元素的下标 SeqList 应用实例1 67 intDeleteK SeqList a inti intk intj if a numa num return0 else for j i jnum k j a List j a List j k a num a num k return1 判断表是否为空 判断删除位置 个数是否合理 删除从第i个元素开始的k个元素 68 在有序顺序表 递增 中插入值为x的数据元素以保持顺序表的有序性 defineMAX100typedefintDataType typedefstruct DataTypeList MAX intnum 最后一个数据元素的下标 SeqList 应用实例2 69 intOrderlnsert SeqList L DataTypex inti if L num MAX 1 printf 顺序表已满 return0 else for i L num i 0 70 实现单链表的就地逆序 设其头结点的指针为head 编写一个算法将单链表逆置 应用实例3 typedefstructnode DataTypedata structnode next SLNode 71 单链表的就地逆置 p q q q p p p 72 voidreverse SLNode head SLNode p q p head next head next NULL while p NULL q p p p next q next head next head next q 73 已知线性表la和lb中的数据元素按非递减有序排列 将la和lb表中的数据元素合并为一个新的线性表lc lc中的数据元素仍按非递减有序排列 并要求不破坏la和lb表 例如 La 3 5 8 11 Lb 2 6 8 9 11 15 20 合并结果为Lc 2 3 5 6 8 8 9 11 11 15 20 应用实例5 74 typedefstruct DataTypeList Maxlen intnum qltype 方法一 采用顺序表结构 75 intmergeql qltypela qltypelb qltype lc inti j k if la num 1 lb num 1 Maxlen printf n数组下界溢出 return0 i j k 0 while ilist k la list i elselc list k lb list j 76 while ilist k la list i while jlist k lb list j lc num k 1 return1 77 typedefstructnode DataTypedata structnode next slnode 方法二 采用单链表结构 78 La Pa Pb用于搜索La和Lb Pc指向新链表当前结点 79 intmergesl slnode la slnode lb slnode lc