第2章-線性表數(shù)據(jù)結(jié)構(gòu)課件

第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

線性結(jié)構(gòu) 若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼?？杀硎緸椋海╝1,a2,……,an）線性結(jié)構(gòu)的定義：（邏輯、存儲和運(yùn)算）國際教育學(xué)院第2章線性表線性結(jié)構(gòu) 若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；②除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)表達(dá)式：（a1,a2,……,an）線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是線性表簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是

一對一的國際教育學(xué)院線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；線性結(jié)構(gòu)表達(dá)式：第2章線性表1.了解線性結(jié)構(gòu)的特點(diǎn)2.掌握順序表的定義、查找、插入和刪除3.掌握鏈表的定義、查找、插入和刪除4.能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合

教學(xué)目標(biāo)國際教育學(xué)院第2章線性表1.了解線性結(jié)構(gòu)的特點(diǎn)教學(xué)目標(biāo)國際教育學(xué)院2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)教學(xué)內(nèi)容國際教育學(xué)院2.1線性表的類型定義教學(xué)內(nèi)容國際教育學(xué)院（a1,a2,…ai-1，ai,ai＋1，…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長空表線性終點(diǎn)2.1線性表的類型定義國際教育學(xué)院（a1,a2,…ai-1，ai,ai＋1，…,例1分析26個(gè)英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號姓名性別年齡班級041810205于春梅女1804級計(jì)算機(jī)1班041810260何仕鵬男2004級計(jì)算機(jī)2班041810284王爽女1904級計(jì)算機(jī)3班041810360王亞武男1804級計(jì)算機(jī)4班：：：：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性國際教育學(xué)院例1分析26個(gè)英文字母組成的英文表（A,線性表的基本操作1.初始化線性表LInitList(L)2.銷毀線性表LDestoryList(L)3.清空線性表LClearList(L)4.求線性表L的長度ListLength(L)5.判斷線性表L是否為空IsEmpty(L)6.獲取線性表L中的某個(gè)數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)7.檢索值為e的數(shù)據(jù)元素LocateELem(L,e)

8.返回線性表L中e的直接前驅(qū)元素PriorElem(L,e)9.返回線性表L中e的直接后繼元素NextElem(L,e)

10.在線性表L中插入一個(gè)數(shù)據(jù)元素ListInsert(L,i,e)11.刪除線性表L中第i個(gè)數(shù)據(jù)元素ListDelete(L,i,e)抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院線性表的基本操作抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院算法2.1、2.2、2.7、2.12放在后面統(tǒng)一講解國際教育學(xué)院算法2.1、2.2、2.7、2.12放在后面統(tǒng)一講解國際教育2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。簡言之，邏輯上相鄰，物理上也相鄰順序存儲方法：用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組V[n]來實(shí)現(xiàn)。順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。國際教育學(xué)院2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序表示又稱為順序存元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲國際教育學(xué)院元素n……..元素i……..元素2元素1LoLo+mLo+(#defineLIST_INIT_SIZE100//最大長度#defineLISTINCREMENT10 //分配增量typedefstruct{ElemType*elem;//指向數(shù)據(jù)元素的基地址intlength;//線性表的當(dāng)前長度intlistsize；//當(dāng)前分配的存儲容量}SqList；順序表的類型定義數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：查找、插入、刪除國際教育學(xué)院順序表的類型定義數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：國際教育學(xué)院malloc(m)：開辟m字節(jié)長度的地址空間，并返回這段空間的首地址sizeof(x)：計(jì)算變量x的長度free(p)：釋放指針p所指變量的存儲空間，即徹底刪除一個(gè)變量補(bǔ)充：C語言的動(dòng)態(tài)分配函數(shù)（<stdlib.h>

）國際教育學(xué)院補(bǔ)充：C語言的動(dòng)態(tài)分配函數(shù)（<stdlib.h>）國際教new類型名T（初值列表）功能：申請用于存放T類型對象的內(nèi)存空間，并依初值列表賦以初值結(jié)果值：成功：T類型的指針，指向新分配的內(nèi)存失敗：0（NULL）int*p1=newint;

或int*p1=newint(10);delete指針P功能：釋放指針P所指向的內(nèi)存。P必須是new操作的返回值deletep1;補(bǔ)充：C++的動(dòng)態(tài)存儲分配國際教育學(xué)院new類型名T（初值列表）int*p1=newin函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保持一致參數(shù)傳遞有兩種方式傳值方式（參數(shù)為整型、實(shí)型、字符型等）傳地址參數(shù)為指針變量參數(shù)為引用類型參數(shù)為數(shù)組名補(bǔ)充：C++中的參數(shù)傳遞國際教育學(xué)院函數(shù)調(diào)用時(shí)傳送給形參表的實(shí)參必須與形參在類型、個(gè)數(shù)、順序上保voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(floatm,floatn){floattemp;temp=m;m=n;n=temp;}傳值方式把實(shí)參的值傳送給函數(shù)局部工作區(qū)相應(yīng)的副本中，函數(shù)使用這個(gè)副本執(zhí)行必要的功能。函數(shù)修改的是副本的值，實(shí)參的值不變國際教育學(xué)院voidmain()#include<iostream.傳地址方式－－指針變量作參數(shù)voidmain(){floata,b,*p1,*p2;cin>>a>>b;

p1=&a;p2=&b;swap(p1,p2);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){floatt;t=*m;*m=*n;*n=t;}形參變化影響實(shí)參國際教育學(xué)院傳地址方式－－指針變量作參數(shù)voidmain()#incl傳地址方式－－指針變量作參數(shù)voidmain(){floata,b,*p1,*p2;cin>>a>>b;

