2.5 典型題例

【例2-4】若長度為n的線性表采用順序存儲結構，在它的第i個位置插入元素之前，問首先要移動多少個表元素？如果是刪除第i個位置的元素，則所需移動元素的個數又是多少？

【分析與解答】長度為n的線性表其元素序號為：1,2,3,…,i-1,i,…,n，所采用的是順序存儲結構，要在第i個位置插入元素，那么表中序號為i,…,n的元素就需要向后移動，移動后對應的序號為i+1,…,n+1，移動元素的個數為(n+1)-i，即n-i+1。如果是刪除第i個位置的元素，則表中序號為i+1,…,n的元素就需要向前移動，移動后對應的序號為i,…,n-1，移動元素的個數為(n-1)-(i-1)，即n-i。

【例2-5】對長度為n的線性表，以下操作中，哪些在順序表上實現比在鏈表上實現時間效率更高？

（1）輸出第i（1≤i≤n）個元素的值；

（2）交換第1個元素和第2個元素的值；

（3）順序輸出這n個元素的值；

（4）輸出與給定值x相等的元素在線性表中的序號。

【分析與解答】由順序表和鏈表的存儲特性可知：

（1）輸出第i（1≤i≤n）個元素的值，順序表的時間復雜度為O(1)，鏈表對應的時間復雜度為O(n)；

（2）交換第1個元素和第2個元素的值，順序表的時間復雜度為O(1)，鏈表對應的時間復雜度為O(1)；

（3）順序輸出這n個元素的值，順序表的時間復雜度為O(n)，鏈表對應的時間復雜度為O(n)；

（4）輸出與給定值x相等的元素在線性表中的序號，順序表的時間復雜度為O(n)，鏈表對應的時間復雜度為O(n)。

所以只有操作（1）在順序表上實現比在鏈表上實現時間效率更高。

【例2-6】已知長度為n的線性表l采用順序存儲結構，寫一算法，找出線性表中值最小的數據元素。

【分析與解答】先假設順序表的第0個元素值最小，并將其保存在一臨時變量min中，然后從線性表的第1個元素開始，依次將第1,2,…,n-1個元素的值與min的值進行比較。若某元素的值小于min的值，則將該元素的值存放在min中；若不小于min的值，則min的值保持不變。比較結束后，min中存放的就是線性表中值最小的數據元素。

ElementType Minelem(SeqList l)
{
    min=l.elem[0];
    for(i=1;i<l. listlength;i++)
       {
            if (min>l.elem[i])  min=l.elem[i];
       }
     return(min);
} /* minelem */

【例2-7】已知一帶頭結點的線性表，其頭指針為head，寫一算法，將該鏈表中值為value1的所有結點的值改為value2。

【分析與解答】從鏈表的第一個結點開始，依次判斷當前的鏈結點是否滿足條件（其數據域的值是否為value1），若滿足，則對鏈結點數據域的值進行修改（改為value2），若不滿足，則不修改。當前鏈結點判斷并處理后，接著判斷、處理其后繼結點（新的當前鏈結點），直到鏈尾結點處理結束。

void v1tov2(LinkList h,ElementType value1,ElementType value2)
{
   p=h->next;
   while(p!=NULL)
   {
      if(p->data==value1) p->data=value2;
      p=p->next;
   }
} /* v1tov2 */

【例2-8】假設某航班（NF_B969N/2007.9.20 17:30:00）有N個座位，座位號依次為1,2,3,…,n，航班訂票系統能夠實現訂票、退票，乘客登記表按照乘客姓名的字母順序排列。圖2-15所示是航班訂票系統中所用到的鏈表結構，圖2-15（a）所示是鏈表結點結構，圖2-15（b）所示是已訂座位鏈表，圖2-15（c）所示是未訂座位鏈表。

（1）試給出該系統中鏈表的數據類型定義。

（2）對已訂座位鏈表、未訂座位鏈表，問初始狀態各有多少個結點？

（3）訂票、退票算法對已訂座位鏈表與未訂座位鏈表如何操作？

【分析與解答】由圖2-15可知，已訂座位鏈表與未訂座位鏈表都是帶頭結點的單鏈表，已訂座位鏈表的結點包括旅客姓名、身份證號、座位號與指向下一結點的指針，未訂座位鏈表結點旅客姓名、身份證號為空，座位號（從小到大排列）與指向下一結點的指針不為空。

（1）數據類型（旅客信息）DataType定義如下。

#define MAXNAME旅客姓名最大長度
#define MAXID18 /*身份證號的長度*/
typedef struct
{  char name[MAXNAME];/*旅客姓名*/
   char id[MAXID];/*身份證號*/
} DataType;

單鏈表結點類型定義如下。

typedef struct node
{  DataType passenger;
   int number;    /*座位號*/
   struct node *next;
} DataNode;

指向單鏈表結點的指針類型定義如下。

typedef DataNode *Slink;

（2）用于描述航班座位狀態的有兩條單鏈表：未訂座位與已訂座位單鏈表。兩條單鏈表的初始狀態是已訂座位鏈表是一個只有頭結點的空鏈表，未訂座位鏈表帶頭結點共有N+1個結點，每個結點只存放有座位信息。

（3）訂票、退票的實現就是對已訂座位與未訂座位鏈表的插入與刪除操作。訂票算法刪除未訂座位鏈表中的第一個元素結點，輸入的乘客信息存放在該結點中，并將其插入到按乘客姓名升序排列的已訂座位鏈表中。退票算法根據輸入的乘客身份證號，先在已訂座位鏈表中查找，若找到相應結點，則將其摘下，并插入到按座位號升序排列的未訂座位鏈表中。