数据结构(C语言描述)课件.ppt

数据结构辅导 李青山 西安电子科技大学 5/faculty/liqingshan qshli@ 029-8820-4611 课程内容框架 1.2基本概念和术语 1.2基本概念和术语（续） 1.3算法和算法分析 1.3算法和算法分析（续） 1.3算法和算法分析（续） 1.3算法和算法分析（续） 第一部分 线性数据结构 2.线性表 3.栈、队列和串 2.1线性表的逻辑结构 在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素； 存在唯一的一个被称作“最后一个”的数据元素； 除第一个之外，集合中的每一个数据元素均只有一个前驱； 除最后一个之外，集合中每一个数据元素均只有一个后继。 2.1线性表的逻辑结构（续） 线性表：n个数据元素的有限序列（线性表中的数据元素在不同环境下具体含义可以不同，但在同一线性表中的元素性质必须相同）。 表长：线性表中元素的个数n(n=0)。 空表：n=0时的线性表称为空表。 位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。 2.1线性表的逻辑结构（续） ADT List { 数据对象：D={ai | ai属于ElemSet, i = 1,2, … ,n, n=0} 数据关系：R1={ ai-1, ai | ai-1, ai属于D, i =2,3, …, n} 2.2线性表的顺序存储结构 内涵： 线性表的顺序存储指用一组地址连续的存储 单元依次存储线性表的数据元素。这称为顺序表。 特点： * 存储单元地址连续（需要一段连续空间） * 逻辑上相邻的数据元素其物理位置也相邻 * 随机存取 * 存储密度为大（100%） 2.2线性表的顺序存储结构（续） 2.2线性表的顺序存储结构（续） （a1，…， ai, ai+1,…, an) 表长为n 2.2线性表的顺序存储结构（续） （a1，…， ai, ai+1,…, an) 表长为n 2.3线性表的链式存储结构 优点： * 不需要额外空间来存储元素之间的关系 * 可以随机存取任一元素 2.3线性表的链式存储结构（续） 内涵： 线性表的链式存储指用任意的存储单元存放线性表中的元素，每个元素与其前驱和（或）后继之间的关系用指针来存储。这称为链表。 2.3线性表的链式存储结构（续） 单链表中，如果每个结点中只包含一个指域， 称这种链表为线性链表或单链表。 单链表可由头指针唯一确定。 2.3线性表的链式存储结构（续） 用高级语言中的指针类型描述线性表的链式存储 2.3线性表的链式存储结构（续） （a1，…， ai, ai+1,…, an) 表长为n 2.3线性表的链式存储结构（续） （a1，…， ai, ai+1,…, an) 表长为n 教学内容---第三章 2.线性表 3.栈、队列和串 3.1 栈、队列和串的逻辑结构 栈和队列是操作受限的线性表 栈和队列的“操作受限”指操作位置受限 串的特殊性在于线性表中数据元素只能是字符 串一般以子串为操作单位 栈、队列和串具有一般线性表共性的特点 特殊的线性表反而应用面更宽 3.1 栈、队列和串的逻辑结构（续） 栈（Stack）：限定仅在表尾进行插入或删除操作的线性表。 栈顶（top） ：插入或删除的表尾端。 栈底（bottom） ：表头端。 空栈：空表。 3.1 栈、队列和串的逻辑结构（续） ADT Stack { 数据对象：D={ai | ai属于ElemSet, i = 1,2, … ,n, n=0} 数据关系：R1={ ai-1, ai | ai-1, ai属于D, i =2,3, …, n}// a1 为栈底， an 栈顶 3.1 栈、队列和串的逻辑结构（续） 队列（Queue）：限定仅在表的一端进行插入，而另一端进行删除操作的线性表。 队尾（rear） ：允许插入的一端。 队头（front）：允许删除的一端。 空队：空表。 3.1 栈、队列和串的逻辑结构（续） ADT Queue { 数据对象：D={ai | ai属于ElemSet, i = 1,2, … ,n, n=0} 数据关系：R1={ ai-1, ai | ai-1, ai属于D, i =2,3, …, n}// a1 为队头， an 队尾 3.1 栈、队列和串的逻辑结构（续） 串（String）：由零个或多个字符组成的有限序列。S=‘a1a2…an’ 串名、串值 串长 空串、空格串 子串：串中任意连续的字符组成的子序列 主串： 字符在串中的位置、子串在串中的位置 串相等 3.1 栈、队列和串的逻辑结构（续） ADT Sring { 数据对象：D={ai | ai属于CharacterSet, i = 1