第二章線性表

第二章～第四章線性結(jié)構(gòu)

線性結(jié)構(gòu)特點(diǎn)：在數(shù)據(jù)元素的非空有限集中：存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼第二章線性表（6學(xué)時(shí)）第一講2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)第二講

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、線性表的定義

線性表(LinearList)：由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。其中：數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。常將非空的線性表(n>0)記作：(a1，a2，…an)

說明：數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。例1、26個(gè)英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況：（6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：

在此例中，一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成，常把這樣的數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表，又稱為文件。姓名學(xué)號(hào)性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….線性表的基本要求：

從以上三個(gè)例子可以看出，線性表中的數(shù)據(jù)元素可以是各種各樣，但同一線性表中的數(shù)據(jù)元素必須具有相同的特性，即屬于同一數(shù)據(jù)對(duì)象，相鄰的元素之間存在著序偶關(guān)系。通常將線性表記為：(a1,…,ai-1,ai,ai+1,…,an)ai為第i個(gè)元素，i為元素ai在線性表中的位序。線性表的邏輯特征：在非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)a1，它沒有直接前趨，而僅有一個(gè)直接后繼a2；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼，而僅有一個(gè)直接前趨an-1；其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。

線性表是一種典型的線性結(jié)構(gòu)，長(zhǎng)度可增減，對(duì)元素可進(jìn)行訪問，插入、刪除等操作。二、線性表的抽象數(shù)據(jù)類型定義

ADT

List{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,3.,n,n≥0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3...,n}

基本操作：InitList(&L)

操作結(jié)果：構(gòu)建一個(gè)空的線性表。

DestroyList(&L)

初始條件：線性表已存在(已初始化)

操作結(jié)果：銷毀線性表

ClearList(&L)

初始條件：線性表已存在(已初始化)

操作結(jié)果：將線性表重置為空表

ListEmpty(L)

初始條件：線性表已存在(已初始化)

操作結(jié)果：若線性表為空表則返回TRUE,否則返回FALSE

ListLength(L)

初始條件：線性表已存在(已初始化)

操作結(jié)果：返回線性表中元素個(gè)數(shù)

GetElem(L,i,&e)

初始條件：線性表已存在(已初始化)

操作結(jié)果：用e返回第i個(gè)數(shù)據(jù)元素的值。

LocateElem(L,e,compare())

初始條件：線性表已存在(已初始化),

compare是數(shù)據(jù)判定函數(shù)

操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()元素的位序

PriorElem(L,cur_e,&pre_e)

初始條件：線性表已存在(已初始化)

操作結(jié)果：若cur_e是線性表中的數(shù)據(jù)元素,且不是第一個(gè),用pre_e來返回cur_e的前驅(qū);否則操作失敗。NextElem(L,cur_e,&next_e)

初始條件：線性表已存在(已初始化)

操作結(jié)果：若cur_e是線性表中的數(shù)據(jù)元素,且不是最后一個(gè)元素，則用next_e返回它的的后繼，否則操作失敗，next_e無定義。

ListInsert(&L,i,e)

初始條件：線性表已存在,1<=i<=ListLength+1

操作結(jié)果：在第i個(gè)位置之前插入新的元素e,線性表長(zhǎng)度加1

ListDelete(&L,i,&e)

初始條件：線性表已存在且非空，1<=i<=ListLength

操作結(jié)果：刪除線性表的第i個(gè)數(shù)據(jù)元素，并用e返回其值，線性表長(zhǎng)度減一

ListTraverse(L,visit())

初始條件：線性表已存在(已初始化)

操作結(jié)果：依次對(duì)線性表的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。

}ADT

List;在上述基本操作定義的基礎(chǔ)上，還可以進(jìn)行更復(fù)雜的操作。例2-1利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A=A∪B。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，equal))listinsert(la，++la_len，e);}}分析算法復(fù)雜度：O(ListLength(La)×ListLength(Lb))例2-2已知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。

voidmergelist(listla，listlb，list&lc){initlist(lc);i=j=1;k=0;la_len=listlength(la);lb_en=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);istinsert(lc，++k，ai);}while(j<=lb_len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}分析算法復(fù)雜度：O(ListLength(La)+ListLength(Lb))返回一、線性表的順序表示把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置

LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+l線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：

LOC(ai)=LOC(a1)+(i-1)×la1a2aibb+lb+l*(i-1)12i內(nèi)存元素序號(hào)b+l×(n-1)備用空間an

