《数据结构实验(代码加运行结果)》由会员分享，可在线阅读，更多相关《数据结构实验(代码加运行结果)（20页珍藏版）》请在金锄头文库上搜索。
1、集合的差、并运算#include#includeconst int defaultSize=100;templateclass SeqListprotected:T *date; /存放数组int maxSize;int last;void reSize(int newSize); /改变数组空间大小public:SeqList(int sz=defaultSize); /构造函数SeqList(SeqList /复制构造函数int Size()constreturn maxSize; /计算表最大可容纳表项个数int Length()constreturn last+1; /计算表长度int
2、 Search(T /搜索 x 在表现中位置int Locate(int i)const; /定义第 i 个表项，函数返回表项序号bool getDate(int i,T& x)const /取第 i 个表项的值if (i0 void setDate(int i,T& x) /修改第 i 个表项的值if (i0 bool Insert(int i,T /插入 x 在第 i 个表项后bool Remove(int i,T /删除第 i 个表项的值bool IsEmpty()return(last=-1)?true:false; /判空bool IsFull()return (last=maxSi
3、ze-1)?true:false; /判满void input(); /invoid output(); /outSeqListoperator=(SeqList /表整体赋值;template /构造函数SeqList:SeqList(int sz)if(sz0)maxSize=sz;last=-1;date=new TmaxSize;if(date=NULL)cerr /复制构造函数SeqList:SeqList(SeqList& L)maxSize=L.Size();last=L.Length()-1; T value;date=new TmaxSize;if (date=NULL)ce
4、rr /改变 date 数组大小void SeqList:reSize(int newSize)if(newSizeint SeqList:Search(T& x)const /搜索 x 在表项中位置，返回表项序号for(int i=0;iint SeqList:Locate(int i)const /定位第 i 个表项，返回表项序号if(i=1 else return 0;templatebool SeqList:Insert(int i, T& x) /插入 x 在第 i 个表项之后if(last=maxSize-1)return false;if(imaxSize-1)return fa
5、lse;for(int j=last;j=i;j-)datej+1=datej;datei=x;last+;return true;templatebool SeqList:Remove(int i,T& x) /删除第 i 个表项，并返回表项的值if(last=-1)return false;if(ilast+1)return false;x=datei-1;for(int j=i;jvoid SeqList:input() /从键盘输入数据，建立顺序表coutlast;if(lastdatei;templatevoid SeqList:output() /输出循序表coutSeqListS
6、eqList:operator=(SeqList& x) /重载操作，顺序表整体赋值;void Union ( SeqList & A,SeqList & B ) int n = A.Length ( ),x;int m = B.Length ( );for ( int i = 1; i & A,SeqList & B ) int n = A.Length ( );int m = B.Length ( ); int i = 1,x;while ( i A(8);SeqListB(8);cout#includestdio.h#includestdlib.husing namespace std;
7、#define SIZE 80#define OK 1#define ERROR 0typedef struct /定义栈int dataSIZE;int top;int base;SqStack;char OPSET7=+ , - , * , / ,( , ) , #;/定义 OPSET 字符数组为算符集合char Prior77 = / 算符间的优先关系, ,top=s-base)return ERROR;return (s-datas-top-1);void Push(SqStack *s,int e)/插入 e 为新的栈顶元素s-datas-top=e;s-top+;int Pop(S
8、qStack *s)/若栈不空，则删除之，并返回其值；否则返回 REEORint e;if(s-base=s-top)return ERROR;elsee=s-datas-top-1;s-top-;return e;void InitStack(SqStack *s)/置栈 S 为空s-top=0;s-base=0;int Empty(SqStack *s)/判定 s 是否为空栈if(s-base=s-top)return 1;elsereturn 0;int Operate(int a,char theta, int b) /返回 a 与 b 间 theta 运算的结果switch(thet
9、a) case +: return a+b;break;case -: return a-b;break; case *: return a*b;break;case /: return a/b;break;default : return 0; int In(char s,char* TestOp) /s 为待判断字符， TestOp 为已知的算符集合int Find=0;for (int i=0; ibase;printf(Stack OPND:);if(!Empty(s)for(;itop);i+)coutdatai;elsecoutbase;printf(Stack OPTR:);fo
10、r(;itop);i+)coutdatai;void Store(char *s,char ch)/将 ch 存入数组 schar *p=s;while(*p)p+;*p+=ch;int EvaluateExpression_1()/中缀求值SqStack OPND,OPTR;char ch,theta,exp100=0;int i=0,s=0,a=0,b=0,step=0;InitStack(InitStack(Push(gets(exp);ch=exp0;while(ch!=#|GetTop(&OPTR)!=#)if(!In(ch,OPSET)/不是运算符则进栈if(In(expi+1,O
11、PSET)/未出现连续数字Push(ch=exp+i;/ifelse/出现连续数字s=expi+-48;while(expi=0&expi:/退栈并将运算结果入栈theta=Pop(b=Pop(a=Pop(Push(break;/switch/whilereturn GetTop(/EvaluateExpression_1void Change(char *s1,char *s2)/将中缀表达式转为后缀表达式SqStack OPTR;char ch;int i=0,sum=0;InitStack(Push(ch=s10;while(ch!=#|GetTop(&OPTR)!=#)if(!In(c
12、h,OPSET)/不是运算符则进栈if(In(s1i+1,OPSET)/未出现连续数字Store(s2,ch);Store(s2, );/存入一个空格ch=s1+i;/ifelse/出现连续数字while(s1i=0&s1i:/退栈并将运算结果入栈Store(s2,Pop(Store(s2, );/补入一个空格作为间隔break;/switch/whileStore(s2,ch);/Changeint EvaluateExpression_2()/后缀求值SqStack OPND;char ch,theta,receive100=0,exp100=0;int i=0,s=0,a=0,b=0,s
13、tep=0;InitStack(cout=0&expic;cins;if(s=q|s=Q)exit(0);while(s!=n);system(cls);return 0;哈弗曼编/译码器#include #include #include #include #include using namespace std;typedef struct unsigned int weight;unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;typedef char *HuffmanCode;typedef struct unsigned i
14、nt s1;unsigned int s2; MinCode;void Error(char *message);HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);MinCode Select(HuffmanTree HT,unsigned int n);void Error(char *message)fprintf(stderr,Error:%sn,message);exit(1);HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n)unsigned int i,s1=0,s2=0;HuffmanTree p;char *cd;unsigned int f,c,start,m;MinCode min;if(nweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;is2)temp=s1;s1=s2;s2=temp;code.s1=s1;code.s2=s2;return code;nt
