程序員面試分類模擬7

程序員面試分類模擬7論述題1.

如何找出數(shù)組中只出現(xiàn)一次的數(shù)字正確答案：一個整型數(shù)組里除了一個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這個只出現(xiàn)一次的數(shù)字。要求時間復雜度是O(n)，空間復雜（江南博哥）度是O(1)。

如果本題對時間復雜度沒有要求的話，最容易想到的方法就是首先對這個整型數(shù)組排序，然后從第一個數(shù)字開始遍歷，比較相鄰的兩個數(shù)，從而找出這個只出現(xiàn)一次的數(shù)字，所以其時間復雜度最快為O(nlogn)。

由于時間復雜度與空間復雜度的限制，該種方法不可取，所以需要一種更高效的方式。題目強調(diào)只有一個數(shù)字出現(xiàn)一次，其他的出現(xiàn)了兩次，首先想到的是異或運算的性質(zhì)：任何一個數(shù)字異或它自己都等于0，根據(jù)這一特性，如果從頭到尾依次異或數(shù)組中的每一個數(shù)字，因為那些出現(xiàn)兩次的數(shù)字全部在異或中抵消掉了，所以最終的結(jié)果剛好是那個只出現(xiàn)一次的數(shù)字。

程序示例如下：

#include＜stdio.h＞

intfindNotDouble(inta[],intn)

{

intresult=a[0];

inti;

for(i=1;i＜n;++i)

result^=a[i];

returnresult;

}

intmain()

{

intarray[]={1,2,3,2,4,3,5,4,1};

intlen=sizeof(array)/sizeof(array[0]);

intnum=findNotDouble(array,len);

printf("%d\n",num);

return0;

}

程序輸出結(jié)果：

5

引申：如果題目改為整型數(shù)組中除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次，如何求解這兩個只出現(xiàn)一次的數(shù)?

在上述解決方案的基礎上，如果能夠把原數(shù)組分為兩個子數(shù)組，在每個子數(shù)組中，包含一個只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)兩次，問題就可以很容易地解決了：分別對兩個子數(shù)組按照上述解決方案執(zhí)行結(jié)果。

現(xiàn)在問題的難點就是如何劃分為兩個符合求解方案的子數(shù)組。首先從頭到尾依次異或數(shù)組中的每一個數(shù)字，因為其他數(shù)字都出現(xiàn)了兩次，在異或中全部抵消掉了，所以最終得到的結(jié)果將是兩個只出現(xiàn)一次的數(shù)字的異或結(jié)果。而這兩個數(shù)字肯定不一樣，那么這個異或結(jié)果肯定不為0，也就是說在這個結(jié)果數(shù)字的二進制表示中至少就有一位為1，否則就為0了。在結(jié)果數(shù)字中找到第一個為1的位的位置，記為第N位，此時以第N位是不是1為標準把原數(shù)組中的數(shù)字分成兩個子數(shù)組，第一個子數(shù)組中每個數(shù)字的第N位都為1，而第二個子數(shù)組的每個數(shù)字的第N位都為0。通過這種方法就可以把原數(shù)組分成了兩個子數(shù)組，每個子數(shù)組都包含一個只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)了兩次。

程序示例如下：

#include＜stdio.h＞

voidfmdOnce(intdata[],intn,int&num1,int&num2)

if(n＜5)

return;

intr1=0;

for(inti=0;i＜n;i++)

r1^=data[i];

intbitNum=0;

while(!(r1&0x1))

{

r1＞＞=1;

++bitNum;

}

intflag=(1＜＜bitNum);

num1=0;

num2=0;

for(intj=0;j＜n;j++)

{

if(data[j]&flag)

num1^=data[j];

else

num2^=data[j];

}

}

intmain()

{

intarray[]={1,2,3,2,4,3,5,1};

intnum1,hum2;

findOnce(array,sizeof(array)/sizeof(array[0]),num1,num2);

printf("%d\n%d\n",num1,num2);

return0;

}

程序輸出結(jié)果：

5

4

2.

如何判斷一個整數(shù)x是否可以表示成n(n≥2)個連續(xù)正整數(shù)的和正確答案：假設x可以表示成n(n≥2)個連續(xù)正整數(shù)的和，那么數(shù)學表達式如下：x=m+(m+1)+(m+2)+...+(m+n-1)，其中m為分解成的連續(xù)整數(shù)中最小的那一個，由于m是大于等于1的正整數(shù)，可知x=(2m+n-1)×n/2，變換之后m=(2×x/n-n+1)/2，由m的范圍可以知道(2×x/n-n+1)/2≥1，以上就是X和n的關(guān)系。給定一個n，看是否x能分解成n個連續(xù)整數(shù)的和，可以判斷是否存在m，也就轉(zhuǎn)換成(2×x/n-n+1)是否是偶數(shù)的問題。

判斷一個數(shù)是否是偶數(shù)，是一個比較容易解決的問題，所以本題就迎刃而解了，程序示例如下：

#inchude＜stdio.h＞

#include＜math.h＞

intmain()

{

intm=0,n=0,start=0,end=0,flag=0;

floattemp=0.0;

printf("請輸入被分解的數(shù):");

scanf("%d",&m);

printf("請輸入需要被分解的數(shù)字的個數(shù):");

scanf("%d",&n);

temp=(float)m/n-(float)(n-1)/2;

if(temp==(int)temp)

{

for(flag=1,start=(int)temp,end=start+n;start＜end;start++)

printf("%d",start);

printf("\n");

}

if(flag==0)

printf("沒有符合條件的個數(shù)\n");

return0;

}

程序輸出結(jié)果：

請輸入被分解的數(shù)：10

請輸入需要被分解的數(shù)字的個數(shù)：4

1

2

3

4

3.

數(shù)組和鏈表的區(qū)別是什么正確答案：數(shù)組與鏈表是兩種不同的數(shù)據(jù)存儲方式。鏈表的特性是在中間任意位置添加元素、刪除元素都非常地快，不需要移動其他的元素。通常對于單鏈表而言，鏈表中每一個元素都要保存一個指向下一個元素的指針；而對于雙鏈表，每個元素既要保存一個指向下一個元素的指針，還要保存一個指向上一個元素的指針；循環(huán)鏈表則在最后一個元素中保存一個指向第一個元素的指針。

數(shù)組是一組具有相同類型和名稱的變量的集合，這些變量稱為數(shù)組的元素，每個數(shù)組元素都有一個編號，這個編號稱為數(shù)組的下標，可以通過下標來區(qū)別并訪問這些元素，數(shù)組元素的個數(shù)也稱為數(shù)組的長度。

具體而言，數(shù)組和鏈表的區(qū)別主要表現(xiàn)在以下幾個方面：

1)邏輯結(jié)構(gòu)。數(shù)組必須事先定義固定的長度(元素個數(shù))，不能適應數(shù)據(jù)動態(tài)地增減的情況，即在使用數(shù)組之前，就必須對數(shù)組的大小進行確定。當數(shù)據(jù)增加時，可能超出原先定義的元素個數(shù)；當數(shù)據(jù)減少時，造成內(nèi)存浪費。數(shù)組中插入、刪除數(shù)據(jù)項時，需要移動其他數(shù)據(jù)項。而鏈表采用動態(tài)分配內(nèi)存的形式實現(xiàn)，可以適應數(shù)據(jù)動態(tài)地增減的情況，需要時可以用new/malloc分配內(nèi)存空間，不需要時用delete/free將已分配的空間釋放，不會造成內(nèi)存空間浪費，且可以方便地插入、刪除數(shù)據(jù)項。

