数据结构与程序设计专题实验指导书.docx
- 文档编号:1979354
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:19
- 大小:39.51KB
数据结构与程序设计专题实验指导书.docx
《数据结构与程序设计专题实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构与程序设计专题实验指导书.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构与程序设计专题实验指导书
数据结构与程序设计
专题实验参考
1.目标
Ø以培养学生通过计算机编程来解决实际问题的能力为主;
Ø通过该专题实验的进行,训练学生C语言与数据结构的知识来解决实际问题的能力,为学生以后从事程序开发、软件设计以及其它相关研究开发工作奠定基础;
Ø针对给定的问题编写C语言程序、调试并得到正确的结果,解释程序中出现的问题,给出解决思路与方法。
掌握C语言的编程方法,数据结构中的主要逻辑结构、存储结构与算法。
2.基础知识
VisualC++作为一种程序设计语言,它同时也是一个集成开发工具,一个在Windows下进行32位应用程序开发的可视化集成开发环境,提供了软件代码自动生成和可视化的资源编辑功能。
相比其他的编程工具而言,VC++在提供可视化编程方法的同时,也适用于编写直接对系统进行底层操作的程序,其生成代码的质量也较其他很多开发环境更优。
在各种各样的VC++及Windows编程的书籍中,经常会提及这样两个常见以
缩写方式出现的词:
MFC(MicrosoftFoundationClassLibrary),即:
Microsoft基础类库,它是VC++的核心,为编程者提供了一个应用程序框架,这个应用程序框架为编程者完成了很多Windows编程中的例行性工作,如管理窗口、菜单和对话框,执行基本的输入和输出、使用集合类来保存数据对象等等;
API(ApplicationProgrammingInterface),即:
应用程序接口,它是所有Windows应用程序的根本之所在。
简单的说,API就是一系列的例程,应用程序通过调用这些例程来请求操作系统完成一些低级服务。
在Windows这样的图形用户界面中,应用程序的窗口、图标、菜单和对话框等就是由API来管理和维护的。
关于这个开发环境的一些基础性的知识内容,可以在各种参考书籍中查阅。
这里不再占用篇幅。
2.1在VC++集成开发环境中进行简单C程序的编写与运行调试
在VC++集成开发环境所提供的强大的编辑和调试环境的支持下,简单C语
言应用程序的开发过程会变得相对容易些。
但是有一点要明确:
在VC++开发环境中,对程序的调试、运行等都建立在“项目”或“工程”(Project)的基础上。
因此,即使是只有一个C文件,也需要运行在一个工程之中。
2.1.1创建新工程:
(1)选择File→New菜单命令,在弹出的“新建”对话框中选择Project选
项卡。
(2)选择Win32Application,在ProjectName编辑框中输入一个工程名,如
MyProject,选择工程存放的路径Location,单击OK按钮。
(3)选择AnEmptyProject,并单击Finish按钮。
系统弹出一个”NewProject
Information”窗口,点击OK确定。
一个空的工程就创建好了。
在WorkSpace里查看FileView,可以看到MyProject树下有三个文件夹:
SourceFiles,HeaderFiles和ResourceFiles,但是都是空的。
查看Window系统中相应的路径,MyProject目录下有一个名为Debug的空文件夹,三个新创建的文件Myproject.dsp,MyProject.dsw和MyProject.ncb保存项目的相关信息。
2.1.2编写应用程序
(1)点击新建一个文件,并且保存为MyProgram.c。
(2)在WrokSpace的FileView中,点击MyProjectFiles前的+,展开文件
树,在SourceFiles处点击右键,并选择:
”AddFilestoFolder..”。
(3)在弹出的对话框中,选择MyProgram.c,并点击OK,可以看到MyProgram.c出现在SourceFiles文件树之中。
新的应用程序已经创建,并且已经包含到工程之中。
双击MyProgram.c,就可以编写应用程序了。
如果希望编写C++程序,只需在保存文件时使用.cpp作为后缀名即可。
通过File→New,选择C++源文件,也可以很方便地创建应用程序文件。
2.1.3程序的编译、运行
对于C程序而言,其编译运行方法与普通VC++程序的编译运行过程完全一致。
编译、运行的操作都在Build菜单中。
工具栏中的图标:
分别代表:
编译程序、创建应用程序、停止创建过程、执行应用程序、调试、设置断点。
2.2在VC++集成开发环境中创建基于单文档的可视化应用程序
基于单文档的项目就是用单窗口文档做为主窗口的一个程序。
这样的编程工
作在VC++开发软件的帮助下会变得相对简单得多。
我们可以使用MFC,通过AppWizard来生成应用程序框架,然后再在此框架的基础上添加特定的应用程序的功能。
说明一点:
AppWizard能够帮助我们建立起一个应用程序的框架,但绝大多数的应用程序的代码还需要我们亲自编写。
明白这一点是很重要的:
AppWizard所做的,只不过是我们在程序设计过程中所需要的最没有创意的那一部分事情。
对于基于单文档的应用程序来说,我们可以很容易地使用AppWizard来实现一个单文档界面,在整个过程中,只需要做一点点简单的选择就足够了。
2.2.1创建应用程序框架
(1)选择File→New菜单命令,在弹出的“新建”对话框中选择Project选
项卡。
(2)选择MFCAppWizard(exe),在ProjectName编辑框中输入工程名,如
MyApp,单击OK按钮,出现Step1对话框。
(3)选择单文档选项,单击Next按钮,出现Step2对话框。
(4)在以后各步中接受默认设置,一直到最后点击Finish。
(5)点击OK确认新生成项目的信息,系统会自动生成一个基于单文档的
工程。
在FileView中,可以看到向导已经为我们生成了一些基本的应用程序框架,
后面的程序就是在这个框架的基础上进行添加的。
2.2.2程序的编译、运行
点击进行编译链接,生成MyApp.exe。
点击运行。
这个名为“无标题“的
程序就是向导为我们完成的。
(注:
章节2内容摘自西安交通大学电信学院“程序设计专题”课程组编写的《程序设计专题实验参考》)
3.线性表操作与停车场管理方案设计
实验目的:
熟练掌握数组、指针的运用,以及线性表、栈、队列等基本操作。
基本要求:
实现线性表、栈、队列等常用的几种基本操作,并完成停车场管理的程序。
问题描述:
有一狭长停车场可停放n辆车,只有一个门可供进出。
车辆按照到达的早晚从最里面依次向外排列,若停车场中的车辆出来,则在它之后进入停车场的车都要让路,然后这些车辆再依次进场。
以该问题为背景,实现
1)基于链表和顺序表来实现栈的pop与push操作,队列的EnQueue和DeQueue操作;
2)针对停车场管理问题的具体的要求来实现车辆的调度。
注:
栈和队列皆有顺序存储结构和链式存储结果,可以采用不同的形式组合来进行实现。
图1停车场示意图
考核要求:
✓由用户指定n的大小及第m辆车出停车场。
✓在文件或屏幕上显示以下两个时刻栈和队列中的车辆情况:
第m辆车可以开出停车场;第m辆车开出后,其它车重新回到停车场。
✓可以一次输入多辆车的调度指令,程序依次显示每辆车的调度结果。
基本知识:
1)栈的push和pop操作:
StatusPush(SqStack&s,SElemTypee)
{if(s.top-s.base>=s.stacksize)//判断是否栈满
{s.base=(SElemType*)realloc(s.base,
(s.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!
s.base)exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=STACK_INCREMENT;
}
*s.top++=e;//相当于:
*s.top=e;s.top++两条指令;
returnOK;
}//Push;
StatusPop(SqStack&s,SElemType&e)
{if(s.top==s.base)//判断是否栈空
returnERROR;
s.top--;
e=*s.top
returnOK;
}//Pop
2)队列的dequeue和enqueue操作:
StatusEnQueue(SqQueue&Q,QElemTypee)
{if(((Q.rear+1)%MAXQSIZE)==Q.front)
return(ERROR);//
Q.base[Q.rear]=e;//
Q.rear=((Q.rear+1)%MAXQSIZE);
returnOK;
}//EnQueue;
StatusDeQueue(SqQueue&Q,QElemType&e)
{if(Q.rear==Q.front)
return(ERROR);
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
returnOK;
}//DeQueue;
4.树的基本操作及基于霍夫曼树的编码/译码
实验目的:
掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。
基本要求:
熟练掌握树的操作。
问题描述:
给定一段字符,构建霍夫曼树;根据该树求每个字符的编码,并对该段字符串进行编码;将得到的编码进行译码;基于该霍夫曼树,通过遍历算法来输出该树中的叶子节点。
注:
在遍历的时候可以采用递归或非递归办法寻找叶子节点。
考核要求:
所有输入输出数据存储至文件,输入字符串由用户随意指定。
基本知识:
1)霍夫曼树构建及霍夫曼编码:
typedefstruct
{unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HufmanCode;
voidhufmanCode(HufumanTree&HT,HumanCode&HC,int*w,intn)
{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={*w,0,0,0};
for(;i<=m;++i,++p)*p={0,0,0,0};
for(i=n+1;i<=m;++i)//构造赫夫曼树
{Select(HT,i-1,s1,s2);//选择根结点权值最小的2个二叉树
HT[s1].parent=i;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);
}
2)通过遍历求解叶子结点:
voidinorder(BiTreeT)
{InitStack(S);
p=T;
while(p||!
SatckEmpty(S))
{if(p){Push(p);p=p->lchild;}
else{Pop(p);printf(p->data);
p=p->rchild);
}
}
}
上以上函数基础上修改即可,只有叶子结点在进行输出(printf)。
5.图的基本操作及城市交通方案设计
实验目的:
掌握无向图的建立、最小生成树及最短路径的求解。
基本要求:
熟练掌握图的基本操作,完成给定城市交通方案的设计。
问题描述:
用无向图表示n个城市之间的交通网络,顶点表示城市,边表示该线路造价(造价C与长度S成正比,即C=kS)。
针对该问题,实现
1)根据输入的数据完成无向图的生成,输入数据为城市、城市间的关系、线路造价;
2)采用深度优先或广度优先对该无向图实现遍历;
3)编程实现一个最低造价的交通网络,且该网络是一个连通图;
4)在3)中的交通网络中求解给定两城市间的距离。
考核要求:
✓图的数据输入通过教材中的CreateALGraph函数的输入方式进行;
✓分别采用邻接矩阵或邻接表的形式,生成的图的结构(邻接矩阵或邻接表)输入到文件中;
✓采用邻接表实现遍历,可采用深度或广度优先的方式;遍历结果输入到文件或打印到屏幕;
✓采用邻接矩阵实现最小生成树及最短路径求解,结果输入至文件。
基本知识:
1)无向图的生成(以邻接表存储结构,邻接矩阵存储结构类似)
voidCreateALGraph(ALGraph&G)//创建无向图的邻接表
{scanf(&G.vexnum,&G.arcnum,&G.kind);
for(k=1;k<=G.vexnum;k++)//输入顶点,建立顶点数组
{G.vextices[k].firstarc=NULL;scanf(&G.vextices[k].data);}
for(k=1;k<=G.arcnum;k++)//输入边,建立边链表
{scanf(&x1,&x2);
i=Locatevex(G,x1);j=Locatevex(G,x2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=G.vextices[i].firstarc;
G.vextices[i].firstarc=p;//插入到顶点i的边链表
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=i;p->nextarc=G.vextices[j].firstarc;
G.vextices[j].firstarc=p;//插入到顶点j的边链表
}
}
在以上函数中需要注意每个边结点中需要将权值也存储起来。
2)图的深度优先遍历(递归):
voidDFSTraverse(GraphG)
{for(k=1;k<=G.vexnum;++k)visited[k]=FALSE;
for(k=1;k<=G.vexnum;++k)
if(!
visited[k])DFS(G,k);
}
voidDFS(GraphG,intv);
{visited[v]=TRUE;
VISIT(v);//访问图G中第v个顶点
for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
if(!
visited[w])DFS(G,w);
}
intFirstAdjVex(ALGraphG,intv)
{//返回G中第v个顶点的第1个邻接点的序号。
如果v无邻接点,返回0。
if(!
G.vertices[v].firstarc)return(0);
elsereturn(G.vertices[v].firstarc->adjvex);
}
intNextAdjVex(ALGraphG,intv,intw)//返回G中第v个顶点的相对于顶点w的下一个邻接点的序号。
如果v无相对于顶点w的下一个邻接点,返回0。
{ArcNode*p;
p=G.vetrices[v].firstarc;
while(p&&p->adjvex!
=w)p=p->nextarc;
if(p->adjvex==w&&p->nextarc)return(p->nextarc->adjvex);
elsereturn(0);
}
3)图的广度优先遍历(采用队列的数据结构):
voidBFSTraverse(GraphG)
{for(v=1;v<=G.vexnum;++v)visited[v]=FALSE;
InitQueue(Q);
for(v=1;v<=G.vexnum;++v)
if(!
visited[v])
{visited[v]=TRUE;VISIT(v);EnQueue(Q,v);
while(!
EmptyQueue(Q))
{DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!
visited[w])
{visited[w]=TRUE;VISIT(w);EnQueue(Q,w);}
}//endwhile
}//endif
}
4)采用prim算法实现最小生成树:
typedefstruct{VertexTypevexs[MAX];
intEdge[MAX][MAX];
intvexnum,arcnum;
}MGraph;
struct{VertexTypeadjvex;
intlowcost;
}closedge[MAX];
voidMST_Prim(MGraphG,VertexTypeu)
{k=LocateVex(G,u);//求顶点u的序号
for(j=1;j<=G.vexnum;j++)//初始化辅助数组closedge
if(j!
=k)closedge[j]={u,G.Edge[k][j]};
closedge[k].lowcost=0;//初始时U={u}
for(i=1;i {min=∞;k=0;//查找U到V-U中的权值最小的边 for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost>0&&closedge[j].lowcost {k=j;min=closedge[j].lowcost;} printf(closedge[k].adjvex,G.vexs[k]);//输出该边 closedge[k].lowcost=0;//顶点k并入U for(j=1;j<=G.vexnum;j++)//修改V-U中每个顶点到U的最小边 if(G.Edge[k][j] closedge[j]={G.vexs[k],G.Edge[k][j]}; } } 5)Dijkstra算法求最短距离: typedefintPathMatrix[MAX][MAX]; typedefintShortPathTable[MAX]; voidShortestPath(MGraphG,intv0,PathMatrix&P,ShortPathTable&D) //求图G从v0到其余顶点v的最短路径P[v]和路径长度D[v], //如果P[v][w]为TRUE,则w为v0到v的最短路径上的顶点。 {for(i=0;i {final[i]=FALSE;//表示顶点iS D[i]=G.Edge[v0][i]; for(j=0;j if(D[i]<∞){P[i][v0]=TRUE;P[i][i]=TURE;} } D[v0]=0;final[v0]=TRUE; for(i=1;i {min=∞; for(j=0;j if(! final[j]) if(D[j] final[vj]=TRUE;//将顶点vj加入S for(w=0;w if(! final[w]&&(min+G.Edge[vj][w] {D[w]=min+G.Edge[vj][w]; for(j=0;j P[w][w]=TURE; } } } 6.元素的查找与排序 实验目的: 掌握文件读取与写入,常用的查找与排序的算法。 基本要求: 熟练掌握查找与排序的原理与程序实现 问题描述: 编制程序,实现: 1)键盘输入一串数值,生成二叉排序树; 2)完成6种常用排序算法中的3种(冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序)程序实现;给定一段字符串,对实现的算法进行统计关键字的移动次数和比较次数,并将结果存入文件。 考核要求: ✓问题1)中的输入格式为x,y,z,…等一串数值; ✓问题2)中的输入格式为abcd…等一段字符串。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 程序设计 专题 实验 指导书