本節書摘來自華章出版社《數據結構與算法 C語言版》一 書中的第2章，第2.7節，作者：徐鳳生，更多章節內容可以訪問云棲社區“華章計算機”公眾號查看。

2.7習題

1描述頭指針、頭結點、首元結點的區別，并說明頭指針和頭結點的作用。
2在順序表中插入和刪除一個結點需平均移動多少個元素？具體的移動次數取決于哪兩個因素？
3在單鏈表和雙向鏈表中，從當前結點出發是否能訪問到任何一個結點？
4若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結構？為什么？
5有線性表(a1,a2,…,ai－1,ai,ai+1,…,an)，采用單鏈表存儲，頭指針為H，每個結點中存放線性表中的一個元素，現查找某個元素值為x的結點。分別寫出下面三種情況的查找語句，要求查找時間盡量短。
（1）線性表中元素無序。
（2）線性表中元素遞增有序。
（3）線性表中元素遞減有序。
6下面是一個算法的核心部分，試說明該算法的功能。

pre=L->next;//L是一個帶頭結點的單鏈表，結點有數據域data和指針域next
if(pre!=NULL)
while(pre->next!=NULL){
p=pre->next;
if(p->data>=pre->data) pre=p;
else return(FALSE);
}
return(TUURE);
7設pa、pb分別指向兩個帶頭結點的有序（從小到大）單鏈表。閱讀下列程序，并回答以下問題：
（1）程序的功能。
（2）s1、s2中的值的含義。
（3）pa、pb中的值的含義。

void exam(LinkList pa,LinkList pa){
p1=pa->next;p2=pb->next;pa->next=NULL;s1=0;s2=0;
while(p1&&p2){
switch{
case(p1->datadata):p=p1;p1=p1->next;s2++;delete(p);
case(p1->data>p2->data):p2=p2->next;
case(p1->data=p2->data):p=p1;p1=p1->next;p->next=pa->next;
pa->next=p;p2=p2->next;s1++;
}
while(p1){p=p1;p1=p1->next;delete(p);s2++}
}

8假設長度大于1的循環單鏈表中，既無頭結點也無頭指針，p為指向該鏈表中某一結點的指針，編寫算法刪除該結點的前驅結點。
9已知兩個單鏈表La和Lb分別表示兩個集合，其元素遞增排列。編寫算法求其交集Lc，要求Lc以元素遞減的單鏈表形式存儲。
10已知單鏈表L是一個遞增有序表，試編寫一個高效算法，刪除表中值大于min且小于max的結點（若表中有這樣的結點），同時釋放被刪除的結點的空間，這里min和max是兩個給定的參數。請分析你的算法的時間復雜度。
11已知非空單鏈表的頭指針為L，試編寫算法，交換p所指結點與其下一個結點在鏈表中的位置（設p指向的不是鏈表中的最后一個結點）。
12線性表中有n個元素，每個元素是一個字符，現存于數組R［n］中，試編寫算法，使R中元素的字符按字母字符、數字字符和其他字符的順序排列。要求利用原來的空間，元素移動次數最小。
13試編寫在帶頭結點的單鏈表中刪除（一個）最小值結點的（高效）算法。
14已知兩個單鏈表La和Lb，其元素遞增排列。編寫算法，將La和Lb歸并成一個單鏈表Lc，其元素遞減排列（允許表中有相同的元素），要求不另辟新的空間。
15設以帶頭結點的雙向循環鏈表表示的線性表L=(a1,a2,…,ai－1,ai,ai+1,…,an)。試編寫一個時間復雜度為O(n)的算法，將L改造為L=(a1,a3,…,an,…,a4,a2)。
16設有一個雙向循環鏈表，每個結點除有prior、data和next三個域外，還有一個訪問頻度域frep。在鏈表被啟用之前，頻度域frep的值為0，而每當對鏈表進行一次LocateElem(L，e)的操作后，被訪問的結點的頻度域frep的值增1，同時調整鏈表中結點之間的順序，使其按發文頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結點總是靠近表頭結點。試寫出符合上述要求的LocateElem操作的算法。

總結

以上是生活随笔為你收集整理的《数据结构与算法 C语言版》—— 2.7习题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。