實訓習題

1.試以單鏈表作為存儲結構，實現將線性表(a0,a1,…,an-1)就地逆置的操作。

2.設ha和hb是兩個單鏈表，其表中元素遞增有序。現將ha和hb合并成一個按元素值遞減有序的單鏈表hc，并要求輔助空間為O(1)。

3.建立一個雙鏈表，從鏈首開始，順序顯示鏈表中的所有結點的數據，然后從鏈尾開始，反序顯示鏈表中所有結點的數據，最后將一個新結點插入到鏈表的表尾。

4.有兩個順序表la和lb，其元素均為非遞減有序排列，編寫一個算法，將它們合并成一個順序表lc，要求lc也是非遞減有序排列，如la=(2,2,3)，lb=(1,3,3,4)，則lc=(1,2,2,3,3,3,4)。

5.將若干城市的信息存入一個帶頭結點的單鏈表中，結點中的城市信息包括城市名和城市的位置坐標。要求：

（1）給定一個城市名，返回其位置坐標；

（2）給定一個位置坐標p和一個距離d，返回所有與p的距離小于d的城市。

6.約瑟夫環問題的描述是任給正整數n與k，按下述方法可得排列1,2,…,n的一個置換。將數字1,2,…,n環形排列，按順時針方向從1開始計數，計滿k時輸出該位置上的數字（并從環中刪去該數字），然后從下一個數字開始繼續從1計數，直到環中所有數字均被輸出為止。例如，當n=10，k=3時，輸出的置換是3,6,9,2,7,18,5,10,4。試設計一個程序，對輸入的任意正整數n與k，輸出相應的置換（分別用順序表和鏈表實現）。