第1章 C++程序設(shè)計(jì)基礎(chǔ)

C++語(yǔ)言是在C語(yǔ)言基礎(chǔ)上發(fā)展起來(lái)的主流程序設(shè)計(jì)語(yǔ)言之一，除全面兼容面向過(guò)程的程序設(shè)計(jì)語(yǔ)言C外，C++主要支持面向?qū)ο蟪绦蛟O(shè)計(jì)，還支持泛型程序設(shè)計(jì)。本章在已學(xué)習(xí)C程序設(shè)計(jì)基礎(chǔ)上，首先引入了C++語(yǔ)言，介紹作為一個(gè)更好的C，C++引入的基本輸入輸出、函數(shù)重載、內(nèi)聯(lián)函數(shù)、引用等C++語(yǔ)言的重要機(jī)制，介紹了對(duì)象作用域和生存期、函數(shù)調(diào)用實(shí)現(xiàn)過(guò)程、動(dòng)態(tài)分配、鏈表處理等程序設(shè)計(jì)的重要基礎(chǔ)知識(shí)，最后，介紹了順時(shí)針旋轉(zhuǎn)矩陣、單鏈表操作典型案例。計(jì)算機(jī)學(xué)院李衛(wèi)明第一章C++程序設(shè)計(jì)基礎(chǔ)本章主要內(nèi)容：1.1C++概述1.1.1C++簡(jiǎn)介 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)用實(shí)現(xiàn)

1.7引用

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

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

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

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

#include<iostream>//編譯預(yù)處理命令盡管目前很多編譯器還支持帶后綴.h的頭文件，C++標(biāo)準(zhǔn)推薦頭文件名不帶后綴.h，使用時(shí)只需將原C語(yǔ)言形式頭文件名前面加字母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)庫(kù)名字基本定義在std名字空間內(nèi)。如果在樣例中語(yǔ)句2后插入下列語(yǔ)句：usingnamespacestd;

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

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

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

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

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

變量;類型

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

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

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

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

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

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

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

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

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

charname[16]; //姓名

intage; //年齡

cin>>name; //輸入姓名

cin>>age; //輸入年齡

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

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

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

布爾類型布爾類型bool是ISO/ANSI（國(guó)際標(biāo)準(zhǔn)化組織／美國(guó)國(guó)家標(biāo)準(zhǔn)化組織）最近增補(bǔ)到C++語(yǔ)言中的。布爾變量包含兩種取值：true或false。如果在表達(dá)式中使用布爾變量，它將把自身取值的true或false分別轉(zhuǎn)換為1或0。如果將數(shù)值轉(zhuǎn)換為布爾類型，如數(shù)值是零，布爾變量為false；如數(shù)值是非零值，布爾變量就為true。VS2013基本(內(nèi)置)類型的相對(duì)大小圖示:計(jì)算機(jī)學(xué)院李衛(wèi)明例編寫(xiě)判斷一個(gè)整型是否為質(zhì)數(shù)的函數(shù)，并用此函數(shù)輸出1~100之間的質(zhì)數(shù)，要求編寫(xiě)測(cè)試程序。一個(gè)整型n如果大于1，并且不能被2~n-1之間的整數(shù)所整除，那么n為質(zhì)數(shù)，由質(zhì)數(shù)的定義很容易實(shí)現(xiàn)判斷一個(gè)整型是否為質(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)}程序運(yùn)行時(shí)屏幕輸出如下：2357111317192329313741434753596167717379838997請(qǐng)按任意鍵繼續(xù)...計(jì)算機(jī)學(xué)院李衛(wèi)明1.2函數(shù)重載C++允許在同一作用域內(nèi)定義多個(gè)同名函數(shù)，但要求這些函數(shù)參數(shù)的類型或個(gè)數(shù)不相同。這個(gè)功能稱為函數(shù)重載，是一種參數(shù)性多態(tài)。在同一個(gè)作用域內(nèi)，函數(shù)名相同，參數(shù)的類型或個(gè)數(shù)不同的函數(shù)稱為重載函數(shù)。重載函數(shù)的形參個(gè)數(shù)或類型必須至少有其中之一不同，不允許參數(shù)個(gè)數(shù)和類型都相同而只有返回值類型不同，這是由于系統(tǒng)無(wú)法從函數(shù)的調(diào)用形式判斷與哪一個(gè)重載函數(shù)相匹配。例:intMax(inta,intb);floatMax(floata,floatb);doubleMax(doublea,doubleb);計(jì)算機(jī)學(xué)院李衛(wèi)明例求2個(gè)數(shù)中最小值（分別考慮整數(shù)、浮點(diǎn)數(shù)的情況）。intMin(inta,intb) //求2個(gè)整數(shù)的最小值{ returna<b?a:b; //返回a,b的最小值 }floatMin(floata,floatb) //求2個(gè)浮點(diǎn)數(shù)的最小值{ returna<b?a:b; //返回a,b的最小值 }intmain() //主函數(shù)main(){ inta,b; //定義整型變量

