首页 随笔

[TOC]

# 1，数据结构与算法入门

程序=数据结构+算法

研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作

因为操作对象和操作对象之间的关系不同产生不同的数据结构

# 算法

何为算法，使用计算机 C 语言编程计算 1 到 100 的和（1+2+3+……+100）多数会给出这样的答案

#include <stdio.h>
int main() {
    int ans=0,i;
    for(i=1;i<=100;i++){
        ans+=i;
    }
    printf("%d",ans);
    return 0;
}

循环计算了一百次，但是如果我们使用等差数列求和

#include <stdio.h>
int main() {
    int ans=(1+100)*100/2;
    printf("%d",ans);
    return 0;
}

使用更加简单的方式，用较小的计算量完成计算

# 算法的特性

  1. 输入输出：
    算法具有 0 个或者多个输入，至少一个输出
  2. 确定性：
    算法的每一步都具有确定的含义，无二义性，即相同的输入得到的输出结果相同
  3. 有穷性
    每个算法都应该在有限的时间内完成
  4. 可行性
    一个算法是可以被执行的，即算法的每个操作都可以通过已经实现的基本运算执行有限次数来完成

# 算法的设计要求

  1. 正确性：算法能够满足指定的功能，能够得到正确答案
  2. 健壮性：当输入的数据不合法时，也能够做出相应的处理
  3. 可读性：指算法是可以阅读，理解和交流的
  4. 耗时低占用空间少（高效性）：运行时间（Running time）与占用空间（Storage space）概念，在设计算法时，我们总是希望能够更少的使用时间和空间达成我们的目标。

# 基本概念和术语

数据是信息的载体，是可以被计算机识别，存储并加工处理的描述客观事物的信息符号的总称

数据元素是数据的基本单位，数据元素由若干数据项组成
数据项是构成数据元素的最小单位

image-20220905152622667

数据对象：相同性质数据元素的集合，是数据的一个子集

数据结构：数据结构 = 数据对象 + 结构（带结构的数据对象）
数据对象不是孤立存在的，他们之间存在某种关系，数据对象之间的关系成为结构

# 数据结构

数据结构的两个层次：

1、逻辑结构

  1. 数据的逻辑结构是从数据元素的逻辑关系上描述数据的。
  2. 是指数据元素之间的逻辑关系的整体，通常是从求解问题中提
    炼出来的。
  3. 数据逻辑结构与数据的存储无关，是独立于计算机的。

2、物理结构

  • 数据元素及其关系在计算机存储器中的存储方式。

逻辑结构实例

  • 集合

数据元素只是属于一个集合，无其他关系

image-20220906150436900

  • 线性结构

一对一，线性表，栈，队列

image-20220906150444092

  • 树形结构

一对多

image-20220906150452330

  • 图形结构

多对多

image-20220906150458844

接下来一个列题

image-20220905155124056

image-20220905155321699

image-20220905155137275

数据结构分 3 个方面

逻辑结构，储存结构，数据运算

数据元素之间的逻辑关系是数据的逻辑结构

数据元素及其关系在计算器中的储存方式是数据的储存结构（物理结构）

施加在该数据上面的操作是数据运算

同一逻辑可以对应多种储存结构
同样的运算，在不同的储存结构中，其实现过程是不同的

# 存储结构

顺序储存：

借助元素在存储器中的相应位置来表示数据元素间的逻辑关系

链式存储结构

借助指示元素存储地址的指针表示数据元素间的逻辑关系

# 数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称

数据类型和数据结构之间的关系：数据类型就是已经实现了的数据结构

# 抽象数据类型（ADT）：

更高层次的数据对象，可以通过固有的数据类型来表示或实现

抽象数据类型（Abstract Data Type，ADT）只是一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。

# 算法分析

# 算法的时间复杂度

时间复杂度表示一个程序运行所需要的时间，其具体需要在机器环境中才能得到具体的值，但我们一般并不需要得到详细的值，只是需要比较快慢的区别即可

时间频度中，n 称为问题的规模，当 n 不断变化时，时间频度 T (n) 也会不断变化。
T（n)/f (n) 的极限值为不等于零的常数，则称 f (n) 是 T (n) 的同数量级函数。记作 T (n)=Ｏ(f (n)), 称Ｏ(f (n)) 为算法的渐进时间复杂度，简称时间复杂度。

# 度量时间复杂度的两种方法

  1. # 事后统计法

    在程序运行结束之后直接查看运行时间的方式进行时间复杂度的统计
    （特别依赖计算机环境，算法的测试困难，有时一套算法需要海量的数据才能真正比较出效果）

  2. # 事先估计法

    事先统计法采取在计算机编译程序前对该算法进行预估的方式估算。

# 算法的空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。

a) 固定部分。这部分空间的大小与输入 / 输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

b) 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

# 程序允许时的内存与地址

# 内存

image-20220913002747179

首先看这张图，可以看到每一个数据都有一个地址与其对应，也是因为有地址的存在，我们才可以使用计算机轻易的去访问一个数据

接下来可以用一串 c 语言代码来体现数据喝地址的关系

#include<stdio.h>
int main(){
    int i;
    char array[11]="ACDEQSFVCK";
    for(i=0;i<10;i++){
        printf("The %c Address is %x \n",array[i],&array[i]);
       //% x 可以换成 % p 都是十六进制表示，只不过 % p 会把所有的位数显示出来
    }
    return 0;
}

image-20220913004106041

可以看到这是一段连续的地址，当你把 char 类型换成 int 型之后可能又不太一样，因为 char 是 1 字节的，而 int 占 4 字节，所以 int 的地址会变成 4 个一跳的方式往上增长。

# 两个必须学会的函数知识

# 1. Malloc 函数

malloc（）函数在堆中申请分配一个大小为 size 个字节的连续内存空间，若成功分配，则返回一个指向所分配空间起始地址的指针，否则返回空指针（NULL）。

# 2.Free 函数

free（）函数用来释放已分配的内存空间，参数 p 是待释放的内存空间的首指针

总结来说 malloc 就是用来申请内存空间，而 free 是为了释放内存空间

#include<stdio.h>
#include<stdlib.h>
int main(){
    int *p;     // 定义一个指向整形的指针变量
    p=(int*)malloc(5*sizeof(int));  // 申请 5 个整形大小的内存空间并返回起始地址给 p
    if(p==NULL){    // 申请失败
        // 执行申请失败的代码，一般 print 一个报错
        exit(1);    // 退出
    }
    p[0]=1000;  // 为空间中添加数据
    printf("%d",p[0]);  // 打印这个数据
    free(p);    // 释放 p 的内存空间，此时 p 依旧存在，只不过失去了指向的对象，成了野指针
    p=NULL; // 为其赋 NULL，此时它不再是一个野指针
    return 0;
}

整个内存申请释放的过程