数据结构-C语言

绪论

数据

  • 什么是数据

    数据是描述客观事物的数值,字符以及能输入机器且能被处理的各种符号集合。

  • 数据元素

    数据元素是组成数据的基本单位，是数据集合的个体。

    • 数据项

      一个数据元素可以由一个或多个数据项组成,数据项,是有独立含义的最小单位，此时的数据元素通常称为记录

  • 数据对象

    性质相同的数据元素的集合,是数据的子集

  • 数据结构

    数据结构是相互之间存在一种或多种特定关系的数据元素的集合

    数据元素+ 特定关系 = 数据结构

  • 逻辑结构

    • 集合结构:
      1. 集合结构中的数据元素数据元素同属于一个集合
      2. 数据元素相互之间没有其他关系
    • 线性结构: 数据元素之间是一对一的关系
    • 树形结构: 数据元素之间存在一种一对的层次关系
    • 图形结构: 数据元素之间是多对多的关系

  • 物理结构

    • 定义: 又叫做存储结构,是值数据的逻辑结构在计算机中的存储形式
    • 数据存储结构: 把数据元素存储再地址连续的存储单元中
    • 链式存储结构: 把数据元素放在任意的存储单元里

  • 数据类型

    • 计算机中, 内存空间是有限的 ，不同类型的数据分配的内存空间大小不同
    • 在C 语言中,按照取值的不同,数据类型分为两类：
      • 原子型: 不可以再分解的基本类型,包括整型、实型、字符型等。
      • 结构型: 由若干个类型组合而成,是可以再分解的

  • 抽象数据类型ADT: Abstract Data Type

    • 是对已有的数据类型进行抽象
    • 抽象数据类型是值一个数据类型及定义在该模型上的一组操作
typedef 的使用 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
//
// Created by coder-itl on 2021/9/29.
//
#include "stdio.h"
#include "malloc.h"

typedef int zs; /* 为 int 再重新多取一个名字,zs 等价于 int */

int main() {
    /* typedef 的使用 */
    zs a = 10;
    printf("%d", a);
    return 0;
}
typedef.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
struct Student {
    int id;
    int stuBirthday;
} ST;



//
// Created by coder-itl on 2021/9/29.
//
#include "stdio.h"

typedef int zs; /* 为 int 再重新多取一个名字,zs 等价于 int */

typedef struct Student {
    int id;
    int stuBirthday;
} ST;

int main() {

   /* 等价形式 */
    ST st;
    st.stuBirthday = 2001;
    
 	/* 声明结构体变量 */
    struct Student sst;
    sst.stuBirthday = 2004;
    
    return 0;
}
时间复杂度

time.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 

int test(int n){
    /* 执行一次 */
    int sum = 0;
    /* 执行一次 */
    int i = 1;
    /* 
     * i<=n:执行 n 次
     * i++: 执行 n 次
     * */
    for(;i<=n;i++){
        /* 执行 n 次 */
        sum=sum+i;
    }
    /* 执行一次 */
    return sum;
    /*
     * 时间复杂度 = 1+1+n+n+n+1 = 3+3n = O(n);
     * */
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 

int test(int n) {
    /**
     * int i = 0;  执行一次
     * i<n: 执行 n 次
     * i++: 执行 n 次
     * time =  1+2n
     *
     * int j = 0;  执行一次
     * j<n: 执行 n 次
     * j++: 执行 n 次
     *time = 1+2n+n = 3n
     *
     * 循环: 外层循环走一次,内层循环走 n 次数
     * totalTime =  1+2n+n*(1+3n)+1 = 1+2n+n+3n^2+1 = +3n^2+3n+2
     */
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            /* 执行 n 次 */
            printf("timeout...");
        }
    }
    /* 执行一次 */
    return n;
    /*
     * 时间复杂度 = = O(n^2);
     * */
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/**
     * int i = 0; 执行 1 次
     * i<n: 执行 n 次
     * i++: 执行 n 次
     *
     * int j = 0; 执行 1 次
     * j<20: 执行 20 次
     * j++: 执行 20 次
     *
     * printf("coder-itl");  执行 20 次
     * 
     * 嵌套for循环: 外层循环执行一次,内层循环执行 n 次
     * time = 1+n+n+n*(1+20+20+20) = 2n+1+61n = 63n+1
     * O(n)
     */
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 20; j++) {
            /* 执行 20 次 */
            printf("coder-itl");
        }
    }
 
