2.1 線性表的類型定義

2.1.1 線性表的基本概念

線性表是由n（n≥0）個數據元素所構成的有限序列，通常表示為{a1，a2，…，ai，…，an}。其中：下標i標識數據元素在線性表中的位序號；n為線性表的表長，當n=0時，此線性表為空表。線性表中的數據元素ai僅是一個抽象符號，在不同的場合下代表不同的含義，它可能是一個字母、數字、記錄或更復雜的信息。例如：英文字母表{A，B，C，…，Z}；某單位工資表中所有職工的工資按某種順序排列得到表{4315.5，3523.4，2000.0，…，5432.1}。這兩個表都可看成是一個線性表，前者的數據元素是字母，后者的數據元素是實數，并且這兩者的數據元素都屬于簡單類型。又如表2-1所示的是某個班的成績表，這個成績表中的所有記錄序列構成了一個線性表。此線性表中的每一個數據元素是由學號、姓名、大學英語、高等數學、計算機文化基礎和總分6個數據項所構成的記錄。

由上述例子可以得到：對于同一個線性表，其每一個數據元素的值雖然不同，但必須具有相同的數據類型；同時，數據元素之間具有一種線性的或“一對一”的邏輯關系，如圖2-1所示。即在線性表中：

（1）第一個數據元素沒有前驅，這個數據元素被稱為開始結點；

（2）最后一個數據元素沒有后繼，這個數據元素被稱為終端結點；

（3）除第一個和最后一個數據元素之外，其他數據元素有且僅有一個前驅和一個后繼。

具有上述邏輯關系的數據結構被稱為線性結構。線性表就是一種線性結構。

2.1.2 線性表的抽象數據類型描述

線性表的結構簡單，其長度允許動態地增長或收縮；可以對線性表中的任何數據元素進行訪問和查找；數據元素的插入和刪除操作可以在線性表中的任何位置上進行；可以求線性表中指定數據元素的前驅和后繼；可以將兩個線性表合并成一個線性表，或將一個線性表拆分成兩個或多個線性子表等。線性表的抽象數據類型描述如下：

      ADT List{
          數據對象：D={ai|ai∈ElemType，1≤i≤n，n≥0，ElemType是約定的數據元素類型，使用時用戶
                  需根據具體情況進行自定義}

          數據關系：R={＜ai，ai+1＞|ai、ai+1∈D，1≤i≤n-1}
          基本操作：
          InitList（&L）：初始化操作，創建一個空的線性表L。
          DestroyList（&L）：銷毀操作，釋放一個已經存在的線性表L的存儲空間。
          ClearList（&L）：清空操作，將一個已經存在的線性表L置成空表。
          ListEmpty（L）：判空操作，判斷線性表L是否為空，若為空，則函數返回TRUE；否則，函數返回
              FALSE。
          ListLength（L）：求線性表的長度操作，求線性表L中數據元素的個數并返回其值。
          GetElem（L，i，&e）：讀取第i個數據元素操作，求線性表中第i個數據元素的值并用e返回其值。
                其中i的合法范圍為：1≤i≤n。
          ListInsert（&L，i，e）：插入操作，在線性表L的第i個數據元素之前插入一個值為e的數據元素。
                    其中i的合法范圍為：1≤i≤n+1。當i=1 時，在表頭插入e；當i=n+1時，在表尾
                    插入e。
          ListDelete（&L，i，&e）：刪除操作，刪除線性表L中第i個數據元素，并用e返回其值。其中i的
                    合法范圍為：1≤i≤n。
          LocateElem（L，e）：查找操作，查找線性表L中值為e的數據元素，并返回線性表中首次出現指定
                    數據元素e的位序號，若線性表中不包含此數據元素，則返回0。
          DisplayList（L）：輸出操作，輸出線性表L中各個數據元素的值。
      }ADT List

線性表的基本操作的種類往往與它用于解決的實際問題有關，上述給出的僅是其中一些常用的基本操作，讀者在實際應用中可酌情進行增減。如果實現了上述定義的抽象數據類型線性表，則可利用其中的基本操作來實現其他一些更復雜的操作。

【例2-1】編寫算法實現：建立一個線性表{a，z，d，m，z}，然后查找線性表中第一次出現的值為字母z的數據元素，并返回其在線性表中的位置。

【分析】先利用初始化操作InitList（&L）構造一個空的線性表，然后再利用插入操作ListInsert（&L，i，e）將線性表中的5個字母依次插入表的尾部。這樣，一個滿足已知條件的線性表就建立好了。最后調用查找操作LocateElem（L，＇z＇）即可確定第一個字母z在線性表中的位置。

