广东工业大学数据结构实验报告(12届)

广东工业大学数据结构实验报告（1）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：求一个正整数的各位数字之和实验目的求一个正整数的各位数字之和。实验软件环境1．计算机每人一台。2．软件：VisualStudio2012实验内容#include<stdio.h>intfunc(intnum){ ints=0; do { s+=num%10; num/=10; }while(num); return(s);}voidmain(){ intn; printf("输入一个整数:"); scanf("%d",&n); printf("各位数字之和:%d\n",func(n)); printf("\n");}实验结果和分析当输入一个整数的时候，得出的是该整数的所有数字的和实验心得体会本实验过程中，感觉能用简单的方法实现程序就应该用简单的，一开始我用了多个for循环，感觉没必要，就用了do-while循环，因此保持程序的简洁，精悍是最应该的，过于冗杂的程序不仅臃肿，而且难以分析，分享。广东工业大学数据结构实验报告（2）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：求两个多项式的相加运算一、实验目的熟悉并学会使用多项式的表示方法以及计算方法二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容#include<stdio.h>#include<malloc.h>#defineMAX20 //多项式最多项数typedefstruct //定义存放多项式的数组类型{ doublecoef; //系数 intexp; //指数}PolyArray[MAX];typedefstructpnode //定义单链表结点类型{ doublecoef; //系数 intexp; //指数 structpnode*next;}PolyNode;voidDispPoly(PolyNode*L) //输出多项式{ boolfirst=true; //first为true表示是第一项 PolyNode*p=L->next; while(p!=NULL) { if(first) first=false; elseif(p->coef>0) printf("+"); if(p->exp==0) printf("%g",p->coef); elseif(p->exp==1) printf("%gx",p->coef); else printf("%gx^%d",p->coef,p->exp); p=p->next; } printf("\n");}voidDestroyList(PolyNode*&L) //销毁单链表{ PolyNode*p=L,*q=p->next; while(q!=NULL) { free(p); p=q; q=p->next; } free(p);}voidCreateListR(PolyNode*&L,PolyArraya,intn)//尾插法建表{ PolyNode*s,*r;inti; L=(PolyNode*)malloc(sizeof(PolyNode)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for(i=0;i<n;i++) { s=(PolyNode*)malloc(sizeof(PolyNode));//创建新结点 s->coef=a[i].coef; s->exp=a[i].exp; r->next=s; //将*s插入*r之后 r=s; } r->next=NULL; //终端结点next域置为NULL}voidSort(PolyNode*&head) //按exp域递减排序{ PolyNode*p=head->next,*q,*r; if(p!=NULL) //若原单链表中有一个或以上的数据结点 { r=p->next; //r保存*p结点后继结点的指针 p->next=NULL; //构造只含一个数据结点的有序表 p=r; while(p!=NULL) { r=p->next; //r保存*p结点后继结点的指针 q=head; while(q->next!=NULL&&q->next->exp>p->exp) q=q->next; //在有序表中找插入*p的前驱结点*q p->next=q->next; //将*p插入到*q之后 q->next=p; p=r; } }}voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc)//求两有序集合的并{ PolyNode*pa=ha->next,*pb=hb->next,*s,*tc; doublec; hc=(PolyNode*)malloc(sizeof(PolyNode)); //创建头结点 tc=hc; while(pa!=NULL&&pb!=NULL) { if(pa->exp>pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } elseif(pa->exp<pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pb->exp;s->coef=pb->coef; tc->next=s;tc=s; pb=pb->next; } else //pa->exp=pb->exp { c=pa->coef+pb->coef; if(c!=0) //系数之和不为0时创建新结点 { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; } pa=pa->next; pb=pb->next; } } if(pb!=NULL)pa=pb; //复制余下的结点 while(pa!=NULL) { s=(PolyNode*)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } tc->next=NULL;}voidmain(){ PolyNode*ha,*hb,*hc; PolyArraya={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}}; PolyArrayb={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}}; CreateListR(ha,a,4); CreateListR(hb,b,5); printf("原多项式A:");DispPoly(ha); printf("原多项式B:");DispPoly(hb); Sort(ha); Sort(hb); printf("有序多项式A:");DispPoly(ha); printf("有序多项式B:");DispPoly(hb); Add(ha,hb,hc); printf("多项式相加:");DispPoly(hc); DestroyList(ha); DestroyList(hb); DestroyList(hc);}四、实验结果和分析五、实验心得体会本实验过程中，我进一步了解了单链表的各种操作以及对应的函数的使用方法，以及学会熟练调用函数来实现，比较深刻地体会到了使用单链表的好处和方便。广东工业大学数据结构实验报告（3）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：病人看病模拟程序一、实验目的掌握顺序栈以及循环队列的使用。二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容#include<stdio.h>#include<malloc.h>typedefstructqnode{intdata;structqnode*next;}QNode; //链队节点类型typedefstruct {QNode*front,*rear;}QuType; //链队类型voidDestroyqueue(QuType*&qu) //释放链队{ QNode*p,*q; p=qu->front; if(p!=NULL) //若链队不空 { q=p->next; while(q!=NULL) //释放队中所有的节点 { free(p); p=q; q=q->next; } free(p); } free(qu); //释放链队节点}voidSeeDoctor(){intsel,flag=1,find,no;QuType*qu;QNode*p;qu=(QuType*)malloc(sizeof(QuType)); //创建空队qu->front=qu->rear=NULL;while(flag==1) //循环执行 { printf("1:排队2:就诊3:查看排队4.不再排队,余下依次就诊5:下班请选择:"); scanf("%d",&sel); switch(sel) { case1: printf(">>输入病历号:"); do { scanf("%d",&no); find=0; p=qu->front; while(p!=NULL&&!find) { if(p->data==no) find=1; else p=p->next; } if(find) printf(">>输入的病历号重复,重新输入:"); }while(find==1); p=(QNode*)malloc(sizeof(QNode)); //创建节点 p->data=no;p->next=NULL; if(qu->rear==NULL) //第一个病人排队 qu->front=qu->rear=p; else { qu->rear->next=p;qu->rear=p; //将*p节点入队 } break; case2: if(qu->front==NULL) //队空 printf(">>没有排队的病人!\n"); else //队不空 { p=qu->front; printf(">>病人%d就诊\n",p->data); if(qu->rear==p) //只有一个病人排队的情况 qu->front=qu->rear=NULL; else qu->front=p->next; free(p); } break;case3:if(qu->front==NULL) //队空 printf(">>没有排列的病人!\n"); else //队不空 { p=qu->front; printf(">>排队病人:"); while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n"); } break;case4:if(qu->front==NULL) //队空printf(">>没有排列的病人!\n"); else //队不空 { p=qu->front; printf(">>病人按以下顺序就诊:"); while(p!=NULL) { printf("%d",p->data); p=p->next; } printf("\n"); } Destroyqueue(qu); //释放链队 flag=0; //退出 break; case5:if(qu->front!=NULL) //队不空 printf(">>请排队的病人明天就医!\n"); flag=0; //退出 Destroyqueue(qu); //释放链队 break; }}}voidmain(){SeeDoctor();}四、实验结果和分析五、实验心得体会本实验过程中，要求考虑的情况较多，在循环队列中使用指针的使用过程中对空的这种情况还是欠缺考虑，所以以后在进行循环队列使用中务必要记得考虑对空的情况。广东工业大学数据结构实验报告（4）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：文本串加密和解密程序一、实验目的掌握顺序栈以及循环队列的使用。二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容lgo4-1.cpp#include<stdio.h>#defineMaxSize100 //最多的字符个数typedefstruct{chardata[MaxSize]; //定义可容纳MaxSize个字符的空间intlength; //标记当前实际串长}SqString;voidStrAssign(SqString&s,charcstr[]) //s为引用型参数{ inti; for(i=0;cstr[i]!='\0';i++) s.data[i]=cstr[i]; s.length=i;}voidStrCopy(SqString&s,SqStringt) //s为引用型参数{ inti; for(i=0;i<t.length;i++) s.data[i]=t.data[i]; s.length=t.length;}boolStrEqual(SqStrings,SqStringt){ boolsame=true; inti; if(s.length!=t.length) //长度不相等时返回0 same=false; else for(i=0;i<s.length;i++) if(s.data[i]!=t.data[i]) //有一个对应字符不相同时返回0 { same=false; break; } returnsame;}intStrLength(SqStrings){ returns.length;}SqStringConcat(SqStrings,SqStringt){ SqStringstr; inti; str.length=s.length+t.length; for(i=0;i<s.length;i++) //将s.data[0..s.length-1]复制到str str.data[i]=s.data[i]; for(i=0;i<t.length;i++) //将t.data[0..t.length-1]复制到str str.data[s.length+i]=t.data[i]; returnstr;}SqStringSubStr(SqStrings,inti,intj){ SqStringstr; intk; str.length=0; if(i<=0||i>s.length||j<0||i+j-1>s.length) returnstr; //参数不正确时返回空串 for(k=i-1;k<i+j-1;k++) //将s.data[i..i+j]复制到str str.data[k-i+1]=s.data[k]; str.length=j; returnstr;}SqStringInsStr(SqStrings1,inti,SqStrings2){ intj; SqStringstr; str.length=0; if(i<=0||i>s1.length+1)//参数不正确时返回空串 returnstr; for(j=0;j<i-1;j++) //将s1.data[0..i-2]复制到str str.data[j]=s1.data[j]; for(j=0;j<s2.length;j++) //将s2.data[0..s2.length-1]复制到str str.data[i+j-1]=s2.data[j]; for(j=i-1;j<s1.length;j++) //将s1.data[i-1..s1.length-1]复制到str str.data[s2.length+j]=s1.data[j]; str.length=s1.length+s2.length; returnstr;}SqStringDelStr(SqStrings,inti,intj){ intk; SqStringstr; str.length=0; if(i<=0||i>s.length||i+j>s.length+1)//参数不正确时返回空串 returnstr; for(k=0;k<i-1;k++) //将s.data[0..i-2]复制到str str.data[k]=s.data[k]; for(k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到str str.data[k-j]=s.data[k]; str.length=s.length-j; returnstr;}SqStringRepStr(SqStrings,inti,intj,SqStringt){ intk; SqStringstr; str.length=0; if(i<=0||i>s.length||i+j-1>s.length)//参数不正确时返回空串 returnstr; for(k=0;k<i-1;k++) //将s.data[0..i-2]复制到str str.data[k]=s.data[k]; for(k=0;k<t.length;k++) //将t.data[0..t.length-1]复制到str str.data[i+k-1]=t.data[k]; for(k=i+j-1;k<s.length;k++) //将s.data[i+j-1..s.length-1]复制到str str.data[t.length+k-j]=s.data[k]; str.length=s.length-j+t.length; returnstr;}voidDispStr(SqStrings){ inti; if(s.length>0) { for(i=0;i<s.length;i++) printf("%c",s.data[i]); printf("\n"); }}//文件名:exp4-4.cpp#include<stdio.h>#include<string.h>#defineMaxSize100typedefstruct{ chardata[MaxSize]; intlength; //串长}SqString;externvoidStrAssign(SqString&,char[]); //在algo4-1.cpp文件中externvoidDispStr(SqString);SqStringA,B; //全局串SqStringEnCrypt(SqStringp){ inti=0,j; SqStringq; while(i<p.length) { for(j=0;p.data[i]!=A.data[j];j++); if(j>=p.length) //在A串中未找到p.data[i]字母 q.data[i]=p.data[i]; else //在A串中找到p.data[i]字母 q.data[i]=B.data[j]; i++; } q.length=p.length; returnq;}SqStringUnEncrypt(SqStringq){ inti=0,j; SqStringp; while(i<q.length) { for(j=0;q.data[i]!=B.data[j];j++); if(j>=q.length) //在B串中未找到q.data[i]字母 p.data[i]=q.data[i]; else //在B串中找到q.data[i]字母 p.data[i]=A.data[j]; i++; } p.length=q.length; returnp;}voidmain(){ SqStringp,q; intok=1; StrAssign(A,"abcdefghijklmnopqrstuvwxyz"); //建立A串 StrAssign(B,"ngzqtcobmuhelkpdawxfyivrsj"); //建立B串 charstr[MaxSize]; printf("\n"); printf("输入原文串:"); gets(str); //获取用户输入的原文串 StrAssign(p,str); //建立p串 printf("加密解密如下:\n"); printf("原文串:");DispStr(p); q=EnCrypt(p); //p串加密产生q串 printf("加密串:");DispStr(q); p=UnEncrypt(q); //q串解密产生p串 printf("解密串:");DispStr(p); printf("\n");}四、实验结果和分析五、实验心得体会串加密实际上就是对每个字符进行一定的算法，而这个算法只有你自己知道，其他人不知道。通过该算法，我们可以进行加密与解密工作。新技能get。广东工业大学数据结构实验报告（5）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：求解n皇后问题一、实验目的掌握递归应用二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容#include<stdio.h>#include<stdlib.h>constintN=20; //最多皇后个数intq[N]; //存放各皇后所在的列号intcount=0; //存放解个数voidprint(intn) //输出一个解{ count++; inti; printf("第%d个解：",count); for(i=1;i<=n;i++) printf("(%d,%d)",i,q[i]); printf("\n");}intplace(intk,intj) //测试(k,j)位置能否摆放皇后{ inti=1; while(i<k) //i=1～k-1是已放置了皇后的行 { if((q[i]==j)||(abs(q[i]-j)==abs(i-k))) return0; i++; } return1;}voidqueen(intk,intn) //放置1-k的皇后{ intj; if(k>n) print(n); //所有皇后放置结束 else for(j=1;j<=n;j++) //在第k行上穷举每一个位置 if(place(k,j)) //在第k行上找到一个合适位置(k,j) { q[k]=j; queen(k+1,n); }}voidmain(){ intn; //n存放实际皇后个数 printf("皇后问题(n<20)n="); scanf("%d",&n); if(n>20) printf("n值太大,不能求解\n"); else { printf("%d皇后问题求解如下：\n",n); queen(1,n); printf("\n");}}四、实验结果和分析五、实验心得体会递归应用能够帮我们解决很多需要重复操作的繁琐的算法问题，运用递归我们可以省下不少的时间，能让我们更有效率的进行其他的工作，因此递归算法是十分重要的。广东工业大学数据结构实验报告（6）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：求5X5阶螺旋方阵一、实验目的掌握矩阵的各种算法二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容#include<stdio.h>#defineMaxLen10voidfun(inta[MaxLen][MaxLen],intn){ inti,j,k=0,m; if(n%2==0)//m=én/2ù m=n/2; else m=n/2+1; for(i=0;i<m;i++) { for(j=i;j<n-i;j++) { k++; a[i][j]=k; } for(j=i+1;j<n-i;j++) { k++; a[j][n-i-1]=k; } for(j=n-i-2;j>=i;j--) { k++; a[n-i-1][j]=k; } for(j=n-i-2;j>=i+1;j--) { k++; a[j][i]=k; } }}voidmain(){ intn,i,j; inta[MaxLen][MaxLen]; printf("输入n(n<10):"); scanf("%d",&n);fun(a,n); printf("%d阶数字方阵如下:\n",n); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%4d",a[i][j]); printf("\n"); }}四、实验结果和分析五、实验心得体会矩阵的算法在大一的时候已经学过，我们只需要熟练的运用好循环进行输入就好了。广东工业大学数据结构实验报告（7）学院：自动化专业:12级物联网3班姓名：xxx学号：xxx老师：张小波实验日期：2014年6月21日实验地点：实二203成绩评定：实验题目：构造哈夫曼树一、实验目的掌握二叉树的遍历，构造。以及哈夫曼树的相关知识。二、实验软件环境1．计算机每人一台。2．软件：VisualStudio2012三、实验内容#include<stdio.h>#include<string.h>#defineN50 //叶子节点数#defineM2*N-1 //树中节点总数typedefstruct{ chardata[5]; //节点值 intweight; //权重 intparent; //双亲节点 intlchild; //左孩子节点 intrchild; //右孩子节点}HTNode;typedefstruct{ charcd[N]; //存放哈夫曼码 intstart;}HCode;voidCreateHT(HTNodeht[],intn){ inti,k,lnode,rnode; intmin1,min2; for(i=0;i<2*n-1;i++) //所有节点的相关域置初值-1 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) //构造哈夫曼树 { min1=min2=32767; //lnode和rnode为最小权重的两个节点位置 lnode=rnode=-1; for(k=0;k<=i-1;k++) if(ht[k].parent==-1) //只在尚未构造二叉树的节点中查找 { if(ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } elseif(ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; }}voidCreateHCode(HTNodeht[],HCodehcd[],intn){ inti,f,c; HCodehc; for(i=0;i<n;i++) //根据哈夫曼树求哈夫曼编码 { hc.start=n;c=i; f=ht[i].parent; while(f!=-1) //循序直到树根节点 { if(ht[f].lchild==c) //处理左孩子节点 hc.cd[hc.start--]='0'; else //处理右孩子节点 hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; } hc.start++; //start指向哈夫曼编码最开始字符 hcd[i]=hc; }}voidDispHCode(HTNodeht[],HCodehcd[],intn){ inti,k; intsum=0,m=0,j; printf("输出哈夫曼编码:\n");//输出哈夫曼编码 for(i=0;i<n;i++) { j=0; printf("%s:\t",ht[i].data); for(k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf("\n"); } printf("平均长度=%g\n",1.0*sum/m);}voidmain(){ intn=15,i; char*str[]={"The","o