C++ 面向?qū)ο蟪绦蛟O(shè)計 課件全套 （李衛(wèi)明）第0-8章 緒論、C++程序設(shè)計基礎(chǔ) - C++標(biāo)準(zhǔn)模板庫簡介

C++面向?qū)ο蟪绦蛟O(shè)計

總課時： 48學(xué)時課內(nèi)上機:12學(xué)時參考書SiddharthaRao.21天學(xué)通C++(第8版)袁國忠譯

比較通俗，含C++11介紹TheC++ProgrammingLanguage.BjarneStroustrup全面系統(tǒng)，C++語言發(fā)明者著作StanleyB.Lippman等.C++Primer(第5版)傳統(tǒng)名著、配合數(shù)據(jù)結(jié)構(gòu)知識理解NicolaiM.Josuttis.C++標(biāo)準(zhǔn)程序庫(第2版)侯捷譯.ＳＴＬ工具類著作鄭莉，董淵，何江舟.C++語言程序設(shè)計(第4版)C++98教材推薦自學(xué)網(wǎng)站：菜鳥教程RunOOB.com代碼交流網(wǎng)站:，大型代碼貼在網(wǎng)站上后給出鏈接聯(lián)系方式：QQ課程交流群：開發(fā)軟件的工程稱為軟件工程，軟件工程總體目標(biāo)（SoftwareEngineeringGoals）如下：可靠性（Reliability）不可靠的軟件系統(tǒng)沒有價值可理解性（Understandability）難于理解的軟件系統(tǒng)很難維護和繼續(xù)改進成本有效性（CostEffectiveness）軟件維護和改進成本需要在合理范圍內(nèi)可適應(yīng)性（Adaptability）軟件系統(tǒng)需要容易修改和擴充以適應(yīng)應(yīng)用需求的變化可重用性（Reusability）代碼應(yīng)該便于類似系統(tǒng)中重復(fù)使用計算機學(xué)院李衛(wèi)明程序設(shè)計語言發(fā)展簡史機器語言、匯編語言高級語言面向過程程序設(shè)計--------結(jié)構(gòu)化程序設(shè)計(StructuredProgramming)面向?qū)ο蟪绦蛟O(shè)計（ObjectOrientedProgramming)C++、Java、C#GenericProgramming泛型編程思維數(shù)據(jù)庫語言可視化面向?qū)ο箝_發(fā)工具我們課程主要講述C++面向?qū)ο蟪绦蛟O(shè)計計算機學(xué)院李衛(wèi)明高級語言工作有以下方式：解釋執(zhí)行、編譯執(zhí)行、混合方式解釋方式：在特定解釋環(huán)境下，源程序可一邊解釋、一邊執(zhí)行源程序

解釋執(zhí)行優(yōu)點：可在多種平臺解釋、運行缺點：速度慢、需開發(fā)環(huán)境編譯方式：先將多個源程序文件編譯、鏈接后形成可執(zhí)行程序，再執(zhí)行源程序1 編譯目標(biāo)程序1源程序2 編譯目標(biāo)程序2。。。源程序n 編譯目標(biāo)程序n 多個目標(biāo)程序和庫文件

鏈接

exe程序

執(zhí)行優(yōu)點：速度快、無需開發(fā)環(huán)境缺點：只能運行特定平臺混合方式：

先將源程序編譯成中間代碼，虛擬機再解釋執(zhí)行；如Java、C#計算機學(xué)院李衛(wèi)明C++簡史C:AT&TLabDennisRitchie1970sC++:BjarneStrouStrup1980s，STL是C++后期發(fā)展的強大標(biāo)準(zhǔn)庫。C++標(biāo)準(zhǔn):C++語言在不斷發(fā)展中,ISO1998通過C++98標(biāo)準(zhǔn)；2003小修訂，稱C++03；2011年頒布新標(biāo)準(zhǔn)，稱C++0X或C++11，主要推進STL和多線程等高級應(yīng)用。微軟C++托管架構(gòu)：微軟在C++標(biāo)準(zhǔn)基礎(chǔ)上增加的，不屬于標(biāo)準(zhǔn)C++基于C++開發(fā)工具:CodeBlocks、VisualC++6.0、VS2012、VS2013、GNUC++等.結(jié)構(gòu)化程序設(shè)計和面向?qū)ο蟪绦蛟O(shè)計結(jié)構(gòu)化程序設(shè)計:方法：自頂向下、逐步分解(功能分解）控制流：順序、分支、循環(huán)程序=算法+數(shù)據(jù)結(jié)構(gòu) (數(shù)據(jù)、處理數(shù)據(jù)代碼分開)Program=DataStructure+Algorithm面向?qū)ο蟪绦蛟O(shè)計：（世界是一個由相互協(xié)作自治主體組成的集合）程序=對象+消息Program=Object+Message封裝(Encapsulation)和信息隱蔽(InformationHiding)、繼承(Inheritance)、多態(tài)(Polymorphism)可較好支持程序可重用性、可理解性、可擴充性、提高軟件強壯性計算機學(xué)院李衛(wèi)明C++：

一個更好的CC++全面兼容C，繼承了C的“簡潔”、靈活、高效特點；C++在對C增加了面向?qū)ο蟮男赂拍畹耐瑫r也增加一些非面向?qū)ο蟮男绿匦?，這些特性使C++使用起來更方便與更安全；C++控制流與C完全相同；基本數(shù)據(jù)類型也與C相同，只增加了也增加了bool類型，值有true,false兩種（C99標(biāo)準(zhǔn)也支持此類型）支持面向?qū)ο蟪绦蛟O(shè)計C++通過類和繼承支持面向?qū)ο蟪绦蛟O(shè)計支持泛型程序設(shè)計在C++中，通過模板簡單而實用地實現(xiàn)了泛型程序設(shè)計技術(shù)，STL是最著名的標(biāo)準(zhǔn)泛型庫C++11新標(biāo)準(zhǔn)豐富了C++高端應(yīng)用，應(yīng)預(yù)重視。

重要新機制：右值引用、Lambda表達式、智能指針C++可稱謂博大精深，切記循序漸進，使用好已掌握的成分。本課程基于C++11標(biāo)準(zhǔn)講述C++面向?qū)ο蟪绦蛟O(shè)計計算機學(xué)院李衛(wèi)明語法、語義、語用簡單地說，語法是語言規(guī)定的、必須遵守的形式；語義是語句的意義；語用就是語言成分的使用方法。程序開發(fā)過程：

集成開發(fā)環(huán)境IDE中（IntegratedDevelopmentEnvironment）集成了以上四個步驟，大大方便了程序開發(fā)工作。

