第3章線性結構1/25§3.1引子【分析】多項式的關鍵數據是：多項式項數n、每一項的系數ai

（及相應指數i）。有3種不同的方法。一元多項式：主要運算：多項式相加、相減、相乘等方法1：采用順序存儲結構直接表示[例3.1]一元多項式及其運算。例如：下標i012345……a[i]10–3004……表示成：在數據的邏輯結構中,一種常見而且簡單的結構是線性結構，即數據元素之間構成一個有序的序列。方法2：采用順序存儲結構表示多項式的非零項。第3章線性結構§3.1引子每個非零項涉及兩個信息：指數和系數，可以將一個多項式看成是一個(，)二元組的集合。例如：和表示成：數組下標i012……數組下標i0123……系數9153–系數26–4–1382–指數1282–指數19860–P1(x)(b)P2(x)相加過程：比較（9,12）和（26，19），將（26,19）移到結果多項式；繼續比較（9,12）和（–4，8），將（9,12）移到結果多項式；比較（15,8）和（–4，8），15+（–4）=11，不為0，將新的一項（11,8）增加到結果多項式；比較（3,2）和（–13,6）,將（–13,6）移到結果多項式；比較（3,2）和（82,0）,將（3,2）移到結果多項式；將（82,0）直接移到結果多項式。最后得到的結果多項式是：((26,19),(9,12),(11,8),(–13,6),(3,2),(82,0))

2/25方法3：采用鏈表結構來存儲多項式的非零項。每個鏈表結點存儲多項式中的一個非零項，包括系數和指數兩個數據域以及一個指針域，表示為：coefexponlinktypedef

structPolyNode*Polynomial;typedef

structPolyNode{

intcoef;

intexpon; Polynomiallink;}例如:鏈表存儲形式為：第3章線性結構§3.1引子912P1P215832NULL2619–48–136820NULL3/25[例3.2]二元多項式又該如何表示？比如，給定二元多項式：

【分析】可以將上述二元多項式看成關于x的一元多項式

所以，上述二元多項式可以用“復雜”鏈表表示為：第3章線性結構§3.1引子圖3.4二元多項式非零項的鏈表表示12P832NULL9240NULL153–11NULL4/25我們可以研究更一般的有序對象序列的組織與管理方法，下一節將引出線性表的抽象定義，分別討論基于順序存儲和鏈式存儲的線性表實現方法；并探討線性表的基本操作插入元素和刪除元素。第3章線性結構§3.1引子4/25第3章線性結構5/25§3.2線性表的定義與實現【定義】“線性表(LinearList)”是由同一類型的數據元素構成的有序序列的線性結構。線性表中元素的個數稱為線性表的長度；當一個線性表中沒有元素（長度為0）時，稱為空表；表的起始位置稱表頭，表的結束位置稱表尾。,類型名稱：線性表（List）數據對象集：線性表是

n(≥0)個元素構成的有序序列(a1,a2,,an)；

ai+1稱為

ai的直接后繼，

ai-1為

ai的直接前驅；直接前驅和直接后繼反映了元素之間一對一的鄰接邏輯關系。操作集：對于一個具體的線性表LList，一個表示位置的整數i，一個元素XElementType，線性表的基本操作主要有：1、ListMakeEmpty()：初始化一個新的空線性表L；2、ElementType

FindKth(intK,ListL)：根據指定的位序K，返回相應元素

；3、intFind(ElementTypeX,ListL)：已知X，返回線性表L中與X相同的第一個元素的相應位序i；若不存在則返回空；4、voidInsert(ElementTypeX,inti,ListL)：指定位序i前插入一個新元素X；5、voidDelete(inti,ListL)：刪除指定位序i的元素；6、intLength(ListL)：返回線性表L的長度n。線性表的順序存儲實現第3章線性結構§3.2.1線性表的順序存儲實現在內存中用地址連續的一塊存儲空間順序存放線性表的各元素。一維數組在內存中占用的存儲空間就是一組連續的存儲區域。typedef

struct{ ElementTypeData[MAXSIZE];

intLast;/*當前的最后一個元素的下標*/}List;ListL,*PtrL;下標i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last訪問下標為i的元素：L.Data[i]或PtrL->Data[i]線性表的長度：L.Last+1或PtrL->Last+16/251.初始化（建立空的順序表）第3章線性結構主要操作的實現List*MakeEmpty(){List*PtrL;PtrL=(List*)malloc(sizeof(List));PtrL->Last=-1;

returnPtrL;}2.查找intFind(ElementTypeX,List*PtrL){int

i=0;

while(i<=PtrL->Last&&PtrL->Data[i]!=X)

i++;

if(i>PtrL->Last)return-1;/*如果沒找到，返回-1*/

else

returni;/*找到后返回的是存儲位置*/}查找成功的平均比較次數為(n+1)/2，平均時間性能為

