资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复习,第1页,第1页,通过本课程学习，应能掌握数据结构特点、存储办法和基本运算，培养自己利用,C+,语言正确编写算法及调试能力，利用数据结构处理简朴实际问题能力，可为后续计算机方面课程学习打下坚实基础。,本课程学习目的,:,基本要求,:,1,、掌握主要数据结构逻辑结构、存储结构及基本运算实现，会,利用线性表、二叉树等设计算法以处理一些简朴实际问题，会通过阅读算法理解算法,；,2,、学会做简朴算法分析，包括算法时间复杂度和空间复杂度。,第2页,第2页,题型：,一、选择题（,20,分）,20*1,二、填空题（,20,分）,10*2,三、应用题（,45,分 二叉树（二叉树遍历和转换、哈夫曼树和编码）、图（最小生成树或单源点最短路径）、查找（散列查找）、排序（希尔、快速或堆）,5*9,四、算法设计题（,15,分 单链表应用、二叉树遍历应用）,题目给出函数框架，只需实现函数功效即可,第3页,第3页,设一颗二叉树以二叉链表为存储结构，设计一个算法求此二叉树上度为,1,结点个数。,struct BiNode /,二叉树结点结构,int data;,BiNode*lchild,*rchild;,;,int count(BiNode *root)/*root,为二叉树根结点*,/,第4页,第4页,第一章 概论,基本要求,:,1,、熟悉数据、数据元素,(,数据项,),、数据结构、数据逻辑结构与物理结构概念,2,、熟悉逻辑结构分线性和非线性（树、图）结构 及每种结构基本特性,3,、理解物理结构分顺序存储和链式存储,4,、理解算法定义、算法特性、算法时间复杂度、算法空间复杂度,5,、理解简朴计算语句频度和估算算法时间复杂度办法,第5页,第5页,第二章 线性表,基本要求：,1、了解线性表逻辑结构特性，以及线性表两种存放实现方式,2、纯熟掌握两种存放结构描述方法。链表是本章重点和难点。,3、灵活掌握次序表定义与基本操作实现，包含插入、删除算法实现；,4、灵活掌握链表结构实现线性表基本操作实现算法；,5、能够从时间和空间复杂度角度综合比较线性表两种存放结构不同特点及其合用场合。,6、会用线性表处理简朴实际问题。,第6页,第6页,第三章 栈、队列,基本要求：,1,、掌握,栈和队列定义、特性，并能正确应用它们处理实际问题；会通过阅读算法理解算法。,2,、纯熟掌握,栈顺序表示、链表表示以及相应操作实现。尤其注意栈空和栈满条件；（主要是出栈和入栈）掌握递归函数阅读。,3,、,纯熟掌握,队列顺序表示、链表表示以及相应操作实现。尤其是循环队列中队头与队尾指针改变情况及队列空和队列满条件及元素个数。,第7页,第7页,循环队列,空：,front=rear,满：,(rear+1)%MAXN=front,队列元素个数：,（,rear-front+MAXN)%MAXN,入队,:rear=(rear+1)%MAXN;,datarear=x;,出队：,front=(front+1)%MAXN,return(datafront);,第8页,第8页,第,4,章 串和数组,1,、掌握数组在以行（列）为主存储结构中地址计算法；,2,、,掌握对特殊矩阵（主要是下三角）进行压缩存储时下标变换公式；,3,、理解,稀疏矩阵三元组压缩存储办法,4,、理解串基本操作含义，并能利用这些基本操作来实现串其它各种操作办法。,第9页,第9页,基本要求：,1,、理解树和森林概念。包括树定义、树术语；,2,、纯熟掌握二叉树结构特性，熟悉二叉树各种存储结构特点和性质；,3,、纯熟掌握二叉树遍历办法及遍历算法和算法应用；,4,、理解树各种存储结构及其特点，掌握树、森林与二叉树转换办法；,5,、掌握建立哈夫曼树和哈夫曼编码办法及带权路径长度计算,.,完全二叉树、满二叉树,第,5,章 树,第10页,第10页,基本要求,1,、理解图基本概念，熟悉图各种存储结构（邻接矩阵和邻接表）；,2,、纯熟掌握图两种搜索路径遍历；,3,、掌握结构最小生成树（,prim,算法）办法，并理解克鲁斯卡尔算法；,4,、理解求,AOV,网拓扑排序办法；,5,、掌握用,Dijkstra,办法求解单源最短路径问题；,6,、理解在,AOE,网中求关键路径办法。,第,6,章 图,第11页,第11页,基本要求,1,、纯熟掌握顺序表和有序表查找算法及其性能分析办法,:,顺序查找、二分查找（鉴定树）,2,、纯熟掌握哈希函数结构及处理冲突办法（依据哈希函数结构哈希表，并计算平均查找长度）,3,、理解二叉排序树特点、创建和查找,第,7,章 查找,第12页,第12页,例：设哈希函数,H(K)=k%13,给定键值序列为,87,25,310,8,27,132,68,95,187,123,70,63,47,，处理冲突办法为线性探测再散列，试在,018,散列地址空间中对该关键字序列结构哈希表，并计算该表成功查找平均查找长度。,第13页,第13页,第,8,章 排序,基本要求：,1,、掌握排序基本概念和各种排序办法特点，并能加以灵活应用；,2,、掌握插入排序、互换排序、选择排序办法及其性能分析办法；,3,、理解归并排序办法。,第14页,第14页,
展开阅读全文