本課程建議開發(fā)工具CodeBlocks13.12以上，CodeBlocks13.12在可資源里查找，也可自行下載、安裝。同學(xué)們至少會用一種集成開發(fā)環(huán)境（如能做到兩種更好），在該環(huán)境下輸入和運行、調(diào)試程序。計算機學(xué)院李衛(wèi)明CodeBlocks13.12安裝說明CodeBlock13.12安裝包可在資源里或QQ群里下載，下載后雙擊安裝程序，建議按默認(rèn)選項安裝，安裝路徑最好不要包含中文。安裝完成后首次運行時按缺省選項自動檢測、設(shè)定已安裝的C/C++編譯器。計算機學(xué)院李衛(wèi)明計算機學(xué)院李衛(wèi)明新建一個程序（工程）。工程類型選控制臺應(yīng)用（Consoleapplication）。計算機學(xué)院李衛(wèi)明文件名、路徑名建議不要包含中文，避免以后的程序調(diào)試。計算機學(xué)院李衛(wèi)明通過Build菜單項下Rebuild子菜單重新編譯、鏈接程序。計算機學(xué)院李衛(wèi)明通過Build菜單項下Run子菜單運行程序。計算機學(xué)院李衛(wèi)明計算機學(xué)院李衛(wèi)明通過Settings菜單項下Compiler…子菜單，勾選C++11編譯器選項。遇到編譯器設(shè)定有問題時，可嘗試用下述自動檢測方法解決。計算機學(xué)院李衛(wèi)明調(diào)試（Debug）手段程序開發(fā)過程中存在兩種錯誤：語法錯誤（編譯錯誤）、語義錯誤。存在語法錯誤時，程序無法通過編譯、鏈接、運行，對照語言規(guī)定，比較容易排除語法錯誤；存在語義錯誤的程序可以通過編譯、鏈接，也可以運行，但運行結(jié)果存在錯誤。

通過IDE提供的調(diào)試工具查找程序語義錯誤是程序設(shè)計學(xué)習(xí)過程中必須掌握的技術(shù)，開發(fā)工具提供的主要調(diào)試手段有：設(shè)置斷點、觀察表達式(變量)值、修改變量值、單步執(zhí)行（traceinto,stepover)、設(shè)置斷言，大家應(yīng)該在程序設(shè)計過程中逐步掌握好程序調(diào)試。計算機學(xué)院李衛(wèi)明C++語言是在C語言基礎(chǔ)上發(fā)展起來的主流程序設(shè)計語言之一，除全面兼容面向過程的程序設(shè)計語言C外，C++主要支持面向?qū)ο蟪绦蛟O(shè)計，還支持泛型程序設(shè)計。本章在已學(xué)習(xí)C程序設(shè)計基礎(chǔ)上，首先引入了C++語言，介紹作為一個更好的C，C++引入的基本輸入輸出、函數(shù)重載、內(nèi)聯(lián)函數(shù)、引用等C++語言的重要機制，介紹了對象作用域和生存期、函數(shù)調(diào)用實現(xiàn)過程、動態(tài)分配、鏈表處理等程序設(shè)計的重要基礎(chǔ)知識，最后，介紹了順時針旋轉(zhuǎn)矩陣、單鏈表操作典型案例。計算機學(xué)院李衛(wèi)明第一章C++程序設(shè)計基礎(chǔ)本章主要內(nèi)容：1.1C++概述1.1.1C++簡介 1.1.2C++11內(nèi)置數(shù)據(jù)類型 1.1.3常量、變量和C++基本輸入輸出 1.2函數(shù)重載

1.3內(nèi)聯(lián)函數(shù)

1.4缺省參數(shù)值

1.5作用域和生存期

1.6棧和函數(shù)調(diào)用實現(xiàn)

1.7引用

1.7.1引用的概念 1.7.2引用和參數(shù)傳遞 1.8動態(tài)分配和釋放1.8.1C++內(nèi)存申請和釋放 1.8.2典型范例——順時針旋轉(zhuǎn)矩陣 1.9鏈表處理1.9.1鏈表基礎(chǔ) 1.9.2典型范例——單鏈表構(gòu)造、插入、顯示、銷毀

計算機學(xué)院李衛(wèi)明//Ex1.1一個簡單的C++入門程序1//文件名:hello.cpp2#include<iostream>34intmain()5{6std::cout<<"Hello,C++World!"<<std::endl;//用C++方法輸出一行

7return0;8}程序運行時屏幕輸出如下：Hello,world!請按任意鍵繼續(xù)...計算機學(xué)院李衛(wèi)明1.1C++概述1.1.1C++簡介樣例代碼前面的編號是為了便于程序內(nèi)容解釋，不是正式程序的組成部分。本講義其余樣例也是如此處理。每個C++程序都由若干個函數(shù)和類組成，與C一樣，所有C++程序必須有且只有一個main()函數(shù)，程序從此函數(shù)開始執(zhí)行。有的操作系統(tǒng)（如Linux)要求執(zhí)行一個程序后必須向操作系統(tǒng)返回一個數(shù)值，標(biāo)準(zhǔn)C++要求main()函數(shù)必須聲明為int型，但有些C++編譯系統(tǒng)并未完全執(zhí)行C++這一規(guī)定，如將樣例中語句4改為“voidmain()”和刪除語句7后，程序也能通過有些編譯器的編譯。大家應(yīng)養(yǎng)成給程序添加注釋的習(xí)慣。在C++程序中，可以使用C語言中“/*……*/”形式的注釋；還可以使用以“//”開頭的注釋，代表本行“//”后面文字是注解。

例如樣例中語句6：std::cout<<"Hello,C++World!"<<std::endl; //用C++的方法輸出一行計算機學(xué)院李衛(wèi)明預(yù)處理命令和命名空間std文件iostream的內(nèi)容提供輸入或輸出時所需要的一些信息，如std::cout，使用時需要如下文件包含預(yù)處理命令：

#include<iostream>//編譯預(yù)處理命令盡管目前很多編譯器還支持帶后綴.h的頭文件，C++標(biāo)準(zhǔn)推薦頭文件名不帶后綴.h，使用時只需將原C語言形式頭文件名前面加字母c并去除后綴.h即可,如#include<stdio.h>//傳統(tǒng)C形式#include<cstdio>//C++推薦C++標(biāo)準(zhǔn)引入了名字空間概念。如樣例中std::cout和std::endl一樣，C++標(biāo)準(zhǔn)庫名字基本定義在std名字空間內(nèi)。如果在樣例中語句2后插入下列語句：usingnamespacestd;

編譯器便會在名字空間std里搜索相關(guān)名字，相關(guān)名字前std::就可以省略，以節(jié)省篇幅，本講義后續(xù)樣例基本照此處理計算機學(xué)院李衛(wèi)明std::cout實際上是C++系統(tǒng)預(yù)定義的對象名，稱為標(biāo)準(zhǔn)輸出流對象。“<<”是“插入運算符”，在上面的代碼中將運算符“<<”右側(cè)雙引號內(nèi)的字符串“Hello,World!”插入到輸出流中，std::endl用于表示換行，std::endl也插入到輸出流中，C++系統(tǒng)將輸出流的內(nèi)容輸出到系統(tǒng)指定的設(shè)備（一般為顯示器）上C++中也可以用C函數(shù)printf()進行輸出，但不建議使用；同時不可與cout混用程序調(diào)試執(zhí)行時，執(zhí)行結(jié)束后輸出窗口將關(guān)閉，如暫停，以便用戶觀察執(zhí)行結(jié)果，可以包含頭文件<cstdlib>并在main()函數(shù)返回前添加下述語句：

system("PAUSE"); //輸出系統(tǒng)提示信息

計算機學(xué)院李衛(wèi)明1.1.2 C++11內(nèi)置數(shù)據(jù)類型C++11內(nèi)置基本數(shù)據(jù)類型與C基本相同，包括算術(shù)類型和空類型(void)?？疹愋筒粚?yīng)具體值，僅用于特殊場合，如表示函數(shù)無返回值時使用空類型作為返回類型、復(fù)合指針類型void*時表示指針指向類型暫時不明確。算術(shù)類型分為整形和浮點型2大類，浮點型包括:float、double、longdouble，其它內(nèi)置算術(shù)類型都是整形，如表1.1所示。計算機學(xué)院李衛(wèi)明

