實(shí)驗(yàn)二-鏈表-實(shí)驗(yàn)報(bào)告(共17頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一元多項(xiàng)式表達(dá)和相加 實(shí)驗(yàn)報(bào)告 一、 實(shí)驗(yàn)內(nèi)容和目的實(shí)驗(yàn)?zāi)康模赫莆諉捂湵淼慕?、合并和遍歷操作實(shí)驗(yàn)內(nèi)容：1. 單鏈表的建立（創(chuàng)建一個(gè)一元多項(xiàng)式） 2. 單鏈表的遍歷（一元多項(xiàng)式的輸出、一元多項(xiàng)式的項(xiàng)數(shù)統(tǒng)計(jì)） 3. 單鏈表的合并（一元多項(xiàng)式的加減運(yùn)算）二、 實(shí)驗(yàn)原理基本原理：使用單鏈表儲(chǔ)存一元多項(xiàng)式的指數(shù)和系數(shù)信息。每個(gè)結(jié)點(diǎn)含有兩個(gè)數(shù)據(jù)域，分別用于存放每一項(xiàng)的指數(shù)和系數(shù)；一個(gè)指針域用于存放下一個(gè)結(jié)點(diǎn)的指針。一個(gè)完整的鏈表表示一個(gè)一元多項(xiàng)式。單鏈表的建立： 為了后續(xù)操作的方便，本實(shí)驗(yàn)中創(chuàng)建的單鏈表是按指數(shù)倒序排序的。 例：創(chuàng)建一元多項(xiàng)式：18x12+17x9+9x6+5x

2、3+6x2+19x 為了更好說(shuō)明建立的過(guò)程，輸入的過(guò)程并非按照指數(shù)降序的順序輸入。實(shí)際的輸入如下：步驟一：把最先輸入的數(shù)據(jù)作為鏈表的第一個(gè)結(jié)點(diǎn)步驟二：用第二個(gè)數(shù)據(jù)創(chuàng)建一個(gè)新的結(jié)點(diǎn)，如果新結(jié)點(diǎn)指數(shù)大于某個(gè)結(jié)點(diǎn)，則新的結(jié)點(diǎn)插在該結(jié)點(diǎn)的前面；否則跟后面一個(gè)再比較（源碼中p和q指針向鏈表后移動(dòng)）；如果新的結(jié)點(diǎn)比前面的每一個(gè)結(jié)點(diǎn)都要?。磓指向鏈表最后一個(gè)結(jié)點(diǎn)），則插在鏈表的末尾端。下圖為新結(jié)點(diǎn)中指數(shù)比前面每個(gè)結(jié)點(diǎn)的指數(shù)都要小如果發(fā)現(xiàn)新結(jié)點(diǎn)的指數(shù)大于鏈表中某個(gè)特定結(jié)點(diǎn)時(shí)（圖中紅色數(shù)字表示操作順序） 不斷重復(fù)上述步驟，直到所有的數(shù)據(jù)都儲(chǔ)存到單鏈表中。單鏈表的合并（即本例中的一元多項(xiàng)式的加減法）：根據(jù)上述的

3、鏈表創(chuàng)建算法，創(chuàng)建好的鏈表都具有按指數(shù)大小降序的特點(diǎn)。為了確保合并以后的單鏈表也具有此特點(diǎn)，因此合并的過(guò)程中，同樣會(huì)邊合并，邊比較大小，從而確保合并的結(jié)果仍然具有此特性。例：多項(xiàng)式P1為：18x17+9x8+4x2+3x多項(xiàng)式P2為：12x12+7x8+4x3多項(xiàng)式運(yùn)算P1+P2的結(jié)果為：18x17+12x12+16x8+4x3+4x2+3x從上述的鏈表創(chuàng)建算法可以創(chuàng)建出兩個(gè)對(duì)應(yīng)的鏈表先利用兩個(gè)指針，Pa和Pb，分別指向兩個(gè)多項(xiàng)式的結(jié)點(diǎn)。如果Pa指向結(jié)點(diǎn)指數(shù)大于Pb指向結(jié)點(diǎn)的指數(shù)，把Pa指向的結(jié)點(diǎn)插入到新的鏈表之中。具體步驟如圖如果Pa指向結(jié)點(diǎn)指數(shù)小于Pb指向結(jié)點(diǎn)的指數(shù)，則把Pb指向的結(jié)點(diǎn)插入

4、到新的鏈表之中。具體步驟如圖如果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)。具體步驟如圖一直重復(fù)上述操作，當(dāng)其中一個(gè)鏈表結(jié)點(diǎn)已經(jīng)全部插入到新的鏈表中時(shí)，則把另外一個(gè)鏈表剩下的所有結(jié)點(diǎn)插入到鏈表之中（即只需要把剩下的結(jié)點(diǎn)接起來(lái)）。具體步驟如圖當(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ù)，然后

