大学数据结构ppt课件(清华版).pptVIP

数据结构Data Structure 　 长春大学软件工程系 ２０11．2;　 学 分： 　3 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，2011年 参考书： [1] 殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26 [2] 殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。 [3] 李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。 [4] 严蔚敏等，数据结构题集(C语言版)，清华大学出版社， 1997年4月。;内 容 安 排;第1章 序 论;§1.1 什么是数据结构;Q1：如何采用计算机解决问题？;Q2：数据结构解决什么样的问题？; 介于数学、计算机硬件和计算机软件三者之间的一门核心课程;§1.2 基本概念和术语;Q1：什么是数据结构？;术语：数据、数据元素和数据项;Q2：学习数据结构有什么用？;;解释1： 什么叫数据的逻辑结构???;例：用图形表示下列数据结构，并指出它 们是属于线性结构还是非线性结构。;（2） S=(D, R) D={di | 1≤i≤5} R={(di , dj ), ij};解释2：什么叫数据的物理结构？;解释3：什么是数据的运算？;§1.3 抽象数据类型的表示和实现;Q1 数据类型与抽象数据类型的区别？;Q2 抽象数据类型如何定义？;例：给出自然数(Natural Number )的抽象数据类型定义。;Q3 抽象数据类型如何表示和实现？;§1.4 算法和算法分析;答：算法是解决某一特定类型问题的有限运算 序列。是一系列输入转换为输出的计算步 骤。;Q2. 算法设计的要求？;时间复杂度T(n)按数量级递增顺序为： ;渐进符号（O）的定义：当且仅当存在一个正的常数 C，使得对所有的 n ? n0 ，有 f(n) ? Cg(n)， 则f(n) = O(g(n)) ;例：分析以下程序段的时间复杂度。;Q4. 空间复杂度如何表示？;作业：;上堂课要点回顾;数据结构课程的内容;近3周上课内容;线性结构的特点：;第2章 线性表;（a1, a2, … ai-1，ai, ai＋1 ，…, an） ;例1 分析26 个英文字母组成的英文表;练：判断下列叙述的正误：;二.线性表的类型定义（详见课本P19）;2.2 线性表的顺序表示和实现;2.2.1 顺序表的表示;2.线性表顺序存储特点：;线性表的顺序存储结构示意图;一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是９８，则Ｍ[３]的第一个字节的地址是 ;3.线性表的动态分配顺序存储结构;问1：自定义结构类型变量test的长度m是多少？ m＝sizeof(test) 问2：结构变量test的首地址(指针p）是多少？ p＝(test*)malloc(m) 问3：怎样删除结构变量test？只能借助其指针删除！ free(p);2.2.2 顺序表的实现（或操作）;2.建立 Status InitList_Sq( SqList L ) { //构造一个空的线性表L。 L.elem = ( ElemType * ) malloc( LIST_INIT_SIZE * sizeof ( ElemType) ); If ( ! L.elem ) exit ( OVERFLOW ) ; // 存储分配失败 L.length = 0; // 空表长度为0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq;3.插入 在线性表的第i个位置前插入一个元素;在线性表的第i个位置前插入一个元素的示意图如下：;实现步骤：(n为表长） 将第i +1至第n 位的元素向前移动一个位置； 表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当有1≤i≤n 或 i=[1, n];;2.2.3 顺序表的运算效率分析;证明：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。 若在首结点前