nb+l×(maxlen-1)用結(jié)構(gòu)進(jìn)行表示和實(shí)現(xiàn)：#defineLIST_INIT_SIZE100//線性表初始空間，是單位空間的倍數(shù)#defineLISTINCREMENT10//分配空間增量typedefstructSqlist{elemtype*elem;//數(shù)組指針//存儲(chǔ)空間起始地址intlength;

//當(dāng)前長(zhǎng)度intlistsize;

//當(dāng)前分配空間}Sqlist;例如：Sqlist*L;二、順序表上的基本操作1、初始化：構(gòu)造一個(gè)空表。算法如下：StatusInitList_Sq(Sqlist&L){L.elem=(ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}2、插入：在表的第i(1≦i≦n+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)e，使長(zhǎng)度為n的線性表：(a1，…ai-1，ai，…，an)變成長(zhǎng)度為n+1的線性表(a1，…ai-1，e，ai，…，an)內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1an-1eStatusListInsert_Sq(Sqlist&L，ElemTypee，inti){elemtype*p,*q,*newbase;if(i<1||i>L.length+1){//當(dāng)前存儲(chǔ)空間已滿，增加分配printf(“positionerror”);returnERROR;}if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);//q為插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}分析：這里的問題規(guī)模是表的長(zhǎng)度，設(shè)它的值為n。該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，該語句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是n-i+1。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。當(dāng)i=n時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O（1）；當(dāng)i=1時(shí)，結(jié)點(diǎn)后移語句將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，其時(shí)間復(fù)雜度為O（n）。計(jì)算算法平均時(shí)間復(fù)雜度T(n)設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：

也就是說，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。3、刪除線性表的刪除運(yùn)算是指將表的第i(1≦i≦n)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長(zhǎng)度為n-1的線性表(a1，…ai-1，ai+1，…，an)內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號(hào)i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號(hào)i+1n-1nanai+2StatusDeletelist(sqlist&L，inti,elemtype&e){ElemType*p,*q;if(i<1||i>L.length){printf(“positionerror”);returnERROR;}p=&(L.elem[i-1]);e=*p;q=&(l.elem[l.length-1]);

for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}分析：該算法的時(shí)間分析與插入算法相似，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長(zhǎng)n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動(dòng)結(jié)點(diǎn)；若i=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動(dòng)表中除開始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時(shí)間復(fù)雜度分別為O(1)和O(n)。刪除算法的平均性能分析與插入算法相似。在長(zhǎng)度為n的線性表中刪除一個(gè)結(jié)點(diǎn)，令Ede(n)表示所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i，故

式中，Qi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。

在等概率的假設(shè)下，Q1=Q2=Q3=…=Qn=1/n由此可得：

即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是O(n)

結(jié)論：在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低