5、將兩個(gè)多項(xiàng)式進(jìn)行加法運(yùn)算。三、 程序流程圖四、 實(shí)驗(yàn)結(jié)果4.1 程序主菜單4.2 創(chuàng)建多項(xiàng)式4.3 一元多項(xiàng)式的加法操作4.4 一元多項(xiàng)式的減法操作4.5 求一元多項(xiàng)式系數(shù)操作五、 操作說(shuō)明1. 主菜單中的1（創(chuàng)建一元多項(xiàng)式）2（輸出一元多項(xiàng)式） 5（求一元多項(xiàng)式操作）三個(gè)選項(xiàng)操作的對(duì)象是同一個(gè)一元多項(xiàng)式，因此，要使用輸出和求項(xiàng)數(shù)功能之前，需要選擇1（創(chuàng)建一元多項(xiàng)式）創(chuàng)建多項(xiàng)式。2. 多項(xiàng)式的加減操作的操作對(duì)象是兩個(gè)新的多項(xiàng)式，操作結(jié)束以后，進(jìn)行加減運(yùn)算的多項(xiàng)式和結(jié)果多項(xiàng)式均不會(huì)保存。3. 在多項(xiàng)式的加減運(yùn)算過(guò)程中，只要其中一個(gè)多項(xiàng)式的創(chuàng)建出現(xiàn)問(wèn)題，整個(gè)加減法運(yùn)算操作就會(huì)終止。六、 附錄：代碼

6、#include <stdio.h>#include <stdlib.h>#define OK 0#define ERROR 1typedef struct LNodeint exp;/ 指數(shù)float coef;/ 系數(shù)struct LNode *next;/ 指針域 LNode;/* 基本操作的實(shí)現(xiàn)*/ 向鏈表中插入一個(gè)新的結(jié)點(diǎn)（插入過(guò)程中保持指數(shù)降序排序）/ hNode頭結(jié)點(diǎn)/ nNode要插入的新結(jié)點(diǎn)int InsertLNode(LNode *hNode, LNode *nNode)LNode *p, *q;/ 如果鏈表為空表，則把元素放在鏈表第一個(gè)位置if

7、(hNode->next = NULL)hNode->next = nNode;elsep = 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->

