图的基本操作及应用

武  夷  学  院 

课程设计报告

课程设计项目研究报告

目  录

第 1 章  项目简介    3

1.1 项目名称    3

1.2 开发人员    3

1.3 指导教师    3

第 2 章  项目研究意义    3

2.1 课程设计概述    3

第3章  课程设计项目进度表    5

第4 章  课程设计任务分配表    5

第5 章  达到的效果    6

               图5—1    6

5．2 图的数据类型定义表    7

第6 章  源程序    17

第7 章  附录    28

（1）  图的基本操作及应用    28

（2）二叉树的遍历    29

第8 章  设计心得    29

第9 章  参考文献    30

第 1 章  项目简介

1.1 项目名称

（1）图的基本操作及应用

（2）二叉树的遍历

1.2 开发人员

1.3 指导教师

第 2 章  项目研究意义

2.1 课程设计概述

（1）图是一种比树更为复杂的一些的非线性结构。在图状结构中，任意两个结点之间都可能具有邻接关系，也就是在图的数据元素之间存在多对多的关系。所以图状结构可以描述任意结点之间的关系，例如各种线性结构和树形结构，这些都可以看做图这种结构的特例。于是，从某种意义上讲，图应该是一种最基本的数据结构。

图是一种应用极为广泛的数据结构。比如，在供电网络分析、交通运输管理、市政管线铺设、工作进度安排等诸多方面，都常采用图状结构来模拟各种复杂的数据对象。当前，它的应用已经渗透到了计算机科学、社会科学、人文科学、工程技术等各个领域。

本设计基于图的结构，创建一个无向图，基于设计要求，我们对要求进行编号，让用户可以自由选择操作，我们可以将各个顶点的数据域储存所需的信息，可以用深度遍历或者广度遍历对信息进行访问，也可以删除顶点的数据。这对于很多操作系统都是很需要的。

1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历 用栈实现非递归的前序、和后序遍历 还有对树的层序遍历以及树与二叉树的转换。  

（2）本程序要求用户以字符输入 若要实现终端结点 最后以回车键建入数据。 本程序的结果将依次打印出递归前序遍历和后序遍历 用栈实现非递归的前序和中序遍历和后序遍历 和线索化层序遍历 输入树及树传换成二叉树。

2.2 需求分析及研究意义

（1）具备“数据结构”这门课程的扎实基础，尤其是对图论知识的掌握，对于学习计算机专业的其他课程，如操作系统、数据库管理系统、软件工程、编译原理、人工智能、图视学等都是十分有益的。图的操作运用于计算机的许多领域，是不可缺少的结构体。对如今的计算机时代而言，图结构的运用将涉及人工智能化的许多方面。

数据结构是计算机科学与技术专业、计算机信息管理与应用专业，电子商务等专业的基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。.

（2）问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）条件是什么？ 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。编写课程设计报告并提交相关内容

第3章  课程设计项目进度表

程序设计思想

5.1 程序设计思想：                                                                            （1）把图的要实现的功能用菜单的形式表示出来，并由图的创建为工具，一次实现图的一些基本功能，结构框架如图5—1

                                                图5—1                                            

（2）创建二叉树，建立二叉链表存储结构，并且利用栈的五种基本运算（置空栈，进栈，出栈，取栈顶元素，判栈空）来实现二叉树的先序，中序，后序的三种遍历。

5．2 图的数据类型定义表

（1）课设中图的有关操作用到了以下一些结构体的定义说明如下：

typedef char VertexType[4];

typedef char InfoPtr;

typedef int VRType;

#define MaxSize 50               

typedef enum{DG,DN,UG,UN}GraphKind;/

typedef struct ArcNode {

int adjvex;                

InfoPtr *info;                

    struct ArcNode *nextarc;     

}ArcNode;

typedef struct VNode{

VertexType data;           

 ArcNode *firstarc;            

}VNode,AdjList[MaxSize];

typedef struct {

    AdjList vertex;

int vexnum,arcnum;           

GraphKind kind;            

}AdjGraph;

（2）typedef struct student 

{struct student *lchild,*rchild; 

char data; 

}*STU; 

STU stree_creat(char *s,int k) 

