（贵州省普通高中信息学奥赛CSP-JS NOIP—入门组C++知识点讲解）第15讲 数据结构与算法

学科竞赛编程 教研研究院 C++ NOIP NOI IOI 1 1 PART ONE 什么是数据结构 彭军、向毅《数据结构与算法》 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 Sartaj Sahni 《数据结构、算法与应用》 “数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 Clifford A.Shaffer在《数据结构与算法分析》 “数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。” Robert L.Kruse在《数据结构与程序设计》 将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。 1 PART ONE 什么是数据结构 例：如何在书架上摆放图书 图书的摆放要使得2个相关的操作方便实现： 操作1：新书怎么插入？ 操作2：怎么找到某本指定的书？ 1 PART ONE 什么是数据结构 方法二：按照书名的拼音字母顺序排放 操作1：新进一本《阿Q正传》…… 操作2：二分查找！ 适用于图书量不是特别多的情况。 方法三：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放 操作1：先定类别，二分查找确定位置，移出空位 操作2：先定类别，再二分查找  问题：空间如何分配？类别应该分多细？ 方法一： 随便放 操作1：哪里有空放哪里，一步到位！ 操作2：……累死 需解决问题： 操作1：新书怎么插入？ 操作2：怎么找到某本指定的书？ 数据结构与解决问题方法 解决问题方法的效率， 跟数据的组织方式有关 解决问题方法的效率， 跟空间的利用效率有关 解决问题方法的效率， 跟算法的巧妙程度有关 1 PART ONE 解决问题方法与数据组织方式有关 写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数 void PrintN ( int N ) { int i; for ( i=1; i<=N; i++ ) { printf(“%d ”, i ); } return; } void PrintN ( int N ) { if ( N ) { PrintN( N – 1 ); printf(“%d ”, N ); } return; } 循环实现 递归实现 1 PART ONE 解决问题方法与空间的利用效率有关 写程序计算给定多项式 在给定点x = 1.1 处的值f(1.1) 试一试，看看谁快吧！ double f1( int n, double a[], double x ) { int i; double a[MAXN]; /* 存储多项式的系数*/ for ( i=0; i<MAXN; i++ ) a[i] = (double)i; double p = a[0]; for ( i=1; i<=n; i++ ) p += (a[i] * pow(x, i)); return p; } double f2( int n, double a[], double x ) { int i; double a[MAXN]; /* 存储多项式的系数*/ for ( i=0; i<MAXN; i++ ) a[i] = (double)i; double p = a[n]; for ( i=n; i>0; i-- ) p = a[i-1] + x*p; return p; } 1 PART ONE 数据结构的三大结构 逻辑结构 （抽象层） 逻辑结构指人对数据之间关系的理解和看法，逻辑结构和计算机无关。 集合结构 线性结构 树型结构 网状结构 物理结构 （结构层） 物理结构描述计算机内部数据之间实际的关系。 顺序结构 链式结构 数据结构的基本操作 创建/销毁 -分配资源、建立结构、释放资源 插入/删除  -增加、减少数据元素 获取/修改  -遍历、迭代、随机访问（增删改查） 排序/查找  -算法应用 1 PART ONE 集合结构 集合结构中的元素除了同属于一个集合外没有其它关系，集合不强调元素之间的任何关联性，是一种松散的组合 线性结构 网状结构 网状结构中的元素具有多对多的交叉映