C语言基础知识点

指针

保存地址的变量

int i;  
int *p = &i;

指针变量：

• 变量的值是内存的地址
• 普通变量的值是实际的值
• 指针变量的值是具有实际值的变量地址

*是一个单目运算符

• 用来访问指针的值所表示的地址上的变量

• 可以做右值也可以做左值

• int k = *p;
  *p = k+1;
  

左值：

• 出现在赋值号左边的不是变量，而是值，是表达式计算的结果
• 特殊的值，所以叫左值

数组变量是特殊的指针

• 数组变量本身表达地址，所以 int a[10]; int *p = a;//无需用&取地址
• 但数组的单元表达的是变量，需要用&取地址 a == &a[0];
• []运算符可以对数组做，也可以对指针做： p[0] <==> a[0]
• *运算符可以对指针做，也可以对数组做： *a = 25;
• 数组变量是const的指针，所以不能被赋值

*P++:

• 取出p所指的那个数据来，完事之后顺便把p移到下一个位置去
  *的优先级虽高，但是没有++高
• 常用于数组类的连续空间操作
• 在某些cpu上，这可以直接被翻译成一条汇编指令

字符串：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-u4BbgeqV-1637722943581)(images1632396073955.png)]

• 字符串可以表达为char*的形式
• char*不一定是字符串
• 本意是指向字符的指针，可能指向的是字符的数组(就像int*一样)
• 只有它所指的字符串数组有结尾的0，才能说所指的是字符串

绪论

数据结构+算法=程序

算法：解决问题的步骤

程序：对问题的具体代码实现

数据结构

被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

数据结构三要素： 逻辑结构：

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的**

存储结构/物理结构

• 一个数据结构在计算机中 映像 称为存储结构
• 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。
• 它包括数据元素的表示和关系的表示。
• 数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

四种基本存储方法：

顺序存储、链式存储、索引存储和散列存储

顺序存储特点:

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构

1. 随机存取表中元素。
2. 插入和删除操作需要移动元素，不便于插入和删除操作
3. 存储密度大

链式存储特点：

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)

1. 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2. 逻辑上相邻的节点物理上不必相邻。
3. 插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4. 查找结点时链式存储要比顺序存储慢。
5. 每个结点是由数据域和指针域组成。

索引存储特点：

除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成

1. 检索速度快
2. 用结点的索引号来确定结点存储地址

缺点是增加了附加的索引表,会占用较多的存储空间。

散列存储特点：

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术

1. 散列的数据访问速度要高于数组
2. 由节点的关键码值决定节点的存储地址

数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

最常用的5种方法：

插入、删除、修改、排序、查找

线性数据结构：

线性表、栈、队列、数组、串、双端队列

非线性数据结构：

集合机构、树形结构、图状结构

多型数据类型：

数据元素的类型不确定

数据的物理结构：

数据元素的表示 和 数据元素间关系的表示

抽象数据类型：

它的定义仅取决于它的一组 逻辑特性，与 计算机内部如何实现无关，即不论其内部结构如何变化，只要它的 数学特性 不变，都不影响其外部使用

评价算法的两个重要指标：

时间复杂度、空间复杂度

时间复杂度：

• 语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级
• 记作：T(n)=O(f(n))
• 它表示随问题n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度

空间复杂度：

• 算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数

最坏情况与平均情况：

• 最坏情况运行时间是一种保证，那就是运行时间将不会再坏了。 在应用中，这是一种最重要的需求， 通常， 除非特别指定， 我们提到的运行时间都是最坏情况的运行时间
• 平均运行时间是所有情况中最有意义的，因为它是期望的运行时间
• 一般在没有特殊说明的情况下，都是指最坏时间复杂度

算法 算法特性：

有穷性、确定性、可行性、有零个或多个输入、有零个或多个输出

算法是由若干条指令组成的有穷的序列 算法性质：

输入、输出、确定性、有限性

数据结构和数据类型区别：

• 数据结构定义了一组按某些关系结合在一起的数组元素。（只定义）
• 数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。（即定义又操作）

线性结构和非线性结构区别：

