《数据结构(C语言版)》笔记

Published: November 02, 2020 by Authur Lee

本博客主要是将一些不易注意到的知识点、易错点以及易忘点整理一下，更多的是用来补充学习而非系统学习。

二、线性表

指针为数据元素之间的逻辑关系的映像。

静态链表中，为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过以及被删除的分量用游标链成一个备用的链表。

(清华版本的说法)用top = 0表示空栈。

(清华版本的说法)对于循环队列，判断队列空间为空或者满的两种处理方法：其一是另设一个标识位；其二是少用一个元素空间，约定“队列头指针在队列尾指针的下一位置”上作为队列“满”的标志。

串值必须用一对单引号括起来。

串的块链存储表示中，设尾指针的目的是为了便于进行联结操作，但注意联结时需要处理第一个串尾的无效字符。

串的字符集的大小也是一个影响字符串处理效率的重要因素。一般来说，字符集越小，则字符的机内编码就短，这也影响串值的存储方式的选取。

线性表、栈和队列(操作受限的线性表)、串都是非结构的原子类型，元素的值是不再分解的。数组和广义表可以看作是线性表的拓展，表中的元素本身也是一个数据结构。

在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。

矩阵中的下标一般从1开始，但是还是要具体问题具体分析(题目会告诉我们)。

【对稀疏矩阵进行压缩的目的】节约存储空间(更主要)，降低运算的时间。

【稀疏矩阵】假设在m*n的矩阵中，有t个元素不为零。称 $稀疏因子$ 为矩阵的稀疏因子，一般来说，稀疏因子小于等于0.05时称为稀疏矩阵。

稀疏矩阵的三元顺序表中，为了便于随机存取任意一行的非零元，需知道每一行的第一个非零元在三元组表中的位置。为此，可将指示“行”信息的辅助数组固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表。

两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，每个对应分量相乘不为零，其累加值也可能为零。

在对广义表进行的操作下的递归定义时，有两种分析方法：一种是把广义表分解成表头和表尾两部分；另一种是把广义表看成是含有n个并列子表(假设将原子也视为子表)的表。

树的其他三种表示法：1.嵌套集合的形式；2.广义表的形式；3.凹入表示法(类似书的目录)。

存储二叉树的其中两种结构：二叉链表和三叉链表(多了一个指向parent的指针)。

线索化二叉树的过程即为在遍历的过程中修改空指针的过程。

由于哈夫曼树中没有度为1的结点(这类树又称为严格的(或正则的)二叉树)。

性质MST:假设G = (V,E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含边(u,v)的最小生成树。

MST是最小生成树的一种性质的简称，内容如上。

拓扑排序如何在计算机中实现？我们采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组indegree。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换为以弧头顶点的入度减一来实现。

下面是一些比较少见的内部排序算法，之后会有博客专门介绍。