算法与数据结构(一)
1.从问题到程序
用计算机实现问题求解，实质上就是在计算机中建立一个解决问题的模型。用来表示问题或处理问题的模型可以有不同的抽象形式：
a.容易被人理解但不太严格的需求模型；
b.比较抽象但很精确的数学模型；
c.容易被计算机理解或执行的实现模型；
程序是使用程序设计语言描述的实现模型，他是问题求解的一个可以在计算机上运行的模型。
为一个实际问题建立一个正确的求解程序，通常可以分为：
a.分析阶段
首先，我们要知道用户的需求是什么，设计者根据他深入分析，使用规范说明语言给出系统的需求模型。
b.设计阶段
这个阶段的任务是建立求解系统的实现模型，重点是算法的设计和数据结构的设计。
c.编码阶段
他主要任务是用适当的程序设计语言(c,c++,java等)吧设计阶段的成果，编写成可以执行的程序。
d.调试和维护
这个阶段的任务是调试编写好的程序，发现和排除程序代码中的错误。而维护工作是软件开发的一个重点，他的比重占整个软件开发过程的70%左右。
2.抽象数据类型
类型：是一组值(或者对象)的集合。如：boolean作为一个种类型是由真(true)和假(false)两个值组成的集合。
数据类型；通常是指在计算机语言中可以使用的一个类型，他不但包括这个类型的值集合，还包括定义在这个类型上的一组操作。
如：
1 int a；//定义
2
3 int b=2；//定义
4
5 int c=3；//定义
6
7 a=b+c; //操作，包括加，减，乘，除，取余等抽象数据类型：可以定义为具有一定行为(操作)的抽象类型，他不关心类型中值的具体表示方式和数据类型中定义的各种操作的具体实现方法， 是所有可能的值的具体表示和噶中操作的具体实现的抽象。我个人理解为是解决某个问题的一个思路，而具体怎么实现是不管的。
如：圆的抽象数据类型
1 ADT Circle is
2 operations
3 area
4 计算圆的面积
5 circumference
6 计算圆的周长
7 getRadius
8 获取圆的半径
9 setRadius
10 设置圆的半径
11 end ADT Circle3.数据结构
a.按逻辑结构分类
1.线性结构
1 L=<K1,R1>,其中k1={a,b,c,d},R1={<a,b>,<b,c>,<c,d>}
2 L就是一个线性结构。
3
4 a--->b--->c--->d2.树形结构
1 T=<k2,R2>,其中k2={1,2,3,4,5},R2={<1,2>,<1,3>,<2,4>,<2,5>},T就是一个树形结构。
2
3 1
4 / \
5 2 3
6 / \
7 4 53.复杂结构
1 G=<k3,R3>,k3={a,b,c},R3={<a,b>,<a,c>,<b,c>},G就是一个复杂结构。
2
3 a
4 / \
5 b ---- c4.算法
算法是由有穷规则构成的为解决某一类问题的运算序列(方法或过程)，
1 算法的性质：
2
3 a.有穷性
4 b.确定性
5 c.可行性5.排序问题
1 假设有n>=1个不同的整数a0，a1,a2....a(n-1),要求把这些整数从大到小进行排序。
2 输入：是含n个元素的整数数组，记为a，启动的元素依次是：a[0],a[1],a[2]....a[n-1]。
3 输出：是一个输入数组a的元素重新排序数组，记为a'，其中的元素依次是：a'[0],a'[1]....a'[n-1],并且满足a'[0]>a'[1]>a'[2]....a'[n-1]。
4
5 算法思想：
6
7 1.从a数组中选出一个最大的整数放到一个空的数组a'中，作为a'的第一个元素。
8 2.从a中剩下的元素中选出一个最大的整数放到a'中，接在前一个已放入元素的后面。
9 反复执行操作2，直到a中的整数都放到拍好序的数组a'中。
10
11 第一步精化：
12
13 1.从a[0]到a[n-1]中选出最大的整数，设为a[j],把a[0]与a[j]进行交换。
14 2.从a[1]到a[n-1]中选出最大的整数，设为a[j],把a[1]与a[j]进行交换。
15 .........
16 n.从从a[n-1]到a[n-1]中选出最大的整数，设为a[j],把a[n-1]与a[j]进行交换。(当然这时候因为j=n-1，故这步可以省略)。
17
18 第二部精化：
19
20 i以1为步长，从0到n-2，循环执行：
21 1.从a[i]到a[n-1]中选出最大的整数，设为a[j]。
22 2.把a[i]与a[j]进行交换。
23
24 第三步精化：
25
26 循环i以1为步长，从0到n-2，执行：
27 1.j<--i
28 2.循环k以1为步长，从i+1到n-1，执行：
29 若a[k]>a[j],则j<--k
30 3.t<--a[i];a[i]<--a[j];a[j]<--t;
31
32
33 最终的选择排序算法是：
34
35 void sortIntArray(int [],int n)
36 {
37 int i,j,k,t;
38 for(i=0;i<n-1;i++)
39 {
40 j=i; //把a[i]作为最大整数的初值
41 for(k=i+i;k<n;k++) //从a[i]到a[n-1]中选出最大整数
42 {
43 if(a[k]>a[i]) j=k;
44 t=a[i];
45 a[i]=a[j];
46 a[j]=t;
47 }
48 }
49 }