8、;coef;free(nNode);break;/ 如果新的結(jié)點(diǎn)指數(shù)比q 的指數(shù)小/ 如果q 是最后一個(gè)結(jié)點(diǎn)，直接插入在q 的后面/ 如果q 不是最后一個(gè)結(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;return OK;/ 兩個(gè)多項(xiàng)式的相加操作/ 因?yàn)橄嗉舆^(guò)程中，會(huì)根據(jù)指數(shù)的大小，一邊運(yùn)算一般排序/ 因此，要求傳入的Pa 和Pb 都是按指數(shù)降序排序的一元多項(xiàng)式void AddPolyn(LNode

9、*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 指針不同時(shí)為空while (Pa && Pb)/ 如果Pa 所指向結(jié)點(diǎn)的指數(shù)大于Pb 所指向結(jié)點(diǎn)的指數(shù)if (P

10、a->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;re

11、cycle = 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;/ 如果其中一個(gè)鏈表已經(jīng)遍歷完畢

12、，把鏈表剩下的所有結(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)void SubtractPolyn(LNode *Pa, LNode *Pb)LNode *p;/ 把Lb 中每項(xiàng)的系數(shù)變成其相反數(shù)for (p = Pb->next; p != NULL; p = p->next)p->coef = -(p-

13、>coef);AddPolyn(Pa, Pb);/* 具體功能的實(shí)現(xiàn)*/int CreatePolynomial(LNode *hNode)int i, n, exp;float coef;LNode *node;printf("請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：");/ 如果輸入的不是整數(shù)if ( scanf("%d", &n) = 0 )printf("無(wú)效輸入.n");return ERROR;/ 清空上述操作中未讀入的數(shù)值。防止對(duì)后面的操作產(chǎn)生影響fflush(stdin);printf("即將創(chuàng)建一個(gè)項(xiàng)數(shù)為%d 的

14、多項(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);/ 防止不正確輸入導(dǎo)致的死循環(huán)fflush(stdin);/ 操作前檢查輸入的有效性/ 如果輸入的數(shù)據(jù)無(wú)效則要求重新輸入if ( scanf("%f,%d", &coef, &exp) = 2)node = (LNode *)malloc(sizeof(LNode);if (!node)printf(&

15、quot;內(nèi)存分配失?。");system("pause");return ERROR;/ 向新結(jié)點(diǎn)賦值node->exp = exp;node->coef = coef;node->next = NULL;/ 把新結(jié)點(diǎn)插入到鏈表之中InsertLNode(hNode, node);elseprintf("輸入無(wú)效，請(qǐng)重新輸入。n");i-;if (i = n + 1)return OK;elsereturn ERROR;void PrintPolynomial(LNode *head)LNode *p = head->

16、;next;int i = 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(" ");elsep

17、rintf("b");/ 覆蓋前面的加號(hào)p = p->next;printf("n");/ 遍歷并輸出整數(shù)序列void ListTravel(LNode *head)int n = 0;LNode *p;/ 先對(duì)多項(xiàng)式的項(xiàng)數(shù)進(jìn)行統(tǒng)計(jì)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->ne

18、xt )printf("%.2f, %d, ", p->coef, p->exp);void ListCount(LNode *head)LNode *p;int i = 0;/ 每發(fā)現(xiàn)一個(gè)非空結(jié)點(diǎn)，i 加一for (p = head->next; p != NULL; p = p->next) i+;printf("n 該一元多項(xiàng)式有%d 項(xiàng)nn", i);system("pause");/ 創(chuàng)建兩個(gè)一元多項(xiàng)式并相加void CreateAndPlus()LNode *La, *Lb;/ 為兩個(gè)新的鏈表分配內(nèi)

19、存空間La = (LNode *)malloc(sizeof(LNode);Lb = (LNode *)malloc(sizeof(LNode);La->next = NULL;Lb->next = NULL;/ 清屏system("cls");printf("n現(xiàn)在創(chuàng)建第一個(gè)一元多項(xiàng)式nn");if (CreatePolynomial(La) = ERROR)printf("創(chuàng)建多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單.n");system("pause");return;PrintPolynomial(La

20、);printf("n現(xiàn)在創(chuàng)建第二個(gè)一元多項(xiàng)式nn");if (CreatePolynomial(Lb) = ERROR)printf("創(chuàng)建多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單.n");system("pause");return;PrintPolynomial(Lb);printf("n求和結(jié)果：n");AddPolyn(La, Lb);PrintPolynomial(La);system("pause");void CreateAndSubtract()LNode *La, *Lb;/ 為兩個(gè)

21、新的鏈表分配內(nèi)存空間La = (LNode *)malloc(sizeof(LNode);Lb = (LNode *)malloc(sizeof(LNode);La->next = NULL;Lb->next = NULL;/ 清屏system("cls");printf("n現(xiàn)在創(chuàng)建第一個(gè)一元多項(xiàng)式nn");if (CreatePolynomial(La) = ERROR)printf("創(chuàng)建多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單.n");system("pause");return;PrintPolyno

22、mial(La);printf("n現(xiàn)在創(chuàng)建第二個(gè)一元多項(xiàng)式nn");if (CreatePolynomial(Lb) = ERROR)printf("創(chuàng)建多項(xiàng)式時(shí)出現(xiàn)錯(cuò)誤，即將返回主菜單.n");system("pause");return;PrintPolynomial(Lb);printf("n兩個(gè)多項(xiàng)式相減以后的結(jié)果：n");SubtractPolyn(La, Lb);PrintPolynomial(La);system("pause");int main(void)LNode *hea

23、d = (LNode *)malloc(sizeof(LNode);char ch = '0'if (!head)printf("鏈表頭指針內(nèi)存分配失??！n");system("pause");return ERROR;head->next = NULL;while (1)/ 解決閃屏或者不能接受用戶輸入的問(wèn)題fflush(stdin);system("cls");printf("nn");printf(" 單鏈表的應(yīng)用演示程序n");printf(" 一元多項(xiàng)式

24、的表示及相加n");printf("n");printf(" 1. 創(chuàng)建一個(gè)一元多項(xiàng)式并輸出n");printf(" 2. 遍歷單鏈表并輸出整數(shù)序列n");printf(" 3. 創(chuàng)建兩個(gè)一元多項(xiàng)式并相加n");printf(" 4. 創(chuàng)建兩個(gè)一元多項(xiàng)式并相減n");printf(" 5. 求一個(gè)一元多項(xiàng)式中的項(xiàng)數(shù)n");printf("n");printf(" Q. 退出程序n");printf("nn");printf(" 請(qǐng)選擇：");scanf("%c", &ch);switch (ch)case '1':system("cls");/ 如果鏈表已經(jīng)創(chuàng)建，則需要重新分配空間/ 并釋放原有的空間if (h