冲刺拼搏，在前进中寻找乐趣。二级 C 语言公共基础知识之 数据结构考点 1 算法的复杂度1．算法的基本概念算法的基本特征：可行性、确定性、有穷性、输入（可为 0）、输出(不能为 0)2．算法复杂度 包括时间复杂度和空间复杂度名称描述时间复杂度是指执行算法所需要的计算工作量空间复杂度是指执行这个算法所需要的内存空间考点 2 逻辑结构和存储结构1．逻辑结构2．存储结构考点 3 线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度一般将数据结构分为两大类型：线性结构与非线性结构假如一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件也最多有一个后件则称该数据结构为线性结构线性结构又称线性表在一个线性结构中插入或删除任何一个结点后还应是线性结构栈、队列、串等都线性结构假如一个数据结构不是线性结构则称之为非线性结构数组、广义表、树和图等数据结构都是非线性结构考点 4 栈1．栈的基本概念栈（stack）是一种特别的线性表是限定只在一端进行插入与删除的线性表在栈中一端是封闭的既不允许进行插入元素也不允许删除元素；另一端是开口的允许插入和删除元素通常称插入、删除的这一端为栈顶另一端为栈底当表中没有元素时称为空栈栈顶元素总是后被插入的元素从而也是最先被删除的元素；栈底元素总是最先被插入的元素从而也是最后才能被删除的元素"先进后出"或"后进先出"2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素（2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量考点 5 队列1．队列的基本概念队列是只允许在一端进行删除在另一端进行插入的顺序表通常将允许删除的这一端称为队头允许插入的这一端称为队尾 当表中没有元素时称为空队列队列的修改是依照先进先出的原则进行的因此队列也称为先进先出的线性表或者后进后出的线性表例如：火车进遂道最先进遂道的是火车头最后是火车尾而火车出遂道的时候也是火车头先出最后出的是火车尾若有队列：Q =（q1q2...qn）那么q1 为队头元素（排头元素）qn 为队尾元素队列中的元素是根据 q1q2...qn 的顺序进入的退出队列也只能根据这个次序依次退出即只有在 q1q2...qn-1 都退队之后qn 才能退出队列因最先进入队列的元素将最先出队所以队列具有先进先...