p1=&a;p2=&b;swap(p1,p2);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){float*t;t=m;m=n;n=t;}形參變化不影響實(shí)參？？國際教育學(xué)院傳地址方式－－指針變量作參數(shù)voidmain()#incl傳地址方式－－引用類型作參數(shù)引用：它用來給一個(gè)對象提供一個(gè)替代的名字。#include<iostream.h>voidmain(){ inti=5; int&j=i; i=7; cout<<"i="<<i<<"j="<<j;}j是一個(gè)引用類型,代表i的一個(gè)替代名i值改變時(shí),j值也跟著改變，所以會輸出i=7j=7什么是引用？？？國際教育學(xué)院傳地址方式－－引用類型作參數(shù)引用：它用來給一個(gè)對象提供一個(gè)替voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float＆m,float＆n){floattemp;temp=m;m=n;n=temp;}傳地址方式－－引用類型作參數(shù)國際教育學(xué)院voidmain()#include<iostream.（1）傳遞引用給函數(shù)與傳遞指針的效果是一樣的，形參變化實(shí)參也發(fā)生變化。（2）引用類型作形參，在內(nèi)存中并沒有產(chǎn)生實(shí)參的副本，它直接對實(shí)參操作；而一般變量作參數(shù)，形參與實(shí)參就占用不同的存儲單元，所以形參變量的值是實(shí)參變量的副本。因此，當(dāng)參數(shù)傳遞的數(shù)據(jù)量較大時(shí)，用引用比用一般變量傳遞參數(shù)的時(shí)間和空間效率都好。引用類型作形參的三點(diǎn)說明國際教育學(xué)院（1）傳遞引用給函數(shù)與傳遞指針的效果是一樣的，形參變化實(shí)參也（3）指針參數(shù)雖然也能達(dá)到與使用引用的效果，但在被調(diào)函數(shù)中需要重復(fù)使用“*指針變量名”的形式進(jìn)行運(yùn)算，這很容易產(chǎn)生錯(cuò)誤且程序的閱讀性較差；另一方面，在主調(diào)函數(shù)的調(diào)用點(diǎn)處，必須用變量的地址作為實(shí)參。引用類型作形參的三點(diǎn)說明國際教育學(xué)院（3）指針參數(shù)雖然也能達(dá)到與使用引用的效果，但在被調(diào)函數(shù)中需傳地址方式－－數(shù)組名作參數(shù)#include<iostream.h>voidsub(char);voidmain（void）{chara[10]=“hello”;sub(a);cout<<a<<endl;}voidsub(charb[]){b[]=“world”;}傳遞的是數(shù)組的首地址對形參數(shù)組所做的任何改變都將反映到實(shí)參數(shù)組中國際教育學(xué)院傳地址方式－－數(shù)組名作參數(shù)#include<iostream#include<iostream.h>#defineN10intmax(inta[]);voidmain(){ inta[10]; inti,m; for(i=0;i<N;i++) cin>>a[i]; m=max(a); cout<<"themaxnumberis:"<<m;}intmax(intb[]){inti,n;n=b[0];for(i=1;i<N;i++) if(n<b[i])n=b[i];returnn;}用數(shù)組作函數(shù)的參數(shù)，求10個(gè)整數(shù)的最大數(shù)國際教育學(xué)院#include<iostream.h>intmax(i練習(xí)：用數(shù)組作為函數(shù)的參數(shù)，將數(shù)組中n個(gè)整數(shù)按相反的順序存放，要求輸入和輸出在主函數(shù)中完成#include<iostream.h>#defineN10voidsub(intb[]){ inti,j,temp,m; m=N/2; for(i=0;i<m;i++){j=N-1-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}voidmain(){ inta[10],i; for(i=0;i<N;i++) cin>>a[i]; sub(a); for(i=0;i<N;i++) cout<<a[i];}國際教育學(xué)院練習(xí)：用數(shù)組作為函數(shù)的參數(shù)，將數(shù)組中n個(gè)整數(shù)按相反的順序存放線性表的基本操作1.初始化線性表LInitList(L)2.銷毀線性表LDestoryList(L)3.清空線性表LClearList(L)4.求線性表L的長度ListLength(L)5.判斷線性表L是否為空IsEmpty(L)6.獲取線性表L中的某個(gè)數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)7.檢索值為e的數(shù)據(jù)元素LocateELem(L,e)

8.返回線性表L中e的直接前驅(qū)元素PriorElem(L,e)9.返回線性表L中e的直接后繼元素NextElem(L,e)