{STU p;

课程设计最终实现的结果：

（1）图的创建操作，输入顶点v1、v2、v3、v4、v5、v6、v7。并输入相应的弧尾和弧头，如下图所示：

                                  图5-1

.图的浏览操作，输入数字键2，调试界面会出现如下所示：

                                      图5-2  

求图的度的操作和邻接矩阵的操作，输入数字键3，调试界面如下图所示：

                              图 5-3      

求各个顶点的度及连通性的判断，输入数字键4，调试界面如下：

图5-4.

图的深度遍历，我们以第一个顶点开始进行深度遍历，遍历得结果如下图所示：

                                 图5-5

图的广度遍历，我们以第一个顶点开始进行深度遍历，遍历得结果如下图所示：

                                    图5-6

删除结点删除节点v1，调试界面如图所示：

图5-7                                     

图的销毁操作，键入数字键8，调试界面如下图示：                                   

                                  图5-8

检验图是否被销毁的操作，只需再一次进行图的浏览操作，此时该图已无节点的存在，图的销毁成功!结果如下图所示：

                                        图5-9

（2）二叉树的建立：如图5-10

图5-10

二叉树的遍历：如图5-11

图5-11

第6 章  源程序

（1）

/*---------------------------图的建立-------------------*/

void CreateGraph(AdjGraph *G)

{

    int i,j,k;

    VertexType v1,v2;                /*定义两个顶点v1和v2*/

    ArcNode *p;

    printf("请输入图的顶点数,边数(逗号分隔): ");

    scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);

    printf("请输入%d个顶点的值:\\n",G->vexnum);

    for(i=0;ivexnum;i++)            /*将顶点存储在头结点中*/

    {

scanf("%s",G->vertex[i].data);

G->vertex[i].firstarc=NULL; /*将相关联的顶点置为空*/

    }

    printf("请输入弧尾和弧头(以空格作为间隔):\\n");

    for(k=0;karcnum;k++)            /*建立边链表*/

    {

        scanf("%s%s",v1,v2);

        i=LocateVertex(*G,v1);

        j=LocateVertex(*G,v2);/*j为弧头i为弧尾创建邻接表*/

        p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

p->info=NULL;

p->nextarc=G->vertex[i].firstarc;

G->vertex[i].firstarc=p;/*i为弧头j为弧尾创建邻接表*/

        p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=i;

p->info=NULL;

p->nextarc=G->vertex[j].firstarc;

G->vertex[j].firstarc=p;

    }

    (*G).kind=UG;

}

/*---------------------------图的浏览-------------------*/

void DisplayGraph(AdjGraph G)