2)內(nèi)存結(jié)構(gòu)。(靜態(tài))數(shù)組從棧中分配空間，對于程序員方便快速，但是自由度小。鏈表從堆中分配空間，自由度大，但是申請管理比較麻煩。

3)數(shù)組中的數(shù)據(jù)在內(nèi)存中是順序存儲的，而鏈表是隨機存儲的。數(shù)組的隨機訪問效率很高，可以直接定位，但插入、刪除操作的效率比較低。鏈表在插入、刪除操作上相對數(shù)組有很高的效率，而如果要訪問鏈表中的某個元素，那就得從表頭逐個遍歷，直到找到所需要的元素為止，所以鏈表的隨機訪問效率比數(shù)組低。

4)鏈表不存在越界問題，數(shù)組有越界問題。數(shù)組便于查詢，鏈表便于插入刪除，數(shù)組節(jié)省空間但是長度固定，鏈表雖然變長但是占了更多的存儲空間。

所以，由于數(shù)組存儲效率高、存儲速度快的優(yōu)點，如果需要頻繁訪問數(shù)據(jù)，很少插入刪除操作，則使用數(shù)組；反之，如果頻繁插入刪除，則應使用鏈表。兩者各有用處。

4.

何時選擇順序表、何時選擇鏈表作為線性表的存儲結(jié)構(gòu)為宜正確答案：順序表按照順序存儲，即數(shù)據(jù)元素存放在一個連續(xù)的存儲空間之中，實現(xiàn)順序存取或(按下標)直接存取。鏈表按照鏈接存儲，即存儲空間一般在程序的運行過程中動態(tài)分配與釋放，且只要存儲器中還有空間，就不會產(chǎn)生存儲溢出的問題。

順序表與鏈表各有短長，在實際應用中，應根據(jù)具體問題的要求和性質(zhì)來選擇使用哪一種存儲結(jié)構(gòu)，通常有以下幾方面的考慮：

1)空間。順序表的存儲空間是靜態(tài)分配的，鏈表的存儲空間是動態(tài)分配的。順序表的存儲密度比鏈表大，當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規(guī)模時，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。

2)時間。順序表是隨機存取結(jié)構(gòu)，若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。

所以，不能籠統(tǒng)地說哪種實現(xiàn)更好，必須根據(jù)實際問題的具體需要，并對各個方面的優(yōu)缺點進行綜合評估，才能最終選擇一種比較適合的實現(xiàn)方法。

5.

如何使用鏈表頭正確答案：在回答這個問題前，首先弄清楚一個概念，什么是結(jié)點?簡單地說，結(jié)點表示的就是數(shù)據(jù)域與指針域的和，數(shù)據(jù)域存儲數(shù)據(jù)元素的信息，指針域指示直接后繼存儲位置，所以結(jié)點表示數(shù)據(jù)元素或數(shù)據(jù)元素的映像關(guān)系。

單鏈表的開始結(jié)點之前附設一個類型相同的結(jié)點，稱之為頭結(jié)點，頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息(也可以存放如線性表的長度等附加信息)，頭結(jié)點的指針域存儲指向開始結(jié)點的指針(即第一個元素結(jié)點的存儲位置)。如圖所示為帶頭結(jié)點的單鏈表。

圖1帶頭結(jié)點的單鏈表

頭結(jié)點的作用主要有以下兩點：

1)對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除表中任何結(jié)點，所要做的都是修改前一結(jié)點的指針域，因為任何元素結(jié)點都有前驅(qū)結(jié)點。若鏈表沒有頭結(jié)點，則首元素結(jié)點沒有前驅(qū)結(jié)點，在其前插入結(jié)點或刪除該結(jié)點時操作會復雜些。

2)對帶頭結(jié)點的鏈表，表頭指針是指向首結(jié)點的非空指針，因此空表與非空表的處理是一樣的。

在實現(xiàn)運算時，需要動態(tài)產(chǎn)生出其頭結(jié)點，并將其后繼指針置為空。

voidinitial_List(node*L)

{

L=(node*)malloc(sizeof(node));

L-＞next=NULL;

}

需要注意的是，開始結(jié)點、頭指針、頭結(jié)點并不是一個概念，它們是有區(qū)別的。開始結(jié)點是指鏈表中的第一個結(jié)點，也就是沒有直接前趨的那個結(jié)點，而鏈表的頭指針是指向鏈表開始結(jié)點的指針(沒有頭結(jié)點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。圖2所示鏈表的頭指針為head，則稱該鏈表為鏈表head，在定義鏈表變量時可以這樣聲明：node*head，而頭結(jié)點是人為地在鏈表的開始結(jié)點之前附加的一個結(jié)點。有了頭結(jié)點之后，頭指針指向頭結(jié)點，無論鏈表是否為空，頭指針總是非空。而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結(jié)點之后)。

圖2鏈表head結(jié)構(gòu)

6.

如何實現(xiàn)單鏈表的插入、刪除操作正確答案：插入運算是將值為x的新結(jié)點插入到單鏈表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。具體算法如下：

1)找到ai-1存儲位置p。

2)生成一個數(shù)據(jù)域為x的新結(jié)點*s。

3)令結(jié)點*p的指針域指向新結(jié)點s。

4)新結(jié)點s的指針域指向結(jié)點ai。

圖3所示為單鏈表插入結(jié)點示意圖。

圖3單鏈表插入結(jié)點示意圖

單鏈表插入結(jié)點具體算法實現(xiàn)如下：

StatusInsertList(LinkListhead,DataTypex,inti)

{

ListNode*p;

p=head;

intj=1;

while(p&&j＜i)

{

p=p-＞next;

++j;

}

if(!p)‖j＞i)

{

printf("PositionError");

retumERROR;

}

s=(ListNode*)malloc(sizeof(ListNode));

s-＞data=x;

s-＞next=p-＞next;

P-＞next=s;

returnOK;

}

單鏈表插入算法的時間主要耗費在查找操作GetNode，即獲得結(jié)點上，故單鏈表插入操作的時間復雜度為O(n)。

單鏈表的刪除操作是將單鏈表的第i個結(jié)點刪去。其具體步驟如下：

1)找到ai-1的存儲位置P(因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中)。

2)令p→next指向ai的直接后繼結(jié)點(即把ai從鏈上摘下)ai+1。

3)釋放結(jié)點ai的空間，將其歸還給“存儲池”。

圖4所示為單鏈表刪除結(jié)點示意圖。

圖4單鏈表刪除結(jié)點示意圖

單鏈表刪除結(jié)點具體算法實現(xiàn)如下：

StatusDeleteList(LinkListhead,inti)

{

ListNode*p,*r;

P=head;

intj=1;

while(p-＞next&&j＜i)

{

p=p-＞next;

++j;

}

if(p-＞next==NULL‖j＞i)

{

printf("PositionError");

returnERROR;

}

r=p-＞next;

P-＞next=r-＞next;

free(r);

returnOK;

}

