《馮毅數(shù)據(jù)結(jié)構(gòu)ch》

實(shí)例線性表的邏輯結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)下一章第二章線性表線性表的應(yīng)用舉例順序表與鏈表比較書目自動(dòng)檢索系統(tǒng)書目文件1、各條書目信息之間存在一個(gè)對一個(gè)的線性關(guān)系2、如何在計(jì)算機(jī)中存儲書目信息3、數(shù)據(jù)操作：查找，插入，刪除，修改等線性表實(shí)例約瑟夫環(huán)(JosephCircle)問題描述：

編號為1,2,...,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）?，F(xiàn)在給定一個(gè)隨機(jī)數(shù)m>0，從編號為1的人開始，按順時(shí)針方向1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止。報(bào)m的人出圈，同時(shí)留下他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始，重新從1開始報(bào)數(shù)，如此下去，直至所有的人全部出列為止。 請編寫程序求出圈的順序。45961573182132245例：m：密碼k：計(jì)數(shù)出隊(duì)序列：start526743k=1311、各元素之間存在一個(gè)對一個(gè)的線性關(guān)系2、如何在計(jì)算機(jī)中存儲3、數(shù)據(jù)操作：查找，刪除等約瑟夫環(huán)(JosephCircle)在數(shù)據(jù)元素的非空有限集中存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼線性結(jié)構(gòu)特點(diǎn)定義：一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列例英文字母表（A,B,C,…..Z)是一個(gè)線性表例數(shù)據(jù)元素特征：有限、序列、同構(gòu)元素個(gè)數(shù)n—表長度，n=0空表1<i<n時(shí)ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼元素同構(gòu)，且不能出現(xiàn)缺項(xiàng)運(yùn)算：存取插入刪除查找合并分解排序求長度線性表的邏輯結(jié)構(gòu)ADT

List{數(shù)據(jù)對象：D={ai|aiElemSet,i=1,2,…,n,n≥0},n—表長,n=0,空表

數(shù)據(jù)關(guān)系：R={<ai-1，ai>|ai-1，aiD,i=2，…，n},i為ai在線性表中位序

基本操作：結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作

引用型操作(只讀操作)

加工型操作(修改操作)}ADT

List線性表的抽象數(shù)據(jù)類型定義初始化操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空線性表L結(jié)構(gòu)銷毀操作：

DestroyList(&L)

初始條件：線性表L已存在操作結(jié)果：銷毀線性表L引用型操作：

ListEmpty(L)//線性表判空

初始條件：線性表L已存在操作結(jié)果：若L為空表，返回TRUE;否則返回FALSE

ListLength(L)//求線性表的表長

初始條件：線性表L已存在操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)

GetElem(L,i,&e)//求線性表的第i個(gè)元素

初始條件：線性表L已存在，且1≤i≤ListLength(L)操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值線性表的抽象數(shù)據(jù)類型定義引用型操作：

LocateElem(L,e,compare())//定位函數(shù)

初始條件：線性表L已存在，compare()是元素判定函數(shù)操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的元素的位序。

PriorElem(L,cur_e,&pre_e)//求數(shù)據(jù)元素的前驅(qū)

初始條件：線性表L已存在操作結(jié)果：若cur_e是L中元素，且不是第一個(gè)，則用pre_e 返回其前驅(qū)；否則操作失敗，pre_e無定義

NextElem(L,cur_e,&next_e)//求數(shù)據(jù)元素的后繼

初始條件：線性表L已存在操作結(jié)果：若cur_e是L中元素,且不是最后一個(gè),則用next_e 返回其后繼;否則操作失敗，next_e無定義

ListTraverse(L,visit())//線性表遍歷

初始條件：線性表L已存在,visit()為某個(gè)訪問函數(shù)操作結(jié)果：依次對L中每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操 作失敗線性表的抽象數(shù)據(jù)類型定義加工型操作：

ClearList(&L)//線性表置空

初始條件：線性表L已存在操作結(jié)果：將L重置為空表

ListInsert(&L,i,e)//插入數(shù)據(jù)元素

初始條件：線性表L已存在，且1≤i≤ListLength(L)+1操作結(jié)果：在L中第第i個(gè)位置之前插入元素e,L的長度加1

ListDelete(&L,i,&e)//刪除數(shù)據(jù)元素

初始條件：線性表L已存在且非空，1≤i≤ListLength(L)操作結(jié)果：刪除L的第i個(gè)元素,并用e返回其值,L的長度減1

