基于考研的C语言与数据结构指北
基于考研的C语言与数据结构指北
C语言与数据结构指北
写作背景
现在是2022年4月16日11点33分，还没吃午饭，我又emo了，望着王道数据结构长长的进度条，是不是来不及了。说实话，看视频是容易理解，但是视频也太长了吧…倍速又感觉怪怪的。但是看文档多快啊，可是网上的资料质量参差不齐，往往要点击较多的链接才能得到我们想要的答案，要于是萌发了写作此文的想法，也算是笔记，便于自己以后复习使用，当然不会面面俱到，主要是记录笔者认为重要的知识点。
warning：本文不是基于408的考试大纲，而是基于某211的考试大纲。
废话不多说，开始吧！
C.1 概述 C 程序的特点、算法性能分析与度量
概述 C 程序的特点
C程序的特点，首先应该了解的是C语言是一种过程性语言。
然后总结谭浩强第4版的内容，C语言有如下特点：
- 简洁、紧凑，方便、灵活。C语言仅有37个关键字、9种控制语句。
- 运算符足够丰富，共34种运算符：有哪34种及其作用，请前往C 运算符_w3cschool查看。
- 数据类型丰富
- 具有if…else\while等这些结构化的控制语句
- 语法限制不严格，强调灵活性。比如：对数组下标越界不作检查等等。
- 集成高级语言和低级语言的许多功能，能够直接访问物理地址，进行位运算，直接操作硬件。
- 程序可移植性好，几乎所有的操作系统都能使用C。
- 生成的目标代码（编译器或汇编器处理源代码后所生成的代码，它一般由机器代码或接近于机器语言的代码组成）质量高，程序执行效率高。
算法性能分析与度量
算法性能的度量是通过时间复杂度和空间复杂度。
这里默认大家都学习什么是时间复杂度和空间复杂度。
常见的时间复杂度有，从快到慢的排序为：
复杂度 | 名称 |
|---|---|
O(1) | 常数复杂度 |
O(logn) | 对数复杂度 |
O(n) | 线性复杂度 |
O(nlogn) | 线性对数复杂度 |
O(n2) | 平方复杂度 |
O(n3) | 立方复杂度 |
O(2n) | 指数复杂度 |
O(n!) | 阶乘复杂度 |
笔者以前在PTA上做过一道非常好的题目：
到了现在普遍内存空间过剩的情况下，空间复杂度似乎不是那么重要了。
如果输入值与程序占用的空间无关，空间复杂度就是0(1)，如果呈线性关系，那么就是O(n)，如果是n2的关系增长，那么就是O(n2)。
C.2 算法概述、算法的表示方法、结构化程序设计方法
算法概述
根据谭浩强第四版，广义的算法：为了解决一个问题而使用的方法和步骤。我们这里主要讲述计算机算法。计算机算法分为数值运算算法和非数值运算算法。
- 数值运算的目的是求数值解,例如求方程的根、求一个函数的定积分等,都属于数值运算范围。
- 非数值运算包括的面十分广泛,最常见的是用于事务管理领域例如对一批职工按姓名排序、图书检索、人事管理和行车调度管理等。
不过不是随便写一些语句就是算法，算法具有以下特性：
- 有穷性：步骤是有限的。
- 确定性：算法的步骤应当是确定的，不能产生歧义。
- 有（0或多个）输入和（1或多个）输出。
- 有效性：每一个步骤要能够执行，并且得到确定的结果。
怎样表示一个算法
可以用自然语言、流程图和伪代码表示。
考手画流程图感觉不现实~
自然语言能描述清楚估计就行了，不过以防万一，大家还是稍微了解一下。
平行四边形是输入输出、菱形是判断、长方形是一般的步骤。
谭浩强还提到了N-S流程图：
结构化程序设计方法
为了得到结构化的程序，我们需要使用这些方法：
- 自顶向下
- 逐步细化
- 模块化设计
- 结构化编码
C.3 数据类型、运算符与表达式
… 后续会继续更新