設單鏈表的長度為n，則單鏈表刪除第i個結(jié)點時，必須保證1≤i≤n，否則不合法。而當i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此，被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當*p存在(即p!=NULL)且*p不是終端結(jié)點(即p-＞next!=NULL)同時滿足j≤i時，才能確定被刪結(jié)點存在。此時，算法的時間復雜度也是O(n)。

引申：如何刪除單鏈表的頭元素?

要刪除頭元素，首先需要通過頭結(jié)點定位頭元素，并將頭結(jié)點指向頭元素的下一個元素，然后釋放頭元素的內(nèi)存空間。具體代碼如下：

voidRemoveHead(LinkListhead)

{

ListNode*p;

p=head-＞next;

head-＞next=p-＞next;

free(p);

}

7.

如何找出單鏈表中的倒數(shù)第k個元素正確答案：為了找出單鏈表中的倒數(shù)第k個元素，最容易想到的方法是首先遍歷一遍單鏈表，求出整個單鏈表的長度n，然后將倒數(shù)第k個，轉(zhuǎn)換為正數(shù)第n-k個，接下去遍歷一次就可以得到結(jié)果。但是該算法需要對鏈表進行兩次遍歷，第一次遍歷用于求解單鏈表的長度，第二次遍歷用于查找正數(shù)第n-k個元素。

于是想到了第二種方法，如果沿從頭至尾的方向從鏈表中的某個元素開始，遍歷k個元素后剛好達到鏈表尾，那么該元素就是要找的倒數(shù)第k個元素。根據(jù)這一性質(zhì)，可以設計如下算法：從頭結(jié)點開始，依次對鏈表的每一個結(jié)點元素進行這樣的測試，遍歷k個元素，查看是否到達鏈表尾，直到找到那個倒數(shù)第k個元素為止。此種方法將對同一批元素進行反復多次的遍歷，對于鏈表中的大部分元素而言，都要遍歷k個元素，如果鏈表長度為n，該算法時問復雜度為O(kn)級，效率太低。

存在另外一種更高效的方式，只需要一次遍歷即可查找到倒數(shù)第k個元素。由于單鏈表只能從頭到尾依次訪問鏈表的各個結(jié)點，所以如果要找鏈表的倒數(shù)第k個元素，也只能從頭到尾進行遍歷查找。在查找過程中，設置兩個指針，讓其中一個指針比另一個指針先前移k-1步，然后兩個指針同時往前移動。循環(huán)直到先行的指針值為NuLL時，另一個指針所指的位置就是所要找的位置。程序代碼如下：

template＜classT＞

structListNode

{

Tdata;

ListNode*next;

};

template＜classT＞

ListN0de＜T＞*FindElem(ListNode＜T＞*head,intk)

{

ListNode＜T＞*ptr1,*ptr2;

ptr1=ptr2=head;

for(inti=0;i＜k;++i)∥前移k步

{

ptr1=ptr1-＞next;

}

while(ptr1!=NULL)∥循環(huán)檢測

{

ptr1=ptr1-＞next;

ptr2=ptr2-＞next;

}

returnptr2;

}

8.

如何實現(xiàn)單鏈表反轉(zhuǎn)正確答案：輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后鏈表的頭結(jié)點。鏈表結(jié)點定義如下：

structListNode

{

intm_nKey;

ListNode*m_pNext;

}

為了正確地反轉(zhuǎn)一個鏈表，需要調(diào)整指針的指向，而與指針操作相關(guān)代碼總是容易出錯的。先舉個例子看一下具體的反轉(zhuǎn)過程。例如，1、m、n是3個相鄰的結(jié)點，假設經(jīng)過若干步操作，已經(jīng)把結(jié)點1之前的指針調(diào)整完畢，這些結(jié)點的mpNext指針都指向前面一個結(jié)點?，F(xiàn)在遍歷到結(jié)點m，當然需要調(diào)整結(jié)點的m_pNext指針，讓它指向結(jié)點1，但需要注意的是，一旦調(diào)整了指針的指向，鏈表就斷開了，因為已經(jīng)沒有指針指向結(jié)點n，沒有辦法再遍歷到結(jié)點n了，因此為了避免鏈表斷開，需要在調(diào)整m的mpNext之前要把n保存下來。接下來試著找到反轉(zhuǎn)后鏈表的頭結(jié)點，不難分析出反轉(zhuǎn)后鏈表的頭結(jié)點是原始鏈表的尾結(jié)點，即mpNext為空指針的結(jié)點。

具體的實現(xiàn)過程如下：

ListNode*ReverseIteratively(ListNode*pHead)

{

ListNode*pReversedHead=NULL;

ListNode*pNode=pHead;

ListNode*pPrev=NULL;

while(pNode!=NULL)

{

ListNode*pNext=pNode-＞m_pNext;

if(pNext==NULL)

pReversedHead=pNode;

pNode-＞m_pNext=pPrev;

pPrev=pNode;

pNode=pNext;

}

returnpReversedHead;

}

如果本題簡化為逆序輸出單鏈表元素，那么遞歸將是最簡單的方法。在遞歸函數(shù)之后輸出當前元素，這樣能確保輸出第n個結(jié)點的元素語句永遠在第n+1個遞歸函數(shù)之后執(zhí)行，也就是說第n個元素永遠在第n+1個元素之后輸出，最終先輸出最后一個元素，然后是倒數(shù)第2個、倒數(shù)第3個，直到輸出第一個元素位置。具體實現(xiàn)過程如下：

voidPrintReverseLink(ListNode*head)

{

if(head-＞Next!=null)

{

PrintReverseLink(head-＞m_pNext);

printf("%d\n",head-＞m_Next-＞m_nKey);

}

}

本題不是要求逆序輸出，而是需要把單鏈表逆序，所以在使用遞歸思想的時候，還需要處理遞歸后的邏輯問題。具體而言，是在反轉(zhuǎn)當前結(jié)點之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)結(jié)點，不過該方法存在一個問題，就是反轉(zhuǎn)后的最后一個結(jié)點會形成一個環(huán)，所以必須將函數(shù)返回的結(jié)點的mpNext域設置為NULL，同時考慮到鏈表反轉(zhuǎn)時需要改變head指針，所以在進行參數(shù)傳遞時，需要傳遞引用。

具體的實現(xiàn)過程如下：

ListNode*Reverse(ListNode*p,ListNode*&head)

{

if(p==NULL‖p-＞m_pNext==NULL)

{

head=p;

returnp

}

else

{

ListNode*temp=Reverse(p-＞m_pNext,head);

temp-＞m_pNext=p;

returntemp;

}

}

需要注意的是，當單鏈表有環(huán)時，就會無法反轉(zhuǎn)，因為如果單鏈表有環(huán)，則存在兩個結(jié)點指向同一結(jié)點的情況。如果反轉(zhuǎn)就變成一個結(jié)點指向兩個了，而這對于單鏈表是不可能的。

9.

如何從尾到頭輸出單鏈表正確答案：structListNode

{

intm_nKey;

ListNode*m_pNext;

};

