一元多項(xiàng)式相加數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)一-1307班譚淇蔚.docx

中南大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告題 目 實(shí)驗(yàn)一 線性表的操作 學(xué)生姓名 譚淇蔚 學(xué)生學(xué)號(hào) 3901130721 專業(yè)班級(jí) 軟件工程1307班 完成日期 2014年3月31日星期一 實(shí)驗(yàn)一 線性表的操作（一元多項(xiàng)式相加）1. 需求分析 我們使用計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。而數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。所以我們做的是實(shí)驗(yàn)一-線性表的操作。實(shí)驗(yàn)的目的是掌握線性表的基本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算以及熟練運(yùn)用掌握的線性表的操作，實(shí)現(xiàn)一元n次多項(xiàng)式的加法運(yùn)算。學(xué)習(xí)實(shí)現(xiàn)一元n次多項(xiàng)式的加法是符號(hào)多項(xiàng)式的操作，是表處理的典型用例，需要注意的是：順序存儲(chǔ)結(jié)構(gòu)指的是用數(shù)組方法，使用數(shù)組方法實(shí)現(xiàn)時(shí)，在插入和刪除的方面，數(shù)組不如鏈表靈活，方法復(fù)雜，刪除其中一個(gè)需要將其后的數(shù)組元素改變位置，使其數(shù)組保持原有的順序結(jié)構(gòu)，在查找方面較鏈表簡(jiǎn)單，只需要知道其下標(biāo)就可以知道。鏈接存儲(chǔ)結(jié)構(gòu)指的是用鏈表方法,值得注意的是，刪除和插入較為靈活，不需要變動(dòng)大多數(shù)元素，但是查找過(guò)程相對(duì)于數(shù)組這種順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)較為復(fù)雜，耗時(shí)巨大。我們要學(xué)習(xí)的是通過(guò)對(duì)兩種方法基本操作的掌握來(lái)做到實(shí)現(xiàn)一元n次多項(xiàng)式的相加減。 我們程序的任務(wù)是：能進(jìn)行簡(jiǎn)單的線性表操作（插入、刪除、查找）以及線性表合并等運(yùn)算。能通過(guò)這些基本操作實(shí)現(xiàn)一元多項(xiàng)式相加。明確規(guī)定：輸入的形式：按照提示（比如：“請(qǐng)您輸入第一個(gè)結(jié)構(gòu)體數(shù)組的項(xiàng)數(shù)（不超過(guò)50項(xiàng)）：”、“請(qǐng)您輸入第二個(gè)結(jié)構(gòu)體數(shù)組的項(xiàng)數(shù)（不超過(guò)50項(xiàng)）：”、“請(qǐng)輸入第n項(xiàng)的系數(shù)”、“請(qǐng)輸入第n項(xiàng)的指數(shù)”等等），先輸入多項(xiàng)式的項(xiàng)數(shù)，之后順次輸入每一項(xiàng)的系數(shù)與指數(shù)。輸入值的范圍：項(xiàng)數(shù)沒(méi)有要求，但不能過(guò)于巨大；系數(shù)取為float型數(shù)據(jù)，指數(shù)取為int型數(shù)據(jù)，輸出的形式：按照提示（比如：“您輸入的第一個(gè)多項(xiàng)式為：”、“您輸入的第二個(gè)多項(xiàng)式為：”等等），會(huì)輸出原輸入的多項(xiàng)式和經(jīng)過(guò)排序和合并之后的降冪型多項(xiàng)式。同時(shí)，系數(shù)會(huì)以保留小數(shù)點(diǎn)后兩位數(shù)字的形式輸出；若指數(shù)輸入時(shí)為小數(shù)，則輸出時(shí)會(huì)自動(dòng)截取其整數(shù)部分。程序所能達(dá)到的功能：程序可以對(duì)輸入的序列紊亂的多項(xiàng)式進(jìn)行加工，使之按照降冪排列，之后對(duì)兩多項(xiàng)式進(jìn)行加法運(yùn)算（包括系數(shù)為負(fù)的加法），最后輸出最終的多項(xiàng)式。測(cè)試數(shù)正確數(shù)據(jù)：輸入：2*X3+2*X6+2*X7+2*X8+2*X10 和 - 3*X10+4*X8+2*X7+3*X5+3*X3輸出：7.00*X2+8.00*X1+2.00錯(cuò)誤數(shù)據(jù)：輸入：-8*X1.5+4*X2 和 3*X2+12*X1.6輸出：7.00*X2+4.00*X12概要設(shè)計(jì)（1）鏈接存儲(chǔ)結(jié)構(gòu)：struct node float coef; int expo; struct node *next;chainLink;函數(shù)主體部分，利用頭指針進(jìn)行鏈表操作，利用display進(jìn)行打印出屏幕，利用order函數(shù)對(duì)其進(jìn)行降冪排序，當(dāng)兩個(gè)多項(xiàng)式已經(jīng)創(chuàng)建完畢時(shí)，利用add函數(shù)進(jìn)行兩個(gè)多項(xiàng)式相加。（2）順序存儲(chǔ)結(jié)構(gòu)抽象數(shù)據(jù)類型為結(jié)構(gòu)體數(shù)組：struct polyfloat coef;int exp;函數(shù)主體部分，會(huì)引用指針進(jìn)行參數(shù)傳遞，在函數(shù)主體部分定義了3個(gè)結(jié)構(gòu)體數(shù)組同時(shí)定義其所對(duì)應(yīng)的指針，利用用戶輸入，利用print函數(shù)將其打印出來(lái)，再用sort函數(shù)將其降序排列，做完兩個(gè)結(jié)構(gòu)體數(shù)組后，接著利用add函數(shù)將兩個(gè)多項(xiàng)式相加。3詳細(xì)設(shè)計(jì)（1）鏈接存儲(chǔ)結(jié)構(gòu)：結(jié)構(gòu)體定義：struct nodeint coef; /系數(shù) int exp; /指數(shù) struct node * next;/指針域chainLink;/創(chuàng)建chainLink的node結(jié)點(diǎn)對(duì)象（值得注意的是，與順序存儲(chǔ)結(jié)構(gòu)不同的是，內(nèi)部還定義了指針域）功能函數(shù)介紹：struct node *create() /定義建立多項(xiàng)式函數(shù)，并返回鏈表頭指針struct node *h = NULL, *q, *p;/定義結(jié)構(gòu)體頭指針h，標(biāo)記指針p和q，p是創(chuàng)造新節(jié)點(diǎn)的標(biāo)記指針，q是鏈接鏈表的指針；int i = 1, N; /定義多項(xiàng)式的項(xiàng)數(shù)N及標(biāo)記數(shù)icout N;p = 0;/指針初始化；q = 0;/本地指針初始化；for (; i = N; i+)p = (struct node *)malloc(sizeof(chainLink); /為一個(gè)新節(jié)點(diǎn)分配空間cout 請(qǐng)輸入第 i (*p).coef;cout 請(qǐng)輸入第 i (*p).exp;if (i = 1) h = p; q = p; /建立頭節(jié)點(diǎn)elseq-next = p;q = p;q-next = NULL;/p,q都成為新鏈表的尾指針；p-next = NULL;return h;PS：值得注意的是，我在里面P，q指針均使其值為0，是讓其為空指針，對(duì)其進(jìn)行初始化，在visual studio 2013版中，如果不進(jìn)行初始化，會(huì)被報(bào)錯(cuò)。打印函數(shù)display:void display(struct node *h)struct node *p; /定義標(biāo)記指針，輸出鏈表p = h;while (p != NULL)if (p-coef = 0)struct node *d;d = h;while (d-next != p)d = d-next;d-next = p-next;p = p-next;/刪去系數(shù)為0的節(jié)點(diǎn)；elseif (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp = 0) cout (*p).coef exp!=0&p-exp!=1)cout (*p).coef *X (*p).exp +;else cout (*p).coef next;cout next; /將原來(lái)的鏈表建立成待排序鏈表h1-next = NULL; /截?cái)嗟谝粋€(gè)原鏈表中的節(jié)點(diǎn)while (h2 != NULL)q = h1;p = q-next;t = h2; /從待排序鏈表中選出一個(gè)節(jié)點(diǎn)準(zhǔn)備插入到新鏈表中h2 = h2-next; /移動(dòng)待排序鏈表的頭指針，便于進(jìn)行下一次挑選t-next = NULL;if (t-expq-exp) /應(yīng)插入頭指針之前的情況t-next = q;h1 = t;continue;if (p = NULL&t-exp exp) q-next = t; /應(yīng)插入表尾的情況while (p != NULL)if (t-expp-exp)q-next = t;t-next = p;break;elseq = q-next;p = p-next;if (p = NULL) q-next = t;return h1; /新鏈表即為按降冪順序排好的鏈表，返回其頭指針Order函數(shù)其實(shí)是利用了3個(gè)頭指針，具體操作看代碼即可，其實(shí)很容易懂。 相加函數(shù)add：struct node *add(struct node *h1, struct node *h2) /定義加法函數(shù)，并返回結(jié)果的鏈表的頭指針struct node *p, *q, *head, *r; /定義結(jié)構(gòu)體頭指針head和標(biāo)記指針p,q,rp = h1;q = h2;head = (struct node *)malloc(sizeof(chainLink); /為結(jié)果多項(xiàng)式分配頭指針if (p-exp = q-exp) head = h1; p = p-next; elseif (p-expexp) head = h2; q = q-next; else p-coef = p-coef + q-coef; head = p; p = p-next; q = q-next; r = head;while (p != NULL&q != NULL)if (p-expq-exp) r-next = p; p = p-next; elseif (p-expexp) r-next = q; q = q-next; else p-coef = p-coef + q-coef; r-next = p; p = p-next; q = q-next; r = r-next;if (p = NULL&q = NULL) r-next = NULL;elseif (p = NULL) r-next = q;if (q = NULL) r-next = p;return head;add函數(shù)大部分其實(shí)和老師PPT思路差不多。比較兩個(gè)多項(xiàng)式中指數(shù)大小，然后分別對(duì)其余兩個(gè)進(jìn)行操作。（2）順序存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)體定義：struct polyfloat coef;int exp;/結(jié)構(gòu)體數(shù)組定義主函數(shù)結(jié)構(gòu)體數(shù)組的創(chuàng)建以及導(dǎo)引指針的創(chuàng)建：poly p50, *po=p;poly p150, *po1=p1;poly p2100, *po2=p2;/定義三個(gè)結(jié)構(gòu)體數(shù)組，用于存放多項(xiàng)式,定義三個(gè)指針變量；print函數(shù)以及參數(shù)調(diào)用代碼：void print(struct poly *s, int n)for (int i = 0; i n; i+)if (i = n - 1)cout (*s)i.coef *X (*s)i.exp;elsecout (*s)i.coef *X (*s)i.exp+;/輸出數(shù)組主函數(shù)中調(diào)用print函數(shù)的具體形式：print(&po, n1);sort函數(shù)的代碼：void sort(struct poly *s, int n)int i, temp1, j; /定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i與j，和整型標(biāo)記temp1float temp2; /定義單精度型標(biāo)記temp2for (i = 0; in - 1; i+)for (j = i + 1; j(*s)i.exp)temp1 = (*s)j.exp;(*s)j.exp = (*s)i.exp;(*s)i.exp = temp1;temp2 = (*s)j.coef;(*s)j.coef = (*s)i.coef;(*s)i.coef = temp2;for (i = 0; in - 1; i+)if (*s)i.exp = (*s)i + 1.exp)(*s)i + 1.coef = (*s)i.coef + (*s)i + 1.coef;if (i = n - 2)(*s)i.coef = (*s)i + 1.coef;(*s)i + 1.coef = 0;elsefor (j = i; j(*s1)j.exp)(*s2)p.coef = (*s)i.coef;(*s2)p.exp = (*s)i.exp;i+;else(*s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;j+;if (i = n1 | j = n2)p+;break;if (i = n1)for (; jn2; j+)(*s2)p.coef = (*s1)j.coef;(*s2)p.exp = (*s1)j.exp;p+;elsefor (; in1; i+)(*s2)p.coef = (*s)i.coef;(*s2)p.exp = (*s)i.exp;p+;for (m = 0; mp; m+)if (*s2)m.coef0)if (*s2)m.exp = 0)cout (*s2)m.coef +;else cout (*s2)m.coef *X (*s2)m.exp 0)if (*s2)m.exp = 0)cout (*s2)m.coef +;else /printf( %.2f*X%d +, dxs2m.coef, dxs2m.exp);cout (*s2)m.coef *X (*s2)m.exp +;cout b b n;add函數(shù)在主函數(shù)中的調(diào)用：add(&po, &po1, &po2, n1, n2);4調(diào)試分析（1）鏈接存儲(chǔ)結(jié)構(gòu)：設(shè)計(jì)過(guò)程，注意指針保護(hù)，如果一步不小心，容易造成頭指針消失，所以需要指針來(lái)保護(hù)頭指針，至于其他方面倒是沒(méi)有什么問(wèn)題?？偟膩?lái)說(shuō)，代碼長(zhǎng)度170，算不上特別多，該有的功能也考慮到了。（2）順序存儲(chǔ)結(jié)構(gòu)在設(shè)計(jì)過(guò)程中，發(fā)現(xiàn)如果不采用指針參數(shù)傳遞結(jié)構(gòu)體數(shù)組，而是對(duì)單個(gè)多項(xiàng)式進(jìn)行單個(gè)功能操作，即對(duì)于每一個(gè)多項(xiàng)式都會(huì)用同功能的函數(shù)，只不過(guò)不同名稱來(lái)實(shí)現(xiàn)，這樣造成代碼冗長(zhǎng)，我試過(guò)寫出了286行的代碼，但visual studio2013無(wú)法編譯如此冗長(zhǎng)的代碼，所以我決定使用指針導(dǎo)向進(jìn)行優(yōu)化，優(yōu)化后的代碼行數(shù)是162行，少了100多行，實(shí)現(xiàn)功能也比之前多了一些。雖然沒(méi)法像我第一次寫那286行的代碼可以實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建結(jié)構(gòu)體數(shù)組，但我認(rèn)為，這162行的代碼的結(jié)構(gòu)體數(shù)組50個(gè)大小，理應(yīng)足夠計(jì)算，如果要更大，建議修改代碼中創(chuàng)建結(jié)構(gòu)體數(shù)組大小的尺寸?？傮w來(lái)說(shuō)，還算不錯(cuò)，知識(shí)經(jīng)過(guò)一個(gè)寒假忘得七零八落，感覺(jué)我還沒(méi)有完全掌握這類知識(shí)，等有時(shí)間重新將自己進(jìn)行優(yōu)化，也希望老師給予指導(dǎo)。5用戶使用說(shuō)明（1）鏈接存儲(chǔ)結(jié)構(gòu)：按照提示一步步來(lái)即可；舉例：請(qǐng)輸入第一個(gè)多項(xiàng)式：請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：3請(qǐng)輸入第一項(xiàng)的系數(shù)：2請(qǐng)輸入第一項(xiàng)的指數(shù)：2請(qǐng)輸入第二項(xiàng)的系數(shù)：3請(qǐng)輸入第二項(xiàng)的指數(shù)：5請(qǐng)輸入第三項(xiàng)的系數(shù)：3請(qǐng)輸入第三項(xiàng)的指數(shù)：1類似如上操作，到時(shí)大部分會(huì)在屏幕顯示。（2）順序存儲(chǔ)結(jié)構(gòu)按照提示一步步來(lái)即可；舉例：請(qǐng)您輸入第一個(gè)結(jié)構(gòu)體數(shù)組的項(xiàng)數(shù)（不超過(guò)50項(xiàng)）：2請(qǐng)您輸入第二個(gè)結(jié)構(gòu)體數(shù)組的項(xiàng)數(shù)（不超過(guò)50項(xiàng)）：2現(xiàn)在是輸入第一個(gè)多項(xiàng)式請(qǐng)輸入第1項(xiàng)系數(shù)：2請(qǐng)輸入第1項(xiàng)指數(shù)：2請(qǐng)輸入第2項(xiàng)系數(shù)：3請(qǐng)輸入第2項(xiàng)指數(shù)：3現(xiàn)在是輸入第二個(gè)多項(xiàng)式：請(qǐng)輸入第1項(xiàng)系數(shù)：3請(qǐng)輸入第1項(xiàng)指數(shù)：3請(qǐng)輸入第2項(xiàng)系數(shù)：4請(qǐng)輸入第2項(xiàng)指數(shù)：4接著屏幕便會(huì)顯示出來(lái)。6測(cè)試結(jié)果（1）鏈接存儲(chǔ)結(jié)構(gòu)：（2）順序存儲(chǔ)結(jié)構(gòu)7附錄（1）鏈接存儲(chǔ)結(jié)構(gòu)：#include using namespace std;struct nodeint coef; /系數(shù) int exp; /指數(shù) struct node * next;/指針域chainLink;/創(chuàng)建chainLink的node結(jié)點(diǎn)對(duì)象struct node *create() /定義建立多項(xiàng)式函數(shù)，并返回鏈表頭指針struct node *h = NULL, *q, *p;/定義結(jié)構(gòu)體頭指針h，標(biāo)記指針p和q，p是創(chuàng)造新節(jié)點(diǎn)的標(biāo)記指針，q是鏈接鏈表的指針；int i = 1, N; /定義多項(xiàng)式的項(xiàng)數(shù)N及標(biāo)記數(shù)icout N;p = 0;/指針初始化；q = 0;/本地指針初始化；for (; i = N; i+)p = (struct node *)malloc(sizeof(chainLink); /為一個(gè)新節(jié)點(diǎn)分配空間cout 請(qǐng)輸入第 i (*p).coef;cout 請(qǐng)輸入第 i (*p).exp;if (i = 1) h = p; q = p; /建立頭節(jié)點(diǎn)elseq-next = p;q = p;q-next = NULL;/p,q都成為新鏈表的尾指針；p-next = NULL;return h;void display(struct node *h)struct node *p; /定義標(biāo)記指針，輸出鏈表p = h;while (p != NULL)if (p-coef = 0)struct node *d;d = h;while (d-next != p)d = d-next;d-next = p-next;p = p-next;/刪去系數(shù)為0的節(jié)點(diǎn)；elseif (p-coefexp = 0) cout (*p).coef +;else cout ( (*p).coef ) *X (*p).exp exp = 0) cout (*p).coef exp!=0&p-exp!=1)cout (*p).coef *X (*p).exp +;else cout (*p).coef next;cout next; /將原來(lái)的鏈表建立成待排序鏈表h1-next = NULL; /截?cái)嗟谝粋€(gè)原鏈表中的節(jié)點(diǎn)while (h2 != NULL)q = h1;p = q-next;t = h2; /從待排序鏈表中選出一個(gè)節(jié)點(diǎn)準(zhǔn)備插入到新鏈表中h2 = h2-next; /移動(dòng)待排序鏈表的頭指針，便于進(jìn)行下一次挑選t-next = NULL;if (t-expq-exp) /應(yīng)插入頭指針之前的情況t-next = q;h1 = t;continue;if (p = NULL&t-exp exp) q-next = t; /應(yīng)插入表尾的情況while (p != NULL)if (t-expp-exp)q-next = t;t-next = p;break;elseq = q-next;p = p-next;if (p = NULL) q-next = t;return h1; /新鏈表即為按降冪順序排好的鏈表，返回其頭指針struct node *add(struct node *h1, struct node *h2) /定義加法函數(shù)，并返回結(jié)果的鏈表的頭指針struct node *p, *q, *head, *r; /定義結(jié)構(gòu)體頭指針head和標(biāo)記指針p,q,rp = h1;q = h2;head = (struct node *)malloc(sizeof(chainLink); /為結(jié)果多項(xiàng)式分配頭指針if (p-exp = q-exp) head = h1; p = p-next; elseif (p-expexp) head = h2; q = q-next; else p-coef = p-coef + q-coef; head = p; p = p-next; q = q-next; r = head;while (p != NULL&q != NULL)if (p-expq-exp) r-next = p; p = p-next; elseif (p-expexp) r-next = q; q = q-next; else p-coef = p-coef + q-coef; r-next = p; p = p-next; q = q-next; r = r-next;if (p = NULL&q = NULL) r-next = NULL;elseif (p = NULL) r-next = q;if (q = NULL) r-next = p;return head;int main()struct node *h1, *h2, *h3;/定義3個(gè)頭指針；cout n請(qǐng)輸入第一個(gè)多項(xiàng)式：n;h1 = create();/創(chuàng)造第一個(gè)線性鏈表；cout n您輸入的第一個(gè)多項(xiàng)式為：n;display(h1);/把多項(xiàng)式顯示出來(lái)；h1 = order(h1);cout n降冪排列后的第一個(gè)多項(xiàng)式為：n;display(h1);cout n;cout n請(qǐng)輸入第二個(gè)多項(xiàng)式：n;h2 = create();/創(chuàng)造第二個(gè)線性鏈表；cout n您輸入的第二個(gè)多項(xiàng)式為：n;display(h2);/把多項(xiàng)式顯示出來(lái)；h2 = order(h2);cout n降冪排列后的第二個(gè)多項(xiàng)式為：n;display(h2);cout n;h3 = add(h1, h2);/利用加函數(shù)將多項(xiàng)式相加；cout n第一個(gè)多項(xiàng)式和第二個(gè)多項(xiàng)式相加后：n;display(h3);system(pause);return 0;（2）順序存儲(chǔ)結(jié)構(gòu)#include using namespace std;struct polyfloat coef;int exp;/結(jié)構(gòu)體數(shù)組定義void defStruct(struct poly *s,int n)int i = 0;for (; i n; i+)cout 請(qǐng)輸入第 i + 1 (*s)i.coef;cout 請(qǐng)輸入第 i + 1 (*s)i.exp;/初始化順序結(jié)構(gòu)體數(shù)組void print(struct poly *s, int n)for (int i = 0; i n; i+)if (i = n - 1)cout (*s)i.coef *X (*s)i.exp;elsecout (*s)i.coef *X (*s)i.exp+;/輸出數(shù)組void sort(struct poly *s, int n)int i, temp1, j; /定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i與j，和整型標(biāo)記temp1float temp2; /定義單精度型標(biāo)記temp2for (i = 0; in - 1; i+)for (j = i + 1; j(*s)i.exp)temp1 = (*s)j.exp;(*s)j.exp = (*s)i.exp;(*s)i.exp = temp1;temp2 = (*s)j.coef;(*s)j.coef = (*s)i.coef;(*s)i.coef = temp2;for (i = 0; in - 1; i+)if (*s)i.exp = (*s)i + 1.exp)(*s)i + 1.coef = (*s)i.coef + (*s)i + 1.coef;if (i = n - 2)(*s)i.coef = (*s)i + 1.coef;(*s)i + 1.coef =