windows第11章数据结构.ppt

,成功之路,数据结构与算法（1）,,李元波,回顾,值类型与引用类型 装箱与拆箱 数组：同一类型的若干数据连续存储的集合 形式参数 索引器：在类或结构接口中，也可以像引用数组一样引用自己的成员 结构：关键字struct声明，结构跟类相似，可以包含构造函数、常数、字段、方法、属性 枚举 ：用关键字enum声明，枚举是用于存储一组数值常量的集合 ArrayList，Hashtable，Queue，Stack List,Dictionary,课程目标,了解什么是数据结构 数据结构的主要分类 什么是算法 算法复杂度 掌握第一种数据结构： 最简单的线性表-顺序表,数据结构,数据结构(Data Structure) 是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。,基本数据结构,集合：数据元素除了存在“同属于一个集合”的关系外，不存在任何其它关系(a)。 线性结构：数据元素存在着一对一的关系(b)。 树形结构：数据元素存在着一对多的关系(c)。 图状结构：数据元素存在着多对多的关系(d)。,(a)集合 (b)线性结构 (c)树形结构 (d)图状结构,基本数据结构-线性结构,学生信息表是一个线性的数据结构，表中的每一行是一个记录（在数据库信息处理系统中，表中的一个数据元素称为一个记录）。一条记录由学号、姓名、行政班级、性别和出生年月等数据项组成。表中数据元素之间的关系是一对一的关系。,基本数据结构-树形结构,家族关系是典型的树形结构 树形结构具有严格的层次关系,基本数据结构-图状结构,四个城市的公路交通图 每个城市是一个顶点（在图状结构中，数据元素称为顶点），它们之间是多对多的关系。 这些公路构成了一个公路交通网，所以，又把图状结构称为网状结构(NetworkStructure),算法,算法(Algorithm)是对某一特定类型的问题的求解步骤的一种描述，是指令的有限序列。其中的每条指令表示一个或多个操作。,算法时间复杂度,一个算法的时间复杂度是指该算法的运行时间与问题规模的对应关系。 通常把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。 算法中的基本操作一般是指算法中最深层循环内的语句,int x = n; int y = n+1; for(int i = 0; i x ; i +) for( int j = 0; j y ; j +) /do something ,算法时间复杂度,算法中基本操作重复执行的频度T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)。其中“O”表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，或者说，用“O”符号表示数量级的概念。 O(1)，常数阶：算法没有循环语句，则算法中基本操作的执行频度与问题规模n无关。 O(n)：算法只有一个一重循环，基本操作的执行频度与问题规模n呈线性增大关系. 其他复杂度: 平方阶O（ ）、立方阶O（ ）、对数阶O( )等。,算法时间复杂度举例,O(n),x=n; /*n1*/ y=0; while(y x) y=y+1; ,O( ),O( ),for(i=1；in；+i) for(j=0；jn；+j) Aij=i*j; ,x=n; /*n1*/ y=0; while(x = (y+1)*(y+1) y=y+1; ,线性表,线性表(Linear List)是具有相同类型的数据元素的一个有限序列 “有限”:指的是线性表中的数据元素的个数是有限的，线性表中的每一个数据元素都有自己的位置(Position)。 “相同类型”，指的是线性表中的数据元素都属于同一种类型。,线性表的基本操作,线性表的基本操作用接口来表示： public interface IListDS int GetLength(); /求长度 void Clear(); /清空操作 bool IsEmpty(); /判断线性表是否为空 void Append(T item); /附加操作 void Insert(T item, int i); /插入操作 T Delete(int i); /删除操作 T GetElem(int i); /取表元 int Locate(T value); /按值查找 ,线性表种类,1 顺序表 2单向链表 3双向链表 4循环链表,顺序表,顺序表是最简单的一类线性表存储结构。 顺序表是指用一块地址连续的存储空间依次存储线性表的数据元素。,数据,容量,实际数量,顺序表特点1,105,106,107,108,109,110,201,202,203,204,205,206,207,208,209,210,301,302,303,304,305,306,307,308,309,310,101,102,103,104,A公司房间,B公司房间,A公司租用4间房间,B公司租用5间 房间,XXX酒店,顺序表特点2,由于线性表中每个元素所占用的空间是相同的，只需按照公式计算便可以快速地访问指定元素。假设顺序表中第一个元素的位置是Loc，每个数据元素所占用的存储空间为n,线性存储空间,下标位置,0,1,i-1,存储地址,Loc,Loc + n,Loc + (i 1) * n,顺序表的实现-类关系图,顺序表典型方法,追加 插入 删除,-1,顺序表-追加操作1/3,Append(50),50,追加操作-第一次添加,-1,顺序表-追加操作2/3,Append(200),200,追加操作-继续添加,50,-1,顺序表-追加操作3/3,Append(6),6,追加操作,50,200,追加操作时间复杂度,和已经存在的数据没有关系 时间复杂度为：O(1),顺序表-插入操作1/2,Insert(0,12),12,插入操作,顺序表-插入操作2/2,Insert(2,73),50,12,73,插入操作,插入操作时间复杂度,顺序表上的插入操作，时间主要消耗在数据的移动上 最好的情况： 插入末尾即第n个下标位置，没有任何移动 最坏的情况： 插入头部即第0个下标位置，则需要移动所有的数据，总共移动n次 平均移动次数是：n/2 时间复杂度为：O(n),顺序表-删除操作1/2,Delete(0),12,删除操作,顺序表-删除操作2/2,Delete(2),50,200,6,73,删除操作,删除操作时间复杂度,顺序表上的删除操作，时间主要消耗在数据的移动上，和插入操作相似 最好的情况： 删除末尾即第n-1个标位置，没有任何移动 最坏的情况： 删除头部即第0个下标位置，则需要移动移动剩余的所有的数据，总共移动n-1次 平均移动次数是：（n-1）/2 时间复杂度为：O(n),查找操作时间复杂度,思考？定位查找操作时间复杂度 查找操作有2种 取表元public T GetElem(int i) 按值查找public int Locate(T value),12,顺序表的实现-具体代码分析,Demo,顺序表应用举例,反转 已知顺序表 L，写一反转算法将其倒置，下面是顺序表倒置前后的数据存储图。,顺序表练习,练习：合并顺序表 有数据类型为整型的顺序表 SLa 和 SLb，其数据元素均按从小到大的升序排列。 编写一个算法将它们合并成一个表 SLc。 要求 SLc 中数据元素按降序排列。 算法思路： 依次倒序扫描SLa 和 SLb 的数据元素，比较 SLa 和 SLb 当前数据元素的值； 将较大值的数据元素赋给SLc，如此直到一个顺序表被扫描完； 然后将未完的那个顺序表中余下的数据元素赋给SLc即可。 SLc的容量要能够容纳SLa和SLb两个表相加的长度。,顺序表作业,作业 在“合并顺序表”这道练习的基础上添加一个限制条件，要求 SLc 中数据元素不能重复。,总结,数据结构及分类