三數(shù)據(jù)結(jié)構(gòu)章線性表

第2章線性表主講：周瑞英主要內(nèi)容2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)插入操作時間復雜度分析刪除操作時間復雜度分析2.3線性表的鏈式表示和實現(xiàn)2.4一元多項式的表示及相加問題描述有一個學生成績表，以升序的方式存儲著N位學生的成績，如下表所示。學號姓名成績20131001宋祖英8020131002孫儷7020131003鄧超7020131004唐嫣7020131005劉德華90問題要求編寫一個學生成績管理系統(tǒng)，實現(xiàn)如下的功能：對學生成績表，不論是插入還是刪除學生成績，都要保證成績按升序排列；可以按給定的姓名或?qū)W號查詢指定學生的信息；可以按升序或降序顯示所有學生的成績。線性表的定義線性表(List)是零個或多個數(shù)據(jù)元素組成的有限序列強調(diào)幾點：它是一個序列，元素之間是有個先來后到的若元素存在多個，則第一個元素無前驅(qū)，而最后一個元素無后繼，其他元素都是有且只有一個前驅(qū)和后繼線性表是有限的。線性表的定義數(shù)學語言描述定義：若線性表記為(a1,…,ai-1,ai,ai+1,…an)則表中ai-1領(lǐng)先與ai，ai領(lǐng)先與ai+1，稱ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素。線性表元素的個數(shù)n(n>=0)定義為線性表的長度，當n=0時，稱為空表。a1…ai-1aiai+1an線性表舉例La=（34,89,765,12,90,-34,22）數(shù)據(jù)元素類型為int。

Ls=(“Hello”,“World”,“China”,“e”)數(shù)據(jù)元素類型為char[10]。Lb=(學生1,學生2,...,學生30)數(shù)據(jù)元素類型為下列所示類型：structstudent{stirngstuno;//學號

stringname;//姓名

intscore;}//成績線性表抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型：把數(shù)據(jù)類型和相關(guān)操作捆綁在一起。線性表的數(shù)據(jù)元素數(shù)據(jù)元素之間的關(guān)系建立在線性表上的基本操作插入、刪除、查找等順序存儲結(jié)構(gòu)指用一組連續(xù)的存儲單元依次存儲線性表中的每個數(shù)據(jù)元素。物理存儲結(jié)構(gòu)線性表順序存儲結(jié)構(gòu)存儲地址內(nèi)存單元Loc(a1)a1Loc(a1)+ca2Loc(a1)+2ca3……Loc(a1)+(i-1)caiLoc(a1)+icai+1Loc(a1)+(n-1)can地址計算方法注意：編程中數(shù)組從0開始計算，而算法中的位置是從1開始。假設(shè)1個元素占用的是c個存儲單元，那么線性表中第i+1個元素和第i個元素的存儲位置關(guān)系是：loc(ai+1)=loc(ai)+c第i個數(shù)據(jù)元素ai存儲位置可以由ai推算得出：loc(a1)+(i-1)*c順序存儲結(jié)構(gòu)的特點邏輯與物理一致：邏輯上相鄰，物理上也相鄰——利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系隨機存?。嚎梢岳蒙鲜鼋o出的數(shù)學公式，快速地計算出任何一個數(shù)據(jù)元素的存儲地址線性表的順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)封裝需要三個屬性：存儲空間的起始位置，數(shù)組data線性表的最大存儲容量：maxsize線性表的當前長度：length注意：數(shù)組的長度是存放線性表的存儲空間總長度，一般初始化后不變。線性表的當前長度是線性表中元素的個數(shù)，是會變化的線性表基本操作懶洋洋來啦，我要站最前面慢羊羊來啦，我站最后面沸羊羊：我肚子疼線性表的基本操作初始化操作：Init_SeqList()插入操作：Insert_SeqList(DataTypea,inti)刪除操作：Delete_SeqList(inti)取表元素：Search_SeqList(inti)定位元素：Search_SeqList(DataTypevalue)求表長度：GetLength()清空操作：Clear()判斷線性表是否為空：IsEmpty()順序存儲結(jié)構(gòu)的類型定義在C語言中，實現(xiàn)線性表的順序存儲結(jié)構(gòu)的類型定義如下

#defineMAXSIZE100typedefstructnode{DataTypedata[MAXSIZE]；

