《算法与程序设计》课件

算法与程序设计课程概述1课程目标2学习内容掌握算法设计与程序实现算法基础、程序结构、排序与查找考核方式第一章算法基础什么是算法1解决问题的明确步骤算法的特性2有限性、确定性、可行性等算法的表示方法3自然语言、流程图、伪代码算法的定义解决问题的步骤精确定义的操作序列有限性有限时间内完成确定性每步操作明确无歧义可行性操作可实际执行算法的五大特性有穷性输出在有限步骤后结束确定性至少有一个输出每步操作无二义性输入可行性3有零个或多个输入每步操作可执行2415算法的表示方法流程图伪代码图形化表示算法类编程语言表示自然语言用日常语言描述流程图符号流程图是算法的直观表示方法伪代码示例算法计算1到n的和输入正整数n输出sum

1.设sum=

02.循环i从1到nsum=sum+i

3.返回sum伪代码不限于特定编程语言第二章基本程序结构循环结构1重复执行选择结构2条件判断顺序结构3基本执行单元顺序结构定义按顺序执行的语句特点无条件分支或跳转示例赋值、输入输出语句选择结构if-else语句switch-case语句二路分支结构多路分支结构语句示例if-elseif成绩=60{输出通过;}else{输出不通过;}根据条件判断执行不同分支语句示例switch-caseswitch等级{case A:输出优秀;break;case B:输出良好;break;case C:输出及格;break;default:输出不及格;}多条件分支的简洁表示循环结构while循环do-while循环for循环先判断后执行先执行后判断有明确循环次数循环示例whileint i=1,sum=0;while i=100{sum+=i;i++;}计算1到100的和循环示例do-whileint num;do{输入num;处理num;}while num!=0;至少执行一次循环体循环示例forint sum=0;for inti=1;i=100;i++{sum+=i;}适合已知循环次数的场景第三章函数函数的定义与调用2创建和使用函数函数的概念1模块化编程单元参数传递值传递与引用传递3函数的概念模块化程序设计将大问题分解为小问题代码重用避免重复编写相同代码抽象化隐藏具体实现细节可维护性便于修改和维护函数的定义与调用返回值函数原型语法函数执行结果提前声明函数签名返回类型函数名参数列表参数传递值传递引用传递复制实参的值给形参传递实参的地址或引用函数示例int maxinta,int b{return aba:b;}void swapinta,int b{int temp=a;a=b;b=temp;}max函数使用值传递，swap函数使用引用传递递归函数定义递归与迭代的比较函数直接或间接调用自身优雅但效率可能较低递归函数示例阶乘计算斐波那契数列n!=n*n-1!Fn=Fn-1+Fn-2第四章数组字符数组1字符串处理二维数组2表格数据一维数组3线性数据集合一维数组定义相同类型元素的集合初始化声明时赋初值访问元素通过索引访问一维数组示例//定义并初始化数组int scores

[5]={85,92,78,90,88};//访问元素int highest=scores

[1];//92//修改元素scores

[2]=80;数组索引从0开始二维数组定义初始化访问元素行列结构的数据按行或整体初始化使用两个索引二维数组示例//定义3x3矩阵int matrix

[3]

[3]={{1,2,3},{4,5,6},{7,8,9}};//访问元素int center=matrix

[1]

[1];//5适合表示表格数据字符数组1定义2字符串结束符存储字符串的特殊数组\0标记字符串结束3字符串处理函数strcpy、strlen、strcat等字符数组示例//定义字符数组char greeting