10.在線性表L中插入一個(gè)數(shù)據(jù)元素ListInsert(L,i,e)11.刪除線性表L中第i個(gè)數(shù)據(jù)元素ListDelete(L,i,e)抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院線性表的基本操作抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院典型操作的算法實(shí)現(xiàn)1.初始化線性表L（參數(shù)用引用）intInitList(SqList&L){

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空間if(L.elem==NULL)exit(OVERFLOW);//分配失敗L.length=0;//空表長度置0returnOK;//成功返回OK}國際教育學(xué)院典型操作的算法實(shí)現(xiàn)1.初始化線性表L（參數(shù)用引用）國際1.初始化線性表L（參數(shù)用指針）intInitList(SqList*L){

L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配空間if(L->elem==NULL)exit(OVERFLOW);//分配失敗L->length=0;//空表長度置0returnOK;//成功返回OK}典型操作的算法實(shí)現(xiàn)國際教育學(xué)院1.初始化線性表L（參數(shù)用指針）典型操作的算法實(shí)現(xiàn)國際教2.銷毀線性表LvoidDestroyList(SqList&L){if(L.elem)free(L.elem);//釋放存儲空間}3.清空線性表LvoidClearList(SqList&L){L.length=0;//將線性表的長度置為0}國際教育學(xué)院2.銷毀線性表L3.清空線性表L國際教育學(xué)院4.

求線性表L的長度intGetLength(SqList&L){return(L.length);}5.判斷線性表L是否為空intIsEmpty(SqList&L){if(L.length==0)returnTRUE;elsereturnFALSE;}國際教育學(xué)院4.求線性表L的長度5.判斷線性表L是否為空國際教育學(xué)院6.獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容//根據(jù)指定位置，獲取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容intGetElem(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;//判斷i值是否合理，若不合理，返回ERROR

e=L.elem[i-1];//第i-1的單元存儲著第i個(gè)數(shù)據(jù)returnOK;}國際教育學(xué)院6.獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容國際教育學(xué)院查找（根據(jù)指定數(shù)據(jù)查找，返回?cái)?shù)據(jù)所在的位置）

順序查找圖示253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功國際教育學(xué)院查找（根據(jù)指定數(shù)據(jù)查找，返回?cái)?shù)據(jù)所在的位置）順序查找圖示22534571648

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失敗國際教育學(xué)院253457164801查找算法時(shí)間效率分析？？？7.在線性表L中查找值為e的數(shù)據(jù)元素intLocateELem(SqList&L,ElemType&e){for(i=0;i<L.length;i++)if(L.elem[i]==e)returni+1;return0;}國際教育學(xué)院查找算法時(shí)間效率分析？？？7.在線性表L中查找值為e的查找成功的平均比較次數(shù)(pi為各項(xiàng)的查找概率)

若查找概率相等，則

查找不成功數(shù)據(jù)比較n

次查找算法時(shí)間效率分析

國際教育學(xué)院查找成功的平均比較次數(shù)(pi為各項(xiàng)的查找概率)

2512478936141234567892512479989361499插入251247893614251247893614251247893614插第4個(gè)結(jié)點(diǎn)之前，移動(dòng)6－4+1次插在第i個(gè)結(jié)點(diǎn)之前，移動(dòng)n-i+1

次插入（插在第i個(gè)結(jié)點(diǎn)之前）

國際教育學(xué)院2512599插入252525插第4個(gè)結(jié)點(diǎn)之前，移動(dòng)6實(shí)現(xiàn)步驟：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?應(yīng)當(dāng)有1≤i≤n+1或i=[1,n+1]將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫到第i個(gè)位置；表長加1。國際教育學(xué)院實(shí)現(xiàn)步驟：國際教育學(xué)院8.在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e

intListInsert(SqList&L,inti,ElemType&e){if(L.length==LIST_INIT_SIZE)returnERROR;//檢查是否有剩余空間if(i<1||i>L.length+1)returnERROR;//檢查i值是否合理

for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//將第i個(gè)之后的依次向后移動(dòng)L.elem[i-1]=e;//將新元素放入第i個(gè)位置L.length++;returnOK;}國際教育學(xué)院8.在線性表L中第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e國際教若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部后移（特別慢）；若要考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)，該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上插入算法時(shí)間效率分析

…國際教育學(xué)院若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；算法時(shí)間主要耗251247893614123456789251247361425124736142512473614刪除刪除（刪除第i個(gè)結(jié)點(diǎn)）

刪除第4個(gè)結(jié)點(diǎn)，移動(dòng)6－4次刪除第i個(gè)結(jié)點(diǎn)，移動(dòng)n-i

次國際教育學(xué)院251252525刪除刪除（刪除第i個(gè)結(jié)點(diǎn)）刪除第4實(shí)現(xiàn)步驟：事先需要判斷，刪除位置i是否合法?應(yīng)當(dāng)有1≤i≤n或i=[1,n]將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長減1。國際教育學(xué)院實(shí)現(xiàn)步驟：國際教育學(xué)院9.將線性表L中第i個(gè)數(shù)據(jù)元素刪除intListDelete(SqList&L,inti,ElemType&e){if(IsEmpty(L))returnERROR;//檢測是否為空if(i<1||i>L.length)returnERROR;//檢查i值是否合理e=L.elem[i-1];//將欲刪除的元素保留在e中

for(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j];//依次將第i+1后的元素向前移L.length--;returnOK;}國際教育學(xué)院9.將線性表L中第i個(gè)數(shù)據(jù)元素刪除國際教育學(xué)院若刪除尾結(jié)點(diǎn)，則根本無需移動(dòng)（特別快）；若刪除首結(jié)點(diǎn)，則表中n-1個(gè)元素全部前移（特別慢）；若要考慮在各種位置刪除（共n種可能）的平均移動(dòng)次數(shù)，該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上刪除算法時(shí)間效率分析

國際教育學(xué)院若刪除尾結(jié)點(diǎn)，則根本無需移動(dòng)（特別快）；算法時(shí)間主要耗費(fèi)在移顯然，順序表的空間復(fù)雜度S(n)=O(1)（沒有占用輔助空間）查找、插入、刪除算法的平均時(shí)間復(fù)雜度為

O(n)國際教育學(xué)院顯然，順序表的空間復(fù)雜度S(n)=O(1)查找、插入、刪除算（1）利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)一致順序表（順序存儲結(jié)構(gòu)）的特點(diǎn)這種存取元素的方法被稱為隨機(jī)存取法（2）在訪問線性表時(shí)，可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲地址。因此可以粗略地認(rèn)為，訪問每個(gè)元素所花時(shí)間相等

國際教育學(xué)院（1）利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前順序表的優(yōu)缺點(diǎn)缺點(diǎn)：在插入、刪除某一元素時(shí)，需要移動(dòng)大量元素浪費(fèi)存儲空間屬于靜態(tài)存儲形式，數(shù)據(jù)元素的個(gè)數(shù)不能自由擴(kuò)充鏈表為克服這一缺點(diǎn)優(yōu)點(diǎn)：存儲密度大（結(jié)點(diǎn)本身所占存儲量/結(jié)點(diǎn)結(jié)構(gòu)所占存儲量）可以隨機(jī)存取表中任一元素國際教育學(xué)院順序表的優(yōu)缺點(diǎn)缺點(diǎn)：鏈表為克服這一缺點(diǎn)優(yōu)點(diǎn)：國際教育學(xué)院2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰線性表的鏈?zhǔn)奖硎居址Q為非順序映像或鏈?zhǔn)接诚瘛H教育學(xué)院2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)奖硎救绾螌?shí)現(xiàn)？通過指針來實(shí)現(xiàn)單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3freefirst(b)經(jīng)過一段運(yùn)行后的單鏈表結(jié)構(gòu)國際教育學(xué)院如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)單鏈表的存儲映像free(a)可利例畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：邏輯結(jié)構(gòu)：（a,b,…,y,z）aheadb/\z……國際教育學(xué)院例畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：各結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域：存儲元素?cái)?shù)值數(shù)據(jù)指針域：存儲直接后繼結(jié)點(diǎn)的存儲位置指針數(shù)據(jù)國際教育學(xué)院各結(jié)點(diǎn)由兩個(gè)域組成：指針數(shù)據(jù)國際教育學(xué)院與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成2、鏈表：

