《数据结构 四川理工》由会员分享，可在线阅读，更多相关《数据结构 四川理工（58页珍藏版）》请在金锄头文库上搜索。
1、第第1 1章 绪 论章 绪 论复习要点：复习要点：1.数据结构基本概念2. 数据元素、数据项、逻辑结构、物理结构 3.时间复杂度、空间复杂度、语句频度等计算 DCS of SUSE DCS of SUSE基本概念n(1)数据：所有能被计算机识别、存储和处理的符号的集 合（包括数字、字符、声音、图像等信息 ）。n(2)数据元素:是数据的基本单位，具有完整确定的实际 意义。在计算机程序中通常作为一个整体进行考虑和处 理。一个数据元素可由若干个数据项组成。n(3)数据项:构成数据元素的项目。它是数据不可分割的 最小单位。n(4)数据类型：指一个类型和定义在这个类型上的操作集 合。例：C语言（基本类型
2、：整型、浮点型、字符型等构 造类型：数组、结构、联合、指针、枚举等）n(5)抽象数据元素：抽象定义的、没有实际含义的数据元 素。n(6)抽象数据类型：用户自己定义的数据类型。 DCS of SUSE DCS of SUSE数据结构 DCS of SUSE DCS of SUSE集合结构： 仅同属一个集合线性结构: 一对一（1:1) 树 结 构: 一对多（1:n)图 结 构: 多对多 (m:n)线 性逻辑结构可细分为4类：数据的逻辑结构指数据元素之间的逻辑关系。即从逻辑关系上描述数据 ，它与数据的存储无关，是独立于计算机的。 DCS of SUSE DCS of SUSEn（1） R=(D, S
3、)n D= a, b, c, d, e, f n S=, , , , 解： 上述表达式可用图形表示为：b c a e f d此结构为线性的。例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。 DCS of SUSE DCS of SUSE物理结构亦称存储结构，是数据的逻辑 结构在计算机存储器内的表示（或映像） 。它依赖于计算机。 存储结构可分为4大类：例：复数3.02.3i 的两种存储方式：顺序、链式、索引、散列2.303023.00300 041503023.0030004152.3法1：地址 内容法2：地址 内容2字节数据的物理结构 DCS of SUSE DCS of
4、SUSE时间复杂度和空间复杂度如何表示？ DCS of SUSE DCS of SUSE特别说明：如果无论算法规模怎样变化，其执行时间为一常数，则该 算法的时间复杂度为O(1). DCS of SUSE DCS of SUSE DCS of SUSE DCS of SUSE第2章 线性表复习要点： 1.基本概念线性结构、线性表、位序、长度、空表等 2.线性表的基本操作主要掌握插入、删除等运算及特性 3.顺序存储、链式存储特点，组织方式顺序表、单链表、双链表的查找、插入和删除 等操作 DCS of SUSE DCS of SUSEn一、线性表（linear_list）n 线性表是n个数据元素的有
5、限序列 ，记为：n L=（a1,a2, ,an）数据元素之间的关系是：ai-1领先于ai，ai领先于ai+1。称ai-1是ai的直接前驱 元素；ai+1是ai的直接后继 元素。除a1外，每个元素有且仅有一个直接前驱元素，除an外，每个元素有且仅有一个直接后继元素。线性表中数据元素的个数n(n=0)称为线性表的长度，当n=0时，称为空表。 DCS of SUSE DCS of SUSE线性表的顺序存储结构n一、顺序存储结构n 用一组地址连续的存储单元依次存储线性表的元素。设线性表的每 个元素占用k个存储单元，则第i个元素ai 的存储位置为： Loc(ai)=Loc(a1)+(i-1)*k 其中，
6、Loc(ai)为线性表的起址。a1 a2aianbb+kb+(i-1)kb+(n-1)k特点： 存储单元地址连续（需要一段连续空间） 逻辑上相邻的数据元素其物理位置也相邻 存储密度大（100%） 随机存取元素序号与存储位置存在如下关系：Loc(ai) = Loc(a1) + (i - 1) * d (1in)线性表的顺序存储指用一组地址连续的存储单元 依次存储线性表的数据元素。这称为顺序表。 DCS of SUSE DCS of SUSEn二. 插入和删除操作n1. 插入运算 INSERT（L, i, b）n插入前：L=（a1, . , ai-1, ai, . ,an）n插入后：L=（a1,
7、. , ai-1, b, ai, . ,an ）算法思想： 进行合法性检查，1 n呢？特别说明：特别说明：指指 针的移动，不针的移动，不 会删除结点。会删除结点。 DCS of SUSE DCS of SUSEn单链表上的插入运算(第i个位置上插入新的结 点)逻辑运算n(a1, a2, , ai-1, ai, ai+1, , an) (a1, a2, , ai-1, e, ai, ai+1, , an)在元素ai之前插入一个新元素e单链表上的实现示意图a1 ai an Lai-1 ai+1 基本步骤： 找到第i-1个元素所在结点； 申请一个新结点s并填入e值； 修改s的指针域指向p的下一结点；
8、p e s思考：第步是否可交换？ DCS of SUSE DCS of SUSEn链表的优缺点 优点：n插入、删除时无须移动元素，只需修改 指针n根据需要申请存储空间，且不要求连续 的存储空间 缺点：n对表中的元素只能进行顺序访问n用指针指示元素之间的逻辑关系（直接 前驱、后继），存储空间利用率低 DCS of SUSE DCS of SUSEhead ai-1ai+1anai a1双向链表双向链表上的插入操作(将元素e插入到链表的第 i个结点前)基本步骤： (1) 定位指针p指向结点ai-1 ;pes(2) 建立新结点s并赋e ; (3) 修改s的next指针域指向p下一结点：s-next
9、= p-next;(5) 修改p的next指针域指向s结点：p-next = s; (6) 修改s下一结点的prior指针域指向s：s-next-prior = s;(4) 修改s的prior指针域指向p结点：s-prior = p;问题：修改指针的步骤是否可随意？不带头结点？ DCS of SUSE DCS of SUSE双向链表上的删除操作(删除第i个结点)head ai-1ai+1anai a1基本步骤： (1) 定位指针p指向结点ai;p(2) 修改p的前一结点的next指针域指向p下一结点： p-prior-next = p-next; (3) 修改p的下一结点的prior指针域指向
10、p前一结点： p -next -prior = p-prior; (4) 释放结点p。 DCS of SUSE DCS of SUSE第3章 栈和队列n一、栈的概念栈（stack）是插入和删除操作限定在表尾进行的线性表 。 n栈的逻辑表示为：S =（a1,a2, ,an）表尾元素an称为栈顶(top)表头元素a1称为栈底(bottom)n不含元素的空表称为空栈n栈的运算特性是后进先出(Last In First Out- LIFO)或先进后出(First In Last Out-FILO) DCS of SUSE DCS of SUSEn二、队列的概念n队列（Queue）是限定仅在一端插入,另
11、一端删除的线性 表。n允许插入的一端叫队尾( rear),n允许删除的一端叫队头(front),n不含元素的空表称为空队列n队列的运算特性是先进先出(First In First Out- FIFO)出队列入队列a1 a2 . an队头队尾 DCS of SUSE DCS of SUSE插入、删除操作栈：Push( j = 1;while (i Strlength(T) ) return (i Strlength(T);return 0; / Index算法时间复杂度?O(n*m)，其中n、m分别为主串和子串长度 DCS of SUSE DCS of SUSE第5章 数组和广义表 要点：数组基
12、本概念和特殊矩阵的压缩 存贮 vLOC(aij)=LOC(a11)+(i-1)*n+j-1*d对称矩阵数组Bai,jan,na1,1a2,1a2,2a3,11234km下标a1,1 a1,2 a1,na2,1 a2,2 a2,n ai,j an,1 an,2 an,na1,1a2,1 a2,2 ai,j an,1 an,2 an,nk = ? m = ? DCS of SUSE DCS of SUSE第6章 树与二叉树要点：（1）二叉树的性质、推论及应用性质1、性质2、性质3、性质4、性质5（2）完全二叉树的概念及特点（3）二叉树的遍历（4）线索二叉树的基本概念和数据结构（5）树、森林与二叉树
13、的转换，及相关特点（6）Huffman 树及Huffman编码 DCS of SUSE DCS of SUSE树的基本术语 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树的个数,度为零的 结点称为叶结点; 3. 树的度:树中所有结点的度的最大值Max(D(I)含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为 第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度 5.森林:是m(m=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.结论：一棵树的各结点的度之和，等于该树的分支数目。 D
14、CS of SUSE DCS of SUSE二叉树性质(扩展要求掌握各性质的推论)性质1. 在二叉树的第i层上至多有2i-1个结点(i1)。性质2. 深度为k的二叉树至多有2k-1个结点(k1)。 （深度一定，二叉树的最大结点数也确定） 性质3. 二叉树中,终端结点数n0与度为2的结点数n2有 如下关系: n0=n2+1性质4. 结点数为n的完全二叉树，其深度为 log2n + 1 DCS of SUSE DCS of SUSE性质5. 在按层序编号的n个结点的完全二叉树中， 任意一结点i(1in)有： i=1时，结点i是树的根；否则(i1)，结点i的 双亲为结点i/2。 2in时，结点i无左
15、孩子，为叶结点；否则， 结点i的左孩子为结点2i。 2i+1n时，结点i无右孩子；否则，结点i的 右孩子为结点2i+1。 性质6. 含有n个结点的二叉链表中，有n+1个 空链域。重点说明：对于前4个性质，要求能推广到多叉树。 DCS of SUSE DCS of SUSE二叉树的遍历遍历顺序：DLR，LDR，LRD，层序遍历DLR根结点根的 左子树根的 右子树 DCS of SUSE DCS of SUSE线索二叉树： 结点结构 在二叉链表中增加 ltag 和 rtag 两个标志域lchild ltag data rtag rchild 若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）； 若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）； DCS of SUSE DC