floatx,y; //定義浮點(diǎn)型變量

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

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

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

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

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

floatVolume(floatl=10.0,floatw=8.0,floath=6.0);//正確 對(duì)于上面正確的函數(shù)聲明，可采用如下形式的函數(shù)調(diào)用：v=Volume(10.1,8.2,6.8); //形參值全從實(shí)參得到,l=10.1,w=8.2,h=6.8v=Volume(10.1,8.2); //最后1個(gè)形參的值取默認(rèn)值,l=10.1,w=8.2,h=6.0v=Volume(10.1); //最后2個(gè)形參的值取默認(rèn)值,l=10.1,w=8.0,h=6.0v=Volume(); //形參的值全取默認(rèn)值,l=10.0,w=8.0,h=6.0計(jì)算機(jī)學(xué)院李衛(wèi)明例函數(shù)默認(rèn)參數(shù)示例。voidShow(charstr1[],charstr2[]="",charstr3[]=""); //在聲明函數(shù)時(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}計(jì)算機(jī)學(xué)院李衛(wèi)明1.5變量(對(duì)象)作用域和生存期C++用標(biāo)識(shí)符命名對(duì)象、函數(shù)和類型、類成員、類模板等，標(biāo)識(shí)符作用域指通過(guò)該名字可以直接訪問(wèn)使用的范圍。C++名字作用域從小到大依次有：復(fù)合語(yǔ)句作用域和函數(shù)原型作用域、函數(shù)作用域、類作用域、名字空間作用域和文件作用域。對(duì)象的生存期代表程序運(yùn)行時(shí)，對(duì)象從建立到消失的時(shí)間周期。作用域和生存期，兩者是不同的概念，也存在一定的關(guān)聯(lián)性計(jì)算機(jī)學(xué)院李衛(wèi)明聲明在函數(shù)原型里的形式參數(shù)名字，只在該函數(shù)聲明內(nèi)有效，作用域是該函數(shù)聲明，函數(shù)聲明內(nèi)的形參名字也因而可以省略。聲明或定義在復(fù)合語(yǔ)句內(nèi)的名字，作用域只是該復(fù)合語(yǔ)句，作為對(duì)象名字時(shí)，相應(yīng)對(duì)象稱為局部對(duì)象，程序在開(kāi)始執(zhí)行該局部對(duì)象所在復(fù)合語(yǔ)句時(shí)在運(yùn)行棧上建立局部對(duì)象，執(zhí)行完局部對(duì)象所在復(fù)合語(yǔ)句離開(kāi)時(shí)撤銷局部對(duì)象。同樣地，聲明或定義在函數(shù)體內(nèi)的名字，作用域只是該函數(shù)體，作為對(duì)象名字時(shí)，相應(yīng)對(duì)象也是局部對(duì)象，程序在開(kāi)始執(zhí)行該局部對(duì)象所在函數(shù)體時(shí)在運(yùn)行棧上建立局部對(duì)象，執(zhí)行完函數(shù)體離開(kāi)時(shí)撤銷局部對(duì)象。函數(shù)定義時(shí)的形參作用域就是該函數(shù)定義，形參對(duì)象也是局部對(duì)象，程序在開(kāi)始執(zhí)行該局部對(duì)象所在函數(shù)時(shí)在運(yùn)行棧上建立局部對(duì)象，執(zhí)行完函數(shù)離開(kāi)時(shí)撤銷局部對(duì)象。定義在類外和函數(shù)外，但在名字空間里的標(biāo)識(shí)符，具有該名字空間作用域，定義在名字空間里的對(duì)象在程序開(kāi)始執(zhí)行時(shí)在全局對(duì)象和靜態(tài)對(duì)象專用存儲(chǔ)區(qū)上建立，程序執(zhí)行結(jié)束時(shí)撤銷。定義在類外和函數(shù)外，不在名字空間內(nèi)的對(duì)象是外部對(duì)象，作用域限定在定義開(kāi)始到該文件結(jié)束，程序在開(kāi)始執(zhí)行時(shí)在全局對(duì)象和靜態(tài)對(duì)象專用存儲(chǔ)區(qū)上建立外部對(duì)象，執(zhí)行結(jié)束時(shí)撤銷外部對(duì)象。計(jì)算機(jī)學(xué)院李衛(wèi)明帶extern修飾的外部對(duì)象，代表本文件或其它文件定義的同名外部對(duì)象，作用域限定在該文件內(nèi)。帶static修飾的外部靜態(tài)對(duì)象與普通外部對(duì)象生存期相同，作用域限定在該文件內(nèi)，其它文件不可引用該外部靜態(tài)對(duì)象。帶static修飾的局部靜態(tài)對(duì)象與普通局部對(duì)象作用域相同，限定局部范圍內(nèi)，在程序第一次執(zhí)行到該靜態(tài)對(duì)象定義語(yǔ)句時(shí)在全局對(duì)象和靜態(tài)對(duì)象專用存儲(chǔ)區(qū)上建立，程序執(zhí)行完結(jié)束時(shí)撤銷。定義在不同作用域中的標(biāo)識(shí)符名字相同時(shí)根據(jù)最小作用域原則確定標(biāo)識(shí)符代表的對(duì)象、函數(shù)、類型等。動(dòng)態(tài)分配生成的對(duì)象是匿名對(duì)象，通過(guò)指針間接訪問(wèn)，在new動(dòng)態(tài)分配時(shí)在堆空間生成，在delete刪除操作時(shí)撤銷，沒(méi)有執(zhí)行delete刪除所指對(duì)象時(shí)，會(huì)造成對(duì)象所占內(nèi)存空間資源泄漏，影響程序執(zhí)行所需內(nèi)存資源，詳見(jiàn)本章第8、9節(jié)。關(guān)于類成員作用域和成員生存期在第2章在講述。計(jì)算機(jī)學(xué)院李衛(wèi)明變量(對(duì)象)作用域和生存期小結(jié)對(duì)象(變量)生存期是指自對(duì)象生成至消失的時(shí)間段；由C++存儲(chǔ)類修飾符auto、register、static 、extern指示；對(duì)象（變量）作用域指變量(對(duì)象)名稱有效使用范圍。C++變量(對(duì)象)作用域 生存期 修飾符

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

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

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