n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)國際教育學(xué)院與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和a1heada2an……h(huán)ead循環(huán)鏈表示意圖：3、單鏈表、雙鏈表、循環(huán)鏈表：

結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表有兩個(gè)指針域的鏈表，稱為雙鏈表首尾相接的鏈表稱為循環(huán)鏈表國際教育學(xué)院a1heada2an……h(huán)ead循環(huán)鏈表示意圖：3、單鏈表、4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針首元結(jié)點(diǎn)是指鏈表中存儲第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息國際教育學(xué)院4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1hea例：一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是31國際教育學(xué)院例：一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,L上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)國際教育學(xué)院上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANL討論1.如何表示空表？有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表非空表 空表0ana0headhead^表頭結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)國際教育學(xué)院討論1.如何表示空表？有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表討論2.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？⒈便于首元結(jié)點(diǎn)的處理首元結(jié)點(diǎn)的地址保存在頭結(jié)點(diǎn)的指針域中,所以在鏈表的第一個(gè)位置上的操作和其它位置一致，無須進(jìn)行特殊處理;⒉便于空表和非空表的統(tǒng)一處理無論鏈表是否為空，頭指針都是指向頭結(jié)點(diǎn)的非空指針，因此空表和非空表的處理也就統(tǒng)一了。

國際教育學(xué)院討論2.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？⒈便于首元結(jié)點(diǎn)的處理討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長度值。頭結(jié)點(diǎn)的數(shù)據(jù)域H國際教育學(xué)院討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為（1）結(jié)點(diǎn)在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰鏈表（鏈?zhǔn)酱鎯Y(jié)構(gòu)）的特點(diǎn)（2）訪問時(shí)只能通過頭指針進(jìn)入鏈表，并通過每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，所以尋找第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等這種存取元素的方法被稱為順序存取法國際教育學(xué)院（1）結(jié)點(diǎn)在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在優(yōu)點(diǎn)數(shù)據(jù)元素的個(gè)數(shù)可以自由擴(kuò)充插入、刪除等操作不必移動(dòng)數(shù)據(jù)，只需修改鏈接指針，修改效率較高鏈表的優(yōu)缺點(diǎn)國際教育學(xué)院優(yōu)點(diǎn)鏈表的優(yōu)缺點(diǎn)國際教育學(xué)院缺點(diǎn)存儲密度小存取效率不高，必須采用順序存取，即存取數(shù)據(jù)元素時(shí)，只能按鏈表的順序進(jìn)行訪問（順藤摸瓜）鏈表的優(yōu)缺點(diǎn)國際教育學(xué)院缺點(diǎn)鏈表的優(yōu)缺點(diǎn)國際教育學(xué)院練習(xí)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。2.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。3.順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。4.線性表若采用鏈?zhǔn)酱鎯r(shí)，結(jié)點(diǎn)之間和結(jié)點(diǎn)內(nèi)部的存儲空間都是可以不連續(xù)的。5.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型×

國際教育學(xué)院練習(xí)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。×國際教育2.3.1線性鏈表（單鏈表）非空表空表單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名若頭指針名是L，則把鏈表稱為表L

國際教育學(xué)院2.3.1線性鏈表（單鏈表）非空表空表單鏈表是由表頭唯一typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLNode*next;//指針域}LNode,*LinkList;

//*LinkList為Lnode類型的指針單鏈表的存儲結(jié)構(gòu)定義LNode*pLinkList

