（C）数据结构基本认识，必要知识点复习

1. 定义

1.1 基本认识

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。简单来说，它就是组织和存储数据的方式，使得数据能够被高效地访问、修改和处理。例如，我们可以把一个班级学生的信息（姓名、年龄、成绩等）看作是数据元素，而将这些数据元素按照某种规则（如表格形式、链表形式等）组织起来，这个规则和相应的组织方式就是数据结构。

1.2 算法

算法是对特定问题求解步骤的一种描述，是为了实现某个任务而规定的一个有限长的操作序列。它是在有限步骤内求解某一问题所使用的一组定义明确的规则，包括对数据的输入、处理和输出等操作。

2. 需要学习的前置知识

函数
数组
字符串
指针
内存解析
结构体

3. 复习

3.1 函数

函数是一段被命名的、独立的代码块，它可以接收输入参数（也可以没有输入参数），并执行一系列的操作，最后返回一个结果（也可能没有返回值）。它是程序的基本构建块之一，用于将复杂的程序分解为可管理的、具有特定功能的小单元。

可以增加代码复用性，降低编程难度。函数不被调用时不会执行。对内隐藏细节，对外暴露接口

3.2 字符串

在C语言中没有字符串类型，使用的是字符类型的数组

3.2.1 字符串初始化

#include<stdio.h>
#include<string.h>
int main(){
	char str[12];
	strcpy(str, "Hello World");

	return 0;
}

3.3 内存

3.3.1 计算机体系结构

3.3.2 虚拟内存地址

内存条，显卡，各种适配卡都有其各自的存储地址空间
操作系统将这些设备的存储地址空间抽象成一个巨大的一维数组空间
对于内存的每一个字节会分配一个32位或64位的编号，这个编号称为内存地址

需记住每种类型所占的字节长度

3.4 数组

相同数据类型的集合

数组的长度一旦确定就不能改变

数组中的每一个元素可以用下标表示位置，如果一个数组中有n个元素
那么下标的取值范围为 0 ~ n-1

使用取地址符 & 获取数组的地址时，返回的是数组第 0 个元素的地址（首地址）

sizeof函数：通配符为%zu，返回函数参数在内存中的字节数。可以用来计算数组长度

3.5 指针

指针是用来存放内存地址的变量

int a;	//声明一个整型变量
int *p;	//声明一个指针变量，该指针指向一个int类型值的内存地址

间接引用操作符 * 返回指针变量的指向地址的值

3.5.1 指针与数组

在C语言中，指针与数组的关系十分密切
通过数组下标能完成的操作都可以通过指针完成

一般来说，用指针编写的程序比用数组下标编写的程序执行速度快

#include<stdio.h>
int main(){
	int arr[] = {15, 22, 3, 45, 23};
	int *p;
	p = arr;
	printf("%p\n", arr);
	printf("%p\n", p);
	printf("%d\n", *p);

	return 0;
}

输出结果：

000000000061FE00
000000000061FE00
15

3.5.2 指针做算数运算

给指针加上一个整数，实际上加的是这个整数和指针数据对应类型的字节数的乘积

3.6 结构体

结构体是一个或多个变量的集合，这些变量可以是不同的类型

3.6.1 结构体的声明

struct point{
	int x;
	int y;
};

3.6.2 结构体的初始化与调用

struct point p; //p为变量名

p.x = 10;
p.y = 15;

3.6.3 实例——创建一个结构体封装函数

#include<stdio.h>
//声明结构体
struct point {
	int x;
	int y;
};

//封装函数
struct point createPoint(int x, int y) {
	struct point temp;
	temp.x = x;
	temp.y = y;
	return temp;
}

//主函数
int main() {
	struct point p;
	p = createPoint(5, 10);
	printf("%d\n", p.x);
	printf("%d\n", p.y);
	return 0;
}

3.6.4 结构体与指针

在一些场景中，如果传递给函数的结构体很大，使用指针方式的效率通常更高

//pp指向一个point结构体：
struct point *pp;

//为pp所指向的结构体中的属性赋值：
(*pp).x = 10;
(*pp).y = 5;

//为使用方便，C语言提供了另一种间歇方式：箭头符号（arrow）
pp -> x = 10;
pp -> y = 5;

3.6.7 类型定义

对某一数据类型进行重新定义；起别名

typedef 数据类型别名

typedef int zx;

zx num = 10;

对结构体起别名，以省略struct

typeddef struct point{	//point结构体名可省略
	int x;
	int y;
}aa;					//aa即为别名
aa p;					//声明时不再需要struct

3.7 内存分类

C程序编译后，会以三种形式使用内存：

静态/全局内存
程序运行开始时分配，程序终止时消失
自动内存（栈内存）
函数内部声明的变量使用这部分内存，在函数被调用时才创建
动态内存（堆内存）
根据需求编写代码动态分配内存，可以编写代码释放，内存中的内容直到释放才消失

3.7.1 动态分配内存

基本步骤：

使用malloc（memory allocate）函数匹配内存
```
p = void* malloc(size_t);
/*void*表示是通用数据类型的指针*/  
```
如果成功，会返回从堆内存上分配的内存指针
如果失败，会返回空指针
使用分配的内存
使用free函数释放内存

实例：

#include<stdio.h>
#include<stdlib.h>
int main(){
    int *p;
    p = (int*)malloc(sizeof(int));
    *p = 15;
  
    printf("%d\n", *p);
    free(p);
    return 0;
}

结构体实例：

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int x;
    int y;
} po;

int main(){
    po *p;
    p = (po*)malloc(sizeof(po));
    p->x = 5;
    p->y = 10;
    printf("%d\n", p->x);
    printf("%d\n", p->y);
    return 0;
}