第二章線性表

第二章～第四章線性結構

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

2.3線性表的鏈式表示和實現(xiàn)一、線性表的定義

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

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

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

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

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

ADT

List{

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

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

基本操作：InitList(&L)

操作結果：構建一個空的線性表。

DestroyList(&L)

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

操作結果：銷毀線性表

ClearList(&L)

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

操作結果：將線性表重置為空表

ListEmpty(L)

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

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

ListLength(L)

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

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

GetElem(L,i,&e)

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

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

LocateElem(L,e,compare())

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

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

操作結果：返回L中第1個與e滿足關系compare()元素的位序

PriorElem(L,cur_e,&pre_e)

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

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

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

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

ListInsert(&L,i,e)

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

操作結果：在第i個位置之前插入新的元素e,線性表長度加1

ListDelete(&L,i,&e)

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

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

ListTraverse(L,visit())

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

操作結果：依次對線性表的每個數(shù)據(jù)元素調用函數(shù)visit()。一旦visit()失敗，則操作失敗。

}ADT

List;在上述基本操作定義的基礎上，還可以進行更復雜的操作。例2-1利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合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);}}分析算法復雜度：O(ListLength(La)×ListLength(Lb))例2-2已知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表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);}}分析算法復雜度：O(ListLength(La)+ListLength(Lb))返回一、線性表的順序表示把線性表的結點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置

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

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

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

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

//當前長度intlistsize;

//當前分配空間}Sqlist;例如：Sqlist*L;二、順序表上的基本操作1、初始化：構造一個空表。算法如下：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)個位置上，插入一個新結點e，使長度為n的線性表：(a1，…ai-1，ai，…，an)變成長度為n+1的線性表(a1，…ai-1，e，ai，…，an)內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1an-1eStatusListInsert_Sq(Sqlist&L，ElemTypee，inti){elemtype*p,*q,*newbase;if(i<1||i>L.length+1){//當前存儲空間已滿，增加分配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ī)模是表的長度，設它的值為n。該算法的時間主要花費在循環(huán)的結點后移語句上，該語句的執(zhí)行次數(shù)（即移動結點的次數(shù)）是n-i+1。由此可看出，所需移動結點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關。當i=n時，由于循環(huán)變量的終值大于初值，結點后移語句將不進行；這是最好情況，其時間復雜度O（1）；當i=1時，結點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結點，這是最壞情況，其時間復雜度為O（n）。計算算法平均時間復雜度T(n)設Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：

也就是說，在順序表上做插入運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復雜度為O(n)。3、刪除線性表的刪除運算是指將表的第i(1≦i≦n)結點刪除，使長度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長度為n-1的線性表(a1，…ai-1，ai+1，…，an)內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標01i-1n-2in-112i元素序號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ù)也是由表長n和位置i決定。若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結點；若i=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結點外的所有結點。這兩種情況下算法的時間復雜度分別為O(1)和O(n)。刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結點，令Ede(n)表示所需移動結點的平均次數(shù)，刪除表中第i個結點的移動次數(shù)為n-i，故

式中，Qi表示刪除表中第i個結點的概率。

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

即在順序表上做刪除運算，平均要移動表中約一半的結點，平均時間復雜度也是O(n)

結論：在順序表中插入或刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低

4、按值查找線性表中的按值查找是指在線性表中查找與給定值e相等的數(shù)據(jù)元素。在順序表中完成該運算最簡單的方法是：從第一個元素a1起依次和e比較，直到找到一個與e相等的數(shù)據(jù)元素，則返回它在順序表中的存儲下標或序號（二者差一）；或者查遍整個表都沒有找到與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;/*返回的是存儲位置*/}5、線性表應用舉例——線性表合并有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也是從小到大的升序排列。算法思路：依次掃描通過A和B的元素，比較當前的元素的值，將較小值的元素賦給C，如此直到一個線性表掃描完畢，然后將未完的那個順序表中余下部分賦給C即可。C的容量要能夠容納A、B兩個線性表相加的長度。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++;}三、順序存儲結構的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分練習與作業(yè)練習：分析線性表按值查找和合并的時間復雜度。作業(yè)：習題二2、11返回2.11設順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。解：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、鏈表：

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

節(jié)點

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

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

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

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

typedefstructLNode{

ElemTypedata;

structLNode*next;}

LNode*LinkList;例如：LinkListp;

