数据结构lst.ppt

Data Structure,数据结构,逻辑结构,存数结构,数据运算,线性表,栈,队列,树,图,串,线性结构,非线性结构,顺序存储,链式存储,查找,排序,第一章 绪论,1.2 基本概念和术语合上课本思考一下，假设学号中每一个阿拉伯数字都是一个数据元素，你可以用它们构建出几类数据结构？1.4 算法和算法分析算法的5个重要特性确实很重要！大圈表示法它不是英文，它是希腊字母。,分析时间复杂度应该是小菜一碟！P15例：(a)+x;s=0;(b)for(i=1;i=n;+i)+x;s+=x;(c)for(j=1;j=n;+j)for(k=1;k=n;k+)+x;s+=x;,第2章 线性表,线性结构的特点。2.2 线性表的顺序表示和实现为什么可以随机存储？删除和插入时的逻辑状态变化？2.3 线性表的链式表示和实现单链表的逻辑状态？删除和插入逻辑状态变化？两种存储方式的优缺点。,线性表的插入与删除操作示例,序号 数据元素 序号 数据元素 序号 数据元素 序号 数据元素,插入25,删除24,常见的指针操作,第3章 栈和队列,3.1 栈3.4 队列限定性的线性表结构，分别被做了哪些限定？二者都附设了两个指针，作用相同吗？其它章节的哪些算法用到了栈和队列？,第4章 串,4.1 定义4.2 串的表示和实现4.3 串的模式匹配算法了解概念,第5章 数组和广义表,5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义-表头、表尾、原子、子表5.5 广义表的存储结构,第6章 树和二叉树,6.16.26.36.46.6,第7章 图,7.1 图的定义和数据无向图 G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)7.2 图的存储结构7.3 图的遍历图的遍历序列唯一吗？给出了邻接表的图呢？7.4 图的连通性问题,第9章 查找（略）,9.1 静态查找表9.1.1 顺序表的查找9.1.2 有序表的查找9.2 动态查找表定义9.3 哈希表定义,第10章 排序（略）,10.4 选择排序10.4.3 堆排序10.7 比较讨论直接插入排序、希尔排序、快速排序、简单选择排序、堆排序、归并排序、基数排序算法平均比较次数平均时间辅助存储,题型说明,单选共 15 题，每题 2 分，共 30 分填空共10个空，每空 2 分，共 20 分判断共 10 题，每题 2 分，共 20 分分析共 2 题，共 30 分,成绩考核,总成绩=试卷成绩X80%+实验成绩X20%,all thebestfor theexam！,