《算法與程序設(shè)計(jì)》課件

算法與程序設(shè)計(jì)課程概述1課程目標(biāo)掌握算法設(shè)計(jì)與程序?qū)崿F(xiàn)2學(xué)習(xí)內(nèi)容算法基礎(chǔ)、程序結(jié)構(gòu)、排序與查找考核方式第一章：算法基礎(chǔ)1什么是算法解決問題的明確步驟2算法的特性有限性、確定性、可行性等3算法的表示方法自然語言、流程圖、偽代碼算法的定義解決問題的步驟精確定義的操作序列有限性有限時間內(nèi)完成確定性每步操作明確無歧義可行性操作可實(shí)際執(zhí)行算法的五大特性12345輸入有零個或多個輸入輸出至少有一個輸出有窮性在有限步驟后結(jié)束確定性每步操作無二義性可行性每步操作可執(zhí)行算法的表示方法自然語言用日常語言描述流程圖圖形化表示算法偽代碼類編程語言表示流程圖符號流程圖是算法的直觀表示方法偽代碼示例算法：計(jì)算1到n的和輸入：正整數(shù)n輸出：sum1.設(shè)sum=02.循環(huán)i從1到nsum=sum+i3.返回sum偽代碼不限于特定編程語言第二章：基本程序結(jié)構(gòu)1循環(huán)結(jié)構(gòu)重復(fù)執(zhí)行2選擇結(jié)構(gòu)條件判斷3順序結(jié)構(gòu)基本執(zhí)行單元順序結(jié)構(gòu)定義按順序執(zhí)行的語句特點(diǎn)無條件分支或跳轉(zhuǎn)示例賦值、輸入輸出語句選擇結(jié)構(gòu)if-else語句二路分支結(jié)構(gòu)switch-case語句多路分支結(jié)構(gòu)if-else語句示例if(成績>=60){輸出("通過");}else{輸出("不通過");}根據(jù)條件判斷執(zhí)行不同分支switch-case語句示例switch(等級){case'A':輸出("優(yōu)秀");break;case'B':輸出("良好");break;case'C':輸出("及格");break;default:輸出("不及格");}多條件分支的簡潔表示循環(huán)結(jié)構(gòu)while循環(huán)先判斷后執(zhí)行do-while循環(huán)先執(zhí)行后判斷for循環(huán)有明確循環(huán)次數(shù)while循環(huán)示例inti=1,sum=0;while(i<=100){sum+=i;i++;}計(jì)算1到100的和do-while循環(huán)示例intnum;do{輸入(num);處理(num);}while(num!=0);至少執(zhí)行一次循環(huán)體for循環(huán)示例intsum=0;for(inti=1;i<=100;i++){sum+=i;}適合已知循環(huán)次數(shù)的場景第三章：函數(shù)函數(shù)的概念模塊化編程單元1函數(shù)的定義與調(diào)用創(chuàng)建和使用函數(shù)2參數(shù)傳遞值傳遞與引用傳遞3函數(shù)的概念模塊化程序設(shè)計(jì)將大問題分解為小問題代碼重用避免重復(fù)編寫相同代碼抽象化隱藏具體實(shí)現(xiàn)細(xì)節(jié)可維護(hù)性便于修改和維護(hù)函數(shù)的定義與調(diào)用語法返回類型函數(shù)名(參數(shù)列表)返回值函數(shù)執(zhí)行結(jié)果函數(shù)原型提前聲明函數(shù)簽名參數(shù)傳遞值傳遞復(fù)制實(shí)參的值給形參引用傳遞傳遞實(shí)參的地址或引用函數(shù)示例intmax(inta,intb){return(a>b)?a:b;}voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}max函數(shù)使用值傳遞，swap函數(shù)使用引用傳遞遞歸函數(shù)定義函數(shù)直接或間接調(diào)用自身遞歸與迭代的比較優(yōu)雅但效率可能較低遞歸函數(shù)示例階乘計(jì)算n!=n*(n-1)!斐波那契數(shù)列F(n)=F(n-1)+F(n-2)第四章：數(shù)組1字符數(shù)組字符串處理2二維數(shù)組表格數(shù)據(jù)3一維數(shù)組線性數(shù)據(jù)集合一維數(shù)組定義相同類型元素的集合初始化聲明時賦初值訪問元素通過索引訪問一維數(shù)組示例//定義并初始化數(shù)組intscores[5]={85,92,78,90,88};//訪問元素inthighest=scores[1];//92//修改元素scores[2]=80;數(shù)組索引從0開始二維數(shù)組定義行列結(jié)構(gòu)的數(shù)據(jù)初始化按行或整體初始化訪問元素使用兩個索引二維數(shù)組示例//定義3x3矩陣intmatrix[3][3]={{1,2,3},{4,5,6},{7,8,9}};//訪問元素intcenter=matrix[1][1];//5適合表示表格數(shù)據(jù)字符數(shù)組1定義存儲字符串的特殊數(shù)組2字符串結(jié)束符'\0'標(biāo)記字符串結(jié)束3字符串處理函數(shù)strcpy、strlen、strcat等字符數(shù)組示例//定義字符數(shù)組chargreeting[6]={'H','e','l','l','o','\0'};charmessage[]="Hello";//自動添加'\0'//字符串函數(shù)intlength=strlen(message);//5字符串長度不包括結(jié)束符'\0'第五章：排序算法冒泡排序相鄰元素比較交換選擇排序選擇最小元素交換插入排序構(gòu)建有序序列插入冒泡排序算法原理相鄰元素比較，大元素上浮時間復(fù)雜度O(n2)，穩(wěn)定排序算法冒泡排序示例voidbubbleSort(intarr[],intn){for(inti=0;i<n-1;i++)for(intj=0;j<n-i-1;j++)if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);}大元素像泡泡一樣上浮到序列頂端選擇排序算法原理找最小元素放到已排序部分末尾時間復(fù)雜度O(n2)，不穩(wěn)定排序算法選擇排序示例voidselectionSort(intarr[],intn){for(inti=0;i<n-1;i++){intmin_idx=i;for(intj=i+1;j<n;j++)if(arr[j]<arr[min_idx])min_idx=j;swap(arr[i],arr[min_idx]);}}每次從未排序部分選最小元素插入排序算法原理將元素插入已排序部分適當(dāng)位置時間復(fù)雜度O(n2)，穩(wěn)定排序算法插入排序示例voidinsertionSort(intarr[],intn){for(inti=1;i<n;i++){intkey=arr[i];intj=i-1;while(j>=0&&arr[j]>key){arr[j+1]=arr[j];j--;}arr[j+1]=key;}}類似于玩撲克牌時整理手牌第六章：查找算法順序查找從頭到尾逐個比較二分查找對有序序列減半查找順序查找算法原理從第一個元素開始逐個比較時間復(fù)雜度O(n)，適用于無序序列順序查找示例intsequentialSearch(intarr[],intn,intx){for(inti=0;i<n;i++)if(arr[i]==x)returni;return-1;//未找到}簡單但效率較低的查找方法二分查找1算法原理比較中間元素，縮小查找范圍2前提條件序列必須有序3時間復(fù)雜度O(logn)，效率高二分查找示例intbinarySearch(intarr[],intl,intr,intx){if(r>=l){intmid=l+(r-l)/2;if(arr[mid]==x)returnmid;if(arr[mid]>x)returnbinarySearch(arr,l,mid-1,x);returnbinarySearch(arr,mid+1,r,x);}return-1;//未找到}每次將查找范圍減半第七章：指針指針的概念存儲內(nèi)存地址的變量1指針與數(shù)組數(shù)組名作為指針2指針與函數(shù)指針作為參數(shù)和返回值3指針的概念地址變量在內(nèi)存中的位置指針變量存儲地址的變量引用與解引用&獲取地址，*訪問內(nèi)容指針與數(shù)組數(shù)組名與指針數(shù)組名是首元素地址指針數(shù)組元素為指針的數(shù)組指針與函數(shù)指針作為函數(shù)參數(shù)實(shí)現(xiàn)引用傳遞效果指針作為函數(shù)返回值返回動態(tài)分配的內(nèi)存函數(shù)指針指向函數(shù)的指針指針示例intx=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]的值指針操作直接訪問內(nèi)存第八章：結(jié)構(gòu)體結(jié)構(gòu)體的定義自定義復(fù)合數(shù)據(jù)類型結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體組成的數(shù)組結(jié)構(gòu)體指針指向結(jié)構(gòu)體的指針結(jié)構(gòu)體的定義語法struct關(guān)鍵字定義新類型成員訪問使用點(diǎn)運(yùn)算符(.)結(jié)構(gòu)體數(shù)組1定義元素為結(jié)構(gòu)體的數(shù)組2初始化整體或單個結(jié)構(gòu)體初始化3訪問元素?cái)?shù)組索引和成員運(yùn)算符結(jié)構(gòu)體指針定義指向結(jié)構(gòu)體的指針變量成員訪問使用箭頭運(yùn)算符(->)結(jié)構(gòu)體示例//定義結(jié)構(gòu)體structStudent{intid;charname[50];floatscore;};//使用結(jié)構(gòu)體structStudents1={1001,"張三",85.5};printf("學(xué)號:%d\n",s1.id);//結(jié)構(gòu)體指針structStudent*ptr=&s1;printf("姓名:%s\n",ptr->name);結(jié)構(gòu)體用于表示復(fù)雜數(shù)據(jù)第九章：文件操作文件的打開與關(guān)閉建立和斷開文件連接文件的讀寫操作數(shù)據(jù)的輸入和輸出文件的打開與關(guān)閉fopen()打開文件，返回文件指針fclose()關(guān)閉文件，釋放資源文件的讀寫操作fprintf()格式化寫入文本fscanf()格式化讀取文本fwrite()/fread()二進(jìn)制數(shù)據(jù)讀寫文件操作示例//寫入文件FILE*fp=fopen("data.txt","w");if(fp!=NULL){fprintf(fp,"學(xué)號:%d,姓名:%s\n",1001,"張三");fclose(fp);}//讀取文件fp=fopen("data.txt","r");if(fp!=NULL){charbuffer[100];while(fgets(bu