/* 线性表链式存储算法 文件名：xianxingb.h 2005.5.11 2005.5.12完成v1.0 2005.5.13 */ #include <iostream> using namespace std; typedef int ElemType;

class xianxingb { public: xianxingb (); void OrderInsertList (ElemType item); void OutputList (); bool DeleteList (ElemType item); ElemType GetElemList (int pos); bool EmptyList (); void ClearList (); ~xianxingb ();

struct sNode //元素结构体 { ElemType data; struct sNode *next; }; struct sNode *HL; //表头指针 int count; //链表元素个数 }; xianxingb::xianxingb () //构造函数 { HL = NULL; count = 0; } void xianxingb::OrderInsertList(ElemType item) //插入一个节点 { struct sNode *newp = new sNode; //动态分配一个存储节点 if (!newp) { cout << "内存用完\n"; exit(1); } newp->data = item; //给新节点赋值 if (HL == NULL || item < HL->data) //链表为空或新元素的值小于表头节点，则把它插入到表头 { newp->next = HL; HL = newp; count++; return; } sNode *q = HL,*p = q->next; //建2个指针，q在前，p在后，分别指向链表中的元素 while (p) //顺序查找值比新值大的节点 { if (item < p->data) break; q = p; p = p->next; } q->next = newp; //插入新节点 newp->next = p; count++; } void xianxingb::OutputList() //遍历输出 { struct sNode *p = HL; while (p) { cout << p->data << ' '; p = p->next; } cout << endl; } bool xianxingb::DeleteList(ElemType item) //删除等于指定值的第一个元素 { struct sNode *p = HL,*q = p; while (q) { if (q->data == item) { if (q == HL) //如果指定值是首元素 { HL = q->next; } else //指定值不是首元素 { p->next = q->next; } delete q; //释放已删除元素占用的内存 count--; //元素个数-1 return true; } p = q; q = q->next; } cout << "未找到指定值"; return false; } ElemType xianxingb::GetElemList(int pos) //取得第pos个元素的值 { if (pos < 1 || pos >count) { cout << "超出范围\n"; exit(1); } struct sNode *p = HL; for (int i=1;i<pos ;i++ ) { p = p->next; } return p->data; } bool xianxingb::EmptyList() //判断是否为空 { return HL == NULL; } void xianxingb::ClearList() { struct sNode *p = HL,*q = p; while (q) { q = p->next; delete p; p = q; } HL = NULL; } xianxingb::~xianxingb() //析构函数（清除所有元素，释放空间） { ClearList(); }

/* 多项式算法 文件名：duoxiangshi.cpp 2005.5.13 2005.5.13 */ //#include <iostream> #include "xianxingb.h" //using namespace std;

class duoxiangshi:public xianxingb { public: void OrderInsertList (ElemType item,int sb); void OutputList (); int compute (int ds); ~duoxiangshi ();

struct sNode { ElemType zhishu; //指数 int xishu; //系数 struct sNode *next; }; struct sNode *HL; //表头指针 }; void duoxiangshi::OrderInsertList(ElemType sb,int item) //插入一个节点，sb:指数;item:系数 { struct sNode *newp = new sNode; //动态分配一个存储节点 if (!newp) { cout << "内存用完\n"; exit(1); } newp->xishu = item; //给新节点赋值 newp->zhishu = sb; newp->next = NULL; if (HL == NULL || sb < HL->zhishu) //链表为空或新元素的值小于表头节点，则把它插入到表头 { newp->next = HL; HL = newp; count++; return; } sNode *q = HL,*p = q->next; //建2个指针，q在前，p在后，分别指向链表中的元素 while (p) //顺序查找值比新值大的节点 { if (sb < p->zhishu) break; q = p; p = p->next; } q->next = newp; //插入新节点 newp->next = p; count++; } void duoxiangshi::OutputList () //遍历链表 { struct sNode *p = HL; while (p) { cout << p->xishu << ' ' << p->zhishu << ';'; p = p->next; } cout << endl; } int duoxiangshi::compute(int ds) //计算多项式值 { int jieguo = 0,i = 0,xunhuan = ds; struct sNode *p = HL; while (p) { if (p->zhishu == 0) { jieguo += p->xishu; } else { for (i=1;i<p->zhishu ;i++ ) { xunhuan *= ds; } jieguo += xunhuan; } p = p->next; } return jieguo; } duoxiangshi::~duoxiangshi() //析构函数 { struct sNode *p = HL,*q = p; while (q) { q = p->next; delete p; p = q; } HL = NULL; }

int main() { ElemType num; int sb,x; duoxiangshi S; printf("多项式计算，输入系数和指数\n"); cout << "系数："; cin >> num; cout << "指数："; cin >> sb; while (sb >= 0) { S.OrderInsertList(sb,num); cout << "共" << S.count << "个元素\n"; cout << "系数："; cin >> num; cout << "指数："; cin >> sb; } cout << "共" << S.count << "个元素\n"; S.OutputList(); cout << "共" << S.count << "个元素\n"; /* cout << "变量值："; cin >> x; cout << "多项式值 = " << S.compute(x); */ return 0; }