從頭到尾輸出單鏈表比較簡單，于是很自然地想把鏈表中鏈接結(jié)點的指針反轉(zhuǎn)過來，改變鏈表的方向，然后就可以從尾到頭輸出了，但該方法需要額外的操作，是否還有更好的方法呢?答案是肯定的。

接下來的想法是從頭到尾遍歷鏈表，每經(jīng)過一個結(jié)點的時候，把該結(jié)點放到一個棧中。當遍歷完整個鏈表后，再從棧頂開始輸出結(jié)點的值，此時輸出的結(jié)點的順序已經(jīng)反轉(zhuǎn)過來了。該方法雖然沒有只需要遍歷一遍鏈表，但是需要維護一個額外的?？臻g，實現(xiàn)起來會比較麻煩。

是否還能有更高效的方法?于是我們想到了第三種方法，既然想到了棧來實現(xiàn)這個函數(shù)，而遞歸本質(zhì)上就是一個棧結(jié)構(gòu)，于是很自然地又想到了用遞歸來實現(xiàn)。要實現(xiàn)反過來輸出鏈表，每訪問到一個結(jié)點的時候，先遞歸輸出它后面的結(jié)點，再輸出該結(jié)點自身，這樣鏈表的輸出結(jié)果就反過來了。

具體實現(xiàn)如下：

voidPrintListReversely(ListNode*pListHead)

{

if(pListHead!=NULL)

{

PrintListReversely(pListHead-＞m_pNext);

printf("%d",pListHead-＞m_nKey);

}

}

該題還有兩個常見的變體：

1)從尾到頭輸出一個字符串。

2)定義一個函數(shù)求字符串的長度，要求該函數(shù)體內(nèi)不能聲明任何變量。

對于這兩個變體的解答，都可以參考本題的實現(xiàn)方式，在此就不再贅述了。

10.

如何尋找單鏈表的中間結(jié)點正確答案：最容易想到的思路是首先求解單鏈表的長度length，然后遍歷length/2的距離即可查找到單鏈表的中間結(jié)點，但是此種方法需要遍歷兩次鏈表，即第一次遍歷求解單鏈表的長度，第二次遍歷根據(jù)索引獲取中間結(jié)點。

如果是雙向鏈表，可以首尾并行，利用兩個指針一個從頭到尾，一個從尾到頭，當兩個指針相遇的時候就找到中間元素。以此思想為基礎，如果是單鏈表也可以采用雙指針的方式來實現(xiàn)中間結(jié)點的快速查找。

第一步，有兩個指針同時從頭開始遍歷。第二步，一個快指針一次走兩步，一個慢指針一次走一步。第三步，快指針先到鏈表尾部，而慢指針則恰好到達鏈表中部(快指針到鏈表尾部，當鏈表長度為奇數(shù)時，慢指針指向的即是鏈表中間指針；當鏈表長度為偶數(shù)時，慢指針指向的結(jié)點和慢指針指向結(jié)點的下一個結(jié)點都是鏈表的中間結(jié)點)。

具體實現(xiàn)如下：

node*SearchMid(node*head)

{

node*temp=head;

node*mid=head;

while(head!=NULL&&head-＞next!=NULL&&head-＞next-＞next!=NULL)

{

head=head-＞next-＞next;

temp=temp-＞next;

mid=temp;

}

returnmid;

}

11.

如何進行單鏈表排序正確答案：最容易想到的排序算法是冒泡排序法，所以首先用冒泡排序法進行單鏈表的排序。程序示例如下：

#include＜stdio.h＞

#include＜stdlib.h＞

typedefstructnode

intdata;

structnode*next;

}linklist;

linklist*head=NULL;

linklist*CreateList(int*arr,intlen)

