《数据结构笔记一》： 指针、结构体、动态内存分配、算法时间复杂度。
两个变量的值之间进行交换
#include<stdio.h>void swap(int a ,int b){int temp;temp = a;a = b;b = temp;printf("a = %d , b= %d\n"a,b);}int main(int argc, char const *argv[]){int m =5;int n = 10;swap(m,n);printf("m= %d,n = %d\n"m,n);return 0;}输出结果：
a10 b5
m 5 n10
指针与数组
在C语言中，指针与数组的关系十分密切
通过数组下标完成的操作都可以通过指针完成
一般来说，用指针编写的程序比用数组下标编写的程序执行速度快
例如
#include<stdio.h>int main(int argc ,char const *argv[]){int a[] = {11,12,13,14,15};int *p;p = a;printf( " %p\n ", a);printf(" %p\n ", p);printf(" %d\n ", *p) return 0;}输出结果：
0x7ffb2414610
0x7ffb2414610
11
可以看到 取 *p地址输出的是数组的首位元素
那如果想取数组的其他元素呢？ 怎么做
看下例子
#include<stdio.h>int main(int argc , char const **argv){int a[] = {11,12,13,14,15};int *p;p = a;//加入一个for循环 普通数组遍历for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++ ){printf( "%d\n", a[i] );}//加入一个for循环 指针遍历数组方式for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++){printf("%d \n"; ****(p + i) ); //给指针加一个整数，实际上是给这个整数和指针数据类型对应字节数的乘积 p = p+14}return 0 ;}输出结果：
11
12
13
14
15
11
12
13
14
15
C语言数据类型字节数对照表
| 数据类型 | 32位系统 | 64位系统 | 有符号范围（近似） | 无符号范围（近似） | 说明 |
|---|---|---|---|---|---|
char | 1 | 1 | -128 ~ 127 | 0 ~ 255 | 固定1字节，signed char和unsigned char范围不同 |
short int / signed short | 2 | 2 | -32,768 ~ 32,767 | 0 ~ 65,535 | 固定2字节 |
unsigned short int | 2 | 2 | - | 0 ~ 65,535 | |
int / signed int | 4 | 4 | -2,147,483,648 ~ 2,147,483,647 | 0 ~ 4,294,967,295 | 通常4字节（C标准要求至少2字节） |
unsigned int | 4 | 4 | - | 0 ~ 4,294,967,295 | |
long int / signed long | 4 | 系统依赖 | -2,147,483,648 ~ 2,147,483,647 | 0 ~ 4,294,967,295 | Windows 64位：4字节 Linux/macOS 64位：8字节 |
unsigned long int | 4 | 系统依赖 | - | 同signed long范围 | |
long long int | 8 | 8 | -9e18 ~ 9e18 | 0 ~ 1.8e19 | 固定8字节（C99标准引入） |
unsigned long long int | 8 | 8 | - | 0 ~ 1.8e19 | |
float | 4 | 4 | IEEE 754单精度 | - | 约6-7位有效数字 |
double | 8 | 8 | IEEE 754双精度 | - | 约15位有效数字 |
long double | 8/12/16 | 8/16 | 扩展精度 | - | GCC：16字节 MSVC：8字节 |
void* (指针) | 4 | 8 | - | - | 地址空间大小： 32位系统：4字节 64位系统：8字节 |
跨平台固定宽度类型（stdint.h）
| 类型 | 字节数 | 范围（有符号） | 范围（无符号） |
|---|---|---|---|
int8_t | 1 | -128 ~ 127 | 0 ~ 255 (uint8_t) |
int16_t | 2 | -32,768 ~ 32,767 | 0 ~ 65,535 |
int32_t | 4 | -2.1e9 ~ 2.1e9 | 0 ~ 4.2e9 |
int64_t | 8 | -9e18 ~ 9e18 | 0 ~ 1.8e19 |
典型系统对比
| 系统/类型 | long（64位系统） | 指针（64位系统） | long double |
|---|---|---|---|
| Windows 64位 | 4字节 | 8字节 | 8字节（MSVC） |
| Linux 64位 | 8字节 | 8字节 | 16字节（GCC） |
| macOS 64位 | 8字节 | 8字节 | 16字节 |
结构体的声明
结构体是一个或多个变量的集合，这些变量可以是不同的类型
struct 结构体名
{
数据类型 变量名；
数据类型 变量名；
}
例如
struct point{int x;char y;}结构体的初始化与调用
struct 结构体名 变量名
struct point p
编写一个函数，传入两个int参数，在函数创建一个结构体point类型的变量
将传入的两个参数分别赋值给该结构体变量的x和y，最后将该结构体变量返回
#include<stdio.h>struct point createPoint(int x ,int y){struct point temp;temp.x = x;temp.y = y;return temp;}int main(int argc, char const *argv[]){struct point p;p = createPoint(5,10);printf( "%d\n", p.x );printf( "%d\n", p.y);return 0; }简化写法
#include<stdio.h>typedef struct{int x;int y;}po;int main(int argc, char const *argv[]){po p;p.x = 5;p.y = 10; printf( "%d\n", p.x );printf( "%d\n", p.y);return 0;}内存的分类
c程序编译后，会以三种形式使用内存
静态/全局内存
静态声明的变量和全局变量使用这部分内存，这些变量在程序开始运行时分配
直到程序结束才消失
自动内存(栈内存)
函数内部声明的变量使用这个部分内存，在函数被调用时才创建
动态内存（堆内存）
根据需求编写代码动态分配内存，可以编写代码释放，内存中的内容直到释放才消失
例如 动态内存分配
在C语言中，动态分配内存的基本步骤
- 使用malloc函数分配内存
- void* malloc(size_t)
- 如果成功，会返回从堆内存上分配的内存指针
- 如果失败，会返回空指针
- 使用分配的内存
- 使用free函数释放内存
- 返回值
示例：
#include<stdio.h>#include<stdlib.h>int main(int argc , char const* argv[]){int *p;p = (int*) malloc (sizeof(int) );** p* = 15;printf(''%d\n", *p);free(p);return 0;}算法时间复杂度
算法要满足5个特性
有穷性、确定性、可行性、输入、输出
评价算法好坏的基本标准
正确性、可读性、健壮性、高效性
时间复杂度
也称渐近时间复杂度
T(n) = O( f(n) )
随着问题规模n的增大，算法执行时间和增长率和f(n)增长率成正比
计算时间复杂度例子
#include<stdio.h>int main(int argc , char const *argv){for(int i = 1 ; i <= n ; i++) //时间复杂度 频度为 n+1{for(int j = 1 j <= n ; j++) //频度为 n*(n+1){c[ i ][ j ] = 0; //频度为 n * nfor(int k = 1; k <= n ;k++) //频度为 n * n * (n+1){c[ i ][ j ] = c[ i ][ j ] + a[ i ][ k ] * b[ k ][ j ]; //频度为 n * n * n 最终时间复杂度 T(n) = O(n³) }}}}对算法时间复杂度的度量，通常只讨论算法在最坏的情况下的时间复杂度，即分析在最坏的情况下，算法执行的时间上界。