《數(shù)據(jù)結(jié)構(gòu)與算法》第二章線性表

第二章線性表2.1

線性表的類型定義2.2線性表的順序表示和實現(xiàn)2·3線性表的鏈式表示和實現(xiàn)2.4一元多項式的表示及相加邏輯結(jié)構(gòu)存儲結(jié)構(gòu)操作建立。。。線性表廣義表串樹二叉樹圖數(shù)組堆棧和隊列順序存儲鏈式存儲索引散列清除。。。插入數(shù)據(jù)元素刪除數(shù)據(jù)元素修改數(shù)據(jù)元素排序查找(檢索)2.1線性表的類型定義一、線性表的邏輯結(jié)構(gòu)二、線性表的ADT例2-1利用線性表運算實現(xiàn)A=A

B例2-2利用線性表運算把兩個有序的序列合并成一個有序序列2.2線性表的順序表示和實現(xiàn)2·3線性表的鏈式表示和實現(xiàn)一、線性表的邏輯結(jié)構(gòu)1.線性表的定義2.線性結(jié)構(gòu)的特點

3.線性表的長度4.位序5.空表如：(A,B,C,D,………,Z)(85,67,78,65,……,92)((‘m’,87),(‘f’,65),……(‘m’,92))

1.定義:含有大量記錄的線性表又稱為文件線性表是由有限個元素構(gòu)成的有序序列可記作：〔a1,a2,……,an〕2.特點:(1)表中每個元素都有它自己的位置除第一個元素外，每個元素都有唯一的前驅(qū)除最后一個元素外，每個元素都有唯一的后繼i是ai在線性表中的位序(索引)(2)表中元素具有相同特性(數(shù)據(jù)類型),

屬于同一數(shù)據(jù)對象有序性均勻性二、線性表的ADTADTList{數(shù)據(jù)對象:D={ai∣ai∈ElemSet,i=1,2,3，…,n,n≥0}數(shù)據(jù)關(guān)系:R={<ai-1,ai>∣ai-1、ai∈D,i=2,3,…,n}根本操作:InitList(&L);操作結(jié)果:構(gòu)造一個空的線性表L.DestroyList(&L);

初始條件:線性表L已經(jīng)存在.

操作結(jié)果:銷毀線性表L.1003張三女9887671002李四男9992741021王五男787677ClearList(&L);

初始條件:線性表L已經(jīng)存在.

操作結(jié)果:將L重置為空表.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776

ListEmpty(L);初始條件:線性表L已經(jīng)存在.操作結(jié)果:假設(shè)L為空表,那么返回TRUE,否那么返回FALSE.1003張三女9887671002李四男9992741021王五男787677TRUEFALSEListLength(L);

初始條件:線性表L已經(jīng)存在.

操作結(jié)果:返回L中數(shù)據(jù)元素個數(shù).GetElem(L,i,&e);

初始條件:線性表L已經(jīng)存在,1≤i≤ListLength(L).

操作結(jié)果:用e存放L中第i個數(shù)據(jù)元素的值.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776ListLength(L)為4GetElem(L,3,e);e為王五的數(shù)據(jù)LocateElem(L,e,compare());初始條件:線性表L已經(jīng)存在,compare()是數(shù)據(jù)元素判定函數(shù).操作結(jié)果:返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序.假設(shè)這樣的數(shù)據(jù)元素不存在,那么返回值為0.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776假設(shè)e為王五，那么LocateElem(L,e,equal)返回3假設(shè)e為馬六，那么LocateElem(L,e,equal)返回0PriorElem(L,cur_e,&pre_e);初始條件:線性表L已經(jīng)存在.操作結(jié)果:假設(shè)cur_e是L的數(shù)據(jù)元素,且不是第一個,那么用pre_e存放它的前驅(qū),否那么操作失敗,pre_e無定義.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776假設(shè)cur_e為李四，PriorElem(L,cur_e,pre_e);pre_e為張三假設(shè)cur_e為張三，PriorElem(L,cur_e,pre_e);pre_e值無意義NextElem(L,cur_e,&next_e);初始條件:線性表L已經(jīng)存在.操作結(jié)果:假設(shè)cur_e是L的數(shù)據(jù)元素,且不是最后一個,那么用next_e存放它的后繼,否那么操作失敗,next_e無定義.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776假設(shè)cur_e為李四，NextElem(L,cur_e,next_e);next_e為王五假設(shè)cur_e為萬一，NextElem(L,cur_e,next_e);next_e值無意義ListInsert(&L,i,e);初始條件:線性表L已經(jīng)存在,1≤i≤ListLength(L)+1.操作結(jié)果:在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加1.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776ListInsert(L,3,e);e為馬六的數(shù)據(jù)1033馬六男8080801021王五男7876771008萬一女756776ListDelete(&L,i,&e);初始條件:線性表L已經(jīng)存在且非空,1≤i≤ListLength(L).操作結(jié)果:刪除L的第i個數(shù)據(jù)元素,并用e存放其值,L的長度減1.1003張三女9887671002李四男9992741021王五男7876771008萬一女756776ListDelete(L,3,e);1008萬一女756776ListTraverse(L,visit());初始條件:線性表L已經(jīng)存在.操作結(jié)果:依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit().一旦visit()失敗,那么操作失敗.}ADTListInitList(&L);DestroyList(&L);ClearList(&L);ListLength(L);GetElem(L,i,&e);LocateElem(L,e,compare());PriorElem(L,cur_e,&pre_e);NextElem(L,cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);ListTraverse(L,visit());例2-1用線性表LA和LB分別表示集合A和B，利用線性表運算實現(xiàn)A=A