{

intdata;

linklist*pCurrent,*rear;

head=(linklist*)malloc(sizeof(linklist));

rear=head;

intcount=0;

while(count＜len)

{

pCurrent=(linklist*)malloc(sizeof(linklist));

pCurrent-＞data=arr[count];

rear-＞next=pCurrent;

rear=pCurrent;

count++;

}

rear-＞next=NULL;

returnhead;

voidShowList(linklist*p)

{

while(p)

{

printf("%d",p-＞data);

p=p-＞next;

}

printf("\n");

}

voidBubbleSortList(linklist*p)∥鏈表冒泡順序

{

linklist*_temp=p-＞next;

linklist*_node=p-＞next;

inttemp;

for(;_temp-＞next;_temp=_temp-＞next)

{

for(_node=p-＞next;_node-＞next;_node=_node-＞next)

{

if(node-＞data＞_node-＞next-＞data)

{

temp=_node-＞data;

node-＞data=_node-＞next-＞data;

_node-＞next-＞data=temp;

}

}

}

intmain()

{

intarray[]={3,4,5,1,2,-1,7};

CreateList(array,sizeof(array)/sizeof(array[0]));

BubbleSortList(head);

ShowList(head-＞next);

return0;

}

程序輸出結(jié)果：

-1123457

在各種排序算法中，冒泡排序并非最高效的。對鏈表這一特定數(shù)據(jù)結(jié)構(gòu)而言，最好使用歸并排序算法。而堆排序、快速排序這些在數(shù)組排序時性能非常好的算法，用在只能“順序訪問”的鏈表中卻不盡如人意，但是歸并排序卻可以，它不僅保持了O(nlogn)的時間復雜度，而且它的空間復雜度也從O(n)降到了O(1)，除此之外，歸并排序是分治法的實現(xiàn)。具體實現(xiàn)過程如下：

#include＜iostream＞

#defineMAXSIZE1024

#defineLENGTH8

usingnamespacestd;

typedefstruct

{

intr[MAXSIZE+1];

intlength;

}SqList;

voidMerge(SqListSR,SqList&TR,inti,intm,intn)

{

intj,k;

for(j=m+1,k=i;i＜=m&&j＜=n;++k)

{

if(SR.r[i]＜=SR.r[j])

TR.r[k]=SR.r[i++];

else

TR.r[k]=SR.r[j++];

}

while(i＜=m)

TR.r[k++]=SR.r[i++];

while(j＜=n)

TR.r[k++]=SR.r[j++];

voidMSort(SqListSR,SqList&TR1,ints,intt)

{

intm;

SqListTR2;

if(s==t)

TR1.r[s]=SR.r[t];

else

{

m=(s+t)/2;

MSort(SR,TR2,s,m);

MSort(SR,TR2,m+1,t);

Merge(TR2,TR1,s,m,t);

}

}

voidMergeSort(SqList&L)

MSort(L,L,1,L.length);

intmain()

{

inti;

SqListL={{0,49,38,65,97,76,13,27},LENGTH};

MergeSort(L);

for(i=1;i＜=L.length;i++)

cout＜＜L.r[i]＜＜"";

cout＜＜endl;

return0;

}

程序輸出結(jié)果：

013273849657697

12.

如何實現(xiàn)單鏈表交換任意兩個元素(不包括表頭)正確答案：對于單鏈表而言，假設交換的結(jié)點為A與B，那么需要交換A與B的next指針以及AB直接前驅(qū)的next指針。需要注意的特殊情況：當A與B相鄰時，此時需要做特殊處理；如果A與B元素相同，就沒有必要交換；如果A與B結(jié)點中有一個是表頭，也不交換。

程序示例如下：

structnode

{

intdata;

node*next;

};

node*FindPre(node*head,node*p)

{

node*q=head;

while(q)

{

if(q-＞next==p)

returnq;

else

q=q-＞next;

}

returnNULL;

}

node*Swap(node*head,node*p,node*q)

{

if(head==NULL‖P==NULL‖q==NULL)

{

cout＜＜"invalidparameter:NULL"＜＜endl;

returnhead;

}

if(p-＞data==q-＞data)

returnhead;

if(p-＞next==q)

{

node*pre_p=FindPre(head,p);

pre_p-＞next=q;

p-＞next=q-＞next;

q-＞next=p;

}

elseif(q-＞next==p)

{

node*pre_q=FindPre(head,q);

pre_q-＞next=p;

q-＞next=p-＞next;

p-＞next=q;

}

elseif(p!=q)

{

node*pre_p=FindPre(head,p);

node*pre_q=FindPre(head,q);

node*after_p=p-＞next;

p-＞next=q-＞next;

q-＞next=after_p;

pre_p-＞next=q;

pre_q-＞next=p;

}

returnhead;

}

13.

如何檢測一個較大的單鏈表是否有環(huán)正確答案：單鏈表有環(huán)是指單鏈表中某個結(jié)點的next指針域指向的是鏈表中在它之前的某一個結(jié)點，這樣在鏈表的尾部形成一個環(huán)形結(jié)構(gòu)。檢測單鏈表是否有環(huán)，一般有以下幾種方法。

方法一：定義一個指針數(shù)組，初始化為空指針，從鏈表的頭指針開始往后遍歷，每次遇到一個指針就跟指針數(shù)組中的指針相比較，若沒有找到相同的指針，說明這個結(jié)點是第一次訪問，還沒有形成環(huán)，將這個指針添加到指針數(shù)組中去。若在指針數(shù)組中找到了同樣的指針，說明這個結(jié)點已經(jīng)被訪問過了，于是就形成了環(huán)。

方法二：定義兩個指針fast與slow，slow的初始值指向頭結(jié)點，fast的初始值指向頭結(jié)點的下一點，slow每次前進一步，fast每次前進兩步，兩個指針同時向前移動，快指針每移動一次都要跟慢指針比較，直到當快指針等于慢指針為止，就證明這個鏈表是帶環(huán)的單向鏈表，否則證明這個鏈表是不帶環(huán)的循環(huán)鏈表(fast先行到達尾部為NULL，則為無環(huán)鏈表)。

structlisttype

{

intdata;

structlisttype*next;

};

typedefstructlisttype*list;

intIsLoop(lists11)

{

listfast=s11-＞next;∥較slow快一步，步長為1

listslow=s11;

if(fast==NULL‖fast==slow)∥判斷鏈表長為2時是否相交

return-1;

while(fast!=NULL)

{

fast=fast-＞next;

slow=slow-＞next;

if(fast==slow)

return1;

}

}

方法三：通過使用STL庫中的map表進行映射。首先定義map＜node*,int＞m；將一個node*指針映射成數(shù)組的下標，并賦值為一個int類型的數(shù)值。然后從鏈表的頭指針開始往后遍歷，每次遇到一個指針P，就判斷m[p]是否為0。如果為0，則將m[p]賦值為1，表示該結(jié)點是第一次訪問；而如果m[p]的值為1，則說明這個結(jié)點已經(jīng)被訪問過一次了，于是就形成了環(huán)。

程序代碼示例如下：

map＜node*,int＞m;

boolIsLoop(node*head)

{

if(!head)

returnfalse;

node*p=head;

while(p)

{

if(m[p]==0)∥默認值都是0

m[p]=1;

elseif(m[p]==1)

returntrue;

p=p-＞next;

}

}

如果單鏈表有環(huán)，按照方法二的思路，走得快的指針fast若與走得慢的指針slow相遇時，slow指針肯定沒有遍歷完鏈表，而fast指針已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(1≤n)。假設slow指針走了s步，則fast指針走了2s步(fast步數(shù)還等于S加上在環(huán)上多轉(zhuǎn)的n圈)，設環(huán)長為r，則滿足如下關(guān)系表達式：

2s=s±nr

s=nr

設整個鏈表長為L，入口環(huán)與相遇點距離為x，起點到環(huán)入口點的距離為a。則滿足如下關(guān)系表達式：

a+x=nr

a+x=(n-1)r+r=(n-1)r+L-a

a=(n-1)r+(L-a-x)

(L-a-x)為相遇點到環(huán)入口點的距離，從鏈表頭到環(huán)入口點的距離=(n-1)*循環(huán)內(nèi)環(huán)+相遇點到環(huán)入口點，于是從鏈表頭與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環(huán)入口點。

程序代碼如下：

list*FindLoopPort(list*head)

{

list*slow=head,*fast=head;

while(fast&&fast-＞next)

{

slow=slow-＞next;

fast=fast-＞next-＞next;

if(slow==fast)break;

}

if(fast==NULL‖fast-＞next==NULL)

returnNULL;

slow=head;

while(slow!=fast)

{

slow=slow-＞next;

fast=fast-＞next;

}

returnslow;

}

14.

如何判斷兩個單鏈表(無環(huán))是否交叉正確答案：單鏈表相交是指兩個鏈表存在完全重合的部分(注意，不是交叉到一個點)。判斷兩個單鏈表是否交叉，一般有兩種方法：

1)將這兩個鏈表首尾相連，然后檢測看這個鏈表是否存在環(huán)，如果存在，則兩個鏈表相交，而檢測出來的依賴環(huán)入口即為相交的第一個點。

2)利用鏈表相交的性質(zhì)，如果兩個鏈表相交，那么兩個鏈表從相交點到鏈表結(jié)束都是相同的結(jié)點，必然是Y字形，所以判斷兩個鏈表的最后一個結(jié)點是不是相同即可。即先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結(jié)尾點，則兩個鏈表相交，這時記下兩個鏈表的長度length，再遍歷一次，長鏈表結(jié)點先出發(fā)前進(lengthMax-lengthMin)步，之后兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。

程序代碼實現(xiàn)如下：

boolIsIntersect(Node*list1,Node*list2,Node*&value)

{

value=NULL;

if(list1==NULL‖list2==NULL)

returnfalse;

Node*temp1=list1,*temp2=list2;

intsize1=0,size2=0;

while(temp1-＞next)

{

temp1=temp1-＞next;

++size1;

}

while(temp2-＞next)

{

temp2=temp2-＞next;

++size2;

}

if(temp1==temp2)

{

if(size1＞size2)

while(size1-size2＞0)

{

list1=list1-＞next;

--size1;

}

if(size2＞size1)

while(size2-size1＞0)

{

list2=list2-＞next;

--size2;

}

while(list1!=list2)

{

list1=list1-＞next;

list2=list2-＞next;

}

value=list1;

returntrue;

}

else

returnfalse;

}

15.

如何刪除單鏈表中的重復結(jié)點正確答案：一個沒有排序的鏈表，如list={a,1,x,b,e,f,f,e,a,g,h,b,m}，請去掉重復項，并保留原順序，以上鏈表去掉重復項后為newlist={a,1,x,b,e,f,g,h,m}，請寫出一個高效算法。

方法一：遞歸求解。

linkdelSame(linkhead)

{

linkpointer,temp=head;

if(head-＞next==NULL)

returnhead;

head-＞next=delSame(head-＞next);

pointer=head-＞next;

while(pointer!=NULL)

{

if(head-＞number==pointer-＞number)

{

temp-＞next=pointer-＞next;

free(pointer);

pointer=temp-＞next;

}

else

{

pointer=pointer-＞next;

temp=temp-＞next;

}

}

returnhead;

}

采用遞歸方法效率不夠高效，于是想到了方法二的Hash法。

方法二：使用Hash法，具體過程如下。

1)建立一個hash_map，key為鏈表中已經(jīng)遍歷的結(jié)點內(nèi)容，開始時為空。

