實(shí)驗(yàn)鏈表實(shí)驗(yàn)報(bào)告

一元多項(xiàng)式體現(xiàn)和相加試驗(yàn)匯報(bào)試驗(yàn)內(nèi)容和目的試驗(yàn)?zāi)康模赫莆諉捂湵淼慕?、合并和遍歷操作試驗(yàn)內(nèi)容：1.單鏈表的建立（創(chuàng)立一種一元多項(xiàng)式）2.單鏈表的遍歷（一元多項(xiàng)式的輸出、一元多項(xiàng)式的項(xiàng)數(shù)記錄）3.單鏈表的合并（一元多項(xiàng)式的加減運(yùn)算）試驗(yàn)原理基本原理：使用單鏈表儲(chǔ)存一元多項(xiàng)式的指數(shù)和系數(shù)信息。每個(gè)結(jié)點(diǎn)具有兩個(gè)數(shù)據(jù)域，分別用于寄存每一項(xiàng)的指數(shù)和系數(shù)；一種指針域用于寄存下一種結(jié)點(diǎn)的指針。一種完整的鏈表表達(dá)一種一元多項(xiàng)式。文檔來(lái)自于網(wǎng)絡(luò)搜索單鏈表的建立：為了后續(xù)操作的以便，本試驗(yàn)中創(chuàng)立的單鏈表是按指數(shù)倒序排序的。例：創(chuàng)立一元多項(xiàng)式：18為了更好闡明建立的過(guò)程，輸入的過(guò)程并非按照指數(shù)降序的次序輸入。實(shí)際的輸入如下：環(huán)節(jié)一：把最先輸入的數(shù)據(jù)作為鏈表的第一種結(jié)點(diǎn)環(huán)節(jié)二：用第二個(gè)數(shù)據(jù)創(chuàng)立一種新的結(jié)點(diǎn)，假如新結(jié)點(diǎn)指數(shù)不小于某個(gè)結(jié)點(diǎn)，則新的結(jié)點(diǎn)插在該結(jié)點(diǎn)的前面；否則跟背面一種再比較（源碼中p和q指針向鏈表后移動(dòng)）；假如新的結(jié)點(diǎn)比前面的每一種結(jié)點(diǎn)都要?。磓指向鏈表最終一種結(jié)點(diǎn)），則插在鏈表的末尾端。文檔來(lái)自于網(wǎng)絡(luò)搜索下圖為新結(jié)點(diǎn)中指數(shù)比前面每個(gè)結(jié)點(diǎn)的指數(shù)都要小假如發(fā)現(xiàn)新結(jié)點(diǎn)的指數(shù)不小于鏈表中某個(gè)特定結(jié)點(diǎn)時(shí)（圖中紅色數(shù)字表達(dá)操作次序）不停反復(fù)上述環(huán)節(jié)，直到所有的數(shù)據(jù)都儲(chǔ)存到單鏈表中。單鏈表的合并（即本例中的一元多項(xiàng)式的加減法）：根據(jù)上述的鏈表創(chuàng)立算法，創(chuàng)立好的鏈表都具有按指數(shù)大小降序的特點(diǎn)。為了保證合并后來(lái)的單鏈表也具有此特點(diǎn)，因此合并的過(guò)程中，同樣會(huì)邊合并，邊比較大小，從而保證合并的成果仍然具有此特性。文檔來(lái)自于網(wǎng)絡(luò)搜索例：多項(xiàng)式P1為：18多項(xiàng)式P2為：12 多項(xiàng)式運(yùn)算P1+P2的成果為：18 從上述的鏈表創(chuàng)立算法可以創(chuàng)立出兩個(gè)對(duì)應(yīng)的鏈表先運(yùn)用兩個(gè)指針，Pa和Pb，分別指向兩個(gè)多項(xiàng)式的結(jié)點(diǎn)。假如Pa指向結(jié)點(diǎn)指數(shù)不小于Pb指向結(jié)點(diǎn)的指數(shù)，把Pa指向的結(jié)點(diǎn)插入到新的鏈表之中。詳細(xì)環(huán)節(jié)如圖假如Pa指向結(jié)點(diǎn)指數(shù)不不小于Pb指向結(jié)點(diǎn)的指數(shù)，則把Pb指向的結(jié)點(diǎn)插入到新的鏈表之中。詳細(xì)環(huán)節(jié)如圖假如Pa指向的結(jié)點(diǎn)指數(shù)等于Pb指向的結(jié)點(diǎn)指數(shù)，則先把兩者指向結(jié)點(diǎn)指數(shù)相加，儲(chǔ)存到Pa指向結(jié)點(diǎn)中。移動(dòng)Pa，Pb指針，釋放本來(lái)Pb指向的結(jié)點(diǎn)。詳細(xì)環(huán)節(jié)如圖文檔來(lái)自于網(wǎng)絡(luò)搜索一直反復(fù)上述操作，當(dāng)其中一種鏈表結(jié)點(diǎn)已經(jīng)所有插入到新的鏈表中時(shí)，則把此外一種鏈表剩余的所有結(jié)點(diǎn)插入到鏈表之中（即只需要把剩余的結(jié)點(diǎn)接起來(lái)）。詳細(xì)環(huán)節(jié)如圖文檔來(lái)自于網(wǎng)絡(luò)搜索 當(dāng)完畢上述的操作，把Pa指針指向新鏈表的指向新的鏈表頭。把舊的兩個(gè)鏈表頭釋放掉。一元多項(xiàng)式的減法，實(shí)際上也是一元多項(xiàng)式的加法。程序?qū)τ谝辉囗?xiàng)式的減法處理如下，A和B是兩個(gè)多項(xiàng)式，A-B=A+(-B)，也就是說(shuō)，把作為減數(shù)的多項(xiàng)式中每一項(xiàng)的系數(shù)變成其相反數(shù)，然后將兩個(gè)多項(xiàng)式進(jìn)行加法運(yùn)算。文檔來(lái)自于網(wǎng)絡(luò)搜索程序流程圖試驗(yàn)成果4.1程序主菜單4.2創(chuàng)立多項(xiàng)式4.3一元多項(xiàng)式的加法操作4.4一元多項(xiàng)式的減法操作4.5求一元多項(xiàng)式系數(shù)操作操作闡明1.主菜單中的1（創(chuàng)立一元多項(xiàng)式）2（輸出一元多項(xiàng)式）5（求一元多項(xiàng)式操作）三個(gè)選項(xiàng)操作的對(duì)象是同一種一元多項(xiàng)式，因此，要使用輸出和求項(xiàng)數(shù)功能之前，需要選擇1（創(chuàng)立一元多項(xiàng)式）創(chuàng)立多項(xiàng)式。文檔來(lái)自于網(wǎng)絡(luò)搜索2.多項(xiàng)式的加減操作的操作對(duì)象是兩個(gè)新的多項(xiàng)式，操作結(jié)束后來(lái)，進(jìn)行加減運(yùn)算的多項(xiàng)式和成果多項(xiàng)式均不會(huì)保留。文檔來(lái)自于網(wǎng)絡(luò)搜索3.在多項(xiàng)式的加減運(yùn)算過(guò)程中，只要其中一種多項(xiàng)式的創(chuàng)立出現(xiàn)問(wèn)題，整個(gè)加減法運(yùn)算操作就會(huì)終止。附錄：代碼#include<stdio.h>#include<stdlib.h>#defineOK0#defineERROR1typedefstructLNode{ intexp; //指數(shù) floatcoef; //系數(shù) structLNode*next; //指針域}LNode;/*基本操作的實(shí)現(xiàn)*///向鏈表中插入一種新的結(jié)點(diǎn)（插入過(guò)程中保持指數(shù)降序排序）//hNode 頭結(jié)點(diǎn)//nNode 要插入的新結(jié)點(diǎn)intInsertLNode(LNode*hNode,LNode*nNode){ LNode*p,*q; //假如鏈表為空表，則把元素放在鏈表第一種位置 if(hNode->next==NULL) { hNode->next=nNode; } else { p=hNode; q=hNode->next; while(q!=NULL) { //假如新的結(jié)點(diǎn)指數(shù)比q結(jié)點(diǎn)的指數(shù)大，則該結(jié)點(diǎn)插在q結(jié)點(diǎn)的前面 if(nNode->exp>q->exp) { nNode->next=q; p->next=nNode; break; } //假如新的結(jié)點(diǎn)指數(shù)與q的指數(shù)相等，指數(shù)相加，不插入結(jié)點(diǎn) if(nNode->exp==q->exp) { q->coef=nNode->coef+q->coef; free(nNode); break; } //假如新的結(jié)點(diǎn)指數(shù)比q的指數(shù)小 //假如q是最終一種結(jié)點(diǎn)，直接插入在q的背面 //假如q不是最終一種結(jié)點(diǎn)，則q指針往后移動(dòng) if(q->next==NULL) { nNode->next=q->next; q->next=nNode; break; } else { p=p->next; q=q->next; } } } returnOK;}//兩個(gè)多項(xiàng)式的相加操作//由于相加過(guò)程中，會(huì)根據(jù)指數(shù)的大小，一邊運(yùn)算一般排序//因此，規(guī)定傳入的Pa和Pb都是按指數(shù)降序排序的一元多項(xiàng)式voidAddPolyn(LNode*Pa,LNode*Pb){ LNode*head,*q,*tmp; //用于儲(chǔ)存新創(chuàng)立的多項(xiàng)式 LNode*recycle; //用于指數(shù)相等系數(shù)相加后結(jié)點(diǎn)的釋放 LNode*PtrB; //用于合并完畢后鏈表頭結(jié)點(diǎn)的釋放 head=(LNode*)malloc(sizeof(LNode*)); head->next=NULL; q=head; PtrB=Pb; Pa=Pa->next; Pb=Pb->next; //假如Pa和Pb指針不一樣步為空 while(Pa&&Pb) { //假如Pa所指向結(jié)點(diǎn)的指數(shù)不小于Pb所指向結(jié)點(diǎn)的指數(shù) if(Pa->exp>Pb->exp) { //把Pa指向的結(jié)點(diǎn)插入到新的鏈表之中 tmp=Pa; Pa=Pa->next; tmp->next=NULL; q->next=tmp; q=q->next; continue; } //假如Pa所指向結(jié)點(diǎn)的指數(shù)等于Pb所指向結(jié)點(diǎn)的指數(shù) if(Pa->exp==Pb->exp) { //先把Pa指向結(jié)點(diǎn)和Pb指向結(jié)點(diǎn)的系數(shù)相加，并儲(chǔ)存到Pa指向的結(jié)點(diǎn) //再把Pa指向的結(jié)點(diǎn)插入到新的鏈表之中 tmp=Pa; tmp->coef=tmp->coef+Pb->coef; recycle=Pb; Pa=Pa->next; Pb=Pb->next; free(recycle); tmp->next=NULL; q->next=tmp; q=q->next; continue; } //假如Pa所指向結(jié)點(diǎn)的指數(shù)不不小于Pb所指向結(jié)點(diǎn)的指數(shù) if(Pa->exp<Pb->exp) { //把Pb指向的結(jié)點(diǎn)插入到新的鏈表 tmp=Pb; Pb=Pb->next; tmp->next=NULL; q->next=tmp; q=q->next; continue; } } //假如其中一種鏈表已經(jīng)遍歷完畢，把鏈表剩余的所有結(jié)點(diǎn)插入到新的鏈表之中 if(Pa) { q->next=Pa; } if(Pb) { q->next=Pb; } PtrB->next=NULL; //釋放舊的鏈表頭結(jié)點(diǎn) free(PtrB); //把新的鏈表頭結(jié)點(diǎn)賦到Pa Pa=head;}//對(duì)兩個(gè)一元多項(xiàng)式進(jìn)行相減操作//A-B=A+(-B)voidSubtractPolyn(LNode*Pa,LNode*Pb){ LNode*p; //把Lb中每項(xiàng)的系數(shù)變成其相反數(shù) for(p=Pb->next;p!=NULL;p=p->next) p->coef=-(p->coef); AddPolyn(Pa,Pb);}/*詳細(xì)功能的實(shí)現(xiàn)*/intCreatePolynomial(LNode*hNode){ inti,n,exp; floatcoef; LNode*node; printf("請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)："); //假如輸入的不是整數(shù) if(scanf("%d",&n)==0) { printf("無(wú)效輸入...\n"); returnERROR; } //清空上述操作中未讀入的數(shù)值。防止對(duì)背面的操作產(chǎn)生影響 fflush(stdin); printf("即將創(chuàng)立一種項(xiàng)數(shù)為%d的多項(xiàng)式\n",n); printf("輸入的格式為：先系數(shù)后指數(shù)，兩者之間使用英文逗號(hào)間隔\n"); for(i=1;i<=n;i++) { printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)和指數(shù)：",i); //防止不對(duì)的輸入導(dǎo)致的死循環(huán) fflush(stdin); //操作前檢查輸入的有效性 //假如輸入的數(shù)據(jù)無(wú)效則規(guī)定重新輸入 if(scanf("%f,%d",&coef,&exp)==2) { node=(LNode*)malloc(sizeof(LNode)); if(!node) { printf("內(nèi)存分派失??！\n"); system("pause"); returnERROR; } //向新結(jié)點(diǎn)賦值 node->exp=exp; node->coef=coef; node->next=NULL; //把新結(jié)點(diǎn)插入到鏈表之中 InsertLNode(hNode,node); } else { printf("輸入無(wú)效，請(qǐng)重新輸入。\n"); i--; } } if(i==n+1) returnOK; else returnERROR;}voidPrintPolynomial(LNode*head){ LNode*p=head->next; inti=0; //用于控制加號(hào)輸出 while(p!=NULL) { //假如系數(shù)不為0，輸出該項(xiàng) if(p->coef!=0) { //根據(jù)參數(shù)的正負(fù)輸出加減號(hào) if(i++!=0&&p->coef>0) putchar('+'); printf("%.2fx^%d",p->coef,p->exp); //防止系數(shù)為0的前一項(xiàng)的指數(shù)被覆蓋 if(p->next&&p->next->coef==0) printf(""); } else printf("\b"); //覆蓋前面的加號(hào) p=p->next; } printf("\n");}//遍歷并輸出整數(shù)序列voidListTravel(LNode*head){ intn=0; LNode*p; //先對(duì)多項(xiàng)式的項(xiàng)數(shù)進(jìn)行記錄 for(p=head->next;p!=NULL;p=p->next) n++; //輸出項(xiàng)數(shù) printf("%d,",n); //通過(guò)鏈表的遍歷實(shí)現(xiàn)整數(shù)序列中的指數(shù)和系數(shù)部分 for(p=head->next;p!=NULL;p=p->next) printf("%.2f,%d,",p->coef,p->exp);}voidListCount(LNode*head){ LNode*p; inti=0; //每發(fā)現(xiàn)一種非空結(jié)點(diǎn)，i加一 for(p=head->next;p!=NULL;p=p->next) i++; printf("\n該一元多項(xiàng)式有%d項(xiàng)\n\n",i); system("pause");}//創(chuàng)立兩個(gè)一元多項(xiàng)式并相加voidCreateAndPlus(){ LNode*La,*Lb; //為兩個(gè)新的鏈表分派內(nèi)存空間 La=(LNode*)malloc(sizeof(LNode)); Lb=(LNode*)malloc(sizeof(LNode)); La->next=NULL; Lb->next=NULL; //清屏 system("cls"); printf("\n目前創(chuàng)立第一種一元多項(xiàng)式\n\n"); if(CreatePolynomial(La)==ERROR) { printf("創(chuàng)立多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單...\n"); system("pause"); return; } PrintPolynomial(La); printf("\n目前創(chuàng)立第二個(gè)一元多項(xiàng)式\n\n"); if(CreatePolynomial(Lb)==ERROR) { printf("創(chuàng)立多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單...\n"); system("pause"); return; } PrintPolynomial(Lb); printf("\n求和成果：\n"); AddPolyn(La,Lb); PrintPolynomial(La); system("pause");}voidCreateAndSubtract(){ LNode*La,*Lb; //為兩個(gè)新的鏈表分派內(nèi)存空間 La=(LNode*)malloc(sizeof(LNode)); Lb=(LNode*)malloc(sizeof(LNode)); La->next=NULL; Lb->next=NULL; //清屏 system("cls"); printf("\n目前創(chuàng)立第一種一元多項(xiàng)式\n\n"); if(CreatePolynomial(La)==ERROR) { printf("創(chuàng)立多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單...\n"); system("pause"); return; } PrintPolynomial(La); printf("\n目前創(chuàng)立第二個(gè)一元多項(xiàng)式\n\n"); if(CreatePolynomial(Lb)==ERROR) { printf("創(chuàng)立多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單...\n"); system("pause"); return; } PrintPolynomial(Lb); printf("\n兩個(gè)多項(xiàng)式相減后來(lái)的成果：\n"); SubtractPolyn(La,Lb); PrintPolynomial(La); system("pause");}intmain(void){ LNode*head=(LNode*)malloc(sizeof(LNode)); charch='\0'; if(!head) { printf("鏈表頭指針內(nèi)存分派失敗！\n"); system("pause"); returnERROR; } head->next=NULL; while(1) { //處理閃屏或者不能接受顧客輸入的問(wèn)題 fflush(stdin); system("cls"); printf("\n\n"); printf("單鏈表的應(yīng)用演示程序\n"); printf("一元多項(xiàng)式的表達(dá)及相加\n"); printf("\n"); printf("1.創(chuàng)立一種一元多項(xiàng)式并輸出\n"); printf("2.遍歷單鏈表并輸出整數(shù)序列\(zhòng)n"); printf("3.創(chuàng)立兩個(gè)一元多項(xiàng)式并相加\n"); printf("4.創(chuàng)立兩個(gè)一元多項(xiàng)式并相減\n"); printf("5.求一種一元多項(xiàng)式中的項(xiàng)數(shù)\n"); printf("\n"); printf("Q.退出程序\n"); printf("\n\n"); printf("請(qǐng)選擇："); scanf("%c",&ch); switch(ch) { case'1': system("cls"); //假如鏈表已經(jīng)創(chuàng)立，則需要重新分派空間 //并釋放原有的空間 if(head->next!=NULL)