Bvoidunion(List&La,ListLb){La_len=ListLength(La);//計算A的長度Lb_len=ListLength(Lb);//計算B的長度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取B中一個元素if(!LocateElem(La,e,equal))//檢查A中有無？ListInsert(La,++La_len,e);//沒有就插在表尾}}//union例2-2線性表LA和LB分別表示兩個非遞減序的有序序列，利用線性表運算把LA和LB合并成一個有序序列LCvoidMergeList(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);}}//MergeList線性表的物理結(jié)構(gòu)a1a2……an

∧

a1a3a2abdfh42576398010110線性表的物理結(jié)構(gòu)靜態(tài)鏈表2.2線性表的順序表示和實現(xiàn)線性表的順序表示是指:

用一組地址連續(xù)的存儲單元

依次存儲線性表中的數(shù)據(jù)元素即：邏輯相鄰，物理也相鄰，以物理相鄰表示元素之間的邏輯相鄰a1a2……an一、順序表示設(shè)ai的物理存儲位置為LOC(ai)，需要的存儲單元長度為hLOC(ai)=LOC(ai-1)+hLOC(ai)=LOC(a1)+(i-1)*h

每個元素的存儲位置與線性表的起始位置相差一個常數(shù),該常數(shù)與數(shù)據(jù)元素的位序成正比因此，可以隨機存取，且任一元素的存取時間相同.//–––––線性表的動態(tài)分配順序存儲結(jié)構(gòu)–––––#defineLIST_INIT_SIZE100//線性表存儲空間的初始分配#defineLISTINCREMENT10//線性表存儲空間的分配增量typedefstruct{

ElemType*elem;//存儲空間基址

intlength;//當前長度

intlistsize;//當前分配的存儲容量}SqList;3597...L.elemSqListL;L.length=4;L.listsize=100;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_Sq(SqList&L){//構(gòu)造一個空的線性表L.L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲分配失敗

L.length=0;//空表長度為0L.listsize=LIST_INIT_SIZE;//初始存儲容量

returnOK;}//InitList_Sq二、線性表的動態(tài)分配實現(xiàn)01234567……98991.初始化：L.elem2.插入元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){q=&(L.elem[i-1]); //q為插入位置if(L.length>=1)for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;//插入e++L.length;returnOK;//表長增1}//ListInsert_SqL.elemi-1qpen-1if(i<1‖i>L.length+1)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;//增加存儲容量

}

算法執(zhí)行時間主要花在移動元素上設(shè)pi表示在第i個元素之前插入新元素的概率在第i個元素之前插入新元素需移動n-i+1個元素平均移動次數(shù)為：T(n)=O(n)3.刪除元素StatusListDelete_Sq(SqList&L,inti,ElemType&e)