O(n)。§3.2.1線性表的順序存儲實現7/25第3章線性結構下標i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下標i01…i-1ii+1…n…SIZE-1Dataa1a2…aiai+1…an…-Last3.插入（第

i(1≤i≤n+1)個位置上插入一個值為X的新元素)先移動，再插入X§3.2.1線性表的順序存儲實現8/25插入算法第3章線性結構voidInsert(ElementTypeX,inti,List*PtrL){intj;

if(PtrL->Last==MAXSIZE-1){/*表空間已滿，不能插入*/printf(＂表滿＂);return;}

if(i<1||i>PtrL->Last+2){/*檢查插入位置的合法性*/printf(＂位置不合法＂);return;}

for(j=PtrL->Last;j>=i-1;j--)PtrL->Data[j+1]=PtrL->Data[j];/*將

ai～

an倒序向后移動*/PtrL->Data[i-1]=X;/*新元素插入*/PtrL->Last++;/*Last仍指向最后元素*/

return;}平均移動次數為n/2，平均時間性能為

O(n)。§3.2.1線性表的順序存儲實現9/25第3章線性結構下標i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下標i01…i-1…n-2n-1…MAXSIZE-1Dataa1a2…ai+1…anan…-Last4.

刪除（刪除表的第

i(1≤i≤n)個位置上的元素)后面的元素依次前移§3.2.1線性表的順序存儲實現10/25刪除算法第3章線性結構voidDelete(inti,List*PtrL){intj;

if(i<1||i>PtrL->Last+1){/*檢查空表及刪除位置的合法性*/printf(“不存在第%d個元素”,i);

return;}

for(j=i;j<=PtrL->Last;j++)PtrL->Data[j-1]=PtrL->Data[j];/*將

ai+1～

an順序向前移動*/PtrL->Last--;/*Last仍指向最后元素*/

return;}平均移動次數為(n-1)/2，平均時間性能為

O(n)。§3.2.1線性表的順序存儲實現11/25線性表的鏈式存儲實現第3章線性結構不要求邏輯上相鄰的兩個數據元素物理上也相鄰，它是通過“鏈”建立起數據元素之間的邏輯關系。因此對線性表的插入、刪除不需要移動數據元素，只需要修改“鏈”。typedef

structNode{ElementTypeData;

structNode*Next;}List;ListL,*PtrL;訪問序號為i的元素？求線性表的長度？§3.2.3線性表的鏈式存儲實現12/251.求表長第3章線性結構主要操作的實現intLength(List*PtrL){List*p=PtrL;/*p指向表的第一個結點*/intj=0;while(p){p=p->Next;j++;/*當前p指向的是第

j個結點*/}returnj;}時間性能為

O(n)。§3.2.3線性表的鏈式存儲實現13/25第3章線性結構2.查找List*FindKth(intK,List*PtrL){List*p=PtrL;

inti=1;

while(p!=NULL&&i<K){p=p->Next;i++;}

if(i==K)returnp;/*找到第K個，返回指針*/

else

returnNULL;

/*否則返回空*/}List*Find(ElementTypeX,List*PtrL){List*p=PtrL;

while(p!=NULL&&p->Data!=X)p=p->Next;

returnp;}（1）按序號查找:

FindKth;（2）按值查找:Find平均時間性能為

O(n)。§3.2.3線性表的鏈式存儲實現14/25第3章線性結構3.插入（在鏈表的第

i-1(1≤i≤n+1)個結點后插入一個值為X的新結點)（1）先構造一個新結點，用s指向；（2）再找到鏈表的第

i-1個結點，用p指向；（3）然后修改指針，插入結點(p之后插入新結點是s)head……pss->Next=p->Next;p->Next=s;

§3.2.3線性表的鏈式存儲實現思考:修改指針的兩個步驟如果交換一下，將會發生什么?15/25插入算法第3章線性結構List*Insert(ElementTypeX,inti,List*PtrL){List*p,*s;

if(i==1){/*新結點插入在表頭*/s=(List*)malloc(sizeof(List));/*申請、填裝結點*/s->Data=X;s->Next=PtrL;

returns;/*返回新表頭指針*/}p=FindKth(i-1,PtrL);/*查找第i-1個結點*/

if(p==NULL){/*第i-1個不存在，不能插入*/printf(＂參數i錯＂);returnNULL;}else{s=(List*)malloc(sizeof(List));/*申請、填裝結點*/s->Data=X;s->Next=p->Next;/*新結點插入在第i-1個結點的后面*/p->Next=s;

returnPtrL;}}平均查找次數為n/2，平均時間性能為

O(n)。空表時的插入要作為特例，除非單鏈表帶虛頭結點。§3.2.3線性表的鏈式存儲實現16/25第3章線性結構（1）先找到鏈表的第

