资源描述：
《数据结构复习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、«算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列栈:是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底，最后插入的最先删除。队列：是允许从一头插入另一端删除的线性表，允许删除的叫对头，允许插入的叫队尾，最先插入的最先删除。循环队列：递归：在一个函数结束本函数之前，直接或间接调用本身函数数据：描述客观事物的符号数据元素：数据的基本单位数据结构：数据元素和数据元素关系集合数据项:有独立含义的数据的最小单位数据结构的两要素：数据元素集合、数据元素之间的关系集合数据结构的形式定义为：数据结构是一个二元组Data_Structu
2、re＝（D，R）其中，D是数据元素的有限集，R是D上关系的有限集。数据结构概念包括：数据的逻辑结构、数据的存储（物理）结构、数据的操作算法的评价：正确性、可读性、健壮性、效率高效和低存储算法特性：有穷性、确定性、可行性、输入、输出线性表：在数据元素非空的有限集合中，存在唯一叫做“第一个”和最后一个的数据元素线性表定义：一个线性表是n个数据元素的有限序列顺序表：用一组地址连续的存储单元存放一个线性表顺序表的特点：实现物理地址相邻，随机存取，用一维数组实现顺序表优点：实现物理地址相邻，可随机存取，结构紧凑顺序表缺点：空间浪费，表容量难以扩充，插入或删除操作需要大量移动线性链表：节点中
3、只含一个指针域的链表线性链表的特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的数据元素每个数据元素，出来存储本身信息外，还需存储其直接后继的信息单链表特点它是一种动态结构，整个存储空间为多个链表共用不需要预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表循环链表中最后一个节点的指针指向头节点，是链表构成环状特点：从表中任一节点出发均可找到表中其他节点，提高查找效率约瑟夫环栈：限定仅在表尾进行插入或删除操作的线性表入栈算法intpush(ints[],intx,inttop){if(top==M){printf("over
4、flow");return(-M);}s[top]=x;return(++top);}出栈算法：intpop(ints[],inttop,int*q){if(top==0){printf("stackempty");return(0);}*q=s[--top];return(top);}栈的应用：回文和进制转换，斐波那契计算器队列：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表（先进先出）队尾——允许插入的一端对头——允许删除的一端判断队空和队满：少用一个空间：队空：front==rear队满：(rear+１) ％M==front入栈算法：voiden_cycqu
5、e(intsq[],intfront,intrear,intx){if(((rear+1)%M)==front)printf("overflow");else{rear=(rear+1)%M;sq[rear]=x;}}出栈算法：intdl_cycque(intsq[],intfront,intrear,int*q){if(front==rear)return(0);else{front=(front+1)%M;*q=sq[front];return(1);}}队列的应用：走迷宫、划分子集查找方法评价：查找速度、占用存储空间多少、算法本身复杂程度、平均查找长度平均查找长度ASL：为
6、确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值折半查找：使用条件：采用顺序存储结构的有序表分块查找：查找过程：将表分成几块，快内无序，块间有序；先确定待查记录所在快，再在快内查找适用条件：分块有序表哈希查找：在记录的关键字与记录的存储地址之间建立的一种对应关系基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系，这样，不经过比较，一次存取就能得到所查元素的查找方法冲突：key1¹key2，但H(key1)=H(key2)的现象同义词：具有相同函数值的两个关键字哈希函数的构造方法：直接定址法（不会发生冲突）、平方取中法（适用于不知道全部关键字的情况）、折
7、叠法（种类：移位叠加、间界叠加，适用关键字位数很多，且每位上数字分布大致均匀情况）、除留余数法、随机数法（适用于关键字长度不等的情况）选取哈希函数，考虑的因素：计算哈希函数所需时间关键字长度哈希表长度关键字分布情况记录的查找频率处理冲突的方法：开放定址法分类：u线性探测再散列：di=1,2,3,……m-1u二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(k£m/2)u伪随机探测再散列：di=伪随机数序列再哈希法链地址法方法：将所有关键字为同义词的记录存储在一个