{//在順序線性表L中刪除第i個元素,并用e返回其值

//i的合法值為1≤i≤ListLength_Sq(L)if((i<1)‖(i>L.length))returnERROR;

//i值不合法}//ListDelete_sqL.elemi-1pqen-1

p=&(L.elem[i-1]);

//p為被刪除元素的位置

e=*p;

//被刪除元素的值賦給e

q=L.elem+L.length-1

//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;

//被刪除元素之后的元素左移

--L.length;

//表長減1

returnOK;設(shè)刪除第i個元素的概率為Pi那么平均移動元素的次數(shù)為：T(n)=O(n)intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個值與e滿足compare()的元素的位序//假設(shè)找到,那么返回其在L中的位序,否那么返回0i=1;//i的初值為第1個元素的位序p=L.elem;//p的初值為第1個元素的存儲位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sqvoidunion_Sq(SqList&La,SqListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中La_len=ListLength_Sq(La);Lb_len=ListLength_Sq(Lb);//求線性表的長度for(i=1;i<=Lb_len;i++){GetElem_Sq(Lb,i,e);//取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem_Sq(La,e,equal))ListInsert_Sq(La,++La_len,e);//La中不存在和e相同的數(shù)據(jù)元素,那么插入之}}//union4·合并兩個集合5·合并有序序列順序線性表La和Lb的元素按值非遞減排列歸并La和Lb得到新的順序線性表Lc,Lc的元素也按值非遞減排列voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){InitList_Sq(Lc);i=j=1;k=0;La_len=ListLength_Sq(La);Lb_len=ListLength_Sq(Lb);

while((i<=La_len)&&(j<=Lb_len))//La和Lb均為空

{GetElem_Sq(La,i,ai);GetElem_Sq(Lb,j,bj);if(ai<=bj){ListInsert_Sq(Lc,++k,ai);++i;}else{ListInsert_Sq(Lc,++k,bj);++j;}}

while(i<=La_len){GetElem_Sq(La,i++,a);ListInsert_Sq(Lc,++k,a);}while(j<=Lb_len){GetElem_Sq(Lb,j++,b);ListInsert_Sq(Lc,++k,b);}}//MergeLest_SqvoidMergeList_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++;eles*pc++=*pb++;

}while(pa<=pa_last)*pc++=*pa++;

//插入La的剩余元素

while(pb<=pb_last)*pc++=*pb++;

//插入Lb的剩余元素}//MergeLest_Sq2·3線性表的鏈式表示和實現(xiàn)一、線性鏈表

靜態(tài)鏈表二、循環(huán)鏈表三、雙向鏈表∧∧∧∧數(shù)據(jù)域指針域

1.存儲映象

用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素既需要表示數(shù)據(jù)元素,又需要表示相鄰元素的邏輯關(guān)系。鏈表中只有一個指針域的鏈表稱為線性鏈表或單鏈表一、線性鏈表2.線性鏈表的特點：

★整個鏈表的存取必須從頭指針開始★最后一個結(jié)點的指針域為空NULL

★用指針表示數(shù)據(jù)元素之間的邏輯關(guān)系鏈表是非隨機存取的存儲結(jié)構(gòu)

★可附設(shè)頭指針

★一種動態(tài)結(jié)構(gòu)，表可以擴充∧∧3.線性鏈表的運算⑴存儲結(jié)構(gòu)typedefstructLNode{ElemTypedata;

structLNode*next;}LNode,*LinkList;LNodedatanextLinkListStatusInitList_L(LinkList&L){//建立一個空的鏈表，L為帶頭結(jié)點的單鏈表的頭指針.

L=(LinkList)malloc(sizeof(LNode));//生成頭結(jié)點

if(!L)returnERROR;L->next=NULL;returnOK;}//InitList_L∧⑵獲取第i個元素StatusGetElem_L(LinkListL,inti,ElemType&e){//L為帶頭結(jié)點的單鏈表的頭指針.//當?shù)趇個元素存在時,其值賦給e并返回OK,否那么返回ERRORp=L->next;j=1;//初始化,p指向第一個結(jié)點,j為計數(shù)器while(p&&j<i){//順指針向后查找,直到p指向第i個元素或p為空p=p->next;++j;}if(!p||j>i)returnERROR;//第i個元素不存在e=p->data;//取第i個元素returnOK;}//GetElem_LStatusListInsert_L(LinkList&L,inti,ElemTypee){//在帶頭結(jié)點的單線性鏈表L中第i個位置之前插入元素ep=L;j=0;while(p&&j<i-1){p=p->next;++j;}

