数据结构复习.doc

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