1、 算法（ algorithm） 解决某一特定问题的具体步骤的描述，是指令的有限序列 栈 : 是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底，最后插入的最先删除。 队列：是允许从一头插入另一端删除的线性表，允许删除的叫对头，允许插入的叫队尾，最先插入的最先删除。 循环队列： 递归：在一个函数结束本函数之前，直接或间接调用本身函数 数据：描述客观事物的符号 数据元素： 数据的基本单位 数据结构： 数据元素和数据元素关系集合 数据项 :有独立含义的数据的最小单位 数据结构的两要素：数据元素集合、数据元素之间的关系集合 数据结构的形式定义为：数据结构是一个二元组 Da
2、ta_Structure （ D， R） 其中， D 是数据元素的有限集， R 是 D 上关系的有限集。 数据结构概念包括：数据的逻辑结构、数据的存储 （物理） 结构、数据的操作 算法的评价： 正确性、可读性、健壮性、效率高效和低存储 算法特性：有穷性、确定性、可行性、输入、输出 线性表：在数据元素非空的有限集合中，存在唯一叫做“第一个”和最后一个的数据元素 线性表定义：一个线性表是 n 个数据元素的有限序列 顺序表：用一组地址连续的存储单元存放一个线性表 顺序表的特点：实现物理地址相邻，随机存取，用一维数组实现 顺序表优点：实现物理地址相邻，可随机存取，结构紧凑 顺序表缺点： 空间浪费，表容
3、量难以扩充，插入或删除操作需要大量移动 线性链表：节点中只含一个指针域的链表 线性链表的特点： 用一组任意的存储单元存储线性表的数据元素 利用指针实现了用不相邻的存储单元存放逻辑上相邻的数据元素 每个数据元素，出来存储本身信息外，还需存储其直接后继的信息 单链表特点 它是一种动态结构，整个存储空间为多个链表共用 不需要预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢 循环链表 循环链表中最后一个节点的指针指向头节点，是链表构成环状 特点：从表中任一节点出发均可找到表中其他节点，提高查找效率 约瑟夫环 栈：限定仅在表尾进行插入或删除操作的线性表 入栈算法 int push(int s
4、,int x,int top) if(top=M) printf(“overflow“); return(-M); stop=x; return(+top); 出栈算法： int pop(int s,int top,int *q) if(top=0) printf(“stack empty“); return(0); *q=s-top; return(top); 栈的应用： 回文和进制转换 ，斐波那契计算器 队列：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表（先进先出） 队尾 允许插入的一端 对头 允许删除的一端 判断队空和队满： 少用一个空间： 队空： front = re
5、ar 队满： (rear + ) M = front 入栈算法： void en_cycque(int sq,int front,int rear,int x) if(rear+1)%M)=front) printf(“overflow“); else rear=(rear+1)%M; sqrear=x; 出栈算法： int dl_cycque(int sq,int front,int rear,int *q) if(front=rear) return(0); else front=(front+1)%M; *q=sqfront; return(1); 队列的应用： 走迷宫、划分子集 查找方
6、法评价： 查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度 平均查找长度 ASL：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值 折半查找：使用条件：采用顺序存储结构的有序表 分块查找： 查找过程：将表分成几块，快内无序，块间有序；先确定待查记录所在快，再在快内查找 适用条件：分块有序表 哈希查找：在记录的关键字与记录的存储地址之间建立的一种对应关系 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系，这样，不经过比较，一次存取就能得到所查元素的查找方法 冲突： key1key2，但 H(key1)=H(key2)的现象 同义词：具有相同函数值的两个关
7、键字 哈希函数的构造方法： 直接定址法（不会发生冲突）、平方取中法（适用于不知道全部关键字的情况）、折叠法（种类：移位叠加、间界叠加，适用关键字位数很多，且每位上数字分布大致均匀情况）、除留余数法、随机数法（适用于关键字长度不等的情况） 选取哈希函数，考虑的因素： 计算哈希函数所需时间 关键 字长度 哈希表长度 关键字分布情况 记录的查找频率 处理冲突的方法：开放定址法 分类： 线性探测再散列： di=1,2,3,m-1 二次探测再散列：di=1,-1,2,-2,3,k(km/2) 伪随机探测再散列： di=伪随机数序列 再哈希法 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，
8、并用一维数组存放头指针 排序：一个数据元素（记录）的任意序列，重新排列成一个按关键字有序的序列 排序分类 按待排序记录所在位置 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 按排序依据原则 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序： 2-路归并排序 基数排序 直接插入排序：整个排序过程为 n-1 趟插入，即先将序列中第一个记录看成一个有序子序列，然后从第 2 个记录开始，逐个进行插入，直至整个序列有序 折半插入排序：用折半查找方法确定插入位置的排序 希尔排序：先取一个正整数 d1n，把所有相隔 d1的记录放一组，组内进行直接插入排序；然后去 d2d1，重复上述分组和排序操作；直至 di = 1，即所有记录放进一个组中排序为止 冒泡排序： 快速排序：