//尋找第i-1個結(jié)點

if(!p‖j>i-1)returnERROR;//i小于1或者大于表長

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點

s->data=e;s->next=p->next;

//插入L中

p->next=s;returnOK;}//ListInsert_L⑶插入元素⑷刪除元素StatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點的單鏈線性表L中,刪除第i個元素,并由e返回其值

p=L;j=0;

while(p->next&&j<i-1){p=p->next;++j;}//尋找第i個元素,并令p指向其前驅(qū)

if(!(p->next)‖j>i-1)returnERROR;//刪除位置不合理

q=p->next;p->next=q->next;//刪除并釋放結(jié)點

e=q->data;free(q);returnOK;}//ListDelete_LvoidCreateList_L(LinkList&L,intn){//逆位序輸入n個元素的值,建立帶表頭結(jié)點的單鏈線性表L.L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結(jié)點的單鏈表

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入到表頭

}}//CreateList_L⑸逆位序輸入元素的值，建立線性鏈表voidCreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);p->next=L->next;L->next=p;}}//CreateList_L⑹把兩個有序鏈表合并成一個有序鏈表voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){InitList_L(Lc);i=j=1;k=0;La_len=ListLength_L(La);Lb_len=ListLength_L(Lb);while((i<=La_len)&&(j<=Lb_len))//La和Lb均為空

{GetElem_L(La,i,ai);GetElem_L(Lb,j,bj);if(ai<=bj){ListInsert_L(Lc,++k,ai);++i;}else{ListInsert_L(Lc,++k,bj);++j;}}while(i<=La_len){GetElem_L(La,i++,a);ListInsert_L(Lc,++k,a);}while(j<=Lb_len){GetElem_L(Lb,j++,b);ListInsert_L(Lc,++k,b);}}//MergeLest_LvoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//單鏈線性表La和Lb的元素按值非遞減排列//歸并La和Lb得到新的單鏈線性表Lc,Lc的元素也按值非遞減排列pa=La->next;pb=Lb->next;Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點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é)點}//MergeList_L靜態(tài)鏈表特點:1.在靜態(tài)空間里實現(xiàn)動態(tài)數(shù)據(jù)結(jié)構(gòu)2.兩個鏈表:數(shù)據(jù)鏈表和空閑空間鏈表3.沒有現(xiàn)成的空間管理函數(shù)下標01234567891011abdfhabdfh42576398010110234567891.靜態(tài)鏈表用一維數(shù)組存儲鏈表//–––––線性表的靜態(tài)單鏈表存儲結(jié)構(gòu)–––––//#defineMAXSIZE1000

//鏈表的最大長度typedefstruct{ElemTypedata;intcur;}component,SlinkList[MAXSIZE];2·運算：

