【正文】 的若干個數(shù)進行排序，下面的做法可行嗎？ int n； cin n。 int a[n]。 for (int i=0。 in。 i++) cin a[i]。 sort(a,n)。 動態(tài)變量 ? 動態(tài)變量是指在程序運行中，由程序根據(jù)需要所創(chuàng)建的變量。例如： ? int *p,*q。 ? p = new int。 //創(chuàng)建了一個 int型動態(tài)變量， p指向之。 或 ? p = (int *)malloc(sizeof(int))。 //include cstdlib ? 再例如： ? q = new int[n]。 //創(chuàng)建了一個由 n個 int型元素所構(gòu)成 //的動態(tài)數(shù)組變量， q指向其第一個元素。 或 ? q = (int *)malloc(sizeof(int)*n)。 介紹三個有用的內(nèi)存申請函數(shù) 或： (1) malloc(m) — 將總共需要的字節(jié)數(shù)作為參數(shù)傳遞給該函數(shù)，返回值是指向最新分配的內(nèi)存的指針，而如果內(nèi)存沒有分配好，則返回值是 NULL。 例 ： int *pointer=(int *)malloc(10*sizeof (int))。 說明 : malloc( )返回的內(nèi)存是 “ 沒有 “ 初始化的。這塊內(nèi)存可能包含任何隨機的垃圾，你可以馬上用有效數(shù)據(jù)或者至少是用零來初始化這塊內(nèi)存。 ■ (2) calloc(n, m) — calloc()函數(shù)是 malloc的簡單包裝。它的主要優(yōu)點是把動態(tài)分配的內(nèi)存清零。 返回值是指向最新分配的內(nèi)存的指針，而如果內(nèi)存沒有分配好，則返回值是 NULL。將需要的存儲空間數(shù)量和單個空間的字節(jié)數(shù)作為參數(shù)傳遞給該函數(shù)。 例： int *point=（ int *） calloc(10, sizeof（ int))。 ■ （ 3） realloc(p, m ) — realloc 可以對給定的空間進行擴大或者縮小，無論是擴張或是縮小，原有內(nèi)存的中內(nèi)容將保持不變。當然，對于縮小，則被縮小的那一部分的內(nèi)容會丟失。 realloc 并不保證調(diào)整后的內(nèi)存空間和原來的內(nèi)存空間保持同一內(nèi)存地址。相反， realloc 返回的指針很可能指向一個新的地址。 例： p = (int *) realloc (p, 15*sizeof(int))。 說明 ：傳一個空指針（ 0）給 realloc 時， realloc 相當于malloc。 int* p = (int *) realloc (0,sizeof(int) * 10)。 //分配一個全新的內(nèi)存空間，等同于： int* p = (int *) malloc(sizeof(int) * 10)。 ■ ? 動態(tài)變量沒有名字，對動態(tài)變量的訪問需要通過指向動態(tài)變量的指針變量來進行（ 間接訪問 ）。例如： int *p,*q。 p = new int。 ...*p... //訪問上面創(chuàng)建的 int型動態(tài)變量 q = new int[n]。 ...*(q+3)... //或 ...q[3]...，訪問上面創(chuàng)建的 //動態(tài)數(shù)組中的第 4個元素 ? 在 C++中，動態(tài)變量需要由程序顯式地撤消（使之消亡）。例如： ?delete p。 //撤消 p指向的 int型動態(tài)變量 或 ?free(p)。 ? 再例如： ?delete []q。 //撤消 q指向的動態(tài)數(shù)組 或 ?free(q)。 ? 用 new創(chuàng)建的動態(tài)變量需要用 delete來撤銷；用 malloc創(chuàng)建的動態(tài)變量則需要用free撤銷。 ? new與 malloc的主要區(qū)別在于： ?new自動計算所需分配的空間大小，而 malloc則需要顯式指出。 ?new自動返回相應類型的指針，而 malloc要作強制類型轉(zhuǎn)換。例如： ? int *p,*q。 ? p = new int。 ? q= (int *)malloc(sizeof(int))。 ?如果創(chuàng)建的是動態(tài)對象， new會去調(diào)用相應對象類的構(gòu)造函數(shù)，而 malloc則否。 ? delete與 free的主要區(qū)別是： ?如果 p指向的是對象（或?qū)ο髷?shù)組），則 delete p（或 delete []p）會去調(diào)用對象類的析構(gòu)函數(shù)，而 free(p)則否。 ? 用 delete和 free只能撤消動態(tài)變量！ ?int x,*p。 ?p = amp。x。 ?delete p。 //Error “內(nèi)存泄漏”與“懸浮指針”問題 ? 內(nèi)存泄漏 ：沒有撤消動態(tài)對象，而把指向它的指針指向了別處，這時，這個動態(tài)變量存在但不可訪問，從而浪費空間。例如： int x,*p。 p = new int[10]。 p = amp。x。 //之后，上面的動態(tài)數(shù)組就訪問不到了！ ? 懸浮指針 ：用 delete或 free撤消動態(tài)變量后，指針仍指向該變量所對應的空間，這時就會出現(xiàn)一個“ 懸浮指針 ” 。例如： int x,*p。 p = new int[10]。 ...... delete []p。 ...... *p = 1。 // 危險 動態(tài)變量的應用 ―― 動態(tài)數(shù)組 ? 對輸入的若干個數(shù)進行排序，如果輸入時先輸入數(shù)的個數(shù)，然后再輸入各個數(shù)，則可用下面的動態(tài)數(shù)組來表示這些數(shù)： int n。 int *p。 cin n。 p = new int[n]。 for (int i=0。 in。 i++) cin p[i]。 sort(p,n)。 ...... delete []p。 ? 對輸入的若干個數(shù)進行排序，在輸入時，先輸入各個數(shù)，最后輸入一個結(jié)束標記（如： 1），這時，可以按以下方式實現(xiàn)： const int INCREMENT=10。 int max_len=20,count=0,n,*p=new int[max_len]。 cin n。 while (n != 1) { if (count = max_len) { max_len += INCREMENT。 int *q=new int[max_len]。 for (int i=0。 icount。 i++) q[i] = p[i]。 delete []p。 p = q。 } p[count] = n。 count++。 cin n。 } sort(p,count)。 ...... delete []p。 思考： 用 中函數(shù)怎么實現(xiàn)？ { max_len += INCREMENT。 int *q=（ int*） realloc （ max_len*sizeof（ int）） 。 if （ q!=NULL) p=q。 } ? ? 上面的實現(xiàn)方法雖然可行，但是， ?當數(shù)組空間不夠時，它需要重新申請空間、進行數(shù)據(jù)轉(zhuǎn)移以及釋放原有的空間，這樣做比較麻煩并且效率有時不高。 ?當需要在數(shù)組中增加或刪除元素時，還將會面臨數(shù)組元素的大量移動問題。 ? 鏈表 可以避免數(shù)組的上述問題！ 動態(tài)變量的應用 ―― 鏈表 ? 鏈表用于表示由若干個（個數(shù)不定）同類型的元素所構(gòu)成的具有線性結(jié)構(gòu)的復合數(shù)據(jù)。 ? 鏈表中的每一個元素除了本身的數(shù)據(jù)外，還 包含一個（或多個）指針 ，它（們）指向鏈表中下一個（和其它）元素。 ? 上述的定義隱含著鏈表元素在內(nèi)存中不必存放在連續(xù)的空間內(nèi)。 ? 如果每個元素只包含一個指針，則稱為 單鏈表 ，否則稱為 多鏈表 。 單鏈表 ? 單鏈表的每個元素只包含一個指針。 ? 需要一個 頭指針 ，指向第一個元素。 ? 單鏈表中的結(jié)點類型和表頭指針變量的定義如下： struct Node { int content。 //代表結(jié)點的數(shù)據(jù) Node *next。 //代表后一個結(jié)點的地址 }。 //結(jié)點的類型定義 Node *head=NULL。 //頭指針變量定義，初始狀態(tài)下 //為空值。 NULL在 cstdio中定義 head a1 a2 an NULL 在鏈表中插入一個結(jié)點 ? 首先產(chǎn)生一個新結(jié)點： Node *p=new Node。 //產(chǎn)生一個動態(tài)變量來表示新結(jié)點。 pcontent = a。 //把 a賦給新結(jié)點中表示結(jié)點值的成員。 ? 圖示為： p a ? 如果鏈表為空（創(chuàng)建第一個結(jié)點時），則進行下面的操作： if (head == NULL) { head = p。 //頭指針指向新結(jié)點。 pnext = NULL。 //或 ， headnext = NULL。 //把新結(jié)點的 next成員置為 NULL。 } ? 圖示為： p head NULL a ? 如果新結(jié)點插在表頭，則進行下面的操作： pnext = head。 //把新結(jié)點的下一個結(jié)點指定為 //鏈表原來的第一個結(jié)點。 head = p。 //表頭指針指向新結(jié)點。 ? 圖示為： head p a1 a2 an NULL a ? 如果新結(jié)點插在表尾，則進行下面的操作： Node *q=head。 //q指向第一個結(jié)點 while (qnext != NULL) //循環(huán)查找最后一個結(jié)點 q = qnext。 //循環(huán)結(jié)束后， q指向鏈表最后一個結(jié)點 qnext = p。 //把新結(jié)點加到鏈表的尾部。 pnext = NULL。 //把新結(jié)點的 next成員置為 NULL。 ? 圖示為： p a NULL NULL head a1 a2 an q ? 如果新結(jié)點插在鏈表中第 i（ i0）個結(jié)點（ ai）的后面，則進行下面的操作： Node *q=head。 //q指向第一個結(jié)點。 int j=1。 //當前結(jié)點的序號，初始化為 1 while (j i) //循環(huán)查找第 i個結(jié)點。 { if (qnext == NULL) break。 //沒有下一個結(jié)點了 q = qnext。 //q指向下一個結(jié)點 j++。 //結(jié)點序號增加 1 } //循環(huán)結(jié)束時， q或者指向第 i個結(jié)點，或者指向最后一個結(jié)點（結(jié)點數(shù)不夠 i時）。 if (j == i) //q指向第 i個結(jié)點。 { pnext = qnext。 //把新結(jié)點的下一個結(jié)點指定為 q所指向 //結(jié)點的下一個結(jié)點。 qnext = p。 //把新結(jié)點指定為 q所指向結(jié)點的下一個結(jié)點。 } else //鏈表中沒有第 i個結(jié)點。 cout 沒有第 i 個結(jié)點 \n。 ? 圖示為： q head p a1 ai an a NULL 在鏈表中刪除一個結(jié)點 下面的操作假設鏈表不為空，即： head != NULL ? 如果刪除鏈表中第一個結(jié)點，則進行下面的操作： Node *p=head。 //p指向第一個結(jié)點。 head = headnext。 //頭指針指向第一個結(jié)點的下一個結(jié)點。 delete p。 //歸還刪除結(jié)點的空間。 ? 圖示為： head p a1 a2 an NULL ? 如果刪除鏈表的最后一個結(jié)點，則進行下面的操作： Node *q1=NULL,*q2=head。 //循環(huán)查找最后一個結(jié)點，找到后， q2指向它， q1指向它的前一個結(jié)點。 while (q2next != NULL) { q1 = q2。 q2 = q2next。 } if (q1 != NULL) //存在倒數(shù)第二個結(jié)點。 q1next = NULL。 //把倒數(shù)第二個結(jié)點的 next置為 NULL。 else //鏈表中只有一個結(jié)點。 head = NULL。 //把頭指針置為 NULL。 delete q2。 //歸還刪除結(jié)點的空間。 ? 圖示為： head q1 q2 a1 an1 an (空 ) NULL NULL ? 如果刪除鏈表中第 i（ i0）個結(jié)點 ai，則進行下面的操作： if (i == 1) //要刪除的結(jié)點是鏈表的第一個結(jié)點。 { Node *p=head。 //p指向第一個結(jié)點。 head = headnext。 //head指向第一個結(jié)點的下一個結(jié)點。 delete p。 //歸還刪除結(jié)點的空間。 } else //要刪除的結(jié)點不是鏈表的第一個結(jié)點。 { Node *p=head。 //p指向第一個結(jié)點。 int j=1。 //當前結(jié)點的序號，初始化為 1 while (j i1)