數(shù)據(jù)結(jié)構(gòu)實驗報告實習題名：線性表的基本運算以及多項式的算術運算班級：B120413姓名：陳何淵學號B12041318日期：2013.10.7順序表的基本運算：問題描述實現(xiàn)單鏈表的定義和基本操作。實現(xiàn)順序表的逆置。刪除表中所有元素值等于x的元素。若表中存在這樣的元素，刪除之，函數(shù)返回true；否則返回false。概要設計如下圖顯示了名為SeqList.dsw的工程，包含3個文件，包括linearlist.h，list.h和SeqList.cpp。其中l(wèi)inearlist.h和list.h是程序頭文件。List.h是linearlist.h的派生類來實現(xiàn)線性表的基本運算。SeqList.cpp是程序運行文件。而主函數(shù)代碼如圖所示：詳細設計類和類的層次結(jié)構(gòu)程序使用兩個類，即linearlist.h和list.h和一個主函數(shù)main。其中l(wèi)inearlist.h是公公接口。模板類list.h是linearlist.h的派生類，實現(xiàn)了順序表的所有接口函數(shù)，同時也包括了Reverse()和DeleteX()函數(shù)。而main函數(shù)包含了list.h從而實現(xiàn)了單鏈表的基本運算。如下圖是linearlist.h和list.h的實現(xiàn)部分。核心算法對于函數(shù)voidReverse()；首先申請一個臨時變量temp，然后數(shù)組從下標為零到下標【n/2】遍歷，通過中間的臨時變量temp,將下標為j和下標為n-j-1兩個數(shù)組元素互換而達到順序表逆置的目的。voidReverse(){Ttemp;for(intj=0;j<n/2;j++){temp=elements[j];elements[j]=elements[n-j-1];elements[n-j-1]=temp;}}對于函數(shù)boolDeleteX(constT&x)先定義一個變量k并且賦值n，然后數(shù)組從頭到尾遍歷，通elements[i]==x控制條件來實現(xiàn)以下操作:如果為真，則后繼元素前移一個，否則繼續(xù)遍歷。boolDeleteX(constT&x){intk=n; for(inti=0;i<n;i++) {if(elements[i]==x) {for(intj=i+1;j<n;j++) elements[j-1]=elements[j]; n--;}} returnk==n;}算法分析主要算法voidReverse()；和boolDeleteX(constT&x)；的算法時間復雜度為O（n）程序代碼template<classT>intSeqList<T>::Search(Tx)const{ for(intj=0;j<n;j++) if(elements[j]==x) returnj; return-1;}template<classT>boolSeqList<T>::Insert(inti,Tx){ if(1<-1||i>n-1) { cout<<"OutofBounds"<<endl;returnfalse; } if(n==maxLength) { cout<<"OverFlow"<<endl;returnfalse; } for(intj=n-1;j>i;j--)elements[j+1]=elements[j]; elements[i+1]=x; n++; returntrue;}template<classT>boolSeqList<T>::Delete(inti){ if(!n) { cout<<"UnderFlow"<<endl;returnfalse; } if(i<0||i>n-1) { cout<<"OutofBounds"<<endl;returnfalse; } for(intj=i+1;j<n;j++) elements[j-1]=elements[j]; n--; returntrue;}測試結(jié)果實習小結(jié)編寫代碼的過程中應該書寫規(guī)范以減少錯誤，同時得理解線性表的相關運算和它的存取結(jié)構(gòu)，調(diào)試過程中的不斷更正錯誤。多項式的算術操作：問題描述設計帶表頭結(jié)點的單鏈表表示多項式實現(xiàn)輸入并建立多項式，輸出多項式和多項式運算。重載*運算符。以線性表來描述一元多項式，存儲結(jié)構(gòu)采用單鏈表，每個結(jié)點存儲的多項式中某一項的系數(shù)和指數(shù)，建立單鏈表的元素按指數(shù)遞減有序排列。概要設計如下圖顯示了名為Polynominal.dsw的工程，包含了2個文件，包括Polynominal.cpp和Polynominal.h。Polynominal.h是該程序頭文件，Polynominal.cpp是其運行文件。其中Polynominal是Term的友元類。而主函數(shù)代碼如圖所示：詳細設計類及其類與類的關系Polynominal.h中包含了兩個類，一個是Term類，一個是Polynominal類。其中Polynominal類是Term類的友元類。第一個類是為創(chuàng)建多項式中的每一項而建立的類。其中對Term類的構(gòu)造函數(shù)實現(xiàn)了重載，而Term(intc,inte,Term*nxt);是為創(chuàng)建表頭項結(jié)點；Term(intc,inte);是為創(chuàng)建非表頭項結(jié)點；Term*InsertAfter(intc,inte);是Term類型的函數(shù)指針，其目的是為返回插入的項的地址，從而使前一項得到該項的地址。Polynominal則是多項式類。其中voidAddTerms(istream&in);是為添加項；voidPolyAdd(Polynominal&r);和voidPolyMul(Polynominal&r);是多項式的加法與乘法函數(shù)，friendPolynominal&operator+(Polynominal&,Polynominal&);和friendPolynominal&operator*(Polynominal&,Polynominal&);分別是對其運算進行重載。另外增加表尾結(jié)點指針Term*theLast，指向多項式鏈表的表尾。類中函數(shù)如下圖所示：2．核心算法加法核心算法：設p，q分別指向多項式p（x）和q（x）的當前正進行比較的項結(jié)點，初始時分別指向多項式中最高次冪的項結(jié)點。q1指向q的前驅(qū)結(jié)點。對p（x）進行遍歷，根據(jù)指針p、q的exp域的大小情況做相應處理實現(xiàn)加法運算。多項式相加的算法步驟如下：若p->exp<q->exp，則q指示的項應成為結(jié)果多項式中的一項，所以q1和q右移一項，指針p不動。若p->exp==q->exp，則系數(shù)相加，即q->coef=q->coef+p->coef。如果q->coef不為零，則指針q1和q均右移一個結(jié)點，否則從q（x)中刪除q指示的結(jié)點，指針p右移一項。若p->exp>q->exp,則復制p所指示的結(jié)點，并將其插在q1之后；指針p右移一項。重復上述處理，直到p（x）中全部結(jié)點都處理完。voidPolynominal::PolyAdd(Polynominal&r){Term*q,*q1=theList,*p;p=r.theList->link;q=q1->link;while(p->exp>=0){while(p->exp<q->exp){q1=q;q=q->link;}if(p->exp==q->exp){q->coef=q->coef+p->coef;if(q->coef==0){q1->link=q->link;delete(q);q=q1->link;}else{q1=q;q=q->link;}}elseq1=q1->InsertAfter(p->coef,p->exp);p=p->link;}}乘法核心算法：創(chuàng)建Polynomial的對象s1和s，以及Term型指針，*p，*q，*p1，*q1；p1指向當前對象表頭結(jié)點，q1指向?qū)ο髍的表頭r.theList，而p，q分別指向p1和q1的后一項；固定p，讓p遍歷q并做運算。多項式相乘的算法步驟如下：若p->exp>=0,則申請指向s1的表頭節(jié)點的指針，*ps1，ps2*；1）：若q->exp>=0，則系數(shù)相乘，指數(shù)相加，通過指針ps1插入到s1中，并把表尾結(jié)點連接在該新項后面，q與q1指向下一項，直至q->exp<0；2）：將s1存入到s中，累加每次的相乘結(jié)果，即s=s+s1，然后q1重指向r的表頭結(jié)點，q指向下一項，p與p1也分別指向下一項；3）：將s1中的數(shù)據(jù)清空，為下一次數(shù)據(jù)存儲做準備；4）：循環(huán)上述步驟直到p->exp<0；voidPolynominal::Polymul(Polynominal&r){Term*p=theList,*q;p=p->link;for(;p->exp>=0;p=p->link){q=r.theList;q=q->link;Polynominaltemp;Term*t=temp.theList;for(;q->exp>=0;q=q->link){t=t->InsertAfter(p->coef*q->coef,p->exp+q->exp);}poly.PolyAdd(temp);}}程序代碼Term*Term::InsertAfter(intc,inte){link=newTerm(c,e,link); returnlink；}Polynominal&operator*(Polynominal&a,Polynominal&b){ a.PolyMul(b); returna;}運行代碼：#include<iostream>#include"Polynominal.h"voidmain(){ Polynomin