专栏首页Hongten算法与数据结构(一)

算法与数据结构(一)

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 Circle

3.数据结构

  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--->d

    2.树形结构

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    5

    3.复杂结构

1 G=<k3,R3>,k3={a,b,c},R3={<a,b>,<a,c>,<b,c>},G就是一个复杂结构。
2 
3                           a
4                          /   \
5                        b ---- c

4.算法

  算法是由有穷规则构成的为解决某一类问题的运算序列(方法或过程),

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python开发_python代码风格(coding style)

    Hongten
  • How to create a repository in Github with Eclipse?

    How to create a repository in Github with Eclipse? Here is an answer.

    Hongten
  • python开发_glob

    =============================================

    Hongten
  • 挑战程序竞赛系列(25):3.5最大权闭合图

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • 拓扑排序-HDU2647 Reward

    什么是拓扑排序? 简单来说,在做一件事之前必须先做另一(几)件事都可抽象为图论中的拓扑排序,比如课程学习的先后,安排客人座位等。 一个图能拓扑排序的充要条件...

    唔仄lo咚锵
  • shell脚本自动化采集性能sql(r2笔记39天)

    通过v$sql_monitor能够实时采集可能存在的sql性能问题,但是每次问题发生的时候采取采取措施就有点“晚”了,我们需要防患于未然,把一些潜在问题提前发现...

    jeanron100
  • 「POJ - 2318」TOYS (叉乘)

    有一个玩具盒,被n个隔板分开成左到u右n+1个区域,然后给每个玩具的坐标,求每个区域有几个玩具。

    饶文津
  • Codeforces Round #544 (Div. 3) D. Zero Quantity Maximization(思维)

    题目链接:http://codeforces.com/contest/1133/problem/D

    Ch_Zaqdt
  • Golang语言 -并行程序

    go在设计的时候,就有针对并行的语法 —-channel 和goroutine 前者 可以很方便的进行消息和数据传递,在取数据和拿数据的时候可以不用关心底层实现...

    李海彬
  • 如何在Ubuntu 16.04上使用Icinga监视主机和服务

    Icinga是一个开源监控系统,用于监控网络主机和服务的运行状况。在本教程中,我们将使用Icinga设置两种不同类型的监视配置。第一种是基于对主机外部服务的简单...

    灬半痴

扫码关注云+社区

领取腾讯云代金券