線性表的抽象數(shù)據(jù)類型定義

線性表的順序存儲結(jié)構(gòu)an……..ai……..a2a1LLOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L其中：L—一個(gè)元素占用的存儲單元個(gè)數(shù)LOC(ai)—線性表第i個(gè)元素的地址特點(diǎn)：實(shí)現(xiàn)邏輯上相鄰—物理地址相鄰實(shí)現(xiàn)隨機(jī)存取實(shí)現(xiàn)：可用C語言的一維數(shù)組實(shí)現(xiàn)順序表定義：用一組地址連續(xù)的存儲單元存放一個(gè)線性表叫~元素地址計(jì)算方法：length表長listsize表容量elem存儲區(qū)首地址a1a2an01length-1listsize-1elem順序表實(shí)現(xiàn)/*定義動(dòng)態(tài)順序表*/typedefint

ElemType;#defineLIST_INIT_SIZE100

//線性表存儲空間的初始分配量#defineLISTINCREMENT10

//線性表存儲空間的分配增量typedefstruct{ElemType*elem;//存儲空間基址intlength;//當(dāng)前表長intlistsize;//當(dāng)前分配的存儲容量//以sizeof(ElemType)為單位}SqList;線性表的基本操作在順序表中的實(shí)現(xiàn)Status

InitList_Sq(SqList&L){L.elem=(ElemType*)malloc(

LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);

L.length=0;

L.listsize=LIST_INIT_SIZE;return(OK);}順序表結(jié)構(gòu)初始化：length=0表長listsize=LIST_INIT_SIZE表容量elem存儲區(qū)基址a1a2an01length-1listsize-1elem算法時(shí)間復(fù)雜度：O(1)線性表的基本操作在順序表中的實(shí)現(xiàn)int

LocateElem_Sq(SqListL,ElemTypee){}順序表查找：算法時(shí)間復(fù)雜度：O(n

)找64ppppppp

513192137566475查找成功L.elemL.lengthL.listsizei=

1;

//i初值為第1元素的位序p=L.elem;

//p指向第一個(gè)元素while(i<=L.length&&*p++!=e)i++;if(i<=L.length)returni;elsereturn0;inti;ElemType*p;i=1234567順序表刪除定義：線性表的刪除是指將第i（1iL.length）個(gè)元素刪除，使長度為L.length的線性表

變成長度為L.length-1的線性表需將第i+1至第L.length共（L.length-i)個(gè)元素前移線性表的基本操作在順序表中的實(shí)現(xiàn)a1a2aiai+1an12ii+1L.lengtha1a2ai+1ai+2an12ii+1L.length-1L.lengthai+1ai+2an順序表刪除線性表的基本操作在順序表中的實(shí)現(xiàn)Status

ListDelete_Sq(SqList&L,inti,ElemType&e){if(i<1||i>L.length)returnERROR;

p=&(L.elem[i-1]);//p指向被刪除元素

e=*p;//被刪除元素賦給e

q=L.elem+L.length-1;//q指向表尾元素for(++p;p<=q;p++)*(p-1)=*p;--L.length;//表長減1return(OK);}順序表刪除算法：ElemType*p,*q;a1a2...ai-1an...aiai+1L.elempqpai+1an...pp線性表的基本操作在順序表中的實(shí)現(xiàn)判斷i值合法性元素依次前移算法時(shí)間復(fù)雜度：O(n

)設(shè)Qi是刪除第i個(gè)元素的概率，則在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個(gè)元素時(shí)，平均移動(dòng)表的一半元素，當(dāng)n很大時(shí)，效率很低順序表刪除算法評價(jià)：線性表的基本操作在順序表中的實(shí)現(xiàn)順序表插入定義：線性表的插入是指在第i（1iL.length+1）個(gè)元素之前插入一個(gè)新的元素x，使長度為L.length的線性表變成長度為L.length+1的線性表需將第i至第n共（L.length-i+1)個(gè)元素后移線性表的基本操作在順序表中的實(shí)現(xiàn)a1a2aiai+1an12ii+1L.lengthL.length+1anai+1aix順序表插入線性表的基本操作在順序表中的實(shí)現(xiàn)Status

ListInsert_Sq(SqList&L,inti,ElemTypee){if(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;}

q=&(L.elem[i-1]);//q指向插入位置,p指向表尾元素for(

;p>=q;p--)*(p+1)=*p;