datanext數(shù)據(jù)域指針域datanextp結點（*p）(*p)表示p所指向的結點(*p).datap->data表示p指向結點的數(shù)據(jù)域(*p).nextp->next表示p指向結點的指針域為增強程序的可讀性，通常設置一個鏈表的頭指針，單鏈表可以用頭指針的名字來命名。如：下面鏈表可稱為表head:將標識鏈表的頭指針說明為LinkList類型的變量，如：

LinkListhead;當head=NULL，則表示一個空表；當head=第一個結點的地址，即鏈表的頭指針；將指向某結點的指針變量說明為LNode*類型，如:

LNode*p；

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

110……130135……160頭指針head165170……200205……h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………165例1、已知線性表的鏈式表示如下：求該線性表

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

a、頭插法建表該方法從一個空表開始，重復讀入數(shù)據(jù)，生成新結點，將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。LinkListCreateList1()//表長不定、表元素為字符{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)//表長已知、表元素為整型{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、尾插法建表頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當前鏈表的尾結點。在尾部插入建立單鏈表H=NULLr=NULL/*初始狀態(tài)*/29rH7629rH187629rH25∧42187629rH42187629rH3）、查找運算（1）、按序號查找在鏈表中，即使知道被訪問結點的序號i，也不能象順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結點往下搜索，直到搜索到第i個結點為止。因此，鏈表不是隨機存取結構。設單鏈表的長度為n，要查找表中第i個結點，僅當1≦i≦n時，i的值是合法的。但有時需要找頭結點的位置，故我們將頭結點看做是第0個結點，其算法如下：StatusGetElem(LinkListL,inti,ElemType&e){intj;//記錄當前查找位置LNode*p;//當前查找節(jié)點p=L->next;j=1;while(p&&j<i){p=p–>next;j++;}if(!p||j>i)//p不存在returnERROR;e=p->data;returnOK;}算法分析：時間復雜度O(n)（2）、按值查找按值查找是在鏈表中，查找是否有結點值等于給定值key的結點，若有的話，則返回首次找到的其值為key的結點的存儲位置；否則返回NULL。查找過程從開始結點出發(fā)，順著鏈表逐個將結點的值和給定值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）、插入運算插入運算是將值為e的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結點*p，并令結點*p的指針域指向新結點，新結點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯關系的變化，插入過程如：

例如：在線性表兩個數(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;//頭結點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;}分析：時間復雜度為O(n)5）、刪除運算刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的存儲地址是在其直接前趨結點ai-1的指針域next中，所以我們必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。此過程為：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;}算法分析：時間復雜度為O(n)

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

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

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

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

(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)三、順序存儲結構的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分2.4對以下單鏈表分別執(zhí)行下列各程序段，并畫出結果示意圖。解：

2.13試寫一算法在帶頭結點的單鏈表結構上實現(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試寫一算法在帶頭結點的單鏈表結構上實現(xiàn)線性表操作Length(L)。解：//返回單鏈表的長度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)鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環(huán)狀

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

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

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

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

非空雙向循環(huán)鏈表：LAB結構特性：設指針p指向某一結點，則雙向鏈表結構的對稱性可用下式描述：

(p—>prior)—>next=p=(p—>next)—>prior即結點*p的存儲位置既存放在其前趨結點*(p—>prior)的直接后繼指針域中，也存放在它的后繼結點*(p—>next)的直接前趨指針域中?；静僮鳎篖istLength、GetElem和LocateElem等一些基本操作只涉及單方向指針，則其算法描述與單鏈表相同，但在插入、刪除操作設計兩個方向的指針。插入：例在結點p前插入數(shù)據(jù)域為x的結點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;}算法分析：時間復雜度為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;}算法分析：時間復雜度為O(n)三、如何選取順序表的存儲結構１．基于存儲的考慮順序表的存儲空間是靜態(tài)分配的,鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低，存儲密度是指一個結點中數(shù)據(jù)元素所占的存儲單元和整個結點所占的存儲單元之比。２．基于運算的考慮如果經(jīng)常做的運算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時平均移動表中一半的元素，當數(shù)據(jù)元素的信息量較大且表較長時，這一點是不應忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優(yōu)于前者。３．基于環(huán)境的考慮順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是考慮的一個因素?？傊?，兩中存儲結構各有長短，選擇那一種由實際問題中的主要因素決定，即從實際應用出發(fā)。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈式存儲。返回2.4線性表應用例：一元多項式的表示及相加一、一元多項式的表示：

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