数据结构和算法：01.定义

数据结构和算法-定义

• 知识点：

知识点：

1.数据结构算法基本概念

1.1 数据结构：

指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系，简单的理解就是元素之间的相互关系。

其中逻辑结构分为四类：

1. 集合结构
2. 线性结构
3. 树形结构
4. 图形结构

存储结构一般分为：

1. 顺序存储
2. 链式存储

1.2 算法

指特定问题求解步骤的描述。算法的特性有：输入，输出，有穷性，确定性和可行性。

算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量，也称之为时间复杂度和空间复杂度。

2. 算法的时间复杂度和空间复杂度

时间复杂度是一个函数，它定性描述了该算法的运行时间，时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。

常见的时间复杂度：

• 常数阶O(1)，
• 对数阶O( log ⁡ 2 n \log_2 n log2​n)，
• 线性阶O(n)，
• 线性对数阶O(n* log ⁡ 2 n \log_2 n log2​n)，
• 平方阶O( n 2 n^2 n2)，
• 立方阶O( n 3 n^3 n3)，
• k次方阶O( n K n^K nK)，
• 指数阶O ( 2 n 2^n 2n)。

举几个列：

// 比如我们现在 求 1+2+3+4+***+n
// 任何算法在特定执行的 n 步骤下，我们都可以推演出算法的复杂度（时间，空间）
// 简单的理解为执行的步骤
int sum1(int n){// n + 2 步 O(n)
    int sum = 0; // 1步
    for (int i = 0; i <= n ; ++i) { // n 步
        sum += i;
    }
    return sum;// 1步
}

int sum2(int n){ // O(1)
    return (1+n)*n / 2; // 1步
}

// 空间复杂度 反转一个字符串 aaa222bbb -> bbb222aaa
char* reverse1(char str1[],int n){ // O(n)
    // 第一种写法
    // 创建一个新的数组
    char* res = (char*)malloc(sizeof(char)*n);

    // 倒序循环
    for(int i = n - 1; i >=0; i--){
        // 赋值
        res[n - 1 - i] = str1[i];
    }

    return res; // 1
}

void reverse2(char str[],int n){// 空间复杂度是 O(1) 时间复杂度是 O(n)
    int mid = n / 2;
    for(int i = 0; i < mid; i++){
        // i 的位置和 i+mid 的位置进行交换
        // 交换 1 次交换是两次赋值
    }
}

作业：读一篇英文文档统计字符出现的个数

#include<stdio.h>
#include<stdlib.h>
//统计各字符的出现频bai率，只统du计ASC[0，127]的字符，中文字符不参加统计 
void tongji(int *c,FILE *fp){
 zhiintd;
  while((d=fgetc(fp))!=EOF){
    if (d>=0 && d<128) c[d]++;
  }
}

int main(){
    FILE *fp;
    int c[128],i;
    if ((fp=fopen("d:\\temp.txt","r"))==NULL){ //自行dao指定打开的文件 
     printf("打开文件失败\n");
     return 1;
    }
    
    for(i=0;i<128;i++){
        c[i]=0;
    }
    
    tongji(c,fp);
    fclose(fp);
    printf("字符\tASC码\t频率\n");
    for(i=32;i<128;i++){ //显示ASC字符是32以上的统计结果 
    if(c[i]!=0)
          printf("%c\t%d\t%d\n",i,i,c[i]);
    }
}