《数组的典型问题及其算法》由会员分享，可在线阅读，更多相关《数组的典型问题及其算法（17页珍藏版）》请在金锄头文库上搜索。
1、第三章习题课第三章习题课数组的典型问题及算法数组的典型问题及算法*江苏科技大学电子信息学院2一、数组元素的删除 二、数组元素的插入 三、查找元素 四、数组排序 五、字符串匹配 六、矩阵问题 *江苏科技大学电子信息学院3一、 数组元素的删除 v例题：删除从键盘输入的字符串中的空格字符（设从键盘 输入的字符串保存在字符数组str中）。v算法一：对数组遍历，找到要删除的元素，其后的元素依 次向前移动一位。程序段如下： int i=0,j; while(stri) /遍历数组if(stri= ) /查找满足条件的元素 j=i;/A行，定位开始移动位置 while(strj)/依次前移一位strj=st
2、rj+1; /B行j+; i-; /C行i+; 程序解读： (1)能不能把A行改为：j=i+1;把B行相应地改为：strj-1=strj; (2)C行的作用是什么?*江苏科技大学电子信息学院4一、 数组元素的删除 v算法二：对数组遍历，把非空格字符(条件) 依次复制数组 中。程序段如下： int i=0,j=0; while(stri) /遍历数组if(stri!= ) /条件 strj+=stri; /复制i+; strj=0; /A程序解读： (1)能否去掉A行? (2)解法一中为什么不要加结束标记? (3)解法二可用指针完成，完整程序见下页。*江苏科技大学电子信息学院5#include
3、void main() char str80,*ptr1=str,*ptr2; cin.getline(ptr1,79); / cin.getline(str,79); ptr2=str; / ptr2=ptr1; while(*ptr1) if(*ptr1!= ) *ptr2+=*ptr1; ptr1+; *ptr2=0; coutai)break; 上述查找语句可写为： for(int i=0;ii;j-) aj=aj-1; /A行 (3)把k插入到ai的位置：ai= k;算法分析： (1)能不能把A行改为： for(int j=i;j void main() int a10=8,6,4,
4、2,n=4,k; cink; for(int i=0;ii;j-) aj=aj-1;/A行 ai=k; n+;/B行 for(i=0;i=i;j-) aj+1=aj; (2) B行的作用是什么?练习：解析与训练 练习题P.64第17题 。*江苏科技大学电子信息学院8三、 查找元素v查找的方法有多种，如顺序查找法、对半查找法 、分块查找（索引查找）等。v在删除和插入元素中所使用的是顺序查找，即从 序列的第一个元素开始，将给定的值与序列中各 元素逐个进行比较，直到找到满足条件的元素或 没有满足的元素。 v而对顺序方式存放的有序表，则可使用对（折） 半查找法将要查找的关键字与顺序表中间位 置上的元素
5、进行比较，这个中间位置把顺序表分 成了两个子表，若比较相等，则查找成功；否则 ，根据比较结果确定下一步应在哪个子表中进行 查找，如此进行下去，直到查找到满足条件的数 据元素，或者确定表中无此元素。 *江苏科技大学电子信息学院9三、查找元素v例题：在序列a =2,4,6,8,10,12,14,16,18,20中查找键盘 输入的k 。v算法： (1)定义l(0)和h(9)表示查找范围，m表示中间位置，f(0)作 为是否找到的标记。 (2)m=(l+h)/2; (3)若am=k查找结束：if(am=k)f=1; break; (4)若kam) ，在m+1与h之间查找：else l=m+1; (6)查
6、找过程中，l与h不断接近，重复(2)(5)直到lh，即 l void main() int a10=2,4,6,8,10,12,14,16,18,20,k, l=0,h=9,m,f=0; cink; while(l=0) /A行k=0;for ( i=0; iai+1) k=1; s=ai; ai=ai+1; ai+1=s;j-; 四、 数组排序 交换排序练习：解析与训练练习题P.68第29题。程序解读，A行能否写成： while( k int i=0,j,k,number=0; while(stri) /遍历母串j=i;k=0; /Awhile(strj=sk) /字符串匹配if(sk+1=0) number+;break;/匹配成功j+,k+;i+; cout=i;j-)aN-i-1j=; for(j=N-i-2;ji;j-)aji=;*江苏科技大学电子信息学院17#include #define N 5 void main() int aNN,startnum=1; for(int n=N%2?N/2+1:N/2,i=0;i=i;j-)aN-i-1j=startnum+; for(j=N-i-2;ji;j-)aji=startnum+; for(i=0;iN;i+) for(int j=0;jN;j+)coutaijt; coutn; 六、 矩阵问题
