第1章 C++程序设计基础

C++语言是在C语言基础上发展起来的主流程序设计语言之一，除全面兼容面向过程的程序设计语言C外，C++主要支持面向对象程序设计，还支持泛型程序设计。本章在已学习C程序设计基础上，首先引入了C++语言，介绍作为一个更好的C，C++引入的基本输入输出、函数重载、内联函数、引用等C++语言的重要机制，介绍了对象作用域和生存期、函数调用实现过程、动态分配、链表处理等程序设计的重要基础知识，最后，介绍了顺时针旋转矩阵、单链表操作典型案例。计算机学院李卫明第一章C++程序设计基础本章主要内容：1.1C++概述1.1.1C++简介 1.1.2C++11内置数据类型 1.1.3常量、变量和C++基本输入输出 1.2函数重载

1.3内联函数

1.4缺省参数值

1.5作用域和生存期

1.6栈和函数调用实现

1.7引用

1.7.1引用的概念 1.7.2引用和参数传递 1.8动态分配和释放1.8.1C++内存申请和释放 1.8.2典型范例——顺时针旋转矩阵 1.9链表处理1.9.1链表基础 1.9.2典型范例——单链表构造、插入、显示、销毁

计算机学院李卫明//Ex1.1一个简单的C++入门程序1//文件名:hello.cpp2#include<iostream>34intmain()5{6std::cout<<"Hello,C++World!"<<std::endl;//用C++方法输出一行

7return0;8}程序运行时屏幕输出如下：Hello,world!请按任意键继续...计算机学院李卫明1.1C++概述1.1.1C++简介样例代码前面的编号是为了便于程序内容解释，不是正式程序的组成部分。本讲义其余样例也是如此处理。每个C++程序都由若干个函数和类组成，与C一样，所有C++程序必须有且只有一个main()函数，程序从此函数开始执行。有的操作系统（如Linux)要求执行一个程序后必须向操作系统返回一个数值，标准C++要求main()函数必须声明为int型，但有些C++编译系统并未完全执行C++这一规定，如将样例中语句4改为“voidmain()”和删除语句7后，程序也能通过有些编译器的编译。大家应养成给程序添加注释的习惯。在C++程序中，可以使用C语言中“/*……*/”形式的注释；还可以使用以“//”开头的注释，代表本行“//”后面文字是注解。

例如样例中语句6：std::cout<<"Hello,C++World!"<<std::endl; //用C++的方法输出一行计算机学院李卫明预处理命令和命名空间std文件iostream的内容提供输入或输出时所需要的一些信息，如std::cout，使用时需要如下文件包含预处理命令：

#include<iostream>//编译预处理命令尽管目前很多编译器还支持带后缀.h的头文件，C++标准推荐头文件名不带后缀.h，使用时只需将原C语言形式头文件名前面加字母c并去除后缀.h即可,如#include<stdio.h>//传统C形式#include<cstdio>//C++推荐C++标准引入了名字空间概念。如样例中std::cout和std::endl一样，C++标准库名字基本定义在std名字空间内。如果在样例中语句2后插入下列语句：usingnamespacestd;

编译器便会在名字空间std里搜索相关名字，相关名字前std::就可以省略，以节省篇幅，本讲义后续样例基本照此处理计算机学院李卫明std::cout实际上是C++系统预定义的对象名，称为标准输出流对象。“<<”是“插入运算符”，在上面的代码中将运算符“<<”右侧双引号内的字符串“Hello,World!”插入到输出流中，std::endl用于表示换行，std::endl也插入到输出流中，C++系统将输出流的内容输出到系统指定的设备（一般为显示器）上C++中也可以用C函数printf()进行输出，但不建议使用；同时不可与cout混用程序调试执行时，执行结束后输出窗口将关闭，如暂停，以便用户观察执行结果，可以包含头文件<cstdlib>并在main()函数返回前添加下述语句：

system("PAUSE"); //输出系统提示信息

计算机学院李卫明1.1.2 C++11内置数据类型C++11内置基本数据类型与C基本相同，包括算术类型和空类型(void)。空类型不对应具体值，仅用于特殊场合，如表示函数无返回值时使用空类型作为返回类型、复合指针类型void*时表示指针指向类型暂时不明确。算术类型分为整形和浮点型2大类，浮点型包括:float、double、longdouble，其它内置算术类型都是整形，如表1.1所示。计算机学院李卫明