p國際教育學(xué)院typedefstructLNode{單鏈表的存儲結(jié)構(gòu)定LNode*p注意區(qū)分指針變量和結(jié)點(diǎn)變量兩個(gè)不同的概念指針變量p：表示結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p：表示一個(gè)結(jié)點(diǎn)若p->data=ai,則p->next->data=ai+1

國際教育學(xué)院LNode*p注意區(qū)分指針變量和結(jié)點(diǎn)變量兩個(gè)不同的概念若p線性表的基本操作1.初始化線性表LInitList(L)2.銷毀線性表LDestoryList(L)3.清空線性表LClearList(L)4.求線性表L的長度ListLength(L)5.判斷線性表L是否為空IsEmpty(L)6.獲取線性表L中的某個(gè)數(shù)據(jù)元素內(nèi)容GetElem(L,i,e)7.檢索值為e的數(shù)據(jù)元素LocateELem(L,e)

8.返回線性表L中e的直接前驅(qū)元素PriorElem(L,e)9.返回線性表L中e的直接后繼元素NextElem(L,e)10.在線性表L中插入一個(gè)數(shù)據(jù)元素ListInsert(L,i,e)11.刪除線性表L中第i個(gè)數(shù)據(jù)元素ListDelete(L,i,e)抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院線性表的基本操作抽象數(shù)據(jù)類型的定義為：P19國際教育學(xué)院1.初始化單鏈表StatusInitList_L(LinkList&L){//構(gòu)造一個(gè)空的線性表LL=(LinkList)malloc(sizeof(LNode));if(!L)returnOVERFLOW;//3L->next=NULL;returnOK;}國際教育學(xué)院1.初始化單鏈表國際教育學(xué)院2.銷毀單鏈表StatusDestroyList_L(LinkList&L){LinkListp;while(L){p=L;L=L->next;free(p);}returnOK;}國際教育學(xué)院2.銷毀單鏈表國際教育學(xué)院3.清空單鏈表StatusClearList(LinkList&L){

//將L重置為空表LinkListp,q;p=L->next;//p指向第一個(gè)結(jié)點(diǎn)while(p)//沒到表尾{q=p->next;free(p);p=q;}L->next=NULL;//頭結(jié)點(diǎn)指針域?yàn)榭誶eturnOK;}國際教育學(xué)院3.清空單鏈表國際教育學(xué)院4.求線性表L的長度intListLength_L(LinkListL){//返回L中數(shù)據(jù)元素個(gè)數(shù)LinkListp;p=L->next;//p指向第一個(gè)結(jié)點(diǎn)i=0;while(p){//遍歷單鏈表,統(tǒng)計(jì)結(jié)點(diǎn)數(shù)

i++;p=p->next;}

returni;}國際教育學(xué)院4.求線性表L的長度國際教育學(xué)院5.判斷線性表L是否為空StatusListEmpty(LinkListL){//若L為空表，則返回TRUE，否則返回FALSEif(L->next)//非空returnFALSE;elsereturnTRUE;}國際教育學(xué)院5.判斷線性表L是否為空國際教育學(xué)院按序號查找按值查找查找國際教育學(xué)院按序號查找查找國際教育學(xué)院思考：順序表里如何找到第i個(gè)元素？鏈表的查找：要從鏈表的頭指針出發(fā)，順著鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)按序號查找國際教育學(xué)院思考：順序表里如何找到第i個(gè)元素？按序號查找國際教育學(xué)院計(jì)數(shù)器j置為1，指針p從首元結(jié)點(diǎn)順鏈掃描當(dāng)p掃描下一結(jié)點(diǎn)時(shí)，j相應(yīng)地加1

j=i時(shí)，p所指結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)p為null且j≠i時(shí)，表示i大于表長j>i時(shí)，表示i小于1按序號查找的思想國際教育學(xué)院計(jì)數(shù)器j置為1，指針p從首元結(jié)點(diǎn)順鏈掃描按序號查找的思想國際6.獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容（算法2.8）StatusGetElem_L(LinkListL,inti,Elemtype&e){LinkListp;p=L->next;//初始化,p指向第一個(gè)結(jié)點(diǎn)j=1;//j為計(jì)數(shù)器while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;//i大于表長或小于1e=p->data;//取第i個(gè)元素returnOK;}按序號查找國際教育學(xué)院6.獲取線性表L中的某個(gè)數(shù)據(jù)元素的內(nèi)容（算法2.8）按序號查從首元結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較若有結(jié)點(diǎn)與key相等，則返回值為key的結(jié)點(diǎn)位置否則返回NULL按值查找的思想國際教育學(xué)院從首元結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較按值7.在線性表L中查找值為e的數(shù)據(jù)元素LNode*LocateELem(LinkListL,Elemtypee){LinkListp;p=L->next;while(p&&p->data!=e)

p=p->next;//尋找滿足條件的結(jié)點(diǎn)return(p);//返回L中值為e的數(shù)據(jù)元素的位置}按值查找國際教育學(xué)院7.在線性表L中查找值為e的數(shù)據(jù)元素按值查找國際教育學(xué)院8.返回線性表L中e的直接前驅(qū)元素StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e){//若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè),則用pre_e返回它的前驅(qū),返回OK;否則操作失敗,pre_e無定義,返回INFEASIBLELinkListq,p=L->next;//p指向第一個(gè)結(jié)點(diǎn)while(p->next)//p所指結(jié)點(diǎn)有后繼{q=p->next;if(q->data==cur_e){*pre_e=p->data;returnOK;}p=q;/*p向后移*/}returnINFEASIBLE;}國際教育學(xué)院8.返回線性表L中e的直接前驅(qū)元素國際教育學(xué)院9.返回線性表L中e的直接后繼元素StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e)//若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼,返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE*/LinkListp=L->next;/*p指向第一個(gè)結(jié)點(diǎn)*/while(p->next)/*p所指結(jié)點(diǎn)有后繼*/{if(p->data==cur_e){*next_e=p->next->data;returnOK;}p=p->next;}returnINFEASIBLE;}國際教育學(xué)院9.返回線性表L中e的直接后繼元素國際教育學(xué)院將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間步驟：（1）找到ai-1存儲位置p（2）生成一個(gè)新結(jié)點(diǎn)*s（3）將新結(jié)點(diǎn)*s的數(shù)據(jù)域置為x（4）新結(jié)點(diǎn)*s的指針域指向結(jié)點(diǎn)ai（5）令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)*s插入（插在第i個(gè)結(jié)點(diǎn)之前）

國際教育學(xué)院將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-s->next=p->next;p->next=s插入（插在第i個(gè)結(jié)點(diǎn)之前）

思考：步驟1和2能互換么？國際教育學(xué)院s->next=p->next;p->next=10.在L中第i個(gè)元素之前插入數(shù)據(jù)元素e

（算法2.9）StatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)returnERROR;//i大于表長加1或小于1s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)s->data=e;//插入L中s->next=p->next;p->next=s;returnOK;}插入（插在第i個(gè)結(jié)點(diǎn)之前）

