一，数据结构的基础概念

程序（程序设计）：为计算机处理问题编制的一组指令集合。

算法：处理问题的策略。

数据结构：问题的数学模型。

1，计算机的应用涉及到的更多的是非数值计算的问题。即计算机处理的对象是纯粹的数值以外的表格、图像、声音等各种具有一定结构的数据。

计算机应用系统中的两个关键问题:

1）表示:对象及其关系在计算机中的表示。只有对象及其相互关系已存储在计算机中，才能被进一步

处理;

2）操作:对对象进行处理，访问。

2，相关名词：

◆数据(Data)

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合

数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。

◆数据元素(Data Element)

数据元素(Data Element) :是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。

一个数据元素可由一个或多个数据项(Data Item )组成，数据项是有独立含义的最小单位

◆数据对象(Data 0bject )

数据对象是性质相同的数据元素的集合，是数据的一个子集。（整数，浮点数）

◆数据结构(Data Structure)

是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。

◆数据类型(Data Type)

数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。

例如:

在高级语言中，整型类型的取值范围为: -32768~+32767,

运算符集合为加、减、乘、除、取模，

即+、一、*、/、%。

原子类型:其值不可分解。如C语言中的标准类型(整型、实型、字符型)

结构类型:其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。

◆数据抽象与抽象数据类型

抽象数据类型(Abstract Data Type):指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来;它定义了一组运算，但将运算的实现过程隐藏起来。

例如:线性表的抽象数据类型的描述:

ADT Linear list{
数据元素        所有a;属于同一数据对象，i=1， 2,.....n;        n>=0;
逻辑结构        所有数据元素a; (i=1, 2, ..., n-1)存在次序关系
                        <a i, a i+1>, a无前趋，an无后继;
操作        设L为Linear_ list
                Initial(L):初始化空线性表; 
                Length(L):求线性表的表长;
                Get(L,i):取线性表的第i个元素;
                Insert(L,b):在线性表的第i个位置插入元素b;
                Delete(L,i):删除线性表的第i个元素;
} ADT Linear list

ADT有两个重要特征:

①数据抽象:用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口(即外界使用它的方法)

②数据封装:将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

3，数据结构的内容：

逻辑结构、存储结构和运算集合。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。

逻辑结构:指数据元素之间逻辑关系描述。

形式化描述: Data_ Structure=(D,R)

其中D是数据元素的有限集，R是D上关系的有限集。

四类基本的结构

集合结构、线性结构、树型结构、图状结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

存储结构:逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。

数据元素的表示:用若干个二进制“位串”表示

数据元素之间关系在计算机中的表示方法:

顺序映象(顺序存储结构)

非顺序映象(非顺序存储结构)

运算集合:在计算机中进行运算操作的集合。

二，算法及其时间复杂度

1，算法的特性：

1.有限性:有限步骤之内正常结束，不能形成无穷循环。

2.确定性:算法中的每一一个步骤必须有确定含义，无二义性得以实现。.

3.输入:有多个或0个输入。

4.输出:至少有一个或多个输出。

5.可行性:原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。

2，算法设计的要求：

1）正确性：

一般可分为四个层次:

(1)程序不含语法错误;

(2)程序对于几组输入数据能够得出满足规格说明要求的结果;

(3)程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;

(4)程序对于一切合法的输入数据都能产生满足规格说明要求的结果。

2）可读性：

一个程序的命名一般应该按照它的含义，函数的整个结构都要非常的清晰。

3）健壮性：

抗病毒，抗干扰能力

4）高效率和低存储量的要求:

一般我们需要一-个程序的效率是比较高的，占用的存储空间是比较少的。

3，算法，语言，程序的关系：

1.算法:描述了数据对象的元素之间的关系(包括数据逻辑关系、存贮关系描述)

2.描述算法的工具:算法可用自然语言、框图或高级程序设计语言进行描述。

(本课程选择类C语言描述算法。)

3.程序是算法在计算机中的实现。

4，算法的性能分析：

1）评价算法的标准：

评价算法的标准:

