基于考研的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)，如果是n²的关系增长，那么就是O(n²)。

C.2 算法概述、算法的表示方法、结构化程序设计方法 算法概述

根据谭浩强第四版，广义的算法：为了解决一个问题而使用的方法和步骤。

我们这里主要讲述计算机算法。

计算机算法分为数值运算算法和非数值运算算法。

• 数值运算的目的是求数值解,例如求方程的根、求一个函数的定积分等,都属于数值运算范围。
  

• 非数值运算包括的面十分广泛,最常见的是用于事务管理领域例如对一批职工按姓名排序、图书检索、人事管理和行车调度管理等。
  

不过不是随便写一些语句就是算法，算法具有以下特性：

• 有穷性：步骤是有限的。
  

• 确定性：算法的步骤应当是确定的，不能产生歧义。
  

• 有（0或多个）输入和（1或多个）输出。
  

• 有效性：每一个步骤要能够执行，并且得到确定的结果。
  

怎样表示一个算法

可以用自然语言、流程图和伪代码表示。

考手画流程图感觉不现实~

自然语言能描述清楚估计就行了，不过以防万一，大家还是稍微了解一下。

平行四边形是输入输出、菱形是判断、长方形是一般的步骤。

谭浩强还提到了N-S流程图：

结构化程序设计方法

为了得到结构化的程序，我们需要使用这些方法：

• 自顶向下
• 逐步细化
• 模块化设计
• 结构化编码

C.3 数据类型、运算符与表达式

…
后续会继续更新