本文主要内容：数据结构类型，算法，时间复杂度，空间复杂度，内存分段。
程序=数据结构+算法
数据结构类型
1.逻辑类型
(1)线性结构（1:1）：
顺序表
链表
栈（FILO）
队列（FIFO）
(2)非线性结构：
层次结构（1:N）---树状结构
网状结构（N:N）---图
2.存储类型
存储设备内部数据之间的关系
(1)顺序存储
如数组，堆区(malloc)结构体内部字符串
方便查找不方便增删。
(2)链式存储
方便增删不方便查找。
(3)索引存储
如字典，顺序+链式。
(4)散列存储
哈希(hash)算法.
3.运算
增，删，改，查，排列
算法
1.时间复杂度
评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
规则：
多项式：保留最高次幂项，砍去系数。
常数：1。
inta=1;a=a+1;//执行次数是2次.//这个算法的时间复杂度为O(1).for(inti=0;in;i++){//时间复杂度为O(1)的算法...}//上面算法循环体中的代码执行了n次，因此时间复杂度为O(n).//执行次数是线性的.for(intnumber=1;numbern;number*=2){//时间复杂度为O(1)的算法...}//随着number每次乘以2后，都会越来越接近n，//当number不小于n时就会退出循环。假设循环的次数为X，//则由2^x=n得出x=log?n，因此得出这个算法的时间复杂度为O(logn)。//执行次数是对数的.for(inti=0;in;i++){for(intj=0;jn;i++){//复杂度为O(1)的算法...}}//内层循环的时间复杂度已经得知是O(n)，现在经过外层循环n次，//那么这段算法的时间复杂度则为O(n2)。//执行次数是一个多项式.for(inti=0;in;i++){for(intj=0;ji;j++){//复杂度为O(1)的算法}}//内循环中intj=0,ji。//当i=0时，内循环执行了0次；i=1时内循环执行1次，//当i=n-1时执行了n-1次，我们可以推算出总的执行次数为：//n+(n-1)+(n-2)+(n-3)+……+1//=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……//=(n+1)+(n+1)+(n+1)+(n+1)+……//=(n+1)n/2//=n(n+1)/2//=n2/2+n/2//只保留最高阶，因此保留n2/2再砍去系数//那么这段算法的时间复杂度则为O(n2)。
常见：
冒泡：n^2
快排：平均nlog2^n；最大n^2
2.空间复杂度
评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。即最大一次使用的空间的大小。
内存分段
4G----高地址----
---内核空间
---
3G----应用层（用户空间）----
---主程序传参环境(argv[])
---
---栈区（函数局部变量）
---
---垃圾空间
---
---堆区（malloc申请）
---
---静态区
数据区:
.bss：未初始化的数据
.data：初始化的数据（全局变量，static）
.rodata：只读数据段：字符串常量
---只读区
text代码段
.init0----低地址----NULL、（void*）0（）不可读不可写，只用来比较和赋初始值
堆区：M
malloc申请，free释放
不释放容易导致内存泄漏！
函数传参：
全局变量：
以全局变量为耻，以局部变量为荣。
不好维护，空间不影响大量申请。
局部变量：
无static修饰的，存在栈区，函数退出，空间释放。
主函数的局部变量：
不能大量申请，容易导致栈溢出。
预览时标签不可点收录于话题#个上一篇下一篇