4、按值查找線性表中的按值查找是指在線性表中查找與給定值e相等的數(shù)據(jù)元素。在順序表中完成該運(yùn)算最簡(jiǎn)單的方法是：從第一個(gè)元素a1起依次和e比較，直到找到一個(gè)與e相等的數(shù)據(jù)元素，則返回它在順序表中的存儲(chǔ)下標(biāo)或序號(hào)（二者差一）；或者查遍整個(gè)表都沒有找到與e相等的元素，返回-1或0。intLocation_SeqList(SeqListL,ElemTypee){inti=0;//此題與書不同ElemType*p;p=L.elem;while(i<=L.length&&*p!=e){i++;++p;}if(i>L.length)return-1;elsereturni;/*返回的是存儲(chǔ)位置*/}5、線性表應(yīng)用舉例——線性表合并有順序表A和B，其元素均按從小到大的升序排列，編寫一個(gè)算法將它們合并成一個(gè)順序表C，要求C的元素也是從小到大的升序排列。算法思路：依次掃描通過A和B的元素，比較當(dāng)前的元素的值，將較小值的元素賦給C，如此直到一個(gè)線性表掃描完畢，然后將未完的那個(gè)順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個(gè)線性表相加的長(zhǎng)度。voidmergelist_sq(sqlistla,sqlistlb,sqlist&lc){pa=la.elem;pb=lb.elem;lc.listsize=lc.length=la.length+lb.length;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){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}三、順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分練習(xí)與作業(yè)練習(xí)：分析線性表按值查找和合并的時(shí)間復(fù)雜度。作業(yè)：習(xí)題二2、11返回2.11設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。解：StatusInsertOrderList(SqList&va,ElemTypex){ //在非遞減的順序表va中插入元素x,并使其仍成為順序表的算法 inti; if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0&&x<va.elem[i-1];i--) va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; returnOK;}解：StatusInsertOrderList(SqList&va,ElemTypex){ inti; if(va.length>=va.listsize){newbase=(ElemType*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);va.elem=newbase;va.listsize+=LISTINCREMENT;} for(i=va.length;i>0&&x<va.elem[i-1];i--) va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; returnOK;}一、線性鏈表1、鏈表：

鏈表是用一組任意的存儲(chǔ)單元來依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的，因此，對(duì)于每個(gè)數(shù)據(jù)元素ai，除了要存儲(chǔ)本身的數(shù)據(jù)信息外，還要存儲(chǔ)其直接后繼的信息，即地址。

節(jié)點(diǎn)

data域是數(shù)據(jù)域，用來存放結(jié)點(diǎn)的值。next是指針域（亦稱鏈域），用來存放結(jié)點(diǎn)的直接后繼的地址（或位置）。特點(diǎn)：鏈表正是通過每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。datanexta1a2an^…...“指針”回顧內(nèi)存的兩種訪問形式：

直接訪問：根據(jù)所聲明變量和地址之間的一一對(duì)應(yīng)關(guān)系進(jìn)行訪問。如：inti=3;printf(“%d”,i);

間接訪問：將變量i的地址存放于另外一個(gè)內(nèi)存單元中，如：i_pointer=&i;printf(“%d”,*i_pointer);*i_pointer=5;聲明：類型名*指針變量名。int*i_pointer;6320002002內(nèi)存地址存儲(chǔ)內(nèi)容分配變量ij200032000…3000i…i_pointer

2、線性鏈表：1）、定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫線性鏈表，也叫單鏈表。2）、實(shí)現(xiàn)：借助于C語言的結(jié)構(gòu)指針

typedefstructLNode{

ElemTypedata;

structLNode*next;}

LNode*LinkList;例如：LinkListp;

datanext數(shù)據(jù)域指針域datanextp結(jié)點(diǎn)（*p）(*p)表示p所指向的結(jié)點(diǎn)(*p).datap->data表示p指向結(jié)點(diǎn)的數(shù)據(jù)域(*p).nextp->next表示p指向結(jié)點(diǎn)的指針域?yàn)樵鰪?qiáng)程序的可讀性，通常設(shè)置一個(gè)鏈表的頭指針，單鏈表可以用頭指針的名字來命名。如：下面鏈表可稱為表head:將標(biāo)識(shí)鏈表的頭指針說明為L(zhǎng)inkList類型的變量，如：

LinkListhead;當(dāng)head=NULL，則表示一個(gè)空表；當(dāng)head=第一個(gè)結(jié)點(diǎn)的地址，即鏈表的頭指針；將指向某結(jié)點(diǎn)的指針變量說明為L(zhǎng)Node*類型，如:

LNode*p；

heada1a2an^…...頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，在其數(shù)據(jù)域存發(fā)附加信息，如鏈表的長(zhǎng)度等。線性表為空：頭結(jié)點(diǎn)指針域?yàn)榭?。heada1a2頭結(jié)點(diǎn)an^…...head空表^ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771952數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲(chǔ)地址1713192531374331H頭指針

110……130135……160頭指針head165170……200205……h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………165例1、已知線性表的鏈?zhǔn)奖硎救缦拢呵笤摼€性表

線性表:(bat，cat，eat，fat，hat，jat，lat，mat)batcateatmat^…h(huán)ead3）、基本操作實(shí)現(xiàn)（1）建立：動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：a、頭插法建表 頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。b、尾插法建表 若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。

a、頭插法建表該方法從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。LinkListCreateList1()//表長(zhǎng)不定、表元素為字符{charch;LinkListhead;LNode*p;head=null;ch=getchar();while(ch!=‵\n′){p=(LNode*)malloc(sizeof(LNode));p–>data=ch;p–>next=head;head=p;ch=getchar();}returnhead;}

