数据结构与算法知识汇总1
需积分: 0 194 浏览量
2022-08-04
00:11:46
上传
评论
收藏 357KB PDF 举报
1
【第一章：绪论】
1. 通常，用 O(1)表示常数计算时间。常见的渐进时间复杂度按数量级递增排列为：
O(1) < O(
2
log
n) < O(n) < O(n
2
log
n) < O(
2
n
) < O(
3
n
) < O(
n
2
)
2. 程序一定是算法：算法和程序的一个重要区别在于，程序不一定是有穷的，而算法必须
是有穷的。也就是说，一个算法必须具有有穷性，而程序则不一定。
【第二章：线性表】
3. 对于如下语句的理解：
typedef struct node
{
int data;
struct node *next;
}LNode,*LinkList;
这是定义一个结构体，这个结构体有两个属性，一个是 int 类型的 data; 另一个是这个结构
体本身类型的指针 next;
给这个结构定义了一个别名:LNode，一个指针别名:LinkList;
LNode a; 等价于 struct node a; 声明一个 struct node 结构体类型的结构体变量 a;
LinkList b; 等价于 struct node *b; 等价于 LNode *b; 声明一个 struct node 结构体类型的
指针变量 b;
4. 通常，“较稳定”的线性表选择顺序存储，而频繁做插入删除等“动态性”较强的线性
表宜选择链式存储。(线性表的存储分为顺序存储以及链式存储)
5. 【单链表逆置】算法思想：分为带头结点和不带头结点两种情况；
（1）带头结点的单链表逆置：保存第一个数据结点（即头指针指向的头结点的下一个结点）
至 p,此时，可以通过 p 访问到链表中的每一个结点。这时将原链表置空，再将 p 指向的结点
保存在 q 中，并让 p 指向 p 的下一个结点，将 q 插入头结点后即可。（利用了前插法）
代码如下：
void reverseWithHeadNode(LinkList H)
{
LNode *p,*q;
p = H->next;//让 p 指向第一个数据结点；
H->next = NULL;//原链表置空；
while(p)
{
q = p;//将当前数据结点保存在 q 中；
p = p->next;//当前结点指向下一个；
//将 q 插到头结点后；
q->next = H->next;
H->next = q;
}
}
（2）不带头结点的单链表逆置：新建一个空表 p，让 q 指向待操作的表。保存当前处理结
剩余11页未读，继续阅读
艾法
- 粉丝: 19
- 资源: 319
最新资源
- Picasso_v3.1 2.ipa
- chromedriver-mac-arm64.zip
- 蓝zapro.apk
- chromedriver-linux64.zip
- UCAS研一深度学习实验-MNIST手写数字识别python源码+详细注释(高分项目)
- 基于Python和PyTorch框架完成的一个手写数字识别实验源码(带MINIST手写数字数据集)+详细注释(高分项目)
- 基于Matlab在MNIST数据集上利用CNN完成手写体数字识别任务，并实现单层CNN反向传播算法+源代码+文档说明(高分项目)
- NVIDIA驱动、CUDA和Pytorch及其依赖
- 基于SVM多特征融合的微表情识别python源码+项目说明+详细注释(高分课程设计)
- html动态爱心代码一（附源码）
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0