数据结构lst.ppt

DATA STRUCTURE数据结构逻辑结构存数结构数据运算线性表栈队列树图串线性结构非线性结构顺序存储链式存储查找排序第一章 绪论 1.2 基本概念和术语 合上课本思考一下，假设学号中每一个阿拉伯数字都是一个数据元素，你可以用它们构建出几类数据结构？ 1.4 算法和算法分析 算法的5个重要特性确实很重要！ 大圈表示法它不是英文，它是希腊字母。 分析时间复杂度应该是小菜一碟！分析时间复杂度应该是小菜一碟！例：例： (a) +x;s=0;(b) for (i=1;i=n;+i) +x;s+=x;(c) for (j=1;j=n;+j) for (k=1;knext ;bpa操作前操作后qbpa p=p-next ;bpa操作前操作后pba q-next=p ;cpbqa操作前操作后qbacp(a) q-next=p-next ;(a)xypbqa操作前操作后qbaxyp操作前ypxbqa操作后ypxbqa(b)操作前ypxbqa操作后ypxbqa(b)第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.1 6.2 6.3 6.4 6.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 THE BEST FOR THE EXAM！