数据结构实验(代码加运行结果).doc

集合的差、并运算#include#includeconst int defaultSize=100;templateclass SeqListprotected:T *date;/存放数组int maxSize;int last;void reSize(int newSize);/改变数组空间大小public:SeqList(int sz=defaultSize);/构造函数SeqList(SeqList& L);/复制构造函数int Size()constreturn maxSize;/计算表最大可容纳表项个数int Length()constreturn last+1;/计算表长度int Search(T& x)const;/搜索x在表现中位置int Locate(int i)const;/定义第i个表项，函数返回表项序号bool getDate(int i,T& x)const/取第i个表项的值if (i0 & i0 & i=last+1)datei-1=x;bool Insert(int i,T& x);/插入x在第i个表项后bool Remove(int i,T& x);/删除第i个表项的值bool IsEmpty()return(last=-1)?true:false;/判空bool IsFull()return (last=maxSize-1)?true:false;/判满void input();/invoid output();/outSeqListoperator=(SeqList& L);/表整体赋值;template /构造函数SeqList:SeqList(int sz)if(sz0)maxSize=sz;last=-1;date=new TmaxSize;if(date=NULL)cerr存储分配出错！endl;exit(1);template/复制构造函数SeqList:SeqList(SeqList& L)maxSize=L.Size();last=L.Length()-1; T value;date=new TmaxSize;if (date=NULL)cerr存储分配出错！endl;exit(1);for (int i=1;i=last+1;i+)L.getDate(i,value);datei-1=value;template/改变date数组大小void SeqList:reSize(int newSize)if(newSize=0)cerr无效的数组大小endl;return;if(newSize!=maxSize)T* newarray=new TnewSize; if(newarray=NULL) cerr存储分配出错！endl;exit(1);int n=last+1;T *srcptr=date;T *destptr=newarray;while(n-)*destptr+=*srcptr+;delete date;date = newarray; maxSize= newSize;templateint SeqList:Search(T& x)const/搜索x在表项中位置，返回表项序号for(int i=0;i=last;i+)if(datei=x)return i+1;return 0;templateint SeqList:Locate(int i)const/定位第i个表项，返回表项序号if(i=1 & i=last+1)return i;else return 0;templatebool SeqList:Insert(int i, T& x)/插入x在第i个表项之后if(last=maxSize-1)return false;if(imaxSize-1)return false;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;j=last;j+)datej-i=datej;last-;return true;templatevoid SeqList:input()/从键盘输入数据，建立顺序表coutlast;if(last=maxSize-1)break;coutmaxSize-1:;for(int i=0;idatei;templatevoid SeqList:output()/输出循序表coutlastendl;for(int i=0;i=last;i+)cout#i+1:dateiendl;templateSeqListSeqList:operator=(SeqList& x)/重载操作，顺序表整体赋值;void Union ( SeqList & A, SeqList & B ) int n = A.Length ( ),x; int m = B.Length ( ); for ( int i = 1; i m; i+ ) B.getDate(i,x); /在B中取一元素 int k = A.Search (x); /在A中搜索它 if ( k = 0 ) /若未找到插入它 A.Insert (n, x); n+; void Intersection ( SeqList & A, SeqList & B ) int n = A.Length ( ); int m = B.Length ( ); int i = 1,x; while ( i n ) A.getDate(i,x); /在A中取一元素 int k = B.Search (x); /在B中搜索它if ( k = 0) A.Remove (i,x); n-; else i+; /未找到在A中删除它 int main() SeqListA(8); SeqListB(8); cout输入A表元素：endl; A.input(); cout输入B表元素：endl; B.input(); Union(A,B); A.output(); Intersection(A,B); A.output(); return 0; 算术表达式求值演示#include#includestdio.h#includestdlib.husing namespace std;#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(SqStack *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(theta) 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; i7; i+) if (s = TestOpi) Find= 1; return Find;int ReturnOpOrd(char op,char* TestOp) /确定运算符类型,op为待确定运算符，TestOp为已知的算符集合 int i; for(i=0; ibase;printf(Stack OPND:);if(!Empty(s) for(;itop);i+) coutdatai;elsecout base;printf(Stack OPTR:);for(;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(&OPND);InitStack(&OPTR);Push(&OPTR,#);gets(exp);ch=exp0;while(ch!=#|GetTop(&OPTR)!=#)if(!In(ch,OPSET)/不是运算符则进栈if(In(expi+1,OPSET)/未出现连续数字Push(&OPND,ch-48);ch=exp+i;/ifelse/出现连续数字s=expi+-48;while(expi=0&expi=9)s=s*10+expi+-48;Push(&OPND,s);s=0;ch=expi;elseswitch(precede(GetTop(&OPTR),ch)case :/退栈并将运算结果入栈theta=Pop(&OPTR);b=Pop(&OPND);a=Pop(&OPND);Push(&OPND,Operate(a,theta,b);break;/switch/whilereturn GetTop(&OPND);/EvaluateExpression_1void Change(char *s1,char *s2)/将中缀表达式转为后缀表达式SqStack OPTR;char ch;int i=0,sum=0;InitStack(&OPTR);Push(&OPTR,#);ch=s10;while(ch!=#|GetTop(&OPTR)!=#)if(!In(ch,OPSET)/不是运算符则进栈if(In(s1i+1,OPSET)/未出现连续数字Store(s2,ch);Store(s2, );/存入一个空格ch=s1+i;/ifelse/出现连续数字while(s1i=0&s1i=9)Store(s2,s1i);i+;/whileStore(s2, );/存入一个空格ch=s1i;/else/ifelseswitch(precede(GetTop(&OPTR),ch)case :/退栈并将运算结果入栈Store(s2,Pop(&OPTR);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,step=0;InitStack(&OPND);cout请输入一个中缀表达式endl;gets(receive);/输入中缀表达式Change(receive,exp);cout=0&expi=9)s=s*10+expi+-48;/whilePush(&OPND,s);s=0;ch=exp+i;/else/ifelse theta=ch;b=Pop(&OPND);a=Pop(&OPND);Push(&OPND,Operate(a,theta,b);i+=2;ch=expi;return GetTop(&OPND);/EvaluateExpression_2int main()char s=0,c;while(1)coutc;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 int 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(n=1) Error(Code too small!);m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT,i=0;iweight=*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;i=m;i+)min=Select(HT,i-1);s1=min.s1;s2=min.s2;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;printf(HT List:n);printf(Numberttweightttparentttlchildttrchildn);for(i=1;i=m;i+)printf(%dtt%dtt%dtt%dtt%dn,i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);HC=(HuffmanCode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char *);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char *);strcpy(HCi,&cdstart);free(cd);return HC;MinCode Select(HuffmanTree HT,unsigned int n)unsigned int min,secmin;unsigned int temp;unsigned int i,s1,s2,tempi;MinCode code;s1=1;s2=1;for(i=1;i=n;i+)if(HTi.parent=0)min=HTi.weight;s1=i;break;tempi=i+;for(;i=n;i+)if(HTi.weightmin&HTi.parent=0)min=HTi.weight;s1=i;for(i=tempi;i=n;i+)if(HTi.parent=0&i!=s1)secmin=HTi.weight;s2=i;break;for(i=1;i=n;i+)if(HTi.weights2)temp=s1;s1=s2;s2=temp;code.s1=s1;code.s2=s2;return code;void main()HuffmanTree HT=NULL;HuffmanCode HC=NULL;unsigned int *w=NULL;unsigned int i,n;cout请输入你要输入的字符个数 n:;scanf(%d,&n);w=(unsigned int *)malloc(n+1)*sizeof(unsigned int *);w0=0;printf(Enter weight:n);for(i=1;i=n;i+)coutwiwi;HC=HuffmanCoding(HT,HC,w,n);coutHuffmanCode:endl;coutNumber Weight Codeendl;for(i=1;i=n;i+)couti wi HCiendl;内部排序算法比较#include#include#include#includeusing namespace std;#define ARRAYLEN 10int move1=0,move2=0,move3=0,compare1=0,compare2=0,compare3=0;int creatdata(int arr,int n,int min,int max)/生成不重复随机函数int i,j,flag;srand(time(NULL);if (max-min+1)n) return 0;for(i=0;in;i+)doarri=(max-min+1)*rand()/(RAND_MAX+1)+min;flag=0;for(j=0;ji;j+)if(arri=arrj)flag=1;while(flag);return 1;int division(int a,int left,int right)/分割函数int base=aleft;while(leftright)while(leftbase)-right;aleft=aright;while(leftright&aleftbase)+left;aright=aleft;compare2=compare2+5;move2=move2+2;aleft=base;return left;void bubblesort(int