广东工业大学数据结构实验报告（1）
学院：自动化
专业:12级物联网3班
姓名：xxx 学号：xxx 老师：张小波
实验日期：2014年6月21日
实验地点：实二203 成绩评定：
实验题目：求一个正整数的各位数字之和
一、实验目的
求一个正整数的各位数字之和。
二、实验软件环境
1．计算机每人一台。 2．软件：Visual Studio 2012
三、实验内容
#include int func(int num) { int s=0; do {
s+=num%10;
num/=10; } while(num); return(s); } void main() { int n; 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．软件：Visual Studio 2012
三、实验内容
#include #include #define MAX 20 typedef struct { double coef;
int exp;
} PolyArray[MAX]; typedef struct pnode //定义单链表结点类型 { double coef;
int exp; } PolyNode; void DispPoly(PolyNode *L) //输出多项式 { bool first=true;
PolyNode *p=L->next; while (p!=NULL) //多项式最多项数
//定义存放多项式的数组类型
//系数 //指数
//系数 //指数
struct pnode *next; //first为true表示是第一项
{
} printf(\"\\n\"); } void DestroyList(PolyNode *&L) //销毁单链表 { PolyNode *p=L,*q=p->next; while (q!=NULL) {
} free(p); } void CreateListR(PolyNode *&L,PolyArray a,int n) //尾插法建表 { PolyNode *s,*r;int i; L=(PolyNode *)malloc(sizeof(PolyNode)); //创建头结点
L->next=NULL; r=L;
{
} r->next=NULL; } void Sort(PolyNode *&head) { PolyNode *p=head->next,*q,*r; if (p!=NULL)
if (first)
first=false; printf(\"+\"); printf(\"%g\",p->coef); printf(\"%gx\",p->coef); printf(\"%gx^%d\",p->coef,p->exp); else if (p->coef>0) if (p->exp==0) else if (p->exp==1) else p=p->next; free(p); p=q; q=p->next;
//r始终指向终端结点,开始时指向头结点
for (i=0;icoef=a[i].coef; s->exp=a[i].exp; r->next=s; r=s; //终端结点next域置为NULL
//按exp域递减排序
//将*s插入*r之后
//若原单链表中有一个或以上的数据结点
{
} } void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc) //求两有序集合的并 { PolyNode *pa=ha->next,*pb=hb->next,*s,*tc; double c; hc=(PolyNode *)malloc(sizeof(PolyNode)); tc=hc; while (pa!=NULL && pb!=NULL) {
r=p->next; p=r;
//r保存*p结点后继结点的指针
p->next=NULL; while (p!=NULL) {
} r=p->next; q=head; //构造只含一个数据结点的有序表
//r保存*p结点后继结点的指针
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;
//创建头结点
if (pa->exp>pb->exp) {
} else if (pa->exp
} else {
c=pa->coef+pb->coef; if (c!=0) {
s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; //系数之和不为0时创建新结点 //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; s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next;
}
} } pa=pa->next; pb=pb->next; if (pb!=NULL) pa=pb; //复制余下的结点
while (pa!=NULL) {
} tc->next=NULL; } void main() { PolyNode *ha,*hb,*hc; PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}}; PolyArray b={{-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); } s=(PolyNode *)malloc(sizeof(PolyNode)); //复制结点 s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next;
四、实验结果和分析
五、实验心得体会
本实验过程中，我进一步了解了单链表的各种操作以及对应的函数的使用方法，以及学会熟练调用函数来实现，比较深刻地体会到了使用单链表的好处和方便。
广东工业大学数据结构实验报告（3）
学院：自动化
专业:12级物联网3班
姓名：xxx
学号：xxx 老师：张小波
实验日期：2014年6月21日
实验地点：实二203 成绩评定：
实验题目：病人看病模拟程序
一、实验目的
掌握顺序栈以及循环队列的使用。
二、实验软件环境
1．计算机每人一台。 2．软件：Visual Studio 2012
三、实验内容
#include #include typedef struct qnode { int data; struct qnode *next; } QNode; { QNode *front,*rear; } QuType; { QNode *p,*q; p=qu->front; if (p!=NULL)
{
//链队节点类型
typedef struct
//链队类型
void Destroyqueue(QuType *&qu) //释放链队
//若链队不空
q=p->next; while (q!=NULL)
//释放队中所有的节点
{
free(p);
p=q;
q=q->next;
}
free(p); } free(qu);
//释放链队节点
} void SeeDoctor() { int sel,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)
{
case 1: 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;
//队空 //队不空
{ p=qu->front; printf(\" >>病人%d就诊\\n\",p->data); if (qu->rear==p)
//只有一个病人排队的情况
qu->front=qu->rear=NULL; printf(\" >>没有排队的病人!\\n\");
case 2: if (qu->front==NULL)
else
else qu->front=p->next; free(p); break;
//队空 //队不空 printf(\" >>没有排列的病人!\\n\");
}
case 3:if (qu->front==NULL)
else
{
} break;
p=qu->front; printf(\" >>排队病人:\"); while (p!=NULL) {
} printf(\"\\n\"); printf(\"%d \",p->data); p=p->next; case 4:if (qu->front==NULL)
//队空 //队不空 printf(\" >>没有排列的病人!\\n\");
else
{
} Destroyqueue(qu); flag=0; break;
//队不空
printf(\" >>请排队的病人明天就医!\\n\");
//释放链队 //退出 p=qu->front; printf(\" >>病人按以下顺序就诊:\"); while (p!=NULL) {
} printf(\"\\n\"); printf(\"%d \",p->data); p=p->next;
case 5:if (qu->front!=NULL)
} void main() { SeeDoctor(); }
} flag=0;
break;
//退出
//释放链队 Destroyqueue(qu); }
四、实验结果和分析
五、实验心得体会
本实验过程中，要求考虑的情况较多，在循环队列中使用指针的使用过程中对空的这种情况还是欠缺考虑，所以以后在进行循环队列使用中务必要记得考虑对空的情况。
广东工业大学数据结构实验报告（4）
学院：自动化
专业:12级物联网3班
姓名：xxx 学号：xxx
老师：张小波
实验日期：2014年6月21日
实验地点：实二203 成绩评定：
实验题目：文本串加密和解密程序
一、实验目的
掌握顺序栈以及循环队列的使用。
二、实验软件环境
1．计算机每人一台。 2．软件：Visual Studio 2012
三、实验内容
lgo4-1.cpp #include #define MaxSize 100 typedef struct { char data[MaxSize]; } SqString; void StrAign(SqString &s,char cstr[]) //s为引用型参数 {
} void StrCopy(SqString &s,SqString t) {
} bool StrEqual(SqString s,SqString t)
//最多的字符个数
//定义可容纳MaxSize个字符的空间
int length; //标记当前实际串长
int i; s.data[i]=cstr[i]; for (i=0;cstr[i]!=\'\\0\';i++) s.length=i;
//s为引用型参数
int i; s.data[i]=t.data[i]; for (i=0;i
{ bool same=true;
//长度不相等时返回0 int i; if (s.length!=t.length)
} int StrLength(SqString s) { return s.length; } SqString Concat(SqString s,SqString t) { SqString str; int i; str.length=s.length+t.length; for (i=0;i
} SqString SubStr(SqString s,int i,int j) { SqString str; int k; str.length=0; if (is.length || js.length)
return str;
//参数不正确时返回空串
for (k=i-1;k
str.length=j; return str; } SqString InsStr(SqString s1,int i,SqString s2) { int j; SqString str; str.length=0; if (is1.length+1) //参数不正确时返回空串
return str;
//将s1.data[0..i-2]复制到str
//将s2.data[0..s2.length-1]复制到str str.data[j]=s1.data[j]; for (j=0;j
for (j=0;j
same=false; for (i=0;i
if (s.data[i]!=t.data[i]) //有一个对应字符不相同时返回0 { } same=false; break; else return same; str.data[i]=s.data[i]; str.data[s.length+i]=t.data[i]; for (i=0;i
//将s.data[i..i+j]复制到str str.data[k-i+1]=s.data[k];
str.data[i+j-1]=s2.data[j];
//将s1.data[i-1..s1.length-1]复制到str str.data[s2.length+j]=s1.data[j]; for (j=i-1;js.length || i+j>s.length+1) //参数不正确时返回空串
return str;
//将s.data[0..i-2]复制到str str.data[k]=s.data[k]; str.data[k-j]=s.data[k]; for (k=0;k
for (k=i+j-1;ks.length || i+j-1>s.length) //参数不正确时返回空串
return str;
//将s.data[0..i-2]复制到str //将t.data[0..t.length-1]复制到str str.data[k]=s.data[k]; str.data[i+k-1]=t.data[k]; str.data[t.length+k-j]=s.data[k]; for (k=0;k
} } int i; for (i=0;i0)
//文件名:exp4-4.cpp
#include #include #define MaxSize 100 typedef struct { char data[MaxSize]; //串长 int length; } SqString; extern void StrAign(SqString &,char []); //在algo4-1.cpp文件中 extern void DispStr(SqString); SqString A,B; { int i=0,j; SqString q; while (i } q.length=p.length; return q; } SqString UnEncrypt(SqString q) { int i=0,j; SqString p; while (i } p.length=q.length; return p; } void main() { SqString p,q; int ok=1; //全局串 SqString EnCrypt(SqString p) for (j=0;p.data[i]!=A.data[j];j++); if (j>=p.length) else i++; //在A串中未找到p.data[i]字母 //在A串中找到p.data[i]字母 q.data[i]=p.data[i]; q.data[i]=B.data[j]; for (j=0;q.data[i]!=B.data[j];j++); if (j>=q.length) else i++; //在B串中未找到q.data[i]字母 p.data[i]=q.data[i]; //在B串中找到q.data[i]字母 p.data[i]=A.data[j]; StrAign(A,\"abcdefghijklmnopqrstuvwxyz\"); //建立A串 StrAign(B,\"ngzqtcobmuhelkpdawxfyivrsj\"); //建立B串 char str[MaxSize]; printf(\"\\n\"); printf(\"输入原文串:\"); gets(str); //获取用户输入的原文串 StrAign(p,str); //建立p串 printf(\"加密解密如下:\\n\"); printf(\" 原文串:\");DispStr(p); q=EnCrypt(p); //p串加密产生q串 //q串解密产生p串 printf(\" 加密串:\");DispStr(q); p=UnEncrypt(q); printf(\"\\n\"); } printf(\" 解密串:\");DispStr(p); 四、实验结果和分析 五、实验心得体会 串加密实际上就是对每个字符进行一定的算法，而这个算法只有你自己知道，其他人不知道。通过该算法，我们可以进行加密与解密工作。新技能get。 广东工业大学数据结构实验报告（5） 学院：自动化 专业:12级物联网3班 姓名：xxx 学号：xxx 老师：张小波 实验日期：2014年6月21日 实验地点：实二203 成绩评定： 实验题目：求解n皇后问题 一、实验目的 掌握递归应用 二、实验软件环境 1．计算机每人一台。 2．软件：Visual Studio 2012 三、实验内容 #include #include const int N=20; //最多皇后个数 int q[N]; //存放各皇后所在的列号 int count=0; //存放解个数 void print(int n) //输出一个解 { count++; int i; printf(\" 第%d个解：\",count); for (i=1;i } int place(int k,int j) { int i=1; while (i //i=1～k-1是已放置了皇后的行 } return 0; i++; return 1; } void queen(int k,int n) { int j; if (k>n) } void main() { int n; scanf(\"%d\",&n); if (n>20) { } printf(\" %d皇后问题求解如下：\\n\",n); queen(1,n); printf(\"\\n\"); printf(\"n值太大,不能求解\\n\"); else //n存放实际皇后个数 printf(\" 皇后问题(n { q[k]=j; queen(k+1,n); } //所有皇后放置结束 //在第k行上穷举每一个位置 //在第k行上找到一个合适位置(k,j) else //放置1-k的皇后 } 四、实验结果和分析 五、实验心得体会 递归应用能够帮我们解决很多需要重复操作的繁琐的算法问题，运用递归我们可以省下不少的时间，能让我们更有效率的进行其他的工作，因此递归算法是十分重要的。 广东工业大学数据结构实验报告（6） 学院：自动化 专业:12级物联网3班 姓名：xxx 学号：xxx 老师：张小波 实验日期：2014年6月21日 实验地点：实二203 成绩评定： 实验题目：求5X5阶螺旋方阵 一、实验目的 掌握矩阵的各种算法 二、实验软件环境 1．计算机每人一台。 2．软件：Visual Studio 2012 三、实验内容 #include #define MaxLen 10 void fun(int a[MaxLen][MaxLen],int n) { int i,j,k=0,m; if (n%2==0) //m=én/2ù { m=n/2; m=n/2+1; else for (i=0;i } for (j=i+1;j } } } for (j=n-i-2;j>=i;j--) { } for (j=n-i-2;j>=i+1;j--) { } k++; a[j][i]=k; k++; a[n-i-1][j]=k; void main() { int n,i,j; int a[MaxLen][MaxLen]; printf(\"输入n(n } } for (j=0;j 四、实验结果和分析 五、实验心得体会 矩阵的算法在大一的时候已经学过，我们只需要熟练的运用好循环进行输入就好了。 广东工业大学数据结构实验报告（7） 学院：自动化 专业:12级物联网3班 姓名：xxx 学号：xxx 老师：张小波 实验日期：2014年6月21日 实验地点：实二203 成绩评定： 实验题目：构造哈夫曼树 一、实验目的 掌握二叉树的遍历，构造。以及哈夫曼树的相关知识。 二、实验软件环境 1．计算机每人一台。 2．软件：Visual Studio 2012 三、实验内容 #include #include #define N 50 #define M 2*N-1 typedef struct { char data[5]; //节点值 int weight; int parent; int lchild; int rchild; } HTNode; typedef struct { char cd[N]; int start; } HCode; void CreateHT(HTNode ht[],int n) { int i,k,lnode,rnode; //叶子节点数 //树中节点总数 //权重 //双亲节点 //左孩子节点 //右孩子节点 //存放哈夫曼码 int min1,min2; for (i=0;i { } } void CreateHCode(HTNode ht[],HCode hcd[],int n) { int i,f,c; HCode hc; for (i=0;i { } } void DispHCode(HTNode ht[],HCode hcd[],int n) //所有节点的相关域置初值-1 //构造哈夫曼树 //lnode和rnode为最小权重的两个节点位置 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for (i=n;i if (ht[k].parent==-1) //只在尚未构造二叉树的节点中查找 { } if (ht[k].weight } else if (ht[k].weight } hc.start++; hcd[i]=hc; //start指向哈夫曼编码最开始字符 if (ht[f].lchild==c) //处理左孩子节点 hc.cd[hc.start--]=\'0\'; //处理右孩子节点 hc.cd[hc.start--]=\'1\'; else c=f;f=ht[f].parent; { int i,k; int sum=0,m=0,j; printf(\"输出哈夫曼编码:\\n\"); //输出哈夫曼编码 for (i=0;i } printf(\"平均长度=%g\\n\",1.0*sum/m); } void main() { int n=15,i; char *str[]={\"The\",\"of\",\"a\",\"to\",\"and\",\"in\",\"that\",\"he\",\"is\",\"at\",\"on\",\"for\",\"His\",\"are\",\"be\"}; int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNode ht[M]; HCode hcd[N]; for (i=0;i } CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); } strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; j=0; printf(\" %s:\\t\",ht[i].data); for (k=hcd[i].start;k } m+=ht[i].weight; sum+=ht[i].weight*j; printf(\"\\n\"); printf(\"%c\",hcd[i].cd[k]); j++; 四、实验结果和分析 五、实验心得体会 哈夫曼树也称最优二叉树，二叉树很多时候确实是一件很有用的东西，也是我们必须掌握的一个算法。 广东工业大学数据结构实验报告（8） 学院：自动化 专业:12级物联网3班 姓名：xxx 学号：xxx 老师：张小波 实验日期：2014年6月21日 实验地点：实二203 成绩评定： 实验题目：实现二分找查的算法 一、实验目的 掌握找查的方法。 二、实验软件环境 1．计算机每人一台。 2．软件：Visual Studio 2012 三、实验内容 #include #define MAXL 100 typedef int KeyType; typedef char InfoType[10]; typedef struct { //其他数据 //顺序表类型 KeyType key; //KeyType为关键字的数据类型 InfoType data; } NodeType; typedef NodeType SeqList[MAXL]; { int low=0,high=n-1,mid,count=0; while (low //定义表中最多记录个数 int BinSearch(SeqList R,int n,KeyType k) //二分查找算法 mid=(low+high)/2; printf(\" 第%d次比较:在[%d,%d]中比较元素R[%d]:%d\\n\",++count,low,high,mid,R[mid].key); if (R[mid].key==k) //查找成功返回 return mid; if (R[mid].key>k) //继续在R[low..mid-1]中查找 } high=mid-1; low=mid+1; //继续在R[mid+1..high]中查找 else return -1; } void main() { SeqList R; KeyType k=9; int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10; for (i=0;i R[i].key=a[i]; //建立顺序表 printf(\"关键字序列:\"); for (i=0;i } printf(\"元素%d的位置是%d\\n\",k,i); printf(\"元素%d不在表中\\n\",k); else 四、实验结果和分析 五、实验心得体会 找查的算法最主要还是弄清楚各指针以及关键字的代码，一个不小心 就很容易弄错了。