一般来说评价一个算法的好坏就是看它的时间和空间，因为空间现在的内存都很大，考虑的比较少，我们主要考虑算法的时间复杂度怎样进行度量。

评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。

2）性能评价：

对问题规模N与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。

3）算法效率的衡量：

通常有两种衡量算法效率的方法:

事后统计法

缺点: 1.必须执行程序

       2.其它因素掩盖算法本质（硬件）

事前分析估算法

编写完算法之后，再去粗略计算时间复杂度

和算法执行时间相关的因素：

1)算法选用的策略

2)问题的规模

3)编写程序的语言

4)编译程序产生的机器代码的质量

5)计算机执行指令的速度

一个算法耗费的时间=算法中每条语句的执行时间之和

若不考虑机器硬、软件因素，可以认为算法“运行工作量的大小是问题规模的函数。

6，关于算法执行时间：

●定义:

一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一-次 所需时间的乘积。

●分析:

不是针对实际执行的时间精确地算出算法执行具体时间，而是针对算法中基本操作语句(原操作)的执行次数做出估计，从中得到算法执行时间的信息。

语句频度是指该语句在一个算法中重复执行的次数。

7，算法的时间复杂度：

算法的时间复杂度，即是算法的时间量度记做:T(n)=O(f(n))

例如:

(1) x=x+1; 时间复杂度为0(1)， 称为常量阶; .

(2) for(i=1;i<= n; i++) x=x+1;时间复杂度为O(n), 称为线性阶;

(3) for(i=1;i<= n; i+)

for (j=1;j<= n; j++) x=x+1;时间复杂度为0(n2),称为平方阶。

8，算法性能评价：

对问题规模N与该算法在运行时所占的空间与所耗费的时间T给出一个数量关系的评价。

一个算法的执行时间大致上等于其所有语句执行时间的总和。

9，算法的空间复杂度：

作为算法所需存储空间的量度，记做:

S(n)=O(f (n))

算法的存储量包括:

1.输入数据所占空间

2.程序本身所占空间

3.辅助变量所占空间

10，例子：

问题:编写程序实现用一元人民币换成

分、两分、五分的硬币共50枚。

分析:假设一分、两分、五分的硬币各

为x, y, z枚。

则有:

x+y+ z= 50

x+ 2y+ 5z= 100

对于一个特定的问题，我们可能会有很多的解决方法，但是不同的方法各有利弊，所以说算法的设计至关重要。

综上，我们提出以下讨论：

1，什么是数据类型？数据类型的作用是什么？

数据类型解决了“存”的问题：它决定了使用这个类型需要开辟空间的大小以及内存中的数据是如何存储的；

数据类型解决了“取（读）”的问题：它改变了看待内存空间的视角，比如在内存中同样的两块4个字节的空间，存放着同样的二进制码，如果这两块内存对应的两个变量类型不一样，那么它们的意义也就不一样了。

解决指定问题的一种解决方案。定义区分各种数据变量，以便计算机存储，处理。

2，数据结构四种逻辑结构的特点是什么?

1.数据4种逻辑结构：（1）集合结构：数据元素之间没有任何关系。（2）线性结构：数据元素之间定义了线性关系。1对1。（3）树形结构：数据元素之间定义了层次关系。1对多。（4）图状结构：数据元素之间定义了网状关系。多对多。2.（1）集合结构。集合任何两数据元素间都没逻辑关系,组织形式松散。（2）线性结构。线性结构 结点按逻辑关系依排列形锁链。（3）树形结构。树形结构具支、层特性,其形态点象自界树。（4）图状结构。图状结构结点按逻辑关系互相缠绕,任何两结点都邻接。扩展资料：1.数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。2.数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。

3，

在一重循环中的语句，其时间复杂度一定是O(n)吗？

例如：

   void fun(int n)
    {
        int i=0, s=0;
        while(s<n)
        {
                i++;
                s=s+i;;
        }
    }

请分析该算法的时间复杂度，其时间复杂度是O(n)吗?

不是

s = s + i，i累加

设循环次数为x

s=1+2+3+...+x=x（x+1）/2

循环执行条件为s=x(x+1)/2

所以时间复杂度为O(√n)