《數(shù)據(jù)結(jié)構(gòu)與算法》第2章-線性表

數(shù)據(jù)結(jié)構(gòu)與算法

〔C++語言版〕第2章線性表線性表的類型定義根本概念線性表是由n〔n≥0〕個類型相同的數(shù)據(jù)元素組成的有限序列，通常表示為L=(a1,…,ai–1,ai,ai+1,…,an)。其中，L為線性表名稱，ai為組成該線性表的數(shù)據(jù)元素，ai–1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai–1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。當i=1,2,…,n–1時，ai有且僅有一個直接后繼；當i=2,3,…,n時，ai有且僅有一個直接前驅(qū)。線性表的長度就是線性表中元素的個數(shù)n〔n≥0〕。當n=0時，稱為空表。在非空表中的每個數(shù)據(jù)元素都有一個確定的位置，如a1是第一個數(shù)據(jù)元素，an是最后一個數(shù)據(jù)元素，ai是第i個數(shù)據(jù)元素。稱i為數(shù)據(jù)元素ai在線性表中的位序。線性表的類型定義例如，某大學(xué)生命科學(xué)學(xué)院的學(xué)生名冊可視為一個線性表，如圖2.1所示，表中每個數(shù)據(jù)元素由學(xué)號、姓名、性別、年齡、院名稱、系名稱等數(shù)據(jù)項組成。從圖2.1可以看出，學(xué)生名冊線性表是一個相當靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可根據(jù)需要增長或者縮短，即對線性表的數(shù)據(jù)元素不僅可訪問，還可進行插入、刪除等操作。線性表的類型定義抽象數(shù)據(jù)類型描述ADTLinearList{數(shù)據(jù)集合：D={ai|ai/ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai/D,i=2,…,n}數(shù)據(jù)操作：Init_List(&L)//初始化線性表,引用參數(shù),操作對象本身輸入：空。輸出：構(gòu)造一個空的線性表L。Destroy_List(&L)//撤銷線性表輸入：線性表L。輸出：撤銷線性表L。Clear_List(&L)//清空線性表輸入：線性表L。輸出：線性表L重置為空表。線性表的類型定義List_Empty(L)//判斷線性表是否為空輸入：線性表L。輸出：假設(shè)線性表L為空表，那么返回TRUE，否那么返回FALSE。List_Length(L)//求線性表的長度輸入：線性表L。輸出：線性表L中數(shù)據(jù)元素個數(shù)。Get_Elem(L,i,&e)//取線性表中第i個數(shù)據(jù)元素的值輸入：線性表L，1≤i≤ListLength(L)。輸出：用e返回線性線L中第i個數(shù)據(jù)元素的值。LocateElem(L,e,compare())//返回給定值在線性表中的位置輸入：線性表L，compare()是數(shù)據(jù)元素相等判定函數(shù)。輸出：線性表L中第1個與e滿足相等關(guān)系的數(shù)據(jù)元素的位序。假設(shè)這樣的數(shù)據(jù)元素不存在，那么返回值為0。線性表的類型定義Prev_Elem(L,cur_e,&pre_e)//返回當前元素的前一個元素值輸入：線性表L。輸出：假設(shè)cur_e是線性表L的數(shù)據(jù)元素，且不是第一個，那么用pre_e返回它的直接前驅(qū)元素；否那么操作失敗，pre_e無定義。Next_Elem(L,cur_e,&next_e)//返回當前元素的后一個元素值輸入：線性表L。輸出：假設(shè)cur_e是線性表L的數(shù)據(jù)元素，且不是最后一個，那么用next_e返回它的直接后繼元素；否那么操作失敗，next_e無定義。線性表的類型定義Insert_List(&L,i,e)//在線性表的第i個位置之前插入數(shù)據(jù)元素輸入：線性表L，1≤i≤ListLength(L)+1。輸出：在線性表L中第i個位置之前插入新的數(shù)據(jù)元素e，線性表L的長度加1。Delete_List(&L,i,&e)//刪除線性表中第i個數(shù)據(jù)元素輸入：線性表L非空，1≤i≤ListLength(L)。輸出：刪除L中第i個數(shù)據(jù)元素，并用e返回其值，線性表L的長度減1。Traverse_List(L,visit())//遍歷線性表輸入：線性表L。輸出：依次對線性表L的每個數(shù)據(jù)元素調(diào)用visit()進行訪問。一旦visit()失敗，那么操作失敗。}ADTLinearList線性表的類型定義線性表抽象類線性表的類型定義異常類NoMem和OutOfBounds如果分配內(nèi)存失敗，應(yīng)引發(fā)一個異常。有時異?？赡苡蒼ew引發(fā)，而有時那么需要編程者來引發(fā)。為了在所有情形下都能引發(fā)一個異常，本節(jié)定義一個異常類NoMem，非法操作將會簡單地引發(fā)一個類型為NoMem的異常。另外，在刪除操作中，為了從一個表中刪除第k個元素，需要先確認表中包含第k個元素，然后再刪除這個元素。如果表中不存在第k個元素，那么應(yīng)出現(xiàn)一個越界異常，定義為OutOfBounds，每當正在執(zhí)行的函數(shù)中任何一個參數(shù)超出所期望的范圍時，就引發(fā)這種類型的異常。線性表的類型定義線性表的順序存儲結(jié)構(gòu)根本概念線性表的順序表示線性表的順序表示，是指用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素。設(shè)a1的存儲地址為Loc(a1)，每個數(shù)據(jù)元素占用d個字節(jié)存儲單元，那么第i個數(shù)據(jù)元素的地址為Loc(ai)=Loc(ai)+(i–1)×d，1≤i≤n，如下圖：線性表的順序存儲結(jié)構(gòu)Loc(a1)通常稱作線性表的起始位置或基地址。只要確定了存儲線性表的起始位置，線性表中任一個數(shù)據(jù)元素都可隨機存取。因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。線性表的這種機內(nèi)表示稱為線性表的順序存儲結(jié)構(gòu)或順序映射。通常，稱這種存儲結(jié)構(gòu)的線性表為順序表，其特點是以數(shù)據(jù)元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。線性表的順序存儲結(jié)構(gòu)線性表的動態(tài)分配順序存儲結(jié)構(gòu)的描述線性表的長度可變，而且最大存儲空間隨問題的不同而不同，因此需要動態(tài)地分配線性表的空間。在C++語言中，可用動態(tài)分配的一維數(shù)組來表示，描述見如下程序：線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)根本操作線性表的初始化、查找和輸出線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)插入和刪除操作插入操作。線性表的插入操作是指在線性表的第i–1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素b，其結(jié)果是使長度為n的線性表(a1,…,ai–1,ai,…,an)變成長度為n+1的線性表(a1,…,ai–1,b,ai,…,an)，并且數(shù)據(jù)元素ai–1和ai之間的邏輯關(guān)系發(fā)生了變化。在線性表的順序存儲結(jié)構(gòu)中，由于邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，因此需將第i～n〔共n–i+1〕個元素向后移動一個位置，才能反映這個邏輯關(guān)系的變化。如下圖，為了在線性表的第4個和第5個元素之間插入值為25的數(shù)據(jù)元素，那么需要將第5～8個元素依次往后移動一個位置。線性表的順序存儲結(jié)構(gòu)注意，在插入操作期間，可能出現(xiàn)兩類異常：第一類異常發(fā)生的情形是沒有正確指定插入點，如在插入新元素之前，表中元素個數(shù)少于k–1個，或者k＜0，在這種情形下，引發(fā)一個OutOfBounds異常；當表已經(jīng)滿時，會發(fā)生第二類異常，此時數(shù)組中沒有剩余的空間來容納新元素，因此將引發(fā)一個NoMem異常。Insert操作的時間復(fù)雜度為O(length–k)線性表的順序存儲結(jié)構(gòu)刪除操作刪除操作。與線性表的插入運算相反，線性表的刪除操作是使長度為n的線性表(a1,…,ai–1,ai,ai+1,…,an)變?yōu)殚L度為n–1的線性表(a1,…,ai–1，ai+1,…,an)，并且數(shù)據(jù)元素ai–1、ai和ai+1之間的邏輯關(guān)系也會發(fā)生變化，需要把第i+1～n個元素〔共n–i個元素〕依次向前移動一個位置來反映這個變化。如下圖，為了刪除第4個元素，需要將第5～8個元素依次向前移動一個位置。下圖程序中給出了刪除操作的C++代碼。線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)時間復(fù)雜度分析從上述算法可見，當在順序存儲結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要消耗在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。假設(shè)pi是在第i個元素之前插入一個元素的概率，那么在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的期望值為不失一般性，假設(shè)在線性表的任何位置插入元素都是等概率的，即pi=1/(n+1)，上式可化簡為線性表的順序存儲結(jié)構(gòu)對于刪除過程，假設(shè)qi是刪除第i個元素的概率，那么在長度為n的線性表中刪除一個元素時所需移動元素次數(shù)的期望值為同樣假設(shè)是等概率的情況，即qi=1/(n+1)，那么有由此可見，在順序存儲結(jié)構(gòu)的線性表中插入或刪除一個數(shù)據(jù)元素，平均約需移動表中一半元素。假設(shè)表長為n，那么上面的插入算法和刪除算法的時間復(fù)雜度均為O(n)。線性表的順序存儲結(jié)構(gòu)以下是一個使用類LinearList的C++程序，它假定之前的程序均存儲在LinearList.h之中，且異常類定義位于文件exception.h之中。該例如完成以下操作：創(chuàng)立一個大小為5的整數(shù)線性表L；輸出該表的長度〔為0〕；在第0個元素之后插入2；在第一個元素之后插入6和8〔至此，線性表為2，6，8〕；尋找并輸出第一個元素〔為2〕；輸出當前表的長度〔為3〕；刪除并輸出第一個元素。線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)該程序執(zhí)行的結(jié)果如下：例2-1

試利用數(shù)組來實現(xiàn)線性表的插入、刪除、定位操作。例2-1

例2-2一個線性表中的元素按元素值非遞減有序排列，試設(shè)計算法刪除表中多余的值相同的元素。算法一：例2-2算法二：線性表的鏈式存儲結(jié)構(gòu)線性鏈表線性鏈表的定義

線性鏈表是指用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素〔這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的〕，通過存儲數(shù)據(jù)元素信息的數(shù)據(jù)域和直接后繼存儲位置的指針域構(gòu)成數(shù)據(jù)元素ai的存儲映射，即結(jié)點〔node〕，如以下圖所示。n個結(jié)點ai〔1≤i≤n〕鏈接成一個鏈表，即為線性表(a1,a2,…,an)的鏈式存儲結(jié)構(gòu)。由于此鏈表的每個結(jié)點中只包含一個指針域，故又稱線性鏈表或單鏈表。線性表的鏈式存儲結(jié)構(gòu)例如，以下圖所示為一個科研團隊成員的姓名線性表〔孫強，劉萍，張亮，李明，王冰，錢廣，崔齊，吳英〕的線性鏈表存儲結(jié)構(gòu)，整個鏈表的存取由頭指針H開始進行，它指向鏈表中第一個結(jié)點的存儲位置，線性鏈表中最后一個結(jié)點的指針為“空”〔NULL〕。線性表的鏈式存儲結(jié)構(gòu)線性表的單鏈表存儲結(jié)構(gòu)的類定義以下程序定義了LinkNode和LinearListLink類，鏈表對象是線性表抽象類LinearList的派生類，代表整個線性鏈表，它需要記錄首結(jié)點的地址和鏈表中當前結(jié)點個數(shù)等有關(guān)鏈表的信息，并針對其設(shè)置有關(guān)操作。線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)LinearListLink<T>定義為LinkNode<T>的一個友類，所以LinearListLink<T>可訪問LinkNode<T>的所有成員〔包括是私有成員〕。公共成員函數(shù)Length、Find、Delete和Insert由抽象類LinearList繼承而來。假設(shè)L是LinearListLink型變量，那么L可作為一個單鏈表的頭指針，它指向鏈表中的第一個結(jié)點。假設(shè)L為空〔L=NULL〕，那么表示線性表為“空”，線性表的長度為0。有時，在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可不存儲任何信息，也可存儲線性表長度等附加信息；頭結(jié)點的指針域存儲指向第一個結(jié)點的指針〔即第一個元素結(jié)點的存儲位置〕。線性表的鏈式存儲結(jié)構(gòu)線性表的帶頭結(jié)點的單鏈表存儲結(jié)構(gòu)示意圖如下圖為單鏈表的一般表示法。線性表的鏈式存儲結(jié)構(gòu)根本操作以下程序給出了析構(gòu)函數(shù)的代碼，它的時間復(fù)雜度為O(n)，其中n為鏈表的長度。接下來的程序中的代碼分別實現(xiàn)了Length操作和Find操作。Length的時間復(fù)雜度為O(n)，F(xiàn)ind的時間復(fù)雜度為O(k)。Output的時間復(fù)雜度為O(n)，它要求對于類型T必須定義<<操作。線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)單鏈表的插入和刪除運算假設(shè)要在線性表的兩個數(shù)據(jù)元素X和Y之間插入一個數(shù)據(jù)元素Z，p為單鏈表存儲結(jié)構(gòu)中指向結(jié)點的指針，如以下圖〔a〕所示。為插入數(shù)據(jù)元素Z，首先要生成一個數(shù)據(jù)域為Z的結(jié)點，然后插入到單鏈表中。根據(jù)單鏈表的邏輯定義，還需修改結(jié)點X中的指針域，令其指向結(jié)點Z，而結(jié)點Z中的指針域應(yīng)指向結(jié)點Y。插入后的單鏈表如以下圖〔b〕所示。線性表的鏈式存儲結(jié)構(gòu)假設(shè)s為指向結(jié)點Z的指針，那么插入結(jié)點操作可以用語句描述如下：s->next=p->next;p->next=s;反之，如以下圖所示在線性表中刪除元素Y時，僅需修改結(jié)點X中的指針域來實現(xiàn)鏈表中邏輯關(guān)系的變化即可。設(shè)p為指向結(jié)點的指針，那么刪除結(jié)點操作可用語句描述如下：p->next=p->next->next;可見，在單鏈表中插入或刪除一個結(jié)點時，僅需修改指針而無須移動元素。以下程序為Insert和Delete的實現(xiàn)，時間復(fù)雜度均為O(n)。因為在第i個結(jié)點之前插入一個新結(jié)點或刪除第i個結(jié)點，都需要先找到第i–1個結(jié)點，即修改指針的結(jié)點，所以它的時間復(fù)雜度為O(n)。線性表的鏈式存儲結(jié)構(gòu)成員函數(shù)Insert的算法實現(xiàn)：線性表的鏈式存儲結(jié)構(gòu)成員函數(shù)Delete的算法實現(xiàn)：例2-3定義和建立單鏈表，并在鏈表上實現(xiàn)根本的建空表、查找、定位、求表長、插入、刪除、置空運算。結(jié)點結(jié)構(gòu)定義：例2-3建表算法：例2-3例2-3例2-3插入算法：例2-4試設(shè)計算法逆置一個用帶頭結(jié)點的鏈表表示的線性表。算法描述如下：線性表的鏈式存儲結(jié)構(gòu)靜態(tài)鏈表線性表的鏈式存儲結(jié)構(gòu)如上描述的鏈表中，數(shù)組的一個分量表示一個結(jié)點，同時用游標〔指示器cur〕代替指針指示結(jié)點在數(shù)組中的相對位置，如以下圖所示。數(shù)組的第0個分量可看成頭結(jié)點，其指針域指示鏈表的第一個結(jié)點。以下圖〔b〕展示了〔a〕所示線性表在插入數(shù)據(jù)元素“孫晉”之后的狀況，〔c〕那么展示了〔a〕所示線性表在刪除數(shù)據(jù)元素“鄭彬”之后的狀況。為了和指針型描述的線性鏈表相區(qū)別，這種用數(shù)組描述的鏈表稱為靜態(tài)鏈表，它適合在不設(shè)“指針”類型的高級程序設(shè)計語言中使用，雖然預(yù)先需要分配一個較大的空間，但在進行線性表的插入和刪除操作時不需要移動元素，僅需修改指針，因此仍具有鏈式存儲結(jié)構(gòu)的主要優(yōu)點。線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)循環(huán)鏈表循環(huán)鏈表〔circularlinkedlist〕是一種表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)形的鏈式存儲結(jié)構(gòu)，因此從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點。如下圖為單鏈的循環(huán)鏈表。循環(huán)鏈表的操作和線性鏈表根本一致，差異在于，判別鏈表中最后一個結(jié)點的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點”。線性表的鏈式存儲結(jié)構(gòu)雙向鏈表在需要頻繁地同時訪問前驅(qū)和后繼結(jié)點時，可采用另一種鏈表結(jié)構(gòu)，即雙向鏈表。所謂雙向鏈表，就是每個結(jié)點都有兩個指針域，一個指向直接后繼結(jié)點，另一個指向直接前驅(qū)結(jié)點，以下圖給出了結(jié)點結(jié)構(gòu)和表結(jié)構(gòu)。線性表的鏈式存儲結(jié)構(gòu)雙向鏈表的類定義：線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)在雙向鏈表中，假設(shè)p為指向表中某結(jié)點的指針，那么顯然有p->next->prior=p->prior->next=p。對雙向鏈表進行插入和刪除時需同時修改兩個方向的指針，它們的算法描述和線性表的操作有很大的不同。以下圖2.16分別顯示了插入和刪除結(jié)點時指針修改的情況。而以下程序分別對應(yīng)插入和刪除操作，兩者時間復(fù)雜度均為O(n)。線性表的鏈式存儲結(jié)構(gòu)插入算法：線性表的鏈式存儲結(jié)構(gòu)刪除算法：例2-5雙向鏈表的定義及插入和刪除操作算法。在雙向鏈表中，每個結(jié)點的指針域有兩個，一個左指針llink，一個右指針rlink，至少一個數(shù)據(jù)域data，如下圖。雙向鏈表可以是循環(huán)的，也可以不是循環(huán)的。對于雙向鏈表〔循環(huán)鏈表〕，假設(shè)p指向表中任一結(jié)點，那么有p=p->llink->rlink=p->rlink->llink。雙向循環(huán)鏈表的定義及插入和刪除一個結(jié)點的算法如下。例2-5結(jié)點結(jié)構(gòu)定義：刪除一個結(jié)點：例2-5插入一個結(jié)點：線性表的鏈式存儲結(jié)構(gòu)順序表和鏈表的比較線性表的應(yīng)用——多項式相加與Josephus問題多項式表示設(shè)一元n次多項式的通用形式為Pn(x)=++…+，其中pi是指數(shù)為ei的項的非零系數(shù)，且滿足0≤e1＜e2＜…＜em＝n，上述情況可考慮采用一個長度為m且每個元素有兩個數(shù)據(jù)項〔系數(shù)項和指數(shù)項〕的線性表Pn(x)：((p1,e1),(p2,e2),…,(pm,em))來存儲，這樣將大大節(jié)省空間。在實際應(yīng)用程序中，假設(shè)只對多項式進行“求值”等不改變多項式的系數(shù)和指數(shù)的運算，那么采用類似于順序表的順序存儲結(jié)構(gòu)即可，否那么應(yīng)采用鏈式存儲表示。本節(jié)將主要討論如何利用線性鏈表的根本操作來實現(xiàn)一元多項式的運算。線性表的應(yīng)用——多項式相加與Josephus問題由上圖中的兩個鏈表表示的多項式相加得到的“和多項式C”鏈表如以下圖所示。線性鏈表類型適用于一般的線性表，而表示一元多項式的應(yīng)該是有序鏈表。線性表的應(yīng)用——多項式相加與Josephus問題多項式的類定義：線性表的應(yīng)用——多項式相加與Josephus問題線性表的應(yīng)用——多項式相加與Josephus問題多項式類的幾種構(gòu)造函數(shù)以及析構(gòu)函數(shù)的定義：線性表的應(yīng)用——多項式相加與Josephus問題線性表的應(yīng)用——多項式相加與Josephus問題多項式相加多項式相加算法：線性表的應(yīng)用——多項式相加與Josephus問題例2-6Josephus問題，設(shè)有n個人圍坐一圈。從第s人開始進行1到m報數(shù)，數(shù)到第m個人出列。然后，再從出列的下一個人重新開始報數(shù)，數(shù)到第m個人再出列。如此反復(fù)，直到所有的人全部出列為止。現(xiàn)要求按出列次序得出n個人的順序表?，F(xiàn)以n=8，s=1，m=4為例，用圖說明報數(shù)出列的過程，如下圖。圖中用s1作為浮動的指針，指向每次報數(shù)的起始位置。小圓圈內(nèi)的數(shù)字為報數(shù)出列的人員，由圖得到n個人按次序報數(shù)出列的人員順序為④⑧⑤②①③⑦⑥。例2-6例2-6為了用計算機求解，設(shè)想有一組1～n的整數(shù)作為待報數(shù)的序列。將它們置于數(shù)組p中。當p[i]報數(shù)出列時，為了節(jié)省空間，可將p[i]從數(shù)組中刪除并暫存在另一個存儲單元w中，且將p[i+1]～p[n]都向前移動一個位置。再將原保存在w中的p[i]值置于p[n]中，如以下圖所示；下次再對剩下的n–1個元素進行上述操作，再將報數(shù)出列的元素置于p[n–1]中；……；如此反復(fù)，直至只剩下一個元素時，就將其保存在p[1]中原處。此時p中保存了報數(shù)出列的序列元素的逆序，最后再將p數(shù)組中的元素逆轉(zhuǎn)，即得到了按次序報數(shù)出列人員的順序表。例2-6如何確定每次報數(shù)出列的位置？由上圖可見，由于元素出列后，后面的元素都要向前挪動一個位置，因此，本次報數(shù)的出列位置也就是下次報數(shù)的起始位置，s1有雙重含義。因為報數(shù)是首尾連續(xù)進行的，所以可用取模的方法；由這次報數(shù)的起始位置推算得到下次的報數(shù)位置，即是本次報數(shù)的出列位置。設(shè)i為每次參加報數(shù)的人數(shù)，那么列出位置可由下式推算而得：s1←(s1+m–1)ModiJosephus問題算法如下。①賦初值s1←s。②報數(shù)出列，循環(huán)i以–1為步長，從n到2重復(fù)執(zhí)行：〔a〕求“出列”位置s1←(s1+m–1)Modi;ifs1=0thens1←i；〔b〕出列w←p[i]；〔c〕元素前移：循環(huán)j以1為步長，從s1到i–1重復(fù)執(zhí)行；p[j]←p[j+1]；(d)令出列元素于報數(shù)序列之尾p[i]←w；③逆轉(zhuǎn)出列的序列，循環(huán)k以i為步長，從i到i/2重復(fù)執(zhí)行：〔a〕w←p[k]；〔b〕p[k]←p[n–k+1]；〔c〕p[n–k+1]←w?！沧ⅲ篿/2為不大于i/2的最大整數(shù)?！尝茌敵鲆殉隽械男蛄校惴ńY(jié)束〔具體程序請讀者自己完成〕。本章總結(jié)學(xué)習(xí)要點本章主要介紹線性表的概念及其邏輯結(jié)構(gòu)形式定義；順序和鏈式兩類存儲結(jié)構(gòu)的描述及實現(xiàn)方法；在線性表的順序和鏈式兩類存儲結(jié)構(gòu)上，如何進行數(shù)據(jù)元素的插入、刪除、定位、表的歸并、集合等根本運算，線性表順序與鏈式實現(xiàn)的時空性能比較，以