专业课程设计任务计划书.doc

计算机科学和技术 专业课程设计任务书

学生姓名

专业班级

学号

题 目
图遍历
课题性质
其它
课题起源
自拟课题
指导老师

同组姓名

关键内容
建立图存放结构输出两种遍历

任务要求

对任意给定图（顶点数和边数自定义），建立它邻接表输出，然后利用栈五种基础运算（清空堆栈，压栈，弹出，取栈顶元素，判空栈）实现图深度搜索遍历和广度优先搜素遍历算法

参考文件

[1] 谭浩强,《C程序设计（第二版）》,北京,清华大学出版社,1月
[2] 严蔚敏,吴伟民,《数据结构（C语言版）》,北京,清华大学出版社,10月
[3] 许卓群，杨冬青等,《数据结构和算法》,高等教育出版社,
[4] 朱战立, 《数据结构》,西安电子科技大学出版社,

审查意见
指导老师签字：
教研室主任签字： 年 月 日
说明：本表由指导老师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页

课 程 设 计

课程设计名称： 数据结构
专 业 班 级 ：
学 生 姓 名 ：
学 号 ：
指 导 教 师 ：
课程设计时间：

一、需求分析
对任意给定图（顶点数和边数自定义），建立它邻接表输出，然后利用栈五种基础运算（清空堆栈，压栈，弹出，取栈顶元素，判空栈）实现图深度搜索遍历和广度优先搜素遍历算法
二、概要设计
Main()
创建邻接表存放图
输出邻接表
对图进行深度优先遍历
对图进行广度优先遍历

邻接表是图一个链式存放结构为，类似于树孩子链表表法。在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。对于无向图，第i个单链表中结点表示依靠于顶点vi边。对于有向图是以顶点vi为尾弧，这个单链表称为顶点vi单链表(即Vi邻接表)。单链表中每一个结点称为表结点，应包含两个域:邻接点域，用以存放和vi相邻接顶点序号；链域用以指向民vi邻接下一个结点。另外，每一个单链表设一个表头结点。每一个表头结点有两个域，一个用来存放顶点vi信息；另一个域用来指向vi邻接表中第一个结点。为了便于管理和随机访问任一顶点单链表，将全部单链表头结点组织成一个一维数组。
vertex
link

adjvex
next

顶点
链头

顶点地址
链针
邻接表表头和表结点形式
typedef struct node{
int adjvex;//弧指向顶点位置
struct node *next;//指向下一条弧指针
}edgenode;//表结点
typedef struct {//头结点
char vertex;//顶点信息
edgenode *link;//指向第一条依附该顶点弧指针
}vexnode,AdjList[maxvertexnum];
建立邻接表方法是：首先将邻接表表头数组初始化，第i个表头vertex初始化为i，；link初始化为NULL。然后读入顶点对<i.j>,产生一个表结点，将j放入到该结点adjvex域，将该结点链到邻接表表头Ｔ第i个表头link域上。

深度优先遍历算法
1.现将全部顶点标识为未访问
2.输出起始顶点，同时置起始顶点已访问标识
3.将起始顶点进栈
4.当栈不为空时反复实施以下步骤
a取目前栈顶顶点
b若栈顶顶点存在未被访问邻接结点，则选择一个顶点进行一下步骤：
输出该顶点
置该顶点已访问标识
将该顶点进栈
c否测目前顶点退栈
存放结构
typedef struct{//栈
int *data;//栈底指针
int *top;//栈顶指针
}seqstack;
广度优先遍历算法
1.现将全部顶点标识为未访问
2.访问选定起始顶点
3.置起始顶点已访问标识，并将该顶点入队
4.当队列不空时
a取对头顶点
b依次访问和顶点相邻未被访问顶点
访问该顶点
置该顶点为已被访问标识，并将它入队
c目前对头元素顶点出队
d反复进行直到对空时结束

三、运行环境（软、硬件环境）
Windows98操作系统.VisualC++6.0软件环境下编译运行

四、开发工具和编程语言
开发工具和编程语言：（数据结构）C语言

数据结构（c语言）
五、具体设计
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#define False 0
#define True 1
#define Null 0
#define maxsize 20//队列最大空间
#define maxvertexnum 20//最大顶点数
typedef struct node{
int adjvex;//弧指向顶点位置
struct node *next;//指向下一条弧指针
}edgenode;//表结点

typedef struct {//头结点
char vertex;//顶点信息
edgenode *link;//指向第一条依附该顶点弧指针
}vexnode,AdjList[maxvertexnum];

typedef struct{//图
AdjList adjlist;
int n,e;//n顶点数，e边数
}Graph;
typedef struct{//栈
int *data;//栈底指针
int *top;//栈顶指针
}seqstack;
//全局变量
vexnode g[maxvertexnum];//先定义后使用vexnode，邻接表g为全程变量
int visited[maxvertexnum]; //定义visit为全程向量