1 2 3456 78 910110下標01234567891011123456789⑴初始化voidInitSpace_SL(SlinkList&space){//將一維數(shù)組space中各分量鏈成一個備用鏈表,//space[0].cur為頭指針，"0"表示空指針

for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//InitSpace_SL123456789

⑵申請建立一個結(jié)點intMalloc_SL(SlinkList&space){//假設(shè)備用空間鏈表非空,那么返回分配的結(jié)點下標,否那么返回0i=space[0].cur;if(space[0].cur)space[0].cur=space[i].cur;returni;}//Malloc_SL⑶回收一個結(jié)點voidFree_SL(SlinkList&space,intk)

⑶回收一個結(jié)點voidFree_SL(SlinkList&space,intk)

//將下標為k的空閑結(jié)點收回到備用鏈表{space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL⑷查找第一個值為e的元素intLocateElem_SL(SlinkListS,ElemTypee){//在靜態(tài)鏈表線性表S中查找第1個值為e的元素.//假設(shè)找到,那么返回它在S中的位序,否那么返回0.i=S[0].cur;//i指示表中第一個結(jié)點while(i&&S[i].data!=e)i=S[i].cur;//在表中順鏈查找returni;}//LocateElem_SLA={a,d,h,f,m,c},B={h,t,u,c}123456789⑸完成集合運算〔A-B〕〔B-A〕0123456789101112345678910110123456789adhfmcr0123456789101182345670910110adhfmc123567u9adtfmcr0123456789101172350689410110adtfmu二、循環(huán)鏈表

1·特點：表中最后一個結(jié)點的指針域指向頭結(jié)點從表的任一結(jié)點出發(fā)均可訪問表中其他結(jié)點2·操作3·僅設(shè)尾指針的循環(huán)鏈表存儲結(jié)構(gòu)typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在帶頭結(jié)點的循環(huán)鏈表L中第i個位置之前插入元素e

p=L;j=0;while(p->next!=L&&j<i-1){p=p->next;++j;}

//尋找第i-1個結(jié)點

if(j>i-1||j<i-1)returnERROR;//i小于1或者大于表長

s=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點

s->data=e;s->next=p->next;//插入L中

p->next=s;returnOK;}//ListInsert_L三、雙向鏈表1．雙向鏈表的結(jié)點結(jié)構(gòu)//–––––線性表的雙向鏈表存儲結(jié)構(gòu)–––––typedefstructDuLNode{ElemTypedata;structDuLNode*prior;

structDuLNode*next;}DuLNode,*DuLinkList;2·特點〔1〕設(shè)d為DuLinkList型變量d->next->prior=d;d->prior->next=d;〔2〕插入與刪除不太方便a1a3a2表（a1,a2,a3）空表Status

ListInsert_DuL(DuLinkList&L,inti,ElemTypee){

//在帶頭結(jié)點的雙鏈循環(huán)線表L中第i個位置之前插入元素e,//i的合法值為1≤i≤表長+1.

p=L->next;j=1;while(p->next!=L&&j<i){p=p->next;j++;}

if(j<i||j>i)

returnERROR;

//第i個元素不存在

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;}//ListInsert_DuLStatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){//刪除帶頭結(jié)點的雙鏈循環(huán)線性鏈表L的第i個元素,i的合法值為1≤i≤表長

if(!(p=GetElemP_DuL(L,i)))returnERROR;

e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}//ListDelete_DuL改進線性鏈表的結(jié)構(gòu)：1.增加表長設(shè)置2.增加表尾指針3.設(shè)置當前位置指針的操作五、對帶頭結(jié)點的單向鏈表的重新定義typedefstructLNode //結(jié)點類型{ElemTypedata; structLNode*next;}*Link,*Position;typedefstruct//鏈表類型{Linkhead,tail;

//分別指向線性鏈表中的頭結(jié)點和最后一個結(jié)點

intlen;

//指向線性鏈表中數(shù)據(jù)元素的個數(shù)}LinkList;StatusMakeNode(Link&p,ElemTypee);//建立由p指向的值為e的結(jié)點，并返回OK，假設(shè)建立失敗，那么返回ERRORStatusInitList(LinkList&L)；

//構(gòu)造一個空的線性鏈表L.voidFreeNode(Link&p);//釋放p所指向的結(jié)點eppp=NULL

∧L.headL.tailL.len=0StatusDestroyList(LinkList&L)；

//銷毀線性鏈表L，L不再存在.StatusClearList(LinkList&L)；

//將線性表L重置為空表，并釋放原鏈表的結(jié)點空間.

∧L.headL.head=L.tail=NULLL.len=0L.tail

∧L.headL.tail

∧L.headL.tailStatusInsFirst(Linkh,Links)；//h指向線性鏈表的一個結(jié)點，將s所指結(jié)點插入在h結(jié)點之后

∧sh

∧shStatusDelFirst(Linkh,Link&q);//h指向線性鏈表的一個結(jié)點//刪除鏈表中h后第一個結(jié)點并以q返回

∧h

∧qhStatusAppend(LinkList&L,Links);

//將指針s所指的一串結(jié)點鏈接在線性表L的最后一個結(jié)點之后，

//并改變鏈表L的尾指針指向新的尾結(jié)點

∧L.headL.tailS

