数据结构1

,1、数据结果讨论的范畴

算法+数据结构=程序

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

例如：数值计算的程序问题

结构静力分析计算--------线性代数方程组

全球天气预报----------环流模式方程

 

非数值计算的方程设计问题

例：求一组（n个）整数中的最大值

算法：？基本操作是“比较俩个数的大小”

模型：？

 

例二：计算机对弈

算法：对弈的规则和策略

模型：？棋盘，旗子的表示

 

例三：足协的数据库管理

算法？需要管理的项目？如何管理？用户界面？

模型：？各种各样的表格和数据库。

 

概况地说

        数据结构描述实现世界实体的数学模型（非数值计算）及其上的操作在计算机中的实现。

2、基本概念

 

一、数据与数据结构

数据：所有能被输入到计算机中，且被计算机处理的符号的集合计算机操作的对象的总称。

是计算机处理的信息的某种特定的符号表示形式。

 

数据元素：

数值中的一个“个体”，数据结构中讨论的基本单位。但不是最小单位。

数据项：数据结构中讨论的最小单位，

数据元素是数据项的集合。

例如：运动员（数据元素）

姓名-俱乐部名称-出生日期(年-月-日【组合项】)-参加日期-职位-业绩

 

数据结构：带结构的数据元素的集合。

 

例如：一个含12位数的十进制可以用三个4位的十进制数表示

3214,6587,9345=====a1(3214),a2(6587),a3(9345)

在a1,a2和a3之间存在“次序”关系

<a1,a2>,<a2,a3>

 

 

 

例子：2行3列的二维数组(a1,a2,a3,a4,a5,a6)

A1	A2	A3
A4	A5	A6

行的次序关系：

Row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}

列的次序关系

Row={<a1,a4>,<a2,a5>,<a3,a6>}

 

数据的逻辑结构可归结为以下四类

线性结构、树形结构、图状结构和集合结构

 

数据结构的形式定义为：

数据结构是一个二元组

Data_Structures=(D,S);

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

 

数据的存储结构

逻辑结构在存储器中的映像

 

数据元素的映像方法：

用二进制位(bit)的位串表示数据元素

 

关系的映像方法:（表示<x,y>的方法）

 

顺序映像

         以存储位置的相邻表示后继关系y的存储位置和x的存储位置之间的一个常量C

         而C是一个隐含值，整个存储结构中只含数据元素本身的信息

x

y

 

链式映像

         以附加信息（指针）表示后继关系

需要用一个和X在一起的附加信息指示Y的存储位置

 

在不同的编程环境中，存储结构可有不同的描述方法

 

抽象数据类型(Abstract Data Type 简称ADT)

是指一个数学模型以及定义在此数学模型上的一组操作

 

 

ADT有俩个重要特征

         数据抽象

用ADT描述程序处理的实体时，强调的是其本质的特征，其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）

数据封装

将实体的外部特征和其内部实现细节分离，并且对外部用户隐藏其内部实现细节

 

抽象数据类型的描述方法

 

抽象数据类型可用（D,S,P）三元组表示

其中，D是数据对象

      S是D上的关系集

      P是对D的基本操作集

 

抽象数据类型的表示和实现

抽象数据类型需要用固有数据类型（高级编程语言中已实现的数据类型）来实现

 

3、算法和量度

 

1，算法

算法是为了解决某类问题而规定的一个有限长的操作序列，一个算法必须满足以下五个重要特征：

1、有穷性

对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。

2、确定性

对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法在执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。

3，可行性

算法中的所有操作必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。

4、有输入

作为算法加工对象的量值，通常提现为算法中的一组变量，有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中

5、有输出

它是一组与“输入”与确定关系的量值，是算法进行加工得到的结果。

 

二，算法设计的原则

设计算法时，通常应考虑达到以下目标：

1、正确性

2、可读性

3、健壮性

4、高效率与地存储量需求

 

 

 

1、正确性

首先，算法应当满足以特定的“规格说明”方式给出的需求。

其次，对算法是否“正确”的理解可以有以下四个层次：

a、程序中不含语法错误

b、程序对于几组输入数据能够得出满足要求的结果；

c、程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；

d、程序对于一切合法的输入数据都能得出满足要求的结果；

 

2、可读性

算法主要是为了人的阅读与交流，其次才是为计算机执行，因此算法应该易于人的理解

 

3、健壮性

当输入的数据非法时，算法应当恰当地做出反映或进行相应处理，而不是莫名其妙的输出结果，并且，处理出错的方法不应是中断程序的执行，而应返回一个表示措辞或者错误性质的值。以便在更高的抽象层面处理

 