void CreatAdjList(Graph &G){
int i,j,k;//i,j为邻接点序号
edgenode *s;
char c;
printf("请输入定点数和边数:\n");
scanf("%d,%d",&G.n,&G.e);
c=getchar();
printf("请输入顶点信息(顶点号):\n");
for(i=1;i<=G.n;i++){//建立有n个顶点顶点表
printf("第%d个顶点为",i);
scanf("%c",&G.adjlist[i].vertex);
c=getchar();
G.adjlist[i].link=NULL;
}
printf("请输入边信息():\n");
for(k=1;k<=G.e;k++){//建立边表
printf("请输入请输入第%d条边起始顶点编号:\n",k);
scanf("%d",&i);
printf("请输入请输入第%d条边终顶点编号:\n",k);
scanf("%d",&j);
s=(edgenode*)malloc(sizeof(edgenode));//分配顶点空间
s->adjvex=j;
s->next=G.adjlist[i].link;
G.adjlist[i].link=s;
}
}

void DisplayAdjList(Graph G)
{
int i;
edgenode *q;
for(i=1;i<=G.n;++i)
{
q=G.adjlist[i].link;
printf("%d",i);
while(q!=NULL)
{
printf("->%d",q->adjvex);
q=q->next;
}
printf("\n");
}
}

void DFSAL(Graph G)
{
edgenode *p;
seqstack s;
int i=1,t;
for(i=1;i<=G.n;i++)
visited[i]=0;
printf("这是深度优先遍历,遍历次序为:\n");//输出起始顶点
s.data=(int*)malloc(maxsize*sizeof(seqstack));
s.top=s.data;//初始化栈
for(i=1;i<=G.n;i++)//考虑到图可能不连通
{
p=G.adjlist[i].link;
t=i;
if(p==NULL)//p==NULL时,即该结点没有邻结点
{
if(!visited[t])
{
printf("%c",G.adjlist[t].vertex);//假如此时该结点没有被访问过,则访问
visited[t]=True;
}
continue;//即该结点没有邻结点,此次循环结束
}
do{
if(p==NULL)//即到了图最底层
{
s.top--;//没有下个邻接点，则退回前一个顶点
p=G.adjlist[*s.top].link;
if(p!=NULL){
t=p->adjvex;
}
}
else if(!visited[t])//该结点中p!=NULL且其没有被访问过
{
printf("%c",G.adjlist[t].vertex);//输出该顶点
visited[t]=True;//置为已访问
if(G.adjlist[t].link==NULL)continue;
*s.top=t;
s.top++;//进栈
p=G.adjlist[t].link;//p指针指到以G.adjlist[t].vertex为起点第一条边,假如//p==NULL
if(p==NULL)//假如该结点没有邻接点则输出之
{
if(!visited[t])printf("%c",G.adjlist[t].vertex);
}
else t=p->adjvex;//假如该结点有邻接点,则把其邻接点顶点号赋值给t
}
else//假如该结点被访问过,且有邻结点,p指向以目前结点邻接点为起点边//也可能P=NULL

{
p=p->next;
if(p!=NULL)t=p->adjvex;//假如该邻接点有邻接点,则记下其邻接点位置
}
}while(s.top!=s.data);
}
}

void BFSAL(Graph G){
int v,Q[maxsize];
edgenode * w;
printf("这是广度优先遍历,遍历次序为:\n");
int front=0,rear=0;//辅助队列置空
for(v=1;v<=G.n;v++)
visited[v]=0;
for(v=1;v<=G.n;v++)
if(!visited[v])
{
visited[v]=1;
printf("%c",G.adjlist[v].vertex);
Q[rear]=v;
rear++; //入队
while (front!=rear)
{ //队不空
front++; //出队
w=G.adjlist[v].link;
while(w){
if(!visited[w->adjvex])
{
visited[w->adjvex]=1;// 访问w;
printf("%c",G.adjlist[w->adjvex].vertex);
Q[rear]=w->adjvex;
rear++;
}
w=w->next;
}
}
}
}

void main(){
Graph G;
int choice;
char ch;
printf("------创建邻接表存放图");
CreatAdjList(G);
printf("已创建一个图了邻接表\n");
DisplayAdjList(G)
while(ch!='n'){
printf("\n请选择操作：");
printf("\n1------深度优先遍历：");
printf("\n2------广度优先遍历");
printf("\n3-----退出\n");
scanf("%d",&choice);
switch(choice){
case 1:DFSAL(G);break;
case 2:BFSAL(G);break;
case 3:ch='n';break;
default:ch='n';
}
}
}
}
六、调试分析
在图创建过程中就碰到了问题，应为少了接收字符getchar()函数，使得再输入顶点信息（字符型）后无法再实施CreatAdjlist()中剩下语句，造成创建失败！再经同学提醒后成功创建了图。在图深度和广度遍历时，因为其出思绪不够清楚，造成在写时漏考虑了部分情况致使无法得出想要结果。在参阅了部分资料后，将思绪搞清楚后，利用非递归得到了想要结果！
七、测试结果