内置数据类型意义最小存储空间bool布尔值未定义char字符型1字节wchar_t宽字符2字节char16_tUnicode字符2字节char32_tUnicode字符4字节short短整型2字节int整型2字节long长整型4字节longlong超长整型8字节float单精度浮点数6位有效数字double双精度浮点数10位有效数字longdouble更高精度浮点数10位有效数字表1.1C++11算术类型定义数组时，数组大小应该是常量表达式，编译时可以确定此常量表达式的数值，不可以是运行时才确定数值的变量，同一个数组的所有元素具有相同数据类型；类类型主要在第2章开始讨论。计算机学院李卫明表1.1C++11算术类型1.1.3 常量、变量和C++基本输入输出

C++字面值常量与C语言一致，如32、3.14159、’A’、”Hello”，不需要命名，内部以内置数据类型或以’\0’字符结束的字符数组形式存储，在此不再展开。同样，与C语言类似，C++可以定义内置数据类型或复合内置数据类型的变量。变量定义的一般形式如下：类型

变量;类型

变量=初始化表达式;类型

变量(初始化表达式);类型

变量{初始化表达式};//C++11新增初始化方式类型

变量列表;计算机学院李卫明表1.1C++11算术类型例：inti=0,j=1,k(5),m{3},n;charch1=‘A’,ch2;doubled=2.58;int*p;charnameA[256];externintGlobalInt;//外部变量声明语句，不可初始化注意，为避免二义性，定义变量时如果没有初始化，不可带小括号。如下述语句声明X是一个返回整形结果的函数X，不是整形变量X。intX();计算机学院李卫明表1.1C++11算术类型C++引入了类和对象概念，是面向对象编程技术中的最基本的概念。类是现实世界或思维世界中实体在计算机中的反映，它将数据以及这些数据上的操作封装在一起，对象是具有类类型的变量。类是具有相同特性的对象的抽象，而对象是类的具体实例。类是抽象的，不占用内存，而对象是具体的，占用存储空间。类是用于创建对象的蓝图。上述声明和定义语句可扩展到标准库已有的类类型或程序自己定义的类类型，类类型的变量就是对象。如下述语句使用C++标准库STL里提供的string类定义了字符串对象str，初始化为“wang”。stringstr=“wang”;C++将变量扩展成对象，对象不仅具有状态，还具有设定的功能。变量可以看成是特殊的对象，我们在第二章开始学习如何设计和实现我们自己的类。计算机学院李卫明表1.1C++11算术类型程序运行过程中，变量或对象从建立时开始到消失时为止的周期称为变量或对象的生存期，详见本章第5节。绝大部分变量或对象的状态在生存期内会发生变化，也有少部分变量或对象在生存期内状态肯定不会发生变化，C++引入关键字const用于表达这一情况。如果类型名称前有const修饰，说明相应类型的变量或对象在建立时初始化后不可修改，一般称为常量或常量对象，常量对象简称为常对象，相对应，一般变量指可变化的量。常量必须在定义时初始化。计算机学院李卫明表1.1C++11算术类型例如：constintiSize=100;constdoublepi=3.14159;constint*p1=&i;int*constp2=&i;constint*constp3=&j;上述语句定义了多个常量，程序运行期间不可改变，如试图改变常量或常对象，编译将报错。注意，上述语句中p1是指针类型变量，不是常量，const修饰的是p1所指量，不可通过p1间接修改所指整形单元；p2、p3是常量，类型是指针，始终指向一个单元，有所不同的是p2所指单元内容可以改变，p3所指内容不可改变。计算机学院李卫明表1.1C++11算术类型在C语言中常用#define命令来定义符号常量，例如：#definePI3.14159 //声明符号常量PI

在预编译时进行字符替换，把程序中出现的字符串PI全部替换为3.14159

常量PI具有数据类型，在编译时要进行类型检查，占用存储单元，在程序运行期间它的值是固定的。建议采用const定义常量代替#define命令来定义符号常量计算机学院李卫明表1.1C++11算术类型C++预定义了标准输出流对象cout，内置数据类型的常量、变量或表达式值可以通过插入运算符<<往输出流对象输出，指定类类型的对象或表达式值也可通过插入运算符<<往输出流对象输出，如string类。如下述语句将变量（也可以是表达式）值输出到输出流对象中：cout<<i<<“,”<<j<<endl;cout<<ch1<<endl;cout<<d<<endl;cout<<nameA;cout<<str;计算机学院李卫明表1.1C++11算术类型C++还预定义了标准输入流对象cin，默认代表输入键盘设备，可以通过提取运算符>>从输入流对象提取数据存放在内置数据类型的变量里，也可提取数据存放在指定类类型的对象里，如string类对象str。如下述语句可以完成从键盘输入：cin>>i>>j;cin>>ch1;cin>>d;cin>>nameA;cin>>str;我们会在第四章学习我们自己设计的类类型的对象如何像内置数据类型或字符串类的对象一样使用提取运算符>>和插入运算符<<进行输入、输出。计算机学院李卫明表1.1C++11算术类型例用const定义常量使用示例。#include<iostream> //编译预处理命令usingnamespacestd; //使用命名空间stdintmain() //主函数main(){ constfloatPI=3.14159; //定义常量PI floatr,s; //定义变量

