数据结构(线性表、树、图).ppt

《数据结构(线性表、树、图).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章数据结构数据结构概要1.数据结构定义：指数据元素的集合及元素之间的关系和构造方法，可以用二元组表示为：B=（A，R），其中A是数据元素的非空有限集合，R是定义在A上的关系的非空有限集合。2.要达到的目标：(1)从问题入手，分析和研究数据结构的特性，选择适当的逻辑结构、存储结构及相应的操作方法。(2)并掌握时间复杂度和空间复杂度的概念。3.按逻辑关系分类线性结构(包括线性表、栈、队列、数组、串等)非线性结构(树、图)第一部分：线性结构一、线性表最常见的一种线性结构，有两种存储方法：顺序存储和

2、链式存储1、定义：N个元素的有限序列，n≥0，通常表示为（a1,a2,…,an）2、特点：元素集合中存在唯一称作“第一个”和唯一“最后一个”元素，除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，序列中的每个元素只有一个直接后继。3、存储结构：顺序存储结构含义：用一组连续的存储单元存放线性表中的数据元素。特点：逻辑相邻的元素，物理位置也相邻。优点和缺点：存取方便，插入删除操作需要移动大量元素。第一部分：线性结构.链式存储结构含义：存储数据元素的同时必须存储元素之间的关系。用节点来存储

3、数据元素，节点地址可以连续，也可以不连续。节点结构：节点的插入和删除操作插入操作删除操作第一部分：线性结构4.其他几种链表结构：双向链表：每个节点包含两个指针，分别指出当前节点元素的直接前驱和直接后继。循环链表：静态链表：借助数组来描述线性表的链式存储结构第一部分：线性结构二、栈和队列1.栈定义只能通过它的一端来实现数据存储和检索的线性结构，也称为后进先出（或先进后出）的线性表。基本运算初始化栈：InitStack(S)判栈空:StackEmpty入栈:Push(S,x)出栈:Pop(S)读栈顶

4、元素:Top(s)存储结构顺序存储：（顺序栈）指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。第一部分：线性结构链式存储（链栈）：为了克服顺序栈可能存在上溢的不足，采用钻链表作为存储结构的栈。栈的应用：表达式求值，括号匹配，递归转非递归。2.队列定义：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，表的另一端删除元素。基本运算：(1)初始化队InitQueue(Q)(2)判队空Empty(Q)(3)入队EnQueue(Q,x)(4)出

5、队DeQueue(Q)(5)读队头元素FrontQue(Q)第一部分：线性结构队列的存储结构顺序存储（顺序队列）利用一组地址连续的存储单元存放队列中的元素，同时设置队头指针和队尾指针，分别表示当前的队首元素和队尾元素。思考:(1)为什么要引入循环队列？(2)什么叫假溢出？如何形成的？链式存储（链队列）队列的应用：常用于需要排队的场合：比如操作系统中处理打印任务，离散事件的计算模拟等。第一部分：线性结构3串即字符串，是一种特殊的线性表，它的数据元素仅由一个字符组成。串的定义是仅由字符构成的有限序列

6、，是取值范围受限的线性表。一般记为：S=‘a1a2…an’，其中S是串名，单引号括起来的字符序列是串值。几个相关的基本概念空串：长度为零的串，不包含任何字符。空格串：由一个或多个空格组成的串。子串：由串中任意长度的连续字符构成的序列称为子串。空串是任意串的子串。串相等：两个串长度相等，且对应位置上的字符也相同。串比较：比较大小时，以ASCII码值作为依据。基本操作赋值strAssign(s,t):将串t赋给串s连接Concat(s,t):串t接续在串s的尾部，形成一个新串。第一部分：线性结构求串

7、长StrLength(s)串比较StrCompare(s,t)返回值-1、0、1分别表示st求子串SubString(s,start,len)串的存储结构静态存储(即串的顺序存储结构)用一组地址连续的存储单元来存储串值的字符序列。（在程序设计语言中可借助字符数组定义串的存储空间）。链式存储用链表存储串中的字符，每个节点中可以存储一个字符，也可以存储多个字符，注意存储密度问题,因为它直接影响到串和处理效率。串的模式匹配即子串的定位操作，是各种串处理中最重要的运算之一。有以下两种算

8、法：（1）朴素模式匹配算法基本思想：P432（2）改进的模式匹配算法基本思想：P433第一部分：线性结构4数组、矩阵和广义表（1）数组定义：线性表的元素又是一个线性表，是定长线性表在维数上的一个扩张。特点：.数据元素数目固定.数据元素具有相同数据类型.数据元素的下标关系具有上下界的约束且下标有序两个基本运算其一：给定一组下标，存取相应的数据元素；其二：给定一组下标，修改相应的数据元素中某个数据项的值。存储结构由于数组一般不作插入和删除运算，所以数组中数据元素个数和元素之间的关系固定不变，因此适合