4、高效率与地存储量需求

通常，效率值得算法执行时间，存储量指的算法执行过程中所需要的最大存储空间，俩者都与问题的规模有关。

 

 

三、算法效率的衡量方法和准则

通长有俩种衡量算法效率的方法

事后统计法

缺点：1、必须执行程序

      2、其他因素掩盖算法的本质

事前分析估算法

 

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

1、算法选用的策略

2、问题的规模

3、编写程序的语音

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

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

 

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

 

假如，随着问题规模N的增长，算法执行时间的增长率和f(n)的增长率相同，则可记住作：

T(n)=O(f(n))

称T(n)为算法的(渐进)时间复杂度

算法=控制结构+原操作（固有数据类型的操作）

算法的执行时间=

∑原操作(i)的执行次数*原操作(i)的执行时间

 

算法的执行时间与原操作执行次数之和成正比

 

从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则

 

例一，矩阵相乘

for(i=;i<=n;++i){

         for(j=1;j<=n;j++){

                   c[i,j]=0;

                   for(k=1;k<=n;++k)

                            c[i,j]+=a[i,k]*b[k,j];

         }

}

基本操作：乘法操作

<!--[if gte msEquation 12]><m:oMath><m:sSup><m:sSupPr><span style='font-family:"Cambria Math","serif";mso-ascii-font-family:"Cambria Math"; mso-hansi-font-family:"Cambria Math"'><m:ctrlPr></m:ctrlPr></span></m:sSupPr><m:e><span style='font-family:宋体;mso-ascii-font-family:"Cambria Math";mso-fareast-font-family: 宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:"Cambria Math"'><m:r><m:rPr><m:scr m:val="roman"/><m:sty m:val="p"/></m:rPr>时间复杂度</m:r></span><span lang=EN-US style='font-family:"Cambria Math","serif"'><m:r><m:rPr><m:scr m:val="roman"/><m:sty m:val="p"/></m:rPr>:O(</m:r><m:r><i style='mso-bidi-font-style:normal'>n</i></m:r></span></m:e><m:sup><i style='mso-bidi-font-style:normal'><span lang=EN-US style='font-family:"Cambria Math","serif"'><m:r>3</m:r></span></i></m:sup></m:sSup></m:oMath><![endif]--><!--[if !msEquation]--><!--[if gte vml 1]><v:shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"> <v:stroke joinstyle="miter"/> <v:formulas> <v:f eqn="if lineDrawn pixelLineWidth 0"/> <v:f eqn="sum @0 1 0"/> <v:f eqn="sum 0 0 @1"/> <v:f eqn="prod @2 1 2"/> <v:f eqn="prod @3 21600 pixelWidth"/> <v:f eqn="prod @3 21600 pixelHeight"/> <v:f eqn="sum @0 0 1"/> <v:f eqn="prod @6 1 2"/> <v:f eqn="prod @7 21600 pixelWidth"/> <v:f eqn="sum @8 21600 0"/> <v:f eqn="prod @7 21600 pixelHeight"/> <v:f eqn="sum @10 21600 0"/> </v:formulas> <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/> <o:lock v:ext="edit" aspectratio="t"/> </v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:79.5pt; height:15.75pt'> <v:imagedata src="file:///C:\Users\lenovo\AppData\Local\Temp\msohtmlclip1\01\clip_image001.png" o:title="" chromakey="white"/> </v:shape><![endif]--><!--[if !vml]--><!--[endif]--><!--[endif]-->)

 

例二、选择排序

 

public void select_sort(int[] a){

         for(int i=0;i<a.length-1;i++){

                   int j=i;//假定第一个是最小的

                   for(int k=i+1;k<a.length;k++){

                            //如果当前元素比J小

                            if(a[k]<a[j]) j=k;

                            //如果当前的值不是假定的最小值

                            if(j!=i){

                                     int x=a[i];

                                     a[i]=a[j];

                                     a[j]=x;

                            }

                   }

         }

}

 

基本操作：比较（数据元素）操作

 

 

 

 

 

 

 

 

 

 

例三，冒泡排序

public void bubble_sort(int[] a){

         for(int i=a.length-1,change=ture;i>1&&change;i--){

                   change=false;

                   for(int j=0;j<i;j++){

                            if(a[j]>a[j+1]){

                                     int x=a[j];

                                     a[j]=a[j+1];

                                     a[j+1]=x;

                                     change=true;

                            }

                   }

         }

}