國際教育學(xué)院10.在L中第i個(gè)元素之前插入數(shù)據(jù)元素e（算法2.9）插入將表的第i個(gè)結(jié)點(diǎn)刪去步驟：（1）找到ai-1存儲位置p（2）保存要?jiǎng)h除的結(jié)點(diǎn)的值（3）令p-＞next指向ai的直接后繼結(jié)點(diǎn)（4）釋放結(jié)點(diǎn)ai的空間刪除（刪除第i個(gè)結(jié)點(diǎn)）

國際教育學(xué)院將表的第i個(gè)結(jié)點(diǎn)刪去刪除（刪除第i個(gè)結(jié)點(diǎn)）國際教育學(xué)院刪除（刪除第i個(gè)結(jié)點(diǎn)）

國際教育學(xué)院刪除（刪除第i個(gè)結(jié)點(diǎn)）國際教育學(xué)院刪除（刪除第i個(gè)結(jié)點(diǎn)）

p->next=p->next->next???ai-1ai-1aiaiai+1ai+1pq刪除前刪除后國際教育學(xué)院刪除（刪除第i個(gè)結(jié)點(diǎn)）p->next=p->nex11.將線性表L中第i個(gè)數(shù)據(jù)元素刪除（算法2.10）StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=0;while(p->next&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn),并令p指向其前驅(qū)p=p->next;++j;}if(!(p->next)&&j>i-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}刪除（刪除第i個(gè)結(jié)點(diǎn)）

國際教育學(xué)院11.將線性表L中第i個(gè)數(shù)據(jù)元素刪除（算法2.10）刪除（刪1.查找:因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為

O(n)。2.插入和刪除:因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為

O(1)。

但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為O(n)

。鏈表的運(yùn)算時(shí)間效率分析國際教育學(xué)院1.查找:因線性鏈表只能順序存取，即在查找時(shí)要從頭指針從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中將該新結(jié)點(diǎn)插入到鏈表的前端單鏈表的建立（前插法）國際教育學(xué)院從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)：單鏈表的建立（前插法）國際教育單鏈表的建立p->data=anp->data=an-1L->next=pp->next=L->next國際教育學(xué)院單鏈表的建立p->data=anp->data=an-1L-voidCreatList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點(diǎn)scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入到表頭}}單鏈表的建立（算法2.11）國際教育學(xué)院voidCreatList_L(LinkList&L,i線性表的應(yīng)用－－線性表合并（算法2.1）問題描述：假設(shè)利用兩個(gè)線性表La和Lb分別表示兩個(gè)集合A和B,現(xiàn)要求一個(gè)新的集合

A=ABLa=(7,5,3,11)Lb=(2,6,3)La=(7,5,3,11,2,6).國際教育學(xué)院線性表的應(yīng)用－－線性表合并（算法2.1）問題描述：La依次取出Lb中的每個(gè)元素，執(zhí)行以下操作：

在La中查找該元素如果找不到，則將其插入La的最后線性表合并－－操作步驟國際教育學(xué)院依次取出Lb中的每個(gè)元素，執(zhí)行以下操作：線性表合并－－操作voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);

