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

數(shù)據(jù)結(jié)構(gòu)02線性表第二章線性表2.1線性表地基本概念2.2線性表地順序存儲結(jié)構(gòu)2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4線性表地應(yīng)用:一元多項式地表達(dá)與運算2.1.1線性表地概念線性表是由n(n≥0)個具有相同類型地數(shù)據(jù)元素a1,a2,…,an組成地有限序列。其數(shù)據(jù)元素地個數(shù)n定義為表地長度。當(dāng)n=0時,稱為空表,常將非空地線性表（n>0）記作: L=(a1,a2,…,ai-1,ai,ai+1,…,an-1,an)其,ai為線性表地第i個數(shù)據(jù)元素,稱i為數(shù)據(jù)元素ai在線性表地位序。數(shù)據(jù)元素ai只是一個抽象地符號,其具體意義在不同地情況下各不相同。2.1.1線性表地概念例1:26個英文字母組成地字母表(A,B,C,D,…,Z)是一個長度為26地線性表,表地數(shù)據(jù)元素是單個英文字母。2.1.1線性表地概念例2:學(xué)生地基本信息表學(xué)號姓名性別族籍貫出生日期年級院系學(xué)生類別112060826趙雪清女漢江蘇1988-08-082012計算機學(xué)碩110060943田春峰男漢河南1989-01-202010計算機專碩212060032陳亮男漢湖南1986-11-302012自動化博士113106000686劉明男漢河北1990-11-122013理學(xué)院專碩513106001607卞雯女漢1992-01-082013理學(xué)院學(xué)碩512061654秦羽男漢山西1989-10-132012電光院專碩2.1.1線性表地概念從以上例子可看出非空地線性表地邏輯特征如下:（1）有且僅有一個開始結(jié)點a1,該結(jié)點沒有前驅(qū),僅有一個后繼a2;（2）有且僅有一個終端結(jié)點an,該結(jié)點沒有后繼,僅有一個前驅(qū)an-1;（3）其余地內(nèi)部結(jié)點ai(2≤i≤n-1)都有且僅有一個前驅(qū)ai-1與一個后繼ai+1。線性表是一種典型地線性結(jié)構(gòu)。數(shù)據(jù)地運算是定義在邏輯結(jié)構(gòu)上地,而運算地具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行地。2.1.2線性表地抽象數(shù)據(jù)類型定義線性表地抽象數(shù)據(jù)類型定義:ADTList{ 數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} //稱n為線性表地表長 //稱n=0時地線性表為空表 數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n} 基本操作:……}ADTList2.1.2線性表地抽象數(shù)據(jù)類型定義InitList（&L） 初始條件:無 操作結(jié)果:構(gòu)造一個空地線性表DestroyList（&L） 初始條件:線性表L已存在 操作結(jié)果:銷毀線性表ClearList(&L)（線性表置空） 初始條件:線性表L已存在 操作結(jié)果:將L重置為空表2.1.2線性表地抽象數(shù)據(jù)類型定義ListEmpty(L)（線性表判空） 初始條件:線性表L已存在 操作結(jié)果:若L為空表,則返回TRUE,否則返回FALSEListLength(L)（求線性表地長度） 初始條件:線性表L已存在 操作結(jié)果:返回L數(shù)據(jù)元素地個數(shù),即表地長度GetElem(L,I,&e)（求線性表某個數(shù)據(jù)元素） 初始條件:線性表L已存在,且1≤i≤ListLength(L) 操作結(jié)果:用e返回L第i個元素地值2.1.2線性表地抽象數(shù)據(jù)類型定義LocateElem(L,e,pare())（定位函數(shù)） 初始條件:線性表L已存在,e為給定值,pare()是數(shù)據(jù)元素判定函數(shù) 操作結(jié)果:返回L第個與e滿足pare()地數(shù)據(jù)元素地位序,若這樣地數(shù)據(jù)元素不存在,則返回值為0PriorElem(L,cur_e,&pre_e)（求數(shù)據(jù)元素地前驅(qū)） 初始條件:線性表L已存在 操作結(jié)果:若cur_e是L地數(shù)據(jù)元素,且有前驅(qū),則用pre_e返回它地前驅(qū),如果沒有前驅(qū),則操作失敗,pre_e無定義2.1.2線性表地抽象數(shù)據(jù)類型定義NextElem(L,cur_e,&next_e)（求數(shù)據(jù)元素地后繼） 初始條件:線性表L已存在 操作結(jié)果:若cur_e是L地數(shù)據(jù)元素,且有后繼,則用next_e返回它地后繼,如果沒有后繼,則操作失敗,next_e無定義ListInsert(&L,i,e)（插入數(shù)據(jù)元素）初始條件:線性表L已存在,1≤i≤ListLength(L)+1操作結(jié)果:在L地第i個位置插入新地數(shù)據(jù)元素e,L地長度加線性表地抽象數(shù)據(jù)類型定義ListDelete(&L,I,&e)（刪除數(shù)據(jù)元素） 初始條件:線性表L已存在,1≤i≤ListLength(L) 操作結(jié)果:刪除L地第i個數(shù)據(jù)元素,并用e返回其值,L地長度減1ListTraverse(L,visit())（遍歷線性表） 初始條件:線性表L已存在,visit()為對數(shù)據(jù)元素地訪問函數(shù) 操作結(jié)果:依次對L地每個數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗,則操作失敗2.1.2線性表地抽象數(shù)據(jù)類型定義對于一些更加復(fù)雜地操作,可以用以上地基本操作組合實現(xiàn)例2.1有兩個集合A與B,分別用兩個線性表La與Lb表示,即線性表地數(shù)據(jù)元素為集合地成員。現(xiàn)求一個新地集合A＝A∪B。2.1.2線性表地抽象數(shù)據(jù)類型定義上述問題可演繹為:擴大線性表La,將存在于線性表Lb而不存在于線性表La地數(shù)據(jù)元素插入到線性表La去。2.1.2線性表地抽象數(shù)據(jù)類型定義操作步驟:從線性表Lb依次查看每個數(shù)據(jù)元素,即依次將每個位置上地數(shù)據(jù)元素存入變量e,需調(diào)用GetElem(Lb,i,e);依據(jù)變量e地值,在線性表La進行查訪,即調(diào)用LocateElem(La,e,equal()),判斷La是否已有該值;若不存在,則插入之,即調(diào)用ListInsert(La,n+1,e),其n表示線性表La當(dāng)前地長度。2.1.2線性表地抽象數(shù)據(jù)類型定義voidunion(List&La,ListLb){//將所有在線性表Lb但不在La地數(shù)據(jù)元素插入到La La_len=ListLength(La);//求線性表地長度 Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e);//取Lb第i個數(shù)據(jù)元素賦給e if(!LocateElem(La,e,equal())) ListInsert(La,++La_len,e); //La不存在與e相同地數(shù)據(jù)元素,則插入之 }//for}//union2.1.2線性表地抽象數(shù)據(jù)類型定義例2.2已知線性表La與Lb數(shù)據(jù)元素按值非遞減有序排列,現(xiàn)要求將La與Lb歸并為一個新地線性表Lc,且Lc地數(shù)據(jù)元素不重復(fù)并仍按值非遞減有序排列。例如,設(shè) La=（2,5,8,11) Lb=(2,3,9,11,15,20)則 Lc=(2,3,5,8,9,11,15,20)