{

    int i;

    ArcNode *p;

    printf("%d个顶点：\\n",G.vexnum);

for(i=0;i    printf("%s ",G.vertex[i].data);

    printf("\\n");

}

/*---------------------------图的各个顶点的度-------------------*/

void vexdu(AdjGraph G)

{

    ArcNode *p;

    int i,count;

for(i=0;i    {

        p=G.vertex[i].firstarc;

        count=0;

        while(p)

        {

            count++;

p=p->nextarc ;

        }

        printf("第%s 的度数:%d\\n",G.vertex[i].data,count);

    }

}

/*---------------------------判断图的连通性-------------------*/

void liantong(AdjGraph G)

{

    ArcNode *p;

    int i,count,j;

    j=0;

for(i=0;i    {

        p=G.vertex[i].firstarc;

        count=0;

        while(p)

        {

            count++;

p=p->nextarc ;

        }

        if(count==0&&j==0)  

        {

            printf("该图是不连通的!");

            j++;

            printf("\\n");

            printf("不连通的结点为:");

        }

        if(count==0) 

        {

            printf("%s、",G.vertex[i].data);    

        }

        if(count>0) printf("该图示连通的!\\n");

    }

}

void Visit(VertexType v)

{

    printf("%s ",v);

}

/*---------------------------返回图中顶点对应的位置-------------------*/

int LocateVertex(AdjGraph G,VertexType v)

{

    int i;

for(i=0;i        if(strcmp(G.vertex[i].data,v)==0)

            return i;

        return -1;

}

/*------------------------图的非递归深度优先-------------------*/

int DFSTraverse2(AdjGraph G,int v)

{

    int i,visited[MaxSize],top;

    ArcNode *stack[MaxSize],*p;

    for(i=0;i     visited[i]=0;

Visit(G.vertex[v].data);                                         /*访问顶点v并将访问标志置为1，表示已经访问*/

    visited[v]=1;

    top=-1;                            /*初始化栈*/

    p=G.vertex[v].firstarc;   /*p指向顶点v的第一个邻接点*/

while(top>-1||p!=NULL)

    {

        while(p!=NULL)

if(visited[p->adjvex]==1)

/*如果p指向的顶点已经访问过，则p指向下一个邻接点*/

p=p->nextarc;

            else

            {

Visit(G.vertex[p->adjvex].data); /*访问p指向的顶点*/

visited[p->adjvex]=1;

                stack[++top]=p;        /*保存p指向的顶点*/

p=G.vertex[p->adjvex].firstarc;/*p指向当前顶点的第一个邻接点*/

            }

if(top>-1)

        {

            p=stack[top--];            /*如果当前顶点都已经被访问，则退栈*/

            p=p->nextarc;            /*p指向下一个邻接点*/

        }

    }

    return 0;

}

/*--------------------广度优先非递归遍历图-------------------*/

void BFSTraverse(AdjGraph G)

{

    int v,u,w,front,rear,j;

    ArcNode *p;

    int queue[MaxSize];                /*定义一个队列Q*/

    front=rear=-1;                    /*初始化队列Q*/

    for(v=0;v<=G.vexnum;v++)            /*初始化标志位*/

        visited[v]=0;

    printf("请输入从哪个顶点开始广度遍历:");

    scanf("%d",&j);

    v=j-1;

    visited[v]=1;         /*设置访问标志为1，表示已经被访问过*/

    Visit(G.vertex[v].data);

    rear=(rear+1)%MaxSize;

    queue[rear]=v;                    /*v入队列*/

    while(front    {

        front=(front+1)%MaxSize;

        v=queue[front];                /*队头元素出队赋值给v*/

        p=G.vertex[v].firstarc;

        while(p!=NULL)                /*遍历序号为v的所有邻接点*/

        {

if(visited[p->adjvex]==0)/*如果该顶点未被访问过*/

            {

visited[p->adjvex]=1;

Visit(G.vertex[p->adjvex].data);

                rear=(rear+1)%MaxSize;

queue[rear]=p->adjvex;

            }

            p=p->nextarc;            /*p指向下一个邻接点*/

        }

    }

}

/*---------------------------图中边存在的判断-------------------*/

int GraphExist(AdjGraph G,int i,int j)//判断是否存在边

 {

 ArcNode *s;

 s=G.vertex[i].firstarc;

while(s&&s->adjvex!=j)

s=s->nextarc;

 if(s)   return 1;

 else    return 0;

 }

/*---------------------------删除图中的弧-------------------*/

int delArc(AdjGraph &G,int i,int j)

{

 ArcNode *p,*q;

 p=G.vertex[i].firstarc;

if(p->adjvex==j){

G.vertex[i].firstarc=p->nextarc;

  free(p);

 }

 else{

while(p->nextarc&&p->nextarc->adjvex!=j)

p=p->nextarc;

  if(p){

q=p->nextarc;

p->nextarc=q->nextarc;

   free(q);

  }

 }

 G.arcnum--;

 return 1;

}

int NodeDel(AdjGraph &G)

 {

 int i,l,n,k;

 VertexType c;

 ArcNode *p;

 printf("请输入要删除的顶点个数：");

 scanf("%d",&n); 

if(n>G.vexnum)

    {

        printf("输入错误/n");

        return -1;

     }

    printf("请输入要删除的顶点:");

 for(k=0;k   {               

  getchar();

  scanf("%s",&c);

  l=LocateVertex(G,c);

if(l<0)

   {

   printf("输入的顶点不存在，请重新输入\\n");

   k--;

   continue;

   }

  for(i=0;i   {

   if(GraphExist(G,i,l)){

    delArc(G,i,l);

   } 

   if(GraphExist(G,l,i)){

    delArc(G,l,i);

   }

   //修改必要表结点的顶点的位置值

   p=G.vertex[i].firstarc;

    while(p)

     {

if(p->adjvex>l)

      {  

p->adjvex--;

      }

p=p->nextarc;

    }

  }

  //释放空间，顶点c后的顶点前移

for(i=l;i  {

   G.vertex[i]=G.vertex[i+1];

  }

  G.vexnum--;

 }

 printf("删除顶点成功");

 return 1;

}

/*---------------------------图的销毁-------------------*/

void DestroyGraph(AdjGraph *G)

{

    int i;

    ArcNode *p,*q;

    for(i=0;i<(*G).vexnum;++i)        /*释放图中的边表结点*/

    {

p=G->vertex[i].firstarc; /*p指向边表的第一个结点*/

        if(p!=NULL)                    /*如果边表不为空，则释放边表的结点*/

        {

q=p->nextarc;

            free(p);

            p=q;

        }

    }

    (*G).vexnum=0;                    /*将顶点数置为0*/

    (*G).arcnum=0;                    /*将边的数目置为0*/

}

（2）

#include

#include

#define null 0 

#define maxsize 100 

#define LEN sizeof(struct student) 

typedef struct student 

{struct student *lchild,*rchild; 

char data; 

}*STU; 

STU stree_creat(char *s,int k) 

{STU p; 

if(s[k]=='\\0'|| k>maxsize)

return NULL; 

else 

{p=(STU)malloc(LEN); 

p->data=s[k];

p->lchild=stree_creat(s,2*k+1);

p->rchild=stree_creat(s,2*k+2);

return p; 

} 

} 

void print(STU p) 

{ STU h[maxsize]={NULL}; 

int top=0,base=0;

h[top]=p;

printf("The chengci order:\\n\\n");

while(h[base]!=NULL)

{

printf("[%c]",h[base]->data);

h[++top]=h[base]->lchild;

h[++top]=h[base]->rchild;

base++;

} 

printf("\\nSuccess......\\n\\n!!!"); 

} 

/*前序遍历*/ 

void Preorder(STU p) 

{if(p) 

{ 

printf("[%c]",p->data);

Preorder(p->lchild);

Preorder(p->rchild);

} 

} 

/*非递归遍历 */

void preorder1 (STU p)

h[top]=p;

{

do

{

while(p!=null)

{

printf("%c",p->data);

if(p->rchild!=null)

{

p_top++;

h[top]=p=p->rchild;

}

p=p->lchild;

}

if(p_top>=0)

{

p=h[p_top];

p_top--;

}

if(p=null && p_top=0)

break;

}while(p_top>=0);

}

/*中序遍历*/ 

void Inorder(STU p) 

{if(p) 

{ 

Inorder(p->lchild);

printf("[%c]",p->data);

Inorder(p->rchild);

} 

} 

void InOrderUnrec(Bitree *t)

{

  Stack s;

  StackInit(s);

  Bitree *p=t;

  while (p!=NULL || !StackEmpty(s))

  {

  while (p!=NULL) //遍历左子树

  {

  push(s,p);

p=p->lchild;

  }

  if (!StackEmpty(s))

  {

  p=pop(s);

  visite(p->data); //访问根结点

  p=p->rchild; //通过下一次循环实现右子树遍历

  }//endif  

  }//endwhile

}

/*后序遍历*/ 

void Postorder(STU p) 

{if(p) 

{ 

Postorder(p->lchild);

Postorder(p->rchild);

printf("[%c]",p->data);

} 

} 

typedef enum{L,R} tagtype;

typedef struct 

{

  Bitree ptr;

  tagtype tag;

}stacknode;

typedef struct

{

  stacknode Elem[maxsize];

  int top;

}SqStack;

void PostOrderUnrec(Bitree t)

{

  SqStack s;

  stacknode x;

  StackInit(s);

  p=t;

  do 

  {

  while (p!=null) //遍历左子树

  {

  x.ptr = p; 

  x.tag = L; //标记为左子树

  push(s,x);

p=p->lchild;

  }

  while (!StackEmpty(s) && s.Elem[s.top].tag==R)  

  {

  x = pop(s);

  p = x.ptr;

  visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点  

  }

  if (!StackEmpty(s))

  {

  s.Elem[s.top].tag =R; //遍历右子树

p=s.Elem[s.top].ptr->rchild;

  }  

  }while (!StackEmpty(s));

}//PostOrderUnrec 

/*交换该二叉树中所有结点左右孩子的非递归算法*/ 

void exchange(STU p) 

{STU t;

if(p!=NULL)

{ t=p->lchild;

p->lchild=p->rchild;

p->rchild=t;

exchange(p->lchild);

exchange(p->rchild);

   }

}

main() 

{STU root=NULL; 

int i=0,j=0,h=0; 

char a[maxsize]={'\\0'}; 

clrscr(); 

/*用一个数组存放一连串的字符串*/ 

gets(a); 

while(a[i]!='\\0') 

i++; 

/*建立二叉树*/ 

root=stree_creat(a,0); 

printf("\\n"); 

/*输出数组中的内容*/ 

print(root); 

/*前序遍历*/ 

printf("Preorder Traversal........\\n"); 

Preorder(root); 

printf("\\n"); 

PreOrderUnrec(Bitree t);

printf("\\n");

/*中序遍历*/ 

printf("\\nInorder Traversal........\\n"); 

Inorder(root); 

printf("\\n"); 

InOrderUnrec(Bitree t);

printf("\\n");

/*后序遍历*/ 

printf("\\nPostorder Traversal........\\n"); 

Postorder(root); 

printf("\\n");

PostOrderUnrec(Bitree t);

printf("\\n");

/*交换该二叉树中所有结点左右孩子的非递归算法*/ 

printf("\\nThe conver order........\\n"); 

exchange(root); 

printf("\\n");

/*层次顺序输出数据*/ 

while(j{if(a[h]!='\\0') 

{printf("[%c]",a[h]); 

j++;} 

else 

printf("[]"); 

h++;}

printf("\\n"); 

getch(); 

}             

第7 章  附录

（1）  图的基本操作及应用

图的基本操作及应用 

第8 章  设计心得

通过本次课程设计，作为小组长的我深刻地认识到：

首先在做课程设计之前一定要先把总体的框架给想好，勾画好蓝图，根据每个人的特长，分配相应的工作，采用模块化程序开发的思想来完成这次课程设计；其次在程序开发的过程中，和队友之间的合作、各个环节的协调；最后，在程序最后的调试、运行个过程中，我和队友通力合作，解决遇到的问题，最终实现了程序的运行。

其中更重要的是我学到了一些知识，了解到了自己在写程序时的一些不足的观点和方法。这次课程设计对自己在编程方面有很大的帮助，自己的能力也得到了提高。在处理遇到的问题时，经过从网上找资料，以及通过队友之间的讨论，最后都把问题解决了。这次的课程设计让我们更加巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养思考，深入研究，分析问题、解决问题的能力。 

程序中需要改进和不足的地方：

（1）在邻接表转化成邻接矩阵时，向内存申请了一个很大的空间，该空间只用于输出邻接矩阵，造成了内存的很大浪费。

（2）邻接表中存放表头结点采用线性存储，可以考虑采用链式存储更为合理。

（3）在广度遍历和深度遍历中，只能输入从第几个结点开始遍历，应该考虑把结点的信息输入，然后开始遍历。

（4）在销毁图的这个模块中，只释放了头结点后面的空间，而头结点并没有释放。

（5）当判断图不连通时，应该输出图的不连通分量并把不连通的部分按广度遍历或者深度遍历输出。

（6）应该再添加一个插入相应结点信息的模块，这样就更为完美。

第9 章  参考文献

[1] 张华新.计算机基础.高等教育出版社,2003年.

[2] 张新新.C语言程序设计.人民教育出版社,2005年.

[3] 宗大华.数据结构.人民邮电出版社,2010年.

[4] 严蔚敏.数据结构（C语言版）.清华大学出版社,2009.

[5] 严蔚敏.数据结构题集（C语言版）.清华大学出版社,2009.

[6] 陈守孔.算法与数据结构.机械工业出版社,2010.

[7] 殷人昆、陶永雷、谢若阳、盛绚华.据结构（面向对象）.华大学出版社,2010.

[8] 徐孝凯. 数据结构实用教程. 清华大学出版社, 1999.