C语言数据结构Java实现01—-算法概述

 

【声明】 

迎接转载,但请保留随笔原来出处→_→ 

生命壹号:http://www.cnblogs.com/smyhvae/

著作来源:http://www.cnblogs.com/smyhvae/p/4724692.html

 

【正文】 

 

 

一、数据结构涵盖的情节:

C语言 1

 

二、算法的基本概念:

1、算法的定义:

Algorithm,是对特定问题求解步骤的一种描述,它是命令的点滴系列,其中每一条指令表示一个或者三个操作。

2、算法的表征:

  • 商朝性:指令连串是零星的
  • 引人注目:每条语句的意义明确,无二义性
  • 动向:每条语句都应在点滴的年月内到位
  • 输入:零个要么四个输入
  • 出口:一个或者六个出口

3、算法与程序的界别:

程序:

  (program)程序是软件开发人士按照用户需要开发的、用程序设计语言描述的适合统计机执行的指令(语句)系列。

先后包含的两个元素:

数据结构

算法

程序设计艺术

编程语言

先后与算法不同。程序是算法用某种程序设计语言的具体贯彻。程序可以不满意算法的商朝性,比如操作系统也是一种程序,如果你愿意,你的电脑可以直接开着,保持操作系统的周转。

比如:

while(true)

{

...

} //是一段程序,但不是一个算法

 

4、程序、算法、软件之间的关系:

先后:算法的电脑实现。用某种编程语言实现。

算法:表示问题的解。

软件:程序+文档

正如图所示:

C语言 2

次第设计=数据结构+算 法

 

三、数据类型:

1、数据类型:

是指一个值的汇聚和概念在聚集上的操作集合。例如:java的整数类型(Integer),就不仅仅意味着整数数值的聚集,还包括对整数类型举行的操作集合,加、减、乘、除、模等操作。

咱俩普通所指的数据类型是某种高级语言帮助的主导数据类型。 
比如java的主干数据类型:int、double、float、char等等。

Java中的数据类型:

C语言 3

2、抽象数据类型:

一个数学模型以及定义在这一个模型上的一组操作(由用户定义,用以代表应用问题的数据模型)。

看起来抽象数据类型和数据类型的概念基本相同。不同点在于:数据类型平时是指某种高级语言的,而抽象数据类型用户重新规划,一种概念。这里的”抽象”的含义在于数学抽象。

  • 原子类型:比如整型
  • 稳定聚合类型:比如复数,四个实数确定的先后构成
  • 可变聚合类型:比如汽车类型,构成的成份是不确定的。(因为小轿车、大卡车的咬合是例外的)

抽象数据类型抽象的层系越高,那么可复用性也越高。比如:java中的Object是对持有目的的纸上谈兵,那么就足以看成所有类的父类。

 

四、抽象数据类型的表示(代码举例):

  • C语言使用结构体
  • Java语言应用类

下边分别用C语言与java语言,来定义学生抽象数据类型。已知学生的信息如下:

学号:111222

姓名:生命壹号

性别:男

出生日期:1991-11

专业:电子与通信工程(计算机方向)

电子邮箱:smyhvae@163.com

 

1、用C代码定义一个学员类:

test1.c:

#include <stdio.h>

//日期结构体
typedef struct 
{
  int year;//年
  int month;//月
  int day;//日      
}Date; 

//学生结构体 
typedef struct
{
  char sid[20];//学号
  char name[20];//姓名
  char gender;//性别
  Date birthday;//出生日期 
  char contact[50];//联系方式         
}Students;

void PrintStudentsInfo(Students s)
{
   printf("学号:%s\n",s.sid); 
   printf("姓名:%s\n",s.name);
   printf("性别:%c\n",s.gender);
   printf("出生日期:%d-%d-%d\n",s.birthday.year,s.birthday.month,s.birthday.day);
   printf("联系方式:%s\n",s.contact);      
}

