C语言公共基础.doc

第一章算法和数据结构
第一课算法的概念
算法的定义
算法是指解决方案的准确而完整的描述,是一系列解决问题的清晰指令。
算法≠程序。
算法的5大特征
1. 至少1个输出:任何算法,必须有输出结果。
2. 至少0个输入,足够的情报:对于复杂算法,情报越充足,效果越好。
3. 有穷性:算法能在有限的执行步骤内、有限的时间内执行结束。
4. 可行性:算法的每一个步骤都必须能够翻译成计算机可执行的基本操作。
5. 确定性:算法的每一个步骤都必须描述准确,没有歧义。
算法的复杂度
【时间复杂度】
以基本操作次数的数量级计数,不以秒计数。
常见复杂度(越小越快):O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(2^n)<O(n!)
【空间复杂度】
算法执行过程中的空间开销。
【二者关系】
虽然算法中常常会以牺牲空间的方式来换取时间效率,但一般认为二者没有必然关系。
第二课数据结构的概念
数据结构的定义
数据结构是指计算机组织、存储数据的方式。
数据结构可分为逻辑结构和存储结构。
其中:
1. 逻辑结构又分为线性结构和非线性结构。
2. 存储结构又分为顺序存储结构和链式存储结构
逻辑结构
逻辑结构不关心数据如何存储,只关心数据的组织方式。
逻辑结构可分为线性结构和非线性结构。
典型线性结构:栈、队列
典型非线性结构:树(二叉树)、网状图
存储结构
存储结构不关心数据如何组织,只关心数据的存储方式。
存储结构又分为顺序存储结构和链式存储结构。
【顺序存储结构】
1. 所有元素在内存中按顺序排列
2. 查找、修改比较方便
3. 插入、删除比较不方便
【链式存储结构】
1. 所有元素在内存中随机分布
2. 插入、删除比较不方便
3. 查找、修改比较方便
4. 由于要存储下一元素的地址,所以需要更多的存储空间
【二者关系】
二者没有必然关系。
第三课栈
基本概念
1. 栈属于逻辑结构的概念,属于线性结构。
2. 栈既可以用顺序存储结构实现,也可以用链式存储结构实现。
3. 栈的特点是先进后出(FILO)。
4. 进出过程中,栈底指针不变,栈顶指针移动。
计算规则
视栈顶和栈底指针的指向规则而定。
一般的,栈底指向首元素的前一位置(比如0),栈顶指针指向尾元素(比如5),即栈中1、2、3、4、5各存储了一个数据。
此时:
栈中元素个数=栈顶指针-栈底指针(比如5-0=5)
第四课队列
基本概念
1. 队列属于逻辑结构的概念,属于线性结构。
2. 队列既可以用顺序存储结构实现,也可以用链式存储结构实现。
3. 栈的特点是先进先出(FIFO)。
4. 队头负责出队,队尾负责入队。
循环队列
循环队列是专门针对顺序存储结构空间固定的特点而设计的,所以一般认为循环队列是顺序存储结构。
其核心原理是:当队尾到达队列最大位置、而队头不在最小位置时如果继续入队,则队尾移至队列最小位置,从头开始移动,形成循环。出队时同理。
计算规则
视栈顶和栈底指针的指向规则而定。
一般的,队头指向首元素的前一位置,队尾指针指向尾元素。
假设队列容量为20:
1. 若队尾>队头(比如队尾为7,队头为2):
队列元素个数=队尾指针-队头指针(7-2=5)
2. 若队头>队尾(比如队尾为2,队头为7):
队列元素个数=队尾指针-队头指针+队列容量(2-7+20=15)
其中,第二种情况只有循环队列中才会出现。
第五课二叉树的计算
基本概念
1. 一个二叉树只有一个根节点。
2. 在二叉树中,任何一个节点最多只能有2个子节点。
3. 一个节点有几个子节点,则度为几。度为0的节点称为叶子节点。
常用公式
1. 第n层的节点数最多为2^(n-1)个。
2. 层数为n的二叉树,总节点数最多为2^n-1个。
3. 叶子节点数= 度为2的节点数+1
4. 二叉树节点总数= 度为2的节点数+ 度为1的节点数+ 叶子节点数
第六课二叉树的遍历
遍历规则
先序遍历:父节点、左子树、右子树
中序遍历:左子树、父节点、右子树
后序遍历:左子树、右子树、父节点
其中左右子树按此规则继续拆分,拆分过程中也按其对应规则遍历,直到不能再拆分为止。
第七课查找算法
顺序查找
其算法复杂度为O(n),长度为n的线性表,最多需要n次才能找到指定元素。
顺序查找最大/最小值
长度为n的线性表,所有元素随机排列,最多需要n-1次才能找到最大/最小值。
二分查找
其算法复杂度为O(logn),长度为n的线性表,最多需要logn次就能找到指定元素。
二分查找使用条件
1. 使用顺序存储结构(如数组)。
2. 所有