for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);

}}線性表合并（算法2.1）國際教育學(xué)院voidunion(List&La,ListLb){問題描述：

已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列,現(xiàn)要求將La和Lb歸并為一個(gè)新的線性表Lc,且Lc中的數(shù)據(jù)元素仍按值非遞減有序排列.La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11).有序表合并（算法2.2）國際教育學(xué)院問題描述：La=(1,7,8)有序表合并（算法2.(1)Lc為空表(2)依次從La或Lb中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc表的最后，直至其中一個(gè)表變空為止(3)繼續(xù)將La或Lb其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc表的最后有序表合并－－操作步驟國際教育學(xué)院(1)Lc為空表(2)依次從La或Lb中“摘取”元voidMergeList(ListLa,ListLb,List&Lc){

InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

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_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}有序表合并（算法2.2）國際教育學(xué)院voidMergeList(ListLa,ListLb(1)創(chuàng)建一個(gè)空表Lc(2)依次從La或Lb中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc表的最后，直至其中一個(gè)表變空為止(3)繼續(xù)將La或Lb其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc表的最后有序的順序表合并－－操作步驟國際教育學(xué)院(1)創(chuàng)建一個(gè)空表Lc(2)依次從La或Lb中“voidMergeList(SqListLa,SqListLb,SqList&Lc)ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;/*不用InitList()創(chuàng)建空表Lc*/pc=(*Lc).elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last)/*表La和表Lb均非空*/{if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;/*插入La的剩余元素*/while(pb<=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;/*插入Lb的剩余元素*/}有序的順序表合并（算法2.7)T(n)=S(n)=O(n)國際教育學(xué)院voidMergeList(SqListLa,SqLis將這兩個(gè)有序鏈表合并成一個(gè)有序的單鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。有序鏈表合并－－重點(diǎn)掌握國際教育學(xué)院將這兩個(gè)有序鏈表合并成一個(gè)有序的單鏈表。有序鏈表合并－－重點(diǎn)LbLa12467881011合并后有序鏈表合并－－重點(diǎn)掌握國際教育學(xué)院LbLa12467881011合并(1)Lc指向La(2)依次從La或Lb中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc表的最后，直至其中一個(gè)表變空為止(3)繼續(xù)將La或Lb其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc表的最后(4)釋放Lb表的表頭結(jié)點(diǎn)有序鏈表合并－－操作步驟國際教育學(xué)院(1)Lc指向La(2)依次從La或Lb中“摘取”有序鏈表合并（初始化）paLbpbLc=pc國際教育學(xué)院有序鏈表合并（初始化）paLbpbpaLa(Lc,pcbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;國際教育學(xué)院paLa(Lc,pcbpb有序鏈PaLa(Lcbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;1Pc國際教育學(xué)院PaLa(Lcbpb有序鏈表合并(La(Lcbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;1Pcpa=pa->next;Pa國際教育學(xué)院La(Lcbpb有序鏈表合并(pLa(Lcbpb有序鏈表合并(pa->data>pb->data)pc->next=pb;1Pcpa國際教育學(xué)院La(Lcbpb有序鏈表合并(pLa(Lcbpb有序鏈表合并(pa->data>pb->data)pc->next=pb;1paPcpc=pb;2國際教育學(xué)院La(Lcbpb有序鏈表合并(pLa(Lcb有序鏈表合并(pa->data>pb->data)pc->next=pb;1paPcpc=pb;2pb=pb->next;pb國際教育學(xué)院La(Lcb有序鏈表合并(pa-La(Lc)12467881011有序鏈表合并pc->next=pa?pa:pb;pa(NULL)pbpc國際教育學(xué)院La(Lc)12467881011有序鏈表合并pc->neLa(Lc)12467881011合并后free(Lb);有序鏈表合并國際教育學(xué)院La(Lc)12467881011合并后free(Lb);有voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;//插入剩余段free(Lb);//釋放Lb的頭結(jié)點(diǎn)}有序鏈表合并（算法2.12）T(n)=S(n)=O(1)國際教育學(xué)院voidMergeList_L(LinkList&La,思考1：要求合并后的表無重復(fù)數(shù)據(jù)，如何實(shí)現(xiàn)？提示：要單獨(dú)考慮

pa->data==pb->data

La(Lc)12467881011國際教育學(xué)院思考1：要求合并后的表無重復(fù)數(shù)據(jù)，如何實(shí)現(xiàn)？提示：要單獨(dú)考慮要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。思考2：將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表，如何實(shí)現(xiàn)？國際教育學(xué)院要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間,不另外占用其它的(1)Lc指向La(2)依次從La或Lb中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc表的表頭結(jié)點(diǎn)之后，直至其中一個(gè)表變空為止(3)繼續(xù)將La或Lb其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc表的表頭結(jié)點(diǎn)之后(4)釋放Lb表的表頭結(jié)點(diǎn)操作步驟作業(yè)國際教育學(xué)院(1)Lc指向La(2)依次從La或Lb中“摘取”(a)修改前(b)插入SHI靜態(tài)鏈表（了解）國際教育學(xué)院(a)修改前(b)插入SHI靜態(tài)鏈表（了解）國際教(a)修改前(b)插入SHI95靜態(tài)鏈表（了解）國際教育學(xué)院(a)修改前(b)插入SHI95靜態(tài)鏈表（了解）國(a)修改前(b)插入SHI,刪除ZHENG靜態(tài)鏈表（了解）國際教育學(xué)院(a)修改前(b)插入SHI,刪除ZHENG靜#defineMAXSIZE1000//鏈表的最大長度typedefstruct{ElemTypedata;intcur;}component,SLinkList[MAXSIZE];特點(diǎn)需預(yù)先分配較大的存儲空間插入和刪除操作時(shí),不需移動(dòng)元素若第i分量代表第k個(gè)結(jié)點(diǎn),則S[i].cur指示第k+1個(gè)結(jié)點(diǎn)的位置

靜態(tài)鏈表（了解）國際教育學(xué)院#defineMAXSIZE1000//鏈表的最大長L->next=L(a)非空單循環(huán)鏈表L(b)空表L循環(huán)鏈表國際教育學(xué)院L->next=L(a)非空單循環(huán)鏈表L(b)空表L循環(huán)p=B->next->next;B->next=A->next;A->next=p...A...B循環(huán)鏈表的合并國際教育學(xué)院p=B->next->next;B->next=A->ne雙向鏈表typedefstructDuNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList國際教育學(xué)院雙向鏈表typedefstructDuNode{國際教育(a)空雙向循環(huán)鏈表(b)雙向循環(huán)鏈表d->next->prior=d->prior->next=dL->next=L國際教育學(xué)院(a)空雙向循環(huán)鏈表(b)雙向循環(huán)鏈表d->next-雙向鏈表的插入國際教育學(xué)院雙向鏈表的插入國際教育學(xué)院1.s->prior=p->prior;雙向鏈表的插入abx......1ps國際教育學(xué)院1.s->prior=p->prior;雙向鏈表的插入ab雙向鏈表的插入1.s->prior=p->prior;2.p->prior->next=s;abx......12ps國際教育學(xué)院雙向鏈表的插入1.s->prior=p->prior;2.雙向鏈表的插入1.s->prior=p->prior;2.p->prior->next=s;3.s->next=p;國際教育學(xué)院雙向鏈表的插入1.s->prior=p->prior;2.雙向鏈表的插入4.p->prior=s;abx......1234ps1.s->prior=p->prior;2.p->prior->next=s;3.s->next=p;國際教育學(xué)院雙向鏈表的插入4.p->prior=s;abx......StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_DuL(L,i)))returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;s->data=e;

s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}雙向鏈表的插入（算法2.18）國際教育學(xué)院StatusListInsert_DuL(DuLinkLi雙向鏈表的刪除國際教育學(xué)院雙向鏈表的刪除國際教育學(xué)院1.p->prior->next=p->next;雙向鏈表的刪除國際教育學(xué)院1.p->prior->next=p->next;雙向鏈表雙向鏈表的刪除1.p->prior->next=p->next;2.p->next->prior=p->prior;國際教育學(xué)院雙向鏈表的刪除1.p->prior->next=p->neStatusListDelete_DuL(DuLinkList&L,inii,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;e=p->data;

p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}雙向鏈表的刪除（算法2.19）國際教育學(xué)院StatusListDelete_DuL(DuLinkLitypedefstruct{//鏈表類型Linkhead,tail;//分別指向頭結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)intlen;//指示線性鏈表中數(shù)據(jù)元素的個(gè)數(shù)}LinkList;typedefstructLNode{//結(jié)點(diǎn)類型ElemTypedata;structLNode*next;}*Link,*Position;鏈表類型的重定義（了解）國際教育學(xué)院typedefstruct{//鏈表類型typedef1、了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)（順序表）和鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表）。2、熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，掌握鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。小結(jié)國際教育學(xué)院1、了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在3、掌握順序表的查找、插入和刪除算法4、掌握鏈表的查找、插入和刪除算法5、能夠從時(shí)間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點(diǎn)及其適用場合小結(jié)國際教育學(xué)院3、掌握順序表的查找、插入和刪除算法小結(jié)國際教育學(xué)院1.將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞減的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間,不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。2.將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲空間,不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。

作業(yè)國際教育學(xué)院1.將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞減的有序鏈表。要求結(jié)3.設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。

4.設(shè)計(jì)一個(gè)算法，通過遍歷一趟，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。作業(yè)國際教育學(xué)院3.設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。作業(yè)提示第1題參考講稿和教材中的算法2.12要單獨(dú)考慮

pa->data==pb->data

La(Lc)12467881011國際教育學(xué)院作業(yè)提示第1題參考講稿和教材中的算法2.12要單獨(dú)考慮

pa(1)Lc指向La(2)依次從La或Lb中“摘取”元素值較小的結(jié)點(diǎn)插入到Lc表的表頭結(jié)點(diǎn)之后，直至其中一個(gè)表變空為止(3)繼續(xù)將La或Lb其中一個(gè)表的剩余結(jié)點(diǎn)插入在Lc表的表頭結(jié)點(diǎn)之后(4)釋放Lb表的表頭結(jié)點(diǎn)作業(yè)提示第2題參考講稿和教材中的算法2.12，步驟如下：國際教育學(xué)院(1)Lc指向La(2)依次從La或Lb中“摘取”12233445561132434854LaLbLc∧papbqpb∧qpaqpaq第2題實(shí)現(xiàn)過程動(dòng)態(tài)演示國際教育學(xué)院12233445561132434854LaLbLc∧pap作業(yè)提示第3題:確定單鏈表中值最大的結(jié)點(diǎn)思想類似于求n個(gè)數(shù)中的最大數(shù)，可假設(shè)第一個(gè)結(jié)點(diǎn)最大，用指針pmax指向，然后用pmax依次和后面的結(jié)點(diǎn)進(jìn)行比較，發(fā)現(xiàn)大者則用pmax指向該結(jié)點(diǎn)，這樣將鏈表從頭到尾遍歷一遍時(shí)，pmax所指向的結(jié)點(diǎn)就是最大者。其中的比較語句形式如下：if(p->data>pmax->data)pmax=p;國際教育學(xué)院作業(yè)提示第3題:確定單鏈表中值最大的結(jié)點(diǎn)國際教育學(xué)院作業(yè)提示第4題：要求將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)算法的思想：從首元結(jié)點(diǎn)開始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部(1)標(biāo)志后繼結(jié)點(diǎn)(2)修改指針（將p插入在頭結(jié)點(diǎn)之后）(3)重置結(jié)點(diǎn)p（p重新指向原表中后繼）國際教育學(xué)院作業(yè)提示第4題：要求將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)(1)標(biāo)志a1a2a3LLpsucca1psucca2psucca3p(1)標(biāo)志后繼結(jié)點(diǎn)(2)修改指針（將p插入在頭結(jié)點(diǎn)之后）(3)重置結(jié)點(diǎn)p（p重新指向原表中后繼）國際教育學(xué)院a1a2a3LLpsucca1psucca2psucc作業(yè)要求2.打印稿：用C語言編寫完整的程序，上機(jī)調(diào)試成功，然后上交一份源程序的B5打印稿1.手