實驗二-鏈表-實驗報告(共17頁)

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

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

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

4、到新的鏈表之中。具體步驟如圖如果Pa指向的結(jié)點指數(shù)等于Pb指向的結(jié)點指數(shù)，則先把兩者指向結(jié)點指數(shù)相加，儲存到Pa指向結(jié)點中。移動Pa，Pb指針，釋放原來Pb指向的結(jié)點。具體步驟如圖一直重復(fù)上述操作，當(dāng)其中一個鏈表結(jié)點已經(jīng)全部插入到新的鏈表中時，則把另外一個鏈表剩下的所有結(jié)點插入到鏈表之中（即只需要把剩下的結(jié)點接起來）。具體步驟如圖當(dāng)完成上述的操作，把Pa指針指向新鏈表的指向新的鏈表頭。把舊的兩個鏈表頭釋放掉。 一元多項式的減法，實際上也是一元多項式的加法。程序?qū)τ谝辉囗検降臏p法處理如下，A和B是兩個多項式，A-B = A+(-B)，也就是說，把作為減數(shù)的多項式中每一項的系數(shù)變成其相反數(shù)，然后

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

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

7、(hNode->next = NULL)hNode->next = nNode;elsep = hNode;q = hNode->next;while (q != NULL)/ 如果新的結(jié)點指數(shù)比q 結(jié)點的指數(shù)大，則該結(jié)點插在q 結(jié)點的前面if (nNode->exp > q->exp)nNode->next = q;p->next = nNode;break;/ 如果新的結(jié)點指數(shù)與q 的指數(shù)相等，指數(shù)相加，不插入結(jié)點if (nNode->exp = q->exp)q->coef = nNode->coef + q->

8、;coef;free(nNode);break;/ 如果新的結(jié)點指數(shù)比q 的指數(shù)小/ 如果q 是最后一個結(jié)點，直接插入在q 的后面/ 如果q 不是最后一個結(jié)點，則q 指針往后移動if (q->next = NULL)nNode->next = q->next;q->next = nNode;break;else p = p->next;q = q->next;return OK;/ 兩個多項式的相加操作/ 因為相加過程中，會根據(jù)指數(shù)的大小，一邊運算一般排序/ 因此，要求傳入的Pa 和Pb 都是按指數(shù)降序排序的一元多項式void AddPolyn(LNode

9、*Pa, LNode *Pb)LNode *head, *q, *tmp;/ 用于儲存新創(chuàng)建的多項式LNode *recycle;/ 用于指數(shù)相等系數(shù)相加后結(jié)點的釋放LNode *PtrB;/ 用于合并完成后鏈表頭結(jié)點的釋放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é)點的指數(shù)大于Pb 所指向結(jié)點的指數(shù)if (P

10、a->exp > Pb->exp)/ 把Pa 指向的結(jié)點插入到新的鏈表之中tmp = Pa;Pa = Pa->next;tmp->next = NULL;q->next = tmp;q = q->next;continue;/ 如果Pa 所指向結(jié)點的指數(shù)等于Pb 所指向結(jié)點的指數(shù)if (Pa->exp = Pb->exp)/ 先把Pa 指向結(jié)點和Pb 指向結(jié)點的系數(shù)相加，并儲存到Pa 指向的結(jié)點/ 再把Pa 指向的結(jié)點插入到新的鏈表之中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é)點的指數(shù)小于Pb 所指向結(jié)點的指數(shù)if (Pa->exp < Pb->exp)/ 把Pb 指向的結(jié)點插入到新的鏈表tmp = Pb;Pb = Pb->next;tmp->next = NULL;q->next = tmp;q = q->next;continue;/ 如果其中一個鏈表已經(jīng)遍歷完畢

12、，把鏈表剩下的所有結(jié)點插入到新的鏈表之中if (Pa)q->next = Pa;if (Pb)q->next = Pb;PtrB->next = NULL;/ 釋放舊的鏈表頭結(jié)點free(PtrB);/ 把新的鏈表頭結(jié)點賦到Pa Pa = head;/ 對兩個一元多項式進(jìn)行相減操作/ A - B = A + (-B)void SubtractPolyn(LNode *Pa, LNode *Pb)LNode *p;/ 把Lb 中每項的系數(shù)變成其相反數(shù)for (p = Pb->next; p != NULL; p = p->next)p->coef = -(p-

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

14、多項式n", n);printf("輸入的格式為：先系數(shù)后指數(shù)，兩者之間使用英文逗號間隔n");for ( i = 1; i <= n; i+ )printf("請輸入第%d 項的系數(shù)和指數(shù)：", i);/ 防止不正確輸入導(dǎo)致的死循環(huán)fflush(stdin);/ 操作前檢查輸入的有效性/ 如果輸入的數(shù)據(jù)無效則要求重新輸入if ( scanf("%f,%d", &coef, &exp) = 2)node = (LNode *)malloc(sizeof(LNode);if (!node)printf(&

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

16、;next;int i = 0;/ 用于控制加號輸出while (p != NULL)/ 如果系數(shù)不為0，輸出該項if (p->coef != 0)/ 根據(jù)參數(shù)的正負(fù)輸出加減號if (i+ != 0 && p->coef > 0)putchar('+');printf("%.2fx%d", p->coef, p->exp);/ 防止系數(shù)為0 的前一項的指數(shù)被覆蓋if (p->next && p->next->coef = 0)printf(" ");elsep

17、rintf("b");/ 覆蓋前面的加號p = p->next;printf("n");/ 遍歷并輸出整數(shù)序列void ListTravel(LNode *head)int n = 0;LNode *p;/ 先對多項式的項數(shù)進(jìn)行統(tǒng)計for ( p = head->next; p != NULL; p = p->next )n+;/ 輸出項數(shù)printf("%d, ", n);/ 通過鏈表的遍歷實現(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)一個非空結(jié)點，i 加一for (p = head->next; p != NULL; p = p->next) i+;printf("n 該一元多項式有%d 項nn", i);system("pause");/ 創(chuàng)建兩個一元多項式并相加void CreateAndPlus()LNode *La, *Lb;/ 為兩個新的鏈表分配內(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)建第一個一元多項式nn");if (CreatePolynomial(La) = ERROR)printf("創(chuàng)建多項式時出現(xiàn)錯誤，即將返回主菜單.n");system("pause");return;PrintPolynomial(La

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

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)建第一個一元多項式nn");if (CreatePolynomial(La) = ERROR)printf("創(chuàng)建多項式時出現(xiàn)錯誤，即將返回主菜單.n");system("pause");return;PrintPolyno

22、mial(La);printf("n現(xiàn)在創(chuàng)建第二個一元多項式nn");if (CreatePolynomial(Lb) = ERROR)printf("創(chuàng)建多項式時出現(xiàn)錯誤，即將返回主菜單.n");system("pause");return;PrintPolynomial(Lb);printf("n兩個多項式相減以后的結(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)存分配失?。");system("pause");return ERROR;head->next = NULL;while (1)/ 解決閃屏或者不能接受用戶輸入的問題fflush(stdin);system("cls");printf("nn");printf(" 單鏈表的應(yīng)用演示程序n");printf(" 一元多項式

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