线性表+应用+多项式+dev c++

#include<iostream> #include<stdlib.h> #include<math.h> using namespace std; struct Term { double coef; //系数 int exp; //指数 }; typedef Term ElemType; struct LNode{ ElemType data; LNode* next; }; bool operator ==(const ElemType& e1, const ElemType& e2) { return e1.exp==e2.exp; } bool operator <(const ElemType& e1, const ElemType& e2) { return e1.exp<e2.exp; } ostream& operator <<(ostream& ostr,const ElemType& x) { ostr<<x.coef<<" "<<x.exp<<" "; return ostr; } ElemType* operator +(const ElemType& e1, const ElemType& e2) { ElemType* e3; e3 = new ElemType; if(e1.exp==e2.exp) { e3->exp = e1.exp; e3->coef = e1.coef+e2.coef; return e3;} else { cout<<"the two variables' exp must be the same in the function <operator +>"<<endl; exit(1);} } //1. 初始化单链表 void InitList(LNode* &HL) { HL=NULL; //置单链表为空 } //2.删除单链表中的所有结点,使之成为一个空表 void ClearList(LNode*& HL) { LNode *cp; //将用cp(current pointer)指向待处理结点 LNode *np; //将用np(next pointer)指向cp的后继结点 cp=HL; //表头指针赋给 cp while(cp!=NULL) { //遍历单链表,释放每个结点的存储空间 np=cp->next; //保存下一个结点的地址 delete cp; //删除当前结点,即被处理的结点 cp=np; //使下一个结点成为当前结点 } //置单链表为空 HL=NULL; } //3. 得到单链表的长度 //由于在单链表的构成中,没有给出单链表的长度,所以此算法需要遍历单链表 //方问的结点进行计数,最后返回计数值。 int LenthList(LNode* HL) { int i=0; //用来统计单链表中结点的个数 while(HL!=NULL) //遍历单链表,统计结点数 { i++; HL=HL->next; } return i; //返回单链表长度 } //4. 检查单链表是否为空 bool EmptyList(LNode* HL) { return HL==NULL; } //5.得到单链表中第 pos个结点中的元素 ElemType GetList(LNode* HL, int pos) { if(pos<1) //pos 值有错,退出运行 { cerr<<"pos is out range!"<<endl; exit(1); } int i=0; //统计已遍历的结点数,1初值为 0 while(HL!=NULL){ //遍历到第 pos 个结点或表为空时止 i++; if(i==pos) break; HL=HL->next; } if(HL!=NULL) //返回结点值 return HL->data; else { cerr<<"pos is out range!"<<endl; exit(1); } } //6.遍历一个单链表 //遍历一个单链表并打印出每个结点的值。 void TraverseList(LNode* HL) //从表头开始依次输出每个结点的值 { while(HL!=NULL) { cout<<HL->data.coef<<" "; cout<<HL->data.exp<<" "; HL=HL->next; } cout<<endl; } //9.向单链表中按给定条件插入一个元素 //(1)判定pos的值,若小于一￥则表明pos值无效,返回假。 //(2)为新插入元素动态分配结点并赋值。 //(3)根据pos的值所表示的不同条件,寻找新结点的插入位置,为此需要从表头开始 // 顺序查找新元素的插入位置,在查找过程中必须保留当前待比较结点的地址及其前驱结点 // 的地址,以便插入时使用。 //(4)在插入位置上完成插入新结点操作,即把新结点链接到当前结点和前驱结点之 // 间。若插入的位置为表头,则需要做特殊处理。 bool InsertList(LNode* &HL,ElemType item,int pos) { //pos 值小干-1返回假 if(pos<-1){ cout<<"pos值无效！"<<endl; return false; } //为item元素建立新结点 LNode* newptr; newptr=new LNode; newptr->data=item; //寻找新结点的插入位置 //用cp指向当前结点(即待查结点),初始指向表头 LNode* cp=HL; //用ap(ahead pointer)指向cp的前驱结点,初始为空 LNode* ap=NULL; if(pos==0){ //按值寻找插入位置 while(cp!=NULL) { //找到新元素插入位置,退出循环 if(item<cp->data) break; else { //ap和cp 指针均后移,实现顺序向后 ap=cp; cp=cp->next; } } } else if(pos==-1) //查找表尾位置 while(cp!=NULL) {ap=cp;cp=cp->next;} else { //按序号pos的值寻找插入位置 int i=0; while(cp!=NULL){ i++; if(i==pos) break; //找到新元素插入位置,退出循环 else { //ap和cp指针均后移,实现顺序向后比 ap=cp; cp=cp->next; } } if(cp==NULL && i+1<pos) { cout<<"pos 值超出单链表长度加1!"<<endl; return false; } } //完成新结点插入操作 if(ap==NULL) { //把新结点插入到表头 newptr->next=HL; HL=newptr; } else { //把新结点插入到非表头位置,即插入到ap 和cp 结点之间 newptr->next=cp; //cp指针也可能为空,此时为表尾 ap->next=newptr; } return true; } //10.从单链表中删除符合给定条件的第1个元素 //删除算法的执行步骤如下: //(1)若单链表为空则返回假。 //(2)若pos 值小于-1时则返回假。 //(3)根据pos的值所表示的条件从单链表中查找被删除的结点,为此需要从单链表中 // 顺序查找,直到查找成功或失败为止。在查找过程中需要保留待比较的当前结点和前驱结 // 点的地址,以便删除结点时使用。 //(4)删除查找到的结点,对表头结点和非表头结点要做不同处理。 //(5)回收被删除结点的存储空间。 //(6)删除成功返回真。 bool DeleteList(LNode* &HL,ElemType& item,int pos) //从L删除元素 { //单链表为空,无法删除,返回假 if(HL==NULL){ cerr<<"单链表为空,删除操作无效！"<<endl; return false; } //pos 值小于-1 返回假 if(pos<-1) { cout<<"pos值无效！"<<endl; return false; } //寻找被删除的元素结点 LNode* cp=HL; //用cp 指向当前结点(即待查结点),初始指向表头 LNode* ap=NULL; //用ap (ahead pointer)指向cp的前驱结点,初始为空 if(pos==0){ //按值查找被删除结点 while(cp!=NULL){ if(item==cp->data) break; //找到被删除结点 cp,退出循环 else { //ap 和cp 指针均后移,实现顺序向后比) ap=cp; cp=cp->next; } } if(cp==NULL) { cout<<"单链表中没有相应的结点可删除!"<<endl; return false; } } else if(pos==-1) //查找表尾结点 while(cp->next!=NULL) { ap=cp;cp=cp->next; } else { //按序号查找结点位置 int i=0; while(cp!=NULL) { i++; if(i==pos) break; //找到被删除结点 cp,退出循环 else { //ap 和 cp 指针均后移,实现顺序向后比较 ap=cp; cp=cp->next; } } if(cp==NULL){ cout<<"pos 值无效!"<<endl; return false; } } //删除 cp 所指向的结点 if(ap==NULL) HL=HL->next; //删除表头结点 else ap->next=cp->next; //删除非表头结点,也可以是表尾结点 //收回被删除结点的存储空间 delete cp; //删除成功返回真 return true; } //11.对单链表进行数据排序 //假定待排序的单链表由表头指针 HL 所指向,对结点值按照从小到大次序进行排序链 //接时,首先建立一个空的单链表,然后把 HL 中的每个结点取出并按值依次插入到新建立 //插入排序算法。 的单链表中,最后由引用参数 HL 带回新建单链表的表头指针。下面就是对单链表进行 //的插入排序算法 void SortList (LNode* &HL) {//建立一个反映排序结果的新单链表并初始化为空 LNode* SL; InitList(SL); //从待排序的HL单链表中依次取出每个结点,按值插入到新链表中 LNode* r=HL; //r指向待取出排序的一个结点,初始为HL表头结点 while(r!=NULL){ //为新插入的士结点在SL中顺序查找出插入位置 LNode* t=r->next; //t指向r的后继结点 LNode* cp=SL; //用cp初始指向SL单链表的表头 LNode* ap=NULL; //用ap指向cp的前驱结点,初始为空 while(cp!=NULL) { if(r->data<cp->data) break; //找到被插入点,退出循环 else{ //ap 和cp 指针均后移,实现顺序向后比较 ap=cp; cp=cp->next; } } //实现插入操作 if(ap==NULL) { //把r结点插入到表头 r->next=SL; SL=r; } else {//把r结点插入 ap 和 cp 结点之间 r->next=cp; //cp可能为空,则r成为SL的表尾 ap->next=r; } //使r指向原单链表的下一个结点 r=t; } //由引用参数带回新单链表的表头指针 HL=SL; } //若多项式线性表采用链接存储结构,则求值算法描述如下。 //P表示存储的数据,x是多项式中的x; double PolySum2(LNode* P, double x) { LNode *t=P; //用t指向多项式单链表的表头结点 double sum=0; //用sum计算累加和,不知第一项是否为常数，因此设置为0 int y; while(t!=NULL) { //累加计算多项式的值 y=t->data.exp; sum+=t->data.coef*pow(x,y); //把一个新项的值累加到sum中 t=t->next; //使t指向下