• 线性结构反映结点间的逻辑关系是 一对一的。
• 非线性结构反映结点间的逻辑关系是多对多的。

TIP

• 算法的计算量的大小称为计算的复杂性**
• 算法的时间复杂度取决于
  • 问题的规模
  • 待处理数据的初态
• 计算机算法指：解决问题的步骤序列，它必须具备
  • 可执行性
  • 确定性
  • 有穷性
• 算法是问题求解步骤的描述
• 逻辑上，数据结构可分为 线性结构、非线性结构
• 栈：与数据的存储结构无关
• 连续存储设计是、存储单元的地址 一定连续
• 计算机中最小的数据单位是“位”
• **数据项**是数据结构中讨论的最小单位，是数据记录中最基本的、不可分的有名数据单位
• 数据的**物理结构**是指数据在计算机内地实际存储形式
• 对于给定的n个元素,可以构造出的逻辑结构有：集合，线性结构 ，树状结构 ，图状结构

线性表 栈 队列 顺序表与单链表物理位置

顺序表中逻辑上相邻的元素物理位置 必定 相邻。

单链表的逻辑上相邻元素物理位置 不一定 相邻

存储密度:

在计算机中是指结点数据本身所占的存储量和整个结点结构所占的存储量之比

计算公式：存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量）

头指针、头节点、首元结点 首元节点：

指：链表中存储线性表中第一个数据元素a1的节点。

头节点：

为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理

头指针：

指向链表中第一个结点（或为头节点或为首元结点）的指针。

PS：

若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题

栈防止上溢：

了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间时，应将两栈的 栈底 分别设在这片内存空间的两端，这样，只有当 两个栈的栈顶在达栈空间的某一为位置相遇 时，才产生上溢

线性表、栈、队列异同点： 同：

1. 都是线性结构、逻辑结构的概念
2. 都可以用顺序存储或链表存储
3. 栈和队列时特殊的线性表，受限的线性表。只是对插入、删除运算加以限制

不同：

1. 运算规则不同
   1. 线性表为随机存取
   2. 栈只允许一段进行插入、删除运算，后进先出
   3. 队列只允许一段插入，另一端删除，先进先出
2. 用途不同
   1. 堆栈用于子工程调用和保护现场
   2. 对了用于多道作业处理、指令寄存及其他运算

假溢出： 原因：

一般的一维数组队列的位置在已经到了数组的上界，不能在有入队操作，但其实数组中还有空位置，这就叫做‘假溢出’。

解决：

采用循环队列解决此问题

判断循环队列是空还是满：

1. 设置一个布尔变量以区别队满还是队空
2. 浪费一个元素的空间，用于区别队满还是队空
   1. 即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素
3. 使用一个计数器记录队列中元素个数（即队列长度）
4. 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N

TIP

• 线性表是具有n个 数据元素 的有限序列
• 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间
• 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( 带头结点的双循环链表 )最节省时间
• 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ 带头结点的双循环链表 ）存储方式最节省运算时间
• 静态链表中指针表示的是 下一个元素地址
• 链表不具备 随机访问任意元素的特点
• 线性表在链式存储时，查找第i个元素的时间同i的值成正比
• 线性表在顺序存储时，查找第i个元素的时间同i的值无关
• 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素
• 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素
• 线性表中结点的集合是**有限**的，其中结点间的关系是 一对一 的
• 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构
• 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）
• 链表的存储结构特点是无序的，而链表的示意图有序
• 链表的结点不会移动，只是指针内容改变
• 顺序表适合随机存取，链表适于“顺藤摸瓜”
• 顺序存储方式的优点是存储密度大，且 插入、删除运算效率较低
• 顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，
  • 例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式
• 向一个有N个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 N/2 个元素
• 单链表的存储密度 小于1
• 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
• 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
• 在具有N个单元的循环队列中，队列满时共有 N - 1 个元素
• 带表头结点的空循环双向链表的长度等于 0
• 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表，都是线性逻辑结构，对于运算的定义略有不同
• 栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项
• 栈和队列的存储方式既可是顺序方式，也可是链接方式
• 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为： （n＋r－f）% n
• 向地址的高端生长，称为向上生成堆栈；向地址低端生长叫向下生成堆栈