i-1個結點，用p指向；（2）再用指針s指向要被刪除的結點（p的下一個結點）;head……ps=p->Next;4.

刪除（刪除鏈表的第

i(1≤i≤n)個位置上的結點)（3）然后修改指針，刪除s所指結點;（4）最后釋放s所指結點的空間。p->Next=s->next;

free（s）;§3.2.3線性表的鏈式存儲實現思考:操作指針的幾個步驟如果隨意改變，將會發生什么?17/25刪除算法第3章線性結構List*Delete(inti,List*PtrL){List*p,*s;

if(i==1){/*若要刪除的是表的第一個結點*/s=PtrL;/*s指向第1個結點*/PtrL=PtrL->Next;/*從鏈表中刪除*/free(s);/*釋放被刪除結點*/

returnPtrL;}p=FindKth(i-1,PtrL);/*查找第i-1個結點*/

if(p==NULL){printf(“第%d個結點不存在”,i-1);returnNULL;}else

if(p->Next==NULL){printf(“第%d個結點不存在”,i);returnNULL;}else{s=p->Next;/*s指向第i個結點*/p->Next=s->Next;/*從鏈表中刪除*/free(s);

/*釋放被刪除結點*/

returnPtrL;}}平均查找次數為n/2，平均時間性能為

O(n)。第一個結點的刪除要作為特例，除非單鏈表帶虛頭結點。§3.2.3線性表的鏈式存儲實現18/25廣義表【例】如何表示一個單位的人員情況。一種簡單的表示方法是用一個線性表來表示，其先后順序按照進單位的時間順序排列：（張三，李四，王五，錢六，孫七，……）如何體現三個不同部門？比如辦公室、生產部、銷售部。同一個部門放在一起。那么可以用三個有序序列的子表構成的線性表來表示：（（張三，……），（李四，孫七，……），（王五，錢六，……））如果想表示這個單位的負責人是誰，可將負責人作為表的第一元素：（丁一，（張三，……），（李四，孫七，……），（王五，錢六，……））【定義】上述這類表就是一種“廣義表(GeneralizedList)”。廣義表是線性表的推廣。廣義表與線性表一樣，也是

由n個元素組成的有序序列。不同點在于，對于線性表而言，n個元素都是基本的單元素。

而在廣義表中，這些元素不僅可以是單元素也可以是另一個廣義表。第3章線性結構§3.2.4廣義表與多重鏈表19/25廣義表的數據結構可以定義如下：第3章線性結構typedef

structGNode{

intTag;/*標志域：0表示該結點是單元素，1表示該結點是廣義表*/

union{/*子表指針域Sublist與單元素數據域Data復用，即共用存儲空間*/ElementTypeData;

structGNode*SubList;}URegion;

structGNode*Next;/*指向后繼結點*/}GList;圖3.7廣義表結構TagDataNextSubList0丁一0張三0李四0孫七……0錢六…………0王五111NULLHeader§3.2.4廣義表與多重鏈表20/25多重鏈表第3章線性結構【定義】在圖３.7的例子中，廣義表采用鏈表存儲的方式實現。像這種鏈表，其元素可能還是另一個子鏈表的起點指針，叫“多重鏈表”。一般來說，多重鏈表中每個結點的指針域會有多個，如前面的例子包含了Next和SubList兩個指針域。

但包含兩個指針域的鏈表并不一定是多重鏈表，比如雙向鏈表不是多重鏈表。多重鏈表在數據結構實現中有廣泛的用途，基本上如樹、圖這樣相對復雜的數據結構都可以采用多重鏈表的方式實現存儲。§3.2.4廣義表與多重鏈表21/25[例3.3]矩陣可以用二維數組表示，但二維數組表示有兩個缺陷：一是數組的大小需要事先確定，另一個是當矩陣包含許多0元素時，將造成大量的存儲空間浪費。例如，對于下面A和B這樣的“稀疏矩陣”最好是只存儲非0元素。如何用多重鏈表方式實現存儲？【分析】采用一種典型的多重鏈表——十字鏈表來存儲稀疏矩陣。鏈表中用于存放矩陣非0元素的每個結點有兩個指針域：一個是行指針(或稱為向右指針)Right，另一個是列指針（或稱為向下指針）Down。

結點的數據域存放元素的行坐標Row、列坐標Col和數值Value。第3章線性結構§3.2.4廣義表與多重鏈表22/25用一個標識域Tag來區分頭結點和非0元素結點：頭節點的標識值為“Head”，矩陣非0元素結點的標識值為“Term”。第3章線性結構(a)結點的總體結構(b)矩陣非0元素結點(c)頭結點§3.2.4廣義表與多重鏈表TagDownRightURegionDownRightRowColValueTermDownRight