【数据结构】清华版严蔚敏《数据结构》重点要点
第二章线性表
1线性表的特点及逻辑结构2．线性表的顺序存储结构及基本操作（插入、删除、定位）
本章难点
线性表的顺序存储结构，基本操作在顺序表上的实现及时间复杂度的计算。
内容和要求
线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素，存在唯一的一个被称作“最后一个”的数据元素，除第一个外，集合中的每个数据元素均只有一个前驱，除最后一个外，集合中的每个数据元素均只有一个后继。
§2.1线性表的定义和逻辑结构
定义：一个线性表是n个数据元素的有限序列。
§2.2线性表的顺序存储结构
一、顺序表：
1、定义：用一组地址连续的存储单元存放一个线性表叫顺序表。
2、元素地址计算方法：
LOC(ai)=LOC(a1)+(i-1)*L
LOC(ai+1)=LOC(ai)+L
其中：
L—一个元素占用的存储单元个数
LOC(ai)—线性表第i个元素的地址
3、特点：实现逻辑上相邻—物理地址相邻；实现随机存取
4、实现：可用C语言的一维数组实现
1）插入定义：线性表的插入是指在第I（1£i£n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表。算法时间复杂度T(n)
2）删除定义：线性表的删除是指将第i（1£i£n）个元素删除，使长度为n的线性表。算法评价
5、顺序存储结构的优缺点
优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑
缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充。
习题第19页1,4
第三章链式存储结构
本章重点
1．线性表的链式存储结构的特点2．单链表的基本运算及实现，循环链表，双向链表
单链表的基本运算（建立、查、插入、删除）实现及算法
内容和要求
§3.1线性表的链式存储结构
特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素
每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点
数据域：元素本身信息
指针域：指示直接后继的存储位置
实现
单链表的基本运算：
单链表特点
它是一种动态结构，整个存储空间为多个链表共用
不需预先分配空间
指针占用额外存储空间
不能随机存取，查速度慢
循环链表(circular linked list)
循环链表是表中最后一个结点的指针指向头结点，使链表构成环状
特点：从表中任一结点出发均可到表中其他结点，提高查效率
操作与单链表基本一致，循环条件不同
单链表p或p->link=NULL
循环链表p或p->link=H
双向链表（double linked list）
单链表具有单向性的缺点
结点定义
习题第34页3，4，5，8
第四章栈和队列
本章重点
1．栈的七种基本操作，两种存储结构（顺序、链式）
2．队列的七种基本操作，两种存储结构（顺序、链式）
本章难点
1．顺序栈上实现栈的几个基本操作所对应的算法
2．链栈上元素进栈和出栈的算法
3．队列的表现和操作实现
内容和要求
栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS
§4.1栈（stack）
栈的定义和特点
定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈
特点：先进后出（FILO）或后进先出（LIFO）
栈的存储结构
顺序栈的实现和入栈、出栈算法
链栈的入栈和出栈算法
§4.2队列
队列的定义及特点
定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
队列特点：先进先出(FIFO)
链队列：结点定义
队列的顺序存储结构
实现：用一维数组实现sq[M]
存在问题
设数组维数为M，则：
当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出
当front¹-1,rear=M-1时，再有元素入队发生溢出——假溢出
解决方案
队首固定，每次出队剩余元素向下移动——浪费时间
循环队列
基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M，则令rear=0;
习题第51页1,2，5，
第五章其他线性数据结构
本章重点
1．串的存储结构及基本操作实现
2．二维数组基本操作，向量存储结构
3．稀疏矩阵的压缩存储、转置算法
本章难点
1．串的堆分配存储结构
2．二维数组向量存储结构、地址的计算方法、稀疏矩阵的压缩存储、转置算法
自学内容和要求
§5.1串
定义
※定栈的定义：串是由零个或多个字符组成的有限序列。
一般记为：S＝‘a1a2….an’(n≥0)
※基本操作有九种
«定义串的存储结构
※串的顺序定长存储结构
※堆分配存储结构
※串的基本操作的实现
1．在串的顺序定长相信结构上实现CONCAT（S，T1，T2）操作
2．在串的堆分配存储结构上实现CONCAT（S，T1，T2）操作
3．在串的顺序定长存储结构上实现子串的定位操作INDEX（S，T）
§5.2多维数组
定义二维数组
※定义及基本操作定义：数组是由下标和值组成的序对的集，数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表
※基本运算：给定一组下标，存取对应的数据元给定一组下标，修改相应数据元素的值。
数组的顺序存储结构次序约定
以行序为主序
以列序为主序
数组元素地址计算方法
矩阵的压缩存储
对称矩阵
三角矩阵
稀疏矩阵的压缩存储方法
顺序存储结构
三元组表
带辅助行向量的二元组表
求转置矩阵
问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表
问题分析
一般矩阵转置算法：
十字链表
设行指针数组和列指针数组，分别指向每行、列第一个非零元
结点定义
习题第65页2,3，5,6，7
第六章树
本章重点
1．二叉树的存储结构及其各种操作，遍历二叉树
2．树和森林与二叉树的转换关系，树的遍历
本章难点
1．遍历二叉树的算法
2．树和森林与二叉树的转换关系，哈夫曼树及编码
内容和要求
§6.1树的定义
定义
定义：树(tree)是n(n>0)个结点的有限集T，其中：
有且仅有一个特定的结点，称为树的根(root)
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)
特点：
树中至少有一个结点——根
树中各子树是互不相交的集合
基本术语
§6.2二叉树
定义
定义：二叉树是n(n³0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成
二叉树的基本性质
特点
每个结点至多有二棵子树(即不存在度大于2的结点)
二叉树的子树有左、右之分，且其次序不能任意颠倒
基本形态
二叉树性质
性质1：«几种特殊形式的二叉树
满二叉树
定义：u性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点
i(1£i£n)，有：
(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是ëi/2û
(2)如果2i>n，则结点i无左孩子；如果2i£n，则其左孩子是2i
(3)如果2i+1>n，则结点i无右孩子；如果2i+1£n，则其右孩子是2i+1
§6.3树的存储结构
树的存储结构
双亲表示法
实现：定义结构数组存放树的结点，每个结点含两个域：
数据域：存放结点本身信息
双亲域：指示本结点的双亲结点在数组中位置
特点：双亲容易，孩子难
孩子表示法
多重链表：每个结点有多个指针域，分别指向其子树的根
结点同构：结点的指针个数相等，为树的度D
结点不同构：结点指针个数不等，为该结点的度d
孩子兄弟表示法（二叉树表示法）
实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点
特点
操作容易
破坏了树的层次
二叉树的存储结构
顺序存储结构
实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素
特点：
结点间关系蕴含在其存储位置中
浪费空间，适于存满二叉树和完全二叉树
链式存储结构
二叉链表
树与二叉树转换
森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构
§6.4树和二叉树的遍历
树的遍历
遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即一个完整而有规律的走法，以得到树中所有结点的一个线性排列
常用方法
先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树
后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点
按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点
二叉树的遍历
方法
先序遍历：先访问根结点，然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后序遍历：先后序遍历左、右子树，然后访问根结点
l按层次遍历：从上到下、从左到右访问各结点
算法
递归算法
§6.5二叉树的应用

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。