算法与数据结构(一)

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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

小米OJ刷题日志

$f[i][j]$表示第一个队列匹配到了$i$位置,第二个队列匹配到了$j$位置是否可行

53620
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

11310
来自专栏python读书笔记

《python算法教程》Day3 - 递归递归简介代码示例

这是《python算法教程》的第3篇读书笔记。由于之前看书的效率太低了,所以拖了一个多星期才写第三篇读书笔记。这次主要简单总结一下递归(recursion)。 ...

31280
来自专栏chenjx85的技术专栏

leetcode-55-跳跃游戏

1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

5110
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

34440
来自专栏Fish

CCF 画图

问题描述   用 ASCII 字符来画图是一件有趣的事情,并形成了一门被称为 ASCII Art 的艺术。例如,下图是用 ASCII 字符画出来的 CSPR...

25460
来自专栏数据结构与算法

深海中的STL—nth_element

如果让你求区间第k大,你会怎么做呢? 主席树?确实是个不错的选择(不过像我这种垃圾还是乖乖打暴力吧) 在c++的stl库中,提供了nth_element...

38870
来自专栏人工智能LeadAI

讨厌算法的程序员 1 | 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生出一...

30670
来自专栏JavaQ

高并发编程-HashMap深入解析

在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存...

11020
来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

17640

扫码关注云+社区

领取腾讯云代金券