*q=e;++L.length;//線性表長度加1return(OK);}順序表插入算法：ElemType*q,*p,*newbase;線性表的基本操作在順序表中的實(shí)現(xiàn)判斷i值合法性判斷是否溢出元素后移插入算法時(shí)間復(fù)雜度：O(n

)p=&(L.elem[L.length-1])設(shè)Pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)的元素次數(shù)的平均次數(shù)為：順序表插入算法評價(jià)：線性表的基本操作在順序表中的實(shí)現(xiàn)優(yōu)點(diǎn)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素存儲空間使用緊湊缺點(diǎn)插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充順序表特點(diǎn)a1a2...aian...鏈?zhǔn)酱鎯Y(jié)構(gòu)……a1a2aian邏輯結(jié)構(gòu)a1a3...an順序存儲結(jié)構(gòu)a2ai...線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點(diǎn)

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)域指針域結(jié)點(diǎn)^ZHAOQIANSUNLIZHOUWUZHENGWANGH例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)域指針域?qū)崿F(xiàn)typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;LNode*h,*p;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)的指針域生成一個(gè)LNode型新結(jié)點(diǎn)：p=(LNode*)malloc(sizeof(LNode));系統(tǒng)回收p結(jié)點(diǎn)：free(p)定義：結(jié)點(diǎn)中只含一個(gè)指針域的鏈表叫~，也叫線性鏈表單鏈表頭結(jié)點(diǎn)：在單鏈表第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)叫～頭結(jié)點(diǎn)指針域?yàn)榭毡硎揪€性表為空La1a2頭結(jié)點(diǎn)an

^…...L空表^頭指針La1a2a3an……^頭指針LinkList

L;單鏈表GetElem(L,i,&e)

：取第i個(gè)數(shù)據(jù)元素。若存在，其值賦給e并返回OK；否則返回ERROR算法思路ppp頭指針La1a2a3an……^Status

GetElem_L(LinkListL,inti,ElemType&e){

p=L->next;//p指向第一個(gè)元素

j=1;//j做計(jì)數(shù)器while()//順鏈查找{}if()//若i不存在returnERROR;

e=p->data;//取得第i個(gè)元素return(OK);}LNode*p;

intj;p==NULL||j>ip!=NULL&&j<ip=p->next;j++;算法時(shí)間復(fù)雜度：O(n)單鏈表基本操作LocateElem_L(L,e)

：查找單鏈表中是否存在結(jié)點(diǎn)e，若有則返回指向e結(jié)點(diǎn)的指針；否則返回NULL算法描述LNode*LocateElem_L(LinkListL,ElemTypee){ LNode*p;

p=L->next; while()

p=p->next; return(p);}pppp&&p->data!=eLa1a2a3an……^單鏈表基本操作While循環(huán)中語句頻度為若找到結(jié)點(diǎn)e，為結(jié)點(diǎn)e在表中的位序否則，為n算法評價(jià)單鏈表基本操作LocateElem_L(L,e)

：查找單鏈表中是否存在結(jié)點(diǎn)e，若有則返回指向e結(jié)點(diǎn)的指針；否則返回NULL算法描述LNode*LocateElem_L(LinkListL,ElemTypee){ LNode*p;

p=L->next; while()

p=p->next; return(p);}p&&p->data!=eListInsert(&L,i,e)

：在第i個(gè)元素前插入e。若i非法，返回ERROR；否則返回OK算法思路考慮：在線性表兩個(gè)數(shù)據(jù)元素a和b間插入e，已知p指向apabess->next=p->next;p->next=s;s=(LinkList)malloc(sizeof(LNode));s->data=e;思考：指針修改順序是否可交換？特別注意：修改指針的語句次序一定要小心處理，否則會出現(xiàn)意想不到的錯(cuò)誤。單鏈表基本操作ListInsert(&L,i,e)

：在第i個(gè)元素前插入e。若i非法，返回ERROR；否則返回OK單鏈表基本操作……a1

ai

an^L

ai-1

ai+1

p①

e

s②③④(a1,a2,…,ai-1,ai,ai+1,…,an)(a1,a2,…,ai-1,e,ai,ai+1,…,an)StatusListInsert_L

(LinkList&L,int

i,ElemTypee){LNode*s,*p;intj;

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

;

s->next=p->next;

p->next=s;

s=(LinkList)malloc(sizeof(LNode));s->data=e;ListDelete(&L,i,&e)

：刪除第i個(gè)元素，用e返回。若i非法，返回ERROR；否則返回OK算法思路考慮：在單鏈表中刪除b，已知p指向apabcqq=p->next;p->next=q->next;free(q);e=q->data;單鏈表基本操作ListDelete(&L,i,&e)

：刪除第i個(gè)元素，用e返回。若i非法，返回ERROR；否則返回OK單鏈表基本操作a1

…ai

an^…L

ai-1

ai+1

p①q②③StatusListDelete_L

(LinkList&L,inti,ElemType&e){LNode*q,*p;intj;

}p=L;j=0;while(p->next&&j<i-1){p=p->next;j++;}if(p->next==NULL||j>i-1)returnERROR;q=p->next;returnOK

;

p->next=q->next;

e=q->data;

free(q);ClearList(&L)

：將單鏈表重置為一個(gè)空表算法思路單鏈表基本操作voidClearList_L

(LinkList&L){LNode*p;

}while(L->next){}p=L->next;

L->next=p->next;

free(p);L->next=p->next;p=L->next;free(p);p①③②a1

ai

an^…L

a2

ai+1

…CreatList(&L,n)

：創(chuàng)建有n個(gè)元素的單鏈表算法思路頭插法（帶頭結(jié)點(diǎn)）a1

…an-1

an^p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);pp->next=L->next;L->next=p;voidCreateList_L

(LinkList&L,intn)//逆序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L{LNode*p;inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;for(i=n;i>0;i--){

p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);

