第2章++补充数组指针链表应用

面向对象程序设计C++信息工程学院王莉面向对象程序设计概述1C++概述2类和对象3派生类和继承4多态性5输入输出流类库6模板与异常处理7补充数组指针应用2第2章补充2.1数组2.2指针2.3链表应用1）一维数组的定义语法格式为：数据类型数组名[常量表达式]；例如：inta[5];//包含5个元素的整型数组a1、一维数组234567102901234a下标10010410810C11011411811C2345671029内存地址2.1数组2）一维数组元素的引用格式：数组名［下标］2345671002901234a[0]a[1]a[2]a[3]a[4]例如：inta[5];//包含5个元素的整型数组aa下标元素（3）一维数组的初始化在定义数组的同时给数组元素赋初值称为数组的初始化。其语法格式为：数据类型数组名[常量表达式]={初值表}；例如：inta[10]={1,2,3,4,5,6,7,8,9,10};//整型数组元素被全部初始化intb[10]={1,3,5,7,9};//初始化了部分数组元素intc[]={2,4,6,8,10};//通过对数组元素全部初始化（4）一维数组元素输入输出1)数组元素的输入for(j=0;jN;j++)cina[j];例如：inta[N];//N是已定义过的常量2)数组元素的输出for(j=0;jN;j++)couta[j];在C++中，使用new可以为一维数组动态分配内存空间，例如：int*p=newint[10];一维数组的长度也可以是变量，例如：intm;cinm;int*p=newint[m];释放new分配的内存空间，格式：delete[]p；（5）动态的一维数组相当于int*p,a[10];p=a;1）二维数组的定义语法格式为：数据类型数组名[常量表达式1][常量表达式2]；例如：inta[3][4];//定义3行4列的数组a2、二维数组2467495170240123024671495127024a内存24674951702410010410810C11011411812012412812C1301341382）二维数组元素的引用格式：数组名［行下标］[列下标]5a[1][2]（3）二维数组元素输入输出1)数组元素的输入for(i=0;i3;i++)for(j=0;j4;j++)cina[i][j];例如：inta[3][4]；2)数组元素的输出for(i=0;i3;i++)for(j=0;j4;j++)couta[i][j];（4）动态的二维数组思考：在c语言中二维数组的处理246749517024246749517024分解inta[3][4]在C++中，使用new可以为二维数组动态分配内存空间。246749517024246749517024分解①列数固定的二维数组，一般格式为：TYPE(*p)[N]=newTYPE[][N];//列固定p是指向包含有N个元素的数组指针。例如：指定列数的二维数组应用（4）动态的二维数组ppp（2）不指定数组的列数：246749517024246749517024分解p定义一个二级指针int**p;p=newint*[3];//int*[3]表示包含3个元素的指针数组给指针数组初始化for(inti=0;i3;++i){p[i]=newint[4];//动态分配包含4个元素数组}当数组使用完毕，释放空间的代码是：for(inti=0;i3;i++){delete[]p[i];//回收指针数组中每个指针所指向的一维数组占内存空间}delete[]p;//回收指针数组占的内存空间例如：不指定数组列数首先，数组的越界可能会引起程序的崩溃(如果崩溃了，还算你走运^_^)。其次是动态性不好，包括动态改变大小，动态申请。诸如此类的事，一定会让你伤透脑筋。有什么办法可以解决这些问题吗？在C++标准模板库（STL，StandardTemplateLibrary）中的array（阵列）、vector（向量）可以实现类似动态数组的功能，安全、方便。3、C++中ARRAY、VECTOR类2.2指针C++编译系统在编译时会为不同数据类型的对象分配大小不同的存储空间。char1个字节int4个字节float4个字节double8个字节每个存储单元都有一个固定的编号-即地址。计算机系统就是通过存放数据的第一个存储单元的地址对数据进行访问的。存放某个数据的第一个单元的地址称为该数据的首地址。指针是一种特殊的数据类型，存储每个指针需要4个字节的存储空间。用户定义的对象必须由系统为其分配存储单元，而不允许用户直接用地址常数为其分配存储单元。指针即内存单元的地址，数据即内存单元中的对象。例如：inta=68;通过地址0065FDF4H就能找到变量a在内存中的存储单元，从而对变量a进行访问。0065FDF4H就是变量a的指针。0065FDF4H682．指针变量存放地址的变量称为指针变量。例如：inta=68,pa；pa=&a;对变量a的两种访问方式：直接访问方式间接访问方式。0065FDF4Hpa680065FDF4Hapa3.指针变量的声明声明指针变量的一般格式为：类型名*变量名;例如：int*ip1;//声明了1个整型指针变量ip1float*fp;//声明了1个浮点型指针变量fp下面写法都是合法的：int*p;//*与类型名之间有空格，与变量名p之间没有空格int*p;//*与类型名之间没有空格，与变量名p之间有空格int*p;//*与类型名和变量名p之间都没有空格int*p;//*与类型名和变量名p之间都有空格4.指针可执行的运算指针只能进行下列几种运算：赋值运算、间接引用运算、算术运算、两个指针的相减运算和两个指针的比较运算。①赋值运算例如：inta=16,b=28;//声明2个整型变量a,bfloatx=32.6f,y=69.1f;//声明2个浮点型变量x,yint*pa=&a,*pb=&b;②间接引用运算例如：inta=16,b=28,c;int*pa,*pb=&b;cout*pbendl;//输出28pa=&a;c=*pa;coutcendl;//输出16*pa=32;//修改pa所指对象a的值，使a变成32coutaendl;//输出32注：*指针变量既可以作为左值，也可以作为右值。作为左值可以修改指针所指对象的值，作为右值只能间接引用所指对象的值。在C++语言中符号*有多种含义。*的含义随其所作用的对象及其位置的不同而不同。例如：inta=16,b=28;int*pa=&a,*pb;//符号*表示pa、pb是指针变量a*=b;//符号*表示进行乘法运算*pa=123;//符号*表示间接引用pa所指向的对象a③算术运算有两种：与整数的加减运算自增、自减运算。与整数的加减运算指针加上或减去一个整数n，表示指针从当前位置向后或向前移动n个sizeof数据类型长度的存储单元。例如:inta=16,*pa=&a,*p1,*p2;p1=pa+3;p2=pa-2;a的首地址是0066FDF4H，自增、自减运算指针的自增或自减表示指针从当前位置向后或向前移动sizeof数据类型长度的存储单元。例如：inta=36,*pa=&a,*p1,*p2;p1=pa++;p2=pa--;p1从pa单元向后移动4个字节；p2从pa单元向前移动4个字节。请注意下列表达式的计算顺序及含义：inta[5]={0,1,2,3,4};*p=a;1.p++;//指针p后移4个字节2.*p++;//先读取p指向的变量的值1，然后使指针p后移4个字节3.(*p)++;//读取p指向的变量a的值2，然后使p指向的变量a自增1,为34.*++p;//先使指针p后移4个字节，然后读取p指向的变量的值35.++*p;//将p指向的变量a自增1，为4④两指针相减例如：inta[10];p1=&a[1];//p1指向a[1]p2=&a[6];//p2指向a[6]cout(p2-p1)/sizeof(int)endl;//输出5⑤两个指针的比较运算例如：inta[10],*p,*q;p=&a[1];//p指向a[1]q=&a[6];//q指向a[6]if(p==q)coutequalendl;elsecoutnotequalendl;2.3简单链表及其应用采用动态分配内存，用new分配内存空间，不需要时用delete释放空间；由n个结点组成的链表（n≥0）指针数据指针数据aiai+1a1a2a3a4a5nulla6head由于结点结构中包含两个域，可以采用C++语言中的结构体类型实现。structNode{ElemTypedata;structNode*next;};1、建立单链表（1）头插法建表①算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。②具体算法实现beforecreat()//返回单链表的头指针{charch;Link*s;//工作指针ch=getchar();//读入第1个字符while(ch!='\n'){s=newLink;//生成新结点s-data=ch;//将读入的数据放入新结点的数据域中s-next=head;head=s;ch=getchar();//读入下一字符}}structLink{chardata;structLink*next;};（2）尾插法建表①算法思路从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。②具体算法实现voidaftercreat(){charch;Link*s,*r;//工作指针ch=getchar();//读入第1个字符while(ch!='\n'){s=newLink;//生成新结点s-data=ch;//将读入的数据放入新结点的数据域中s-next=NULL;if(head==NULL)head=s;//新结点插入空表elser-next=s;//将新结点插到*r之后r=s;//尾指针指向新表尾ch=getchar();//读入下一字符}//endwhile}（3）尾插法建带头结点的单链表①头结点及作用头结点是在链表的开始结点之前附加一个结点。它具有两个优点:⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。②带头结点的单链表③尾插法建带头结点链表算法voidheadaftercreat()//用尾插法建立带头结点的单链表{charch;Link*headnode;headnode=newLink;//生成头结点headnode-next=NULL;Link*s,*r;//工作指针head=headnode;//尾指针初值也指向头结点r=headnode;while((ch=getchar())!='\n'){s=newLink;//生成新结点s-data=ch;//将读入的数据放入新结点的数据域中s-next=NULL;r-next=s;r=s;}}2.插入结点（1）思想方法插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。具体步骤：（1）找到ai-1存储位置;（2）生成一个数据域为x的新结点*s;（3）令结点*p的指针域指向新结点;（4）新结点的指针域指向结点ai。voidinsert(Link*h,charx,inti){Link*p,*s;p=GetNode(h,i-1);//寻找第i-1个结点if(p==NULL)//i1或in+1时插入位置i有错{cout插入位置错误!end