数组的典型问题和其算法.ppt

江苏科技大学电子信息学院 江苏科技大学电子信息学院 第三章习题课 数组的典型问题及算法 * 江苏科技大学电子信息学院 * 一、数组元素的删除 二、数组元素的插入 三、查找元素 四、数组排序 五、字符串匹配 六、矩阵问题 * 江苏科技大学电子信息学院 * 一、 数组元素的删除 例题：删除从键盘输入的字符串中的空格字符（设从键盘输入的字符串保存在字符数组str中）。 算法一：对数组遍历，找到要删除的元素，其后的元素依次向前移动一位。程序段如下： int i=0,j;while(str[i]){ //遍历数组 if(str[i]==‘ ‘){ //查找满足条件的元素 j=i; //A行，定位开始移动位置 while(str[j]){ //依次前移一位 str[j]=str[j+1]; //B行 j++; } i--; //C行 } i++;} 程序解读：(1)能不能把A行改为： j=i+1; 把B行相应地改为： str[j-1]=str[j]; (2)C行的作用是什么? * 江苏科技大学电子信息学院 * 一、 数组元素的删除 算法二：对数组遍历，把非空格字符(条件) 依次复制数组中。程序段如下： int i=0,j=0;while(str[i]){ //遍历数组 if(str[i]!=‘ ‘) //条件 str[j++]=str[i]; //复制 i++;}str[j]=‘\0’; //A 程序解读：(1)能否去掉A行? (2)解法一中为什么不要加结束标记? (3)解法二可用指针完成，完整程序见下页。 * 江苏科技大学电子信息学院 * #includeiostream.h void main() { char str[80],*ptr1=str,*ptr2; cin.getline(ptr1,79); // cin.getline(str,79); ptr2=str; // ptr2=ptr1; while(*ptr1) { if(*ptr1!= ) *ptr2++=*ptr1; ptr1++; } *ptr2=\0; coutstrendl; } 一、 数组元素的删除 练习：《解析与训练》练习题P.65第19题。 * 江苏科技大学电子信息学院 * 二、 数组元素的插入 例题：把键盘输入的k插入到降序序列a[10]={8,6,4,2}中。 算法：(1)对数组中已有元素遍历，查找插入位置。 for(int i=0;in;i++)//n是已有元素个数，本题为4 if(ka[i])break; 上述查找语句可写为： for(int i=0;inka[i];i++);循环结束后，i就是插入位置。 (2)i之后的元素按从后到前的方向依次向后移动一位。 for(int j=n;ji;j--) a[j]=a[j-1]; //A行 (3)把k插入到a[i]的位置：a[i]= k; 算法分析： (1)能不能把A行改为： for(int j=i;jn;j++) a[j+1]=a[j]; (2)若序列为升序序列，应怎样插入? * 江苏科技大学电子信息学院 * 二、 数组元素的插入 #include iostream.h void main() { int a[10]={8,6,4,2},n=4,k;cink; for(int i=0;inka[i];i++); for(int j=n;ji;j--) a[j]=a[j-1];//A行 a[i]=k; n++; //B行 for(i=0;in;i++)couta[i]\t; coutendl; } 程序解读：(1)能不能把A行改为： for(int j=n-1;j=i;j--) a[j+1]=a[j]; (2) B行的作用是什么? 练习：《解析与训练》练习题P.64第17题。 * 江苏科技大学电子信息学院 * 三、 查找元素 查找的方法有多种，如顺序查找法、对半查找法、分块查找（索引查找）等。 在删除和插入元素中所使用的是顺序查找，即从序列的第一个元素开始，将给定的值与序列中各元素逐个进行比较，直到找到满足条件的元素或没有满足的元素。 而对顺序方式存放的有序表，则可使用对（折）半查找法——将要查找的关键字与顺序表中间位置上的元素进行比较，这个中间位置把顺序表分成了两个子表，若比较相等，则查找成功；否则，根据比较结果确定下一步应在哪个子表中进行查找，如此进行下去，直到查找到满足条件的数据元素，或者确定表中无此元素。 * 江