內(nèi)置數(shù)據(jù)類型意義最小存儲空間bool布爾值未定義char字符型1字節(jié)wchar_t寬字符2字節(jié)char16_tUnicode字符2字節(jié)char32_tUnicode字符4字節(jié)short短整型2字節(jié)int整型2字節(jié)long長整型4字節(jié)longlong超長整型8字節(jié)float單精度浮點數(shù)6位有效數(shù)字double雙精度浮點數(shù)10位有效數(shù)字longdouble更高精度浮點數(shù)10位有效數(shù)字表1.1C++11算術(shù)類型定義數(shù)組時，數(shù)組大小應(yīng)該是常量表達式，編譯時可以確定此常量表達式的數(shù)值，不可以是運行時才確定數(shù)值的變量，同一個數(shù)組的所有元素具有相同數(shù)據(jù)類型；類類型主要在第2章開始討論。計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型1.1.3 常量、變量和C++基本輸入輸出

C++字面值常量與C語言一致，如32、3.14159、’A’、”Hello”，不需要命名，內(nèi)部以內(nèi)置數(shù)據(jù)類型或以’\0’字符結(jié)束的字符數(shù)組形式存儲，在此不再展開。同樣，與C語言類似，C++可以定義內(nèi)置數(shù)據(jù)類型或復(fù)合內(nèi)置數(shù)據(jù)類型的變量。變量定義的一般形式如下：類型

變量;類型

變量=初始化表達式;類型

變量(初始化表達式);類型

變量{初始化表達式};//C++11新增初始化方式類型

變量列表;計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型例：inti=0,j=1,k(5),m{3},n;charch1=‘A’,ch2;doubled=2.58;int*p;charnameA[256];externintGlobalInt;//外部變量聲明語句，不可初始化注意，為避免二義性，定義變量時如果沒有初始化，不可帶小括號。如下述語句聲明X是一個返回整形結(jié)果的函數(shù)X，不是整形變量X。intX();計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型C++引入了類和對象概念，是面向?qū)ο缶幊碳夹g(shù)中的最基本的概念。類是現(xiàn)實世界或思維世界中實體在計算機中的反映，它將數(shù)據(jù)以及這些數(shù)據(jù)上的操作封裝在一起，對象是具有類類型的變量。類是具有相同特性的對象的抽象，而對象是類的具體實例。類是抽象的，不占用內(nèi)存，而對象是具體的，占用存儲空間。類是用于創(chuàng)建對象的藍圖。上述聲明和定義語句可擴展到標(biāo)準(zhǔn)庫已有的類類型或程序自己定義的類類型，類類型的變量就是對象。如下述語句使用C++標(biāo)準(zhǔn)庫STL里提供的string類定義了字符串對象str，初始化為“wang”。stringstr=“wang”;C++將變量擴展成對象，對象不僅具有狀態(tài)，還具有設(shè)定的功能。變量可以看成是特殊的對象，我們在第二章開始學(xué)習(xí)如何設(shè)計和實現(xiàn)我們自己的類。計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型程序運行過程中，變量或?qū)ο髲慕r開始到消失時為止的周期稱為變量或?qū)ο蟮纳嫫?，詳見本章?節(jié)。絕大部分變量或?qū)ο蟮臓顟B(tài)在生存期內(nèi)會發(fā)生變化，也有少部分變量或?qū)ο笤谏嫫趦?nèi)狀態(tài)肯定不會發(fā)生變化，C++引入關(guān)鍵字const用于表達這一情況。如果類型名稱前有const修飾，說明相應(yīng)類型的變量或?qū)ο笤诮r初始化后不可修改，一般稱為常量或常量對象，常量對象簡稱為常對象，相對應(yīng)，一般變量指可變化的量。常量必須在定義時初始化。計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型例如：constintiSize=100;constdoublepi=3.14159;constint*p1=&i;int*constp2=&i;constint*constp3=&j;上述語句定義了多個常量，程序運行期間不可改變，如試圖改變常量或常對象，編譯將報錯。注意，上述語句中p1是指針類型變量，不是常量，const修飾的是p1所指量，不可通過p1間接修改所指整形單元；p2、p3是常量，類型是指針，始終指向一個單元，有所不同的是p2所指單元內(nèi)容可以改變，p3所指內(nèi)容不可改變。計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型在C語言中常用#define命令來定義符號常量，例如：#definePI3.14159 //聲明符號常量PI

在預(yù)編譯時進行字符替換，把程序中出現(xiàn)的字符串PI全部替換為3.14159

常量PI具有數(shù)據(jù)類型，在編譯時要進行類型檢查，占用存儲單元，在程序運行期間它的值是固定的。建議采用const定義常量代替#define命令來定義符號常量計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型C++預(yù)定義了標(biāo)準(zhǔn)輸出流對象cout，內(nèi)置數(shù)據(jù)類型的常量、變量或表達式值可以通過插入運算符<<往輸出流對象輸出，指定類類型的對象或表達式值也可通過插入運算符<<往輸出流對象輸出，如string類。如下述語句將變量（也可以是表達式）值輸出到輸出流對象中：cout<<i<<“,”<<j<<endl;cout<<ch1<<endl;cout<<d<<endl;cout<<nameA;cout<<str;計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型C++還預(yù)定義了標(biāo)準(zhǔn)輸入流對象cin，默認(rèn)代表輸入鍵盤設(shè)備，可以通過提取運算符>>從輸入流對象提取數(shù)據(jù)存放在內(nèi)置數(shù)據(jù)類型的變量里，也可提取數(shù)據(jù)存放在指定類類型的對象里，如string類對象str。如下述語句可以完成從鍵盤輸入：cin>>i>>j;cin>>ch1;cin>>d;cin>>nameA;cin>>str;我們會在第四章學(xué)習(xí)我們自己設(shè)計的類類型的對象如何像內(nèi)置數(shù)據(jù)類型或字符串類的對象一樣使用提取運算符>>和插入運算符<<進行輸入、輸出。計算機學(xué)院李衛(wèi)明表1.1C++11算術(shù)類型例用const定義常量使用示例。#include<iostream> //編譯預(yù)處理命令usingnamespacestd; //使用命名空間stdintmain() //主函數(shù)main(){ constfloatPI=3.14159; //定義常量PI floatr,s; //定義變量

cout<<"輸入半徑:"; //輸入提示信息

cin>>r; //輸入半徑r s=PI*r*r; //計算面積

cout<<"面積:"<<s<<endl; //輸出面積

system("PAUSE"); //輸出系統(tǒng)提示信息}計算機學(xué)院李衛(wèi)明例cin與cout使用示例a。#include<iostream> //編譯預(yù)處理命令usingnamespacestd; //使用命名空間stdintmain() //主函數(shù)main(){

cout<<"請輸入你的姓名與年齡:"<<endl;//輸出提示信息

charname[16]; //姓名

intage; //年齡

cin>>name; //輸入姓名

cin>>age; //輸入年齡

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

cout<<"你的年齡是:"<<age<<endl; //輸出年齡

