[计算机软件及应用]第06章数组ppt课件

1、void sort(int s ,int n) int i,j,temp; for(i=0;in-1;i+) for(j=0;jsj+1) temp=sj; sj=sj+1; sj+1=temp; 例例4 shell排序快速排序排序快速排序l思想：思想：l将将n个数的队列分成两段。个数的队列分成两段。l把后一段的每个元素分别与前一段间隔把后一段的每个元素分别与前一段间隔n/2处的元素处的元素进展比较，假设后者大于前者，那么交换。进展比较，假设后者大于前者，那么交换。l当后一段的一切元素都处置完后，那么将比较间隔减当后一段的一切元素都处置完后，那么将比较间隔减小一半，然后从间隔第一个元素为当前间

2、隔的那个元小一半，然后从间隔第一个元素为当前间隔的那个元素开场直到队列最后一个元素反复上述的比较、交换素开场直到队列最后一个元素反复上述的比较、交换过程；过程；l在每一轮比较、交换过程中，一旦发生交换，被交换在每一轮比较、交换过程中，一旦发生交换，被交换到前面的那个值还要继续与前面间隔为当前比较间隔到前面的那个值还要继续与前面间隔为当前比较间隔的那些元素进展比较和交换，不断进展到比较中位于的那些元素进展比较和交换，不断进展到比较中位于前面的那个元素间隔队列的第一个元素小于当前比较前面的那个元素间隔队列的第一个元素小于当前比较间隔为止。间隔为止。l当间隔减小到当间隔减小到0时算法终了。时算法终了

3、。l 72 73 71 23 94 16 5 68(1) gap=4 (2) gap=2 (3) gap=1 7316 571 5727194717268732371687268717394.#define TRUE 1#define FALSE 0int linesearch(int list,int size, int key) int index, found, i; index=-1; found=FALSE; i=0; while(isize&!found) if(listi=key) found=TRUE; index=i; i+; return index;/*折半法在元

4、素按升序陈列得数组折半法在元素按升序陈列得数组v中查找值为中查找值为x得元素得元素*/int binsearch(int x, int v, int n) int top,bottom=n-1,mid; while(top=bottom) mid=(top+bottom)/2; if(xvmid) top=mid+1; else return mid; /找到找到 return -1; /未找到未找到成果的插入和删除成果的插入和删除例例6假设成果曾经输入，并按照从大到小的顺序陈列好。假设成果曾经输入，并按照从大到小的顺序陈列好。如今发现有某个成果被反复输入，需求把该成果删除，如今发现有某个成果

5、被反复输入，需求把该成果删除，使剩下的一切成果依然有序。使剩下的一切成果依然有序。步骤：步骤：查找待删除数据的位置。查找待删除数据的位置。挪动部分元素。挪动部分元素。从被删除位置的后一个元素开场到最后一个元素都向前从被删除位置的后一个元素开场到最后一个元素都向前挪动一个位置。挪动一个位置。程序：程序：l问题：问题：l元素能否可以从最后一个元素开场向前挪动，最后再元素能否可以从最后一个元素开场向前挪动，最后再挪动删除位置后的那个元素？挪动删除位置后的那个元素？l例例7假设成果曾经输入，并按照从大到小的顺序陈列假设成果曾经输入，并按照从大到小的顺序陈列好。如今发现有某个成果被脱漏，需求插入，并使插

6、好。如今发现有某个成果被脱漏，需求插入，并使插入后的一切成果依然有序。入后的一切成果依然有序。l步骤：步骤：l查找待插入数据的位置。查找待插入数据的位置。l挪动部分元素，先挪动最后一个元素，最后挪动待插挪动部分元素，先挪动最后一个元素，最后挪动待插入位置元素。入位置元素。l留意：留意：l数组元素的个数要足够。数组元素的个数要足够。l程序程序行数列数01452301234567.20212223c000c001c002c003c010c011c012c013c020c021c022c023c100c101c102c103c110c111c112c113c120c121c122c123字符串终了标

7、志字符串终了标志 字符数组的初始化a; a; 格式：格式：strlen(strlen(字符串地址字符串地址) /) /应包含的应包含的.h.h文件为文件为string.h string.h 功能：计算字符串长度功能：计算字符串长度返值：前往字符串实践长度，不包括返值：前往字符串实践长度，不包括00在内在内 #include #include #define CITYNUM 10 void main ( ) int i, j, k, num; char cityCITYNUM20; char str80; num = 0; /实践输入的城市数初始化为0 /输入城市名字符串长度不能超越19 for