intlength；

}SeqList,*PSeqList；定義一個順序表：SeqListL；初始化順序表初始化順序表就是創(chuàng)建一個用于存放線性表的空的順序表步驟操作1初始化maxsize為實際值2為數(shù)組申請可以存儲maxsize個數(shù)據(jù)元素的存儲空間，數(shù)據(jù)元素的類型由實際應(yīng)用而定3初始化length為0線性表的存儲圖a1a2…aiai+1…amaxsizelength數(shù)組data表長指針PL線性表舉例—羊羊戰(zhàn)隊線性表的最大長度是多少？線性表當前長度是多少？數(shù)組當前存儲最后一個元素的下標是多少？結(jié)論：length=0，空表Length-1是當前存儲最后一個元素下標若順序插入，則插入的下標為lengthlength最大為maxsize0123456內(nèi)存空間99length7001188229033美羊羊：99喜羊羊：88沸羊羊：90懶羊羊：60慢羊羊：206020445544順序表的初始化編程實現(xiàn)初始化線性表存儲空間，當前存儲個數(shù)length為0PSeqListInit_SeqList(){ PSeqListPL; PL=(PSeqList)malloc(sizeof(SeqList)); if(PL) PL->length=0; returnPL;}插入操作插入數(shù)據(jù)元素是指假設(shè)順序表中已有l(wèi)ength(0≤length≤maxsize)個數(shù)據(jù)元素，在第i(1≤i≤length+1)數(shù)據(jù)元素位置插入一個新的數(shù)據(jù)元素第1步：若沒有指定插入位置，則將數(shù)據(jù)元素插入到順序表的最末一個位置；指定插入位置i，若插入位置i<1或i>length+1，則無法插入，否則轉(zhuǎn)入步驟2。插入操作第2步：將第length個至第i個存儲位置（共length-i+1個數(shù)據(jù)元素依次后移后），將新的數(shù)據(jù)元素置于i位置上。第3步：使順序表長度length加1插入操作編程實現(xiàn)intInsert_SeqList(PSeqListPL，inti，DataTypex){intj;if(!PL){printf(“表不存在”);return(-2);}if(PL->length>=MAXSIZE){printf(“表溢出”);return(-1);}/*表空間已滿，不能插入*/if(i<1||i>PL->length+1){

printf(“插入位置不合法”);return(0);}for(j=PL->length-1;j>=i-1;j--)PL->data[j+1]=PL->data[j];/*移動元素*/PL->data[i-1]=x;

/*新元素插入*/PL->length++;

/*表長加1*/return(1);

/*插入成功，返回*/}時間復雜度分析最壞情況分析：i=1表示第1個元素插入結(jié)論：O(n)最好情況分析:i=(n+1)結(jié)論：O(1)for(j=PL->length-1;j>=i-1;j--)PL->data[j+1]=PL->data[j];循環(huán)體次數(shù)=PL->length-1-(i-1)+1n平均時間復雜度如果數(shù)組長度為n，第i(1<=i<=n+1)個位置插入x，那么共需要移動n-i+1個元素等概率情況下，1<=i<=n+1，共有n+1個位置可以插入平均移動次數(shù)：結(jié)論：O(n)12341020349刪除操作刪除操作指假設(shè)順序表中已有l(wèi)ength(1≤length≤maxsize)個數(shù)據(jù)元素，刪除指定位置的數(shù)據(jù)元素第1步，如果線性表為空，或者不符合1≤i≤length，則提示沒有要刪除的元素，否則轉(zhuǎn)入步驟2。刪除操作第2步，將第i+1到第length（共length-i）個數(shù)據(jù)元素依次前移第3步，使順序表的表長度length減1刪除操作編程實現(xiàn)intDelete_SeqList(PSeqListPL,inti){ intj; if(!PL) { printf("表不存在"); return(-1); } if(i<1||i>PL->length) { printf("刪除位置不合法");return0; } for(j=i;j<PL->length;j++) { PL->data[j-1]=PL->data[j]; } PL->length--; return1;}刪除操作時間復雜度分析最壞情況分析：i=1表示刪除第1個元素結(jié)論：O(n)最好情況分析：i=n表示刪除最后1個元素結(jié)論：O(1)for(j=i;j<PL->length;j++){ PL->data[j-1]=PL->data[j]; }平均時間復雜度如果數(shù)組長度為n，第i(1<=i<=n)個位置刪除，那么共需要移動n-i個元素等概率情況下，1<=i<=n，共有n個位置可以刪除平均移動次數(shù)：結(jié)論：O(n)12341020349查找操作intSearch_SeqList(PSeqListPL,inti){ returnPL->data[i-1];}定位操作intSearchx_SeqList(P