2)從頭開始遍歷鏈表中的結(jié)點。

①如果結(jié)點內(nèi)容已經(jīng)在hash_map中存在，則刪除此結(jié)點，繼續(xù)向后遍歷。

②如果結(jié)點內(nèi)容不在hash_map中，則保留此結(jié)點，將結(jié)點內(nèi)容添加到hash_map中，繼續(xù)向后遍歷。

16.

如何合并兩個有序鏈表(非交叉)正確答案：合并兩個有序鏈表(假設鏈表元素為升序排列)，一般可以采用遞歸和非遞歸兩種方式實現(xiàn)。

首先看遞歸方式，設兩個鏈表的頭結(jié)點分別為head1、head2，如果head1為空，則直接返回head2；如果head2為空，則直接head1。如果headl鏈表的第一個數(shù)據(jù)小于head2鏈表的第一個數(shù)據(jù)，則把head1鏈表的第一個元素存儲到新合并的鏈表中，遞歸遍歷去除第一個元素的head1鏈表和整個head2鏈表。如果head1鏈表的第一個元素大于或等于head2鏈表的第一個元素，則把head2鏈表的第一個元素存儲到新合并的鏈表中，遞歸遍歷整個head1鏈表，去除第一個元素的head2鏈表。具體過程如下：

Node*MergeRecursive(Node*head1,Node*head2)

{

if(head1==NULL)

returnhead2;

if(head2==NULL)

returnhead1;

Node*head=NULL;

if(head1-＞data＜head2-＞data)

{

head=head1;

head-＞next=MergeRecursive(head1-＞next,head2);

}

else

{

head=head2;

head-＞next=MergeRecursive(head1,head2-＞next);

}

returnhead;

}

使用非遞歸的方式時，分別用指針head1、head2來遍歷兩個鏈表，如果當前head1指向的數(shù)據(jù)小于head2指向的數(shù)據(jù)，則將head1指向的結(jié)點歸入合并后的鏈表中；否則將head2指向的結(jié)點歸入合并后的鏈表中。如果有一個鏈表遍歷結(jié)束，則把未結(jié)束的鏈表連接到合并后的鏈表尾部。具體過程如下：

Node*Merge(Node*head,Node*head1,Node*head2)

{

Node*trap=head;

while(NULL!=head1&&NULL!=head2)

{

if(head1-＞data＜head2-＞data)

{

tmp-＞next=head1;

tmp=head1;

head1=head1-＞next;

}

else

{

tmp-＞next=head2;

tmp=head2;

head2=head2-＞next;

}

}

if(NULL!=head1)

{

tmp-＞next=head1;

}

if(NULL!=head2)

{

tmp-＞next=head2;

}

returntmp;

17.

什么是循環(huán)鏈表正確答案：循環(huán)鏈表(CircularLinkedList)是一種首尾相接的鏈表，它與單鏈表的唯一區(qū)別在于對尾結(jié)點的處理，因為在單鏈表中尾結(jié)點的指針域NULL改為指向頭結(jié)點就得到了單循環(huán)鏈表。

在單循環(huán)鏈表上的操作基本上與非循環(huán)鏈表相同，只是將原來判斷指針是否為NULL變?yōu)槭欠袷穷^指針而已，沒有其他較大的變化。圖1所示為帶頭結(jié)點的單循環(huán)鏈表。

圖1帶頭結(jié)點的單循環(huán)鏈表

a)非空表

b)空表

對于單鏈表只能從頭結(jié)點開始遍歷整個鏈表，而對于單循環(huán)鏈表則可以從表中任意結(jié)點開始遍歷整個鏈表。因為有時需要對鏈表常做的操作是在表尾、表頭進行，此時可以改變一下鏈表的標識方法，不用頭指針而用一個指向尾結(jié)點的指針rear來標識，可以使得操作效率得以提高。例如，用尾指針rear表示的單循環(huán)鏈表查找開始結(jié)點a1和尾結(jié)點an就很方便，此時查找時間復雜度都為O(1)。

例如，對兩個單循環(huán)鏈表H1、H2的連接操作，是將H2的第一個數(shù)據(jù)結(jié)點接到H1的尾結(jié)點，若用頭指針標識，則需要找到第一個鏈表的尾結(jié)點，其時間復雜性為O(n)；而鏈表若用尾指針R1、R2來標識，則時間性能為O(1)。操作如下：

p=R1-＞next;

∥保存R1的頭結(jié)點指針

R1-＞next=R2-＞next-＞next;

∥頭尾連接

free(R2-＞next);

∥釋放第二個表的頭結(jié)點

R2-＞next=p;

∥組成循環(huán)鏈表

具體過程如圖2所示。

圖2單循環(huán)鏈表連接

僅設尾指針rear的單循環(huán)鏈表的實現(xiàn)如下：

#include＜stdio.h＞

#include＜stdlib.h＞

typedefstructnode

{

intdata;

structnode*next;

}linklist;

linklist*rear=NULL;

linklist*CreateSingleLoopList()

∥單循環(huán)鏈表的實現(xiàn)

{

int_data;

linklist*pCurrent,*head;

head=(linklist*)malloc(sizeof(1inklist));

scanf("%d",&_data);

rear-＞data=_data;

rear-＞next=head;

head-＞next=rear;

scanf("%d",&_data);

while(_data!=-1)

{

pCurrent=(linklist*)malloc(sizeof(linklist));

pCurrent-＞data=_data;

rear-＞next=pCurrent;

pCurrent-＞next=head;

rear=pCurrent;

scanf("%d",&_data);

}

returnrear;

voidGetRearHead(linklist*p)

∥取開始結(jié)點和尾結(jié)點

{

printf("%d,",p-＞data);∥終端結(jié)點an

printf("%d,",p-＞next-＞next-＞data);∥開始結(jié)點a1

}

intmain()

{

rear=(linklist*)malloc(sizeof(linklist));

CreateSingleLoopList();

GetRearHead(rear);

return0;

}

18.

如何實現(xiàn)雙向鏈表的插入、刪除操作正確答案：循環(huán)單鏈表的出現(xiàn)，雖然能夠?qū)崿F(xiàn)從任一結(jié)點出發(fā)沿著鏈能找到其前驅(qū)結(jié)點，但是時間復雜度為O(n)。如果希望從鏈表中快速確定某一個結(jié)點的前驅(qū)，另一個解決方法就是在單鏈表的每個結(jié)點里再增加一個指向其前驅(qū)的指針域pr。這樣形成的鏈表中就有兩條方向不同的鏈，被稱為雙向鏈表(DoubleLinkedList)。雙向鏈表簡稱雙鏈表，它是由頭指針head唯一確定的。帶頭結(jié)點的雙鏈表的某些運算變得方便。將頭結(jié)點和尾結(jié)點鏈接起來，為雙循環(huán)鏈表。

