计算机二级公共基础(超级)..docxVIP

算法与数据结构算法定义：指解题方案的准确而完整的描述。（不等于程序，也不等于计算方法）基本特征 可行性确定性有穷性——有限个步骤后终止（有限时间内终止）拥有足够的情报四种基本运算与操作：算术运算 逻辑运算 关系运算 数据传输三种基本控制结构：顺序结构 选择结构 循环结构基本设计方法 列举法 归纳法 逆推 逆归 减半递推技术 回溯法指令系统：一个计算机系统能执行所有指令的集合。复杂度 时间复杂度——执行算法所需的计算工作量空间复杂度——执行算法所需的内存空间一种逻辑结构可以有多种存储结构不同存储结构影响效率逻辑结构：对数据元素之间的逻辑关系的描述存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式1.2.1数据结构定义：相互关联的数据元素的集合研究的三个方面逻辑结构 一对多顺序存储结构链接索引等顺序存储方式——主要用于线性的数据结构——它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的相邻衔接关系来体现链式存储结构——在每个节点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系1.2.2线性结构和非线性结构根据数据元素结构中的各数据元素之间前后件关系的复杂程度对于一个非空的数据结构 线性结构 有且只有一个根结点（线性表） 每个结点最多有一个前件，也最多有一个后件非线性结构：不是线性结构在一个线性结构中插入或删除任何一个结点后还是线性结构线性结构：栈、队列、串；循环队列、带链队列、带链栈非线性结构：数组、广义表、树（例二叉树）和图线性表是最简单的最常用的一种线性结构，线性链表指的是采用链式存储结构的线性表，栈和列是一种特殊的线性表，树是一种简单的非线性结构，二叉树是树的一种。线性与非线性是从数据的逻辑结构角度来讲，与该数据结构中含有多少个元素无关，即使是空的二叉树也是非线性结构有序线性表既可以采用顺序存储结构，又可以采用链式存储结构线性表的顺序存储结构具有以下两个基本特点：线性表中所有元素所占的存储空间是连续的线性表中各元素所占的存储空间中是按逻辑顺序依次存放的元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k, ADR(a1)为第一个元素地址，k代表每个元素占的字节数顺序表的运算：查找、插入、删除3种1.3 栈 （先进后出）（后进先出）（子弹匣）限定在一端进行插入与删除的线性表（既可以顺序存储，又可以链式存储）栈顶——允许插入与删除元素的一端栈底——封闭的一端，栈底指针不变栈顶总是最先被删除的一端栈底总是最先被插入的一端栈的基本运算入栈——栈顶插入退栈——取栈顶元素并赋给一个指定变量读栈顶元素：将栈顶元素赋给一个指定的变量。栈具有记忆作用在栈中，栈底指针不变，栈中元素随栈顶指针变化而动态变化与栈结构关联：子程序的调用1.4队列（先进先出）（后进后出）（火车进隧道）只允许一段插入，另一端删除的顺序表（顺序存储）队头——允许删除队尾——允许插入队列运算入队——插入元素退队——删除元素与队列结构有关联： “先到先服务”的作业调度循环队列定义：队列存储空间的最后一个位置绕到第一个位置形成逻辑上的环状空间，供队列循环使用循环队列作为特殊的队列，也是线性结构循环队列中，队尾指针既可以大于队头指针，也可以小于。队列是一种逻辑结构，而循环队列是一种顺序存储结构的队列循环队列中的元素个数由队头指针和队尾指针共同决定※ 求循环队列中的元素个数？队尾指针（rear) 队头指针（front） m为队列容量入队（rear=rear+1） 退队（front=front+1）元素个数为 rear-front , rearfront ; rear-front+m , rearfront;当容量为Q(1:m)，初始状态为rear=front=m，经修改（入队或退队），rear=front=n,则元素个数为0或m1.5链表链式存储一部分为数据域一部分为指针域线性表的链式存储方式比顺序存储方式存储空间要更大一些线性表的存储分为顺序存储和链式存储线性表 顺序存储—存储空间连续 链式存储---可连续也可不连续链式存储 线性结构 非线性结构链式存储既可以存储有序表也可以存储无序表在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致（且各元素的存储顺序是任意的）在线性链表中进行插入与删除，不需要移动链表中的元素线性单链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表如果是双项链表的两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点线性链表的基本运算：查找、插入、删除带链的栈栈也是线性表，也可以采用链式存储结构可利用栈：带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的