2.1.2線性表地抽象數(shù)據(jù)類型定義可演繹為:Lc地數(shù)據(jù)元素,或是La地數(shù)據(jù)元素,或是Lb地數(shù)據(jù)元素,只要先設(shè)Lc為空表,然后將La或Lb地數(shù)據(jù)元素逐個插入到Lc即可。2.1.2線性表地抽象數(shù)據(jù)類型定義為使Lc數(shù)據(jù)元素按值非遞減有序排列,可設(shè)兩個指針i與j分別指向La與Lb某個數(shù)據(jù)元素,若設(shè)i當(dāng)前所指數(shù)據(jù)元素為a,j當(dāng)前所指數(shù)據(jù)元素為b,則當(dāng)前應(yīng)插入到Lc地數(shù)據(jù)元素c為C=a 當(dāng)a≤b時b 當(dāng)a＞b時顯然,指針i與j初值均為1,在所指數(shù)據(jù)元素插入Lc之后,在La或Lb順序后移。思考已知一個非純集合B（集合可能含有重復(fù)元素）,試構(gòu)造一個純集合A,使A只包含B所有值各不相同地數(shù)據(jù)元素。第二章線性表2.1線性表地基本概念2.2線性表地順序存儲結(jié)構(gòu)2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4線性表地應(yīng)用:一元多項式地表達(dá)與運算2.2.1線性表地順序存儲表示線性表線性表地順序存儲結(jié)構(gòu)指地是把線性表地數(shù)據(jù)元素按邏輯順序依次存放在一組地址連續(xù)地存儲單元里,用這種方法存儲地線性表簡稱為順序表。順序表地特點是,表邏輯上相鄰地數(shù)據(jù)元素,存儲時在物理位置上也一定相鄰。2.2.1線性表地順序存儲表示假設(shè)順序表地每個數(shù)據(jù)元素占用m個存儲單元,且數(shù)據(jù)元素地存儲位置定義為其所占地存儲空間第一個單元地存儲地址。則由順序表地特性可知,表相鄰地數(shù)據(jù)元素ai與ai+1地存儲位置LOC(ai)與LOC(ai+1)也是相鄰地,且滿足下列關(guān)系: LOC(ai+1)=LOC(ai)+maiai+1LOC(ai)LOC(ai+1)m個存儲單元2.2.1線性表地順序存儲表示若順序表地起始位置或基地址是LOC(a1),那么順序表地第i個元素ai地存儲位置為: LOC(ai)=LOC(a1)+(i-1)×m已知順序表基地址可得到表任一數(shù)據(jù)元素地地址并訪問它,即: V0=LOC(a1)-m,LOC(ai)=V0+i*m順序表是一種隨機存取存儲結(jié)構(gòu)計算任一數(shù)據(jù)元素地址時間相等2.2.1線性表地順序存儲表示線性表地順序存儲結(jié)構(gòu)示意圖:12…i…n數(shù)據(jù)元素在線性表地位序存儲地址空閑bb+l…b+(i-1)l…b+(n-1)lb+nl…b+(MaxSize-1)la1a2…ai…an…線性表地長度length數(shù)組地長度MaxSize其,b=LOC(a1),即線性表第一個數(shù)據(jù)元素地存儲地址2.2.2順序表地類定義與基本操作在高級語言,一維數(shù)組也具有與順序表相同地如下三個特性:一維數(shù)組地存儲對象也是一組相同類型地數(shù)據(jù);一維數(shù)組也是用一組地址連續(xù)地存儲單元存放數(shù)據(jù);一維數(shù)組地數(shù)據(jù)元素也可以通過數(shù)組下標(biāo)隨機存取。2.2.2順序表地類定義與基本操作可用數(shù)據(jù)類型來描述順序表方式一:<數(shù)據(jù)類型><數(shù)組名>[<常量表達(dá)式>] 例如:inta[5];floatx[100];方式二:<數(shù)據(jù)類型>*<指針變量>=new<數(shù)據(jù)類型>[<常量表達(dá)式>] 例如:int*p=newint[3];數(shù)組容量確定,不能擴充存儲空間可以動態(tài)分配2.2.2順序表地類定義與基本操作順序表地類定義1constintMaxSize=100;typedefintElemType; //ElemType代表數(shù)據(jù)元素地類型classSqList_s{ //順序表類SqList_s private: ElemTypeelem_array[MaxSize]; //一維數(shù)組地容量,MaxSize為可存放地數(shù)據(jù)元素地最大個數(shù) intlength; //線性表地長度,表數(shù)據(jù)元素地實際個數(shù),應(yīng)小于或等于MaxSize public: …//12個基本操作對應(yīng)地成員函數(shù)};2.2.2順序表地類定義與基本操作順序表地類定義2constintLISTINCREMENT=10;typedefintElemType; //ElemType代表數(shù)據(jù)元素地類型classSqList_d{ //順序表類SqList_d private: ElemType*elem; //指針elem指向一維數(shù)組地第一個元素 intlength; //線性表地長度,表數(shù)據(jù)元素地實際個數(shù) intMaxSize;//一維數(shù)組地容量,即動態(tài)分配存儲空間時申請地空間所能存儲地數(shù)據(jù)元素地最大個數(shù) public: …//12個基本操作對應(yīng)地成員函數(shù)};2.2.2順序表地類定義與基本操作順序表地基本操作初始化順序表Step1:動態(tài)分配一組連續(xù)地內(nèi)存空間,作為線性表地存儲空間。Step2:若內(nèi)存分配成功,進行表地初始化,其長度為0,容量為已分配地存儲空間容量。操作步驟:0nelemlengthMaxSize…[0]…[n-1]用C++描述順序表初始化程序代碼為:SqList_d::SqList_d(intn)//構(gòu)造函數(shù){//創(chuàng)建一長度為0,容量為n地空表 elem=(int*)malloc(n*sizeof(int)); //申請表空間 length=0;//空表長為0 MaxSize=n;//初始容量為n}2.2.2順序表地類定義與基本操作銷毀順序表釋放順序表所占用地空間SqList_d::~SqList_d()//析構(gòu)函數(shù){ //釋放表空間 delete[]elem; length=0; MaxSize=0;}時間復(fù)雜度:O(1)空間復(fù)雜度:O(1)2.2.2順序表地類定義與基本操作順序表插入數(shù)據(jù)元素首先分析:插入數(shù)據(jù)元素時,線性表地邏輯結(jié)構(gòu)發(fā)生什么變化？2.2.2順序表地類定義與基本操作(a1,···,ai-1,ai,···,an)變?yōu)?a1,···,ai-1,e,ai,···,an)邏輯關(guān)系<ai-1,ai><ai-1,e>,<e,ai>a1a2···ai-1ai···ana1a2···ai-1eai···an表地長度增加12.2.2順序表地類定義與基本操作voidSqListInsert(inti,inte){ //在第i個位置插入數(shù)據(jù)元素 if(length>=MaxSize) { elem=(int*)realloc(elem,(MaxSize+LISTINCREMENT)*sizeof(int)); MaxSize+=LISTINCREMENT; } if(i<1||i>length+1){ cout<<"插入位置異常";return; } for(intj=length;j>=i;j--) elem[j]=elem[j-1]; elem[i-1]=e;length++;}2.2.2順序表地類定義與基本操作例如:SqListInsert(5,66)102230454226781022304566422678127016位序數(shù)組下標(biāo)2.2.2順序表地類定義與基本操作算法分析設(shè)表地長度為n,則該算法地時間主要耗費在循環(huán)地數(shù)據(jù)元素后移語句上,而該語句地執(zhí)行次數(shù)（即移動數(shù)據(jù)元素地個數(shù)）是n-i+1,由此可知,所需移動地數(shù)據(jù)元素地次數(shù)依賴于:（1）表地長度n;（2）插入位置ii=n+1時,無需移動i=1時,需移動表所有結(jié)點最好情況最壞情況a1a2···ai-1ai···an移動數(shù)據(jù)n-i+1e2.2.2順序表地類定義與基本操作算法地平均移動由于插入可能在表任何位置上進行,因此在長度為n地線性表第i個位置上插入一個數(shù)據(jù)元素,令Eis(n)表示移動數(shù)據(jù)元素次數(shù)地期望值,即平均數(shù)據(jù)移動次數(shù),則在第i個位置上插入一個數(shù)據(jù)元素地移動次數(shù)為n-i+1。代表在第i個位置插入地概率,則 Eis(n)=p1×n+p2×(n-1)+pn×1+pn+1×0若表任何位置i(1≤i≤n+1)上插入元素地概率是均等地,因為順序表有n+1個可插入數(shù)據(jù)元素地位置,則pi=1/(n+1)。因此,在等概率插入地情況下:a1,…ai-1,ai,…,an可能插入地點Eis(n)==[n+(n-1)+···+1+0]=2.2.2順序表地類定義與基本操作結(jié)論:在順序表上做插入運算時,平均移動次數(shù)是表數(shù)據(jù)元素長度地一半。當(dāng)表長n較大時,算法地效率相當(dāng)?shù)?。雖然Eis(n)n地系數(shù)較小,但就數(shù)量級而言,它仍然是線性階地。因此插入算法地平均時間復(fù)雜度為O(n)。2.2.2順序表地類定義與基本操作首先分析:刪除數(shù)據(jù)元素時,線性表地邏輯結(jié)構(gòu)發(fā)生什么變化？順序表刪除數(shù)據(jù)元素2.2.2順序表地類定義與基本操作(a1,···,ai-1,ai,···,an)變?yōu)?a1,···,ai-1,ai+1,···,an)邏輯關(guān)系<ai-1,ai><ai,ai+1><ai-1,ai+1>a1a2···ai-1aiai+1···ana1a2···ai-1ai+1···an表地長度減少12.2.2順序表地類定義與基本操作intSqListDelete(inti){ //刪除表第i個位置數(shù)據(jù)元素 inte; if(length==0){ cout<<"下溢";return-1; } if(i<1||i>length){ cout<<"刪除位置異常";return-1; } e=elem[i-1]; for(intj=i;j<length;j++) elem[j-1]=elem[j]; length--;returne; }2.2.2順序表地類定義與基本操作例如:SqListDelete(3)1022304542267810224566422678127016位序數(shù)組下標(biāo)2.2.2順序表地類定義與基本操作算法分析刪除算法地性能分析與插入算法相似,數(shù)據(jù)元素地移動次數(shù)也是由表長n與位置i決定。i=n時,無需移動i=1時,需移動表剩余所有結(jié)點最好情況最壞情況a1a2···ai-1ai···an移動數(shù)據(jù)n-i2.2.2順序表地類定義與基本操作算法地平均移動由于刪除操作也可能在表任何位置上進行,因此將長度為n地線性表第i個位置上地數(shù)據(jù)元素刪除,令Edl表示所需移動數(shù)據(jù)元素地平均次數(shù),刪除表第i個數(shù)據(jù)元素地移動次數(shù)為n-i,是刪除第i個數(shù)據(jù)元素地概率,則 Edl(n)=p1×(n-1)+p2×(n-2)+···+pn-1×1+pn×0若表任何位置i(1≤i≤n+1)上數(shù)據(jù)元素刪除地概率是均等地,因為順序表有n個可刪除數(shù)據(jù)元素,則pi=1/n。因此,在等概率刪除地情況下:Edl(n)==[(n-1)+(n-2)+···+1+0]=2.2.2順序表地類定義與基本操作結(jié)論:在順序表上做刪除運算時,平均移動次數(shù)約是表數(shù)據(jù)元素長度地一半,因此刪除算法地平均時間復(fù)雜度也是O(n)。2.2.2順序表地類定義與基本操作在順序表查找是否存在值為e地數(shù)據(jù)元素,最簡單地方法是把線性表地各個數(shù)據(jù)元素地值依次與e進行比較。順序表返回數(shù)據(jù)元素地位置（按值查找）2.2.2順序表地類定義與基本操作intLocateElem(inte){//數(shù)據(jù)元素定位,若找到,返回該數(shù)據(jù)元素在表地位序;未找到,返回0。 for(inti=0;i<length;i++) if(elem[i]==e) returni+1; return0;} 2.2.2順序表地類定義與基本操作算法分析線性表按值查找算法地基本操作是進行數(shù)據(jù)元素值地比較。若比較順序是按數(shù)據(jù)元素位序地升序進行,即從第1個數(shù)據(jù)元素開始,則找到第i個數(shù)據(jù)元素需比較地次數(shù)為i(1≤i≤length)。依照數(shù)據(jù)元素插入或刪除地算法性能分析可知,在等概率地情況下,按值查找成功平均需比較(n-1)/2個數(shù)據(jù)元素。所以按值查找算法地平均時間復(fù)雜度為O(n)。2.2.2順序表地類定義與基本操作順序表地按位查找即在順序表查找第i個位置地數(shù)據(jù)元素地值并返回。順序表返回第i個數(shù)據(jù)元素地值（按位查找）2.2.2順序表地類定義與基本操作intGetElem(inti){ //獲取第i個數(shù)據(jù)元素地值 inte; if(i<1||i>length) { cout<<"位置不合法"; return-1; } e=elem[i-1]; returne;}2.2.2順序表地類定義與基本操作算法分析由順序表地定義可知,第i個位置地數(shù)據(jù)元素存儲在數(shù)組下標(biāo)為i-1地位置。由于順序表可隨機存取地特性,可以直接訪問數(shù)組下標(biāo)為i-1位置地數(shù)據(jù)元素并返回其值。因此按位查找算法地平均時間復(fù)雜度為O(1)。2.2.3順序表地應(yīng)用例2.1:有兩個集合A與B,分別用兩個線性表與表示,即線性表地數(shù)據(jù)元素為集合地成員?，F(xiàn)求一個新地集合A＝A∪B。函數(shù)1:voidCreateSqList(intn){//初始化后,創(chuàng)建表長度為n地順序表 if(n>listsize){ cout<<"參數(shù)非法";return; } cout<<"請依次輸入"<<n<<"個元素值:"<<endl; for(inti=1;i<=n;i++) cin>>elem[i-1]; length=n;}2.2.3順序表地應(yīng)用函數(shù)2:voidSqListInsert(inti,inte){//在第i個位置插入元素 if(length>=listsize) { elem=(int*)realloc(elem,(listsize+4)*sizeof(int)); listsize+=4; } if(i<1||i>length+1){cout<<"插入位置異常";return;} for(intj=length;j>=i;j--) elem[j]=elem[j-1]; elem[i-1]=e; length++;}2.2.3順序表地應(yīng)用函數(shù)3:intGetElem(inti){//獲取第i個元素地值 inte; if(i<1||i>length){cout<<"位置不合法";return-1;} e=elem[i-1]; returne;}函數(shù)4:intLocateElem(inte){//元素定位,若找到,返回該元素在表地位序;末找到,返回0。 for(inti=0;i<length;i++) if(elem[i]==e)returni+1; return0;}2.2.3順序表地應(yīng)用主函數(shù):voidmain(){SqListLa(100),Lb(100); intLa_Len,Lb_Len; cout<<"請輸入A集合數(shù)據(jù)元素個數(shù):"; cin>>La_Len;//指定數(shù)據(jù)元素地個數(shù) cout<<endl; La.CreateSqList(La_Len); cout<<"請輸入B集合數(shù)據(jù)元素個數(shù):"; cin>>Lb_Len; cout<<endl; Lb.CreateSqList(Lb_Len); cout<<endl;2.2.3順序表地應(yīng)用主函數(shù): for(inti=1;i<=Lb_Len;i++)//AunionB; { inte=Lb.GetElem(i); if(!La.LocateElem(e)) La.SqListInsert(++La_Len,e); }//endfor La.SqListDisplay();//遍歷輸出La元素}//endmain2.2.4順序表地特點順序表地特點是: 邏輯關(guān)系上相鄰地兩個數(shù)據(jù)元素在物理位置上也相鄰順序表地優(yōu)點是: 節(jié)省存儲空間;隨機存取順序表地缺點是: 插入與刪除操作需移動大量數(shù)據(jù)元素;表容量第二章線性表2.1線性表地基本概念2.2線性表地順序存儲結(jié)構(gòu)2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4線性表地應(yīng)用:一元多項式地表達(dá)與運算2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組地址任意地存儲單元來依次存放線性表地數(shù)據(jù)元素,這組存儲單元既可以是連續(xù)地,也可以是不連續(xù)地,甚至可以零散分布在內(nèi)存地任意位置上。因此,鏈?zhǔn)酱鎯Y(jié)構(gòu)地數(shù)據(jù)元素地邏輯次序與物理次序不一定相同。2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)在線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu),為了表示數(shù)據(jù)元素之間地邏輯關(guān)系,對于每個數(shù)據(jù)元素ai來說,除了存儲其結(jié)點本身地信息外,還需存儲指示其前驅(qū)或后繼結(jié)點地信息。因此,鏈?zhǔn)酱鎯Y(jié)構(gòu)地每個數(shù)據(jù)結(jié)點都需求保存以下兩部分信息:（1）存儲數(shù)據(jù)元素自身信息地部分,稱為數(shù)據(jù)域;（2）存儲與前驅(qū)或后繼結(jié)點地邏輯關(guān)系,稱為指針域。2.3.1單鏈表在鏈?zhǔn)酱鎯Y(jié)構(gòu),如果結(jié)點只包含一個指針域,則稱該線性表為單鏈表。單鏈表datanext 數(shù)據(jù)域存放數(shù)據(jù)元素自身地信息 指針域（鏈域）存放結(jié)點地后繼結(jié)點地地址單鏈表正是通過每個結(jié)點地鏈域next將線性表地個結(jié)點按其邏輯次序鏈接在一起地。2.3.1單鏈表單鏈表每個結(jié)點地存儲地址是存放在其前驅(qū)結(jié)點地next域地,而表地第一個結(jié)點a1無前驅(qū),故應(yīng)設(shè)置一個頭指針head指向a1。此外,由于最后一個結(jié)點an無后繼,故an地指針域為空,即NULL（在圖示常用符號"?"表示）。a1a2a3an^head在鏈?zhǔn)酱鎯Y(jié)構(gòu),邏輯上相鄰地兩個數(shù)據(jù)元素其存儲地物理位置不一定相鄰,因此,這種存儲結(jié)構(gòu)稱為非順序映像或鏈?zhǔn)接诚?。··?.3.1單鏈表例如:線性表地數(shù)據(jù)元素集合為{bat,cat,eat,fat,hat,jat,lat,mat}head:165datanext110hat200……130cat135135eat170……160matNull165bat130170fat110……200jat205205lat160……示意圖2.3.1單鏈表batcateatmat···head由于單鏈表可以由表頭數(shù)據(jù)元素唯一確定,因此單鏈表可以用頭指針地名字來命名。例如:若頭指針名是head,則把鏈表稱為表head。單鏈表地結(jié)點采用結(jié)構(gòu)體類型定義。 typedefintElemType; structNode { ElemTypedata; Node*next; };2.3.1單鏈表Node*p,*head;p為動態(tài)變量指針,它可以存放Node內(nèi)存塊地首地址,能利用標(biāo)準(zhǔn)函數(shù)使得p與一塊內(nèi)存空間關(guān)聯(lián),即p=newNode;//C++p=(structNode*)malloc(sizeof(structNode));/*C*/new分配了一個類型為Node地結(jié)點變量地空間并將其首地址放入指針變量p。datanextp一旦p所指地結(jié)點變量不再需求了,應(yīng)該通過deletep;釋放所指地結(jié)點變量空間。2.3.1單鏈表用C++語言描述線性表地單鏈表存儲結(jié)構(gòu)代碼如下:classLinkList{ private: Node*Head; public: LinkList();//構(gòu)造一個空地線性表L ~LinkList();//銷毀線性表L voidCreateList1(intn);//頭插法創(chuàng)建具有n個數(shù)據(jù)元素地線性鏈表 voidCreateList2(intn);//尾插法創(chuàng)建具有n個數(shù)據(jù)元素地線性鏈表 voidListInsert(inti,inte);//在表第i個位置插入數(shù)據(jù)元素 IntListDelete(inti);//刪除表第i個位置上地數(shù)據(jù)元素 intGetElem(inti);//獲取第i個數(shù)據(jù)元素地值 intLocateElem(inte);//在鏈表查找是否存在數(shù)據(jù)元素e intListLength();//計算表長};2.3.1單鏈表為了操作方便,通常在單鏈表地開始結(jié)點之前附設(shè)一個類型相同地結(jié)點,稱為頭結(jié)點。^Head空表Heada1a2a3an···具有頭結(jié)點地單鏈表2.3.1單鏈表有頭結(jié)點地單鏈表地特點在進行插入刪除等操作時,表第一個結(jié)點（即開始結(jié)點,又稱首結(jié)點或首元結(jié)點）與在表地其它位置上地結(jié)點操作一致,無需進行特殊處理;無論單鏈表是否為空,頭指針始終指向頭結(jié)點。因此,空表與非空表地處理統(tǒng)一,無需進行區(qū)別處理。2.3.1單鏈表1.創(chuàng)建單鏈表鏈表是一個動態(tài)地結(jié)構(gòu),不需求預(yù)分配空間,因此創(chuàng)建鏈表地過程是一個結(jié)點"逐個插入"地過程。問題:假設(shè)線性表結(jié)點地數(shù)據(jù)類型是字符,逐個輸入這些字符型地數(shù)據(jù),并以換行符‘$’為輸入結(jié)束標(biāo)記。創(chuàng)建鏈表地常用方法有以下兩種:1.頭插入法該方法從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放到新結(jié)點地數(shù)據(jù)域,然后將新結(jié)點插入到當(dāng)前鏈表地表頭上,直到讀入結(jié)束代表(比如$）為止。2.3.1單鏈表頭插法建表演示:假設(shè)輸入插入鏈表地字符串為:hdg$headNULLhheadh^dhead存儲池ghead鏈表創(chuàng)建完成2.3.1單鏈表voidCreateList1(intn){//頭插法創(chuàng)建線性表 Node*p,*s; p=Head; cout<<"請依次輸入"<<n<<"個數(shù)據(jù)元素值:"<<endl; for(inti=1;i<=n;i++) { s=newNode;//新建結(jié)點 cin>>s->data; s->next=p->next;//新結(jié)點插入表頭 p->next=s; }}2.3.1單鏈表2.尾插入法為了實現(xiàn)創(chuàng)建鏈表過程結(jié)點地輸入順序與結(jié)點實際地邏輯次序相同,可采用尾插入法。尾插入法每次將新生成地結(jié)點插入到當(dāng)前鏈表地表尾上。為此需要增加一個尾指針r,始終指向當(dāng)前鏈表地尾結(jié)點。voidCreateList2(intn){//尾插法創(chuàng)建線性表 Node*p,*r; p=Head; while(p->next){p=p->next;} cout<<"請依次輸入"<<n<<"個數(shù)據(jù)元素值:"<<endl; for(inti=1;i<=n;i++){ r=newNode;//新建結(jié)點 cin>>r->data; p->next=r;//新結(jié)點插入表尾 p=r; }}2.3.1單鏈表在上述算法,動態(tài)申請結(jié)點空間時未加錯誤處理,在實際使用時,可做下列判定與處理:P=newNode;If(p==NULL)錯誤處理;2.3.1單鏈表2.查找操作①按位序查找鏈?zhǔn)酱鎯Φ鼐€性表,位序上相鄰數(shù)據(jù)元素在存儲位置上不一定相鄰,因此,即使知道被訪問結(jié)點地序號,也不能像順序表那樣按照位序進行直接訪問。在單鏈表,只能從鏈表地頭指針出發(fā),沿next域逐個結(jié)點往下搜索,直到搜索到第i個結(jié)點為止。因此,鏈表不是隨機存取結(jié)構(gòu)。單鏈表沒有表長屬性,當(dāng)移到最后一個結(jié)點之后仍未找到所查元素,則查找過程結(jié)束。2.3.1單鏈表intGetElem(inti){ //獲取第i個數(shù)據(jù)元素地值 Node*p; p=Head->next; intj=1; while(p&&j<i){ p=p->next; j++;} if(!p||j>i)//定位位置不合理:空表或i小于0或i大于表長{ cout<<"位置異常"; return-1;} else returnp->data;}平均時間復(fù)雜度:O(n)2.3.1單鏈表②按值查找按值查找是在鏈表查找是否有結(jié)點值等于給定值key地結(jié)點,若有,則返回首次找到地值為key地結(jié)點地存儲位置;否則返回NULL。查找過程從開始結(jié)點出發(fā),順著鏈表逐個將結(jié)點地值與給定值key作比較。intLocateElem(inte){ intj=1; Node*p; p=Head->next; while(p&&p->data!=e){ p=p->next; j++; } if(p==NULL) return0;//0-不存在,非0-存在返回位置; else returnj;}平均時間復(fù)雜度:O(n)2.3.1單鏈表3.插入操作單鏈表插入操作是將值為e地新結(jié)點s插入到單鏈表地第i個結(jié)點地位置上,即插入到ai-1與ai之間。ai-1aia1a2···j=0j=i-1pess->next=p->next;p->next=s;s=newNode;s->data=e;2.3.1單鏈表voidListInsert(inti,inte){ intj=0; Node*p; p=Head; while(p&&j<i-1)//定位到插入點之前 { p=p->next; j++; } if(!p||j>i-1) { cout<<"位置異常,結(jié)點插入失敗！"; return; }//插入位置不合理,i<0或i>表長

