第1章数据结构与算法
11算法的复杂度1算法的基本概念利用计算机算法为计算机解题的过程实际上是在实施某种算法1算法的基本特征算法一般具有4个基本特征可行性确定性有穷性拥有足够的情报2算法的基本运算和操作算法的基本运算和操作包括算术运算逻辑运算关系运算数据传输3算法的3种基本控制结构算法的3种基本控制结构是顺序结构选择结构循环结构4算法基本设计方法算法基本设计方法列举法归纳法递推递归减半递推技术回溯法5指令系统所谓指令系统指的是一个计算机系统能执行的所有指令的集合2算法复杂度算法复杂度包括时间复杂度和空间复杂度注意两者的区别无混淆见表11表11算法复杂性名称时间复杂度空间复杂度描述执行算法所需要的计算工作量执行这个算法所需要的内存空间
12数据结构121逻辑结构和存储结构1数据结构的基本概念1数据结构指相互有关联的数据元素的集合2数据结构研究的3个方面①数据集合中各数据元素之间所固有的逻辑关系即数据的逻辑结构②在对数据进行处理时各数据元素在计算机中的存储关系即数据的存储结构③对各种数据结构进行的运算2逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述它可以用一个数据元素的集合和定义在此集合中的若干关系来表示数据的逻辑结构有两个要素一是数据元素的集合通常记为D二是D上的关系它反映了数据元素之间的前后件关系通常记为R一个数据结构可以表示成BDR其中B表示数据结构为了反映D中各数据元素之间的前后件关系一般用二元组来表示
1
f例如如果把一年四季看作一个数据结构则可表示成BDRD春季夏季秋季冬季R春季夏季夏季秋季秋季冬季3存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构也称数据的物理结构由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同因此为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系即前后件关系在数据的存储结构中不仅要存放各数据元素的信息还需要存放各数据元素之间的前后件关系的信息一种数据的逻辑结构根据需要可以表示成多种存储结构常用的存储结构有顺序链接等存储结构顺序存储方式主要用于线性的数据结构它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里结点之间的关系由存储单元的邻接关系来体现链式存储结构就是在每个结点中至少包含一个指针域用指针来体现数据元素之间逻辑上的r