L.headL.tailS∧StatusRemove(LinkList&L,link&q);

//刪除線性鏈表L中的尾結(jié)點并以q返回，

//改變鏈表L的尾指針指向新的尾結(jié)點

∧L.headL.tailq

L.headL.tail∧StatusInBefore(LinkList&L,Link&p,Links);//p指向線性鏈表L中的一個結(jié)點，將s所指結(jié)點插入在p所指結(jié)點之前//并修改指針p指向新插入的結(jié)點

∧sp

∧spStatusInAfter(LinkList&L,Link&p,Links);//p指向線性鏈表L中的一個結(jié)點，將s所指結(jié)點插入在p所在結(jié)點之后，//并修改指針p指向新插入的結(jié)點

∧sp

∧spStatusSetCurElem(Link&p,ElemTypee);//p指向線性鏈表L中的一個結(jié)點，用e更新p所指向結(jié)點中數(shù)據(jù)元素的值∧peElemTypeGetCurElem(Linkp);//p指向線性鏈表L中的一個結(jié)點，返回p所指向結(jié)點中數(shù)據(jù)元素的值StatusListEmpty(LinkListL);//假設(shè)線性表L為空表,那么返回TRUE,否那么返回FALSE.intListLength(LinkListL);//返回線性表L中數(shù)據(jù)元素個數(shù).PositionGetHead(LinkListL);//返回線性表L中頭結(jié)點的位置PositionGetLast(LinkListL);//返回線性表L中最后一個結(jié)點的位置PositionPriorPos(LinkListL,Linkp)；//P指向線性表L中的一個結(jié)點，返回p所指向結(jié)點的直接前驅(qū)的位置//假設(shè)無前驅(qū)，那么返回NULL。PositionNextPos(LinkListL,Linkp)；//P指向線性表L中的一個結(jié)點，返回p所指向結(jié)點的直接后繼的位置//假設(shè)無后繼，那么返回NULL。StatusLocatePos(LinkListL,inti,Link&p);//p指向線性鏈表L中第i個結(jié)點的位置并返回OK，i值不合法時返回ERROR。PositionLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//返回線性表L中第1個與e滿足關(guān)系compare()判定關(guān)系的數(shù)據(jù)元素的位置.//假設(shè)這樣的數(shù)據(jù)元素不存在,那么返回值為NULL.StatusListTraverse(LinkListL,Status(*visit)());//依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit().一旦visit()失敗,那么操作失敗.StatusMakeNode(Link&p,ElemTypee);voidFreeNode(Link&p);StatusInitList(LinkList&L)；StatusDestroyList(LinkList&L)；StatusClearList(LinkList&L)；StatusInsFirst(Linkh,Links)；StatusDelFirst(Linkh,Link&q);StatusAppend(LinkList&L,Links);StatusRemove(LinkList&L,link&q);StatusInBefore(LinkList&L,Link&p,Links);StatusInAfter(LinkList&L,Link&p,Links);StatusSetCurElem(Link&p,ElemTypee);ElemTypeGetCurElem(Linkp);StatusListEmpty(LinkListL);intListLength(LinkListL);PositionGetHead(LinkListL);PositionGetLast(LinkListL);PositionPriorPos(LinkListL,Linkp)；PositionNextPos(LinkListL,Linkp)；StatusLocatePos(LinkListL,inti,Link&p);PositionLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));StatusListTraverse(LinkListL,Status(*visit)());StatusLinkInsert_L(LinkList&L,inti,ElemTypee)

{//在帶頭結(jié)點的單鏈線性表L的第i個元素之前插入元素e

if(!LocatePos(L,i-1,h))returnERROR;

//i值不合法

if(!MakeNode(s,e))returnERROR;

//結(jié)點存儲分配失敗

InsAfter(L,h,s);

//對于從第i個結(jié)點開始的鏈表，第i-1個結(jié)點是它的頭結(jié)點

returnOK;

}//ListInsert_LvoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc,int(*compare)(ElemType,ElemType)){//單鏈線性表中的元素按值非遞減排列,歸并和得到新的單鏈線性表，元素也按非遞減排列if(!InitList(Lc))returnERROR; //存儲空間分配失敗ha=GetHead(La);hb=GetHead(Lb);//ha和hb分別指向La和Lb的頭結(jié)點pa=NextPos(La,ha);pb=NextPos(Lb,hb); //pa和pb分別指向La和Lb的當前結(jié)點while(pa&&pb)//La和Lb均非空{(diào)a=GetCurElem(pa);b=GetCurElem(pb);//a和b為兩表中當前比較元素if((*compare)(a,b)<=0) /a<=b{DelFirst(ha,q);Append(Lc,q);pa=NextPos(La,ha);}else{DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,hb);}}//whileif(!ListEmpty(La))//pa

Append(Lc,pa);

//鏈接La中剩余結(jié)點

elseAppend(Lc,pb); //鏈接Lb中剩余結(jié)點FreeNode(ha);FreeNode(hb);

//釋放La和Lb的頭結(jié)點returnOk;}//MergeList_L多項式(Polynomial)n階多項式Pn(x)有n+1項。

系數(shù)a0,a1,a2,…,an

指數(shù)0,1,2,…,n。按升冪排列2.4一元多項式的表示及相加Pn(x)=1+x2+4x3+2x5+6x6Sn(x)=1+x8+2x60+3x100一、一元多項式的表示((1,0),(0,1),(1,2),(4,3),(0,4),(2,5),(6,6))((1,0),(1,8),(2,60),(3,100))ADTPolynomial{數(shù)據(jù)對象:D={ai∣ai∈TermSet,i=1,2,…,m,m≥0;TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)}數(shù)據(jù)關(guān)系:R={<ai-1,ai>∣ai-1,ai∈D,且ai-1中的指數(shù)值<ai中的指數(shù)值,i=1,2,…,n}根本操作:CreatePolyn(&P,m)操作結(jié)果:輸入m項的系數(shù)和指數(shù),建立一元多項式P.DestroyPolyn(&P)操作結(jié)果:銷毀一元多項式P.二、一元多項式的抽象數(shù)據(jù)類型定義

PrintPolyn(P)

操作結(jié)果:打印輸出一元多項式P.PolynLength(P)

操作結(jié)果:返回一元多項式P中的項數(shù),AddPolyn(&Pa,&Pb)

操作結(jié)果:完成多項式相加運算,即:Pa=Pa+Pb,并銷毀一元多項式Pb.

SubtractPolyn(&Pa,&Pb)

操作結(jié)果:完成多項式相減運算,即:Pa=Pa-Pb,并銷毀一元多項式Pb.

MultiplyPolyn(&Pa,&Pb)

操作結(jié)果:完成多項式相乘運算,即:Pa=Pa*Pb,并銷毀一元多項式Pb.

}ADTPolynomial三、一元多項式抽象數(shù)據(jù)類型的實現(xiàn)StatusLocateElem(LinkListL,ElemTypee,Position&q,int(*compare)(ElemType,ElemType));//假設(shè)有序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素,//那么q指示L中第一個這樣的結(jié)點的位置,并返回TRUE;//否那么q指示第一個與e滿足判定函數(shù)//compare()取值>0的元素的前驅(qū)的位置,并返回FALSEStatusOrderInsert(LinkList&L,ElemTypee,int(*compare)(ElemType,ElemType));//按有序判定函數(shù)compare()的約定,//將值為e的結(jié)點插入到有序鏈表L的適當位置例2-4抽象數(shù)據(jù)類型Polynomial的實現(xiàn).typedefstruct{//項的表示,多項式的項作為LinkList的數(shù)據(jù)元素

floatcoef;

//系數(shù)COEFFICIENT

intexpn;

//指數(shù)EXPONENT}term,ElemType;

//兩個類型名:term用于本ADT,ElemType為LinkList的數(shù)據(jù)對象名typedefLinkListpolynomial;

//用帶表頭結(jié)點的有序鏈表表示多項式//–––––根本操作的函數(shù)原型說明–––––//voidCreatePolyn(polynomial&P,intm);//輸入m項的系數(shù)和指數(shù),建立表示一元多項式的有序鏈表PvoidDestroyPolyn(polynomial&P);//銷毀一元多項式PvoidPrintPolyn(polynomialP);//打印輸出一元多項式PintPolynLeng