拓冰网站定制 
耕耘 :C、C、嵌入式技术领域我的个人主页❄️个人专栏《C语言专栏》 《嵌入式专栏》 《数据结构专栏》✨**不要等待机会而要创造机会**✨博主简介:✨✨一位热爱生活的阳光大男孩.✨✨前言本文系统讲解C语言文件操作核心知识涵盖文件概念、流与文件指针机制重点解析fopen、fclose及错误处理结合fseek、ftell实现随机读写并深入剖析缓冲区原理与fflush刷新机制强调打开后判空、关闭置空等最佳实践为高效、安全的文件操作提供完整技术框架。文章目录前言1.数据结构前⾔1.1 数据结构1.2 算法2. 算法效率2.1 复杂度的概念3. 时间复杂度3.1 ⼤O的渐进表⽰法3.2 时间复杂度计算⽰例3.2.1 ⽰例13.2.2 ⽰例23.2.3 ⽰例33.2.4 ⽰例43.2.5 ⽰例53.2.6 ⽰例63.2.7 ⽰例74. 空间复杂度4.1 空间复杂度计算⽰例4.1.1 ⽰例14.1.2 ⽰例25. 常⻅复杂度对⽐6. 复杂度算法题6.1 旋转数组结语1.数据结构前⾔1.1 数据结构数据结构是计算机存储、组织数据的⽅式指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤所以我们要学各式各样的数据结构如线性表、树、图、哈希等1.2 算法算法就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果。2. 算法效率思路轮转数组循环K次将数组所有元素向后移动⼀位1、用循环的嵌套voidrotate(int*nums,intnumsSize,intk){while(k--){//保存数组最后一个数据intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}intmain(){intarr[7]{1,2,3,4,5,6,7};for(inti0;i7;i)//轮转前{printf(%d ,arr[i]);}printf(\n);rotate(arr,7,3);//轮转3次for(inti0;i7;i)//轮转后{printf(%d ,arr[i]);}return0;}2.1 复杂度的概念算法在编写成可执⾏程序后运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。**时间复杂度主要衡量⼀个算法的运⾏快慢⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。**在计算机发展的早期计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。3. 时间复杂度定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率。这个T(N)函数式计算了程序的执⾏次数。程序执行时间 二进制指令运行时间 * 执行次数执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率⼀定优于算法b。注意时间复杂度描述的是一个程序运动的趋势而不是他整体运行的时间。案例// 请计算⼀下Func1中count语句总共执⾏了多少次voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}总执行了T (N) N2 2 ∗ N 10通过对N取值分析对结果影响最⼤的⼀项是 N2实际中我们计算时间复杂度时计算的也不是程序的精确的执⾏次数上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数复杂度的表⽰通常使⽤⼤O的渐进表⽰法。3.1 ⼤O的渐进表⽰法⼤O符号Big O notation是⽤于描述函数渐进⾏为的数学符号1.时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。2.如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。3.T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。3.2 时间复杂度计算⽰例3.2.1 ⽰例1// 计算Func2的时间复杂度voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d\n,count);}**Func2执⾏的基本操作次数T (N) 2N 10根据推导规则第3条得出Func2的时间复杂度为 O(N) **3.2.2 ⽰例2// 计算Func3的时间复杂度voidFunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}printf(%d\n,count);}Func3执⾏的基本操作次数T (N) M N (因为MN都不知道次数所以他们可能相等则可能TN2N或2M)因此Func2的时间复杂度为 O(N) 或 O(M)3.2.3 ⽰例3// 计算Func4的时间复杂度voidFunc4(intN){intcount0;for(intk0;k100;k){count;}printf(%d\n,count);}T (N) 100根据推导规则第1条得出Func2的时间复杂度为 O(1)3.2.4 ⽰例4// 计算strchr的时间复杂度constchar*strchr(constchar*str,intcharacter){constchar*p_begins;while(*p_begin!character){if(*p_begin\0)returnNULL;p_begin;}returnp_begin;}strchr执⾏的基本操作次数1若要查找的字符在字符串第⼀个位置则T (N) 12若要查找的字符在字符串最后的⼀个位置则T (N) N3若要查找的字符在字符串中间位置则T (N) N/2因此strchr的时间复杂度分为最好情况 O(1)最坏情况 O(N)平均情况 O(N)总结通过上⾯我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。最坏情况任意输⼊规模的最⼤运⾏次数(上界)平均情况任意输⼊规模的期望运⾏次数最好情况任意输⼊规模的最⼩运⾏次数(下界)⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界也就是最坏运⾏情况。3.2.5 ⽰例5// 计算BubbleSort的时间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}1若数组有序则T (N) N2若数组有序且为降序则T (N) 2N ∗ (N 1)3若要查找的字符在字符串中间位置则因此BubbleSort的时间复杂度取最差情况为 O(N2 )3.2.6 ⽰例6voidfunc5(intn){intcnt1;while(cntn){cnt*2;}}当n2时执⾏次数为1当n4时执⾏次数为2当n16时执⾏次数为4假设执⾏次数为 x 则 2x n因此执⾏次数 x log n因此func5的时间复杂度取最差情况为O(log2 n)注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰当n接近⽆穷⼤时底数的⼤⼩对结果影响不⼤。因此⼀般情况下不管底数是多少都可以省略不写即可以表⽰为 log n不同书籍的表⽰⽅式不同以上写法差别不⼤我们建议使⽤ log n3.2.7 ⽰例7// 计算阶乘递归Fac的时间复杂度longlongFac(size_tN){if(0N)return1;returnFac(N-1)*N;}调⽤⼀次Fac函数的时间复杂度为 O(1)⽽在Fac函数中存在n次递归调⽤Fac函数因此阶乘递归的时间复杂度为 O(n)4. 空间复杂度空间复杂度也是⼀个数学表达式是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间因为常规情况每个对象⼤⼩差异不会很⼤所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使⽤⼤O渐进表⽰法。注意函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定4.1 空间复杂度计算⽰例4.1.1 ⽰例1// 计算BubbleSort的空间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}函数栈帧在编译期间已经确定好了只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有exchange等有限个局部变量使⽤了常数个额外空间因此空间复杂度为 O(1)4.1.2 ⽰例2// 计算阶乘递归Fac的空间复杂度longlongFac(size_tN){if(N0)return1;returnFac(N-1)*N;}Fac递归调⽤了N次额外开辟了N个函数栈帧每个栈帧使⽤了常数个空间因此空间复杂度为 O(N)5. 常⻅复杂度对⽐6. 复杂度算法题6.1 旋转数组思路1时间复杂度 O(n2 )循环K次将数组所有元素向后移动⼀位voidrotate(int*nums,intnumsSize,intk){while(k--){intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}思路2空间复杂度 O(n)申请新数组空间先将后k个数据放到新数组中再将剩下的数据挪到新数组中voidrotate(int*nums,intnumsSize,intk){intnewArr[numsSize];for(inti0;inumsSize;i){newArr[(ik)%numsSize]nums[i];}for(inti0;inumsSize;i){nums[i]newArr[i];}}思路3空间复杂度 O(1)• 前n-k个逆置4 3 2 15 6 7• 后k个逆置 4 3 2 17 6 5• 整体逆置 5 6 7 1 2 3 4voidreverse(int*nums,intbegin,intend){while(beginend){inttmpnums[begin];nums[begin]nums[end];nums[end]tmp;begin;end--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}结语愿你收获满满点赞、收藏、转发三连不断好运常伴完. 数据结构——拿捏复杂度
耕耘 :C、C、嵌入式技术领域我的个人主页❄️个人专栏《C语言专栏》 《嵌入式专栏》 《数据结构专栏》✨**不要等待机会而要创造机会**✨博主简介:✨✨一位热爱生活的阳光大男孩.✨✨前言本文系统讲解C语言文件操作核心知识涵盖文件概念、流与文件指针机制重点解析fopen、fclose及错误处理结合fseek、ftell实现随机读写并深入剖析缓冲区原理与fflush刷新机制强调打开后判空、关闭置空等最佳实践为高效、安全的文件操作提供完整技术框架。文章目录前言1.数据结构前⾔1.1 数据结构1.2 算法2. 算法效率2.1 复杂度的概念3. 时间复杂度3.1 ⼤O的渐进表⽰法3.2 时间复杂度计算⽰例3.2.1 ⽰例13.2.2 ⽰例23.2.3 ⽰例33.2.4 ⽰例43.2.5 ⽰例53.2.6 ⽰例63.2.7 ⽰例74. 空间复杂度4.1 空间复杂度计算⽰例4.1.1 ⽰例14.1.2 ⽰例25. 常⻅复杂度对⽐6. 复杂度算法题6.1 旋转数组结语1.数据结构前⾔1.1 数据结构数据结构是计算机存储、组织数据的⽅式指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤所以我们要学各式各样的数据结构如线性表、树、图、哈希等1.2 算法算法就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果。2. 算法效率思路轮转数组循环K次将数组所有元素向后移动⼀位1、用循环的嵌套voidrotate(int*nums,intnumsSize,intk){while(k--){//保存数组最后一个数据intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}intmain(){intarr[7]{1,2,3,4,5,6,7};for(inti0;i7;i)//轮转前{printf(%d ,arr[i]);}printf(\n);rotate(arr,7,3);//轮转3次for(inti0;i7;i)//轮转后{printf(%d ,arr[i]);}return0;}2.1 复杂度的概念算法在编写成可执⾏程序后运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。**时间复杂度主要衡量⼀个算法的运⾏快慢⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。**在计算机发展的早期计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。3. 时间复杂度定义在计算机科学中算法的时间复杂度是⼀个函数式T(N)它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率。这个T(N)函数式计算了程序的执⾏次数。程序执行时间 二进制指令运行时间 * 执行次数执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率⼀定优于算法b。注意时间复杂度描述的是一个程序运动的趋势而不是他整体运行的时间。案例// 请计算⼀下Func1中count语句总共执⾏了多少次voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}总执行了T (N) N2 2 ∗ N 10通过对N取值分析对结果影响最⼤的⼀项是 N2实际中我们计算时间复杂度时计算的也不是程序的精确的执⾏次数上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数复杂度的表⽰通常使⽤⼤O的渐进表⽰法。3.1 ⼤O的渐进表⽰法⼤O符号Big O notation是⽤于描述函数渐进⾏为的数学符号1.时间复杂度函数式T(N)中只保留最⾼阶项去掉那些低阶项因为当N不断变⼤时低阶项对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。2.如果最⾼阶项存在且不是1则去除这个项⽬的常数系数因为当N不断变⼤这个系数对结果影响越来越⼩当N⽆穷⼤时就可以忽略不计了。3.T(N)中如果没有N相关的项⽬只有常数项⽤常数1取代所有加法常数。3.2 时间复杂度计算⽰例3.2.1 ⽰例1// 计算Func2的时间复杂度voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d\n,count);}**Func2执⾏的基本操作次数T (N) 2N 10根据推导规则第3条得出Func2的时间复杂度为 O(N) **3.2.2 ⽰例2// 计算Func3的时间复杂度voidFunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}printf(%d\n,count);}Func3执⾏的基本操作次数T (N) M N (因为MN都不知道次数所以他们可能相等则可能TN2N或2M)因此Func2的时间复杂度为 O(N) 或 O(M)3.2.3 ⽰例3// 计算Func4的时间复杂度voidFunc4(intN){intcount0;for(intk0;k100;k){count;}printf(%d\n,count);}T (N) 100根据推导规则第1条得出Func2的时间复杂度为 O(1)3.2.4 ⽰例4// 计算strchr的时间复杂度constchar*strchr(constchar*str,intcharacter){constchar*p_begins;while(*p_begin!character){if(*p_begin\0)returnNULL;p_begin;}returnp_begin;}strchr执⾏的基本操作次数1若要查找的字符在字符串第⼀个位置则T (N) 12若要查找的字符在字符串最后的⼀个位置则T (N) N3若要查找的字符在字符串中间位置则T (N) N/2因此strchr的时间复杂度分为最好情况 O(1)最坏情况 O(N)平均情况 O(N)总结通过上⾯我们会发现有些算法的时间复杂度存在最好、平均和最坏情况。最坏情况任意输⼊规模的最⼤运⾏次数(上界)平均情况任意输⼊规模的期望运⾏次数最好情况任意输⼊规模的最⼩运⾏次数(下界)⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界也就是最坏运⾏情况。3.2.5 ⽰例5// 计算BubbleSort的时间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}1若数组有序则T (N) N2若数组有序且为降序则T (N) 2N ∗ (N 1)3若要查找的字符在字符串中间位置则因此BubbleSort的时间复杂度取最差情况为 O(N2 )3.2.6 ⽰例6voidfunc5(intn){intcnt1;while(cntn){cnt*2;}}当n2时执⾏次数为1当n4时执⾏次数为2当n16时执⾏次数为4假设执⾏次数为 x 则 2x n因此执⾏次数 x log n因此func5的时间复杂度取最差情况为O(log2 n)注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰当n接近⽆穷⼤时底数的⼤⼩对结果影响不⼤。因此⼀般情况下不管底数是多少都可以省略不写即可以表⽰为 log n不同书籍的表⽰⽅式不同以上写法差别不⼤我们建议使⽤ log n3.2.7 ⽰例7// 计算阶乘递归Fac的时间复杂度longlongFac(size_tN){if(0N)return1;returnFac(N-1)*N;}调⽤⼀次Fac函数的时间复杂度为 O(1)⽽在Fac函数中存在n次递归调⽤Fac函数因此阶乘递归的时间复杂度为 O(n)4. 空间复杂度空间复杂度也是⼀个数学表达式是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间因为常规情况每个对象⼤⼩差异不会很⼤所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使⽤⼤O渐进表⽰法。注意函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定4.1 空间复杂度计算⽰例4.1.1 ⽰例1// 计算BubbleSort的空间复杂度voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}函数栈帧在编译期间已经确定好了只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有exchange等有限个局部变量使⽤了常数个额外空间因此空间复杂度为 O(1)4.1.2 ⽰例2// 计算阶乘递归Fac的空间复杂度longlongFac(size_tN){if(N0)return1;returnFac(N-1)*N;}Fac递归调⽤了N次额外开辟了N个函数栈帧每个栈帧使⽤了常数个空间因此空间复杂度为 O(N)5. 常⻅复杂度对⽐6. 复杂度算法题6.1 旋转数组思路1时间复杂度 O(n2 )循环K次将数组所有元素向后移动⼀位voidrotate(int*nums,intnumsSize,intk){while(k--){intendnums[numsSize-1];for(intinumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}}思路2空间复杂度 O(n)申请新数组空间先将后k个数据放到新数组中再将剩下的数据挪到新数组中voidrotate(int*nums,intnumsSize,intk){intnewArr[numsSize];for(inti0;inumsSize;i){newArr[(ik)%numsSize]nums[i];}for(inti0;inumsSize;i){nums[i]newArr[i];}}思路3空间复杂度 O(1)• 前n-k个逆置4 3 2 15 6 7• 后k个逆置 4 3 2 17 6 5• 整体逆置 5 6 7 1 2 3 4voidreverse(int*nums,intbegin,intend){while(beginend){inttmpnums[begin];nums[begin]nums[end];nums[end]tmp;begin;end--;}}voidrotate(int*nums,intnumsSize,intk){kk%numsSize;reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);}结语愿你收获满满点赞、收藏、转发三连不断好运常伴完.