LinkListCreateList2(intn)//表長(zhǎng)已知、表元素為整型{intdata;linklisthead;lnode*phead=null;for(i=n;i>0;--i){p=(LNode*)malloc(sizeof(LNode));scanf(〝%d〞，&p–>data);p–>next=head;head=p;}returnhead;}∧25∧42187629761825∧421825∧4225∧4225∧在頭部插入建立單鏈表headb、尾插法建表頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。在尾部插入建立單鏈表H=NULLr=NULL/*初始狀態(tài)*/29rH7629rH187629rH25∧42187629rH42187629rH3）、查找運(yùn)算（1）、按序號(hào)查找在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能象順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，故我們將頭結(jié)點(diǎn)看做是第0個(gè)結(jié)點(diǎn)，其算法如下：StatusGetElem(LinkListL,inti,ElemType&e){intj;//記錄當(dāng)前查找位置LNode*p;//當(dāng)前查找節(jié)點(diǎn)p=L->next;j=1;while(p&&j<i){p=p–>next;j++;}if(!p||j>i)//p不存在returnERROR;e=p->data;returnOK;}算法分析：時(shí)間復(fù)雜度O(n)（2）、按值查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過程從開始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：StatusLocateNode(LinkListhead，ElemTypekey,LNode*p){p=head–>next;while(p&&p–>data!=key)p=p–>next;if(p->next=NULL&&p->data!=key)returnERROR;elsereturnOK;}算法分析：O(n)4）、插入運(yùn)算插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：

例如：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入e，已知p指向apabess->next=p->next;p->next=s;StatusInsertNode(LinkList&L，Elemtypee，inti){LNode*p，*s;p=L;j=0;//頭結(jié)點(diǎn)while(p&&j<i-1){p=p->next;j++;}if(!p||j>i-1){printf(〝positionerror〞);returnERROR;}s=(linklist*)malloc(sizeof(lnode));s–>data=e;

s–>next=p–next;p–>next=s;

returnOK;}分析：時(shí)間復(fù)雜度為O(n)5）、刪除運(yùn)算刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的指針域next中，所以我們必須首先找到ai-1的存儲(chǔ)位置p。然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過程為：pai-1aiai+1p->next=p->next->next;StatusDeleteList(LinkList&L,inti,ElemType&e){LNode*p，*q;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next||j>I-1)returnERROR;q=p–>next;

p–>next=q–>next;e=q->data;free(q);

returnOK;}算法分析：時(shí)間復(fù)雜度為O(n)

從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無須移動(dòng)結(jié)點(diǎn)，僅需修改指針。單鏈表特點(diǎn)它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲(chǔ)空間為多個(gè)鏈表共用不需預(yù)先分配空間指針占用額外存儲(chǔ)空間不能隨機(jī)存取，查找速度慢3、靜態(tài)鏈表1)、定義：

#defineMAXSIZE1000/*足夠大的數(shù)*/typedefstruct{ElemTypedata;intcur;}component,SlinkNode[MAXSIZE];

這種鏈表的結(jié)點(diǎn)中也有數(shù)據(jù)域data和指針域cur，與前面所講的鏈表中的指針不同，該指針是結(jié)點(diǎn)的相對(duì)地址(數(shù)組的下標(biāo))，稱之為靜態(tài)指針，這種鏈表稱之為靜態(tài)鏈表。

空指針用0表示,表明表尾。數(shù)組的第零分量看作頭結(jié)點(diǎn)。datacur0123451zhao3li5qian4sun2zhou02)、與其他線性表的區(qū)別與鏈表的主要區(qū)別與線性表的主要區(qū)別：物理地址連續(xù)，但邏輯結(jié)構(gòu)不一定連續(xù)。動(dòng)態(tài)鏈表靜態(tài)鏈表結(jié)點(diǎn)是系統(tǒng)分配用戶事先定義結(jié)點(diǎn)地址是與該類型同類型的指針表示數(shù)組下標(biāo)存儲(chǔ)地址不一定連續(xù)地址連續(xù)練習(xí)與作業(yè)本次課練習(xí)：習(xí)題二7本次課作業(yè)：習(xí)題二3、4、13、142.7已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是_____________。

(1)P=P->next;(2)P->next=P;(3)P->next=P->next->next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next;}(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P;(11)Q=P->next;(12)P=L;(13)L=L->next;(14)free(Q);(11)(3)(14)三、順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲(chǔ)空間使用緊湊缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分2.4對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。解：

2.13試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex){ inti=0; LinkListp=L; while(p&&p->data!=x){ p=p->next; i++; } if(!p)return0; elsereturni;}2.14試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。解：//返回單鏈表的長(zhǎng)度intListLength_L(LinkList&L){ inti=0; LinkListp=L; if(p)p=p-next; while(p){ p=p->next; i++; } returni;}二、循環(huán)鏈表1、定義

