数据结构与程序设计专题实验指导书Word格式.docx
《数据结构与程序设计专题实验指导书Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构与程序设计专题实验指导书Word格式.docx（19页珍藏版）》请在冰点文库上搜索。
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创建应用程序框架
（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）;
}//EnQueue;
StatusDeQueue（SqQueue&
Q,QElemType&
e）
{if（Q.rear==Q.front）
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
}//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）//构造赫夫曼树
{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;
=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）;
=G.arcnum;
k++）//输入边，建立边链表
x1,&
x2）;
i=Locatevex（G,x1）;
j=Locatevex（G,x2）;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->
adjvex=j;
nextarc=G.vextices[i].firstarc;
G.vextices[i].firstarc=p;
//插入到顶点i的边链表
adjvex=i;
nextarc=G.vextices[j].firstarc;
G.vextices[j].firstarc=p;
//插入到顶点j的边链表
在以上函数中需要注意每个边结点中需要将权值也存储起来。
2）图的深度优先遍历（递归）：
voidDFSTraverse（GraphG）
{for（k=1;
++k）visited[k]=FALSE;
for（k=1;
++k）
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））
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&
&
adjvex!
=w）p=p->
nextarc;
if（p->
adjvex==w&
nextarc）return（p->
nextarc->
elsereturn（0）;
3）图的广度优先遍历（采用队列的数据结构）：
voidBFSTraverse（GraphG）
{for（v=1;
v<
++v）visited[v]=FALSE;
InitQueue（Q）;
for（v=1;
++v）
visited[v]）
{visited[v]=TRUE;
VISIT（v）;
EnQueue（Q,v）;
while（!
EmptyQueue（Q））
{DeQueue（Q,u）;
for（w=FirstAdjVex（G,u）;
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<
j++）//初始化辅助数组closedge
if（j!
=k）closedge[j]={u,G.Edge[k][j]};
closedge[k].lowcost=0;
//初始时U={u}
for（i=1;
G.vexnum;
i++）
{min=∞;
k=0;
//查找U到V-U中的权值最小的边
j++）
if（closedge[j].lowcost>
0&
closedge[j].lowcost<
min）
{k=j;
min=closedge[j].lowcost;
printf（closedge[k].adjvex,G.vexs[k]）;
//输出该边
//顶点k并入U
for（j=1;
j++）//修改V-U中每个顶点到U的最小边
if（G.Edge[k][j]<
closedge[j].lowcost）
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++）P[i][j]=FALSE;
if（D[i]<
∞）{P[i][v0]=TRUE;
P[i][i]=TURE;
D[v0]=0;
final[v0]=TRUE;
i++）//主循环，每次求一个v到v0的最短路径
j++）//求当前的最短路径的终点vj
final[j]）
if（D[j]<
min）{vj=j;
min=D[j];
final[vj]=TRUE;
//将顶点vj加入S
for（w=0;
w<
w++）//更新当前的最短路径及长度
final[w]&
（min+G.Edge[vj][w]<
D[w]））
{D[w]=min+G.Edge[vj][w];
for（j=0;
j++）P[w][j]=P[vj][j];
//P[w]=P[vj]，若到w，则首先到vj
P[w][w]=TURE;
6.元素的查找与排序
掌握文件读取与写入，常用的查找与排序的算法。
熟练掌握查找与排序的原理与程序实现
编制程序，实现：
1）键盘输入一串数值，生成二叉排序树；
2）完成6种常用排序算法中的3种（冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序）程序实现；
给定一段字符串，对实现的算法进行统计关键字的移动次数和比较次数，并将结果存入文件。
✓问题1）中的输入格式为x,y,z,…等一串数值；
✓问题2）中的输入格式为abcd…等一段字符串。
升级会员 