数据结构学习：数据结构概念了解

数据结构课程的起源

1968年高德纳教授开创了数据结构这门学科，同年，数据结构作为计算机科学的学位课程。

数据结构研究什么

        研究非数值计算类型的程序问题；

        研究数据之间的组织和操作方式；

        研究数据的逻辑结构和存储结构；

为什么要学习数据结构

        学习C语言或者C++只是学了一个语法，就像武侠片里面学武功不仅要学心法还要学招式，这个心法就对应语法，这个招式就要通过学习数据结构来提高。数据结构可以培养专业的程序设计思维，提高使用程序语言描述解决方案的能力。

数据结构与算法的关系

        数据结构是研究数据之间的关系，解决实际问题的还是算法。

        算法是在一定的数据结构基础上来完成的，数据结构与算法是相互交融的。

不下降序列问题

由n个数组成的数列，分别是：a[1]、a[2] 、a[3] ...... a[n]，

若存在i1

则称为长度为m的不下降序列。

例如：3，18，7，14，10，12，23，41，16， 24

则：3，18，23，24是一个长度为4的不下降序列；

3、 7、 10 、12、 16、 24是一个当度为6 的不下降序列；

求：如何求最长不下降序列？如何求所有不下降序列？

学习数据结构需要具备的三大技术点：

C++面向对象技术

C++模板技术

C++异常处理技术

为什么有各种各样的程序存在，程序的本质是什么？

程序 = 数据结构 + 算法

程序是为了解决实际问题而存在的没从本质上而言，程序是解决问题的步骤的描述。

比如：怎样把大象放到冰箱里？

步骤：

1、打开冰箱门；

2、把大象放进去；

3、关上冰箱门。

对应的程序

Elephan* e = new Elephan;
 
Fridge* f = new Fridge;
 
f->open();
 
f->put(e);
 
f->close();

如何解决问题

首先确认问题的类型；

然后确认解决步骤；

解决问题的步骤也是有好差的区分的。

比如：求1到n之间的数累加和的三种算法

程序实例1：

#include 
 
using namespace std;
 
//方法1：使用两个for循环
long sum1(int n)
{
    long ret = 0;
    int* array = new int[n];
 
    //将数组填充进数组
    for(int i=0; i
    {
        array[i] = i + 1;
    }
 
    //数组元素累加
    for(int i=0; i
    {
        ret += array[i];
    }
 
    delete[] array;
 
    return ret;
}
 
 
//方法2：一个循环解决问题
long sum2(int n)
{
    long ret = 0;
    for(int i=1; i<=n; i++)
    {
        ret += i;
    }
 
    return ret;
}
 
//方法3：不用循环解决问题
long sum3(int n)
{
    long ret = 0;
 
    if(n>0)
    {
        ret = (1+n)*n/2;
    }
    else
    {
        ret = 0;
    }
 
    return ret;
}
 
 
 
int main()
{
    cout <<"sum1 = " << sum1(100) << endl;
    cout <<"sum2 = " << sum2(100) << endl;
    cout <<"sum3 = " << sum3(100) << endl;
    return 0;
}
 
 
 
int main()
{
    cout << sum1(100) << endl;
    return 0;
}

 显然3种方法都可以得出正确的结果，但是显然第三种方法的效率是最高的。好在哪里？

评价好程序的标准

用尽量少的时间解决问题；

用尽量少的步骤解决问题；

用尽量少的内存解决问题；

NASA用64K内存的代码就能实现探索外太空。

数据的概念

数据是程序的操作对象，用于描述客观事物，数据可以输入到计算机，可以被计算机程序处理。

数据元素：组成数据的基本单位

数据项：一个数据元素由若干数据项组成

数据对象：性质相同的数据元素的集合

struct Student //数据类型
{
    char* name;
    int age;
};
 
Student s; //数据元素
 
Student sArray[10]; //数据对象
 
s.name = "lili"; //数据项
s.age = 10;      //数据项

数据结构就是指数据对象中数据元素之间的关系。比如数组中，各元素之间存在固定的线性关系。

典型的数据结构

逻辑结构：

        集合结构：数据元素之间没有特定的关系，仅同属相同集合；

        线性关系：数据元素之间时一对一的关系；

        树形关系：数据元素之间存在一对多的层次关系；

        图形关系：数据元素之间时多对多的关系。

物理结构：

        顺序存储结构：将数据存储在地址连续的存储单元中；

        链式存储结构：将数据存储在任意的存储单元中，通过保存地址的方式找到相关联的数据元素。

算法是程序的灵魂

算法的特性：

        算法有输入：

        算法有输出：

        算法的有穷性：算法在有限的步骤会结束，不会无限循环

        算法的确定性：算法的每一步都有确定的含义

        算法的可行性：算法的每一步都是可行的

如何评价算法的好坏

如果两个算法都能满足功能性需求，在工程中怎么评判，怎么选择？

性价比是工程上最关注的。

事后统计法：比较不同算法对同一组输入数据的运行处理时间。

事前分析估算： 依据统计的方法对算法效率进行评估。

如何学习数据结构

1、从概念上形象的理解数据元素之间的关系

2、思考数据关系能解决什么问题；

3、思考基于这种关系能够产生哪些算法；

4、理解并熟悉最终的算法；

5、选择一种熟悉的语言编码实战。