1
2
3
4
5
6
7
8
9
10
 
/* time = O(logn) */

   /* 执行 1 次 */
   int i = 1;
   /* 假设循环 x 次之后,i 就大于 n了,跳出循环m也就是说 2 的 X 次方等于 n ，那么 x = log以2为底 */
   while (i < n) {
       /* 每次都 乘以 2 */
       i = i * 2;
   }

 
1
 
T(n) = O(f(n)) = O(n)
  • T(n): 表示代码执行的时间
  • n： 表示数据规模的大小
  • f(n): 表示每行代码执行的次数总和
  • 因为这是一个公式,所以用f(n) 来表示,公式中的O，表示代码的执行时间T(n) 与f(n) 表达式成正比

大O 时间复杂度实际上并不具体表示代码真正的执行之间,而是代表代码执行时间随数据规模增长的变化趋势，所以,也叫做渐进时间复杂度,简称时间复杂度。

线性表

线性表定义:

线性表(Linear List) 描述: 线性表是 n 个类型相同数据元素的有限序列，对 n>0，除第一个元素无直接前驱、最后一个元素无直接后继外，其余的每个数据元素只有 一个直接前驱和一个直接后继，数据元素之间有一一对应的关系。

线性表的特点:

  • 它是一个序列
    • 数据元素之间是有序的
    • 数据元素之间是一对一的关系
  • 有限性: 线性表的数据元素之间个数是有限的

顺序表中元素存储位置的计算:

  • 如果每个元素占用8 个存储单元,a_i 存储位置是2000 单元,则a_(i+1) 存储位置是?

    假设线性表的每个元素需占用l 个存储单元,则第i+1 个数据元素的存储位置和第i 个数据元素的存储位置之间满足的关系是:LOC(a_(i+1))=LOC(a_1)+l，由此,所有数据元素的存储位置均可由第一个数据元素的存储位置得到:LOC(a_i)=LOC(a_1)+(i-1)*l

线性表的抽象数据类型

  • 线性表的抽象数据类型

    ADTList.png

    • 线性表的顺序结构

      线性表的顺序存储结构: 指的是用一段地址连续的存储单元一次存储线性表的数据元素 

    1
    2
    3
    4
    5
    6
    7
    		 
    #define MAX_SIZE 255
    typedef ine ElemType;
    typedef struct{
        ElementType datas[MAX_SIZE];
        int length;
    }SeqList;
    • 存储空间的起始位置: 数组datas 的存储位置
    • 线性表的最大存储容量: 数组长度 MAX_SIZE
    • 线性表的当前长度: length
    1
    2
    3
    4
    5
    6
    7
    8
    		 
    插入元素:
    	1. 下标 i 以及下标为 i 以后的所有元素后移
    	2. 下标 i 的位置放入数据元素 a

    注意:
    	1. 插入元素后的顺序表长度变为 n + 1
    	2. 插入元素后,最后一个元素的下标为 n
        3. C语言数组实现时,顺序表长度不能超过它的最大长度

    数据结构之顺序表的元素插入

    https://gitee.com/coder-itl/data-structure-c-202110/blob/main/dataStruct/SequenctList.c

    1
    2
    3
    4
    		 
    将第 i 个数据元素从顺序表(a_1,...,a_n)中删除
        1. 找到第 i 个位置的数据元素
        2. 将第 i 个数据元素以后的数据元素依次覆盖前一个位置
        3. 顺序表当前长度减 1

    数据结构之顺序表的元素插入

    https://gitee.com/coder-itl/data-structure-c-202110/blob/main/dataStruct/SequenctList.c