串 数组 三元组表：

• 将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表
• 三个数据项
  1. 行下标
  2. 列下标
  3. 元素值

TIP：

• 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功
• 若N为主串长，M为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为： (N - M + 1) * M
• 串是一种特殊的线性表，其特殊性体现在 数据元素是一个字符

树

结点：

使用树结构存储的每一个数据元素都被称为“结点”

度：

一个结点的儿子结点个数称为该结点的度。一棵树的度指树中结点的最大度数

叶结点/终端结点：

树中度为零的结点

分支结点/非终端结点：

树中度不为零的结点

内部结点：

除根节点外的分支结点

树的高度：

指根结点的高度

TIP:

• 若二叉树用二叉链表作存储结构，则在 N 个结点的二叉树链表中只有 N - 1个非空指针域
• 二叉树中每个节点的两棵子树是有序的
• 用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。
  • 由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个
• 一颗完全二叉树有 N 个结点，则共有 N/2 个叶子结点， 有 N/2 - 1个度为2的结点
• 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树（最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝****0）
• 前/中/后 序遍历的递归算法
  • 平均空间复杂度为 O(n)
  • 时间复杂度为O(n)
• 不含任何结点的空树是一棵树也是一颗二叉树
• 二叉树是非线性数据结构，所以顺序存储结构和链式存储结构都能存储
• 有N个结点的完全二叉树的深度为： log2(n) + 1
• 一个树转换为二叉树后，这棵二叉树的形态是 唯一的
• 完全二叉树中 若一个结点没有 左子结点，则它必定是叶结点
• 一颗度为2的树 与 一颗二叉树的区别
  • 度为2的树 从形式上看似二叉树，但它的子树是无序的。
  • 在一般树中若某结点只有一个孩子，就无需区分其左右次序
  • 二叉树中即使是一个孩子也有左右之分
• 只有一个结点的二叉树的度为 0
• 深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树

图 定义：

• 由顶点的有穷非空集合和顶点之间边的集合组成，通常标识为G=(V,E)
• V是顶点的非空有限集
• E是V中顶点对， 即边的有限集

顶点：

• 在图中的数据元素通常叫做顶点

有向图：

• 若图中的每条边是有向的，则称为有向图
• 一条有向边是顶点的有序对

无向图：

• 若图中的每条边都是没有方向的，则称为无向图
• 无向图中的边表示图中顶点的无序对
• 无向图中 (u,v)和(v,u)表示同一条边
  -

完全图： 无向完全图：

• 在无向图G=（V,E）中，如果任意两个不同的顶点都是邻接的，那么就称该图为无向完全图 如图所示可以证明在一个含有N个顶点的无向完全图中有n*（n-1）/2边

有向完全图：

• 在一个有向图G=（V,E）中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图，如图所示，在一个含有n个顶点的有向完全图中，有n(n-1)条边

弧：

弧是顶点的有序对，记作, 其中v，w是顶点，v称为弧尾，w称为弧头称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v

度： 无向图顶点的度：

顶点v的度是和顶点v相关联的边的数目，记作TD(v)

有向图顶点的度：

1. 入度：一个顶点拥有的弧头的数目 记作ID(v)
2. 出度：一个顶点拥有的弧尾的数目称为出度，记作 OD（v）
3. 度： 一个顶点拥有的入度 + 出度

关联：

• 若(u,v)是一条无向边，则称顶点u和v互为邻接点 / 或者 u和v相邻接；并称边(u,v)关联与顶点u和v，或称边(u,v)与顶点u和v相关联。

简单图：

一个图G若满足：

1. 不存在重复边
2. 不存在顶点到自身的边

称G为简单图

多重图：

若图G中某两个结点之间的变数多于一条，又允许顶点通过同一条边和自己关联，则称为多重图

子图：

设G=(V,E) 是一个图，若V’ 是V的子集， E’是E的子集，且E’中的边所关联的顶点均在V’中，则G’=(V’,E’)也是一个图，并称其为图G的一个子图