链表实现一元多项式运算
{ node* prt = GetPtr(pos-1); //获取指向第pos-1个结点的指针 node* pNext = prt->next; //获取指向第pos个结点的指针 prt->next = new node; //将第pos-1个结点的后继指向新的结点 count++; //置入表中不存在的元素，元素总数加一 prt->next->data = e; //将e写入新结点的数据部分 prt->next->next = pNext; //将新结点的后继指向原来第pos个位置的结点 } }
template
void SimpleLinkList::GetElem(int pos, ET &e) { if(pos<1 || pos>count) cout<data; //获取指向第pos个结点的数据部分 }
template
void SimpleLinkList::DelElem(int pos) { //删除在第pos个位置的结点 if(pos<1 || pos>count) cout<* prt = GetPtr(pos-1); //获取指向第pos-1个结点的指针 node* pNext = prt->next; //获取指向第pos个结点的指针 prt->next = pNext->next; //将第pos-1个结点的后继指向第pos个结点的后继 delete pNext; //将第pos个结点删除 count--; //表元素元素总数减一 } }
template
void SimpleLinkList::operator=(SimpleLinkList& cop) { //赋值符“ = ”重载 Clear(); //对当前链表先清空 if(cop.count>0) { int cot = cop.count; ET elem; node* opr = cop.head; //复制cop的头指针 while(cot>0) //当表中还有元素时 { opr = opr->next; //向后继结点移动一位 elem = opr->data; //取出后继结点中的数据
共7页
11
链表实现一元多项式运算
SetElem(elem); //生成新结点 cot --; //计数元素总数减一 } } }
template
void SimpleLinkList::SUB(SimpleLinkList &A, SimpleLinkList &B) { Clear(); //对当前链表先清空 int countA=1, countB; ET elemA, elemB; node* posA = A.head, * posB; while(countA<=A.count) //当表A中还有元素时 { countB=1; posB = B.head; //从B表表头开始比对 posA = posA->next; elemA = posA->data; //依次获取A表中元素的数据部分 countA++; while(countB<=B.count) //当表B中还有元素时 { posB = posB->next; elemB = posB->data; if(elemA==elemB) break; //将A中的每一个元素分别与B中的每一个元素进行比较，若相同则中断本次循环 countB++; } if(countB>B.count) SetElem(elemA); //若与B中所有元素均不相同时将该元素写入当前表中 } }
template
void SimpleLinkList::ADD(SimpleLinkList &A, SimpleLinkList &B) { Clear(); //对当前链表先清空 int countA=1, countB=1; node* posA = A.head, * posB= B.head; while(countA<=A.count) //当表A中还有元素时 { posA = posA->next; SetElem(posA->data); //依次获取A表中元素的数据部分,写入当前链表 countA++; } while(countB<=B.count) //当表B中还有元素时 { posB = posB->next; SetElem(posB->data); //依次获取B表中元素的数据部分
共7页
12
链表实现一元多项式运算
countB++; } }
template
void SimpleLinkList::Seprate() 偶数前 { 为链表中元素的总个数 int i=0, jb=0, jc=0; int *B = new int[count], *C = new int[count]; 中的元素按奇数、偶数分别存放到数组B、C中 node* pos = head; ET tmp; while(i < count) { pos = pos->next; tmp=pos->data; if(tmp%2 == 1){ B[jb] = tmp; jb++;} else { C[jc] = tmp; jc++;} i++; } i = 0; pos = head; while(i < jb) 中 { pos = pos->next; pos->data = B[i]; i++; } i = 0; while(i < jc) 中奇数之后 { pos = pos->next; pos->data = C[i]; i++; } }
template
void SimpleLinkList::Sort() { int i=1, j; node* posi = head, * posj; ET tmp; while(i <= count-1) { j=i+1;
共7页
//奇偶分离函数，使得所有奇数均排列在
//count
//将链表
//jb用于计数奇数的个数
//jc用于计数偶数的个数
//将奇数依次存回到链表
//将偶数依次存回到链表
//对链表中的元素进行排序
13
链表实现一元多项式运算
posi = posi->next; posj = posi; while(j <= count) { posj = posj->next; if(posi->data > posj->data) //交换数据元素 {tmp=posi->data; posi->data=posj->data; posj->data=tmp;} j++; } i++; } }
template
void SimpleLinkList::Reserve() { int tmp=1; //为逆序的递归算法提供计数变量tmp，变量从1变化到count-1 ResHelp(tmp); //并对其进行调用 }
template
void SimpleLinkList::ResHelp(int &tmp) { node* pos; if(tmpnext; //指向线性链表的第一个元素 head->next=pos->next; //头结点的后继依次向下一个元素 tmp++; //用tmp进行计数，当达到元素总数时退出递归调用 ResHelp(tmp); //对下一个结点递归调用逆序函数 pos->next->next=pos; //从第count-1个元素开始回溯，使其后继指向第count-1个元素 } }
template
void SimpleLinkList::CinHelp() { int choice=1, pos; ET elem; while(choice) { cout<>choice; switch(choice) {
共7页
14
链表实现一元多项式运算
case 1: cout<>pos; choice = count; //链表中原有的元素数不应在计数范围内 cout<>elem; SetElem(elem);} Show(); break; case 2: //插入表元素 cout<>elem>>pos; Insert(pos, elem); Show(); break; case 3: //删除表元素 cout<>pos; if(pos<1 || pos>count) cout<>elem>>pos; ReSetElem(pos, elem); Show(); break; case 5: //清空 Clear(); Show(); break; } cout<>choice; cout<共7页
15
链表实现一元多项式运算
共7页
16