[6]={H,e,l,l,o,\0};char message[]=Hello;//自动添加\0//字符串函数int length=strlenmessage;//5字符串长度不包括结束符\0第五章排序算法冒泡排序相邻元素比较交换选择排序选择最小元素交换插入排序构建有序序列插入冒泡排序时间复杂度算法原理On²，稳定排序算法相邻元素比较，大元素上浮冒泡排序示例void bubbleSortint arr[],int n{for inti=0;in-1;i++for int j=0;jn-i-1;j++if arr[j]arr[j+1]swaparr[j],arr[j+1];}大元素像泡泡一样上浮到序列顶端选择排序算法原理找最小元素放到已排序部分末尾时间复杂度On²，不稳定排序算法选择排序示例void selectionSortintarr[],int n{for inti=0;in-1;i++{int min_idx=i;for intj=i+1;jn;j++if arr[j]arr[min_idx]min_idx=j;swaparr[i],arr[min_idx];}}每次从未排序部分选最小元素插入排序算法原理将元素插入已排序部分适当位置时间复杂度On²，稳定排序算法插入排序示例void insertionSortintarr[],int n{for inti=1;in;i++{int key=arr[i];intj=i-1;while j=0arr[j]key{arr[j+1]=arr[j];j--;}arr[j+1]=key;}类似于玩扑克牌时整理手牌}第六章查找算法顺序查找二分查找从头到尾逐个比较对有序序列减半查找顺序查找算法原理从第一个元素开始逐个比较时间复杂度On，适用于无序序列顺序查找示例int sequentialSearchintarr[],int n,int x{for inti=0;in;i++if arr[i]==xreturn i;return-1;//未找到}简单但效率较低的查找方法二分查找1算法原理2前提条件3时间复杂度比较中间元素，缩小查找范围序列必须有序Olog n，效率高二分查找示例int binarySearchintarr[],int l,int r,intx{if r=l{int mid=l+r-l/2;if arr[mid]==xreturn mid;if arr[mid]xreturn binarySearcharr,l,mid-1,x;return binarySearcharr,mid+1,r,x;}每次将查找范围减半return-1;//未找到}第七章指针指针与数组2数组名作为指针指针的概念1存储内存地址的变量指针与函数指针作为参数和返回值3指针的概念地址指针变量引用与解引用变量在内存中的位置存储地址的变量获取地址，*访问内容指针与数组数组名与指针数组名是首元素地址指针数组元素为指针的数组指针与函数指针作为函数参数指针作为函数返回值实现引用传递效果返回动态分配的内存函数指针指向函数的指针指针示例int x=10;int*p=x;//p指向x*p=20;//通过p修改x的值intarr

[5]={1,2,3,4,5};int*q=arr;//q指向arr

[0]*q+2=30;//修改arr

[2]的值指针操作直接访问内存第八章结构体结构体的定义自定义复合数据类型结构体数组结构体组成的数组结构体指针指向结构体的指针结构体的定义成员访问语法使用点运算符.struct关键字定义新类型结构体数组1定义2初始化元素为结构体的数组整体或单个结构体初始化3访问元素数组索引和成员运算符结构体指针成员访问使用箭头运算符-定义指向结构体的指针变量结构体示例//定义结构体struct Student{int id;char name

[50];float score;};//使用结构体struct Students1={1001,张三,

85.5};printf学号:%d\n,s

1.id;//结构体指针struct Student*ptr=s1;printf姓名:%s\n,ptr-name;结构体用于表示复杂数据第九章文件操作文件的打开与关闭文件的读写操作建立和断开文件连接数据的输入和输出文件的打开与关闭fopen打开文件，返回文件指针fclose关闭文件，释放资源文件的读写操作fprintf fscanffwrite/fread格式化写入文本格式化读取文本二进制数据读写文件操作示例//写入文件FILE*fp=fopendata.txt,w;if fp!=NULL{fprintffp,学号:%d,姓名:%s\n,1001,张三;fclosefp;}//读取文件fp=fopendata.txt,r;if fp!=NULL{文件操作实现数据持久化存储char buffer

[100];while fgetsbuffer,100,fp!=NULLprintf%s,buffer;fclosefp;}算法效率分析时间复杂度空间复杂度算法执行时间的增长率算法所需存储空间的增长率常见算法复杂度输入规模n O1Olog nOn On²不同复杂度算法随输入规模增长的执行时间对比课程总结1重点回顾2编程习惯算法思想、程序结构、数据操注重代码效率、可读性、可维作护性3学习建议多实践、多思考、培养问题解决能力。