数据结构基本概念

基本概念

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;
}
    原文作者:小帅比simon
    原文地址: https://blog.csdn.net/lzjsqn/article/details/52965867
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