p->next=L->next;

L->next=p;}}生成頭結(jié)點(diǎn)循環(huán)插入單鏈表基本操作CreatList(&L,n)

：創(chuàng)建有n個(gè)元素的單鏈表算法思路尾插法（帶頭結(jié)點(diǎn)）p=(LinkList)malloc(sizeof(LNode));p->next=NULL;scanf("%d",&p->data);rear->next=p;rear=p;rearreara2^pan^

…voidCreateList_L_B

(LinkList&L,intn)//順序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L{LNode*p,*rear;inti;

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;

rear=L;for(i=n;i>0;i--){

p=(LinkList)malloc(sizeof(LNode));scanf("%d",&p->data);p->next=NULL;

rear->next=p;rear=p;}}生成頭結(jié)點(diǎn)循環(huán)插入單鏈表基本操作它是一種動(dòng)態(tài)結(jié)構(gòu)，整個(gè)存儲空間為多個(gè)鏈表共用不需預(yù)先分配空間插入、刪除不需移動(dòng)元素指針占用額外存儲空間單鏈表的表長是一個(gè)隱含的值在鏈表中，元素的“位序”概念淡化，結(jié)點(diǎn)的“位置”概念加強(qiáng)不能隨機(jī)存取，查找速度慢在單鏈表的最后一個(gè)元素之后插入元素時(shí)需遍歷整個(gè)鏈表單鏈表特點(diǎn)靜態(tài)鏈表(StaticLinkList)用一維數(shù)組來實(shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)ZHAOQIANSUNWANGWUZHENGZHOUdatacur01234567891011123456780LI在元素LI后插入元素SHISHI95刪除元素ZHENG8#defineMAXSIZE100typedefstruct{

ElemTypedata;intcur;}SLinkList[MAXSIZE];游標(biāo)cursor預(yù)先分配較大空間插入、刪除不需移動(dòng)元素，僅修改指針循環(huán)鏈表(CircularLinkedList)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀L空表特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next==NULL循環(huán)鏈表p或p->next==La1a2a3an……L雙向鏈表（DoubleLinkedList）單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義typedefstructDuLNode{ElemTypedata;structDuLNode*prior,*next;}DuLnode,*DuLinkList;priordatanextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcap雙向循環(huán)鏈表刪除p->prior->next=p->next;p->next->prior=p->prior;free(p);雙向循環(huán)鏈表刪除……L

a1

ai-1

ai

ai+1

an

時(shí)間復(fù)雜度：O(n)StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e)//刪除帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中的第i個(gè)元素{DuLNode*p;if(!(p=GetElemP_DuL(L,i)))returnERROR;//i值非法

p->prior->next=p->next;

p->next->prior=p->prior;

e=p->data;free(p);returnOK;}p①eSbap雙向循環(huán)鏈表插入s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

s=(DuLinkList)malloc(sizeof(DulNode));

s->data=e;StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee)//在帶頭結(jié)點(diǎn)的單鏈表L的第i個(gè)元素之前插入新元素e{DuLNode*p,*s;if(!(p=GetElemP_DuL(L,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;}雙向循環(huán)鏈表插入p……L

