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

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

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

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

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

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

6、#include <stdio.h>#include <stdlib.h>#define OK 0#define ERROR 1typedef struct LNodeint exp;/ 指數float coef;/ 系數struct LNode *next;/ 指針域 LNode;/* 基本操作的實現*/ 向鏈表中插入一個新的結點（插入過程中保持指數降序排序）/ hNode頭結點/ nNode要插入的新結點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)/ 如果新的結點指數比q 結點的指數大，則該結點插在q 結點的前面if (nNode->exp > q->exp)nNode->next = q;p->next = nNode;break;/ 如果新的結點指數與q 的指數相等，指數相加，不插入結點if (nNode->exp = q->exp)q->coef = nNode->coef + q->

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

9、*Pa, LNode *Pb)LNode *head, *q, *tmp;/ 用于儲存新創(chuàng)建的多項式LNode *recycle;/ 用于指數相等系數相加后結點的釋放LNode *PtrB;/ 用于合并完成后鏈表頭結點的釋放head = (LNode *)malloc(sizeof(LNode *);head->next = NULL;q = head;PtrB = Pb;Pa = Pa->next;Pb = Pb->next;/ 如果Pa 和Pb 指針不同時為空while (Pa && Pb)/ 如果Pa 所指向結點的指數大于Pb 所指向結點的指數if (P

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

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

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

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

15、quot;內存分配失?。");system("pause");return ERROR;/ 向新結點賦值node->exp = exp;node->coef = coef;node->next = NULL;/ 把新結點插入到鏈表之中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)/ 如果系數不為0，輸出該項if (p->coef != 0)/ 根據參數的正負輸出加減號if (i+ != 0 && p->coef > 0)putchar('+');printf("%.2fx%d", p->coef, p->exp);/ 防止系數為0 的前一項的指數被覆蓋if (p->next && p->next->coef = 0)printf(" ");elsep

17、rintf("b");/ 覆蓋前面的加號p = p->next;printf("n");/ 遍歷并輸出整數序列void ListTravel(LNode *head)int n = 0;LNode *p;/ 先對多項式的項數進行統(tǒng)計for ( p = head->next; p != NULL; p = p->next )n+;/ 輸出項數printf("%d, ", n);/ 通過鏈表的遍歷實現整數序列中的指數和系數部分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ā)現一個非空結點，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;/ 為兩個新的鏈表分配內

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

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

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

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

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