C语言数组、字符串.ppt

数组概念1.数组有多个数据组成2.元素具有相同基本类型3.内存单元连续,1定义说明：,(1)数组定义时，必须指定数组的大小（或长度），只能是常量表达式(2)数组定义后，系统将给其分配一定大小的内存单元，其所占内存单元的大小与数组元素的类型和数组的长度有关。,数组所占内存单元的字节数=数组大小sizeof（数组元素类型）,(3)数组中每个数组元素的类型均相同，占用内存中连续的存储单元，第一个数组元素的地址是整个数组所占内存块的低地址，也是首地址，最后一个数组元素的地址是整个数组所占内存块的高地址（末地址）。,例如：shortinta20;则数组a所占内存单元的大小为：20*sizeof(short)=20*2=40（字节）。,2引用说明：,(1)下标可以是整型常量、整型变量或整型表达式。C语言规定，下标的最小值是0，最大值则是数组大小减1。,(2)只能逐个引用数组元素，不能一次引用整个数组(3)数组引用要注意越界问题。(4)数组必须先定义，后使用,3初始化赋值说明：,(1)“=”后面的表达式列表一定要用括起来，被括起来的表达式之间用“，”分隔；(2)表达式的个数不能超过数组变量的大小；,例inta4=1,2,3,4,5;/超出了数组的大小,(3)如果表达式的个数小于数组的大小，则未指定值的数组元素被赋值为0；,例inta10=0,1,2,3,4;,(4)当对全部数组元素赋初值时，可以省略数组变量的大小，此时数组变量的实际大小就是初值列表中表达式的个数。,例charstr=a,b,c,d,e;则数组str的实际大小为5。,注意：在定义数组时，如果没有为数组变量赋初值，那么就不能省略数组的大小。而且数组不初始化，其数组元素为随机值。,4一维数组赋值,C语言除了在定义数组变量时用初值列表对数组整体赋值以外，无法再对数组变量进行整体赋值。,例inta5;a=1,2,3,4,5;a=1,2,3,4,5;a5=1,2,3,4,5;,错误！,数组定义后，如何对数组进行赋值呢？只能通过C语句对数组中的数组元素逐一赋值。,使用赋值语句来逐一赋值,例inta4;a0=1;a1=2;a2=3;a3=4;charstr80;str0=b;str1=y;str2=e;str3=0;/将数组str赋值为一字符串bye,这种方法是一种简单而且行之有效的方法，它适用于长度较小的数组或对长度较大的数组部分元素赋值，而且可对每个数组元素赋不同的值。,使用循环语句来逐一赋值,例如，将数组a的各元素赋值成奇数序列。inta10,i;for(i=0;i10;i+)ai=2*i+1;,例如，接受用户键盘输入赋值给数组各元素。inta10,i;for(i=0;i10;i+)scanf(%d,判断下列赋值是否正确？inta3;scanf(%d%d%d,a);,这种方法是在编程中普遍使用的一种方法，它适用于对某数组元素进行有规律的赋值或接受用户通过键盘输入对数组元素的赋值。,使用memset函数来赋值,memset函数原型：,memset(数组名a,具体数值,内存长度),功能：就是将s为首地址的一片连续的n个字节内存单元都赋值为ch。,例如，将数组str的每个数据单元赋值为a。charstr10;memset(str,a,10);,例如，将数组a的每个数据单元赋值为0（清0）。inta10;memset(a,0,10*sizeof(int);,这种方法是适合于数组的整体赋值,使用memcpy函数实现数组间的赋值,memcpy函数：,memcpy(目的数组b,源数组a,内存长度),功能：将s为首地址的一片连续的n个字节内存单元的值拷贝到以d为首地址的一片连续的内存单元中。,例如，两个数组元素之间的赋值。inta5=1,2,3,4,5,b5,i;for(i=0;i5;i+)bi=ai;,memcpy(b,a,5*sizeof(int);,注意：在使用memset和memcpy函数时，源程序中要包含头文件“string.h”。在TC或BC下头文件也可用“mem.h”，在VC下，则也可用“memory.h”。,二维数组及多维数组1、二维数组的定义定义方式：数据类型数组名常量表达式1常量表达式2；,数组元素的存放顺序原因:内存是一维的二维数组：按行序优先多维数组：最右下标变化最快,例inta34;floatb25;intc234;inta3,4;(),行数,列数,元素个数=行数*列数,二维数组理解,二维数组a是由3个元素组成,每个元素ai由包含4个元素的一维数组组成,2、二维数组元素的引用形式：数组名下标1下标23、二维数组元素的初始化p202分行初始化：,存储类型符数据类型数组变量名行常量表达式列常量表达式第0行初值表，第1行初值表，最后1行初值表；,按元素排列顺序初始化,存储类型符数据类型数组变量名行常量表达式列常量表达式初值表；,4、二维数组在程序中赋值,例:通过键盘输入对二维数组a各元素赋值inti,j,a23;for(i=0;i2;i+)for(j=0;j3;j+)scanf(%d,例:调用memset函数把数组a的各元素清0inta23;memset(a,0,6*sizeof(int);,例:通过memcpy函数将数组a各元素的值复制到数组b的各元素中intb23;memcpy(b,a,6*sizeof(int);,1.数组基础题(1)c语言试题集6.1-6.14,6.16-6.22,6.29-6.41(2)、有数组定义inta22=1,2,3;则a01的值为0?(3)、在windows下，写出运行结果，每空2分，共10分。charstr=Hello;char*p=str;intn=10;sizeof(str)=()sizeof(p)=()sizeof(n)=()voidfunc(charstr100)sizeof(str)=(),(4).用宏定义定义一个数据NUM，然后让系统分配NUM大小的整型数组(5).下列程序是否有错，更好的解决方法？inta602501000,i,j,k;for(k=0;k=1000;k+)for(j=0;j250;j+)for(i=0;i60;i+)aijk=0;,时间复杂度,1.概念：度量算法执行的时间长短2.计算复杂度:for（i=1;i=n;+i）for(j=1;j=n;+j)cij=0;/该步骤属于基本操作执行次数：n2for(k=1;k=n;+k)cij+=aik*bkj;/该步骤属于基本操作执行次数：n3,所以，该程序T（n）=O（n3）,3.分类按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。,时间复杂度越低,执行时间越短，越好,2.数组程序题,1.排序：冒泡排序p206，插入排序p207，选择排序(下一张幻灯片)等等2.查找：顺序查找，折半查找(有序数组)等等3.图形：找下标的关系,初始：49386597761327,13,49,一趟：13386597764927,27,38,二趟：13276597764938,三趟：13273897764965,四趟：13273849769765,五趟：13273849659776,六趟：13273849657697,选择排序图示效果,【例4】用选择排序法将10个整数按照从小到大的顺序排序,#includevoidmain()inta5,i,j,k,t;for(i=0;iaj)k=j;/始终保持ak当前最小if(k!=i)t=ak;/一次大的循环后，把ak和前面的值交换ak=ai;ai=t;for(i=0;i5;i+)printf(%dt,ai);,（1）.请编写一个程序，输出显示如下图形。1111112221123211222111111,#defineNUM5voidmain()intaNUMNUM;inti,j,m,n;for(i=0;iNUM;i+)for(j=0;jNUM;j+)m=(i=NUM-i-1)?i:NUM-i-1;n=(j=NUM-j-1)?j:NUM-j-1);if(m=n)aij=m+1;elseaij=n+1;for(i=0;iNUM;i+)for(j=0;jNUM;j+)printf(%d,aij);printf(n);,（2）.已知：无序数组，折半查找，各元素值唯一。函数原型是：Binary_Seach(intarray,intiValue,intiCount)array是数组，在里面用折半查找的方法找等于iValue的值，找到返回1否则0，iCount是元素个数分析：1，变成有序数组2.折半查找,intBinary_Seach(intarray,intiValue,intiCount)inti=0,j=iCount-1;/i低下标，j高下标intn=(i+j)/2;while(n!=0,（3）完成程序，实现对数组的降序排序#includevoidsort();intmain()intarray=45，56，76，234，1，34，23，2，3；sort();return0;voidsort()_|-|,(4)给定一个n个整型元素的数组a，其中有一个元素出现次数超过n/2，求这个元素。方法1：从第一个数开始计算，比较到最后方法2:给数组排序，中间这个就是,（5）求两个有序数组的共同元素，给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如a=0,1,2,3,4b=1,3,5,7,9输出1,3,（6）给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数是重复的，请找出这个数1.传统方法2.所有总数相加-（1+21000）的结果。,6）给定含有1001个元素的数组，其中存放了1-1000之内的整数，只有一个整数不是重复的，请找出这个数,1.传统方法2.利用异或(p132)因为对于任意一个数k，有kk=0，k0=k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，只留下了个数为奇数的那个元素。,(7)循环移位将一个含有n个元素的数组向右循环移动k位，要求时间复杂度是O(n)，且只能使用两个额外的变量分析比如数组1234循环右移1位将变成4123，观察可知123的顺序在移位前后没有改变，只是和4的位置交换了一下，所以等同于1234先划分为两部分123|4，然后将123逆序，再将4逆序得到3214，最后整体逆序得到4123,#includevoidchange(inta,intstart,intend)intt;while(startend)t=astart;astart=aend;aend=t;start+;end-;voidmain()inta4=1,2,3,4;inti,k;ints,e;printf(请输入向右移的位置:);scanf(%d,(8)组合问题给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子a=1,2,3,4,5m=3输出123,124,125,134,135,145234,235,245345,（9）重排问题给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：1.排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变例子a=1,0,2,0,3;变成0,0,1,2,32.不能使用额外存储空间分析：1.设置n为最后元素的下标,从最后一个元素开始往前循环，如果碰到非零，把非零数赋值给an,n-,直至结束,（10）和为n连续正数序列。题目：输入一个正数n，输出所有和为n连续正数序列。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。分析：这是网易的一道面试题。,inti,k=15,m=0,s,j;for(i=2;i0)/排除负数和0for(j=1;j0)for(j=1;j=i;j+)printf(%d,m);m+;printf(n);,4字符数组和字符串区别,1、字符数组定义：数组的类型为字符型，定义与普通数组相同,例：charc10,ch34;,2、字符串p230定义：字符串常量是用双引号括起来的一串字符。如“abc,123C语言中没有字符串变量，通常用字符数组来存储字符串C语言规定，字符串总是以0作为结束标志,字符数组和字符串,3、字符数组的初始化,逐个字符赋值,例；charch3=B,o,y;所占空间为3,用字符串常量赋值,例；charch3=Boy;所占空间为4,判断下列赋值是否等价:charstr=china;charstr=c,h,i,n,a,0;charstr=china;charstr=c,h,i,n,a;charstr10=china;charstr10=c,h,i,n,a;,1.关于strcpy常见面试题,（1）已知strcpy函数的原型是char*strcpy(char*strDest,constchar*strSrc);其中strDest是目的字符串，strSrc是源字符串。NaTPt1)不调用C+/C的字符串库函数，请编写函数strcpy2）strcpy能把strSrc的内容复制到strDest，为什么还要char*类型的返回值？,1)strcpy的实现代码char*strcpy(char*strDest,constchar*strSrc)if(strDest=NULL)|(strSrc=NULL)/1throwInvalidArguments;/2char*strDestCopy=strDest;/3while(*strDest+=*strSrc+)!=0)/4;returnstrDestCopy;,1(A)不检查指针的有效性，说明设计者不注重程序的健壮性(B)检查指针的有效性时使用(!strDest)|(!strSrc)或(!(strDest，同1(B)。(B)循环写成while(*strSrc!=0)*strDest+=*strSrc+;，说明答题者对边界条件的检查不力。循环体结束后，strDest字符串的末尾没有正确地加上0。,2）.找错voidtest1()charstring10;char*str1=0123456789;strcpy(string,str1);答：表面上并且编译都不会错误。但如果string数组原意表示的是字符串的话，那这个赋值就没有达到意图。最好定义为charstring11，这样最后一个元素可以存储字符串结尾符0;,voidtest2()charstring10,str110;for(intI=0;I10;I+)str1I=a;strcpy(string,str1);答：strcpy使用错误，strcpy只有遇到字符串末尾的0才会结束，而str1并没有结尾标志，导致strcpy函数越界访问，不妨让str19=0，这样就正常了。,voidtest3(char*str1)charstring10;if(strlen(str1)=10)strcpy(string,str1);答：这又会出现第一道改错题的错误了。strlen(str1)算出来的值是不包含结尾符0的，如果str1刚好为10个字符1结尾符，string就得不到结尾符了。可将strlen(str1)=10改为strlen(str1)10。,3.求结果#include#includevoidmain()chara5=he;printf(%d,strlen(a);,4.不用库函数，编写strcpy,strcat,strcmp,strlen等函数,intstrcmp(constchar*str1,constchar*str2)intlen=0;assert(str1!=0),intstrlen(constchar*str)intlen=0;assert(str!=NULL);while(*str+)len+;returnlen;,char*strcat(char*strDest,constchar*strScr)/将源字符串加const，表明其为输入参数char*address=strDest;/该语句若放在assert之后，编译出错assert(strDest!=NULL)/为了实现链式操作，将目的地址返回,5.字符数组和字符串相关题,（1）在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。分析：这道题是2006年googl