vlambda博客
学习文章列表

Linux_C开发_第八天_数据结构和算法简介


本文主要内容:数据结构类型,算法,时间复杂度,空间复杂度,内存分段。


程序 = 数据结构 + 算法


 数据结构类型

1. 逻辑类型

(1)线性结构(1:1):

    顺序表

    链表

    栈(FILO)

    队列(FIFO)

(2)非线性结构

    层次结构(1:N) ---树状结构

    网状结构(N:N)---图


2. 存储类型

存储设备内部数据之间的关系

(1)顺序存储

        如数组,堆区(malloc)结构体内部字符串

        方便查找不方便增删

(2)链式存储

        方便增删不方便查找。

(3)索引存储

        如字典,顺序+链式。

(4)散列存储

        哈希(hash)算法.


3. 运算

    增,删,改,查,排列



算法

1. 时间复杂度

评估执行程序所需的时间。可以估算出程序对处理器的使用程度。

    规则

        多项式:保留最高次幂项,砍去系数。

        常数:1。

int a = 1a = a+1;//执行次数是2次.//这个算法的时间复杂度为O(1).
for(int i=0;i<n;i++) { //时间复杂度为O(1)的算法  ...}//上面算法循环体中的代码执行了n次,因此时间复杂度为O(n).//执行次数是线性的.


for(int number=1; number<n; number*=2) {  //时间复杂度为O(1)的算法  ...}//随着number每次乘以2后,都会越来越接近n,//当number不小于n时就会退出循环。假设循环的次数为X,//则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。//执行次数是对数的.
for(int i=0;i<n;i++){ for(int j=0;j<n;i++){ //复杂度为O(1)的算法 ... }}//内层循环的时间复杂度已经得知是O(n),现在经过外层循环n次,//那么这段算法的时间复杂度则为O(n²)。//执行次数是一个多项式.  for(int i=0; i<n; i++){ for(int j=0; j<i; j++){ //复杂度为O(1)的算法 }} //内循环中int j=0,j<i。//当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//=n²/2+n/2//只保留最高阶,因此保留 n²/2 再砍去系数//那么这段算法的时间复杂度则为O(n²)。


    常见: 

        冒泡:n^2

        快排:平均 nlog2^n;最大 n^2


2. 空间复杂度

    评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。即最大一次使用的空间的大小。





内存分段

---    内核空间

---

3G----应用层(用户空间)----

---    主程序传参&环境(argv[])

---

---    栈区(函数局部变量)

---

---    垃圾空间

---

---    堆区(malloc申请)

---

---    静态区

            数据区:

                .bss :未初始化的数据

                .data:初始化的数据(全局变量,static)

                .rodata:只读数据段:字符串常量

---    只读区

                text 代码段



堆区:300M

malloc申请,free释放

不释放容易导致内存泄漏!


函数传参

全局变量

    以全局变量为耻,以局部变量为荣。

    不好维护,空间不影响大量申请。

局部变量

    无static修饰的,存在栈区,函数退出,空间释放。

主函数的局部变量

    不能大量申请,容易导致栈溢出。