指針和引用1.docx

從概念上講。指針從本質(zhì)上講就是存放變量地址的一個(gè)變量，在邏輯上是獨(dú)立的，它可以被改變，包括其所指向的地址的改變和其指向的地址中所存放的數(shù)據(jù)的改變。而引用是一個(gè)別名，它在邏輯上不是獨(dú)立的，它的存在具有依附性，所以引用必須在一開(kāi)始就被初始化，而且其引用的對(duì)象在其整個(gè)生命周期中是不能被改變的（自始至終只能依附于同一個(gè)變量）。在C+中，指針和引用經(jīng)常用于函數(shù)的參數(shù)傳遞，然而，指針傳遞參數(shù)和引用傳遞參數(shù)是有本質(zhì)上的不同的：指針傳遞參數(shù)本質(zhì)上是值傳遞的方式，它所傳遞的是一個(gè)地址值。值傳遞過(guò)程中，被調(diào)函數(shù)的形式參數(shù)作為被調(diào)函數(shù)的局部變量處理，即在棧中開(kāi)辟了內(nèi)存空間以存放由主調(diào)函數(shù)放進(jìn)來(lái)的實(shí)參的值，從而成為了實(shí)參的一個(gè)副本。值傳遞的特點(diǎn)是被調(diào)函數(shù)對(duì)形式參數(shù)的任何操作都是作為局部變量進(jìn)行，不會(huì)影響主調(diào)函數(shù)的實(shí)參變量的值。而在引用傳遞過(guò)程中，被調(diào)函數(shù)的形式參數(shù)雖然也作為局部變量在棧中開(kāi)辟了內(nèi)存空間，但是這時(shí)存放的是由主調(diào)函數(shù)放進(jìn)來(lái)的實(shí)參變量的地址。被調(diào)函數(shù)對(duì)形參的任何操作都被處理成間接尋址，即通過(guò)棧中存放的地址訪問(wèn)主調(diào)函數(shù)中的實(shí)參變量。正因?yàn)槿绱?，被調(diào)函數(shù)對(duì)形參做的任何操作都影響了主調(diào)函數(shù)中的實(shí)參變量。引用傳遞和指針傳遞是不同的，雖然它們都是在被調(diào)函數(shù)?？臻g上的一個(gè)局部變量，但是任何對(duì)于引用參數(shù)的處理都會(huì)通過(guò)一個(gè)間接尋址的方式操作到主調(diào)函數(shù)中的相關(guān)變量。而對(duì)于指針傳遞的參數(shù)，如果改變被調(diào)函數(shù)中的指針地址，它將影響不到主調(diào)函數(shù)的相關(guān)變量。如果想通過(guò)指針參數(shù)傳遞來(lái)改變主調(diào)函數(shù)中的相關(guān)變量，那就得使用指向指針的指針，或者指針引用。為了進(jìn)一步加深大家對(duì)指針和引用的區(qū)別，下面我從編譯的角度來(lái)闡述它們之間的區(qū)別：程序在編譯時(shí)分別將指針和引用添加到符號(hào)表上，符號(hào)表上記錄的是變量名及變量所對(duì)應(yīng)地址。指針變量在符號(hào)表上對(duì)應(yīng)的地址值為指針變量的地址值，而引用在符號(hào)表上對(duì)應(yīng)的地址值為引用對(duì)象的地址值。符號(hào)表生成后就不會(huì)再改，因此指針可以改變其指向的對(duì)象（指針變量中的值可以改），而引用對(duì)象則不能修改。最后，總結(jié)一下指針和引用的相同點(diǎn)和不同點(diǎn)：相同點(diǎn)：都是地址的概念；指針指向一塊內(nèi)存，它的內(nèi)容是所指內(nèi)存的地址；而引用則是某塊內(nèi)存的別名。不同點(diǎn)：指針是一個(gè)實(shí)體，而引用僅是個(gè)別名；引用只能在定義時(shí)被初始化一次，之后不可變；指針可變；引用“從一而終”，指針可以“見(jiàn)異思遷”；引用沒(méi)有const，指針有const，const的指針不可變；引用不能為空，指針可以為空；“sizeof引用”得到的是所指向的變量(對(duì)象)的大小，而“sizeof指針”得到的是指針本身的大?。恢羔樅鸵玫淖栽?+)運(yùn)算意義不一樣；引用是類(lèi)型安全的，而指針不是(引用比指針多了類(lèi)型檢查#include #include using namespace std;std:istream& istate_reset(std:istream& cin_pass);int main() /*int v1,v2,v3;coutEnter content:v1v2;while(!cin.eof()coutcin.get()endl;coutThe output is:v1 v2endl; /顯示1 2coutEnter the third integer:v3; /直接對(duì)cin流進(jìn)行處理，并未等待輸入coutThe output is:v3val; /重新使用恢復(fù)后的流coutAfter reset,the output is:valival,!cin_pass.eof()if(cin_pass.fail() /出現(xiàn)可恢復(fù)錯(cuò)誤std:cerrbad data,try again; /提示用戶(hù)cin_pass.clear(); /恢復(fù)流cin_pass.ignore(200, );continue; /回到循環(huán)開(kāi)始處，繼續(xù)讀入數(shù)據(jù)/讀入正常coutthe normal output is:ivalendl;cin_pass.clear();return cin_pass; /只有在輸入開(kāi)始時(shí)輸入了文件結(jié)束符，才能跳出循環(huán)，中間出現(xiàn)只會(huì)認(rèn)為是出現(xiàn)可恢復(fù)錯(cuò)誤#include #include using namespace std;std:istream* istate_reset(std:istream* cin_pass);int main() /*int v1,v2,v3;coutEnter content:v1v2;while(!cin.eof()coutcin.get()endl;coutThe output is:v1 v2endl; /顯示1 2coutEnter the third integer:v3; /直接對(duì)cin流進(jìn)行處理，并未等待輸入coutThe output is:v3val; /重新使用恢復(fù)后的流coutAfter reset,the output is:valival,!(*cin_pass).eof()if(*cin_pass).fail() /出現(xiàn)可恢復(fù)錯(cuò)誤std:cerrbad data,try again; /提示用戶(hù)(*cin_pass).clear(); /恢復(fù)流(*cin_pass).ignore(200, );continue; /回到循環(huán)開(kāi)始處，繼續(xù)讀入數(shù)據(jù)/讀入正常coutthe normal output is:ivalendl;(*cin_pass).clear();return cin_pass; /只有在輸入開(kāi)始時(shí)輸入了文件結(jié)束符，才能跳出循環(huán)，中間出現(xiàn)只會(huì)認(rèn)為是出現(xiàn)可恢復(fù)錯(cuò)誤常見(jiàn)算法時(shí)間復(fù)雜度：O(1): 表示算法的運(yùn)行時(shí)間為常量O(n): 表示該算法是線性算法O(2n): 二分查找算法O(n2): 對(duì)數(shù)組進(jìn)行排序的各種簡(jiǎn)單算法，例如直接插入排序的算法。O(n3): 做兩個(gè)n階矩陣的乘法運(yùn)算O(2n): 求具有n個(gè)元素集合的所有子集的算法O(n!): 求具有N個(gè)元素的全排列的算法優(yōu)-劣O(1)O(2n)O(n)O(n2)O(2n)時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線性階O(n)、線性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)。算法的時(shí)間復(fù)雜度（計(jì)算實(shí)例）定義：如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(mén)(n)，它是n的某一函數(shù) T(n)稱(chēng)為這一算法的“時(shí)間復(fù)雜性”。當(dāng)輸入量n逐漸加大時(shí)，時(shí)間復(fù)雜性的極限情形稱(chēng)為算法的“漸近時(shí)間復(fù)雜性”。我們常用大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說(shuō)有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n2)，它給你一個(gè)上界，但并不是上確界，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。此外，一個(gè)問(wèn)題本身也有它的復(fù)雜性，如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問(wèn)題復(fù)雜性的下界，那就稱(chēng)這樣的算法是最佳算法?！按驩記法”：在這種描述中使 用的基本參數(shù)是 n，即問(wèn)題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。這里的“O”表示量級(jí) (order)，比如說(shuō)“二分檢索是 O(logn)的”,也就是說(shuō)它需要“通過(guò)logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長(zhǎng)。這種漸進(jìn)估計(jì)對(duì)算法的理論分析和大致比較是非常有價(jià)值的，但在實(shí)踐中細(xì)節(jié)也可能造成差異。例如，一個(gè)低附加代價(jià)的O(n2)算法在n較小的情況下可能比一個(gè)高附加代價(jià)的 O(nlogn)算法運(yùn)行得更快。當(dāng)然，隨著n足夠大以后，具有較慢上升函數(shù)的算法必然工作得更快。 O(1)Temp=i;i=j;j=temp; 以上三條單個(gè)語(yǔ)句的頻度均為 1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時(shí) 間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)。 O(n2)2.1. 交換i和j的內(nèi)容 sum=0； （一次） for(i=1;i=n;i+) （n次 ） for(j=1;j=n;j+) （n2次 ） sum+； （n2次 ）解：T(n)=2n2+n+1 =O(n2)2.2. for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; 解： 語(yǔ)句1的頻度是n-1 語(yǔ)句2的頻度是(n-1)*(2n+1)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2 該程序的時(shí)間復(fù)雜度T(n)=O(n2). O(n) 2.3. a=0; b=1; for (i=1;i=n;i+) s=a+b; b=a; a=s; 解： 語(yǔ)句1的頻度：2, 語(yǔ)句2的頻度： n, 語(yǔ)句3的頻度： n-1, 語(yǔ)句4的頻度：n-1, 語(yǔ)句5的頻度：n-1, T(n)=2+n+3(n-1)=4n-1=O(n). O(log2n )2.4. i=1; while (i=n) i=i*2; 解： 語(yǔ)句1的頻度是1, 設(shè)語(yǔ)句2的頻度是f(n), 則：2f(n)=n;f(n)=log2n 取最大值f(n)= log2n, T(n)=O(log2n )O(n3)2.5. for(i=0;in;i+) for(j=0;ji;j+) for(k=0;kj;k+) x=x+2; 解：當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,.,m-1 , 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+.+m-1=(m-1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了: 0+(1-1)*1/2+.+(n-1)n/2=n(n+1)(n-1)/6所以時(shí)間復(fù)雜度為O(n3). 我們還應(yīng)該區(qū)分算法的最壞情況 的行為和期望行為。如快速排序的最 壞情況運(yùn)行時(shí)間是 O(n2)，但期望時(shí)間是 O(nlogn)。通過(guò)每次都仔細(xì) 地選擇基準(zhǔn)值，我們有可能把平方情況 (即O(n2)情況)的概率減小到幾乎等于 0。在實(shí)際中，精心實(shí)現(xiàn)的快速排序一般都能以 (O(nlogn)時(shí)間運(yùn)行。 下面是一些常用的記法： 訪問(wèn)數(shù)組中的元素是常數(shù)時(shí)間操 作，或說(shuō)O(1)操作。一個(gè)算法如 果能在每個(gè)步驟去掉一半數(shù)據(jù)元素，如二分檢索，通常它就取 O(logn)時(shí)間。用strcmp比較兩個(gè)具有n個(gè)字符的串需要O(n)時(shí)間 。常規(guī)的矩陣乘算法是O(n3)，因?yàn)樗?