数据结构总复习及作业2015.ppt

数据结构总复习;;第一章 绪言 基本概念和术语（掌握） 数据结构，数据，数据元素，数据项 逻辑结构与存储结构 算法分析（掌握） 算法定义 算法特性： 算法评价： 时间复杂度与空间复杂度（了解）;第二章 线性表 逻辑结构（掌握） 存储结构（掌握） 顺序存储结构 链式存储结构 单链表 双向链表 循环链表 双向循环链表 静态链表（了解） 基本操作（掌握） 插入 删除 查找 应用------一元多项式相加（掌握）;第三章 栈和队列---操作受限的线性表 栈 特点（掌握） ：FILO(LIFO) 存储结构（掌握） ：顺序栈与链栈 基本操作（掌握） ：入栈与出栈 应用（掌握） ：回文、括号匹配、表达式求值;队列 特点（掌握） ：FIFO（LILO） 存储结构（掌握） ： 顺序队列 链队列 循环队列（掌握） 基本操作（掌握） 入队 出队 应用（了解）：迷宫，优先队列等;第四章 数组 线性结构 存储结构 顺序存储结构（掌握） ：次序约定 （算法实现不要求） 压缩存储（掌握） 对称矩阵 对角矩阵 三角矩阵 稀疏矩阵 算法：求转置矩阵（了解）;第五章 树 逻辑结构： 按分支关系定义的层次结构 定义（掌握）： 深度、度、叶子等 满二叉树、完全二叉树 二叉树性质（掌握） ：5 存储结构 树（掌握） 双亲表示法 孩子表示法（孩子链表与多重链表） 孩子兄弟表示法（二叉链表）;二叉树（掌握） 顺序存储结构 二叉链表 三叉链表 树、森林与二叉树转换（掌握） 遍历 按层次、先序、中序、后序 遍历递归（掌握）与非递归算法（了解） 遍历算法应用（掌握） 由先序序列建立二叉链表 统计叶子结点 求二叉树深度 已知先序和中序序列，构造二叉树;应用 Huffman树（掌握） 定义，WPL 构造方法 有n个叶子结点的Huffman树共有2n-1个结点 应用 Huffman编码与译码 最佳判定树;第六章 图 定义（掌握） ：图、有向图、度、连通、完备图等 存储结构 邻接矩阵（掌握） 邻接表与逆邻接表（掌握） 十字链表（了解） 邻接多重表（了解） 遍历：深度优先与广度优先（掌握遍历策略及算法）深度优先生成树、广度度优先生成树;应用（掌握求解过程，不要求写算法 ） 最小生成树（Prim与Kruscal） 拓扑排序 最短路径（Dijkstra） ;第七章 查找 静态查找表 顺序查找（掌握） 折半查找（掌握） 分块查找（了解） 动态查找表（了解） 二叉排序树 定义 构造方法 生成、插入、删除与查找 中序遍历二叉排序树可得到结点有序序列;哈希查找（掌握） 定义、基本思想 Hash函数构造方法 处理冲突方法 哈希表构造 哈希查找过程与ASL;第八章 排序 掌握排序的 基本概念和性能分析方法，排序策略 插入排序 直接插入排序（掌握） 折半插入排序（掌握） 希尔排序（了解） 交换排序 冒泡排序（掌握） 快速排序（了解） 选择排序 简单选择排序（掌握） 堆排序（掌握，不考算法）;归并排序：2-路归并排序（了解） 基数排序：链式基数排序（了解） 排序方法思想 每趟排序结果 排序方法性能分析评价;作业1.线性表 从键盘读入n个整数（升序），请编写算法实现： CreateList()：建立带表头结点的单链表； PrintList()：显示单链表(形如:H-10-20-30-40); InsertList()：在有序单链表中插入元素x； ReverseList()：单链表就地逆置； DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。 选作：使用文本菜单完成功能选择及执行。思考题：你能将上述算法改为双向循环链表吗？;L;L;L;L;L;L;L;L;L;L;L;L;LinkList SortList(LinkList L) //链表就地排序 { LNode *p,*pre,*q,*temp; p=L-next; if(p==NULL) return L; //空表,不用排序，返回 q=p-next; p-next=NULL; while(q!=NULL) { pre=L; p=L-next; while(p!=NULL) //查找插入位置 { if(q-datap-data) { pre=p; p=p-next; } else break; } temp=q-next; //插入 pre-next=q; q-next=p; q=temp; } return L; };作业2;设A为n阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素aij的地址计算公式和存放下三角阵时任一矩阵元素aij的地