一、8.3：结构体指针与typedef的应用
二、8.4：C++引用
引用修改指针变量：
注意：引用必须与变量名紧挨着。
改为纯C语言的二级指针如下：
三、8.5：C++引用案例实战
结构体的存储与其他变量相同，若是malloc则是在堆中，其余则在栈中；
用malloc申请的结构体分布如下：
num与score存储在堆区；
C语言中期阶段
一、9.3：逻辑结构与存储结构
逻辑结构：树、图、线性表、集合
存储结构：顺序存储+链式存储
链式存储的数据结构定义代码：
typedef struct LinkNode
{
int data;
LinkNode* next;
}LinkN,*LinkList;
LinkList L = new LinkNode();二、9.4：算法的基本概念与时间复杂度
1、算法的五个基本特性：有穷、确定、可行、输入、输出
有穷：算法必须在有限的步骤内结束，不能陷入无限循环；
确定：算法的每一步必须是确定的，而不能有歧义；
可行：必须用已有的基本操作实现算法
2、O是同阶
时间复杂度的对比：
三、历年真题中求解时间复杂度
平均复杂度：各种输入等概率下的期望时间复杂度
时间复杂度的类型总结：
对于递增相加的i、j、k，直接相乘每一层循环即可；
类型1的两种情况均为O(n3)；
1、2022年（未掌握）：选B
2、2019年：掌握
3、2017年：未掌握，纠错在相册
4、2011年与2012年（均掌握）：
5、2014年：掌握
6、2025年真题
选B，简单
四、空间复杂度
空间复杂度包括：算法的空间复杂度与数据结构的空间复杂度，算法的空间复杂度是O(1)，只需关注数据结构即可。
1、函数递归调用带来的内存开销:
情况1：O(n)
情况2：
五、线性表中的涉及的真题
1、2010顺序表
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int* R = new int[n];
for (int i = 0; i < n; i++)
{
R[i] = i;
}
int* Q = new int[n];
int p;
cin >> p;
int j = 0;
for (int i = p; i < n; i++)
{
Q[j] = R[i];
j++;
}
for (int i = 0; i < p; i++)
{
Q[j] = R[i];
j++;
}
for (int i = 0; i < n; i++)
{
cout << Q[i] << ' ';
}
}时间复杂度：O(n) 空间复杂度：O(n)
2、
六、10.2：线性表的顺序表示原理解析
1、概念
相同类型元素、元素个数有限、唯一前驱与后继、逻辑结构
2、存储类型->线性表的顺序表示，顺序表
（1）概念：逻辑上相邻的元素物理上也相邻
（2）插入
判断插入位置是否合法：0≤i≤len
插入与删除的时间复杂度均为O(n)
3、真题
2023选择题：有一个小坑，查找有两种：顺序查找与折半查找，顺序查找是O(n)，折半查找是O(logN)；
所以选项A的最短时间是O(logN)
七、10.5：线性表的链式存储
1、数据结构定义
typedef struct
{
int data;
LinkNode* next;
}LinkNode,*Linklist;
Linklist LK = new LinkNode();
注意：链表最后一个节点的next值为NULL且要自行定义一个头节点
看题干怎么描述的吧：
八、头插法新建链表实战
#include<iostream>
using namespace std;
typedef struct LinkNode
{
int data;
LinkNode* next;
}LinkNode,*LinkList;
//要用引用,因为申请了头节点，所以不用单独处理第一个节点
void LHeadInsert(LinkList &L)
{
//为头节点申请空间
L = new LinkNode();
L->next = NULL;
int x;
cin >> x;
//开启while循环
while (x != 9999)
{
LinkList q = new LinkNode();
q->data = x;
q->next = L->next;
L->next = q;
cin >> x;
}
}
//打印出来
void printList(LinkList& L)
{
LinkList q;
q = L->next;
while (q)
{
cout << q->data << endl;
q = q->next;
}
}
int main()
{
//定义头节点
LinkList L;
//输入数据为3，4，5，6，7，9999
LHeadInsert(L);
//输出
printList(L);
}