数据结构（Python版）全套PPT课件.pptx

;;课程学习指导;平时成绩 : 40% ;;; N.沃思（Niklaus Wirth)教授提出：;书目自动检索系统;人机对奕问题;;多叉路口交通灯管理问题;设计出合适的数据结构及相应的算法 即：首先要考虑对相关的各种信息如何表示、组织和存储？; 形成阶段： 60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。;;数据结构在计算机学科中的地位 ;;;;;数据结构的两个层次：;划分方法一;;存储结构;;1536;逻辑结构和存储结构都相同, 但运算不同, 则数据结构不同. 例如, 栈与队列;;抽象数据类型 (ADTs: Abstract Data Types);抽象数据类型可以用以下的三元组来表示： ADT = （D，S，P） 数据对象 D上的关系集 D上的操作集 ;抽象数据类型;;（4）内存的动态分配与释放 ; （9）输入输出语句形式有： 输入语句 input() 输出语句 output() （10）扩展函数有： 求最大值 max 求最小值 min;;算法和算法分析;;算法的评价:;;算法和算法分析;;算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=O(f(n)) ;;找出语句频度最大的那条语句作为基本语句 计算基本语句的频度得到问题规模n的某个函数f(n) 取其数量级用符号“O”表示;;;;例4：顺序查找，在数组a[i]中查找值等于e的元素，返回其所在位置。 for i in range(n): if a[i]==e: return i+1 return 0;;空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小);【算法1】? for i in range(n/2): t=a[i] a[i]=a[n-i-1] a[n-i-1]=t?;1、数据、数据元素、数据项、数据结构等基本概念 2、对数据结构的两个层次的理解 逻辑结构 存储结构 3、抽象数据类型的表示方法 4、算法、算法的时间复杂度及其分析的简易方法 ;;;;第2章 线性表 第3章 栈和队列 第4章 串、数组和广义表 ;;;;;;;2.2 案例引入;;Rn(x)?=?Pn(x)?+?Qm(x);;;;;;;;（1）查找 （2）插入 （3）删除 （4）修改 （5???排序 （6）计数;图书顺序表;;;线性表的重要基本操作;;线性表的顺序表示又称为顺序存储结构或顺序映像。;;线性表的重要基本操作;;def clear_list(self): self.length = 0;线性表的重要基本操作;;查找（根据指定数据获取数据所在的位置） ;;;;判断插入位置i 是否合法。;;;;【算法步骤】;;若删除尾结点，则根本无需移动（特别快）； 若删除首结点，则表中n-1个元素全部前移（特别慢）； 若要考虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？;;顺序表（顺序存储结构）的特点;顺序表的优缺点 ;;线性表的链式表示和实现;如何实现？;各结点由两个域组成： 数据域：存储元素数值数据 指针域：存储直接后继结点的存储位置;与链式存储有关的术语;;4、头指针、头结点和首元结点 ;上例链表的逻辑结构示意图有以下两种形式：;;讨论2. 在链表中设置头结点有什么好处？;讨论3. 头结点的数据域内装的是什么？;结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻;链表的优缺点;;练习;;class LNode: def __init__(self, data=None): self.data = data # 结点的数据域 self.next = None # 结点的指针域 def __str__(self): return str(self.data);单链表基本操作的实现;【算法步骤】;;求表长 def __iter__(self): p = self.head while p is not None: