数据结构课程设计 数据结构课程设计思路
大家好，关于数据结构课程设计很多朋友都还不太明白，不过没关系，因为今天小编就来为大家分享关于数据结构课程设计思路的知识点，相信应该可以解决大家的一些困惑和问题，如果碰巧可以解决您的问题，还望关注下本站哦，希望对各位有所帮助！
数据结构课程设计是什么
.需求分析
1.运行环境
硬件：计算机486/64M以上
操作系统： WIN9x以上/WIN2000/WIN XP/WIN ME
相关软件：vistualC++
2．程序所实现的功能：
（1）建立并显示图的邻接表。
（2）深度优先遍历，显示遍历结果。
（3）对该图进行拓扑排序，显示排序结果。
（4）给出某一确定顶点到所有其它顶点的最短路径。
3.程序的输入，包含输入的数据格式和说明
(1)输入顶点数,及各顶点信息(数据格式为整形)
(2)输入边数,及权值(数据格式为整形)
4.程序的输出，程序输出的形式
(1)输出图的邻接表、深度优先遍历结果、拓扑排序结果。
(2)输入某一确定顶点到其它所有顶点的最短路径。
5.测试数据
二、设计说明
1、算法设计的思想
建立图类，建立相关成员函数。最后在主函数中实现。具体成员函数的实现请参看源程序。
2、主要的数据结构设计说明
图邻接矩阵、邻接表的建立。图的深度优先遍历、拓扑排序、顶点之间的最短路径。
3、程序的主要模板template<class Type> class Graph
4、程序的主要函数
Graph、link()、DFTraverse()、TopologicalOrder()、
TopologicalOrder()、GetVertexPos()、ShortestPath
三、上机结果及体会
1、实际完成的情况说明
主要程序参考教材《数据结构——C++版》。
2、程序的性能分析
可连续建图
3、上机过程中出现的问题及其解决方案。
编译没有错误，但结果有问题。解决方案：虽然程序的编译通过，只能说明语法上没有问题，结果只所以不正确是因为算法上原因。
4、程序中可以改进的地方说明
程序中的深度优先遍历，浪费空间较大，可以考虑用循环来做。但这样将付出代码长度度加长的代价。
5、程序中可以扩充的功能及设计实现假想
实现假想：随用户的输入可以随时动态的显示图的生成。
6、收获及体会
编写程序即是一件艰苦的工作，又是一件愉快的事情。最大的收获：编程时如果遇到看似简单但又无法解决的问题，很容易灰心丧气。此时切不可烦躁，一定要冷静的思考，认真的分析。要勇敢的面对问题，勇敢的接受问题，勇敢的处理问题，最后最勇敢的解决问题。
四、参考文献
数据结构（C++版）叶核亚主编机械工业出版社
数据结构经典算法实现与习题解答汪杰编著人民邮电出版社
数据结构课程设计苏仕华编著机械工业出版社
数据结构程序设计题典李春葆编著清华大学出版社
数据结构课程与题解（用C/C++描述）胡圣荣编著北京大学出版社
[程序运行流程图]
char op//程序控制变量
求一份数据结构课程设计报告
//class CNode.h
#ifndef __CNODE_H__
#define __CNODE_H__
#include<iostream>
using namespace std;
struct stData//出生年月结构
{
int m_nYear;
int m_nMonth;
int m_nDay;
};
struct stResult//五门课成绩结构
{
double m_dSubject_1;//自己改成绩的名称
double m_dSubject_2;
double m_dSubject_3;
double m_dSubject_4;
double m_dSubject_5;
};
struct stStudent//声明学生信息的结构
{
string m_strNumber;//学生学号
string m_strName;//姓名
char m_chSex;//性别
struct stData m_stData;//出生年月
string m_strAppearance;//政治面貌
struct stResult m_stResult;//五门课成绩
};
typedef class CNode
{
private:
struct stStudent m_stStudent;
CNode* m_Next;
public:
CNode();//构造函数
~CNode();//析构函数
void SetNodeData();//设置结点内容的函数成员
stStudent GetNodeData();//获取结点内容的函数成员
void SetNodeNext(CNode* _Next);//设置结点Next指针的函数成员
void ShowNodeData();//输出结点内容的函数成员
CNode* GetNodeNext();//获取结点Next指针的函数成员
}LinkNode;
#endif
//class CLinkList
#ifndef __CLINKLIST_H__
#define __CLINKLIST_H__
#include"CNode.h"
typedef class CLinkList
{
private:
LinkNode* m_Head;//链表的头指针
LinkNode m_Node;//链表的头结点
public:
CLinkList();//构造函数
~CLinkList();//析构函数
void CreateList();//初始化链表的函数成员
LinkNode* GetListNode(int _nIndex);//按位置查找指定位结点的成员函数
void InsertList(int _nIndex);//插入结点的成员函数
void DeleteList(int _nIndex);//删除某一结点的成员函数
LinkNode* GetHeadList();//获取头指针的成员函数
void SetListData(int _nIndex);//设置链表中某一结点的值的成员函数
void ShowListData(int _nIndex);//这个是现实链表中某一结点值的函数成员
void DestroyList(int _nIndex);//销毁某一位置以后链表的成员函数
void ShowList();//显示链表的成员函数
}LinkList;
#endif
//class CLinkList
#include"CLinkList.h"
#include"CNode.h"
CLinkList::CLinkList()
{
cout<<"这个是构造函数"<< endl;
m_Head=&m_Node;//链表的头指针指向头结点
m_Node.SetNodeNext(NULL);//将头结点的Next指针设置为NULL;
}
CLinkList::~CLinkList()
{
cout<<"这个是析构函数"<< endl;
}
void CLinkList::CreateList()//以向后追加的方式创建一个链表，输入0退出
{
int nTemp= 0;//定义一个临时变量用于标志程序结束
cout<<"欢迎来创建链表!"<< endl;
CNode* pTemp= NULL;//定义一个临时结点指针，用来增加新结点用
CNode* pNode= m_Head;//定义一个标记指针，首先叫其指向头结点
while(1)
{
pTemp= new LinkNode;
cout<<"请输入下一个结点的内容!"<< endl;
pTemp->SetNodeData();//设置链表中结点的内容
cout<<"如果想继续输入下一个学生的信息请输入 1，否则输入 0"<< endl;
cin>> nTemp;
if('0'== nTemp)
{
break;
}
pNode->SetNodeNext(pTemp);//让链尾的Next指向新建的结点
pNode= pTemp;//将结尾元素向后移
}
cout<<"创建链表结束"<< endl;
}
LinkNode* CLinkList::GetListNode(int _nIndex)
{
cout<<"这个是按位置查找指定位结点的成员函数"<< endl;
LinkNode* pNode= m_Head->GetNodeNext();//定义一个临时的结点指针,初始化指向头结点
int Temp= 0;//定义一个临时的变量，用来标记已检查结点的个数的
if(-1== _nIndex)//返回头结点（即头指针）
{
return m_Head;
}
if(_nIndex<-1)//_nIndex控制条件
{
cout<<"您输入的是错误的位置！"<< endl;
return 0;
}
while(pNode!= NULL)
{
if(_nIndex== Temp)
{
return pNode;
}
pNode= pNode->GetNodeNext();//临时结点向后移动
++Temp;
}
return pNode;//没找到结点就返回NULL
}
void CLinkList::ShowListData(int _nIndex);
void CLinkList::InsertList(int _nIndex)//插入结点的函数成员
{
cout<<"这个是插入结点的成员函数"<< endl;
LinkNode* pNode= GetListNode(_nIndex- 1);//定义一个结点类的指针，指向的是要插入位置的前一指针
LinkNode* pTemp= new CNode;//定义一个临时结点指针，用来增加新结点用
pTemp->SetNodeData();//设置插入结点的内容
pTemp->SetNodeNext(pNode->GetNodeNext());
pNode->SetNodeNext(pTemp);
}
void CLinkList::DeleteList(int _nIndex)
{
cout<<"这个是删除某一结点的成员函数"<< endl;
LinkNode* pNode= GetListNode(_nIndex- 1);//定义一个结点类的指针，指向的是要删除位置的前一指针
LinkNode* pTemp= NULL;//定义一个临时结点指针，用来指向要删除的结点
pTemp=pNode->GetNodeNext();//把pTemp指向要删除的结点
pNode->SetNodeNext(pTemp->GetNodeNext());//把pNode指向要删除的结点的后一个结点
delete pTemp;//删除结点
pTemp= NULL;
}
LinkNode* CLinkList::GetHeadList()
{
cout<<"这个是获取头指针的成员函数"<< endl;
return m_Head;
}
void CLinkList::SetListData(int _nIndex)
{
cout<<"这个是设置链表中某一结点的值的成员函数"<< endl;
CNode*pNode= GetListNode(_nIndex);//定义一个结点类的指针，指向的是要修改内容位置的结点
pNode->SetNodeData();//修改内容
}
void CLinkList::ShowListData(int _nIndex)
{
cout<<"这个是显示链表中某一结点值的成员函数"<< endl;
CNode*pNode= GetListNode(_nIndex);//定义一个结点类的指针，指向的是要获取内容位置的结点
pNode->ShowNodeData();//返回想要得到位置的结点内容
}
void CLinkList::DestroyList(int _nIndex)
{
cout<<"这个是销毁某一位置以后链表的成员函数"<< endl;
LinkNode* pTemp= GetListNode(_nIndex- 1);//定义一个结点指针，指向要销毁位置的前一结点
LinkNode* pNode= pTemp->GetNodeNext();//定义一个结点指针，指向要销毁位置的结点
while(pTemp->GetNodeNext()!= NULL)//销毁动作的结束条件或初始条件
{
pTemp->SetNodeNext(pNode->GetNodeNext());//把需要销毁的位置的前结点的Next指向销毁位置的下一个结点
delete pNode;//销毁结点
pNode= pTemp->GetNodeNext();//把pNode重新指向要销毁位置的结点
}
}
void CLinkList::ShowList()
{
cout<<"这个是显示链表的成员函数"<< endl;
int nTemp= 0;//定义一个临时的整形变量用来控制输入的个数
LinkNode* pTemp= m_Head->GetNodeNext();//定义一个结点类指针，指向第0位的结点
if(NULL== pTemp)
{
cout<<"这是个空链"<< endl;
}
while(pTemp!= NULL)
{
pTemp->ShowNodeData();
++nTemp;
if(0== nTemp% 5&& nTemp!= 0)//控制每行只能输出5个结点的内容
{
cout<< endl;
}
pTemp= pTemp->GetNodeNext();
}
}
//class CNode
#include"CNode.h"
CNode::CNode()//构造函数
{
//m_stStudent={0};
m_Next= NULL;
}
CNode::~CNode()//析构函数
{
}
void CNode::SetNodeData()
{
char* pNumber= new char[30];//用来接收字符串的临时变量
char* pName= new char[30];
char* pAppearance= new char[30];
cout<<"学生学号:"<< endl;
cin>> pNumber;
m_stStudent.m_strNumber= pNumber;
cout<<"姓名:"<< endl;
cin>> pName;
m_stStudent.m_strName= pName;
cout<<"性别:"<< endl;
cin>> m_stStudent.m_chSex;
cout<<"出生年月:"<< endl;
cout<<"m_stData.m_nYear"<< endl;
cin>> m_stStudent.m_stData.m_nYear;
cout<<"m_stData.m_nMonth"<< endl;
cin>> m_stStudent.m_stData.m_nMonth;
cout<<"m_stData.m_nDay"<< endl;
cin>> m_stStudent.m_stData.m_nDay;
cout<<"政治面貌:"<< endl;
cin>> pAppearance;
m_stStudent.m_strAppearance= pAppearance;
cout<<"五门课成绩:"<< endl;
cout<<"m_dSubject_1:"<< endl;
cin>> m_stStudent.m_stResult.m_dSubject_1;
cout<<"m_dSubject_2:"<< endl;
cin>> m_stStudent.m_stResult.m_dSubject_2;
cout<<"m_dSubject_3:"<< endl;
cin>> m_stStudent.m_stResult.m_dSubject_3;
cout<<"m_dSubject_4:"<< endl;
cin>> m_stStudent.m_stResult.m_dSubject_4;
cout<<"m_dSubject_5:"<< endl;
cin>> m_stStudent.m_stResult.m_dSubject_5;
delete []pNumber;//释放内存
pNumber= NULL;//指针置空
delete []pName;//释放内存
pName= NULL;
delete []pAppearance;//释放内存
pAppearance= NULL;
}
stStudent CNode::GetNodeData()//返回结点内容（即学生信息）
{
return m_stStudent;
}
void CNode::SetNodeNext(CNode* _Next)
{
m_Next= _Next;
}
void CNode::ShowNodeData()
{
const char* pNumber= m_stStudent.m_strNumber.c_str();//用来接收字符串的临时变量
const char* pName= m_stStudent.m_strNumber.c_str();
const char* pAppearance= m_stStudent.m_strAppearance.c_str();
cout<<"学生学号:"<< pNumber<<'\t'<<"姓名:"<< pName<<'\t'<<"性别:"<< m_stStudent.m_chSex;
cout<<"出生年月:"<< m_stStudent.m_stData.m_nYear<<','<< m_stStudent.m_stData.m_nMonth<<','<< m_stStudent.m_stData.m_nDay;
cout<<"政治面貌:"<< pAppearance<<"五门课成绩:"<< endl;
cout<<"m_dSubject_1:"<< m_stStudent.m_stResult.m_dSubject_1<< endl;
cout<<"m_dSubject_2:"<< m_stStudent.m_stResult.m_dSubject_2<< endl;
cout<<"m_dSubject_3:"<< m_stStudent.m_stResult.m_dSubject_3<< endl;
cout<<"m_dSubject_4:"<< m_stStudent.m_stResult.m_dSubject_4<< endl;
cout<<"m_dSubject_5:"<< m_stStudent.m_stResult.m_dSubject_5<< endl;
}
CNode* CNode::GetNodeNext()
{
return m_Next;
}
#include"CLinkList.h"
#include"CNode.h"
void Text();//测试函数声明
int main()
{
cout<<"这是mian函数"<< endl;
Text();
return 0;
}
void Text()
{
cout<<"这个是测试函数"<< endl;
LinkList* pList= new LinkList;//创建一个内存链表对象
cout<<"------------------CreateList-----------------------------"<< endl;
pList->CreateList();//初始化链表的函数成员
pList->ShowList();
cout<< endl;
cout<<"------------------GetListNode-----------------------------"<< endl;
LinkNode* pNode= NULL;//定义一个临时的结点类指针用于检测查找函数成员
pNode= pList->GetListNode(3);//按位置查找指定位结点的成员函数的测试
if(pNode)
{
cout<<"用按位置查找的方法找到了指定位结点"<< endl;
}
else
{
cout<<"对不起，用按位置查找的方没有找到指定位结点"<< endl;
}
cout<< endl;
cout<<"------------------InsertList-----------------------------"<< endl;
pList->InsertList(0);//插入结点的成员函数的测试
pList->ShowList();
cout<< endl;
cout<<"------------------DeleteList-----------------------------"<< endl;
pList->DeleteList(0);//删除某一结点的成员函数的测试
pList->ShowList();
cout<< endl;
cout<<"------------------GetHeadList-----------------------------"<< endl;
pNode= NULL;
pNode= pList->GetHeadList();//获取头指针的成员函数的测试
if(pNode)
{
cout<<"已经返回了头指针"<< endl;
}
else
{
cout<<"对不起，头指针为空"<< endl;
}
cout<< endl;
cout<<"------------------GetHeadList-----------------------------"<< endl;
pList->SetListData(3);//设置链表中某一结点的值的成员函数的测试
pList->ShowList();
cout<< endl;
cout<<"------------------GetListData-----------------------------"<< endl;
cout<<"pList->ShowListData(3)=";
pList->ShowListData(3);//获取链中某一结点值的成员函数的测试
cout<< endl;
cout<<"------------------DestroyList(3)-----------------------------"<< endl;
pList->DestroyList(3);//销毁第3位置以后链表的成员函数的测试
pList->ShowList();
cout<< endl;
cout<<"------------------DestroyList(0)-----------------------------"<< endl;
pList->DestroyList(0);//销毁第0位置以后链表的成员函数的测试
pList->ShowList();
cout<< endl;
delete pList;//释放内存
pList= NULL;//指针置空
}
你的要求太多，没仔细看，我把我给别人写的赋值给你吧，我已经写的很全了，程序有问题可以给我留言
急!!!数据结构课程设计
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 30//最大顶点数
#define INFINITY 10000000//无穷大
typedef struct ArcCell{
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
char vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
//查询顶点位置
int LocateVex(MGraph G,char v){
int i=0;
while(G.vexs[i]!=v&&i<G.vexnum)
i++;
return i;
}
//创建图的邻接矩阵
MGraph CreateMGraph(){
MGraph G;
int i,j,k;
int w;
char v1,v2;
cout<<"请输入图的顶点数：";
cin>>G.vexnum;
cout<<"请输入图的弧数：";
cin>>G.arcnum;
for(i=0;i<G.vexnum;i++){
cout<<"请输入第"<<i+1<<"个顶点：";
cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=INFINITY;
for(k=0;k<G.arcnum;k++){
cout<<"请输入弧"<<k+1<<"所关联的顶点和权值：";
cin>>v1>>v2>>w;
if(LocateVex(G,v1)<G.vexnum)
i=LocateVex(G,v1);
else{
cout<<"没有找到此顶点！"<<endl;
k--;
continue;
}
if(LocateVex(G,v2)<G.vexnum)
j=LocateVex(G,v2);
else{
cout<<"没有找到此顶点！"<<endl;
k--;
continue;
}
G.arcs[i][j].adj=w;
G.arcs[j][i]=G.arcs[i][j];
}
cout<<"MGraph创建成功！"<<endl;
return G;
}
//……………………输出MGraph…………………
void PrintMGraph(MGraph G){
cout<<"图的邻接矩阵"<<endl;
int i,j;
for(i=0;i<G.vexnum;i++)
cout<<""<<G.vexs[i];
cout<<endl;
for( i=0;i<G.vexnum;i++){
cout<<G.vexs[i]<<"";
for( j=0;j<G.vexnum;j++){
if(G.arcs[i][j].adj!=INFINITY)
cout<<G.arcs[i][j].adj<<"";
else
cout<<"∞"<<"";
}
cout<<endl;
}
cout<<"--------------------------------------------"<<endl;
}
//……………………求各个顶点的度…………………
void Vdu(MGraph G){//求各个顶点的度
int i,j;
int V[20];
for(i=0;i<G.vexnum;i++){
int count=0;
for(j=0;j<G.vexnum;j++)
if(G.arcs[i][j].adj!=INFINITY)
count++;
V[i]=count;
}
for(i=0;i<G.vexnum;i++)
cout<<endl<<"第"<<i+1<<"个顶点"<<G.vexs[i]<<"的度为："<<V[i]<<endl;
}
//……………………插入顶点…………………
void InsertVex(MGraph&G){
char v;
int i,j;
cout<<"请输入你想插入的顶点：";
cin>>v;
i=G.vexnum++;
G.vexs[i]=v;
for(j=0;j<G.vexnum;j++)
G.arcs[i][j].adj=INFINITY;
j=G.vexnum-1;
for(i=0;i<G.vexnum;i++)
G.arcs[i][j].adj=INFINITY;
cout<<endl<<"插入成功！"<<endl;
}
//……………………插入弧…………………
void InsertArc(MGraph&G){
char v1,v2;
int i,j,w;
cout<<"请输入你要插入的弧所关联的顶点和权值：";
cin>>v1>>v2>>w;
if(LocateVex(G,v1)<G.vexnum&&LocateVex(G,v2)<G.vexnum){
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i]=G.arcs[i][j];
cout<<endl<<"插入成功！"<<endl;
}else{
cout<<"没有找到关联的顶点！"<<endl;
}
}
//……………………删除顶点…………………
void DeleteVex(MGraph&G){
int i,j;
char v;
cout<<"请输入你所要删除的顶点：";
cin>>v;
if(LocateVex(G,v)<G.vexnum){
int l=LocateVex(G,v);
for(i=l;i<G.vexnum-1;i++)
G.vexs[i]=G.vexs[i+1];
for(i=l;i<G.vexnum-1;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=G.arcs[i+1][j];
for(i=0;i<G.vexnum;i++)
for(j=l;j<G.vexnum-1;j++)
G.arcs[i][j]=G.arcs[i][j+1];
G.vexnum--;
cout<<"已成功删除此顶点！"<<endl;
}else
cout<<"没有此顶点！"<<endl;
}
//……………………删除弧…………………
void DeleteArc(MGraph&G){
int i,j;
char v1,v2;
cout<<"请输入你要删除的弧所关联的顶点";
cin>>v1>>v2;
if(LocateVex(G,v1)<G.vexnum&&LocateVex(G,v2)<G.vexnum){
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j].adj=INFINITY;
G.arcs[j][i]=G.arcs[i][j];
cout<<"已成功删除此弧！"<<endl;
}else
cout<<"没有找到此弧所关联的顶点！"<<endl;
}
typedef struct ArcNode{
int adjvex;
struct ArcNode*nextarc;
}ArcNode;
typedef struct vnode{
char data;
ArcNode*firstarc;
}vnode,adjlist;
typedef struct{
adjlist vertices[MAX_VERTEX_NUM];
int vexnum,arcnum;
}ALGraph;
//……………………创建图的邻接表…………………
ALGraph CreateUDG(MGraph G){
ALGraph gra;
int i,j;
ArcNode*arc,*tem,*p;
for(i=0;i<G.vexnum;i++){
gra.vertices[i].data=G.vexs[i];
gra.vertices[i].firstarc=NULL;
}
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++){
if(gra.vertices[i].firstarc==NULL){
if(G.arcs[i][j].adj!=INFINITY){
arc=(ArcNode*)malloc(sizeof(ArcNode));
arc->adjvex=j;
gra.vertices[i].firstarc=arc;
arc->nextarc=NULL;
p=arc;
j++;
while(G.arcs[i][j].adj!=INFINITY&&j<G.vexnum){
tem=(ArcNode*)malloc(sizeof(ArcNode));
tem->adjvex=j;
gra.vertices[i].firstarc=tem;
tem->nextarc=arc;
arc=tem;
j++;
}
}
}else{
if(G.arcs[i][j].adj!=INFINITY){
arc=(ArcNode*)malloc(sizeof(ArcNode));
arc->adjvex=j;
p->nextarc=arc;
arc->nextarc=NULL;
p=arc;
}
}
}
}
gra.vexnum=G.vexnum;
gra.arcnum=G.arcnum;
cout<<"ALGraph创建成功！"<<endl;
return gra;
}
//……………………输出ALGraph…………………
void PrintUDG(ALGraph gra){
int i;
ArcNode*p;
cout<<"图的各顶点为："<<endl;
for(i=0;i<gra.vexnum;i++)
cout<<gra.vertices[i].data<<"";
cout<<endl;
cout<<"图的邻接表为："<<endl;
for(i=0;i<gra.vexnum;i++){
cout<<i<<""<<gra.vertices[i].data;
p=gra.vertices[i].firstarc;
while(p){
cout<<"->"<<p->adjvex;
p=p->nextarc;
}
cout<<endl;
}
}
//……定义全局变量……
int visited[MAX_VERTEX_NUM];
int we;
//……求第一个邻接点……
int firstadjvex(ALGraph gra,vnode v){
if(v.firstarc!=NULL)
return v.firstarc->adjvex;
else
return-1;
}
//……求相对于w的下一个邻接点
int nextadjvex(ALGraph gra,vnode v,int w){
ArcNode*p;
p=v.firstarc;
while(p!=NULL&&p->adjvex!=w){
p=p->nextarc;
}
if(p->adjvex==w&&p->nextarc!=NULL){
p=p->nextarc;
return p->adjvex;
}else
return-1;
}
//……………………图的深度优先遍历…………………
void DFS(ALGraph gra,int i){
visited[i]=1;
int we1;
cout<<gra.vertices[i].data<<"";
for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we)){
we1=we;
if(visited[we]==0)
DFS(gra,we);
we=we1;
}
}
void DFSTravers(ALGraph gra){
int i;
for(i=0;i<gra.vexnum;i++){
visited[i]=0;
}
for(i=0;i<gra.vexnum;i++){
if(visited[i]==0)
DFS(gra,i);
}
cout<<endl;
}
//…………………………………………………………………
//……………………队列定义和基本操作……………………
typedef struct qnode{
int data;
struct qnode*next;
}qnode,*queueptr;
typedef struct{
queueptr front;
queueptr rear;
}linkqueue;
//……初始化队列………
void initqueue(linkqueue&q){
q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
q.front->next=NULL;
}
//……入队列………
int enqueue(linkqueue&q,int e){
queueptr p;
p=(queueptr)malloc(sizeof(qnode));//系统生成qnode节点并赋予p
if(!p)
return 0;
else{
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
}
//……出队列……
int dequeue(linkqueue&q,int&e){
queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}
//……判断队列是否为空……
int queueempty(linkqueue q){
if(q.front==q.rear)
return 1;
return 0;
}
//………………………………………………………………………
//……………………图的广度优先遍历…………………
void BFSTravers(ALGraph gra){
int i,e;
linkqueue q;
for(i=0;i<gra.vexnum;i++)
visited[i]=0;
initqueue(q);//附设队列存储已经被访问的路径长度为1 2...的顶点
for(i=0;i<gra.vexnum;i++)
if(!visited[i]){
visited[i]=1;
cout<<gra.vertices[i].data<<"";
enqueue(q,i);
while(!queueempty(q)){
dequeue(q,e);
for(we=firstadjvex(gra,gra.vertices[e]);we>=0;we=nextadjvex(gra,gra.vertices[e],we)){
if(!visited[we]){
visited[we]=1;
cout<<gra.vertices[we].data<<"";
enqueue(q,we);
}
}
}
}
cout<<endl;
}
//……………………求图的连通分支…………………
void DFSTraversFL(ALGraph gra){
int i,count=1;
for(i=0;i<gra.vexnum;i++){
visited[i]=0;
}
for(i=0;i<gra.vexnum;i++){
if(visited[i]==0){
cout<<"第"<<count<<"个连通分支为：";
DFS(gra,i);//对连通图，只需从一个顶点出发深度优先遍历即可访问所有顶点
cout<<endl;
count++;
}
}
}
//……………………用普里姆算法求最小生成树…………………
void PRIM(ALGraph gra,int g[][MAX_VERTEX_NUM],int n){
int lowcost[MAX_VERTEX_NUM],prevex[MAX_VERTEX_NUM];
int i,j,k,min;
for(i=2;i<=n;i++){
lowcost[i]=g[1][i];
prevex[i]=1;
}
lowcost[1]=0;
for(i=2;i<=n;i++){
min=INFINITY;
k=0;
for(j=2;j<=n;j++)
if(lowcost[j]<min&&lowcost[j]!=0){
min=lowcost[j];
k=j;
}
cout<<gra.vertices[prevex[k]-1].data<<""<<gra.vertices[k-1].data<<""<<min;
lowcost[k]=0;
for(j=2;j<=n;j++)
if(g[k][j]<lowcost[j]){
lowcost[j]=g[k][j];
prevex[j]=k;
}
cout<<endl;
}
}
//…………求最短路径…………
void ShortPath(MGraph G,char ch){//迪杰斯特拉算法实现，某点到其余各点
int i,j,min,k,t,w;
int v=0;
int final[MAX_VERTEX_NUM];
int lowcost[MAX_VERTEX_NUM];
int q[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
k=LocateVex(G,ch);
for(i=0;i<G.vexnum;i++){
final[i]=0;
lowcost[i]=G.arcs[k][i].adj;
for(j=0;j<G.vexnum;j++)
q[i][j]=0;
if(lowcost[i]<INFINITY){
q[i][k]=1;
q[i][i]=1;
}
}
lowcost[k]=0;
final[k]=1;
for(i=0;i<G.vexnum;i++){
min=INFINITY;
for(j=0;j<G.vexnum;j++)
if(!final[j])
if(lowcost[j]<min){
min=lowcost[j];
v=j;
}
final[v]=1;
for(w=0;w<G.vexnum;w++)
if(!final[w]&&(min+G.arcs[v][w].adj<lowcost[w])){
lowcost[w]=min+G.arcs[v][w].adj;
for(t=0;t<G.vexnum;t++)
q[w][t]=q[v][t];
q[w][w]=1;
}
}
for(i=0;i<G.vexnum;i++){
if(i!=k){
cout<<ch<<" to"<<G.vexs[i]<<endl;
cout<<"最短路径：";
if(lowcost[i]<INFINITY){
for(j=0;j<G.vexnum;j++)
if(q[i][j]&&j!=i)
cout<<G.vexs[j]<<"";
cout<<G.vexs[i];
cout<<"长度："<<lowcost[i]<<endl;
}else
cout<<"不存在！"<<endl;
}
}
}
typedef struct CSNode{
char data;
struct CSNode*firstchild,*nextsibling;
}CSNode,*CSTree;
//……………………深度优先生成树…………………
void DFSTree(ALGraph gra,int v,CSTree&T){//深度优先搜索后顺序输出
visited[v]=1;
int w,first=1;
CSTree p,q;
for(w=firstadjvex(gra,gra.vertices[v]);w>=0;w=nextadjvex(gra,gra.vertices[v],w))
if(!visited[w]){
p=(CSTree)malloc(sizeof(CSNode));
p->data=gra.vertices[w].data;
p->firstchild=NULL;
p->nextsibling=NULL;
if(first){
T->firstchild=p;
first=0;
}else
q->nextsibling=p;
q=p;
DFSTree(gra,w,q);
}
}
void DFSForest(ALGraph gra,CSTree&T){
T=NULL;
CSTree p,q;
int v;
for(v=0;v<gra.vexnum;v++)
visited[v]=0;
for(v=0;v<gra.vexnum;v++)
if(!visited[v]){
p=(CSTree)malloc(sizeof(CSNode));
p->data=gra.vertices[v].data;
p->firstchild=NULL;
p->nextsibling=NULL;
if(!T)
T=p;
else
q->nextsibling=p;
q=p;
DFSTree(gra,v,p);
}
}
//……………………先序遍历深度优先生成树…………………
void Preorder(CSTree T){
if(T){
cout<<T->data<<"";
Preorder(T->firstchild);
Preorder(T->nextsibling);
}
cout<<endl;
}
//……………………求u到v之间的最短路径…………………
void shortestdistance(MGraph G){
int i,u,v,w,S,E;
char start,end;
int Distance[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
cout<<"请输入两个顶点：";
cin>>start>>end;
while(LocateVex(G,start)>=G.vexnum||LocateVex(G,end)>=G.vexnum){
cout<<"没有找到关联的顶点！请重新输入：";
cin>>start>>end;
}
for(i=0;i<G.vexnum;i++)
G.arcs[i][i].adj=0;
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
Distance[u][v]=G.arcs[u][v].adj;
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(Distance[u][w]+Distance[w][v]<Distance[u][v])
Distance[u][v]=Distance[u][w]+Distance[w][v];
S=LocateVex(G,start);
E=LocateVex(G,end);
if(Distance[S][E]==INFINITY)
cout<<start<<"到"<<end<<"的最短路径不存在！"<<endl;
else
cout<<start<<"到"<<end<<"的最短路径为："<<Distance[S][E]<<endl;
}
//……………………求所有顶点之间的最短路径…………………
void shortdistance(MGraph G){//弗洛依德算法实现，任意两顶点
int i,j,u,v,w;
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
for(i=0;i<G.vexnum;i++)
G.arcs[i][i].adj=0;
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
D[u][v]=G.arcs[u][v].adj;
for(u=0;u<G.vexnum;u++)
for(v=0;v<G.vexnum;v++)
for(w=0;w<G.vexnum;w++)
if(D[u][w]+D[w][v]<D[u][v])
D[u][v]=D[u][w]+D[w][v];
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(D[i][j]==INFINITY)
cout<<G.vexs[i]<<"到"<<G.vexs[j]<<"的最短路径不存在！"<<endl;
else
cout<<G.vexs[i]<<"到"<<G.vexs[j]<<"的最短路径为："<<D[i][j]<<endl;
}
void main(){
int i,j;
char ch='y';
MGraph G;
G.vexnum=0;
ALGraph gra;
gra.vexnum=0;
int t[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
CSTree T=NULL;
while(ch=='y'){
cout<<"************************************************************"<<endl;
cout<<" MENU"<<endl;
cout<<"************************************************************"<<endl;
cout<<""<<"1|利用邻接矩阵创建图"<<endl;
cout<<""<<"2|显示图的邻接矩阵"<<endl;
cout<<""<<"3|求各顶点的度"<<endl;
cout<<""<<"4|插入顶点"<<endl;
cout<<""<<"5|插入弧"<<endl;
cout<<""<<"6|删除顶点"<<endl;
cout<<""<<"7|删除弧"<<endl;
cout<<""<<"8|用邻接矩阵创建邻接表UDG"<<endl;
cout<<""<<"9|显示图的邻接表"<<endl;
cout<<""<<"10|深度优先便利序列"<<endl;
cout<<""<<"11|广度优先便利序列"<<endl;
cout<<""<<"12|图的连通分支"<<endl;
cout<<""<<"13|求连通图最小生成树"<<endl;
cout<<""<<"14|求任意顶点到其它顶点的最短路径"<<endl;
cout<<""<<"15|求图的深度优先生成树"<<endl;
cout<<""<<"16|对生成树进行先序遍历"<<endl;
cout<<""<<"17|求两点间的最短路径"<<endl;
cout<<""<<"18|求所有点之间的最短路径"<<endl;
cout<<""<<"0|退出！"<<endl;
cout<<"***********************************************************"<<endl;
cout<<endl<<"请选择你要进行的操作：";
cin>>i;
switch(i){
case 1:
if(G.vexnum==0)
G=CreateMGraph();
else
cout<<"MGraph已经创建！"<<endl;
break;
case 2:
if(G.vexnum!=0)
PrintMGraph(G);
else
cout<<"MGraph为空！"<<endl;
break;
case 3:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
Vdu(G);
break;
case 4:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
InsertVex(G);
break;
case 5:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
InsertArc(G);
break;
case 6:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
DeleteVex(G);
break;
case 7:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
DeleteArc(G);
break;
case 8:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else{
gra=CreateUDG(G);
}
break;
case 9:
if(gra.vexnum!=0)
PrintUDG(gra);
else
cout<<"UDG为空！"<<endl;
break;
case 10:
if(gra.vexnum!=0){
cout<<"图的深度优先遍历序列为：";
DFSTravers(gra);
}
else
cout<<"请先创建ALGraph！"<<endl;
break;
case 11:
if(gra.vexnum!=0){
cout<<"图的广度优先遍历序列为：";
BFSTravers(gra);
}
else
cout<<"请先创建ALGraph！"<<endl;
break;
case 12:
if(gra.vexnum!=0){
cout<<"图的连通分支如下："<<endl;
DFSTraversFL(gra);
}
else
cout<<"请先创建ALGraph！"<<endl;
break;
case 13:
if(gra.vexnum!=0){
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
t[i+1][j+1]=G.arcs[i][j].adj;
cout<<"图的最小生成树为："<<endl;
PRIM(gra,t,G.vexnum);
}
else
cout<<"请先创建ALGraph！"<<endl;
break;
case 14:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else{
char ch;
cout<<"请选择一个顶点：";
cin>>ch;
while(LocateVex(G,ch)>=G.vexnum){
cout<<"没有找到此顶点！请重新选择一个顶点：";
cin>>ch;
}
ShortPath(G,ch);
}
break;
case 15:
if(gra.vexnum==0)
cout<<"请先创建ALGraph！"<<endl;
else
DFSForest(gra,T);
break;
case 16:
if(!T)
cout<<"请先求深度优先生成树！"<<endl;
else{
Preorder(T);
cout<<"深度优先生成树已成功创建！"<<endl;
}
break;
case 17:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
shortestdistance(G);
break;
case 18:
if(G.vexnum==0)
cout<<"请先创建MGraph！"<<endl;
else
shortdistance(G);
break;
case 0:
exit(1);
default:
cout<<"请在0~18之间进行选择！"<<endl;
}
cout<<"是否继续y/n：";
cin>>ch;
system("cls");
}
}
OK，关于数据结构课程设计和数据结构课程设计思路的内容到此结束了，希望对大家有所帮助。