循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀

特點(diǎn)：頭尾相接無須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，卻使得從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率，更加方便靈活。2、單循環(huán)鏈表：

（1）定義：在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)的或開始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。hh空表為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)?？昭h(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如上圖所示。操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=H頭指針表示的單鏈表：找開始結(jié)點(diǎn)a1的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)an，則需從頭指針開始遍歷整個(gè)鏈表，其時(shí)間是O(n)從頭指針遍歷鏈表，時(shí)間是O(n)分類尾指針表示單循環(huán)鏈表：則查找開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rear–>next)—>next和rear，顯然，查找時(shí)間都是O(1)。實(shí)際中為簡(jiǎn)化操作多采用尾指針表示單循環(huán)鏈表。rear例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個(gè)線性表的運(yùn)算。兩個(gè)用尾指針標(biāo)識(shí)的單循環(huán)鏈表的連接headaheadbheada->next=headb->next->nextfreeheadb->next=heada->next?LinkListconnect(LinkListheada，LinkListheadb)//heada、headb均為用尾指針表示的單循環(huán)鏈表{LinkListp=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—>next=p;return(headb);}3、雙向鏈表(Doublelinkedlist):1）、定義：在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的。2）、形式描述為：

typedefstructDListNode{ElemTypedata;structDListNode*prior，*next;}DListNode;typedefDListNode*DLinkList;例如：DLinkListhead;priorbnextprioranextpriordatanext

3）、雙向循環(huán)鏈表：和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。L空雙向循環(huán)鏈表：

非空雙向循環(huán)鏈表：LAB結(jié)構(gòu)特性：設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用下式描述：

(p—>prior)—>next=p=(p—>next)—>prior即結(jié)點(diǎn)*p的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)*(p—>prior)的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(p—>next)的直接前趨指針域中?；静僮鳎篖istLength、GetElem和LocateElem等一些基本操作只涉及單方向指針，則其算法描述與單鏈表相同，但在插入、刪除操作設(shè)計(jì)兩個(gè)方向的指針。插入：例在結(jié)點(diǎn)p前插入數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)xSbaPP->prior算法：StatusListInsert_DuList(DuLinkList&L,i,ElemTypex){DuLinkListp,s;if(!(p=GetEmlemP_DuL(L,i))returnERROR;s=(DuLinkList)malloc(sizeof(DulListNode));

s->element=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;retrunOK;}算法分析：時(shí)間復(fù)雜度為O(n)刪除：cabPp->prior->next=p->next;p->next->prior=p->prior;算法：StatusListDel_DuList(DuLinkList&L,i,ElemType&e){DuLinkListp,s;if(!(p=GetEmlemP_DuL(L,i))returnERROR;e=p->data;

p->prior->next=p->next;p->next->prior=p->prior;free(p);retrunOK;}算法分析：時(shí)間復(fù)雜度為O(n)三、如何選取順序表的存儲(chǔ)結(jié)構(gòu)１．基于存儲(chǔ)的考慮順序表的存儲(chǔ)空間是靜態(tài)分配的,鏈表不用事先估計(jì)存儲(chǔ)規(guī)模，但鏈表的存儲(chǔ)密度較低，存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)單元和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)單元之比。２．基于運(yùn)算的考慮如果經(jīng)常做的運(yùn)算是按序號(hào)訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時(shí)平均移動(dòng)表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大且表較長(zhǎng)時(shí)，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個(gè)角度考慮顯然后者優(yōu)于前者。３．基于環(huán)境的考慮順序表容易實(shí)現(xiàn)，任何高級(jí)語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對(duì)來講前者簡(jiǎn)單些，也是考慮的一個(gè)因素?？傊瑑芍写鎯?chǔ)結(jié)構(gòu)各有長(zhǎng)短，選擇那一種由實(shí)際問題中的主要因素決定，即從實(shí)際應(yīng)用出發(fā)。通?！拜^穩(wěn)定”的線性表選擇順序存儲(chǔ)，而頻繁做插入刪除的即動(dòng)態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯?chǔ)。返回2.4線性表應(yīng)用例：一元多項(xiàng)式的表示及相加一、一元多項(xiàng)式的表示：

Pn(x)=P0+P1x+P2x2+…+Pnxn可用線性表P表示：P=(P0,P1,P2