数据结构讲解讲义课件

第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示和相加 2 1线性表的类型定义 一 线性表的定义线性表是一个由n n 0 个同类型的数据元素a1 a2 an组成的有限序列 通常记为 a1 a2 ai 1 ai ai 1 an 其中 数据元素的个数n为表的长度 当n 0时称为空表 这里的数据元素ai 1 i n 表示线性表中第i个数据元素 它可以是任意类型 2 1线性表的类型定义 例1 26个英文字母组成的字母表 A B C Z 是一个长度为26的线性表 例2 某公司2000年每月产值表 单位 万元 400 420 500 600 650 是一个长度为12的线性表 上述两例中的每一个数据元素都是不可分割的 在一些复杂的线性表中 每一个数据元素又可以由若干个数据项组成 2 1线性表的类型定义 例3 下图为10个学生的成绩表 它也是一个线性表 该线性表的数据元素类型为结构体 2 1线性表的类型定义 二 线性表的逻辑特征在非空的线性表中 有且仅有一个被称作 第一个 的数据元素a1 它没有直接前趋 而仅有一个直接后继a2 有且仅有一个被称作 最后一个 的数据元素an 它没有直接后继 而仅有一个直接前趋an 1 其余的数据元素ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 2 1线性表的类型定义 三 线性表的形式定义L List D R D ai ai ElemSet i 1 2 nn 0 R ai 1 ai D i 2 n ElemSet为某一数据对象集 即数据元素的集合 n为线性表的长度 2 1线性表的类型定义 四 线性表的主要操作 库函数中没有 需要用户自己实现 1 Initiate L 初始化 构造一个空的线性表L 2 Insert L i x 插入 在给定的线性表L中 在第i个元素之前插入数据元素x 线性表L长度加1 3 Delete L i 删除 在给定的线性表L中 删除第i个元素 线性表L的长度减1 4 Locate L x 查找定位 对给定的值x 若线性表L中存在一个元素ai与之相等 则返回该元素在线性表中的位置的序号i 否则返回 1 2 1线性表的类型定义 5 Length L 求长度 对给定的线性表L 返回线性表L的数据元素的个数 6 Get L i e 存取 对给定的线性表L 返回第i 1 i Length L 个数据元素e 7 Traverse L 遍历 对给定的线性表L 依次输出L的每一个数据元素 例 假设利用两个线性表LA和LB分别表示两个集合A和B 要求一个新的集合A A B voidunion List la中不存在和e相同的数据元素 则插入之 时间复杂度O la length lb length 例 已知线性表LA和LB中的数据元素按值非递减有序排列 要求将LA和LB归并为一个新的线性表LC 且LC中的数据元素仍按值非递减有序排列 voidMergeList Listla Listlb List 时间复杂度O la length lb length 2 2线性表的顺序表示和实现 一 线性表的顺序存储表示在计算机中 用一段地址连续的存储单元依次存储线性表的各个数据元素 称作线性表的顺序存储结构 用这种方法存储的线性表简称顺序表 线性表的顺序存储结构中的特点是 其逻辑关系上前后相邻的两个数据元素 在计算机中的存储位置也必定是相邻的 即ai 1一定存在ai的下一个存储单元中 线性表的顺序存储结构示意图如下 2 2线性表的顺序表示和实现 线性表的顺序存储结构示意图 2 2线性表的顺序表示和实现 由于线性表中每个数据元素的类型相同 占用的内存空间也相同 因此 假设线性表中的第一个数据元素的存储地址为Loc a1 设每一个数据元素占用d字节的内存空间 则线性表中第i个元素ai在这段连续的存储空间中的存储地址为 Loc ai Loc a1 i 1 d 2 2线性表的顺序表示和实现 1 线性表的静态分配顺序存储结构 defineMAXNUM100 定义顺序表最大元素个数 ElemTypeList MAXNUM 定义顺序表List 注意 ElemType代表线性表元素的类型 具体编程实现是要用int或char或float或者struct等类型来代替 intlength 定义线性表表长 我们还可将数组和表长封装在一个结构体中 structL list ElemTypeList MAXNUM 定义数组域 intlength 定义表长域 2 2线性表的顺序表示和实现 2 线性表的动态分配顺序存储结构 defineList Init Size100 defineListIncrement10typedefstructL List ElemType elem 存储空间基地址intlength 表长intlistsize 当前分配的存储容量 SqList SqListL 等价于structL ListL 2 2线性表的顺序表示和实现 分配存储空间函数malloc malloc 函数的原型为 void malloc unsignedintsize 函数的作用是在内存自由空间开辟一块大小为size字节的空间 并将此存储空间的起始地址作为函数值带回 例如 malloc 10 sizeof int 的结果是分配了一个长度为20个字节的内存空间 若系统设定的此内存空间的起始地址为1800 则其返回值就为1800 2 2线性表的顺序表示和实现 重新分配空间函数realloc 函数原型为 void realloc void ptr unsignedintsize 函数用于使已分配的空间改变大小 即重新分配 其作用是将ptr指向的存储区 是原先用malloc函数分配的 大小改为size个字节 可以使原先的分配区扩大也可以缩小 它的返回值是一个指针 即新的存储区的首地址 2 2线性表的顺序表示和实现 二 线性表 动态分配顺序存储 的运算1 构造一个空线性表 申请连续的存储空间 准备存放线性表的各个数据元素 其算法如下 voidInitList Sq SqList L L elem ElemType malloc List Init Size sizeof ElemType if L elem Printf Mallocfail Trylater exit 0 L length 0 L listsize List Init Size 2 2线性表的顺序表示和实现 2 顺序表的查找算法在顺序表中查找一个值为x的数据元素 从第一个元素开始 依次和x进行比较 若找到就返回x的位置i 否则输出无此元素 返回 1 算法实现 intLocateList SqListL intx intj for j 0 j L length j if L elem j x returnj printf Nox return 1 2 2线性表的顺序表示和实现 3 线性表的插入运算线性表的插入运算是指在表的第i 1 i n 1 个元素之前 插入一个新元素x 使长度为n的线性表 a1 ai 1 ai an 0i 2i 1n 1变成长度为n 1的线性表 a1 ai 1 x ai an 2 2线性表的顺序表示和实现 其算法如下 voidInsertList Sqlist L ElemTypex inti intj ElemType newbase NULL if iL length 1 printf Positionerror exit 0 if L length L listsize newbase ElemType realloc L elem L listsize ListIncrement sizeof ElemType if newbase printf failed exit 0 L elem newbase L listsize ListIncrement for j L length 1 j i 1 j L elem j 1 L elem j L elem i 1 x L length 考虑移动元素的平均情况 假设在第i个元素之前插入的概率为 则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行插入的概率都是相等的 则移动元素的期望值为 2 2线性表的顺序表示和实现 4 线性表的删除运算线性表的删除运算是指将线性表的第i个 1 i n 数据元素删除 使长度为n的线性表 a1 ai 1 ai ai 1 an 0i 2i 1in 1变成长度为n 1的线性表 a1 ai 1 ai 1 an 考虑移动元素的平均情况 假设删除第i个元素的概率为 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为 若假定在线性表中任何一个位置上进行删除的概率都是相等的 则移动元素的期望值为 2 2线性表的顺序表示和实现 其算法如下 voidDeleteList Sqlist L inti intj if iL length printf Positionerror exit 0 for j i jlength 1 j L elem j 1 L elem j L length 2 2线性表的顺序表示和实现 三 插入 删除算法分析 插入 删除算法的时间主要花费在循环移动元素的语句上 该语句的执行次数不仅依赖于表的长度 而且还与新元素插入或删除的位置i有关 若线性表的表长为n 具体情况如下 2 2线性表的顺序表示和实现 顺序表的查找算法在顺序表中查找第一个值为x的数据元素 从第一个元素开始 依次和x进行比较 若找到就返回x的位序 从1开始 i 否则输出无此元素 返回0 算法实现 intLocateList SqListL intx inti j for j 0 j L length j if L elem j x return i 1 printf Nox return0 2 2线性表的顺序表示和实现 线性表的合并将两个递增有序的线性表合并为一个递增有序的线性表 例如 设La 3 5 8 11 Lb 2 6 8 9 15 20 则 Lc 2 3 5 6 8 8 9 11 15 20 分析 Lc中的数据元素或者是La中的数据元素 或者是Lb中的数据元素 而La和Lb都是有序表 则只要先将Lc置为空表 然后将La和Lb中的元素逐个比较 按序插入到Lc中即可 因此 可设3个指针i j k i和j分别指向La和Lb中的当前待比较的元素 k指向Lc表中当前待放入元素的位置 若设i当前所指的元素为a j当前所指的元素为b 则当前应插入到Lc中的元素c为 当 时c 当 时c b 在i所指元素插入到Lc表后 i指针加1 在La表中后移 指向下一个待比较的元素 j指针操作类似 很显然 指针i和j的初值均为0 2 2线性表的顺序表示和实现 voidmerge intLa intm intLb intn int Lc inti j k i 0 j 0 k 0 Lc int malloc m n sizeof int 初始化表Lc if Lc exit 0 while i m voidMergeList Sq SqListla SqListlb SqList 时间复杂度 O la length lb length 2 2线性表的顺序表示和实现 四 顺序表存储结构的特点任意数据元素的存储地址都可由一个公式直接导出 因此顺序存储结构的线性表可以随机存取其中的任意元素 但是 顺序存储结构也有一些不方便之处 主要表现在 1 数据元素最大个数需预先确定 需预先分配相应的存储空间 2 插入与删除运算的效率很低 为了保持线性表中的数据元素的顺序 在插入操作和删除操作时需移动大量数据 2 3线性表的链式表示和实现 线性表的链式存储结构的特点是用一组任意的存储单元 可以是连续的 也可以是不连续的 存储线性表的数据元素 借助指针来指示元素之间一对一的线性关系 根据指针的个数以及最后一个结点的指针指向可以分为 单链表 双向链表 循环链表等链式存储结构 一 单链表的定义为了表示每个数据元素ai与其后继元素ai 1之间的逻辑关系 对数据元素ai来说 除了需要存储它本身的信息外 还需要存储它的直接后继元素的地址 这两部分信息组成了数据元素ai在内存中的存储映象 存储状态 称为结点 每个结点都有两个域构成 一个是存放数据元素值的域 称为数据域 存储直接后继元素地址的域 称为指针域 n个结点就链成了一个链表 若链表中的每个结点只包含一个指针域 最后一个结点的指针域指向NULL 就称之为线性链表或单链表 举例如下 2 3 1单链表 110 130135 160165170 200205 例1 线性表 bat cat eat fat hat jat lat mat 2 3 1单链表 bat cat eat mat head 例1的单链表可画成下图所示的形式 这就是单链表的逻辑示意图head 由上可见 单链表可由头指针唯一确定 因此单链表可以用头指针的名字来命名 例如 若头指针名是head 则把该单链表称为单链表head 2 3 1单链表 有时 我们在单链表的第一个结点之前附设一个结点 称之为头结点 头结点的数据域可以不存储任何值 也可以存储如线性表的长度等之类的附加信息 头结点的指针域存储第一个结点的地址 若链表为空 则头结点的指针域为 空 如下图 a 所示为一个空线性链表 图 b 所示为一个带头结点的非空线性链表 a1 a2 an a b 带头结点的单链表的示意图 引入头结点的好处是 2 3 1单链表 二 单链表存储结构描述 typedefintElemtype 或者typedefcharElemtype structLnode Elemtypedata structLnode next 实例中结构如下 structstudent longnum structstudent next 2 3 1单链表 三 单链表的相关基本操作创建带头结点的单链表单链表和顺序表不同 它是一种动态结构 它的结点空间不需要预先分配 而是在需要时向系统即时申请 因此建立线性表的链式存储结构的过程就是一个动态生成结点并链成链表的过程 即从 空表 的初始状态开始 依次建立各元素结点 并逐个插入链表 2 3 1单链表 2 3 1单链表 带头结点的单链表的创建算法实现 始终从表尾插入新结点 structstudent creat structstudent head p q longx q head structstudent malloc sizeof structstudent head next NULL printf npleaseinputdatdstothelist scanf ld voidprint structstudent head structstudent p p head next printf nTHelistis if p NULL printf thelistisNULL n while p NULL printf 6ld p num p p next printf n 4 单链表的插入操作在单链表的第i个结点之前插入一个新结点 示意图 p 2 3 1单链表 voidinsert structstudent head structstudent p q t p structstudent malloc sizeof structstudent printf npleaseinputthestudentyouwanttoinsert scanf ld 5 单链表的删除操作删除单链表中第i个结点 p s ai 在单链表中删除一个结点 b 删除并释放第i个结点 a 寻找第i个结点的直接前驱p head 2 3 1单链表 voiddel structstudent head structstudent p q longnum printf npleaseinputthestudent numyouwanttodelete scanf ld 以上算法的时间复杂度均为O n voidsave structstudent head structstudent p1 FILE fp charfile 20 d aa txt printf filename s n file printf Pleasewait n if fp fopen file wb NULL printf can topenfile s file exit 0 p1 head next while p1 NULL fwrite void p1 sizeof structstudent 1 fp p1 p1 next fclose fp structstudent filein void structstudent p1 p2 head inti 0 FILE fp charfile 20 d aa txt printf filename s n file if fp fopen file rb NULL printf can topenfile s file exit 0 head p2 structstudent malloc sizeof p1 p1 structstudent malloc sizeof p1 while fread p1 sizeof p1 1 fp 1 i p2 next p1 p2 p1 p1 next NULL p1 structstudent malloc sizeof p1 free p1 fclose fp if i 0 printf Norecoredin s return head P302 11voidcreatelist L linklist 6 单链表的合并将两个递增有序的单链表合并为一个递增有序的单链表 需设立3个指针pa pb pc 其中pa和pb分别指示La表和Lb表中当前待比较插入的结点 而pc指向Lc表中当前最后一个结点 若pa datadata 则将pa所指结点从原链表断开 连接到pc所指结点之后 否则将pb所指结点链接到pc所指结点之后 显然 初始状态是 当La和Lb表非空时 pa和pb分别指向La和Lb中第一个结点 pc指向空表Lc中的头结点 2 3 1单链表 单链表的合并算法实现structLnode mergelist l structLnode La structLnode Lb structLnode pa pb pc pa La next pb Lb next Lc structLnode malloc sizeof structLnode Lc next NULL pc Lc while pa NULL 2 3 1单链表 2 3 2循环链表 循环链表是另一种形式的链式存储结构 它的特点是单链表中最后一个结点的指针域指向链表的表头结点 整个链表形成一个环 这样 从表中任一结点出发都可找到表中其他的结点 这也是循环链表的优点 逻辑结构示意图如下所示 2 3 2循环链表 图2 12循环链表 循环链表示意图 循环链表的操作和单链表基本一致 差别仅在于 算法中的循环条件不是p或p next是否为NULL 而是p或p next是否等于头指针 2 3 3双向链表 1 双向链表的定义在单链表的每个结点中只有一个指示后继的指针域 因此从任何一个结点出发 都能很容易地通过指针域找到它的所有后继结点 但若需找出该结点的前驱结点 则必须从表头出发重新查找 因此 在单链表中 查找某结点的后继结点的执行时间为O 1 而查找其前驱结点的执行时间为O n 我们可用双向链表来克服单链表的这种缺点 双向链表中每个结点含有两个指针域 一个指向直接前驱 另一个指向直接后继 2 3 3双向链表 priornext head a 空双向链表 head 非空的双向链表双向链表逻辑示意图 NULL a1 a2 an 2 3 3双向链表 2 双向链表存储结构描述typedefstructDuLNode Elemtypedata structDuLNode prior structDuLNode next DuLNode 2 3 3双向链表 若p为指向双向链表中的某一个结点ai的指针 则显然有 p next prior p prior next p在双向链表中 有些操作如 求长度 取元素 查找等 它们只涉及到一个方向的指针 因此它们的算法与单链表的操作相同 但在插入 删除时 则需同时修改两个方向上的指针 2 3 3双向链表 3 双向链表的基本操作 1 在双向链表中插入一个结点在双向链表的第i个结点前插入一个新结点时 设指针p指向第i个结点 称p结点 设s指针指向新结点 称s结点 则操作过程如下图所示 2 3 3双向链表 双向链表插入操作的核心语句序列为 s prior p prior 图中步骤 s prior next s 图中步骤 s next p 图中步骤 p prior s 图中步骤 2 3 3双向链表 2 在双向链表中删除一个结点 在双向链表中删除一个结点 ai 1 ai ai 1 p 在双向链表中删除结点的核心语句序列 p prior next p next 图中步骤 p next prior p prior 图中步骤 free p 2 3 3双向链表 与单向循环链表类似 双向链表也可以有循环表 让头结点的前驱指针指向链表的最后的一个结点 让最后一个结点的后继指针指向头结点 就构成了双向循环链表 下图为一个双向循环链表示例 a1 a2 an head 非空的双向循环链表 总结 顺序表和链表的比较 顺序表和链表的比较主要从以下两方面考虑 1 基于空间的考虑 1 当线性表的长度变化较大 难以估计其存储规模时 以链表作为存储结构好 2 当线性表的长度变化不大 易于事先确定其大小时 为了节约存储空间 宜采用顺序存储结构 2 基于时间的考虑 1 若线性表主要是进行查找 很少做插入 删除操作时 宜采用顺序存储结构 2 对于频繁进行插入和删除的线性表 宜采用链式存储结构 2 4一元多项式的表示及相加 在数学上 一个一元n次多项式Pn x 可以表示为 Pn x p0 p1x p2x2 pnxn它由n 1个系数唯一确定 因此 在计算机里 它可以用一个线性表P来表示 P p0 p1 p2 pn 每一项的指数i隐含在其系数pi的序号里 同样 一个一元m次多项式Qm x 可以表示为 Q q0 q1 q2 qm 设m n 则两个多项式相加的结果Rn x 可用线性表R表示为 R p0 q0 p1 q1 pm qm pm 1 pn 2 4一元多项式的表示及相加 可以对P Q和R采用顺序存储结构 只存储系数 故若多项式的最高次数为n则需要n 1个存储空间 使用这种存储结构可以使多项式相加的算法十分简单 但是当多项式的次数很高且变化很大时 多项式中存在大量的零系数 这种表示方式就会浪费大量存储空间 例 形如S x 1 4x7 2x100的多项式 线性表中只有3个非0元素 但却需要101个连续的存储单元 其中却存储了大量的0元素 浪费了大量的存储空间 2 4一元多项式的表示及相加 为了有效而合理地利用存储空间 只存储非0项的系数及其相应的指数 对于系数为0的所有项全都不存储 一般情况下 去掉系数为0的所有项 一个一元n次多项式可记作 Pn x p1xe1 p2xe2 pmxem其中 pi是指数为ei的项的非0系数 且0 e1 e2 em n那么上述多项式就可以用一个长度为m 且每个数据元素有两个数据项 系数项和指数项 的线性表来唯一确定 p1 e1 p2 e2 pm em 2 4一元多项式的表示及相加 采用链表表示多项式时 每个结点的数据域有两项 系数项 指数项 则结点定义如下 structpoly intcoef 系数项intexp 指数项structpoly next 2 4一元多项式的表示及相加 假设多项式A17 x 8 3x 9x10 5x17与B10 x 8x 14x7 9x10则C17 x A x B x 8 11x 14x7 5x17用单链表表示如下 其头指针分别为Ah Bh 假设链表是按指数递增的有序链表 Ah 81 147 910 Bh 多项式的单链表存储结构 2 4一元多项式的表示及相加 其运算规则如下 假设指针qa和qb分别指向多项式A17 x 和多项式B10 x 中当前进行比较的某个结点 则比较两个结点的数据域的指数项 有三种情况 1 指针qa所指结点的指数值 指针qb所指结点的指数值时 则将qa指针所指向的结点插入到 和链表 的后面 qa指针后移 2 指针qa所指结点的指数值 指针qb所指结点的指数值时 则将qb指针所指向的结点插入到 和链表 的后面 qb指针后移 3 指针qa所指结点的指数值 指针qb所指结点的指数值时 将两个结点中的系数相加 若和不为零 则修改qa所指结点的系数值 同时释放qb所指结点 qa和qb指针均后移 反之 从多项式A17 x 的链表中删除相应结点 并释放指针qa和qb所指结点 qa和qb指针均后移 2 4一元多项式的表示及相加 多项式相加的算法实现structpoly add poly structpoly Ah structpoly Bh structpoly qa qb s r Ch qa Ah next qb Bh next qa和q