cout<<"输入半径:"; //输入提示信息

cin>>r; //输入半径r s=PI*r*r; //计算面积

cout<<"面积:"<<s<<endl; //输出面积

system("PAUSE"); //输出系统提示信息}计算机学院李卫明例cin与cout使用示例a。#include<iostream> //编译预处理命令usingnamespacestd; //使用命名空间stdintmain() //主函数main(){

cout<<"请输入你的姓名与年龄:"<<endl;//输出提示信息

charname[16]; //姓名

intage; //年龄

cin>>name; //输入姓名

cin>>age; //输入年龄

cout<<"你的姓名是:"<<name<<endl; //输出姓名

cout<<"你的年龄是:"<<age<<endl; //输出年龄

system("PAUSE"); //输出系统提示信息}对变量的定义放在执行语句之后。在C语言中要求变量的定义必须在执行语句之前。C++允许将变量的定义放在程序的任何位置。计算机学院李卫明

布尔类型布尔类型bool是ISO/ANSI（国际标准化组织／美国国家标准化组织）最近增补到C++语言中的。布尔变量包含两种取值：true或false。如果在表达式中使用布尔变量，它将把自身取值的true或false分别转换为1或0。如果将数值转换为布尔类型，如数值是零，布尔变量为false；如数值是非零值，布尔变量就为true。VS2013基本(内置)类型的相对大小图示:计算机学院李卫明例编写判断一个整型是否为质数的函数，并用此函数输出1~100之间的质数，要求编写测试程序。一个整型n如果大于1，并且不能被2~n-1之间的整数所整除，那么n为质数，由质数的定义很容易实现判断一个整型是否为质数的函数，具体程序实现如下。boolIsPrime(intn){ if(n<=1)returnfalse; //质数至少为2 for(intp=2;p<n;p++) if(n%p==0)returnfalse; //如n能被p整除,为合数

returntrue; //n不能被2~n-1之间的所有整数整除,为质数}intmain() //主函数main(){ for(intn=1;n<=100;n++) if(IsPrime(n)) //如果n为质数

cout<<n<<""; //那么输出n cout<<endl; //换行

system("PAUSE"); //输出系统提示信息

return0; //返回值0,返回操作系统}程序运行时屏幕输出如下：2357111317192329313741434753596167717379838997请按任意键继续...计算机学院李卫明1.2函数重载C++允许在同一作用域内定义多个同名函数，但要求这些函数参数的类型或个数不相同。这个功能称为函数重载，是一种参数性多态。在同一个作用域内，函数名相同，参数的类型或个数不同的函数称为重载函数。重载函数的形参个数或类型必须至少有其中之一不同，不允许参数个数和类型都相同而只有返回值类型不同，这是由于系统无法从函数的调用形式判断与哪一个重载函数相匹配。例:intMax(inta,intb);floatMax(floata,floatb);doubleMax(doublea,doubleb);计算机学院李卫明例求2个数中最小值（分别考虑整数、浮点数的情况）。intMin(inta,intb) //求2个整数的最小值{ returna<b?a:b; //返回a,b的最小值 }floatMin(floata,floatb) //求2个浮点数的最小值{ returna<b?a:b; //返回a,b的最小值 }intmain() //主函数main(){ inta,b; //定义整型变量

floatx,y; //定义浮点型变量

cout<<"输入整数a,b:"; //输入提示

cin>>a>>b; //输入a,b cout<<a<<","<<b<<"的最小值为"<<Min(a,b)<<endl; //输出a,b的最小值,调用“intMin(inta,intb)” cout<<“输入浮点数x,y:"; //输入提示

cin>>x>>y; //输入x,y cout<<x<<","<<y<<"的最小值为"<<Min(x,y)<<endl; //输出x,y的最小值,调用“floatMin(floata,floatb)” system("PAUSE"); //调用库函数system()，输出系统提示信息}计算机学院李卫明例用重载函数实现分别求2个整数或3个整数中的最小者。intMin(inta,intb) //求2个整数的最小值{ returna<b?a:b; //返回a,b的最小值 }intMin(inta,intb,intc) //求3个整数的最小值{ intt=a<b?a:b; //a,b的最小值

t=t<c?t:c; //t,c的最小值

returnt; //返回a,b,c的最小值 }intmain() //主函数main(){ inta,b,c; //定义整型变量

cout<<"输入整数a,b,c:"; //输入提示

cin>>a>>b>>c; //输入a,b,c cout<<a<<“,”<<b<<“的最小值为”<<Min(a,b)<<endl; //输出a,b的最小值,调用“intMin(inta,intb)” cout<<a<<","<<b<<","<<c<<"的最小值为"<<Min(a,b,c) <<endl;//输出a,b,c的最小值,调用“intMin(inta,intb,intc)” system("PAUSE"); //输出系统提示信息}计算机学院李卫明1.3内联函数内联函数为了避免函数调用开销，可以使用关键字inline指示编译器将函数作内联函数处理例:inlineintMax(inta,intb);inlinefloatMax(floata,floatb);inlinedoubleMax(doublea,doubleb);计算机学院李卫明1.4有默认参数的函数在C语言中，在函数调用时形参从实参获得参数值，所以实参的个数应与形参相同。有时多次调用同一函数时使用相同的实参值，C++允许给形参提供默认值，这样形参就不一定要从实参取值了。如有一函数声明：

floatArea(floatr=1.6); //有默认值的函数声明 上面的函数声明指定参数r的默认值为1.6，如果在调用此函数时无实参，则参数r的值为1.6，例如：

s=Area(); //等价于Area(1.6)计算机学院李卫明默认参数应在函数名第一次出现时指定。默认参数必须是函数参数表中最右边(尾部)的参数。例如：

floatVolume(floatl=10.0,floatw=8.0,floath);//错误

floatVolume(floatl=10.0,floatw=8.0,floath=6.0);//正确 对于上面正确的函数声明，可采用如下形式的函数调用：v=Volume(10.1,8.2,6.8); //形参值全从实参得到,l=10.1,w=8.2,h=6.8v=Volume(10.1,8.2); //最后1个形参的值取默认值,l=10.1,w=8.2,h=6.0v=Volume(10.1); //最后2个形参的值取默认值,l=10.1,w=8.0,h=6.0v=Volume(); //形参的值全取默认值,l=10.0,w=8.0,h=6.0计算机学院李卫明例函数默认参数示例。voidShow(charstr1[],charstr2[]="",charstr3[]=""); //在声明函数时给出默认值intmain() //主函数main(){ Show("你好!"); //str1值取"你好!",str2与str3取默认值

Show("你好,","欢迎学习C++!"); //str1值"你好,",str2取"欢迎学习C++!",str3取默认值

Show("你好",",","欢迎学习C++!"); //str1值"你好,",str2取",",str3取值"欢迎学习C++!" system("PAUSE"); //输出系统提示信息

return0; //返回值0,返回操作系统}voidShow(charstr1[],charstr2[],charstr3[]){ cout<<str1<<str2<<str3<<endl; //输出str1,str2,str3}计算机学院李卫明1.5变量(对象)作用域和生存期C++用标识符命名对象、函数和类型、类成员、类模板等，标识符作用域指通过该名字可以直接访问使用的范围。C++名字作用域从小到大依次有：复合语句作用域和函数原型作用域、函数作用域、类作用域、名字空间作用域和文件作用域。对象的生存期代表程序运行时，对象从建立到消失的时间周期。作用域和生存期，两者是不同的概念，也存在一定的关联性计算机学院李卫明声明在函数原型里的形式参数名字，只在该函数声明内有效，作用域是该函数声明，函数声明内的形参名字也因而可以省略。声明或定义在复合语句内的名字，作用域只是该复合语句，作为对象名字时，相应对象称为局部对象，程序在开始执行该局部对象所在复合语句时在运行栈上建立局部对象，执行完局部对象所在复合语句离开时撤销局部对象。同样地，声明或定义在函数体内的名字，作用域只是该函数体，作为对象名字时，相应对象也是局部对象，程序在开始执行该局部对象所在函数体时在运行栈上建立局部对象，执行完函数体离开时撤销局部对象。函数定义时的形参作用域就是该函数定义，形参对象也是局部对象，程序在开始执行该局部对象所在函数时在运行栈上建立局部对象，执行完函数离开时撤销局部对象。定义在类外和函数外，但在名字空间里的标识符，具有该名字空间作用域，定义在名字空间里的对象在程序开始执行时在全局对象和静态对象专用存储区上建立，程序执行结束时撤销。定义在类外和函数外，不在名字空间内的对象是外部对象，作用域限定在定义开始到该文件结束，程序在开始执行时在全局对象和静态对象专用存储区上建立外部对象，执行结束时撤销外部对象。计算机学院李卫明带extern修饰的外部对象，代表本文件或其它文件定义的同名外部对象，作用域限定在该文件内。带static修饰的外部静态对象与普通外部对象生存期相同，作用域限定在该文件内，其它文件不可引用该外部静态对象。带static修饰的局部静态对象与普通局部对象作用域相同，限定局部范围内，在程序第一次执行到该静态对象定义语句时在全局对象和静态对象专用存储区上建立，程序执行完结束时撤销。定义在不同作用域中的标识符名字相同时根据最小作用域原则确定标识符代表的对象、函数、类型等。动态分配生成的对象是匿名对象，通过指针间接访问，在new动态分配时在堆空间生成，在delete删除操作时撤销，没有执行delete删除所指对象时，会造成对象所占内存空间资源泄漏，影响程序执行所需内存资源，详见本章第8、9节。关于类成员作用域和成员生存期在第2章在讲述。计算机学院李卫明变量(对象)作用域和生存期小结对象(变量)生存期是指自对象生成至消失的时间段；由C++存储类修饰符auto、register、static 、extern指示；对象（变量）作用域指变量(对象)名称有效使用范围。C++变量(对象)作用域 生存期 修饰符

说明起始 终止 内部自动变量 复合语句内执行至此执行完该复合语句auto通常省略内部寄存器变量 同上 同上 同上register形参 函数体内函数开始执行函数执行结束内部静态变量 同上 程序开始执行程序执行结束 static函数体内外部静态变量 该处至文件尾同上同上 static函数体外外部变量该处至文件尾同上同上 [extern]函数体外或其它文件中 extern修饰自由对象 指针指示new生成delete删除 类成员（子对象）类或派生类内对象生存时对象消失时同（宿主）对象C++中由于引入类，实际函数内部静态变量已不应使用C++11auto已作类型自动推导用计算机学院李卫明堆空间、栈空间

全局对象和静态变量空间安排在系统专门提供的数据段内；局部对象存储空间安排在栈内（栈的概念在后面小节和第二章有介绍），具有非常高效率；自由对象根据需要从堆空间申请（malloc,new）；不需要使用时由程序员负责释放（free,delete）；所分配的内存需要手动释放，否则会造成内存泄漏。当然，在应用程序销毁时，也能得到释放。堆的频繁分配与释放可能会带来内存碎片，带来性能上的损失。和Java、C#语言不同，C++标准不提供垃圾自动回收；但某些第三方库和微软托管C++提供了类似垃圾自动回收实现。C/C++程序员必须切实掌握空间申请/释放。计算机学院李卫明1.6 栈和函数调用实现栈(stack)是程序设计中具有最后保存最先输出(LIFO:LastIn,FirstOut)特性的数据结构程序运行时，函数可以相互调用，或者递归调用。函数相互调用或者递归调用是通过运行栈实现的。运行栈可以看成计算机系统为程序运行分配的连续空间。程序执行到函数调用时，一般执行下列操作：1。函数返回地址压栈。2。在栈中，为函数返回类型、函数参数分配空间3。将实参传递给形参(根据不同传递方式，采用不同处理)。4。在栈中，为局部(自动、寄存器)变量分配空间。5。执行函数。6。函数执行结束时。程序从栈中取出返回值，程序转至函数返回地址处执行，同时废弃栈中为返回类型、函数参数、局部变量分配的空间。通过本节后面Hanoi塔问题分析可加深对函数调用包括递归调用的理解。计算机学院李卫明典型的Hanoi塔问题假设有三个命名为A、B、C的塔柱，初始时，在塔柱A上插有n个直径大小各不相同的圆盘，从上往下，圆盘从小到大编号为1、2、3、···n，要求将A柱上的圆盘移至塔柱C。圆盘移动必须遵守下列规则：1：每次只能移动一个圆盘；2：圆盘可以插在任意一个塔柱上；3：任何时刻都不能将一个较大的圆盘放在一个较小的圆盘上。我们可以用分治法分析解决这一问题。对于具有n个圆盘的Hanoi塔问题，形参x、y、z代表三个塔柱。处理思路如下：n等于1时只需将圆盘从x柱移至z柱即可；n大于1时，我们分三步完成：1：借助z塔柱，将x塔柱上的n-1个圆盘按照规定移至到y塔柱；2：将x塔柱上的一个圆盘由x柱移至z柱；3：借助x塔柱，将y塔柱上的n-1个圆盘按规定移至到z塔柱；计算机学院李卫明Hanoi塔问题完整代码如下：//Ex1.21#include<iostream>2usingnamespacestd;3//将n个盘子从x柱搬至z柱，可借助y柱

4voidHanoi(intn,charx,chary,charz);56intmain()7{intn;//盘子数量

8cin>>n;9Hanoi(n,'A','B','C');10}11//将n个盘子从x柱搬至z柱，可借助y柱

12voidHanoi(intn,charx,chary,charz)13{14if(n==1){15cout<<x<<"->"<<z<<endl;//一个盘子时可直接搬动

16}else{17Hanoi(n-1,x,z,y);//将n-1个盘子从x柱搬至y柱，借助z柱

18cout<<x<<"->"<<z<<endl;//剩余一个盘子时可直接搬动

19Hanoi(n-1,y,x,z);//将n-1个盘子从y柱搬至z柱，借助x柱

20}21}计算机学院李卫明EX1.2运行输入3时运行栈变化分析，可调试验证：计算机学院李卫明

1.7引用引用是C++引入的重要机制，广泛应用在函数间参数传递、函数返回值和运算符重载中简单的说，引用就是别名，代表被引用的对象或变量。计算机学院李卫明inti=5,j=10;int&ri=i;//ri是引用，初始化为iconstint&rj=j;//rj是常引用，初始化为jcout<<"i="<<i<<","<<"ri="<<ri<<endl;//输出i=5,ri=5++ri;cout<<"i="<<i<<","<<"ri="<<ri<<endl;//输出i=6,ri=6++i;cout<<"i="<<i<<","<<"ri="<<ri<<endl;//输出i=7,ri=7cout<<"j="<<j<<","<<"rj="<<rj<<endl;//输出j=10,rj=10//++rj;//报错，rj是常量引用，不可修改rj++j;cout<<"j="<<j<<","<<"rj="<<rj<<endl;//输出j=11,rj=11ri=rj;cout<<"i="<<i<<","<<"ri="<<ri<<endl;//输出i=11,ri=11//rj=ri;//报错，rj是常量引用，不可修改rj计算机学院李卫明参数传递和引用C++增加“引用”的主要目的是利用它作为函数参数和返回值，以便扩充函数传递数据的功能。在C语言中，参数传递主要采用采用传值方式。这时形参和实参不是同一个存储单元，函数调用时将实参（变量的值）传递给形参，传递是单向的，在执行函数期间形参值发生变化并不传回给实参。如果需要改变另一函数中变量的值，C语言函数调用需要中通过指针来间接改变所指变量值，使用不太直观、方便。（C数组传递实际是特殊情况，数组名即地址，类似指针）。C++中增加了参数引用传递方式，形参就是实参别名，形参变化即实参变化。计算机学院李卫明例以变量为实参不能实现交换变量的值的。voidSwap(inta,intb) //不能实现交换实参变量的值{ intt=a;a=b;b=t; //循环赋值交换a,b的值}intmain() //主函数main(){ intm=6,n=8; //定义整型变量

Swap(m,n); //调用函数Swap() cout<<m<<""<<n<<endl; //输出m,n的值}计算机学院李卫明在C程序中可以用指针传递变量地址的方法。使形参得到一个变量的地址，这时形参指针变量指向实参变量单元。例用指针变量作形参，实现两个变量的值互换。voidSwap(int*p,int*q) //实现交换*p与*q的值{ intt=*p;*p=*q;*q=t; //循环赋值交换*p与*q的值}intmain() //主函数main(){ intm=6,n=8; //定义整型变量

Swap(&m,&n); //调用函数Swap() cout<<m<<""<<n<<endl; //输出m,n的值}计算机学院李卫明在C++中，把变量的引用作为函数形参，由于形参是实参的引用，也就是形参是实参的别名，这样对形参的操作等价于对实参的操作。例利用引用形参实现交换两个变量的值。voidSwap(int&a,int&b) //实现交换实参变量的值{ intt=a;a=b;b=t; //循环赋值交换a与b的值}intmain() //主函数main(){ intm=6,n=8; //定义整型变量

Swap(m,n); //调用函数Swap() cout<<m<<""<<n<<endl; //输出m,n的值}计算机学院李卫明常引用常引用就是用const对引用加以限定，表示不允许改变该引用的值。例如：inta=6; //定义整型变量a，初值为6constint&b=a; //声明常引用，不允许改变b的值b=8; //改变常引用b的值，错误a=8; //改变a的值，正确常引用通常用作函数形参，这样能保证形参的值不被改变，又可提高大对象参数传递效率。计算机学院李卫明例常引用形参示例。structPerson{ charname[20]; //姓名

charsex[3]; //性别};voidShow(constPerson&p){ cout<<"姓名:"<<<<endl; //输出姓名

cout<<"性别:"<<p.sex<<endl; //输出性别}intmain() //主函数main(){ Personp={"李倩","女"}; //定义结构体变量

Show(p); //输出p}在程序中，用结构名Person作为类型来定义变量p，在C语言中，不能用结构名来定义结构变量名，必须在结构名前加struct才能定义结构变量，即应采用如下形式定义：struct Personp={"李倩","女"};//定义结构体变量计算机学院李卫明1.8动态分配和释放C语言内存申请主要通过malloc库函数进行，对应的释放内存库函数是free，纯粹用于内存分配和释放。作为面向对象的程序设计语言，C++不仅需要动态分配内存，还需要在分配的内存上建立对象，完成对象的初始化，释放时也需要先执行对象所需的扫尾处理，然后再归还空间，因此，C语言时代的malloc、free库函数已不能满足这一要求，C++为了兼容面向过程的C语言程序，保留了这一申请方法。类类型的对象初始化时会自动执行构造函数，对象撤销时会自动执行析构函数完成扫尾处理，关于对象的构造函数和析构函数，参见第2章。C++内存申请和释放主要通过new、delete运算符进行。主要方式有：动态生成单个对象和动态生成连续存放的对象数组，动态生成的对象存放在堆中。计算机学院李卫明T*p=newT;T*p=newT(初始化实参表);T*p=newT{初始化实参表};T*p=newT[n];上述语句中，T代表类型名，可以是内置数据类型、类类型或指向类型的指针型。p是指向T类型的指针变量，用来管理所指对象。前3个语句用于动态生成单个对象，后一个语句用于动态生成连续存放的n个对象，构成动态对象数组，n可以是运行时确定大小的变量或表达式。生成对象成功时返回一个非空指针，程序内部先完成存储空间分配，再在动态分配的空间上完成单个对象或连续多个对象的初始化。如果申请失败，C++编译器和开发工具有2种处理方案：一种是返回空指针，再加以判断处理；另一种是抛出异常，再按异常机制统一处理。抛出异常时，后续语句不再正常执行。关于异常处理，请参见第7章。现代C++程序主要采用第2种申请失败处理方案，具体信息可查阅编译器和开发工具，本讲义样例均采用异常处理方案。计算机学院李卫明注意，这里p是指针型变量，与所管理的匿名对象是相互独立存在的。函数执行完毕，局部指针变量p撤销时，p所指匿名对象并未撤销，所指对象不再需要时，应该显式使用delete删除p所指对象。删除语句如下：deletep;delete[]p;删除p所指对象或对象数组时，指针变量p本身并未消失。前者用于删除new动态生成的单个对象，后者用于删除数组方式new动态生成的连续多个对象，删除时先完成每个对象的扫尾处理（自动调用析构函数），再释放对象内存空间。delete所用指针值必须是相应new申请得到的指针值或空指针，否则，结果不确定。new申请得到的对象在删除后不可再使用，也不可重复释放，否则，结果同样不确定。删除空指针并无不妥，可以正确执行。计算机学院李卫明例new/delete运算符使用示例。intmain() //主函数main(){ int*p; //定义整型指针

p=newint(16); //分配单个整数的存储空间,并初始化为16 if(p==NULL) { cout<<"分配存储空间失败!"<<endl; exit(1); //退出程序的运行,并向操作系统返回1 } cout<<*p<<endl; //输出p所指向的动态存储空间的值16 deletep; //释放存储空间

p=newint; //分配单个整数的存储空间

if(p==NULL) { cout<<"分配存储空间失败!"<<endl; exit(2); //退出程序的运行,并向操作系统返回2 } *p=8; //将p指向的动态存储空间赋值为8 cout<<*p<<endl; //输出p所指向的动态存储空间的值8

……计算机学院李卫明例new/delete运算符使用示例。intmain() //主函数main(){

……

p=newint[8]; //分配整型数组存储空间

if(p==NULL) { cout<<"分配存储空间失败!"<<endl; exit(3); //退出程序的运行,并向操作系统返回3 } inti; //定义整型变量

for(i=0;i<8;i++) p[i]=i; //为数组赋元素值

for(i=0;i<8;i++) cout<<p[i]<<""; //输出数组元素值01234567 cout<<endl; //换行

delete[]p; //释放存储空间}计算机学院李卫明下述语句分别申请动态分配1个整形、1个初始化为10的整形、n个连续整形、一个字符串对象和n个字符串对象，并分别预以释放。intn=100;int*p1,*p2,*p3;string*pStr,*pStrs;p1=newint;p2=newint(10);p3=newint[n];pStr=newstring;pStrs=newstring[n];...deletep1;deletep2;delete[]p3;deletepStr;delete[]pStrs;计算机学院李卫明典型范例——顺时针旋转矩阵编写程序，读入正整数n，输出顺时针分布的矩阵。矩阵内容为顺时针顺序存放的n*n个数1、2、3、...n*n。样例输入：7样例输出：19202122232411837383940252173647484126316354649422741534454443285143332313029613121110987计算机学院李卫明解决这一问题，可按自顶向下、逐步分解的结构化程序设计思路，分解细化成如下算法步骤：Step1.输入n，建立n*n的矩阵，矩阵元素初始化为0；Step2.填充矩阵内容为顺时针顺序存放的n*n个数1、2、3、。。。n*n；2.1确定初始填充位置(iRow,iCol)和方向dir；2.2k=1ton*n循环完成k填充和调整；2.2.1当前位置填充k；2.2.2根据当前方向分4种情况，更新下步填充位置；Step3.输出矩阵。样例实现：1.使用数组版本/p/RTT4RHFtGR/2.使用动态分配版本(传统版,推荐)/p/Hnn7Mt2J6h/3.使用**版本(不推荐使用)/p/BnJbZFykSw/4.使用vector版本(STL版,推荐)/p/7YTPhtJM8C/计算机学院李卫明习题：编写程序，打印出N阶魔阵（N个奇数），要求使用动态分配。如输入N＝3和5时，输出如下：8 1 6 3 5 7 4 9 217 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9计算机学院李卫明1.9链表处理链表处理的基础是单链表，从单链表处理可推广到多链表处理和其它链表处理，本讲义涉及的内容基本限于单链表。线性关系的若干元素组成线性表，单链表可用来表示链表中所有结点内元素以及结点间的线性关系，也就是线性表。图1.2

单链表结点和单链表示例

1.9.1链表基础

图1.2a所示，链表中的结点一般由表示元素的数据域和表示下个结点的指针域2部分组成，指针域为空指针时表示无后续结点。

传统C/C++使用值定义为0的NULL表示空指针，C++11引入专门nullptr表示空指针，图中符号^代表空指针(nullptr)，本讲义中有关单链表的其它图示也一样。

结点数据类型一般定义如下，T代表具体应用中所需数据类型，实际应用中可确定具体数据类型，本节其它讨论中出现的类型T也一样。structNode{Tdata;Node*next;};图1.2b表示元素类型为字符串、无头结点的单链表，用于表示线性表（zhao,zhang,wang,sun,li），此处省略了字符串的双引号，T就是std::string类型；图1.2c表示元素类型为整型、带头结点的单链表，表示线性表（1,5,7,9），此处T就是int类型。整个单链表可通过类型为Node*的指针变量la1、la2访问和管理。注意，指针变量p和p所指结点是独立存在的，通过指针变量p可访问结点的数据域p->data和指针域p->next，这些表示既可作为右值出现在赋值运算符右边表达式，也可作为左值出现在赋值类运算符左边。链表中插入元素时，需要在链表中增加结点，所需结点可以用下述语句动态分配：Node*p;p=newNode;下列语句将p所指结点插入q所指结点后:p->next=q->next;//p后续结点设为原q后续结点q->next=p;//q后续结点设为p需要注意，一般情况下，链表增加结点时，结点需要动态分配。不可把局部变量或全局变量代表的结点作为普通结点链入链表中，否则，函数执行完毕，局部结点会自动消失，全局变量代表的结点则可能多次链入，造成链表混乱。链表需要仔细构建，程序访问链表结点时，需要确保访问内存单元可访问权，如果访问到无权访问内存，程序很可能崩溃。如果从链表中删除结点时，需要修改链表，并且最后删除指针所指结点，释放结点占有的存储空间，否则造成内存泄漏。除非删除的结点是链表的第一个结点，删除结点一般需要修改被删除结点的前一个结点的指针域。删除指针变量q所指结点的后一个结点一般需要执行下述语句：Node*t;t=q->next;//记住被删结点指针q->next=t->next;//修改链表,设q后续结点为原t后续结点deletet;//删除结点注意，最后一个语句删除t所指结点，指针变量t还是存在的，但删除后程序无权访问t所指结点，否则，可能造成结果错误或程序崩溃。正是由于单链表插入和删除结点时需要修改前一个结点的指针域，一般情况下，为简化算法，涉及不同位置插入和删除