system("PAUSE"); //輸出系統(tǒng)提示信息}對變量的定義放在執(zhí)行語句之后。在C語言中要求變量的定義必須在執(zhí)行語句之前。C++允許將變量的定義放在程序的任何位置。計算機學(xué)院李衛(wèi)明

布爾類型布爾類型bool是ISO/ANSI（國際標(biāo)準(zhǔn)化組織／美國國家標(biāo)準(zhǔn)化組織）最近增補到C++語言中的。布爾變量包含兩種取值：true或false。如果在表達式中使用布爾變量，它將把自身取值的true或false分別轉(zhuǎn)換為1或0。如果將數(shù)值轉(zhuǎn)換為布爾類型，如數(shù)值是零，布爾變量為false；如數(shù)值是非零值，布爾變量就為true。VS2013基本(內(nèi)置)類型的相對大小圖示:計算機學(xué)院李衛(wèi)明例編寫判斷一個整型是否為質(zhì)數(shù)的函數(shù)，并用此函數(shù)輸出1~100之間的質(zhì)數(shù)，要求編寫測試程序。一個整型n如果大于1，并且不能被2~n-1之間的整數(shù)所整除，那么n為質(zhì)數(shù)，由質(zhì)數(shù)的定義很容易實現(xiàn)判斷一個整型是否為質(zhì)數(shù)的函數(shù)，具體程序?qū)崿F(xiàn)如下。boolIsPrime(intn){ if(n<=1)returnfalse; //質(zhì)數(shù)至少為2 for(intp=2;p<n;p++) if(n%p==0)returnfalse; //如n能被p整除,為合數(shù)

returntrue; //n不能被2~n-1之間的所有整數(shù)整除,為質(zhì)數(shù)}intmain() //主函數(shù)main(){ for(intn=1;n<=100;n++) if(IsPrime(n)) //如果n為質(zhì)數(shù)

cout<<n<<""; //那么輸出n cout<<endl; //換行

system("PAUSE"); //輸出系統(tǒng)提示信息

return0; //返回值0,返回操作系統(tǒng)}程序運行時屏幕輸出如下：2357111317192329313741434753596167717379838997請按任意鍵繼續(xù)...計算機學(xué)院李衛(wèi)明1.2函數(shù)重載C++允許在同一作用域內(nèi)定義多個同名函數(shù)，但要求這些函數(shù)參數(shù)的類型或個數(shù)不相同。這個功能稱為函數(shù)重載，是一種參數(shù)性多態(tài)。在同一個作用域內(nèi)，函數(shù)名相同，參數(shù)的類型或個數(shù)不同的函數(shù)稱為重載函數(shù)。重載函數(shù)的形參個數(shù)或類型必須至少有其中之一不同，不允許參數(shù)個數(shù)和類型都相同而只有返回值類型不同，這是由于系統(tǒng)無法從函數(shù)的調(diào)用形式判斷與哪一個重載函數(shù)相匹配。例:intMax(inta,intb);floatMax(floata,floatb);doubleMax(doublea,doubleb);計算機學(xué)院李衛(wèi)明例求2個數(shù)中最小值（分別考慮整數(shù)、浮點數(shù)的情況）。intMin(inta,intb) //求2個整數(shù)的最小值{ returna<b?a:b; //返回a,b的最小值 }floatMin(floata,floatb) //求2個浮點數(shù)的最小值{ returna<b?a:b; //返回a,b的最小值 }intmain() //主函數(shù)main(){ inta,b; //定義整型變量

floatx,y; //定義浮點型變量

cout<<"輸入整數(shù)a,b:"; //輸入提示

cin>>a>>b; //輸入a,b cout<<a<<","<<b<<"的最小值為"<<Min(a,b)<<endl; //輸出a,b的最小值,調(diào)用“intMin(inta,intb)” cout<<“輸入浮點數(shù)x,y:"; //輸入提示

cin>>x>>y; //輸入x,y cout<<x<<","<<y<<"的最小值為"<<Min(x,y)<<endl; //輸出x,y的最小值,調(diào)用“floatMin(floata,floatb)” system("PAUSE"); //調(diào)用庫函數(shù)system()，輸出系統(tǒng)提示信息}計算機學(xué)院李衛(wèi)明例用重載函數(shù)實現(xiàn)分別求2個整數(shù)或3個整數(shù)中的最小者。intMin(inta,intb) //求2個整數(shù)的最小值{ returna<b?a:b; //返回a,b的最小值 }intMin(inta,intb,intc) //求3個整數(shù)的最小值{ intt=a<b?a:b; //a,b的最小值

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

returnt; //返回a,b,c的最小值 }intmain() //主函數(shù)main(){ inta,b,c; //定義整型變量

cout<<"輸入整數(shù)a,b,c:"; //輸入提示

cin>>a>>b>>c; //輸入a,b,c cout<<a<<“,”<<b<<“的最小值為”<<Min(a,b)<<endl; //輸出a,b的最小值,調(diào)用“intMin(inta,intb)” cout<<a<<","<<b<<","<<c<<"的最小值為"<<Min(a,b,c) <<endl;//輸出a,b,c的最小值,調(diào)用“intMin(inta,intb,intc)” system("PAUSE"); //輸出系統(tǒng)提示信息}計算機學(xué)院李衛(wèi)明1.3內(nèi)聯(lián)函數(shù)內(nèi)聯(lián)函數(shù)為了避免函數(shù)調(diào)用開銷，可以使用關(guān)鍵字inline指示編譯器將函數(shù)作內(nèi)聯(lián)函數(shù)處理例:inlineintMax(inta,intb);inlinefloatMax(floata,floatb);inlinedoubleMax(doublea,doubleb);計算機學(xué)院李衛(wèi)明1.4有默認(rèn)參數(shù)的函數(shù)在C語言中，在函數(shù)調(diào)用時形參從實參獲得參數(shù)值，所以實參的個數(shù)應(yīng)與形參相同。有時多次調(diào)用同一函數(shù)時使用相同的實參值，C++允許給形參提供默認(rèn)值，這樣形參就不一定要從實參取值了。如有一函數(shù)聲明：

floatArea(floatr=1.6); //有默認(rèn)值的函數(shù)聲明 上面的函數(shù)聲明指定參數(shù)r的默認(rèn)值為1.6，如果在調(diào)用此函數(shù)時無實參，則參數(shù)r的值為1.6，例如：

s=Area(); //等價于Area(1.6)計算機學(xué)院李衛(wèi)明默認(rèn)參數(shù)應(yīng)在函數(shù)名第一次出現(xiàn)時指定。默認(rèn)參數(shù)必須是函數(shù)參數(shù)表中最右邊(尾部)的參數(shù)。例如：

floatVolume(floatl=10.0,floatw=8.0,floath);//錯誤

floatVolume(floatl=10.0,floatw=8.0,floath=6.0);//正確 對于上面正確的函數(shù)聲明，可采用如下形式的函數(shù)調(diào)用：v=Volume(10.1,8.2,6.8); //形參值全從實參得到,l=10.1,w=8.2,h=6.8v=Volume(10.1,8.2); //最后1個形參的值取默認(rèn)值,l=10.1,w=8.2,h=6.0v=Volume(10.1); //最后2個形參的值取默認(rèn)值,l=10.1,w=8.0,h=6.0v=Volume(); //形參的值全取默認(rèn)值,l=10.0,w=8.0,h=6.0計算機學(xué)院李衛(wèi)明例函數(shù)默認(rèn)參數(shù)示例。voidShow(charstr1[],charstr2[]="",charstr3[]=""); //在聲明函數(shù)時給出默認(rèn)值intmain() //主函數(shù)main(){ Show("你好!"); //str1值取"你好!",str2與str3取默認(rèn)值

Show("你好,","歡迎學(xué)習(xí)C++!"); //str1值"你好,",str2取"歡迎學(xué)習(xí)C++!",str3取默認(rèn)值

Show("你好",",","歡迎學(xué)習(xí)C++!"); //str1值"你好,",str2取",",str3取值"歡迎學(xué)習(xí)C++!" system("PAUSE"); //輸出系統(tǒng)提示信息

return0; //返回值0,返回操作系統(tǒng)}voidShow(charstr1[],charstr2[],charstr3[]){ cout<<str1<<str2<<str3<<endl; //輸出str1,str2,str3}計算機學(xué)院李衛(wèi)明1.5變量(對象)作用域和生存期C++用標(biāo)識符命名對象、函數(shù)和類型、類成員、類模板等，標(biāo)識符作用域指通過該名字可以直接訪問使用的范圍。C++名字作用域從小到大依次有：復(fù)合語句作用域和函數(shù)原型作用域、函數(shù)作用域、類作用域、名字空間作用域和文件作用域。對象的生存期代表程序運行時，對象從建立到消失的時間周期。作用域和生存期，兩者是不同的概念，也存在一定的關(guān)聯(lián)性計算機學(xué)院李衛(wèi)明聲明在函數(shù)原型里的形式參數(shù)名字，只在該函數(shù)聲明內(nèi)有效，作用域是該函數(shù)聲明，函數(shù)聲明內(nèi)的形參名字也因而可以省略。聲明或定義在復(fù)合語句內(nèi)的名字，作用域只是該復(fù)合語句，作為對象名字時，相應(yīng)對象稱為局部對象，程序在開始執(zhí)行該局部對象所在復(fù)合語句時在運行棧上建立局部對象，執(zhí)行完局部對象所在復(fù)合語句離開時撤銷局部對象。同樣地，聲明或定義在函數(shù)體內(nèi)的名字，作用域只是該函數(shù)體，作為對象名字時，相應(yīng)對象也是局部對象，程序在開始執(zhí)行該局部對象所在函數(shù)體時在運行棧上建立局部對象，執(zhí)行完函數(shù)體離開時撤銷局部對象。函數(shù)定義時的形參作用域就是該函數(shù)定義，形參對象也是局部對象，程序在開始執(zhí)行該局部對象所在函數(shù)時在運行棧上建立局部對象，執(zhí)行完函數(shù)離開時撤銷局部對象。定義在類外和函數(shù)外，但在名字空間里的標(biāo)識符，具有該名字空間作用域，定義在名字空間里的對象在程序開始執(zhí)行時在全局對象和靜態(tài)對象專用存儲區(qū)上建立，程序執(zhí)行結(jié)束時撤銷。定義在類外和函數(shù)外，不在名字空間內(nèi)的對象是外部對象，作用域限定在定義開始到該文件結(jié)束，程序在開始執(zhí)行時在全局對象和靜態(tài)對象專用存儲區(qū)上建立外部對象，執(zhí)行結(jié)束時撤銷外部對象。計算機學(xué)院李衛(wèi)明帶extern修飾的外部對象，代表本文件或其它文件定義的同名外部對象，作用域限定在該文件內(nèi)。帶static修飾的外部靜態(tài)對象與普通外部對象生存期相同，作用域限定在該文件內(nèi)，其它文件不可引用該外部靜態(tài)對象。帶static修飾的局部靜態(tài)對象與普通局部對象作用域相同，限定局部范圍內(nèi)，在程序第一次執(zhí)行到該靜態(tài)對象定義語句時在全局對象和靜態(tài)對象專用存儲區(qū)上建立，程序執(zhí)行完結(jié)束時撤銷。定義在不同作用域中的標(biāo)識符名字相同時根據(jù)最小作用域原則確定標(biāo)識符代表的對象、函數(shù)、類型等。動態(tài)分配生成的對象是匿名對象，通過指針間接訪問，在new動態(tài)分配時在堆空間生成，在delete刪除操作時撤銷，沒有執(zhí)行delete刪除所指對象時，會造成對象所占內(nèi)存空間資源泄漏，影響程序執(zhí)行所需內(nèi)存資源，詳見本章第8、9節(jié)。關(guān)于類成員作用域和成員生存期在第2章在講述。計算機學(xué)院李衛(wèi)明變量(對象)作用域和生存期小結(jié)對象(變量)生存期是指自對象生成至消失的時間段；由C++存儲類修飾符auto、register、static 、extern指示；對象（變量）作用域指變量(對象)名稱有效使用范圍。C++變量(對象)作用域 生存期 修飾符

說明起始 終止 內(nèi)部自動變量 復(fù)合語句內(nèi)執(zhí)行至此執(zhí)行完該復(fù)合語句auto通常省略內(nèi)部寄存器變量 同上 同上 同上register形參 函數(shù)體內(nèi)函數(shù)開始執(zhí)行函數(shù)執(zhí)行結(jié)束內(nèi)部靜態(tài)變量 同上 程序開始執(zhí)行程序執(zhí)行結(jié)束 static函數(shù)體內(nèi)外部靜態(tài)變量 該處至文件尾同上同上 static函數(shù)體外外部變量該處至文件尾同上同上 [extern]函數(shù)體外或其它文件中 extern修飾自由對象 指針指示new生成delete刪除 類成員（子對象）類或派生類內(nèi)對象生存時對象消失時同（宿主）對象C++中由于引入類，實際函數(shù)內(nèi)部靜態(tài)變量已不應(yīng)使用C++11auto已作類型自動推導(dǎo)用計算機學(xué)院李衛(wèi)明堆空間、?？臻g

全局對象和靜態(tài)變量空間安排在系統(tǒng)專門提供的數(shù)據(jù)段內(nèi)；局部對象存儲空間安排在棧內(nèi)（棧的概念在后面小節(jié)和第二章有介紹），具有非常高效率；自由對象根據(jù)需要從堆空間申請（malloc,new）；不需要使用時由程序員負責(zé)釋放（free,delete）；所分配的內(nèi)存需要手動釋放，否則會造成內(nèi)存泄漏。當(dāng)然，在應(yīng)用程序銷毀時，也能得到釋放。堆的頻繁分配與釋放可能會帶來內(nèi)存碎片，帶來性能上的損失。和Java、C#語言不同，C++標(biāo)準(zhǔn)不提供垃圾自動回收；但某些第三方庫和微軟托管C++提供了類似垃圾自動回收實現(xiàn)。C/C++程序員必須切實掌握空間申請/釋放。計算機學(xué)院李衛(wèi)明1.6 棧和函數(shù)調(diào)用實現(xiàn)棧(stack)是程序設(shè)計中具有最后保存最先輸出(LIFO:LastIn,FirstOut)特性的數(shù)據(jù)結(jié)構(gòu)程序運行時，函數(shù)可以相互調(diào)用，或者遞歸調(diào)用。函數(shù)相互調(diào)用或者遞歸調(diào)用是通過運行棧實現(xiàn)的。運行?？梢钥闯捎嬎銠C系統(tǒng)為程序運行分配的連續(xù)空間。程序執(zhí)行到函數(shù)調(diào)用時，一般執(zhí)行下列操作：1。函數(shù)返回地址壓棧。2。在棧中，為函數(shù)返回類型、函數(shù)參數(shù)分配空間3。將實參傳遞給形參(根據(jù)不同傳遞方式，采用不同處理)。4。在棧中，為局部(自動、寄存器)變量分配空間。5。執(zhí)行函數(shù)。6。函數(shù)執(zhí)行結(jié)束時。程序從棧中取出返回值，程序轉(zhuǎn)至函數(shù)返回地址處執(zhí)行，同時廢棄棧中為返回類型、函數(shù)參數(shù)、局部變量分配的空間。通過本節(jié)后面Hanoi塔問題分析可加深對函數(shù)調(diào)用包括遞歸調(diào)用的理解。計算機學(xué)院李衛(wèi)明典型的Hanoi塔問題假設(shè)有三個命名為A、B、C的塔柱，初始時，在塔柱A上插有n個直徑大小各不相同的圓盤，從上往下，圓盤從小到大編號為1、2、3、···n，要求將A柱上的圓盤移至塔柱C。圓盤移動必須遵守下列規(guī)則：1：每次只能移動一個圓盤；2：圓盤可以插在任意一個塔柱上；3：任何時刻都不能將一個較大的圓盤放在一個較小的圓盤上。我們可以用分治法分析解決這一問題。對于具有n個圓盤的Hanoi塔問題，形參x、y、z代表三個塔柱。處理思路如下：n等于1時只需將圓盤從x柱移至z柱即可；n大于1時，我們分三步完成：1：借助z塔柱，將x塔柱上的n-1個圓盤按照規(guī)定移至到y(tǒng)塔柱；2：將x塔柱上的一個圓盤由x柱移至z柱；3：借助x塔柱，將y塔柱上的n-1個圓盤按規(guī)定移至到z塔柱；計算機學(xué)院李衛(wèi)明Hanoi塔問題完整代碼如下：//Ex1.21#include<iostream>2usingnamespacestd;3//將n個盤子從x柱搬至z柱，可借助y柱

4voidHanoi(intn,charx,chary,charz);56intmain()7{intn;//盤子數(shù)量

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}計算機學(xué)院李衛(wèi)明EX1.2運行輸入3時運行棧變化分析，可調(diào)試驗證：計算機學(xué)院李衛(wèi)明

1.7引用引用是C++引入的重要機制，廣泛應(yīng)用在函數(shù)間參數(shù)傳遞、函數(shù)返回值和運算符重載中簡單的說，引用就是別名，代表被引用的對象或變量。計算機學(xué)院李衛(wèi)明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計算機學(xué)院李衛(wèi)明參數(shù)傳遞和引用C++增加“引用”的主要目的是利用它作為函數(shù)參數(shù)和返回值，以便擴充函數(shù)傳遞數(shù)據(jù)的功能。在C語言中，參數(shù)傳遞主要采用采用傳值方式。這時形參和實參不是同一個存儲單元，函數(shù)調(diào)用時將實參（變量的值）傳遞給形參，傳遞是單向的，在執(zhí)行函數(shù)期間形參值發(fā)生變化并不傳回給實參。如果需要改變另一函數(shù)中變量的值，C語言函數(shù)調(diào)用需要中通過指針來間接改變所指變量值，使用不太直觀、方便。（C數(shù)組傳遞實際是特殊情況，數(shù)組名即地址，類似指針）。C++中增加了參數(shù)引用傳遞方式，形參就是實參別名，形參變化即實參變化。計算機學(xué)院李衛(wèi)明例以變量為實參不能實現(xiàn)交換變量的值的。voidSwap(inta,intb) //不能實現(xiàn)交換實參變量的值{ intt=a;a=b;b=t; //循環(huán)賦值交換a,b的值}intmain() //主函數(shù)main(){ intm=6,n=8; //定義整型變量

Swap(m,n); //調(diào)用函數(shù)Swap() cout<<m<<""<<n<<endl; //輸出m,n的值}計算機學(xué)院李衛(wèi)明在C程序中可以用指針傳遞變量地址的方法。使形參得到一個變量的地址，這時形參指針變量指向?qū)崊⒆兞繂卧＠弥羔樧兞孔餍螀?，實現(xiàn)兩個變量的值互換。voidSwap(int*p,int*q) //實現(xiàn)交換*p與*q的值{ intt=*p;*p=*q;*q=t; //循環(huán)賦值交換*p與*q的值}intmain() //主函數(shù)main(){ intm=6,n=8; //定義整型變量

Swap(&m,&n); //調(diào)用函數(shù)Swap() cout<<m<<""<<n<<endl; //輸出m,n的值}計算機學(xué)院李衛(wèi)明在C++中，把變量的引用作為函數(shù)形參，由于形參是實參的引用，也就是形參是實參的別名，這樣對形參的操作等價于對實參的操作。例利用引用形參實現(xiàn)交換兩個變量的值。voidSwap(int&a,int&b) //實現(xiàn)交換實參變量的值{ intt=a;a=b;b=t; //循環(huán)賦值交換a與b的值}intmain() //主函數(shù)main(){ intm=6,n=8; //定義整型變量

Swap(m,n); //調(diào)用函數(shù)Swap() cout<<m<<""<<n<<endl; //輸出m,n的值}計算機學(xué)院李衛(wèi)明常引用常引用就是用const對引用加以限定，表示不允許改變該引用的值。例如：inta=6; //定義整型變量a，初值為6constint&b=a; //聲明常引用，不允許改變b的值b=8; //改變常引用b的值，錯誤a=8; //改變a的值，正確常引用通常用作函數(shù)形參，這樣能保證形參的值不被改變，又可提高大對象參數(shù)傳遞效率。計算機學(xué)院李衛(wèi)明例常引用形參示例。structPerson{ charname[20]; //姓名

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

cout<<"性別:"<<p.sex<<endl; //輸出性別}intmain() //主函數(shù)main(){ Personp={"李倩","女"}; //定義結(jié)構(gòu)體變量

Show(p); //輸出p}在程序中，用結(jié)構(gòu)名Person作為類型來定義變量p，在C語言中，不能用結(jié)構(gòu)名來定義結(jié)構(gòu)變量名，必須在結(jié)構(gòu)名前加struct才能定義結(jié)構(gòu)變量，即應(yīng)采用如下形式定義：struct Personp={"李倩","女"};//定義結(jié)構(gòu)體變量計算機學(xué)院李衛(wèi)明1.8動態(tài)分配和釋放C語言內(nèi)存申請主要通過malloc庫函數(shù)進行，對應(yīng)的釋放內(nèi)存庫函數(shù)是free，純粹用于內(nèi)存分配和釋放。作為面向?qū)ο蟮某绦蛟O(shè)計語言，C++不僅需要動態(tài)分配內(nèi)存，還需要在分配的內(nèi)存上建立對象，完成對象的初始化，釋放時也需要先執(zhí)行對象所需的掃尾處理，然后再歸還空間，因此，C語言時代的malloc、free庫函數(shù)已不能滿足這一要求，C++為了兼容面向過程的C語言程序，保留了這一申請方法。類類型的對象初始化時會自動執(zhí)行構(gòu)造函數(shù)，對象撤銷時會自動執(zhí)行析構(gòu)函數(shù)完成掃尾處理，關(guān)于對象的構(gòu)造函數(shù)和析構(gòu)函數(shù)，參見第2章。C++內(nèi)存申請和釋放主要通過new、delete運算符進行。主要方式有：動態(tài)生成單個對象和動態(tài)生成連續(xù)存放的對象數(shù)組，動態(tài)生成的對象存放在堆中。計算機學(xué)院李衛(wèi)明T*p=newT;T*p=newT(初始化實參表);T*p=newT{初始化實參表};T*p=newT[n];上述語句中，T代表類型名，可以是內(nèi)置數(shù)據(jù)類型、類類型或指向類型的指針型。p是指向T類型的指針變量，用來管理所指對象。前3個語句用于動態(tài)生成單個對象，后一個語句用于動態(tài)生成連續(xù)存放的n個對象，構(gòu)成動態(tài)對象數(shù)組，n可以是運行時確定大小的變量或表達式。生成對象成功時返回一個非空指針，程序內(nèi)部先完成存儲空間分配，再在動態(tài)分配的空間上完成單個對象或連續(xù)多個對象的初始化。如果申請失敗，C++編譯器和開發(fā)工具有2種處理方案：一種是返回空指針，再加以判斷處理；另一種是拋出異常，再按異常機制統(tǒng)一處理。拋出異常時，后續(xù)語句不再正常執(zhí)行。關(guān)于異常處理，請參見第7章?，F(xiàn)代C++程序主要采用第2種申請失敗處理方案，具體信息可查閱編譯器和開發(fā)工具，本講義樣例均采用異常處理方案。計算機學(xué)院李衛(wèi)明注意，這里p是指針型變量，與所管理的匿名對象是相互獨立存在的。函數(shù)執(zhí)行完畢，局部指針變量p撤銷時，p所指匿名對象并未撤銷，所指對象不再需要時，應(yīng)該顯式使用delete刪除p所指對象。刪除語句如下：deletep;delete[]p;刪除p所指對象或?qū)ο髷?shù)組時，指針變量p本身并未消失。前者用于刪除new動態(tài)生成的單個對象，后者用于刪除數(shù)組方式new動態(tài)生成的連續(xù)多個對象，刪除時先完成每個對象的掃尾處理（自動調(diào)用析構(gòu)函數(shù)），再釋放對象內(nèi)存空間。delete所用指針值必須是相應(yīng)new申請得到的指針值或空指針，否則，結(jié)果不確定。new申請得到的對象在刪除后不可再使用，也不可重復(fù)釋放，否則，結(jié)果同樣不確定。刪除空指針并無不妥，可以正確執(zhí)行。計算機學(xué)院李衛(wèi)明例new/delete運算符使用示例。intmain() //主函數(shù)main(){ int*p; //定義整型指針

p=newint(16); //分配單個整數(shù)的存儲空間,并初始化為16 if(p==NULL) { cout<<"分配存儲空間失敗!"<<endl; exit(1); //退出程序的運行,并向操作系統(tǒng)返回1 } cout<<*p<<endl; //輸出p所指向的動態(tài)存儲空間的值16 deletep; //釋放存儲空間

p=newint; //分配單個整數(shù)的存儲空間

if(p==NULL) { cout<<"分配存儲空間失敗!"<<endl; exit(2); //退出程序的運行,并向操作系統(tǒng)返回2 } *p=8; //將p指向的動態(tài)存儲空間賦值為8 cout<<*p<<endl; //輸出p所指向的動態(tài)存儲空間的值8

……計算機學(xué)院李衛(wèi)明例new/delete運算符使用示例。intmain() //主函數(shù)main(){

……

p=newint[8]; //分配整型數(shù)組存儲空間

if(p==NULL) { cout<<"分配存儲空間失敗!"<<endl; exit(3); //退出程序的運行,并向操作系統(tǒng)返回3 } inti; //定義整型變量

for(i=0;i<8;i++) p[i]=i; //為數(shù)組賦元素值

for(i=0;i<8;i++) cout<<p[i]<<""; //輸出數(shù)組元素值01234567 cout<<endl; //換行

delete[]p; //釋放存儲空間}計算機學(xué)院李衛(wèi)明下述語句分別申請動態(tài)分配1個整形、1個初始化為10的整形、n個連續(xù)整形、一個字符串對象和n個字符串對象，并分別預(yù)以釋放。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;計算機學(xué)院李衛(wèi)明典型范例——順時針旋轉(zhuǎn)矩陣編寫程序，讀入正整數(shù)n，輸出順時針分布的矩陣。矩陣內(nèi)容為順時針順序存放的n*n個數(shù)1、2、3、...n*n。樣例輸入：7樣例輸出：19202122232411837383940252173647484126316354649422741534454443285143332313029613121110987計算機學(xué)院李衛(wèi)明解決這一問題，可按自頂向下、逐步分解的結(jié)構(gòu)化程序設(shè)計思路，分解細化成如下算法步驟：Step1.輸入n，建立n*n的矩陣，矩陣元素初始化為0；Step2.填充矩陣內(nèi)容為順時針順序存放的n*n個數(shù)1、2、3、。。。n*n；2.1確定初始填充位置(iRow,iCol)和方向dir；2.2k=1ton*n循環(huán)完成k填充和調(diào)整；2.2.1當(dāng)前位置填充k；2.2.2根據(jù)當(dāng)前方向分4種情況，更新下步填充位置；Step3.輸出矩陣。樣例實現(xiàn)：1.使用數(shù)組版本/p/RTT4RHFtGR/2.使用動態(tài)分配版本(傳統(tǒng)版,推薦)/p/Hnn7Mt2J6h/3.使用**版本(不推薦使用)/p/BnJbZFykSw/4.使用vector版本(STL版,推薦)/p/7YTPhtJM8C/計算機學(xué)院李衛(wèi)明習(xí)題：編寫程序，打印出N階魔陣（N個奇數(shù)），要求使用動態(tài)分配。如輸入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計算機學(xué)院李衛(wèi)明1.9鏈表處理鏈表處理的基礎(chǔ)是單鏈表，從單鏈表處理可推廣到多鏈表處理和其它鏈表處理，本講義涉及的內(nèi)容基本限于單鏈表。線性關(guān)系的若干元素組成線性表，單鏈表可用來表示鏈表中所有結(jié)點內(nèi)元素以及結(jié)點間的線性關(guān)系，也就是線性表。圖1.2

單鏈表結(jié)點和單鏈表示例

1.9.1鏈表基礎(chǔ)

圖1.2a所示，鏈表中的結(jié)點一般由表示元素的數(shù)據(jù)域和表示下個結(jié)點的指針域2部分組成，指針域為空指針時表示無后續(xù)結(jié)點。

傳統(tǒng)C/C++使用值定義為0的NULL表示空指針，C++11引入專門nullptr表示空指針，圖中符號^代表空指針(nullptr)，本講義中有關(guān)單鏈表的其它圖示也一樣。

結(jié)點數(shù)據(jù)類型一般定義如下，T代表具體應(yīng)用中所需數(shù)據(jù)類型，實際應(yīng)用中可確定具體數(shù)據(jù)類型，本節(jié)其它討論中出現(xiàn)的類型T也一樣。structNode{Tdata;Node*next;};圖1.2b表示元素類型為字符串、無頭結(jié)點的單鏈表，用于表示線性表（zhao,zhang,wang,sun,li），此處省略了字符串的雙引號，T就是std::string類型；圖1.2c表示元素類型為整型、帶頭結(jié)點的單鏈表，表示線性表（1,5,7,9），此處T就是int類型。整個單鏈表可通過類型為Node*的指針變量la1、la2訪問和管理。注意，指針變量p和p所指結(jié)點是獨立存在的，通過指針變量p可訪問結(jié)點的數(shù)據(jù)域p->data和指針域p->next，這些表示既可作為右值出現(xiàn)在賦值運算符右邊表達式，也可作為左值出現(xiàn)在賦值類運算符左邊。鏈表中插入元素時，需要在鏈表中增加結(jié)點，所需結(jié)點可以用下述語句動態(tài)分配：Node*p;p=newNode;下列語句將p所指結(jié)點插入q所指結(jié)點后:p->next=q->next;//p后續(xù)結(jié)點設(shè)為原q后續(xù)結(jié)點q->next=p;//q后續(xù)結(jié)點設(shè)為p需要注意，一般情況下，鏈表增加結(jié)點時，結(jié)點需要動態(tài)分配。不可把局部變量或全局變量代表的結(jié)點作為普通結(jié)點鏈入鏈表中，否則，函數(shù)執(zhí)行完畢，局部結(jié)點會自動消失，全局變量代表的結(jié)點則可能多次鏈入，造成鏈表混亂。鏈表需要仔細構(gòu)建，程序訪問鏈表結(jié)點時，需要確保訪問內(nèi)存單元可訪問權(quán)，如果訪問到無權(quán)訪問內(nèi)存，程序很可能崩潰。如果從鏈表中刪除結(jié)點時，需要修改鏈表，并且最后刪除指針?biāo)附Y(jié)點，釋放結(jié)點占有的存儲空間，否則造成內(nèi)存泄漏。除非刪除的結(jié)點是鏈表的第一個結(jié)點，刪除結(jié)點一般需要修改被刪除結(jié)點的前一個結(jié)點的指針域。刪除指針變量q所指結(jié)點的后一個結(jié)點一般需要執(zhí)行下述語句：Node*t;t=q->next;//記住被刪結(jié)點指針q->next=t->next;//修改鏈表,設(shè)q后續(xù)結(jié)點為原t后續(xù)結(jié)點deletet;//刪除結(jié)點注意，最后一個語句刪除t所指結(jié)點，指針變量t還是存在的，但刪除后程序無權(quán)訪問t所指結(jié)點，否則，可能造成結(jié)果錯誤或程序崩潰。正是由于單鏈表插入和刪除結(jié)點時需要修改前一個結(jié)點的指針域，一般情況下，為簡化算法，涉及不同位置插入和刪除的單鏈表應(yīng)用中鏈表一般帶有頭結(jié)點，頭結(jié)點數(shù)據(jù)域信息可以廢棄，特殊應(yīng)用除外。常見的指針操作及其示意圖//后續(xù)章節(jié)使用更簡潔的new和deleteLinkNode*p;

p=(LinkNode*)malloc(sizeof(LinkNode));p->data=20;p->next=NULL;申請結(jié)點20^pq=p;？20qpq=p->next;qp………20…操作前操作后操作？p？qp…2030…qp…2030…常見的指針操作及其示意圖

操作前操作后操作p=p->next;p…2030…p…2030…q->next=p;q…2030…q…2030…p20p20常見的指針操作及其示意圖

操作操作前操作后q->next=p->next;q…2030…q…2030…p10p106…6…單鏈表初始化(為便于表述，后續(xù)單鏈表一般都帶頭結(jié)點）調(diào)用舉例：LinkNode*head;

CreateList(&head);//構(gòu)造一個帶表頭結(jié)點的空單鏈表StatusCreateList(LinkNode**pLa)//后續(xù)章節(jié)使用更簡潔的*&表示{p=(LinkNode*)malloc(sizeof(LinkNode));if(p==NULL) returnfalse;p->next=NULL;*pLa=p;returnOK;}

單鏈表結(jié)構(gòu)的銷毀voidDestory(LinkNode*la)//銷毀以后不可再使用，因此無需傳回，后同{Clear(la);//釋放所有的數(shù)據(jù)結(jié)點

free(la);//釋放頭結(jié)點}

單鏈表清空//釋放單鏈表中的所有數(shù)據(jù)結(jié)點voidClear(LinkList*head)//頭結(jié)點不變，因此無需傳回{p=head->next;while(p){q=p->next;

deletep;p=q;}head->next=NULL;}生成新結(jié)點q，并插入p之后?q=(LinkNode*)malloc(sizeof(LinkNode));if(!q) returnfalse;//內(nèi)存不足

q->data=e;?q->next=p->next;?p->next=q;

??ai-1aie

pq?刪除結(jié)點的基本操作?q=p->next;?p->next=q->next;?*e=q->data;free(q);

?ai-1aiai+1pq??1.9.2典型范例——單鏈表構(gòu)造、插入、顯示、銷毀編寫程序，建立空單鏈表，先輸入正整數(shù)個數(shù)，再輸入指定個數(shù)的正整數(shù)，將這些正整數(shù)按非遞減（相等或遞增）順序插入單鏈表，最后打印單鏈表。本題單鏈表插入、打印、銷毀用獨立函數(shù)完成。本題是采用結(jié)構(gòu)化程序設(shè)計進行鏈表處理的典型案例，使用模塊化方式實現(xiàn)了單鏈表插入、顯示、銷毀3個算法函數(shù)。其中，單鏈表插入函數(shù)完成在帶頭結(jié)點有序單鏈表中插入新元素結(jié)點，插入前后單鏈表中元素均保持有序，適用于包括空線性表在內(nèi)的所有非遞減線性表；顯示函數(shù)完成單鏈表中元素的顯示；銷毀函數(shù)完成單鏈表中所有結(jié)點的釋放，避免造成內(nèi)存泄漏。樣例輸入586257樣例輸出2->5->6->7->8完整樣例代碼EX1.5：/p/dFBtYwQSbS/計算機學(xué)院李衛(wèi)明作業(yè)：1.用程序求解約瑟夫問題。設(shè)有N個人（他們的編號分別為1～N）坐在圓桌周圍，從第S個人開始報數(shù)，報到M的人出列，然后再從下一人開始報數(shù)，報到M的人出列，如此重復(fù)，直到所有的人都出列為止。按出列的先后輸出一個人的編號。2.編寫程序，將自然數(shù)1，2，～

N*N按蛇形方式逐個順序存入N×N矩陣。如N＝3和4時，矩陣分別為：6 79 7 13 14 162 58 6 8 12 151 34 2 5 9 11

1 3 4 103.編寫程序，將自然數(shù)1，2，～～

N*N按逆時針方向依次填寫在N×N矩陣中。如，N＝3和N＝4時，矩陣分別為:1

8

7

2

9

6

3

4

5和

1

16 15

14 13

2 17

24

23 12

3

18

25 22

11

4

19

20 21 10

5

6

7

8 9計算機學(xué)院李衛(wèi)明第2章類和對象本章主要內(nèi)容：棧和隊列簡單應(yīng)用

抽象、封裝和信息隱蔽

類聲明和類實現(xiàn)

對象數(shù)組和動態(tài)對象

常用容器使用舉例

類的嵌套定義

類類型的數(shù)據(jù)成員和has-a關(guān)系

典型范例——簡單集合類

特