a1

ai-1

ai

ai+1

an

s

e

時(shí)間復(fù)雜度：O(n)s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;eSbap思考：

s->next=p;

p->prior->next=s;s->prior=p->prior;

p->prior=s;

p->prior=s;s->prior=p->prior;

p->prior->next=s;

s->next=p;s->prior=p;

p->next=s;

s->next=p->next;

p->next->prior=s;思考：eSabps->prior=p;

s->next=p->next;

p->next->prior=s;

p->next=s;線性表的應(yīng)用舉例一元多項(xiàng)式的表示及相加一元多項(xiàng)式的表示：可用線性表P表示順序存儲p0p1...p2pn...pi……Head

單鏈表方式存儲p0

p1

pi

pn^但對S(x)這樣的多項(xiàng)式浪費(fèi)空間一般其中用數(shù)據(jù)域含兩個(gè)數(shù)據(jù)項(xiàng)的線性表表示

Head一元稀疏多項(xiàng)式單鏈表方式存儲p1

e1p2

e2…pi

ei…pm^em一元多項(xiàng)式的表示ADT

Polynomial{數(shù)據(jù)對象：D={ai|aiTermSet,i=1,2,…,m,m≥0,TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，aiD,i=2，…，n,且ai-1中的指數(shù)值＜ai中的指數(shù)值

}

基本操作：……}ADT

Polynomial一元多項(xiàng)式的抽象數(shù)據(jù)類型定義如下：基本操作：CreatPolyn(&P,m)

操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P初始條件：一元多項(xiàng)式P已存在操作結(jié)果：銷毀一元多項(xiàng)式P初始條件：一元多項(xiàng)式P已存在操作結(jié)果：打印輸出一元多項(xiàng)式PDestroyPolyn(&P)PrintPolyn(&P)AddPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在操作結(jié)果：多項(xiàng)式相加運(yùn)算,即:Pa=Pa＋Pb，并銷毀PbSubtractPolyn(&Pa,&Pb)

MultiplyPolyn(&Pa,&Pb)初始條件：一元多項(xiàng)式Pa和Pb已存在操作結(jié)果：多項(xiàng)式相減運(yùn)算,即:Pa=Pa－Pb，并銷毀Pb初始條件：一元多項(xiàng)式Pa和Pb已存在操作結(jié)果：多項(xiàng)式相乘運(yùn)算,即:Pa=Pa×Pb，并銷毀Pb一元多項(xiàng)式ADT的實(shí)現(xiàn)typedefstruct{floatcoef;intexp;}term,ElemType;coefexpnexttypedefLinkListpolynomial;voidCreatPolyn(polynomial&P,intm);

voidDestroyPolyn(polynomial

&P);voidPrintPolyn(polynomial

P

);voidAddPolyn(polynomial

&Pa,polynomial

&Pb);voidSubtractPolyn(polynomial

&Pa,polynomial

&Pb);voidMultiplyPolyn(polynomial

&Pa,polynomial

&Pb);intPolynLength(polynomial

P

);一元多項(xiàng)式相加A(x)=7+3x+9x8+

5x17-8x100B(x)=8x+22x7-9x8C(x)=A(x)+B(x)=7+11x+22x7+5x17-8x100+headA703198517-8^100headB81227-9^8coefexp設(shè)qa,qb分別指向A,B中某一結(jié)點(diǎn)，其初值是第一結(jié)點(diǎn)比較qa->exp與qb->expqa->exp<qb->exp:qa->exp>qb->exp:qa->exp==qb->exp:0：0：直到qa或qb為NULL若qb==NULL,結(jié)束若qa==NULL,將B中剩余部分連到A上即可運(yùn)算規(guī)則qa結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)qa后移,qb不動(dòng)qb結(jié)點(diǎn)是和多項(xiàng)式中的一項(xiàng)將qb插在qa之前,qb后移,qa不動(dòng)系數(shù)相加從A表中刪去qa,釋放qa,qb,qa,qb后移修改qa系數(shù)域,釋放qb,qa,qb后移算法描述voidAddPoly(polynomial&Pa,polynomial&Pb){Linkqa,qb,ha,hb;ElemTypesum;

ha=Pa;qa=Pa->next;hb=Pb;qb=Pb->next;while(qa&&qb){if(qa->data.exp<qb->data.exp){}elseif(qa->data.exp>qb->data.exp){