数据结构期末复习提纲

数据结构课程总结数据结构课程总结课程目的与任务：系统地介绍软件设计中常用的几种数据结构和相应的存储结构和算法及分析方法，以及常用的几种查找和排序算法。学习组织、处理数据的理论和方法，建立良好的编程风格，进一个培养数据的抽象能力通过该课程的学习，为后续课程的学习以及软件设计水平的提高打下良好基础。2考试形式考试形式课堂考勤-----------------------10%实验程序检查情况-----------10%实验报告-----------------------10%期末考试-----------------------70%单项选择题 （20分）判断题 （10分）简答题 （36分）算法阅读题 （20分）算法设计题 （14分）3绪论逻辑结构存储结构线性结构非线性结构

线性表栈队列串数组广义表树、二叉树、森林图顺序存储结构链式存储结构索引存储结构散列存储结构数据结构算法算法的基本特征算法分析针对数据结构的各种基本算法及应用计算机科学领域两大核心课题4线性表线性表顺序表链表线性链表（单链表）单循环链表双向链表双向循环链表逻辑结构存储结构及特点基本操作（算法)及分析建立遍历插入删除查找合并(a1,a2,…,an)5栈栈顺序栈链栈初始化空栈入栈出栈取栈顶判栈空an……a2a1栈底栈顶入栈出栈逻辑结构存储结构基本操作（算法）典型应用数制转换表达式求值栈与递归（函数调用）语法检查6队列

队列链队列顺序队列（循环队列）初始化队列入队出队取队头判队空、满逻辑结构存储结构及特点基本操作（算法）典型应用作业调度离散事件模拟……队头队尾入队列出队列anan-1…a3a2a17串s=＂a1a2……..an＂串逻辑结构存储结构基本操作(运算)串的比较串的连接求子串子串定位（模式匹配）BF算法KMP算法顺序存储结构链式存储结构定长顺序存储（静态）堆分配存储（动态）块链结构单字符结点链8数组数组行优先（行主序）列优先（列主序）数组的定义和基本操作数组的顺序表示矩阵的压缩存储及运算特殊矩阵稀疏矩阵对称矩阵三角矩阵对角矩阵三元组顺序表带行逻辑链接的顺序表十字链表9广义表广义表表的长度表的深度非空表的表头和表尾定义

基本操作存储结构（链式存储）（a1,a2,a3,…,an

）10树、二叉树、森林1.定义和性质2.存储结构3.遍历4.线索化顺序结构链式结构二叉链表三叉链表先序线索树中序线索树后序线索树树二叉树森林Huffman编/译码先序遍历中序遍历遍历存储结构遍历孩子--兄弟先根遍历后根遍历线索二叉树Huffman树应用中序遍历后序遍历先序遍历层次遍历11图存储结构遍历邻接矩阵邻接表十字链表邻接多重表深度优先搜索广度优先搜索无向图的应用应用图的连通分量图的生成树最小生成树Prim算法Kruskal算法最短路径Dijkstra算法Floyd算法有向图的应用拓扑排序(AOV网)关键路径问题(AOE网)图12查找比较式查找法计算式查找法基于线性表的查找法（静态查找）基于树的查找法（动态查找）(HASH查找法)顺序查找法折半查找法分块查找法二叉排序树

平衡二叉树哈希函数构造方法哈希冲突解决方法哈希查找过程及性能分析直接定址法数字分析法平方取中法

除留余数法折叠法开放定址法再哈希法链地址法公共溢出区线性探测再散列二次探测再散列13排序基本概念排序的分类排序算法的分析时间复杂