else { Node*s; s=newNode; s->data=e; s->next=p->next; p->next=s; }}平均時間復(fù)雜度:O(n)2.3.1單鏈表4.刪除操作單鏈表地刪除操作是將單鏈表地第i個結(jié)點刪去,即改變ai-1,ai與ai+1之間地鏈接關(guān)系。因為在單鏈表結(jié)點ai地存儲地址是在其前驅(qū)結(jié)點ai-1地指針域next,所以需要首先找到ai-1地存儲位置。然后令p->next指向ai地后繼結(jié)點,即將ai從鏈表上摘下。最后釋放結(jié)點ai地空間。ai-1ai···ai+1···j=0pq=p->next;p->next=q->next;qj=i-1deleteq;2.3.1單鏈表intListDelete(inti){//刪除指定位置元素 inte; Node*p,*q;//設(shè)置伴隨指針 p=Head; intj=0;//計數(shù)器初始化 while(p->next&&j<i-1){ p=p->next; j++;} if(!p->next||j>i-1) { cout<<"位置異常"; return-1; } else { q=p->next; p->next=q->next e=q->data; deleteq; returne; }}平均時間復(fù)雜度:O(n)2.3.1單鏈表從上面地討論可以看出,鏈表上實現(xiàn)插入與刪除運算,無須移動結(jié)點,僅需修改指針。作業(yè):（1）鏈表是有序地,現(xiàn)在插入數(shù)據(jù)x,要求插入后仍然有序（2）鏈表是有序地,現(xiàn)在刪除數(shù)據(jù)x,若x不存在,輸出一段提示信息。要求:按鏈表有頭結(jié)點與無頭結(jié)點兩種情況分別寫出。2.3.2靜態(tài)鏈表靜態(tài)鏈表地概念靜態(tài)鏈表是指用一維數(shù)組表示地單鏈表。在靜態(tài)鏈表,用數(shù)據(jù)元素在數(shù)組地下標(biāo)作為單鏈表地指針。靜態(tài):表地容量是一定地。（數(shù)組地大?。╂湵斫Y(jié)點地鏈域next存放地是其后繼結(jié)點在數(shù)組地位置（即數(shù)組下標(biāo)）靜態(tài)鏈表地特點2.3.2靜態(tài)鏈表靜態(tài)鏈表地類定義classStaticList{public: StaticList(); boolCreate(intlen); boolInsert(constint&e,intindex=1);//默認(rèn)插表頭 boolDelete(int&e,intindex=1);//默認(rèn)刪表尾 voidShow()const;private: NodeStList[MAXSIZE];intLength; intNewSpace();//返回list一個可以用地空間下標(biāo) voidDeleteSpace(intindex);//刪除list地index元素 boolEmpty()const; boolFull()const;};#defineMAXSIZE1000typedefstruct{ intdata; intnext;}Node;2.3.2靜態(tài)鏈表靜態(tài)鏈表地每個數(shù)組地數(shù)據(jù)元素由兩個域構(gòu)成:data:數(shù)據(jù)域,用來存儲數(shù)據(jù)元素自身地信息;next:游標(biāo)域,用來存儲數(shù)據(jù)元素地后繼結(jié)點在數(shù)組地位置。靜態(tài)鏈表圖示0a4-112a30345a18678a229101010a4010121014a31010101610181020a11026102210241026a2101410281030線性鏈表圖示h=5h=1020靜態(tài)鏈表與線性鏈表地區(qū)別？數(shù)組下標(biāo)地址2.3.2靜態(tài)鏈表例:靜態(tài)鏈表地操作設(shè)插入與刪除只在表頭上進行（棧）0179233-14567518923100179233-1456751892310h=7(5,7,2,3)(8,5,7,2,3)表加入x:1.在VList找到一個空閑單元i（比如0）2.令Vlist[i]=x;3.Vlist[i].next=h;4.將靜態(tài)鏈表表頭移至單元i處,即h=i。x72.3.2靜態(tài)鏈表空位置地標(biāo)識:將所有空位置構(gòu)成鏈表,用avail表示鏈?zhǔn)?2179210331923106avail=0h=71.在VList找空位置i2.VList[i].data=xVList[i].next=h;h=i;if(avail==-1) cout<<"表已滿,沒有空余單元";else { i=avail; avail=VList[i].next; VList[i].data=x; VList[i].next=h; h=i;}刪除靜態(tài)鏈表h第一個數(shù)據(jù)元素if(h==1) cout<<"表已空,沒有可刪除地數(shù)據(jù)元素";else{ x=VList[h].data; i=h; h=VList[i].next; VList[i].next=avail; avail=i;}2.3.3循環(huán)鏈表循環(huán)鏈表是一種頭尾相接地鏈表。其特點是無須增加存儲量,僅對表地鏈接方式稍作改變,即可使得表處理更加方便靈活。單循環(huán)鏈表:在單鏈表,將終端結(jié)點地指針域NULL改為指向表頭結(jié)點或開始結(jié)點,得到地單鏈形式地循環(huán)鏈表（只有一個循環(huán)）,并簡稱為單循環(huán)鏈表。從單循環(huán)鏈表任意結(jié)點出發(fā)均可找到表其它結(jié)點。多重循環(huán)鏈表:在某些應(yīng)用,鏈表L里地結(jié)點可能隸屬于多個鏈表（也就是鏈表地結(jié)點有多個指針）,如果這多個鏈表每個都是一個單循環(huán)鏈表,那么L就稱為多重循環(huán)鏈表（鏈表有多個循環(huán)）。2.3.3循環(huán)鏈表為了使空表與非空表地處理一致,循環(huán)鏈表也可設(shè)置一個頭結(jié)點。這樣,空單循環(huán)鏈表僅有一個自成循環(huán)地頭結(jié)點表示.a1a2a3anhead帶頭結(jié)點地空循環(huán)鏈表head…帶頭結(jié)點地非空循環(huán)鏈表在用頭指針表示地單鏈表,找開始結(jié)點a1地時間是O(1),然而要找到終端結(jié)點an,則需從頭指針開始遍歷整個鏈表,其時間是O(n)2.3.2循環(huán)鏈表在很多實際問題,表地操作常常是在表地尾位置上進行,此時頭指針表示地單循環(huán)鏈表就顯得不太方便。為提高此類應(yīng)用地效率,可改用尾指針rear來表示單循環(huán)鏈表,則查找開始結(jié)點a1與尾結(jié)點an都將很方便。a1a2a3an…rear此時,頭結(jié)點地位置是rear->next,尾節(jié)點地位置是rear。顯然,查找頭結(jié)點與尾結(jié)點地時間復(fù)雜度都是O(1)。2.3.2循環(huán)鏈表由于鏈表沒有NULL指針,即鏈表沒有明顯地尾端,可能會使循環(huán)鏈表地操作進入死循環(huán),因此需格外注意。在涉與遍歷操作時,單循環(huán)鏈表地終止條件不再像非循環(huán)鏈表那樣判斷某個指針是否為空,而是判斷該指針是否等于某一指定指針（如頭指針或尾指針）。2.3.4雙向鏈表雙向鏈表:在單鏈表地每個結(jié)點再設(shè)置一個指向其前驅(qū)結(jié)點地指針域prior,這樣形成地鏈表有兩個方向不同地鏈,故稱為雙向鏈表。形式描述為:priordatanexttypedefintElemType;structNode{ ElemTypedata; Node*next; Node*prior;};存儲前驅(qū)結(jié)點地址存儲后繼結(jié)點地址存儲數(shù)據(jù)元素2.3.4雙向鏈表帶頭結(jié)點地空雙循環(huán)鏈表a1a1a1^…h(huán)eadhead帶頭結(jié)點地非空雙循環(huán)鏈表雙鏈表一般由頭指針唯一確定,將頭結(jié)點與尾節(jié)點鏈接起來構(gòu)成雙循環(huán)鏈表。設(shè)指針p指向雙循環(huán)鏈表地某一結(jié)點,則雙循環(huán)鏈表具有如下地對稱性:p->prior->next=p=p->next->prior2.3.4雙向鏈表插入操作:在結(jié)點p前插入一個新結(jié)點sai-1aipess->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;2.3.4雙向鏈表刪除操作:設(shè)結(jié)點p指向待刪除結(jié)點ai-1aiai+1pp->prior->next=p->next;p->next->prior=p->prior;deletep;雙向鏈表地插入,刪除靈活;鏈表維護地工作量大,所需地存儲空間較大。第二章線性表2.1線性表地基本概念2.2線性表地順序存儲結(jié)構(gòu)2.3線性表地鏈?zhǔn)酱鎯Y(jié)構(gòu)2.4線性表地應(yīng)用:一元多項式地表達(dá)與運算2.4.1一元多項式地表示多項式地操作是線性表地典型用例。在數(shù)學(xué)上,一個一元多項式可按升冪表示為:A(x)=a0+a1x+a2x2+…+anxn在計算機,可以用一個線性表(a0,a1,a2,…,an)來表示。但是對于形如 S(x)=5+10x30+90x100地多項式,上述表示方法是否合適？2.4.1一元多項式地表示一般情況下地一元稀疏多項式可寫成An(x)=a1xe1+a2xe2+…+amxem其:ai是指數(shù)為ei地項地非零系數(shù),0≤e1≤e2≤…≤em=n可以用以下線性表表示:((a1,e1),(a2,e2),…,(am,em))2.4.1一元多項式地表示S(x)=5+10x30+90x100例如:用線性表可表示為:((5,0),(10,30),(90,100))2.4.1一元多項式地表示存儲結(jié)構(gòu):用線性鏈表表示。有頭結(jié)點,每個結(jié)點有coef:系數(shù)域exp:指針域,存放非零項地指數(shù)next:指針域:存放指向下一個結(jié)點地指針coefexpnext其,頭結(jié)點地exp為-12.4.1一元多項式地表示一元多項式地抽象數(shù)據(jù)類型定義如下:ADTPolynomial{數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}//ElemSet地每個元素包含一個表示系數(shù)地實數(shù)與表示指數(shù)地整數(shù)數(shù)據(jù)關(guān)系:R={(ai-1,ai)|ai-1,ai∈D,i=2,3,…,n}//ai-1地指數(shù)值＜ai地指數(shù)值2.4.1一元多項式地表示基本操作:DestroyPolyn(&P)