帶頭結(jié)點的雙鏈表的結(jié)點結(jié)構(gòu)如圖1所示。

圖1帶頭結(jié)點的雙向鏈表

雙鏈表的形式描述：

typedefstructdlistnode

{

DataTypedata;

structdlistnode*prior,*next;

}DListNode;

typedefDListNode*DLinkList;

DLinkListhead;

由于雙鏈表的對稱性，在雙鏈表中能方便地完成各種插入、刪除操作。

在雙向鏈表第i個結(jié)點P之前插入一個新的結(jié)點，則指針的變化情況如圖2所示。

圖2雙向鏈表插入操作

具體實現(xiàn)代碼如下：

voidDInsertBefore()

{

∥在帶頭結(jié)點的雙鏈表中，將值為x的新結(jié)點插入*p之前，設p不等于NULL

DListNode*s=malloc(sizeof(DListNode));

s-＞data=x;

s-＞prior=p-＞prior;

s-＞next=p;

p-＞prior-＞next=s;

p-＞prior=s;

}

雙鏈表上刪除結(jié)點*p自身的操作如圖3所示。

圖3雙向鏈表的刪除操作

具體實現(xiàn)代碼如下：

voidDDeleteNode(DListNode*p)

{

∥在帶頭結(jié)點的雙鏈表中，刪除結(jié)點*p，設*p為非終端結(jié)點

p-＞prior-＞next=p-＞next;

p-＞next-＞prior=p-＞prior;

free(p);

}

需要注意的是，與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復雜度均為O(1)。

19.

為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好正確答案：尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便。設一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear→next→next和rear，查找時間都是O(1)。

若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。

20.

如何刪除結(jié)點的前驅(qū)結(jié)點正確答案：假設在長度大于1的單循環(huán)鏈表中，既無頭結(jié)點，也無頭指針，s為指向鏈表中某個結(jié)點的指針，如何刪除結(jié)點*s的直接前驅(qū)結(jié)點?

已知指向這個結(jié)點的指針是*s，那么要刪除這個結(jié)點的直接前趨結(jié)點，首先需要找到一個結(jié)點，它的指針域是指向*s的，然后再把這個結(jié)點刪除。具體過程如下：

voidDeleteNode(ListNode*s)

{

ListNode*P,*q;

p=s;

while(p-＞next-＞next!=s)

{

q=p;

p=p-＞next;

}

q-＞next=s;

free(p);

}

21.

如何實現(xiàn)雙向循環(huán)鏈表的刪除與插入操作正確答案：雙向循環(huán)鏈表是雙向鏈表和循環(huán)鏈表的綜合。循環(huán)鏈表與單鏈表相同，是一種鏈式的存儲結(jié)構(gòu)。所不同的是，循環(huán)鏈表的最后一個結(jié)點的指針是指向該循環(huán)鏈表的第一個結(jié)點或表頭結(jié)點，從而構(gòu)成一個環(huán)形的鏈。在雙向鏈表中，結(jié)點除含有數(shù)據(jù)域外，更有兩個鏈域，一個存儲直接后繼結(jié)點地址，一般稱為右鏈域；一個存儲直接前驅(qū)結(jié)點地址，一般稱為左鏈域。

與單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結(jié)點和做成循環(huán)結(jié)構(gòu)，圖1所示為帶頭結(jié)點的雙向循環(huán)鏈表示意圖。

圖1帶頭結(jié)點的雙向循環(huán)鏈表

通過某結(jié)點的指針P即可以直接得到它的后繼結(jié)點的指針p-＞next，也可以直接得到它的前驅(qū)結(jié)點的指針p-＞prior，所以在有些操作中需要找前驅(qū)時，則必須再使用循環(huán)。例如，結(jié)點的刪除操作。

設P是指向雙向循環(huán)鏈表中的某一結(jié)點，即P是該結(jié)點的指針，則p→prior→next表示的是*P結(jié)點之前驅(qū)結(jié)點的后繼結(jié)點的指針，即與P相等，而p→next→prior表示的是*p結(jié)點之后繼結(jié)點的前驅(qū)結(jié)點的指針，也與P相等。

雙向鏈表中結(jié)點的插入：設P指向雙向鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*P的前面，插入過程如圖2所示。

圖2雙向鏈表插入操作

操作如下：

1)s→prjor=p→prior。

2)p→prior→next=s。

3)s→next=p。

4)p→prior=s。

指針操作的順序不是唯一的，但也不是任意的，第一步操作必須要放到第四步操作之前完成，否則*P的前驅(qū)結(jié)點的指針就丟掉了。

雙向鏈表中結(jié)點的刪除：設P指向雙向鏈表中某結(jié)點，刪除*P。操作過程如圖3所示。

圖3雙向鏈表刪除操作

操作如下：

1)p→prior→next=p→next。

2)p→next→prior=p→prior。

3)free(p)。

22.

如何在不知道頭指針的情況下將結(jié)點刪除正確答案：在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點*p從相應的鏈表中刪去?若可以，其時間復雜度各為多少?

下面討論3種鏈表的情況：

1)單鏈表。如果p指向的結(jié)點為鏈表尾結(jié)點，則無法刪除，否則，可以將p指向結(jié)點的數(shù)據(jù)與p的后繼結(jié)點交換，然后刪除p的后繼結(jié)點。

2)雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結(jié)點可以查找到其直接前趨和直接后繼，從而可以刪除該結(jié)點。其時間復雜度為O(1)。

3)單循環(huán)鏈表。根據(jù)已知結(jié)點位置，可以直接得到其后相鄰的結(jié)點位置(直接后繼)，又因為是循環(huán)鏈表，所以可以通過查找得到p結(jié)點的直接前趨。因此，可以刪去p所指的結(jié)點。其時間復雜度應為O(n)。

23.

如何統(tǒng)計一行字符中有多少個單詞正確答案：單詞的數(shù)目可以由空格出現(xiàn)的次數(shù)決定(連續(xù)的若干個空格作為出現(xiàn)一次空格；一行開頭的空格不統(tǒng)計在內(nèi))。如果測出某一個字符為非空格，而它的前面的字符是空格，則表示“新的單詞開始了”，此時使單詞數(shù)count累加1。如果當前字符為非空格而其前面的字符也是非空格，則意味著仍然是原來那個單詞的繼續(xù)，count不應再累加1。前面一個字符是否空格可以從word的值看出來，若word等于0，則表示前一個字符是空格；如果word等于1，意味著前一個字符為非空格。

程序示例如下：

#include＜stdio.h＞

#defineBUFFERSIZE1024

intmain()