int main()
{
  Students s1;//生成一个学生对象
  Date d1;
  d1.year = 1995;
  d1.month = 6;
  d1.day =30;
  strcpy(s1.sid,"S0001");
  strcpy(s1.name,"张三丰");
  strcpy(s1.contact,"西安市高新四路50号");
  s1.gender = 'M'; 
  s1.birthday = d1;
  PrintStudentsInfo(s1);
  getch();
  return 0;    
}

 运行效果:

C语言 4

 

 2、用Java代码定义一个学员类:

(1)Student.java:

 1 package test1;
 2 
 3 import java.text.SimpleDateFormat;
 4 import java.util.Date;
 5 
 6 /**
 7  * Created by smyhvae on 2015/8/12.
 8  */
 9 public class Student {
10     String num; //学号
11     String name; //姓名
12     char sex; //性别
13     Date birthday; //出生日期
14     String contact; //联系方式
15 
16     public String getNum() {
17         return num;
18     }
19 
20     public void setNum(String num) {
21         this.num = num;
22     }
23 
24     public String getName() {
25         return name;
26     }
27 
28     public void setName(String name) {
29         this.name = name;
30     }
31 
32     public char getSex() {
33         return sex;
34     }
35 
36     public void setSex(char sex) {
37         this.sex = sex;
38     }
39 
40     public Date getBirthday() {
41         return birthday;
42     }
43 
44     public void setBirthday(Date birthday) {
45         this.birthday = birthday;
46     }
47 
48     public String getContact() {
49         return contact;
50     }
51 
52     public void setContact(String contact) {
53         this.contact = contact;
54     }
55 
56     @Override
57     public String toString() {
58 
59         SimpleDateFormat sdf = new SimpleDateFormat("YYYY-mm-dd"); //将Date日期转化为String字符串打印出来
60 
61         return "Student{" +
62                 "num='" + num + '\'' +
63                 ", name='" + name + '\'' +
64                 ", sex=" + sex +
65                 ", birthday=" + sdf.format(birthday) +
66                 ", contact='" + contact + '\'' +
67                 '}';
68     }
69 
70 }

 

(2)JavaTest.java:(给学员类赋值并打印出来)

 1 package test1;
 2 
 3 import java.text.ParseException;
 4 import java.util.Calendar;
 5 import java.util.Date;
 6 
 7 /**
 8  * Created by smyhvae on 2015/8/12.
 9  */
10 public class JavaTest {
11 
12     public static void main(String[] args) throws ParseException {
13 
14         Student s = new Student();
15         s.setNum("111222");
16         s.setName("生命壹号");
17         s.setSex('男');  //这里面赋值可以用中文
18         s.setContact("smyhvae@163.com");
19 
20         Calendar calendar = Calendar.getInstance();
21         calendar.set(1991, 11, 28);
22         Date date = calendar.getTime();
23         s.setBirthday(date);
24 
25         System.out.println(s.toString());
26 
27     }
28 
29 } 

运作效果如下:

C语言 5

  

五、算法的设计目的:

1、算法的宏图目的:

(1)正确性:满意实际问题的解,基本目的。

(2)可读性:有利于人去精晓算法。

(3)健壮性:输入非法数据,能恰到好处做出处理,不爆发莫名其妙的出口。

(4)高效性:包括时间的高效性(日子复杂度)和空间的高效性(空中复杂度)。

2、算法性能目标:

(1)算法的流年效用也称之为时间复杂度。

(2)算法的半空中效率也号称空中复杂度。

(3)同一问题可用不同算法解决,而一个算法的质地优劣将影响到算法乃至程序的频率。算法分析的目的在于采纳适合算法和立异算法。一个算法的评论重要从岁月复杂度和空间复杂度来考虑

(4)算法时间的高效性和空间的高效性平日是争论的。所有一般只会取一个平衡点。(这里反映的是一种军事学思想,探讨总结机,不就是商量时间和空中的定义嘛,鱼与熊掌不可兼得啊)

(5)平时大家假使程序运行在内存中,且内存容量充分使用,所以更多的是钻探时间复杂度。

 

六、算法的时刻复杂度:

算法的日子复杂度反映了算法执行的日子长度。度量一个算法在电脑上推行的光阴一般有两种艺术:

  1.事后总结法:

  2.事先分析法:(常用)

    编写算法使用的高级语言

    编程爆发的机器语言代码质地

    机器指令执行进度

    问题规模

注:算法的光阴复杂度是由最深层嵌套语句的频度决定的。

 

2、O()函数:

  代表算法的命宫效用与算法所处理的多少元素个数n函数关系的最常用函数,即O()函数。

定义:

  一般境况下,算法中基本操作重复执行的次数是问题规模n的某部函数,用T(n)表示,若有某个帮忙函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))
为算法的渐进时间复杂度,简称时间复杂度。看下图便知:

C语言 6

C语言 7

动静一:T(n)与问题规模n无关

当算法的光阴复杂度T(n)与题材规模n无关时,此时算法的时光复杂度T(n)=O(1)。

 

情状二:T(n)与问题规模n有关

例1:设数组a和b在后边部分已经赋值,求如下多少个n阶矩阵相乘算法的时间复杂度:

for(i=0;i<n;i++)
 {
   for(j=0;j<n;j++)
   {
     c[i][j]=0;  //基本语句1
     for(k=0;k<n;k++)
     {
        c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本语句2
     }
   }
 }

 上方代码中:

C语言 8

  

例2:设n为如下算法处理的多少元素个数,求算法时间复杂度。代码如下:

for(i=1;i<=n;i=i*2)
{
   System.out.println(i);
}

 分析:

C语言 9

  

例3:分析冒泡排序算法的年华复杂度。代码如下:

//冒泡排序算法
    public static void bubbleSort(int[] data) {

        if (data == null) {
            return;
        }

        for (int i = 0; i < data.length - 1; i++) {
            boolean flag = false;

            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }

            if (!flag) {
                return;
            }
        }
    }

 时间复杂度分析:

(1)最佳状态下,冒泡排序算法只需要遍历一遍就能确定数组已经排序好了,此时的时刻复杂度为O(n);

(2)最差情况下,需要实行n-1次遍历,则需举办n(n-1)/2次相比和笔录移动,此时冒泡排序算法的流年复杂度T(n)=O(n2)。

 

3、时间复杂度的尺寸关系:

以下六种总括算法时间的多项式是最常用的。其涉及为:

C语言 10

指数时间的关系为:

C语言 11

当n取很大的值时,指数时间算法和多项式时间算法在所需时日上特别悬殊。

小知识:

NP(nondeterministic
polynomial)题材:是指算法复杂度难以用多项式表示的题目,算法复杂度经常是n的指数级,常规算法很难求解。

 

七、算法的空间复杂度:

空中复杂度是指算法在运行期间所急需的内存空间的多寡级。记作:S(n)=O(f(n)),其中n为问题的框框(或大小)。            

注:由于多数算法的空中复杂度问题并不严重,并且算法的上空复杂度分析方法和算法的时日复杂度分析方法基本相同,所以一般数据结构只谈谈算法的日子复杂度,不研究算法的半空中复杂度。

代码举例:分析如下算法的上空复杂度

static void reserse(int[] a,int[] b)
{
   int n= a.length;
   for(int i=0;i<n;i++)
   {
      b[i]=a[n-1-i];
   }
} 

上边代码中,当程序调用reserse(a,b)函数时,要分配的内存空间包括:引用a,引用b,局部变量n和有些变量i;

因而f(n)=c;其中c为常量。所以该算法的半空中复杂度S(n)=O(1)。

 

八、总结:

算法的年华复杂度和四个因素有关:算法中的最大嵌套循环层数;最大嵌套循环结构中老是循环的次数。

一般的话,具有多项式时间复杂度的算法是足以接受的;具有指数(不是对数)时间复杂度的算法,只有当n丰裕刻钟才得以利用。一般功能较好的算法要控制在O(N)要么O(log2
N)

 

手有玫瑰,赠人余香。支付宝扫一扫吧:

C语言 12