基本概念

基本概念

1.数据结构起源

计算机除了数值计算问题以外还需要解决现实生活中很多的问题，而这些问题涉及到现实中很多复杂的对象，不同对象之间具有复杂的关系，数据结构正是描述这些对象之间复杂关系的。但数据结构并非研究复杂算法的一门学科。

2.数据结构基本概念

数据:
　　程序中要操作的对象，用于描述客观事物。可被输入到计算机，也可被计算机处理。如：

　　int a,float pI;

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

int array[20];
Teacher teachers[30];

数据元素:
　　组成数据的基本单位（集合中具体的一个元素／成员/节点）

array[5],teachers[7];

数据项：
　　数据元素中基本组成部分
数据结构：
　　数据对象中数据元素（节点）之间的关系

3.数据结构的逻辑关系

4.数据结构的物理结构

5.数据运算

6.算法

特定问题的求解步骤，表现为指令的有序集合。语言不重要，思想更重要！是解决问题的思想和方法！

7.数据结构和算法的关系

　　数据结构只是静态的描述数据元素之间的关系，算法是在数据结构的基础上设计和现实相应的解决问题的步骤。高效的程序需要有效的结合数据结构和算法。相辅相成。

8.算法特点

输入：具有0个或多个输入
输出：至少有一个输出
有穷性：在有限步骤之后就会结束
确定性：每一步都有确定的含义不出现二义性
可行性：在计算机上可运行实现

9.算法效率的度量

算法最终要编译成具体的计算机指令
每一条指令在具体的计算机CPU上运行时间是固定的
通过具体的n的步骤的多少就可以推导出算法的复杂度

9.1事后统计法

含义：
　　比较不同算法对同一组输入数据的运行处理时间
缺陷

为了获得不同算法的运行时间必须编写相应程序

运行时间严重依赖硬件以及运行时的环境因素

算法的测试数据的选取相当困难

事后统计法虽然直观，但是实施困难且缺陷多

9.2事前分析估算

含义
　　依据统计的方法对算法效率进行估算
影响算法效率的主要因素

算法采用的策略和方法

问题的输入规模

编译器所产生的代码

计算机执行速度

9.3常规估算注意事项

注意1：判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。
注意2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

10.大O表示法

算法效率严重依赖于操作(Operation)次数数量
在判断时首先关注操作数量的最高次项
操作数量的估算可以作为时间复杂度的估算
O(5) = O(1)
O(2n + 1) = O(2n) = O(n)
O(n2+ n + 1) = O(n2)
O(3n3+1) = O(3n3) = O(n3)

11.空间复杂度

算法的空间复杂度通过计算算法的存储空间实现
S(n) = O(f(n))
其中，n为问题规模，f(n))为在问题规模为n时所占用存储空间的函数
大O表示法同样适用于算法的空间复杂度
当算法执行时所需要的空间是常数时，空间复杂度为O(1)

空间与时间的策略

多数情况下，算法执行时所用的时间更令人关注
如果有必要，可以通过增加空间复杂度来降低时间复杂度
同理，也可以通过增加时间复杂度来降低空间复杂度

12.面试题（时间和空间的互换）

在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。设计一个算法，找出出现次数最多的数字。

#include <iostream>
using namespace std;
#define MAX 1000
void search(int array[],int len,int *res_num,int *count)
{
    int i = 0;
    int sp[MAX] = {
  0};
    int max = 0,tmp = 0;
    for (i = 0; i < len;i++)
    {
        sp[(array[i]-1)]++;
    }

    for (i = 0; i < MAX; i++)
    {
        if (max < sp[i])
        {
            max = sp[i];
            tmp = i + 1;
        }
    }
    *res_num = tmp;
    *count = max;
}

int main(void)
{
    int array[] = {
  1,2,5,6,2,4,7,8,9,10,1,23,9,3,9,4,9,12,9,222,9,111,9};
    int max_num = 0,cnt = 0;
    int len = sizeof(array) / sizeof(array[0]);
    search(array, len, &max_num,&cnt);

    cout << "max_num: " <<max_num<<"count : "<<cnt<< endl;
    cout<<"Hello!"<<endl;
    return 0;
}

声明：本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。

数据结构基本概念