C语言线性结构.ppt

1 SchoolofEEUESTC 电子科技大学 电子科技大学UESTC 王正宁电子工程学院电子科技大学 成都 中国 C语言和软件技术基础 2 SchoolofEEUESTC 电子科技大学 软件技术基础 线性结构 3 本章内容要点 SchoolofEEUESTC 线性结构 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 4 SchoolofEEUESTC 线性数据结构的基本概念 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 5 SchoolofEEUESTC 线性数据结构的基本概念 电子科技大学 线性结构特点 在数据元素的非空有限集中存在唯一的一个被称作 第一个 的数据元素存在唯一的一个被称作 最后一个 的数据元素除第一个外 集合中的每个数据元素均只有一个前驱除最后一个外 集合中的每个数据元素均只有一个后继 6 SchoolofEEUESTC 线性数据结构的基本概念 电子科技大学 常见的线性结构类型 线性表堆栈队列数组串 7 SchoolofEEUESTC 线性表的基本概念 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 8 SchoolofEEUESTC 线性表的基本概念 电子科技大学 线性表是一种最简单的线性结构线性表是n个相同类型数据元素的有限线性序列记为 L a1 a2 an 其中n为线性表的长度 数据元素之间的关系 ai 1领先于ai ai领先于ai 1 称ai 1是ai的直接前驱元素 ai 1是ai的直接后继元素 除a1外 每个元素有且仅有一个直接前驱元素 除an外 每个元素有且仅有一个直接后继元素 线性表中数据元素的个数n n 0 称为线性表的长度 当n 0时 称为空表 9 SchoolofEEUESTC 线性表的主要操作 电子科技大学 Initial L 初始化 创建一个空的线性表 Length L 求表长 返回表内元素个数 Get L i 取元素 返回第i个元素 Locate L x 定位 返回x的索引号 Insert L i x 插入 在第i个元素之前插入x Delete L i 删除 删除第i个元素 Prior L elm 求前驱 寻找元素elm的前驱Next L elm 求后继 寻找元素elm的后继Empty L 判断空表 空 true 非空 falseClear L 将L置为空表 置空操作 10 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 11 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 线性表的顺序存储方式顺序表定义 用一组地址连续的存储单元存放的一个线性表元素定位算法 Loc ai Loc a1 i 1 KLoc ai 1 Loc ai K其中 K 一个元素占用的存储单元个数Loc ai 线性表第i个元素的地址 特点 逻辑上相邻 物理地址相邻随机存取实现 可用一维数组实现 12 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 应用举例 对一批图书的信息进行处理图书的信息包括 书名 作者 出版社 价格等 描述这些信息的数据类型可以定义为 typedefstructbook intnum charname 20 charauthor 10 charpublisher 30 floatprice DATATYPE 假设图书的数量为N采用顺序表进行存储首先 需要创建一个顺序表 DATATYPEBook N DATATYPE pData DATATYPE malloc N sizeof DATATYPE free pData 13 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 应用举例 对一批图书的信息进行处理 14 SchoolofEEUESTC 顺序表的插入和删除 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 15 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 元素的插入和删除操作 插入操作 在第i 1个元素和第i个元素之间插入一个新的数据元素x 使原来长度为n的线性表变成长度为n 1的线性表 16 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 元素的插入和删除操作 插入操作 在第i 1个元素和第i个元素之间插入一个新的数据元素x 使原来长度为n的线性表变成长度为n 1的线性表 17 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 插入操作 算法 Insert L i x 插入前 L a1 ai 1 ai an 插入后 L a1 ai 1 x ai an 算法思想 进行合法性检查 1 i n 1 判断线性表是否已满 将第n个至第i个元素逐一后移一个单元 在第i个位置处插入新元素 将表的长度加1 18 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 插入操作的实现 Insert SqList L inti ElemTypee 在顺序表L的第i个元素之前插入新的元素x i的合法范围为1 i L length 1 if i L length 1 returnERROR if L length L lsitsize realloc q 19 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 插入算法的时间复杂度分析 插入算法时间复杂度分析最坏情况是在第1个元素前插入 i 1 此时 要后移n个元素 因此T n O n 20 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 元素的插入和删除操作 删除操作 线性表的删除是指将第i 1 i n 个元素删除 使长度为n的线性表变成长度为n 1的线性表 21 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 删除操作 算法 Delete L i 删除前 L a1 ai 1 ai ai 1 an 删除后 L a1 ai 1 ai 1 an 算法思想 进行合法性检查 i是否满足1 i n 确定被删除的元素在线性表中的位置 将第i 1至第n个元素逐一向前移一个位置 将表的长度减1 22 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 删除操作的实现 Delete SqList L inti ElemType e ListDelete Sq for p p q p p 1 p 被删除元素之后的元素左移 L length 表长减1returnOK p 表尾元素的位置 if iL length returnERROR 删除位置不合法 23 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 删除算法的时间复杂度分析 删除算法时间复杂度分析最坏情况是删除第1个元素 此时 要前移n 1个元素 因此T n O n 24 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 从算法实现可以看到 在线性表中进行插入和删除操作时 时间主要耗费在 移动元素 上 而移动元素的个数取决于元素插入或删除的位置 假设在第i个元素之前插入一个元素的概率为Pi 则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为 不失一般性 假设插入元素是等概率的 即Pi 1 n 1 线性表操作中移动元素的平均情况分析 25 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 从算法实现可以看到 在线性表中进行插入和删除操作时 时间主要耗费在 移动元素 上 而移动元素的个数取决于元素插入或删除的位置 假设删除第i个元素的概率为qi 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为 不失一般性 假设插入元素是等概率的 即qi 1 n 线性表操作中移动元素的平均情况分析 26 SchoolofEEUESTC 线性表的顺序存储方式 电子科技大学 顺序存储结构的优缺点 逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑插入 删除操作需要移动大量的元素必须按最大可能长度预分存储空间 存储利用率低容量难以扩充 是一种静态存储结构 优点 缺点 27 SchoolofEEUESTC 线性表的链式存储方式 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 28 SchoolofEEUESTC 线性表的链式存储方式 电子科技大学 线性链表 用一组任意的存储单元 非连续地址 来存储线性表的元素 每个元素对应一组存储单元 称为结点 每个结点包括两个域 存储数据元素信息的数据域存储直接后继位置的指针域 结点 Node 单链表 由n个结点通过指针域组成的 结点序列 29 SchoolofEEUESTC 线性表的链式存储方式 电子科技大学 单链表 头指针 空指针 用一个头指针指示链表中第一个结点的存储位置 线性链表最后一个结点的指针域为 空 NULL或 30 SchoolofEEUESTC 线性表的链式存储方式 电子科技大学 带头结点的单链表 为了算法实现上的方便 通常在线性链表的第一个元素结点之前附加一个称为 头结点 的元素 当链表为空时 头结点的指针域为NULL 数据域不存储任何信息 指针域存储第一个元素结点的位置 31 SchoolofEEUESTC 线性表的链式存储方式 电子科技大学 头指针和头结点 头指针是指向头结点的指针 引入头结点 便于对链表进行初始化 建立一个空链表带头结点链表的引入是为了把空表和非空表的处理统一起来 32 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 线性数据结构的基本概念线性表的基本概念线性表的顺序存储方式 顺序表顺序表的插入和删除算法线性表的链式存储方式 单链表单链表的创建 访问 插入和删除算法 33 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的创建 结点的实现 typedefstruct node datatypeData struct node Next node 生成一个node型新结点 p node malloc sizeof node p结点的回收 free p node H p p node malloc sizeof node p Next NULL H p p 34 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的访问 typedefstruct node datatypeData struct node Next node p 表示p所指向的结点 p Data p Data表示p指向结点的数据域 p Next p Next表示p指向结点的指针域 p 35 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的插入 在单链表内的指定元素之前插入一个新元素X Insert H i X 36 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的插入 可见 在单链表中插入结点只需要修改指针但同时 若要在第i个结点之前插入元素 修改的是第i 1个结点的指针 因此 在单链表中第i个结点之前进行插入的基本思想为 找到线性表中第i 1个结点 然后修改其指向后继的指针 37 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的插入 算法实现 voidInsertsl node h inti ElemTyepx node p h t intj 0 while p next NULL 插入元素x 38 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的删除 在单链表内删除指定位置的元素 Delete H i 39 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的删除 在单链表中删除第i个结点的基本思想为 找到线性表中第i 1个结点然后将待删除结点的指针域内容赋给它前一结点的指针域最后释放删除结点所占的存储空间 40 SchoolofEEUESTC 单链表的创建 访问 插入和删除 电子科技大学 单链表的删