8cin>>n;9Hanoi(n,'A','B','C');10}11//將n個(gè)盤(pán)子從x柱搬至z柱，可借助y柱

12voidHanoi(intn,charx,chary,charz)13{14if(n==1){15cout<<x<<"->"<<z<<endl;//一個(gè)盤(pán)子時(shí)可直接搬動(dòng)

16}else{17Hanoi(n-1,x,z,y);//將n-1個(gè)盤(pán)子從x柱搬至y柱，借助z柱

18cout<<x<<"->"<<z<<endl;//剩余一個(gè)盤(pán)子時(shí)可直接搬動(dòng)

19Hanoi(n-1,y,x,z);//將n-1個(gè)盤(pán)子從y柱搬至z柱，借助x柱

20}21}計(jì)算機(jī)學(xué)院李衛(wèi)明EX1.2運(yùn)行輸入3時(shí)運(yùn)行棧變化分析，可調(diào)試驗(yàn)證：計(jì)算機(jī)學(xué)院李衛(wèi)明

1.7引用引用是C++引入的重要機(jī)制，廣泛應(yīng)用在函數(shù)間參數(shù)傳遞、函數(shù)返回值和運(yùn)算符重載中簡(jiǎn)單的說(shuō)，引用就是別名，代表被引用的對(duì)象或變量。計(jì)算機(jī)學(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;//報(bào)錯(cuò)，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;//報(bào)錯(cuò)，rj是常量引用，不可修改rj計(jì)算機(jī)學(xué)院李衛(wèi)明參數(shù)傳遞和引用C++增加“引用”的主要目的是利用它作為函數(shù)參數(shù)和返回值，以便擴(kuò)充函數(shù)傳遞數(shù)據(jù)的功能。在C語(yǔ)言中，參數(shù)傳遞主要采用采用傳值方式。這時(shí)形參和實(shí)參不是同一個(gè)存儲(chǔ)單元，函數(shù)調(diào)用時(shí)將實(shí)參（變量的值）傳遞給形參，傳遞是單向的，在執(zhí)行函數(shù)期間形參值發(fā)生變化并不傳回給實(shí)參。如果需要改變另一函數(shù)中變量的值，C語(yǔ)言函數(shù)調(diào)用需要中通過(guò)指針來(lái)間接改變所指變量值，使用不太直觀、方便。（C數(shù)組傳遞實(shí)際是特殊情況，數(shù)組名即地址，類似指針）。C++中增加了參數(shù)引用傳遞方式，形參就是實(shí)參別名，形參變化即實(shí)參變化。計(jì)算機(jī)學(xué)院李衛(wèi)明例以變量為實(shí)參不能實(shí)現(xiàn)交換變量的值的。voidSwap(inta,intb) //不能實(shí)現(xiàn)交換實(shí)參變量的值{ 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的值}計(jì)算機(jī)學(xué)院李衛(wèi)明在C程序中可以用指針傳遞變量地址的方法。使形參得到一個(gè)變量的地址，這時(shí)形參指針變量指向?qū)崊⒆兞繂卧?。例用指針變量作形參，?shí)現(xiàn)兩個(gè)變量的值互換。voidSwap(int*p,int*q) //實(shí)現(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的值}計(jì)算機(jī)學(xué)院李衛(wèi)明在C++中，把變量的引用作為函數(shù)形參，由于形參是實(shí)參的引用，也就是形參是實(shí)參的別名，這樣對(duì)形參的操作等價(jià)于對(duì)實(shí)參的操作。例利用引用形參實(shí)現(xiàn)交換兩個(gè)變量的值。voidSwap(int&a,int&b) //實(shí)現(xiàn)交換實(shí)參變量的值{ 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的值}計(jì)算機(jī)學(xué)院李衛(wèi)明常引用常引用就是用const對(duì)引用加以限定，表示不允許改變?cè)撘玫闹?。例如：inta=6; //定義整型變量a，初值為6constint&b=a; //聲明常引用，不允許改變b的值b=8; //改變常引用b的值，錯(cuò)誤a=8; //改變a的值，正確常引用通常用作函數(shù)形參，這樣能保證形參的值不被改變，又可提高大對(duì)象參數(shù)傳遞效率。計(jì)算機(jī)學(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作為類型來(lái)定義變量p，在C語(yǔ)言中，不能用結(jié)構(gòu)名來(lái)定義結(jié)構(gòu)變量名，必須在結(jié)構(gòu)名前加struct才能定義結(jié)構(gòu)變量，即應(yīng)采用如下形式定義：struct Personp={"李倩","女"};//定義結(jié)構(gòu)體變量計(jì)算機(jī)學(xué)院李衛(wèi)明1.8動(dòng)態(tài)分配和釋放C語(yǔ)言內(nèi)存申請(qǐng)主要通過(guò)malloc庫(kù)函數(shù)進(jìn)行，對(duì)應(yīng)的釋放內(nèi)存庫(kù)函數(shù)是free，純粹用于內(nèi)存分配和釋放。作為面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言，C++不僅需要?jiǎng)討B(tài)分配內(nèi)存，還需要在分配的內(nèi)存上建立對(duì)象，完成對(duì)象的初始化，釋放時(shí)也需要先執(zhí)行對(duì)象所需的掃尾處理，然后再歸還空間，因此，C語(yǔ)言時(shí)代的malloc、free庫(kù)函數(shù)已不能滿足這一要求，C++為了兼容面向過(guò)程的C語(yǔ)言程序，保留了這一申請(qǐng)方法。類類型的對(duì)象初始化時(shí)會(huì)自動(dòng)執(zhí)行構(gòu)造函數(shù)，對(duì)象撤銷時(shí)會(huì)自動(dòng)執(zhí)行析構(gòu)函數(shù)完成掃尾處理，關(guān)于對(duì)象的構(gòu)造函數(shù)和析構(gòu)函數(shù)，參見(jiàn)第2章。C++內(nèi)存申請(qǐng)和釋放主要通過(guò)new、delete運(yùn)算符進(jìn)行。主要方式有：動(dòng)態(tài)生成單個(gè)對(duì)象和動(dòng)態(tài)生成連續(xù)存放的對(duì)象數(shù)組，動(dòng)態(tài)生成的對(duì)象存放在堆中。計(jì)算機(jī)學(xué)院李衛(wèi)明T*p=newT;T*p=newT(初始化實(shí)參表);T*p=newT{初始化實(shí)參表};T*p=newT[n];上述語(yǔ)句中，T代表類型名，可以是內(nèi)置數(shù)據(jù)類型、類類型或指向類型的指針型。p是指向T類型的指針變量，用來(lái)管理所指對(duì)象。前3個(gè)語(yǔ)句用于動(dòng)態(tài)生成單個(gè)對(duì)象，后一個(gè)語(yǔ)句用于動(dòng)態(tài)生成連續(xù)存放的n個(gè)對(duì)象，構(gòu)成動(dòng)態(tài)對(duì)象數(shù)組，n可以是運(yùn)行時(shí)確定大小的變量或表達(dá)式。生成對(duì)象成功時(shí)返回一個(gè)非空指針，程序內(nèi)部先完成存儲(chǔ)空間分配，再在動(dòng)態(tài)分配的空間上完成單個(gè)對(duì)象或連續(xù)多個(gè)對(duì)象的初始化。如果申請(qǐng)失敗，C++編譯器和開(kāi)發(fā)工具有2種處理方案：一種是返回空指針，再加以判斷處理；另一種是拋出異常，再按異常機(jī)制統(tǒng)一處理。拋出異常時(shí)，后續(xù)語(yǔ)句不再正常執(zhí)行。關(guān)于異常處理，請(qǐng)參見(jiàn)第7章?，F(xiàn)代C++程序主要采用第2種申請(qǐng)失敗處理方案，具體信息可查閱編譯器和開(kāi)發(fā)工具，本講義樣例均采用異常處理方案。計(jì)算機(jī)學(xué)院李衛(wèi)明注意，這里p是指針型變量，與所管理的匿名對(duì)象是相互獨(dú)立存在的。函數(shù)執(zhí)行完畢，局部指針變量p撤銷時(shí)，p所指匿名對(duì)象并未撤銷，所指對(duì)象不再需要時(shí)，應(yīng)該顯式使用delete刪除p所指對(duì)象。刪除語(yǔ)句如下：deletep;delete[]p;刪除p所指對(duì)象或?qū)ο髷?shù)組時(shí)，指針變量p本身并未消失。前者用于刪除new動(dòng)態(tài)生成的單個(gè)對(duì)象，后者用于刪除數(shù)組方式new動(dòng)態(tài)生成的連續(xù)多個(gè)對(duì)象，刪除時(shí)先完成每個(gè)對(duì)象的掃尾處理（自動(dòng)調(diào)用析構(gòu)函數(shù)），再釋放對(duì)象內(nèi)存空間。delete所用指針值必須是相應(yīng)new申請(qǐng)得到的指針值或空指針，否則，結(jié)果不確定。new申請(qǐng)得到的對(duì)象在刪除后不可再使用，也不可重復(fù)釋放，否則，結(jié)果同樣不確定。刪除空指針并無(wú)不妥，可以正確執(zhí)行。計(jì)算機(jī)學(xué)院李衛(wèi)明例new/delete運(yùn)算符使用示例。intmain() //主函數(shù)main(){ int*p; //定義整型指針

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

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

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

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

……

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

if(p==NULL) { cout<<"分配存儲(chǔ)空間失敗!"<<endl; exit(3); //退出程序的運(yùn)行,并向操作系統(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; //釋放存儲(chǔ)空間}計(jì)算機(jī)學(xué)院李衛(wèi)明下述語(yǔ)句分別申請(qǐng)動(dòng)態(tài)分配1個(gè)整形、1個(gè)初始化為10的整形、n個(gè)連續(xù)整形、一個(gè)字符串對(duì)象和n個(gè)字符串對(duì)象，并分別預(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;計(jì)算機(jī)學(xué)院李衛(wèi)明典型范例——順時(shí)針旋轉(zhuǎn)矩陣編寫(xiě)程序，讀入正整數(shù)n，輸出順時(shí)針?lè)植嫉木仃?。矩陣?nèi)容為順時(shí)針順序存放的n*n個(gè)數(shù)1、2、3、...n*n。樣例輸入：7樣例輸出：19202122232411837383940252173647484126316354649422741534454443285143332313029613121110987計(jì)算機(jī)學(xué)院李衛(wèi)明解決這一問(wèn)題，可按自頂向下、逐步分解的結(jié)構(gòu)化程序設(shè)計(jì)思路，分解細(xì)化成如下算法步驟：Step1.輸入n，建立n*n的矩陣，矩陣元素初始化為0；Step2.填充矩陣內(nèi)容為順時(shí)針順序存放的n*n個(gè)數(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.輸出矩陣。樣例實(shí)現(xiàn)：1.使用數(shù)組版本/p/RTT4RHFtGR/2.使用動(dòng)態(tài)分配版本(傳統(tǒng)版,推薦)/p/Hnn7Mt2J6h/3.使用**版本(不推薦使用)/p/BnJbZFykSw/4.使用vector版本(STL版,推薦)/p/7YTPhtJM8C/計(jì)算機(jī)學(xué)院李衛(wèi)明習(xí)題：編寫(xiě)程序，打印出N階魔陣（N個(gè)奇數(shù)），要求使用動(dòng)態(tài)分配。如輸入N＝3和5時(shí)，輸出如下：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計(jì)算機(jī)學(xué)院李衛(wèi)明1.9鏈表處理鏈表處理的基礎(chǔ)是單鏈表，從單鏈表處理可推廣到多鏈表處理和其它鏈表處理，本講義涉及的內(nèi)容基本限于單鏈表。線性關(guān)系的若干元素組成線性表，單鏈表可用來(lái)表示鏈表中所有結(jié)點(diǎn)內(nèi)元素以及結(jié)點(diǎn)間的線性關(guān)系，也就是線性表。圖1.2

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

1.9.1鏈表基礎(chǔ)

圖1.2a所示，鏈表中的結(jié)點(diǎn)一般由表示元素的數(shù)據(jù)域和表示下個(gè)結(jié)點(diǎn)的指針域2部分組成，指針域?yàn)榭罩羔槙r(shí)表示無(wú)后續(xù)結(jié)點(diǎn)。

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

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