目录一、数据结构的基本概念二、算法一、数据结构的基本概念1.基本的概念和术语1数据数据是客观事物的符号表示是所有能输入到计算机中并被计算机程序处理的符号的总称。2数据元素数据元素是数据的基本单位在计算机中通常作为一个整体进行考虑和处理。3数据项一个数据可由若干个数据项组成数据项是构成数据元素不可分割的最小单元。4数据对象数据对象是性质相同的数据元素的集合是数据的一个子集。5数据类型一个值的集合和定义在此集合上的一组操作的总称。2.数据结构的三要素相互之间存在一种或多种特性关系的数据元素的集合。数据结构数据结构数据结构包括逻辑结构、存储结构和对数据的运算由三要素唯一确定。1.逻辑结构包含两方便数据元素和关系根据关系的不同可分出不同的基本结构。2.物理结构据的存储结构又称为物理结构表示计算机既要存档下数据又要表明数据的关系。下列是常用的4种存储结构1顺序结构把逻辑上相邻元素存储在物理院上也相邻的存储单位中元素之间的关系由存储单位的邻接关系体现。2链式存储逻辑上相邻的元素在物理位置上可以不相邻借助指示元素存储地址的指针来元素之间的逻辑关系。3索引存储4散列存储3.数据的运算施加在数据上的运算包括运算的定义和实现。注意数据的运算操作并不是固定的而是根据逻辑结构判断是否可以执行哪些操作这些操作基于物理结构具体如何实现。二、算法算法为了解决某些问题而绑定规定的一个有限长操作序列。1.算法特性1有穷性一个算法必须总是在执行又穷步后结束且每一步都必须在又穷时间内完成。注意算法必须是又穷的而程序可以是无穷的。2确定性算法中每条指令必须有确切的含义不会产生二义性。3可行性算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。4输入一个算法有0个到多个输入5输出一个算法有一个或者多个输出是算法进行信息加工后得到的结果。2.算法优劣1正确性2可读性3健壮性4高效性3.时间复杂度一个算法的执行时间大致上等于其所有语句执行时间的总和而语句的执行时间则为该条语句的重复次数和执行一次所需时间的乘积。【总结】时间的复杂度是由算法基本操作总次数得出的。void f(n) { int i1; int j100; while(in) { j; i2; } }void f(n) { int i1; while(in) { printf(showtime\n); for(int j1;in;j) { printf(other show\n); } } printf(over\n); }4.空间复杂度指算法在运行时所需存储空间的度量。即衡量空间开销和问题规模n的关系。【分析】程序执行需要占的空间有什么---主要考虑临时占用的存储空间的大小。例如int abc相当于需要占用3个4B的空间int a[10]相当于需要占用10个4B且连续的空间。