{

charstring[BUFFERSIZE];

inti,count=0,word=0;

charc;

gets(string);

for(i=0;(c=string[i])!='\0';i++)

{

if(c=='')

word=0;

elseif(word==0)

{

word=1;

count++;

}

}

printf("一共有單詞%d個n",count);

return0;

}

程序輸出結(jié)果：

iamhehao

一共有單詞3個

上例中(c=string[i])!='\0'的作用是先將字符數(shù)組的某一元素(一個字符)賦給字符變量c，此時賦值表達式的值就是該字符，然后再判定它是否是結(jié)束符。

24.

如何將字符串逆序正確答案：給定一個字符串s，將s中的字符順序顛倒過來，如s="abcd"，逆序后變成s="dcba"。可以采用多種方法對字符串進行逆序，以下將對其中的一些方法進行分析。

(1)普通逆序

直接分配一個與原字符串等長的字符數(shù)組，然后反向拷貝即可。程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*q=s;

while(*q++)

;

q-=2;

char*p=newchar[sizeof(char)*(q-s+2)];

char*r=p;

∥逆序存儲

while(q＞=s)

*p++=*q--;

*p='\0';

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序輸出結(jié)果

dcba

(2)原地逆序

原地逆序不允額外分配空間，就是將字符串兩邊的字符逐個交換。例如，給定字符串“abcd”，逆序的過程分別是交換字符a和d，交換字符b和c。實現(xiàn)原地逆序的方式有以下3種。

1)設置兩個指針，分別指向字符串的頭部和尾部，然后交換兩個指針所指的字符，并向中間移動指針直到交叉。

程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*p=s;

char*q=s;

while(*q)

++q;

q-;

while(q＞p)

{

chart=*P;

*p++=*q;

*q--=t;

}

returns;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序輸出結(jié)果：

dcba

2)遞歸，需要給定逆序的區(qū)間，調(diào)用方法Reverse(s,0,strlen(s))，對字符串s在區(qū)間left和right之間進行逆序，程序代碼示例如下：

char*Reverse(char*s,intleft,intright)

{

if(left＞=right)

returns;

chart=s[left];

s[left]=s[right];

s[right]=t;

Reverse(s,left+1,right-1);

}

3)非遞歸，同樣指定逆序區(qū)間，和方法1)沒有本質(zhì)區(qū)別，一個使用指針，一個使用下標。

char*Reverse(char*s,intLeft,intright)

{

while(left＜right)

{

chart=s[left];

s[left++]=s[right];

s[right--]=t;

}

returns;

}

(3)不允許臨時變量的原地逆序

原地逆序雖然沒有額外分配空間，但還是使用了臨時變量，占用了額外的空間。如果不允許使用額外空間，主要有以下兩種方法：第一種是異或操作，因為異或操作可以交換兩個變量而無需借助第三個變量；第二種是使用字符串的結(jié)束符'\0'所在的位置作為交換空間，但這有個局限，只適合以'\0'結(jié)尾的字符串，對于不支持這種字符串格式的語言，就不能使用了。

1)異或操作。

#include＜stdio.h＞

char*Reverse(char*s)

{

char*r=s;

char*P=s;

while(*(p+1)!='\0')

++p;

while(p＞s)

{

*p=*p^*s;

*s=*p^*s;

*p=*p--^*s++;

}

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序輸出結(jié)果：

dcba

2)使用字符串結(jié)束符'\0'所在的位置作為交換空間。

程序示例如下：

#include＜stdio.h＞

char*Reverse(char*s)

{

char*r=s;

char*p=s;

while(*p!='\0')

++p;

char*q=p-1;

while(q＞s)

{

*p=*q;

*q--=*s;

*s++=*p;

}

*p='\0';

returnr;

}

intmain()

{

chara[]="abcd";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序輸出結(jié)果：

dcba

(4)按單詞逆序

給定一個字符串，按單詞將該字符串逆序。例如。給定“Thisisasentence”，則輸出是“sentenceaisThis”，為了簡化問題，字符串中不包含標點符號。一共分兩個步驟，第一步先按單詞逆序得“sihTsiaecnetnes”，第二步整個句子逆序得到“sentenceaisThis”。

對于步驟一，關(guān)鍵是如何確定單詞，這里以空格為單詞的分界。當找到一個單詞后，就可以使用上面講過的方法將這個單詞進行逆序，當所有的單詞都逆序以后，將整個句子看做一個整體(即一個大的包含空格的單詞)再逆序一次即可。

程序示例如下：

#include＜stdio.h＞

voidReverseWord(char*p,char*q)

{

while(p＜q)

{

chart=*p;

*p++=*q;

*q--=t;

}

}

char*Reverse(char*s)

{

char*p=s;

char*q=s;

while(*q!='\0')

{

if(*q==")

{

ReverseWord(p,q-1);

q++;

p=q;

}

else

q++;

ReverseWord(p,q-1);

ReverseWord(s,q-1);

returns;

}

intmain()

{

chara[]="Iamgladtoseeyou";

intlen=sizeof(a)/sizeof(a[0]);

printf("%s\n",Reverse(a));

return0;

}

程序輸出結(jié)果：

youseetogladamI

引申：如何實現(xiàn)逆序打印?

與上題類似，還有一類題目要求逆序輸出，而不要求真正地逆序存儲。對于這個問題，可以首先求出字符串長度，然后反向遍歷即可。程序示例如下：

#include＜stdio.h＞

#include＜string.h＞

voidReversePrint(constchar*s)

{

intlen=strlen(s);

for(inti=len-1;i＞=0;--i)

printf("%c",s[i]);

}

intmain()

{

chara[]="abcd";

ReversePrint(a);

printf("\n");

return0;

}

程序輸出結(jié)果：

dcba

如果不想求字符串的長度，可以先遍歷到末尾，然后再遍歷回來，這要借助字符串的結(jié)束符'\0'。程序代碼示例如下：

#include＜stdio.h＞

voidReversePrint(constchar*s)

{

constchar*p=s;

while(*p)

*p++;

--p;

while(p＞=s)

{

printf("%c",*p);

--p;

}

}

intmain()

{

chara[]="abcd";

ReversePrint(a);

printf("\n");

return0;

}

對于上述方法，也可以使用遞歸的方式完成。程序示例代碼如下：

voidReversePrint(constchar*s)

{

if(*(s+1)!='\0')

ReversePrint(s+1);

printf("%c",*s);;

}

25.

如何找出一個字符串中第一個只出現(xiàn)一次的字符正確答案：如何找出一個字符串中第一個只出現(xiàn)一次的字符?例如，輸入abac，則輸出b。本題可以采用hash法來實現(xiàn)。首先申請一個長度為256的表，對每個字符hash計數(shù)即可。因為C/C++中的char有3種類型：char、signedchar和unsignedchar。char類型的符號是由編譯器指定的，一般是有符號的，在對字符進行hash時，應該先將字符轉(zhuǎn)為無符號類型；否則當下標為負值時，就會出現(xiàn)越界訪問。

另外，可以用一個buffer數(shù)組記錄當前找到的只出現(xiàn)一次的字符，避免對原字符串進行第二次遍歷。

程序示例如下：

#inc