【算法2-1】例2-1的設計算法

      int   CreatLocateOut（List  &L）
      {  InitList（L）；            //創建一個空的線性表L
          ListInsert（L，1，＇a＇）；     //在當前線性表的尾部插入字母a
          ListInsert（L，2，＇z＇）；     //在當前線性表的尾部插入字母z
          ListInsert（L，3，＇d＇）；     //在當前線性表的尾部插入字母d
          ListInsert（L，4，＇m＇）；     //在當前線性表的尾部插入字母m
          ListInsert（L，5，＇z＇）；     //在當前線性表的尾部插入字母z
          return  LocateElem（L，＇z＇）；//在線性表L中找字母z
      }//算法2-1 結束

【例2-2】已知兩個線性表La和Lb中的數據元素按值非遞減有序排列，要求編寫算法實現將La和Lb合并成一個新的線性表Lc，且保持其有序性。

【分析】假設已知La={1，7，10}，Lb={3，4，9，15，27}，則按題目要求其操作結果是得到Lc={1，3，4，7，9，10，15，27}。觀察Lc可知，它就是由La和Lb中所有數據元素按從小到大的順序有序組成的。為此，可以從一個空表Lc出發，然后將La和Lb中的元素按從小到大的順序依次插入Lc中。具體的實現方法是先創建一個空表Lc，且引進i，j，k三個整型變量并置其初始值為1。其中i和j分別是用來從左到右掃描表La和Lb中的數據元素，k用來指示當前Lc的尾部位置。然后比較i與j所指示的數據元素值（假設兩者在可比較的前提下）ai和bj，若ai≤bj，則將較小的ai插入Lc的尾部，且使i指向La中的下一個數據元素，否則將較小的bj插入Lc的尾部，且使j指向Lb中的下一個數據元素。如此重復，直到其中一個表的全部元素都插入Lc中為止。最后再將另一個表中剩余的全部元素依次插入Lc的尾部即可。

【算法2-2】例2-2的設計算法

      voidMergeList（List La，List Lb，List&Lc）
      { int i=1，j=1，k=1；
        ElemType ai，bj；
        int La_length=ListLength（La）；   //求出線性表La的表長
        int Lb_length=ListLength（Lb）；   //求出線性表Lb的表長
        InitList（Lc）；                  //創建一個空的線性表Lc
        //當La和Lb都非空時，則將i與j所指示的小者插入Lc尾部
        while（i＜=La_length&j＜=Lb_length）
        {   GetElem（La，i，ai）；
              GetElem（Lb，j，bj）；
              if（ai＜=bj）
              {  ListInsert（Lc，k++，ai）；
                i++；
              }
              else
              {  ListInsert（Lc，k++，bj）；
                j++；
              }
        }
        while（i＜=La_length） //如果La非空，則將La中剩余的全部元素依次插入Lc尾部
        {  GetElem（La，i++，ai）；
            ListInsert（Lc，k++，ai）；
        }
        while（j＜=Lb_length）//如果Lb非空，則將Lb中剩余的全部元素依次插入Lc尾部
        {  GetElem（Lb，j++，bj）；
            ListInsert（Lc，k++，bj）；
        }
      }//算法2-2 結束

【例2-3】已知線性表L，要求編寫算法實現將L拆分成兩個線性表La和Lb，其中La和Lb分別是由L中的奇數位和偶數位的數據元素所組成的序列。

【分析】假設已知L={1，13，4，17，2，10，9，27，7}，按題目要求其操作得到的結果是La={1，4，2，9，7}，Lb={13，17，10，27}。操作思路也是先創建兩個空的線性表La和Lb，然后將L中奇數位的元素插入當前La的尾部，而L中偶數位的元素則插入當前Lb的尾部。重復此操作，直到L中所有的元素都分別插入La或Lb中為止。

【算法2-3】例2-3的設計算法

      void Division（List L，List&La，List&Lb）
      { ElemType a；
        int i=1，j=1；                //i，j分別用來指示當前表La和Lb中的尾部位置
        int k=1；                     //k用來指示當前表L中讀取的元素位置
        int length=ListLength（L）；      //求出線性表L的表長
        //創建兩個空表La和Lb
        InitList（La）；
        InitList（Lb）；
        for（int k=1；k＜=length；k++）
        {  if（k%2==1）
            {  GetElem（L，k，a）；         //讀取L中奇數位的元素
                ListInsert（La，i++，a）；  //將L中奇數位的元素插入La的尾部
            }
            else
            {  GetElem（L，k，a）；         //讀取L中偶數位的元素
                ListInsert（Lb，j++，a）；  //將L中偶數位的元素插入La的尾部
            }
          }
      }//算法2-3 結束

本章重要的內容更應側重于探討對于抽象數據類型線性表中的基本操作，我們該如何去實現它們。下面就將討論基于以下兩種存儲結構的具體實現方法：一種是基于順序存儲的實現；另一種是基于鏈式存儲的實現。