/* 线性表链式存储算法 文件名：xianxingb.h 2005.5.11 2005.5.12完成v0.1 2005.5.24改为模板 */ #include <iostream> using namespace std; template <class ElemType> class xianxingb //线性表类 { public: xianxingb (); void OrderInsertList (ElemType item); //插入一个节点 void OutputList (); //遍历输出 bool DeleteList (ElemType item); //删除等于指定值的第一个元素 ElemType GetElemList (int pos); //取得第pos个元素的值 bool EmptyList (); //判断是否为空 void ClearList (); //清空 ~xianxingb (); struct sNode //元素结构体 { ElemType data; struct sNode *next; }; struct sNode *HL; //表头指针 int count; //链表元素个数 }; template <class ElemType> xianxingb<ElemType>::xianxingb () //构造函数 { HL = NULL; count = 0; } template <class ElemType> void xianxingb<ElemType>::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++; } template <class ElemType> void xianxingb<ElemType>::OutputList() //遍历输出 { struct sNode *p = HL; while (p) { cout << p->data << ' '; p = p->next; } cout << endl; } template <class ElemType> bool xianxingb<ElemType>::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; } template <class ElemType> ElemType xianxingb<ElemType>::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; } template <class ElemType> bool xianxingb<ElemType>::EmptyList() //判断是否为空 { return HL == NULL; } template <class ElemType> void xianxingb<ElemType>::ClearList() //清空 { struct sNode *p = HL,*q = p; while (q) { q = p->next; delete p; p = q; } HL = NULL; } template <class ElemType> xianxingb<ElemType>::~xianxingb() //析构函数（清除所有元素，释放空间） { ClearList(); }

/* 链栈算法 文件名：lianzhan.h 2005.5.14 2005.5.14 */ #include "xianxingb.h" template <class ElemType> class lianzhan:public xianxingb <class ElemType> //链栈类，继承自线性表类 { public: void push (const ElemType& item); //入栈操作 ElemType Pop(); //出栈操作 ElemType Peek(); //读取栈顶元素 bool EmptyStack(); //判断链栈是否为空 }; template <class ElemType> void lianzhan<ElemType>::push(const ElemType& item) //入栈操作 { sNode *newptr = new sNode; if (!newptr) { cerr << "内存分配失败\n"; exit(1); } newptr->data = item; //给新节点赋值 newptr->next = HL; //新节点入栈 HL = newptr; } template <class ElemType> ElemType lianzhan<ElemType>::Pop() //出栈操作，并返回出站元素的值 { if (!HL) { cerr << "不能从空栈出栈\n"; exit(1); } ElemType num = HL->data; //暂存栈顶元素值 sNode *p = HL; //暂存栈顶指针 HL = HL->next; //移动栈顶指针，实现出栈 delete p; //释放出站元素占用的内存 return num; } template <class ElemType> ElemType lianzhan<ElemType>::Peek() //读取栈顶元素 { if (HL == NULL) //链栈为空则不读取 { cerr << "链栈为空\n"; exit(1); } return HL->data; } template <class ElemType> bool lianzhan<ElemType>::EmptyStack() //判断链栈是否为空 { return HL == NULL; }

/* 计算后缀表达式 文件名：houzhui.cpp 2005.5.23 2005.5.23 */ #include "lianzhan.h" double Compute(char *str) { lianzhan <double> L; double x,y; int i = 0; while (str[i]) //扫描每一个字符 { if (str[i] == ' ') //扫描到空格则不作处理，跳到下一个循环 { i++; continue; } switch (str[i]) { case '+': x = L.Pop() + L.Pop(); i++; break; case '-': x = L.Pop(); x = L.Pop() - x; i++; break; case '*': x = L.Pop() * L.Pop(); i++; break; case '/': x = L.Pop(); if (x != 0) { x = L.Pop() / x; } else { cout << "除数不能为0，错误退出\n"; exit(1); } i++; break; default: x = 0; //x保存数字的整数部分的值 while (str[i] >= 48 && str[i] <= 57) { x = x * 10 + str[i] - 48; i++; } if (str[i] == '.') { i++; y = 0; //y保存数字的小数部分的值 double j = 10.0; //小数的权值 while (str[i] >= 48 && str[i] <= 57) { y += (str[i] - 48)/j; i++; j *= 10; } } x += y; //把小数部分的值合并到x中 }//switch结束 L.push(x); }//while结束 if (L.EmptyStack()) //计算结束后栈为空则终止 { cerr << "栈为空\n"; exit(1); } x = L.Pop(); //若栈中只有一个元素，则返回作为表达式的值，否则是错误 if (L.EmptyStack()) { return x; } else { cerr << "出错\n"; exit(1); } } int main(int argc, char *argv[]) { printf("计算后缀表达式\n"); Compute(*argv); return 0; }