数据结构复习

1、数据结构梁春燕华电信息管理教研室主要内容复习串讲题目讲解关于考试复习串讲第一章 绪论数据结构的基本概念和术语：数据、数据元素、数据结构、数据类型抽象数据结构类型ADT的表示与实现算法和算法分析：特性、评价方法（时间空间复杂度）数据结构是什么？其研究的主要内容？类型？算法的评价？数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。 数据的逻辑结构 数据的存储结构 数据的运算：检索、排序、插入、删除、修改等 线性结构 非线性结构 顺序存储 链式存储 线性表栈队列树形

2、结构图形结构数据结构的三个方面：复习串讲第二章 线性表线性表的逻辑结构 ：一对一线性表的顺序存储结构（顺序表）：存储方式、特点、基本操作线性表的链式存储结构：存储方式、特点、基本操作单链表（静态链表）循环链表双向链表线性表的应用举例一元多项式的表示及相加（单链表）约瑟夫问题（循环链表）顺序存储和链式存储的优缺点？顺序存储结构优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充链式存储结构优点 动态结构，整个存储空间为多个链表共用，节省空间 不需预先分配空间，易扩充 插入、删除操作方便缺点

3、指针占用额外存储空间 不能随机存取，查找速度慢测试程序填空：1. 双向链表结点的删除void del_dulist(JD *p) p-prior-next=p-next; p-next-prior=p-prior; free(p);bcaPp-prior-next=p-next;p-next-prior=p-prior;复习串讲第三章 栈和队列栈的逻辑结构 、顺序存储结构、链式存储结构及其基本操作顺序栈：栈空、栈满链式栈：栈空队列的逻辑结构 、顺序存储结构、链式存储结构及其基本操作循环队列：队空、队满链式队列：队空栈和队列的应用数制转换、表达式计算、汉诺塔问题（栈）舞伴问题（队列）栈和队列的异

4、同？相同点 栈和队列都是特殊的线性表，是操作受限的线性表，称限定性DS不同点 栈 限定仅在表尾（栈顶）进行插入或删除操作的线性表 特点：先进后出（FILO）或后进先出（LIFO） 进栈、退栈操作队 列 限定只能在表的一端（队尾）进行插入，在表的另一端（队头）进行删除的线性表 特点：先进先出(FIFO) 进队、出队操作测试2. 循环队列的出队DataType deQueue(CirQueue *Q) DataType temp; if(queueEmpty(Q) Error(“队空n”); temp = Q-dataQ-front; Q-count-; Q-front = (Q-front+1)

5、%QueueSize; return temp;J4J5J6012345rearfront复习串讲第四章 串串及其运算数据元素约束为字符集的线性表基本操作：以串的整体作为操作对象，“子串”的操作串的长度 、串复制 、联接、串比较、求子串 串的存储结构顺序存储：定长顺序存储、堆分配存储链式存储：块链存储串的模式匹配算法简单匹配KMP算法串的存储方式的比较？ 定长顺序存储 顺序存储、串的长度固定 串的插入、联结：串的截断 串的插入、删除：移动元素 串的查找、定位：方便 堆分配存储 顺序存储、串的长度可变 串的插入、删除：移动元素 串的联结、查找、定位：方便 串的块链存储 链式存储、串的长度可变 占

6、用空间大、操作复杂复习串讲第五章 数组和广义表数组的定义和特点特殊的线性表，即线性表中数据元素本身也是一个线性表数组的顺序存储：行序、列序数组的压缩存储：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵数组的链式存储：带行指针向量的单链表、十字链表广义表的概念和表示稀疏矩阵的存储方式？稀疏矩阵（m行n列，t个非零元素，tm*n） 顺序存储方法：m*n 压缩存储方法 顺序存储结构 三元组表：3(t+1) 带辅助行向量的二元组表： 2(t+1)+m+1 伪地址表示法：2(t+1) 链式存储结构 带行指针向量的单链表表示：3t+m 十字链表：5t+m+n复习串讲第六章 树和二叉树二叉树二叉树的特点和性质二叉树

7、的存储结构：顺序、链式（二叉、三叉、线索）二叉树的遍历：先序、中序、后序、层次二叉树的线索化树树的存储结构：双亲、孩子、孩子兄弟表示方法树与二叉树转换森林与二叉树转换树和森林的遍历（与对应二叉树的遍历的关系）Huffman树Huffman树的建立：Huffman算法Huffman树的应用：Huffman编码树和二叉树的遍历算法的应用复习串讲第七章 图图的定义和术语图的存储结构：邻接矩阵、邻接表、有向图的十字链表、无向图的邻接多重表图的遍历：深度优先、宽度优先生成树和最小生成树：普里姆Prim算法、克鲁斯卡尔Kruskal算法图的应用：拓扑排序（AOV网）有向无环图关键路径（AOE网）带权的有向

8、无环图最短路径：迪杰斯特拉Dijkstra算法、弗洛伊德Floyd算法带权的有向图复习串讲第八章 查找静态查找表顺序查找折半查找分块查找动态查找表二叉排序树和平衡二叉树B-树和B+树哈希查找基本概念哈希函数的构造：直接定址法、数字分析法、平方取中法、折叠法、除留余数法冲突处理方法：开放地址法（线性、二次、伪随机）、再哈希法、链地址法哈希表的查找复习串讲第九章 排序排序的基本概念：排序的分类和基本操作插入排序：直接插入、折半插入和希尔排序交换排序：冒泡、快速排序选择排序：简单选择、堆排序归并排序： 2-路归并排序基数排序：链式基数排序不同排序方法的比较？排序方法平均时间辅助空间稳定性直接插入O(n2)O(1)稳定冒泡O(n2)O(1)稳定直接选择O(n2)O(1)稳定希尔O(n1.23)O(1)不稳定快速O(nlog n)O(log n)不稳定堆O(nlog n)O(1)不稳定归并O(nlog n)O(n)稳定基数O(d*n+d*rd)O(n+rd)稳定题目讲解二叉树的存储、遍历树、森林和二叉树的转换及其遍历图的存储结构和遍历Huffman树的建立和Huffman编码哈