8、 (i = 0; i 19) /城市名字符串超越19时，重输 i-; continue; strcpy (cityi, str); /将输入的城市名保管到字符串数组中 num+; /实践输入的城市数增1 for (i = 0; i num - 1; i+) /选择排序升序 k = i; /k为当前城市名最小的字符串数组的下标，初始假设为I /查找比cityk小的字符串的下标放入k中 for (j = i+1; j 0) k = j; if (k != i) /将最小城市名的字符串cityk与cityi交换 strcpy (str, cityi); strcpy (cityi, cityk);

9、strcpy (cityk, str); for (i = 0; i num; i+) /显示排序后的结果 printf (%s , cityi); printf (n);例： 写几个函数 1输入10个职工的姓名和职工号； 2按职工号由小到大的顺序排序，姓名顺序也随之调整。#include #include #define M 10#define N 10void input(char name N,int code,int n);void sort(char name N,int code,int n); void main(void) int i ; char nameMN; int co

10、deM;input(name, code,M); for(i=0;in;i+) printf(%d: %sn,namei,codei); sort(name, code,M); for(i=0;iM;i+) printf(%d: %sn,codei,namei);void input(char nameN,int code,int n) int i; for(i=0;in;i+) printf(name:); scanf(%s,namei); printf(code:); scanf(%d,&codei); void sort(char nameN,int code,int n) in

11、t i,j,temp; char strM; for(i=0;in-1;i+) for(j=0;jcodej+1) temp=codej; codej=codej+1; codej+1=temp; strcpy(str,namej); strcpy(namej,namej+1); strcpy(namej+1,str); #include #define MAX 15 void main ( ) int m, mm, i, j, k, ni, nj; int magicMAXMAX = 0; printf (Enter the number you wanted: ); scanf (%d,

12、&m); if (m = 0) | (m % 2 = 0) /小于0或为偶数前往 printf (Error in input data.n); return; mm = m * m; i = 0; /第一个值的位置 j = m / 2; #include #include void main ( ) long k, min, max, count10 = 0; char str9; int i; /输入最小、最大数 printf (input the first number: ); scanf (%ld, &min); printf (input the last numb

13、er: ); scanf (%ld, &max); if (min max) /最小数比最大数大，退出 printf (ninput error!); return; /统计各数字出现的次数 for (k = min; k = 0 & stri != ; i-) countstri-0+; for (i = 0; i 10; i+) /显示结果 printf (%d-(%ld) , i, counti); if (i = 4) printf (n); printf (n); 736.4 运用程序举例模拟逆波兰台式计算器。综合运用：函数与程序构造、数组涉及：函数的定义、阐明、调用

14、；外部变量的存储类型和作用域；外部数组、静态数组；数组名作函数参数；由多个函数、多个源文件组成C程序。74例6.16模拟台式计算器。允许的运算符有+、-、*、/，输入算式采用逆波兰表示法，浮点数用小数方式，输入换行后输出运算结果。1逆波兰表示法及其算式的实现方法逆波兰是算式的后缀表示，即对每一个运算符而言运算对象在前，运算符在后。如(1+2)*(4/5) 用逆波兰表示法是 1 2+4 5 /*75算式实现方法：相邻的两个运算对象之间必需用空格分开。用数组存放算式中的运算对象和中间结果，称为值栈。当遇运算对象时把运算对象都进栈push。当遇运算符时栈顶的两个运算对象退栈pop，对它们执行运转符规

15、定的操作，然后把运算结果进栈。当遇n时取出栈顶元素输出。762算式实现过程中所用到的操作算式实现过程中所用到的操作对栈的操作：实现一个算式的过程中要多次进展进栈、退栈操作，所以将进栈和退栈分别定义成函数push和pop。77读取一个运算符或运算对象的操作：getop函数用于搜集一个运算对象或运算符。它调用getch函数从缓冲区读一个字符。它调用ungetch退回一个字符到缓冲区。getch 经过调用getchar从规范输入设备接纳一个字符。用ungetch退回一个字符是由于getop函数在搜集运算对象和运算符时多读了一个不属于它们的字符，这个字符应该由下一次getop搜集。78将小数方式的浮点数字符串转换在双精度浮点值的操作：函数atof。留意： getch ，ungetch和atof都是规范函数，所需的头文件为conio.h。793 3程序模块的划分和外部变量的运用程序模块的划分和外部变量的运用包含7个函数，分为三个源文件和一个头文件。deskc.c文件：包含主函数。stack.c文件：包含值栈的操作函数push和pop。getop.c文件：包含获得一个运算符或运算对象的有关函数getop、getch、ungetch、atof。deskc.h头文件：包含符号常量NUMBER的定义，用于表示由getop函数