数据结构
上机实验报告
院系：计算机科学与技术学院
学号：0906840440
姓名：姚凌翔
指导老师：张宏
实验一：多项式相乘
【实验内容及要求】
题目：
hc=ha*hb
要求：
（1） 输入形式： 以“系数 指数”<Enter>的递减序输入，最后以“0 0<Enter>”结束
（2） 输出，见格式
例： 5x9-7x2+6x-5
【程序代码】
#include<iostream.h>
#include<stdlib.h>
struct Node{
double coef;
int exp;
Node *next;
};
Node *Create()
{
Node *h,*p;
double x;
int y;
h=new Node;
h->exp=-1;
p=h;
while(1){
cin>>x>>y;
if(x==0&&y==0) break;
if(y<0){
cout<<"指数不能为负！"<<endl;
exit(1);
}
p->next=new Node;
p=p->next;
p->coef=x;
p->exp=y;
}
p->next=h;
return h;
}
int comp(int a,int b)
{
if(a>b) return -1;
if(a==b) return 0;
else return 1;
}
Node *Add(Node *ha,Node *hb) {
Node *pa,*pb,*q=ha;
pa=ha->next;
pb=hb->next;
while(pb!=hb)
switch(comp(pa->exp,pb->exp)){ case -1:
q=pa;
pa=pa->next;
break;
case 0:
pa->coef+=pb->coef; if(pa->coef==0){
q->next=pa->next; delete pa;
pa=q;
}
else
q=pa;
pa=pa->next; pb=pb->next; break;
case 1:
Node *r;
r=new Node;
r->coef=pb->coef; r->exp=pb->exp;
q->next=r;
r->next=pa;
q=r;
pb=pb->next;
break;
}
return ha;
}
Node *Mul(Node *ha,Node *hb)
{
Node *hc,*p,*q,*r,*pt,*hp;
hc=new Node;
hc->exp=-1;
hc->next=hc;
p=ha->next;
while(p!=ha){
hp=new Node;
hp->exp=-1;
hp->next=hp;
pt=hp;
q=hb->next;
while(q!=hb){
r=new Node;
r->coef=p->coef*q->coef;
r->exp=p->exp+q->exp;
pt->next=r;
r->next=hp;
pt=r;
q=q->next;
}
hc=Add(hc,hp);
p=p->next;
}
return hc;
}
void Outport(Node *h)
{
Node *p;
p=h->next;
while(p!=h){
if(p->coef>0&&p->coef!=1)
if(p!=h->next)
if(p->exp>1)
cout<<"+"<<p->coef<<"X^"<<p->exp; else
switch(p->exp){
case 0:
cout<<"+"<<p->coef;break; case 1:
cout<<"+"<<p->coef<<"X";break; } else if(p->exp>1)
cout<<p->coef<<"X^"<<p->exp; else
switch(p->exp){
case 0:
cout<<p->coef;break;
case 1:
cout<<p->coef<<"X";break; }
else
if(p->coef<0&&p->coef!=-1)
if(p->exp>1)
cout<<p->coef<<"X^"<<p->exp; else
switch(p->exp){
case 0:
cout<<p->coef;break;
case 1:
cout<<p->coef<<"X";break; }
else
switch(int(p->coef)){
case -1:
if(p->exp>1)
cout<<"-X^"<<p->exp;
else
switch(p->exp){
case 0:
cout<<p->coef;break;
case 1:
cout<<"-X";break;
}
break;
case 1:
if(p!=h->next)
if(p->exp>1)
cout<<"+X^"<<p->exp; else
switch(p->exp){
case 0:
cout<<"+"<<p->coef;break;
case 1:
cout<<"+X";break;
}
else
if(p->exp>1)
cout<<"X^"<<p->exp;
else
switch(p->exp){
case 0:
cout<<p->coef;break;
case 1:
cout<<"X";break;
}
break;
}
p=p->next;
}
cout<<endl;
}
void main()
{
Node *ha,*hb,*hc;
cout<<"请输入一元多项式各项的系数和指数，均以0结束："<<endl; ha=Create();
cout<<"请输入一元多项式各项的系数和指数，均以0结束："<<endl; hb=Create();
hc=Mul(ha,hb);
Outport(hc);
}
【程序输出结果】
【结果分析、自己的体会和收获】：
我觉得上机实践对我们更深入地学习数据结构很有帮助。虽然我的C++在上一学期学的还算可以，但毕竟学的只是一些皮毛，而且一个暑假里没有去接触毕竟还是有些生疏了。不过这学期的数据结构则给了我一个继续去深入学习编程的机会，让我受益匪浅。第一，以前学习编程时接触到的程序很小，也比较简单，都是为学习考试的需要而编写的小程序，不具有实用性，而数据结构中的程序使我们真正领略到编程强大的功能与无限的魅力之所在，让我们在将来的计算机职场竞争中更具有竞争力。比如该程序就可以作为一个软件来运算多项式乘法中的问题，从而节省时间。其次，在上机实践初期与到了不少的困难，使我们不得不重新翻开课本温故一下知识点，从而使我们更深刻地理解了它们。还有，通过上机实践，使我们掌握了不少上机操作技能。
通过这次上机实践无疑大大提高了我们的分析思维能力，由于查阅大量书籍，与同学进行交流，不仅学习了一些新的知识，也从中学习了与提高了自学能力与程序设计能力。第二 ，从学习的过程中我也感受到了学习的快乐和成就感。看着自己费尽辛劳所编的程序最后终于开花结果，能够流畅的运行并满足了所有的要求，我心中的自豪感油然而生，以喜悦的心情写下了这份报告书。这么多天的辛勤和脑力折磨终于有了成果，黄天不负有心人，可以说，这次编程使我那些在课本上已经懂得了的和那些很多不太明白的地方都有了新的理解。第三，其实这个程序并不是特别的难，运用的知识都是课本上学过的，但是你要想把他弄的很好也不是那么的容易的。我知道无论做什么事，既然你要做，那么你就要尽自己的最大的努力去把他做好，事在人为。
实验二：二叉树的相关操作
【实验内容及要求】
题目：
建立一棵二叉树，数据以字符串形式从键盘输入。在此二叉树上完成：
（1）前序、中序、后序遍历
（2）求出叶子数
（3）求树高
（4）左右子树交换，输出交换后的前序、中序遍历序列
范例：
{
char data;
TreeNode *lchild,*rchild;
};
char getonech(char ar[])
{
static int i;
return ar[i++];
}
void CreateBinTree(TreeNode *&p,char ar[])
{
char ch;
ch=getonech(ar);
if(ch!= '*')
{
p=new TreeNode;
p->data=ch;
CreateBinTree(p->lchild,ar);
CreateBinTree(p->rchild,ar);
}
else p=NULL;
}
void preorder(TreeNode *p)
{
if(p!=NULL)
{
cout<<p->data; preorder(p->lchild); preorder(p->rchild);
}
}
void inorder(TreeNode *p)
{
if (p)
{
inorder (p->lchild);
cout<<p->data;
inorder (p->rchild);
}
}
void postorder(TreeNode *p)
{
if (p)
{
postorder (p->lchild);
postorder (p->rchild);
cout<<p->data;
}
}
int count(TreeNode *p)
{
if(p)
{
int m=count(p->lchild); m+=count(p->rchild);
if( !m ) return 1;
else return m;
}
else return 0;
}
int depth(TreeNode *&p)
{
if(!p) return 0;
int m=depth(p->lchild)+1;
int n=depth(p->rchild)+1;
return m>n?m:n;
}
void exchange(TreeNode *&p)
{
TreeNode *temp;
if(p)
{
temp=p->lchild;
p->lchild=p->rchild;
p->rchild=temp;
exchange(p->lchild);
exchange(p->rchild);
}
}
void main(void)
{
char s[50];
TreeNode *tree;
cout<<"输入相应的二叉树："; cin.getline(s,50);
CreateBinTree(tree,s);
cout<<"先序为：";
preorder(tree);
cout<<endl;
cout<<"中序为：";
inorder(tree);
cout<<endl;
cout<<"后序为：";
postorder(tree);
cout<<endl;
cout<<"结点数为："<<count(tree)<<endl; cout<<"树高为："<<depth(tree)<<endl; exchange(tree);
cout<<"先序为：";
preorder(tree);
cout<<endl;
} cout<<"中序为："; inorder(tree); cout<<endl;
【程序输出结果】
【结果分析、自己的体会和收获】：
第一次编写一个关于二叉树的完整程序，确实是一件很不容易的事。
编程之前先花了两天复习了一遍教材上与二叉树有关的内容，尤其是二叉树的创建、遍历等内容。值得庆幸的是这个程序涉及到的二叉树的基本操作基本上老师都讲过，自己也认真的做了一下笔记，复习起来不是很麻烦。
初拿到这道题目时，我根据课件上源代码的提示，仔细研读书上已有的代码，认真消化，仔细理解。其中难度最大的就是遍历了。在思考清楚一系列问题后，接下来就是动手编写程序了。在编写的过程中遇到了很多之前根本没有考虑到的问题，经过自己的仔细思考和与同学的讨论，最终还是解决了。
总之，这次上机实践让我切身体会到了什么是二叉树。虽然说总体上与以往上机题目那种几个功能函数加一个主函数存在一定的相同之处，但这次最大的不同之处就在于递归函数的多次调用，这在理解难度和程序编写上都提升了一定的档次。
设计程序光有语法知识是远远不够的，最重要的是多动手，多熟练，在动手的过程中能强化很多概念。另外对程序全局一定要有个清晰的认识，各个函数的关系条理要清晰，否则一旦深入到一个具体的过程中编写代码，再回到全局，很容易迷茫。
很多东西还是要日后体会！多动手多实践，编程的道路上没有捷径。
实验三： 用Dijkstra算法求最短路径
【实验内容及要求】
题目：
用Dijkstra算法求下图的最大短路径，源点取顶点1。
【程序代码】
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#define NUM 6
#define MAXINT 1000
void creategraph(int g[][NUM])
{
ifstream infile("test.txt",ios::in|ios::nocreate);
if(!infile){
cout<<"不能打开输入文件：data.txt"<<endl;
exit(1);
}
int u,v,w;
while(infile>>u){
infile>>v>>w;
g[u-1][v-1]=w;
}
infile.close();
}
void print(int dist[],int path[][NUM],int v0)
{
int i,j;
for(i=0;i<NUM;i++)
if(i!=v0-1){
cout<<"路径长度:"<<dist[i]<<endl;
cout<<"路径为:"<<v0;
for(j=1;j<NUM;j++)
if(path[i][j])
cout<<"->"<<path[i][j];
else break;
cout<<endl<<endl;
}
}
void shortpath(int g[][NUM],int v0) //v0为源点，值为1到NUM {
int i,j,k,v,min;
int set[NUM],dist[NUM],path[NUM][NUM]={0}; for(i=0;i<NUM;i++){
set[i]=0;
dist[i]=g[v0-1][i];
path[i][0]=v0;
}
set[v0-1]=1;
for(i=1;i<NUM;i++){
min=MAXINT;
for(j=0;j<NUM;j++)
if(set[j]==0&&dist[j]<min){
v=j;
min=dist[j];
}
set[v]=1;
for(j=0;j<NUM;j++) //记顶点号
if(!path[v][j]){
path[v][j]=v+1;
break;
}
for(k=0;k<NUM;k++)
if(set[k]==0&&dist[v]+g[v][k]<dist[k]){
dist[k]=dist[v]+g[v][k];
for(j=0;j<NUM;j++)
path[k][j]=path[v][j];
}
}
print(dist,path,v0);
}
void main()
{
int g[NUM][NUM];
for(int i=0;i<NUM;i++)
}
for(int j=0;j<NUM;j++) g[i][j]=MAXINT; creategraph(g); shortpath(g,1);
【程序输出结果】
【结果分析、自己的体会和收获】：
用Dijkstra算法求最短路径是一个简单的求最短路径程序。这个程序的设计基本上都是课堂上讲过的，但实验过程中也遇到了不少问题，最后将这些函数连接起来也这个程序中较难解决的问题。求最短路径在现实生活中是一个简单的工作，但在这个程序的设计过程中，却让我一度头疼，如此简单的求最短路径却需要如此麻烦的程序代码。在这一段紧张的时间里，我也曾几次因为感到手足无措而想要放弃，可是每次又在与同学们的讨论中再次拾得兴趣和信心。几经设计、调试，最终在老师和同学们的帮助下成功地完成了这个任务。对于设计这样一个并不冗长的程序，我体会到，想要完成这样一件事，最需要的就是耐心和勇气，也就是要做好一个长时间和困难做斗争的准备。
在所有工作做完之后，我觉得数据结构的确是有其重要性及实用性的。C++是一个复杂而繁琐的应用软件，但若能够精通数据结构的知识，设计出很好的程序，在现今至少一段时间里就一定能够解决一些问题来为大家服务。这个工作做完之后的那种成就感，也不断激励这我继续前进，同样也使我对数据结构的兴趣提高了不少，希望在以后的学习工程中能有机会对数据结构的知识有更加深入的了解，也希望有机会能够用我所掌握的这些知识，来为大家服务。