川师-数学院-数据结构试验报告资料

四川师范大学数学与软件科学学院实验报告课程名称：数据结构（C语言版）指导老师：冯山实验项目实验名称学时成绩实验一ADT的类C描述向C程序的转换实验2学时实验二线性表及其基本操作实验2学时实验三栈和队列实验6学时实验四字符串实验2学时实验五稀疏矩阵的三元组实现实验4学时实验六二叉树的基本算法实验4学时实验七Huffman树与Huffman树编码算法实验4学时实验八图的建立与遍历算法实验4学时实验九内部排序算法实验4学时实验十查找实验2学时班级：2009级6班学号：2009060630姓名：总成绩：________实验一：ADT的类C描述向C程序的转换实验(2学时)实验目的：(1)复习C语言的基本用法；(2)学会用类C的语言对算法进行描述的方法，将类C算法转换成C源程序的方法和过程；(3)抽象数据类型的定义和表示、实现；(4)加深对数据的逻辑结构和物理结构之间关系的理解；(5)初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现)(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果；实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.安装TC并设置好环境，如果已安装好，可以跳过此步；2.录入程序代码并进行调试和算法分析；对实验内容(1)的操作步骤：1)用类C语言描述算法过程；2)用C语言环境实现该算法。对实验内容(2)的操作步骤：1)完成算法的C实现；2)分析其时间复杂度和空间复杂度。3.编写实验报告。实验结果：//动态分配数组空间#include"stdio.h"#include"malloc.h"intsize,i;int*pArray;int*p;voidmalloc_size(){ pArray=(int*)malloc(size*(sizeof(int)));}intinput_size(){ printf("pleaseinputthesize:\n"); printf("size="); scanf("%d",&size); return0;}intinput_data(){ printf("pleaseinputthevalue:\n"); for(i=0;i<size;i++) { printf("pArray[%d]=",i); scanf("%d",&pArray[i]); } return*pArray;}intCompare(){ intx,y,i; x=y=p[0]; for(i=0;i<size;i++) { if(x>=p[i])x=p[i]; if(y<=p[i])y=p[i]; } printf("min=%d\tmax=%d\n",x,y); return0;}intOutput_data(){ p=pArray; printf("beforeofpaixu:\n"); for(i=0;i<size;i++) { printf("%d\t",*pArray); pArray++; } printf("\n"); return*pArray;}voidpaixu(){ intx=0; inti,j; printf("laterofpaixu:\n"); for(i=0;i<size;i++) { for(j=i+1;j<size;j++) { if(p[i]>=p[j]) { x=p[i];p[i]=p[j];p[j]=x; } } printf("%d\t",p[i]); } printf("\n");}voidmain(){ clrscr(); input_size(); malloc_size(); input_data(); Output_data(); Compare(); paixu();}实验结果：实验二线性表及其基本操作实验(2学时)实验目的：(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；(3)掌握线性表的顺序存储结构和动态存储结构之区分。实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算；实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：//线性链表#include"malloc.h"#include"stdio.h"#defineM6typedefstructnode{ intdata;structnode*next;}*Sqlist;voidInitlialize(Sqlist&L){ L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL;}intGetlength(SqlistL){ inti=0; Sqlistp=L->next; while(p!=NULL) {i++;p=p->next; }returni;}intGetelem(SqlistL,inti){intj=1,e; Sqlistp=L->next; while(j<i) {p=p->next;j++; }e=p->data; printf("第%d个元素是：%d\n",i,e); return1;}intLocatelem(SqlistL,intx){inti=0; Sqlistp=L->next; while(p!=NULL&&p->data!=x) { p=p->next;i++; } if(p==NULL) return0; else { printf("%d是第%d个元素\n",x,i); returni; }}voidCreatlistF(Sqlist&L,inta[],intn)//头插法{//从一个空表开始，读取字符数组a中字符生成新结点，将读取数据存放到新结点数据域，//再将新结点插入当前链表表头、直至结束 Sqlists; inti; L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL; for(i=0;i<n;i++) { s=(Sqlist)malloc(sizeof(Sqlist)); s->data=a[i];s->next=L->next; L->next=s; }}voidCreatlistR(Sqlist&L,inta[],intn)//尾插法{//将新结点插到当前链表表尾，为此必须新增一个尾指针r,使其始终指向当前链表的尾结点Sqlists,r; inti; L=(Sqlist)malloc(sizeof(Sqlist)); L->next=NULL; r=L; for(i=0;i<n;i++) { s=(Sqlist)malloc(sizeof(Sqlist)); s->data=a[i];s->next=NULL; r->next=s;r=s; }}intInselem(Sqlist&L,inti,intx){//1、将所建新结点s的next域指向p的下一结点：s->next=p->next//2、将结点p的next域指向新结点s：p->next=s intj=1; Sqlists,p=L->next; s=(Sqlist)malloc(sizeof(Sqlist)); s->data=x;s->next=NULL; if(i<1||i>Getlength(L)) return0; while(j<i-1) { p=p->next; j++; } printf("在第%d个位置插入数据：%d\n",i,x); s->next=p->next;p->next=s; return1;}intDelelem(Sqlist&L,inti){intj=1;Sqlistp,q;p=L;if(i<1||i>Getlength(L)) return0;while(j<i){ p=p->next;j++;}q=p->next;p->next=q->next;free(q);return1;}voidDisplist(SqlistL){Sqlistp=L->next; while(p!=NULL) { printf("%d\t",p->data); p=p->next; } printf(“\n”);}voidinput(int*pArray,intn){printf("请输入数组数据(共含%d个元):\n",n);for(inti=0;i<n;i++)Scanf(“%d”,&pArray[i]);intmain(intargc,char*argv[]){ SqlistL;intArray[M],Select; Initlialize(L); do{ printf("请输入选择方法（1表示头插法，2表示尾插法,0表示结束）：\n");scanf("%d",&Select);switch(Select) { case1:printf("按头插法建立线性表:\n");input(Array,M);CreatlistF(L,Array,M);break; case2:printf("按尾插法建立线性表:\n");input(Array,M);CreatlistR(L,Array,M);break; } printf("原线性表数据为:\n"); Displist(L); Getelem(L,3);Locatelem(L,2);Inselem(L,5,5);printf("修改后的线性表数据为:\n");// Delelem(L,4);Displist(L); }while(Select!=0); return0;}//运行结果:实验三栈和队列实验(6学时)实验目的：(1)熟练掌握栈和队列的抽象数据类型及其结构特点；(2)实现基本的栈和队列的基本操作算法程序。实验内容：(类C算法的程序实现，任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)；(2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）；实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：（1）/*队列存储*/#include"stdio.h"typedefintstatus;#defineQueueSize10typedefstructsqqueue{ chardata[QueueSize]; intfront,rear;}SqQueue;voidInitQueue(SqQueue&qu){ qu.front=qu.rear=0;}statusEnQueue(SqQueue&qu,charx){if((qu.rear+1)%QueueSize==qu.front) return0; qu.rear=(qu.rear+1)%QueueSize; qu.data[qu.rear]=x; return1;}statusDeQueue(SqQueue&qu,char&x){ if(qu.rear==qu.front) return0; qu.front=(qu.front+1)%QueueSize; x=qu.data[qu.front]; return1;}statusGetHead(SqQueuequ,char&x){ if(qu.rear==qu.front) return0; x=qu.data[(qu.front+1)%QueueSize]; return1;}statusQueueEmpty(SqQueuequ){ if(qu.rear==qu.front) return1; else return0;}voidmain(){SqQueuequ; chare; InitQueue(qu);printf("Queue%s\n",(QueueEmpty(qu)==1"Empty":"NotEmpty"));printf("insera\n");EnQueue(qu,'a');printf("inserb\n");EnQueue(qu,'b');printf("inserc\n");EnQueue(qu,'c');printf("inserd\n");EnQueue(qu,'d');printf("Queue%s\n",(QueueEmpty(qu)==1"Empty":"NotEmpty"));GetHead(qu,e);printf("Queueoftopelemis:%c\n",e);printf("showofQueue:\n");while(!QueueEmpty(qu)) { DeQueue(qu,e); printf("%c\t",e); }printf("\n");}实验结果：（2）/*用栈实现对表达式的求值运算*/#include"stdio.h"#include"malloc.h"#include"stdlib.h"/*数据类型转换库函数*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSTACK_INIT_SIZE100/*初始分配量*/#defineSTACKINCREMENT10/*存储空间的分配增量*/typedefintStatus;typedefcharElemType;typedefElemTypeOperandType;/*操作数*/typedefcharOperatorType;typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){/*构造一个空栈S*/S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);/*存储空间失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}/*InitStack*/StatusGetTop(SqStackS){ /*若栈不空，则用e返回S的栈顶元素*/ElemTypee;if(S.top==S.base)returnERROR;e=*(S.top-1);returne;}/*GetTop*/StatusPush(SqStack&S,ElemTypee)/*插入元素e为新的栈顶元素*/{if(S.top-S.base>=S.stacksize){ /*栈满，追加存储空间*/S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);/*存储空间失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}/*Push*/StatusPop(SqStack&S,ElemType&e)/*取栈顶元素，用e返回*/{/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}/*Pop*/charIn(charc,charOP[])/*判断字符c是否属于运算符*/{if(c>=35&&c<=47)return1; /*常见操作符（如：'#'、'（'、'）'、'+'、'-'、'*'、'\'等）的ASCII码在35到47之间*/elsereturn0;}charOP[8]={'+','-','*','/','(',')','#','\0'};/*定义有所要用到的操作符构成的数组OP[8]*/intm[7][7]={1,1,2,2,2,1,1,1,1,2,2,2,1,1,1,1,1,1,2,1,1,1,1,1,1,2,1,1,2,2,2,2,2,0,-1,1,1,1,1,-1,1,1,2,2,2,2,2,-1,0};/*各运算符间优先级别的关系*//*以上：1表示‘>’；2表示‘<’；0表示‘=’；-1表示‘不存在’*/charPrecede(chari,charj)/*比较数组OP[]中字符i与数组OP中字符j的优先权*/{inta,b;char*p;for(p=OP,a=0;*p!='\0';p++,a++)if(*p==i)break;for(p=OP,b=0;*p!='\0';p++,b++)if(*p==j)break;if(m[a][b]==1)return'>';elseif(m[a][b]==2)return'<';elseif(m[a][b]==0)return'=';elsereturn'O';}charOperate(chara,chartheta,charb)/*对运算数a、b按操作符theta进行二元运算*/{if(a>47)a=atoi(&a);/*将字符数转化为整型数*/if(b>47)b=atoi(&b);switch(theta) {case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':returna/b;break; }return'1';}OperandTypeEvaluateExpression()/*算术表达式求值的算符优先算法*/{SqStackOPTR,OPND;/*设OPTR、OPND分别运算符栈和运算数栈*/OperandTypea,b,c;OperatorTypetheta;InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();while(c!='#'||GetTop(OPTR)!='#') {if(!In(c,OP)){Push(OPND,c);c=getchar();}elseswitch(Precede(GetTop(OPTR),c)) {case'<':Push(OPTR,c);c=getchar();break;case'=':Pop(OPTR,c);c=getchar();break;case'>':Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b));break; } }returnGetTop(OPND);}intmain(){printf("(请输入运算表达式：以#为结束符)\n");inta;a=(int)EvaluateExpression();/*执行函数EvaluateExpression()，将表达式的最终值强制转换为整型，并用a返回*/printf("%d",a);getchar();return0;}测试结果为：①表达式中包含+、-、*的情况；②表达式中包含（）、+、-、*的情况；③表达式中包含（）、+、-、*、/的情况；④表达式中出现负数的情况；实验四字符串实验(2学时)实验目的：掌握有关字符串的基本操作和存储结构，并编写相应的基本操作算法。实验内容：(类C算法的程序实现，任选其二)(1)求字符串的长度算法(必做)；(2)求字符串的子串算法(选做)；(3)字符串的合并算法(选做)；(4)字符串的置换算法(选做)；(5)字符串的插入算法(选做)。实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：#include"malloc.h"#include"stdio.h"typedefintStatus;typedefstructnode{ charch[5];//存放串字符 intlen;//存放串的实际长度}Sqstring;//顺序串类型//串赋值运算算法SqstringStrAssign(Sqstring&s,charch[])//将一个字符数组ch[]赋给串s{inti=0; while(ch[i]!='\0') {s.ch[i]=ch[i]; i++; } s.len=i; returns;}//求串长运算算法StatusStrlength(Sqstrings){returns.len;}//判断算法相等算法StatusStrCompare(Sqstrings,Sqstringt){ if(s.len!=t.len) return0; else for(inti=0;i<s.len;i++) { if(s.ch[i]!=t.ch[i]) { printf("这两个字符串是不相等的\n"); return0; } else { printf("这两个字符串是相等的\n"); return1; } }return1;}//串复制算法StatusStrCopy(Sqstring&s,Sqstringt)//将串t赋给串s{ for(inti=0;i<t.len;i++) { s.ch[i]=t.ch[i]; } s.len=t.len; return0;}//串连接算法SqstringConcat(Sqstring&s,Sqstringt)//将串t连接到串s之后，返回连接后的结果串{Sqstringr; inti,j; for(i=0;i<s.len;i++)//将s复制给r r.ch[i]=s.ch[i]; for(j=0;j<t.len;j++)//将t复制给r r.ch[s.len+j]=t.ch[j]; r.len=i+j; returnr;//返回r}//求字串运算算法SqstringSubStr(Sqstrings,inti,intj)//将从串s的第i个位置取的j个字符以字符串形式返回{ Sqstringt;printf("由A中第%d个字符开始的%d个字符构成的",i,j); if(i<1||i>s.len||j<1||i+j>s.len+1) t.len=0; else { for(intk=i+-1;k<i+j;k++) t.ch[k-i+1]=s.ch[k]; t.len=j; } returnt;}//查找字串位置运算算法intIndex(Sqstring&s,Sqstringt)//返回字串t在主串s中的位置，若不在s中返回0{inti=0,j=0,k; while(i<s.len&&j<t.len) { if(s.ch[i]==t.ch[j])//对应字符相同，继续比较下一个字符 { i++; j++; } else//否则，从主串开头从新开始下一次匹配 { i=i-j+1; j=0; } } printf("1：表示能找到相匹配的字符串，0：表示没有找到相匹配的字符串\n查找结果为\n"); if(j>=t.len) { k=i-t.len+1;//求出第一个字符的位置 printf("%d\n",k); } else { k=0; printf("%d\n",k); } returnk;}//字串插入运算算法intInsStr(Sqstring&s,inti,Sqstringt)//将字串t插入串s中{ intj; printf("在字符串A的第%d个字符处插入字符串B后",i); if(i>s.len+1) return0; else { for(j=s.len;j>i-2;j--)//将s.ch[i-1]--s.ch[s.len-1]后移t.len个位置 s.ch[j+t.len]=s.ch[j]; for(j=0;j<t.len;j++) s.ch[i+j-1]=t.ch[j]; s.len=s.len+t.len;//修改s的长度 return1; }}//字串删除运算算法StatusDelStr(Sqstring&s,inti,intj){ intk; printf("删出A中第%d个字符开始的%d个字符后构成的",i,j); if(i<1||i>s.len||j<1||j>s.len+1) return0; else { for(k=i+j-1;k<s.len;k++)//将s.ch[i+j-1]--s.ch[s.len-1]前移j位 s.ch[k-j]=s.ch[k]; s.len=s.len-j;//修改s的长度 return1; }}//字串替换算法SqstringRepStr(Sqstrings,Sqstrings1,Sqstrings2)//将s中所有出现的字串s1均替换为字串s2{ inti; i=Index(s,s1); while(i>=0) { DelStr(s,i,s1.len);//删除 InsStr(s,i,s2);//插入 i=Index(s,s1); } returns;}//输出串运算算法voidDispStr(Sqstrings,chara){ inti; printf("字符串%c为：\n",a); for(i=0;i<s.len;i++) printf("%c\t",s.ch[i]); printf("\n");}//主函数intmain(){ SqstringA,B,C,D,E,F,G; charArray[5]={'a','b','c','d','\0'}; charBrray[5]={'e','f','g','h','\0'}; charCrray[3]={'c','d','\0'};StrAssign(A,Array); DispStr(A,'A'); StrAssign(B,Brray); DispStr(B,'B'); StrAssign(E,Brray); DispStr(E,'E');StrCompare(A,B);//比较两字符串 printf("将字符串B连接到字符串A后的");F=Concat(A,B);DispStr(F,'F');//将字符串s1连接到s字符串中 printf("将字符串B复制到字符串A后的");StrCopy(A,B);DispStr(A,'A');//将字符串s1复制到s字符串中D=SubStr(A,2,3);DispStr(D,'D');Index(A,E);DelStr(A,3,2);DispStr(A,'A'); return0;}测试结果为：实验五稀疏矩阵的三元组实现实验(4学时)实验目的：掌握稀疏矩阵的三元组表示方法、算法实现。实验内容：(类C算法的程序实现，任选其二)(1)基于三元组的稀疏矩阵表示与输入、输出方法(必做)；(2)基于三元组的稀疏矩阵加法(选做)；(3)基于三元组表示的稀疏矩阵转置(选做)；实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：#include"stdio.h"#defineMaxsize100#defineM6#defineN6typedefstruct{ intr;//行号 intc;//列号 intd;//元素值}TupNode;typedefstruct{ introws;//行数值intcols;//列数值 intnums;//非零元素个数 TupNodedata[Maxsize];}TSMatrix;//三元组顺序表定义//从一个二维矩阵创建其三元组表示的运算算法voidCreatMat(TSMatrix&t,intA[M][N]){ inti,j; t.rows=M; t.cols=N; t.nums=0; for(i=0;i<M;i++) { for(j=0;j<N;j++) { if(A[i][j]!=0)//只存储非0元 { t.data[t.nums].r=i; t.data[t.nums].c=j; t.data[t.nums].d=A[i][j]; t.nums++; } } }}//三元组元素赋值运算算法intValue(TSMatrix&t,intx,intrs,intcs){ inti,k; if(rs>=t.rows||cs>=t.cols) return0; while(k<t.nums&&rs>t.data[k].r)k++;//寻找位置 while(k<t.nums&&cs>t.data[k].c)k++; if(t.data[k].r==rs&&t.data[k].c==cs) t.data[k].d=x;//该元素存在 else//该元素不存在 { for(i=k;i<=t.nums;i++)//将i后面的元素后移 { t.data[i+1].r=t.data[i].r; t.data[i+1].c=t.data[i].c; t.data[i+1].d=t.data[i].d; } t.data[k].r=rs; t.data[k].c=cs; t.data[k].d=x; t.nums++; } return1;}//将指定位置的元素赋给变量的运算算法intAssign(TSMatrixt,int&x,intrs,intcs){ intk=0; if(rs>=t.rows||cs>=t.cols) return0; while(k<t.nums&&rs>t.data[k].r)k++; while(k<t.nums&&cs>t.data[k].c)k++; if(t.data[k].r==rs&&t.data[k].c==cs) { x=t.data[k].d; printf("第%d行第%d列的元素为：x=%d\n",rs,cs,x); returnx; } elsereturn0;}//输出三元组运算算法intDispMat(TSMatrixt){ inti; if(t.nums<=0) return0; printf("\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("------------------------------------\n"); for(i=0;i<t.nums;i++) printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d); return1;}//矩阵转置算法voidTsanTat(TSMatrixt,TSMatrix&tb){ intp,q=0,v; tb.rows=t.cols;; tb.cols=t.rows; tb.nums=t.nums; if(t.nums!=0) { for(v=0;v<t.cols;v++) { for(p=0;p<t.nums;p++) { if(t.data[p].c==v) { tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++; } } } }}//两矩阵相加运算算法intMatAdd(TSMatrixa,TSMatrixb,TSMatrix&c){ inti=0,j=0,k=0; chare; if(a.rows!=b.rows||a.cols!=b.cols) { printf("这两矩阵不能相加：\n"); return0; } c.rows=a.rows;c.cols=a.cols; while(i<a.nums&&j<b.nums) { if(a.data[i].r==b.data[j].r) { if(a.data[i].c<b.data[j].c) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; } elseif(a.data[i].c>b.data[j].c) { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++; j++; } else { e=a.data[i].d+b.data[j].d; if(e!=0) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=e; k++; } i++;j++; } }elseif(a.data[k].r<b.data[j].r) { c.data[k].r=a.data[i].r; c.data[k].c=a.data[i].c; c.data[k].d=a.data[i].d; k++;i++; }else { c.data[k].r=b.data[j].r; c.data[k].c=b.data[j].c; c.data[k].d=b.data[j].d; k++;j++; } c.nums=k; }return1;}intmain()//主函数{ TSMatrixt,tb,tp; inte; intArray[M][N]={0,0,1,0,0,0, 0,2,0,0,0,0, 3,0,0,0,0,0, 0,0,0,5,0,0, 0,0,0,0,6,0, 0,0,0,0,0,7}; CreatMat(t,Array); printf("该稀疏矩阵为：\n"); DispMat(t); Assign(t,e,0,2);//查找元素 TsanTat(t,tb); printf("转置后的矩阵为：\n"); DispMat(tb);MatAdd(t,tb,tp); printf("两矩阵相加后所得矩阵为：\n");DispMat(tp); return0;}测试结果：实验六二叉树的基本算法实验(4学时)实验目的：(1)掌握树和二叉树的基本概念和顺序与链式存储结构；(2)重点掌握二叉树的生成、遍历等算法；(3)掌握二叉树的线索化及基于线索二叉树的遍历算法。实验内容：(类C算法的程序实现)(1)二叉树的基本算法描述及实现（二叉树的建立、输出、插入等算法）(必做)(2)二叉树的先序、后序、中序遍历(必做)实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析2.编写实验报告实验结果：#include"stdio.h"#include"malloc.h"#defineMaxSize20typedefstructtnode{ intdata; structtnode*lchild,*rchild;}BTNode;//建立二叉树运算算法voidCreatBTree(BTNode*&bt,char*str){ BTNode*St[MaxSize],*p=NULL; inttop=-1,k,j=0;charch; bt=NULL;//建立的二叉树初始化时为空 ch=str[0]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break;//为左孩子结点 case')':top--;break; case',':k=2;break;//为右孩子结点 default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL)//p为二叉树的根结点 bt=p; else//已建立二叉树根结点 { switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++;ch=str[j]; }}//求二叉树高度运算算法(递归法)intBTHeight(BTNode*bt){ intlchilddep,rchilddep; if(bt==NULL)//空树高度为0 return0; else { lchilddep=BTHeight(bt->lchild);//求左子树的高度 rchilddep=BTHeight(bt->rchild);//求右子树的高度 return(lchilddep>rchilddep)(lchilddep+1):(rchilddep+1); }}//求二叉树结点个数运算算法(递归法)intNodeCount(BTNode*bt){ intnum1,num2; if(bt==NULL)//空树结点个数为0 return0; else { num1=NodeCount(bt->lchild);//求出左子树的结点树 num2=NodeCount(bt->rchild);//求出右子树的结点树 return(num1+num2+1); }}//求二叉树叶子结点个数运算算法(递归法)intLeafCount(BTNode*bt){ intnum1,num2; if(bt==NULL) return0;//空树叶子结点个数为0 elseif(bt->lchild==NULL&&bt->rchild==NULL) return1;//若为叶子结点返回1 else { num1=LeafCount(bt->lchild);//求出左子树的叶子结点树 num2=LeafCount(bt->rchild);//求出右子树的叶子结点树 returnnum1+num2; }}//以括号表示法输出二叉树运算算法(递归法)voidDispBTree(BTNode*bt){ if(bt!=NULL) { printf("%c",bt->data); if(bt->lchild!=NULL||bt->rchild!=NULL) { printf("("); DispBTree(bt->lchild);//以递归法处理左子树 if(bt->rchild!=NULL) printf(","); DispBTree(bt->rchild);//以递归法处理右子树 printf(")"); } }}//先序遍历voidPreOrder(BTNode*bt){ if(bt!=NULL) { printf("%c",bt->data); PreOrder(bt->lchild);PreOrder(bt->rchild); }}//中序遍历voidInOrder(BTNode*bt){ if(bt!=NULL) { InOrder(bt->lchild); printf("%c",bt->data);InOrder(bt->rchild); }}//后序遍历voidPostOrder(BTNode*bt){ if(bt!=NULL) { PostOrder(bt->lchild);PostOrder(bt->rchild); printf("%c",bt->data); }}intmain()//主函数{BTNode*bt; CreatBTree(bt,"A(B(D,E(G,H),C(,F(I)))"); printf("二叉数bt以括号法显示为:");DispBTree(bt);printf("\n"); printf("先序发遍历二叉数bt为:");PreOrder(bt); printf("\n"); printf("中序发遍历二叉数bt为:");InOrder(bt); printf("\n"); printf("后序发遍历二叉数bt为:");PostOrder(bt); printf("\n"); printf("二叉数bt的高度为：%d\n",BTHeight(bt)); printf("二叉数bt的结点数为：%d\n",NodeCount(bt)); printf("二叉数bt的叶子结点数为：%d\n",LeafCount(bt)); printf("\n"); return0;}测试结果为：实验七Huffman树与Huffman树编码算法实验(4学时)*实验目的：掌握Huffman树的编码方法和算法实现。实验内容：(类C算法的程序实现)(1)建立Huffman树编码的表示结构，对给定输入信息集合进行Huffman编码，输出编码结果(必做)(2)利用Huffman编码算法实现给定信息串的编码结果(必做)实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：//HuffmanTree及其编码#include"malloc.h"#include<iostream>#include"stdio.h"typedefstruct{unsigned intweight;unsigned intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;constintMaxsize=100;intSearch(chardifchar[],intn,chare) //查询此e字符是否已出现{ for(inti=1;i<=n;i++) if(difchar[i]==e) returni; return0;}intstat(chardata[],chardifchar[],intw[])//计算相应字符出现的频率{ intj=0,i,length=strlen(data); inttemp; for(i=0;i<length;i++) { temp=Search(difchar,j,data[i]); if(temp==0) { difchar[++j]=data[i]; w[j]=0; } else w[temp]++; } returnj;}intGetmin(HuffmanTreeT,intn) //返回n个结点中权值最小的且没有父亲结点的结点序号{ inti=1,flag,j; while(T[i].parent!=0) i++; flag=i,j=T[i].weight;//flag为T中第一个没有父亲结点的结点序号 for(i++;i<=n;i++) if(T[i].weight<j&&T[i].parent==0) { j=T[i].weight; flag=i; } T[flag].parent=1; returnflag;}voidSelect(HuffmanTreeT,inti,int&s1,int&s2)//在i个结点中选择2个权值最小的树的根结点序号{ intj; s1=Getmin(T,i); s2=Getmin(T,i); if(T[s1].weight>T[s2].weight) { j=s1;s1=s2;s2=j; }}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值，构造Huffman树HT，并求出n个字符的Huffman编码HCints1,s2,start,m,i;unsignedintc,f;char*cd;HuffmanTreep;if(n<=1)return;m=2*n-1;//结点的总数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//结点0空for(p=HT+1,i=1;i<=n;i++,p++,w++){p->weight=*w;(*p).parent=(*p).lchild=(*p).rchild=0;}for(;i<=m;i++,p++)(*p).parent=0;for(i=n+1;i<=m;i++){Select(HT,i-1,s1,s2);//寻找权值最小的二棵子树HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}intmain(){ HuffmanTreeHT;HuffmanCodeHC;intn=0,i;//n表示输入文字中不同字符的个数chardata[Maxsize];chardifchar[Maxsize],temp;intw[Maxsize];printf("=====-请输入预编码的文字-=====\n");printf("仅限英文字符，输入#结束输入\n"); for(intj=0;j<Maxsize;j++) { scanf("%c",&temp); if(temp!='#') data[j]=temp; else {n=stat(data,difchar,w);HuffmanCoding(HT,HC,w+1,n);printf("=============字符与相应编码为=============\n");for(i=1;i<n;i++)printf("%c:,%s\n",difchar[i],HC[i]); printf("\n===============编码文字===============\n");for(i=0;i<n-1;i++)printf("%s\t",HC[Search(difchar,n,data[i])]);printf("\n"); }} return0;}实验结果：①②实验八图的建立与遍历算法实验(4学时)*实验目的：(1)熟练掌握图的邻接矩阵和邻接表的存储方式；(2)实现一些基本的图的运算算法(如图的遍历)；(3)掌握常见算法如最小生成树、Top排序树、关键路径、最短路径等应用算法。实验内容：(类C算法的程序实现，任选其二)(1)图的基本存储结构和运算算法的实现(必做)；(2)图的遍历算法的实现(选做)；(3)最小生成树的生成算法实现(选做)；(4)Top排序树的算法实现(选做)；(5)关键路径算法的实现(选做)；(6)最短路径算法的实现(选做)。实验准备：1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：1.录入程序代码并进行调试和算法分析；2.编写实验报告。实验结果：//图深度优先遍历算法—邻接矩阵#include<stdio.h>#include<malloc.h>#defineINFINITY32767#defineMAX_VEX20//最大顶点个数bool*visited;//访问标志数组//图的邻接矩阵存储结构typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;//图G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==c)returni;return-1;}//创建无向网voidCreateUDN(Graph&G){inti,j,w,s1,s2;chara,b,temp;printf("输入顶点数和弧数:");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf("输入%d个顶点.\n",G.vexnum);for(i=0;i<G.vexnum;i++){//初始化顶点printf("输入顶点%d:",i);scanf("%c",&G.vexs[i]);temp=getchar();//接收回车}for(i=0;i<G.vexnum;i++)//初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.\n",G.arcnum);for(i=0;i<G.arcnum;i++){//初始化弧printf("输入弧%d:",i);scanf("%c%c%d",&a,&b,&w);//输入一条边依附的顶点和权值temp=getchar();//接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//图G中顶点k的第一个邻接顶点intFirstVex(GraphG,intk){if(k>=0&&k<G.vexnum){//k合理for(inti=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY)returni;}return-1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点intNextVex(GraphG,inti,intj){if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum){//i,j合理for(intk=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY)returnk;}return-1;}//深度优先遍历voidDFS(GraphG,intk){inti;if(k==-1){//第一次执行DFS时,k为-1for(i=0;i<G.vexnum;i++)if(!visited[i])DFS(G,i);//对尚未访问的顶点调用DFS}else{visited[k]=true;printf("%c",G.vexs[k]);//访问第k个顶点for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS}}//主函数voidmain(){inti;GraphG;CreateUDN(G);visited=(bool*)malloc(G.vexnum*sizeof(bool));printf("\n深度优先遍历:");for(i=0;i<G.vexnum;i++)visited[i]=false;DFS(G,-1);printf("\n程序结束.\n");}实验结果：//最短路径：/*用邻接矩阵表示的图的Dijkstra算法的源程序*/#include"stdafx.h"#include<stdio.h>#defineMAXVEX100#defineMAX1e+8typedefcharVexType;typedeffloatAdjType;typedefstruct{intn;/*n为图中顶点个数*/VexTypevexs[MAXVEX];/*顶点信息*/AdjTypearcs[MAXVEX][MAXVEX];/*边信息*/}GraphMatrix;typedefstruct{VexTypevertex;/*顶点信息*/AdjTypelength;/*最短路径长度*/intprevex;/*从v0到达vi(i=1,2,…n-1)的最短路径上vi的前趋顶点*/}Path;Pathdist[6];voidinit(GraphMatrix*pgraph,Pathdist[]){inti;dist[0].length=0;dist[0].prevex=0;dist[0].vertex=pgraph->vexs[0];pgraph->arcs[0][0]=1;/*表示顶点v0在集合U中*/for(i=1;i<pgraph->n;i++) {/*初始化集合V-U中顶点的距离值*/dist[i].length=pgraph->arcs[0][i];dist[i].vertex=pgraph->vexs[i];if(dist[i].length!=MAX)dist[i].prevex=0;elsedist[i].prevex=-1;}}voiddijkstra(GraphMatrixgraph,Pathdist[]){inti,j,minvex;AdjTypemin; init(&graph,dist);/*初始化，此时集合U中只有顶点v0*/for(i=1;i<graph.n;i++) {min=MAX; minvex=0;for(j=1;j<graph.n;j++)/*在V-U中选出距离值最小顶点*/if(graph.arcs[j][j]==0&&dist[j].length<min)min=dist[j].length;minvex=j;if(minvex==0)break; /*从v0没有路径可以通往集合V-U中的顶点*/graph.arcs[minvex][minvex]=1; /*集合V-U中路径最小的顶点为minvex*/for(j=1;j<graph.n;j++) { /*调整集合V-U中的顶点的最短路径*/if(graph.arcs[j][j]==1)continue;if(dist[j].length>dist[minvex].length+graph.arcs[minvex][j]) {dist[j].length=dist[minvex].length+graph.arcs[minvex][j];dist[j].prevex=minvex;}}}}GraphMatrixgraph;voidinitgraph(){inti,j;graph.n=6;for(i=0;i<graph.n;i++)for(j=0;j<graph.