八、参考文件
在“课程设计汇报”最终应附上所参考相关文件，参考文件书写格式以下：
书籍：作者，书名，版本，出版地，出版者，出版年，引用内容所在页码
论文：作者，论文篇名，刊物名，年月卷，论文在刊物中页码
要求：必需独立完成，不能相互剽窃。设计完成后，将所完成工作交由老师检验。并写出一份具体实习汇报。

数据结构课程设计总结
“要想学好一门语言，就要多用它！”即使老师课上讲部分算法思绪很清楚，不过光靠课堂上部分理论知识远远不够。那些只是一个基础，只有经过自己上机调试发觉问题，处理问题才能愈加好，更深入学好这门语言，利用好这门语言！就拿这次课程设计来说，课程设计目标是培养学生综合利用所学知识,发觉,提出,分析和处理实际问题,锻炼实践能力关键步骤,是对学生实际工作能力具体训练和考察过程. 从拿到题目到完成整个编程，才短短一个星期。可是却学到很多很多东西，同时不仅能够巩固了以前所学过知识，而且增强了自己分析和调试能力。
这次我抽到题目是图遍历，这是之前一道上机题，只是要求有点不一样罢了。所以，开始准备试验比较晚，认为即使试验中碰到困难了，到时问一下同学一会就能处理。而且在写程序过程中一直把关键放在深度优先遍历和广度优先遍历那部分，认为那才是整个课题关键。可是令我没想到是，在用邻接表创建图过程中就出现问题了，在CreatAdjList()函数中，在进入创建顶点信息for循环以后，直接跳出了CreatAdjList()函数。本能去查看循环条件可是当确定循环条件没错时，真对它素手无册了。请教了多个同学，在那调试了半天也没结果。以后在机房一位常常调试程序同学，一眼便看出了问题所在。是因为少了一个接收字符getchar（）函数。照她说在部分地方增加了getchar（）函数，调试了一下，真能顺利创建了。小小快乐了一番！回去时忘保留修改稿，于是在自己电脑上改，可是怎么全部创建不成功。于是就在程序中瞎试，几乎把getchar（）在哪全部试了，最终搞了半天也不成。就在网上拼命找getchar（）函数使用方法，“getchar（）;使用方法很多： 一个就是你这个程序用到清空回车符 这种情况通常发生在在循环中包含到输入情况 ；还有一个是一些编译平台（IDE)在运行程序时并没有在程序运行后给人看结果时间 这时候 在程序最终加上getchar（）就能造成程序暂停 给程序员度结果机会”，在了解了大致使用方法后，再改，可是还是不行。以后才发觉是安装了近十二个月但却从未运行过运行环境出问题了。可是经过这次经历让我了解到了，其实假如要学好一门语言，日常部分小知识点自己也要多留心，不能忽略。因为部分看似不起眼小知识点残缺就有可能造成你程序整个无法进行下去。还有可能因为日常极少上机调试关系，在调试时碰到问题有时会有所局限，死盯着自己认为出问题局部块查错。可是往往那样盯上多个小时全部改不了那个错。
记得在网上曾看到过一篇谈论怎样学习数据结构文章：大意识这么1.假如没有学过C语言，或C语言学不好时候把数据结构当成一本数学书来学，它所讲述全部是部分简单图论。在你大脑中根本不能丢失：线性结构，树结构和图结构。当你不再考虑复杂程序设计时，仅仅研究个个离散点之间关系，似乎数据结构也就不会那么难了。2.学习好了抽象离散点关系后，再巩固一下你C语言水平，书中描述全部是类C。所以你只要学习简单C定义、判定、循环语句就基础能看懂书本中全部程序了。 3.以上全部完成后，从数据结构线性表开始。线性表中次序表似乎是为你学习C语言设计，学好线性表链表是你起步关键。后面树结构，图结构，排序，查找全部少不了链式结构，往往这个也是最难。 4.看程序时候一定要自己在纸上画画，最好先学会画程序步骤图，可能那样你学程序也就会愈加快部分。
我想我在编程中最大困难事是不知道怎样去把自己话转化成为程序。我想这可能和之前c语言没有学好有很大关系。
“数据结构”是一门专业技术基础课。它需要我们学会分析计算机加工数据结构特征，初步了解算法时间分析和空间分析，方便设计出简单实用程序。此次试验因为准备较晚，所以全部没有考虑我这个题该怎样写才能使程序简单易读，而且能够在时间和空间上节省资源。不过相信以后在这方面会做得愈加好！