您的当前位置:首页正文

大二数据结构课设报告(初稿)1

2020-06-21 来源:年旅网
数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

目 录

1单位员工通讯录管理系统(*).....................2

1.1 设计题目、需求分析……………………………………………2 1.2 概要设计…………………………………………………..……2 1.3详细设计…………………………………………………….……3 1.4 调试分析………………………………………………………..9 1.5设计心得体会)……………………………………………..…11 1.6附录(程序源码)………………………………………………12

2线索二叉树(**)...............................16

2.1 设计题目、需求分析……………………………………….…16 2.2 概要设计………………………………………………..….…16 2.3详细设计……………………………………………………..…16 2.4 调试分析…………………………………………………….…21 2.5测试结果…………………………………………………..……21 2.6设计心得体会)…………………………………………………22 2.7附录(程序源码)…………………………………………………22

3 .校园导游咨询(***)……………………………………26

3.1 设计题目、需求分析…………………………………….……26 3.2 概要设计…………………………………………………...…26 3.3详细设计…………………………………………………………27 3.4 调试分析…………………………………………….…………27 3.5测试结果………………………………………………..………37 3.6设计心得体会)…………………………………………………38 3.7附录(程序源码)…………………………………………………38

4.总结…………………………………………………..……46

- 1 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

一.单位员工通讯录管理系统(*)

1.1 设计题目、需求分析个

任务:为某个单位建立一个员工通讯录管理系统,可以方便查询每一个员工的办公室电话、手机号、及电子邮箱。

要求:其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。

1.2概要设计

主要是运用链表的基础操作相应通讯录链表的建立,插入,删除等操作。流程图如下图:

1.3详细设计

(1)尾插法建立带头结点的通讯录链表 LinkList CreateList(void) {

LinkList head=(ListNode *)malloc(sizeof(ListNode));//申请头结点 ListNode *p,*rear;

- 2 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

char flag='y'; //结束标志置0 rear=head; //尾指针初始指向头结点 while (flag=='y')

{

p=(ListNode *)malloc(sizeof(ListNode)); //申新结点 cout<<\"编号 姓名 手机 电话 邮箱 \"<>p->data.num;

cout<<\"添加的姓名:\"<>p->data.name; cout<<\"手机:\"<>p->data.phone;

- 3 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

}

}

cout<<\"电话:\"<>p->data.phone; cout<<\"邮箱:\"<>p->data.email;

rear->next=p; //新结点连接到尾结点之后 rear=p; //尾指针指向新结点 cout<<\"继续建表?(y/n):\"<>flag;

rear->next=NULL; //终端结点指针置空 return head; //返回链表头指针

(2)在通讯录链表head中插入结点 void InsertNode(LinkList head,ListNode *p) {

ListNode *p1,*p2; p1=head; p2=p1->next;

while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0) {

p1=p2; //p1指向刚访问过的结点 p2=p2->next; //p2指向表的下一个结点 }

p1->next=p; //插入p所指向的结点 p->next=p2; //连接表中剩余的结点 }

(3)链表的查找

ListNode *FindList(LinkList head) {

ListNode *p; char num[5]; char name[9];

char c;

cout<<\"==================\"<- 4 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cout<<\" a. 按编号查询 \"<next; cin>>c; if (c=='a')

{ cout<<\"请输入要查找者的编号:\"<>num;

while (p&&strcmp(p->data.num,num)<0) p=p->next;

if ((p==NULL)||strcmp(p->data.num,num)>0) p=NULL; 要查找的通讯信息

} else if (c=='b') { cout<<\" 请输入要查找者的姓名:\"<>name;

while(p&&strcmp(p->data.name,name)!=0)

p=p->next;

}

return p;

}

(4)通讯录链表上的结点删除 void DelNode(LinkList head) {char cho; ListNode *p,*q; p=FindList(head); if (p==NULL) { cout<<\"没有查到要删除的通讯者!\\n\"<else if(p!=NULL)

- 5 -

//没有查到

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

{

cout<<\"真的要删除该结点吗?(y/n)\"<>cho;

if (cho=='y'||cho=='Y') {

q=head;

while ((q!=NULL)&&(q->next!=p)) q=q->next; q->next=p->next; //删除结点 free(p); //释放被删结点空间 cout<<\"删除成功!\"<}}

(5)通讯录链表的输出函数 void PrintList(LinkList head) { dl; dl; }

(6)主函数(菜单显示) void main() {

int c,j=1; while(j) {

cout<<\" && 通 信 录 链 表 &&&&&&&&&&&\"<}

p=p->next; //后移一个结点

cout<<\"---------------------------------------------------------------------------------\"<cout<data.num<< p->data.name<< p->data.phone<< p->data.phone<< ListNode *p; p=head->next;

cout<<\"编号/姓名/手机 /电话/邮箱\"<cout<<\"--------------------------------------------------------------------------------\"<p->data.email<- 6 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cout<<\"******************************************\"<cout<<\"********** 1--- 通信录链表建立 *\"<cout<<\"********** 4--- 通信录链表删除 *\"<>c; getchar(); switch(c){

case 1: {

if(flag1!=1)

{cout<<\"请先建立表!\"<cout<<\"*********************************\"<cout<<\"*******************************\"<cout<<\"* 通 讯 录 链 表 的 建 立 \"<case 2:

cout<<\"* 通 讯 者 信 息 的 添 加 *\"<cout<<\"添加的编号:\"<>p->data.num;

cout<<\"添加的姓名:\"<>p->data.name; cout<<\"手机:\"<>p->data.phone; cout<<\"电话:\"<cout<<\"********************************* \"<- 7 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cin>>p->data.phone; cout<<\"邮箱:\"<>p->data.email; InsertNode(head,p); break; }

case 3: {if(flag1!=1) {

{

cout<<\"请先建立表!\"<cout<<\"***********************************\"<cout<<\" 通 讯 录 信 息 的 查 询 *\"<p=FindList(head); if (p!=NULL) {

cout<<\"***********************************\"<cout<<\"编号 姓 名 手机 联系电话 邮箱 \"<cout<<\"--------------------------------------------------\"<cout<data.num<<\"\"<data.name<<\"

cout<<\"---------------------------------------------------\"<} break;}

}

else cout<<\"没有查到要查询的通讯录\"<\"<data.telephone<<\"\"<data.phone<<\" \"<data.email<case 4:

{ if(flag1!=1) {cout<<\"请先建立表!\"<else {

cout<<\"***********************************\"<cout<<\"* 通 讯 录 信 息 的 删 除 *\"<}

DelNode(head); //删除结点

- 8 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

{

break;}

case 5:

if(flag1!=1) {cout<<\"请先建立表!\"<cout<<\"************************************\"<}

cout<<\"***********************************\"<cout<<\"* 通 讯 录 链 表 的 输 出 *\"<break;}

}}

case 0:j=0;break;

default:cout<<\"输入有错,请重新输入!\"<1.4 调试分析

开始,在运行的时候,由于疏忽,将查找模块的两种查找方式显示错位,造成输入与所得结果不符,后来经过反复调试,才得以发现。 输入数据类型为字符型,但在输入过程中不可包含空格,如输入地址过程中不可出现空格!

(1)开始运行时界面如下:

(2)通讯录链表建立界面如下:

- 9 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

(3)通讯录链表插入界面如下:

(4)通讯录链表查询界面如下:

(5)查询界面如下:

- 10 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

(6) 通讯录链表删除界面如下:

(7)通讯录链表输出界面如下:

1.5设计心得体会

相对来说,知道关于链表基础操作的通讯录管理设计问题是属于较基础,较简单的问题,主要是巩固夯实关于链表的基础操作。

经过这一道题的设计与调试,发现自己的基础知识掌握的并不是十分牢固,要在以后主义基础知识的积累,只有这样才能在以后的学习中做到得心应手。

1.6附录(源程序源码)

- 11 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

#include #include \"iostream\" #include \"string.h\" #include \"stdlib.h\" int flag1=0;

using namespace std;

typedef struct //通讯录结点类型 {

char num[5]; //编号 char name[9]; //姓名 char telephone[11];//手机 char phone[13]; //电话 char email[31]; //邮箱 } DataType;

typedef struct node //结点类型定义 {DataType data; //结点数据域 struct node *next; //结点指针域 } ListNode;

typedef ListNode *LinkList; LinkList head; ListNode *p;

LinkList CreateList(void);

void InsertNode(LinkList head,ListNode *p); ListNode *FindList(LinkList head); void DelNode(LinkList head); void PrintList(LinkList head);

LinkList CreateList(void)//尾插法建立带头结点的通讯录链表 {LinkList head=(ListNode *)malloc(sizeof(ListNode));//申请头结点 ListNode *p,*rear; char flag='y'; //结束标志置0

rear=head; //尾指针初始指向头结点 while (flag=='y')

{ p=(ListNode *)malloc(sizeof(ListNode)); //申新结点 cout<<\"编号 姓名 手机 电话 邮箱 \"<>p->data.num; cout<<\"添加的姓名:\"<>p->data.name; cout<<\"手机:\"<>p->data.phone; cout<<\"电话:\"<>p->data.phone; cout<<\"邮箱:\"<- 12 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cin>>p->data.email; rear->next=p; //新结点连接到尾结点之后 rear=p; //尾指针指向新结点 cout<<\"继续建表?(y/n):\"<>flag;}

rear->next=NULL; //终端结点指针置空 return head; //返回链表头指针}

void InsertNode(LinkList head,ListNode *p)//在通讯录链表head中插入 { ListNode *p1,*p2; p1=head; p2=p1->next;

while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0) { p1=p2; //p1指向刚访问过的结点

p2=p2->next; //p2指向表的下一个结点 } p1->next=p; //插入p所指向的结点 p->next=p2; //连接表中剩余的结点} ListNode *FindList(LinkList head)//链表的查找 { ListNode *p; char num[5]; char name[9]; char c;

cout<<\"==================\"<next; cin>>c;

if (c=='a')

{cout<<\"请输入要查找者的编号:\"<>num; while (p&&strcmp(p->data.num,num)<0) p=p->next; if ((p==NULL)||strcmp(p->data.num,num)>0) p=NULL; 要查找的通讯信息} else if (c=='b') { cout<<\" 请输入要查找者的姓名:\"<>name; while(p&&strcmp(p->data.name,name)!=0) p=p->next;} return p;

}void DelNode(LinkList head)//通讯录链表上的结点删除 {char cho;

ListNode *p,*q; p=FindList(head);

- 13 -

//没有查到 数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

if (p==NULL) { cout<<\"没有查到要删除的通讯者!\\n\"<>cho; if (cho=='y'||cho=='Y') { q=head; while ((q!=NULL)&&(q->next!=p)) q=q->next; q->next=p->next; //删除结点 free(p); //释放被删结点空间 cout<<\"删除成功!\"<void PrintList(LinkList head)//通讯录链表的输出函数 {ListNode *p; p=head->next;

cout<<\"编号/姓名/手机 /电话/邮箱\"<cout<<\"----------------------------------------------------------------\"<{ cout<data.num<< p->data.name<< p->data.phone<< p->data.phone<< p->data.email<cout<<\"----------------------------------------------------------------\"<next; //后移一个结点 }} void main() { int c,j=1; while(j)

{cout<<\" &&&&&&&&&&&&& 通 信 录 链 表&\"<>c; getchar(); switch(c) { case 1: { cout<<\"* 通 讯 录 链 表 的 建 立 *\\n\"<- 14 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

break;} case 2: { if(flag1!=1) {cout<<\"请先建立表!\"<cout<<\"**********************************\"<cout<<\"编号(4) 姓名(8) 手机(11) 电话(11) 邮箱(31)\"<>p->data.num; cout<<\"添加的姓名:\"<>p->data.name; cout<<\"手机:\"<>p->data.phone; cout<<\"电话:\"<>p->data.phone; cout<<\"邮箱:\"<>p->data.email; InsertNode(head,p); break; } case 3: { if(flag1!=1) {

cout<<\"请先建立表!\"<else { cout<<\"***********************************\"<cout<< p->data.num<<\" \"<data.name<<\" \"<data.telephone<<\" \"<data.phone<<\" \"<data.email<cout<<\"---------------------------------------------------\"<cout<<\"***********************************\"<- 15 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

break;}

case 5:{if(flag1!=1) {cout<<\"请先建立表!\"<cout<<\"************************************\"<cout<<\"************************************\"<二.线索二叉树(**)

2.1 设计题目 需求分析

1.建立中序线索二叉树,并且中序遍历;

2. 求中序线索二叉树上已知结点中序的前驱和后继;

2.2概要设计

1.根据用户输入,按线序顺序创建二叉树。 2.对用户输入的二叉树进行中序线索化。 3.中线索化后遍历二叉树。

4.根据用户的输入的结点,求其前驱后后继。

2.3详细设计

1.按照递归的方法根据用户的输入建立二叉树(如果是叶子结点后跟两个#号表示)具体代码如下:

int CreateBiThrTree(BiThrTree &T){

//

先序建立二叉树

TElemType ch;

- 16 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

}

cin>>ch; if (ch == '#')

T = NULL;

else{ } return OK;

if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))

exit(OVERFLOW);

T -> data = ch; T -> LTag = Link; T -> RTag = Link;

CreateBiThrTree(T -> lchild); CreateBiThrTree(T -> rchild);

2.对二叉树中序线索化的算法设计:先定义一个线索函数

InThreading(),如果一个结点的rchild为空,那么它的RTag = Thread,lchild为空,那么它的LTag = Thread,反之RTag = Link,LTag = Link,然后按照左子树,结点,右子树递归线索。线索函数定义好了后,再定义中序线索二叉树的函数InOrderThreading(),在InOrderThreading()中先使头结点Thrt的lchild指向T,然后调用线索函数InThreading()对二叉树进行线索化。具体代码如下: void InThreading(BiThrTree p)//线索化

- 17 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

{

if(p){ InThreading(p -> lchild); if(!(p -> lchild)){ p -> LTag = Thread; p -> lchild = pre;

}

if(!(pre -> rchild)){ pre -> RTag = Thread;

pre -> rchild = p;} pre = p;

InThreading(p -> rchild); }}

int InOrderThreading(BiThrTree &Thrt,BiThrTree &T) { 中序线索二叉树 if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt -> LTag = Link; Thrt -> RTag = Thread; Thrt -> rchild = Thrt; if(!T)

Thrt ->lchild = Thrt;

else{

- 18 -

//

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

}

Thrt ->lchild = T; pre = Thrt; InThreading(T); pre -> rchild = Thrt; pre -> RTag = Thread; Thrt -> rchild = pre;

return OK;}

中序遍历二叉树的算法设计为:线索化后,先使指针p指向二

1.

叉树的最左下的结点,然后输出结点信息,接下来如果p -> RTag == Thread && p -> rchild != Thrt那么p的下一个结点为p -> rchild,如果不是,则使p指向p -> rchild,然后再循环,具体代码如下:

int InOrderTraverse_Thr(BiThrTree T){ //中序遍历线索二叉树

BiThrTree p; p = T;

while(p != Thrt) {

while(p -> LTag == Link)

p = p ->lchild;

cout<< p ->data;

while(p -> RTag == Thread && p -> rchild != Thrt){

p = p -> rchild;

- 19 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cout<

data; }

}

p = p -> rchild;

return OK;}

5.求结点前驱的算法为:如果结点p的LTag == Thread,那么它的前驱为p -> lchild,如果它的LTag != Thread,那么它的前驱为它的左子树的最右下的结点。同理可得结点后继的算法。 具体代码如下:

void getPre(BiThrTree T){ //求结点的前驱

BiThrTree s; if(T){

if(T -> lchild == Thrt){

cout< data<<\"结点无前驱\"<else{

if(T -> LTag){

cout< data<<\"结点的前驱是\"< lchild ->

data<for(s = T -> lchild; s -> RTag == 0; s = s -> rchild) ;

}}

cout< data<<\"结点的前驱是\"< data<//求结点的后继

void getNext(BiThrTree T){

BiThrTree s; if(T){

- 20 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

if(T -> rchild == Thrt){

cout< data<<\"结点无后继\"<else{

if(T -> RTag){

cout< data<<\"结点的后继是\"< rchild -> data<for(s = T -> rchild; s -> LTag == 0; s = s -> lchild) ;

cout< data<<\"结点的后继是\"< data<2.4 调试分析

在运行时产生的问题很好解决,在运行中莫名弹出了警告窗口,最后才发现在中序遍历和查找中序的前驱和后继的操作之前必须进行线索化。

2.5 测试结果

过程为:先创建二叉树,然后线索化,然后可以对其进行遍历或查找前驱或后继的操作

- 21 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

2.6设计心得体会

这是一道线索二叉树的程序设计问题,首先先序建立二叉树,在对二叉树进行线索化,在对线索二叉树进行遍历求出前驱和后继。在设计程序的过程中也出现了许多问题,其中也有因基础知识掌握不牢固造成的错误,之后经过看书以及和同学探讨才得以解决,以后要,牢固基础,积极思考。

2.7附录(程序源码)

#include #include #include #define OK 1

#define OVERFLOW -2 typedef char TElemType;

typedef enum PointerTag{Link,Thread};

- 22 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

typedef struct BiThrNode{ //线索二叉树存储结构 TElemType data;

struct BiThrNode *lchild, *rchild;//左右孩子指针 PointerTag LTag, RTag;//zuoyoubiaozhi }BiThrNode, *BiThrTree; BiThrTree pre; BiThrTree Thrt;

void InitBiThrTree(BiThrTree &T){ //初始化二叉树 T = NULL;}

int CreateBiThrTree(BiThrTree &T){ //先序建立二叉树 TElemType ch; cin>>ch; if (ch == '#') T = NULL; else{ if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); T -> data = ch; T -> LTag = Link; T -> RTag = Link; CreateBiThrTree(T -> lchild); CreateBiThrTree(T -> rchild); } return OK;}

void InThreading(BiThrTree p){ //线索函数 if(p){ InThreading(p -> lchild);//左子树线索化 if(!(p -> lchild)){ p -> LTag = Thread; p -> lchild = pre; }//前驱线索化 if(!(pre -> rchild)){ pre -> RTag = Thread; pre -> rchild = p;}//后继线索化 pre = p; InThreading(p -> rchild);//右子树线索化 }}

int InOrderThreading(BiThrTree &Thrt,BiThrTree &T) {//中序遍历二叉树,并将其中序线索化,(中序线索二叉树)

if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))//Thrt指向头结点 exit(OVERFLOW);

Thrt -> LTag = Link;//建头结点 Thrt -> RTag = Thread;//建头结点 Thrt -> rchild = Thrt;//右指针回指 if(!T) Thrt ->lchild = Thrt;//若二叉树空,则左指针回指 else{ Thrt ->lchild = T;

- 23 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

pre = Thrt; InThreading(T);//中序遍历进行中序线索化 pre -> rchild = Thrt; pre -> RTag = Thread;//最后一个节点线索化 Thrt -> rchild = pre;} return OK;}

int InOrderTraverse_Thr(BiThrTree T){ //中序遍历线索二叉树 BiThrTree p; p = T;

while(p != Thrt) { while(p -> LTag == Link) p = p ->lchild; cout<< p ->data; while(p -> RTag == Thread && p -> rchild != Thrt){ p = p -> rchild; cout<

data; } p = p -> rchild; }

return OK;}

void getPre(BiThrTree T){ //求结点的前驱 BiThrTree s; if(T){ if(T -> lchild == Thrt){ cout< data<<\"结点无前驱\"< LTag){ cout< data<<\"结点的前驱是\"< lchild -> data< lchild; s -> RTag == 0; s = s -> rchild) ; cout< data<<\"结点的前驱是\"< data< rchild == Thrt){ cout< data<<\"结点无后继\"< RTag){ cout< data<<\"结点的后继是\"< rchild -> data< rchild; s -> LTag == 0; s = s -> lchild) ; cout< data<<\"结点的后继是\"< data<void findPreAndNext(BiThrTree T, char n){ //查找指定元素的前驱和后继 cout<<\"请输入你要查找的元素: \";

- 24 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cin>>n;

BiThrTree p; p = T;

while(p != Thrt) { while(p -> LTag == Link) p = p ->lchild; if(p -> data == n){ getPre(p); getNext(p); break;} else{ while(p -> RTag == Thread && p -> rchild != Thrt){ p = p -> rchild; if(p -> data ==n){ getPre(p); getNext(p); }} p = p -> rchild; } }} void main(){

BiThrTree T = NULL;

cout<<\"***********************************************\"<cout<<\"* 请选择以下功能对线索二叉树进行操作(输入序号) *\"<cout<<\"1.初始化二叉树 *\"<cout<<\"* 2.先序建立二叉树 *\"<cout<<\"* 3.对二叉树进行中序线索化 *\"<cout<<\"* 4.中序递归遍历二叉树 *\"<cout<<\"* 5.查找指定结点中序的前驱和后继 *\"<cout<<\"***********************************\"<while(cin>>n){ switch(n){ case 1: InitBiThrTree(T); cout<<\"二叉树初始化完成\"<- 25 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

CreateBiThrTree(T); cout<<\"二叉树创建完成\"<三.校园导游咨询(***)

3.1 设计题目

任务:设计一个校园导游程序,为来访的客人提供各种信息

查询服务要求:1)设计学校的校园平面图,所含景点不少于10个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。

(2)为来访客人提供图中任意景点相关信息的查询。

(3)为来访客人提供景点的问路查询,即已知一个景点,查询到某景点之间的一条最短路径及长度。

3.2需求分析:

- 26 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

需要一个邻接矩阵来保存校园导游信息,需要使用FLOYD算法来

球各个景点间的最短路径,需要使用另外一个邻接矩阵来保存最短路劲信息。

3.3 概要设计

1首先定义景点的结构体Vertex用来保存景点信息,再使用地图(一个邻接矩阵形式)MGraph来保存景点信息和景点之间的路径长度,然后定义一个最短路径的邻接矩阵shortest用来保存景点间的最短路径的长度信息,最后使用一个二维数组path来保存最短路径所经过的景点信息。

2. 结构体定义完成后,使用init()函数创建地图,并使用FLOYD算法对邻接矩阵进行求最短路径长度和经过的经典,并把结果保存在shortest数组和path数组中。之后设计introduce()函数用来对景点信息进行介绍,shortestdistance()函数打印两个景点的路径及最短距离。

3. 主函数部分先调用init()函数创建地图,然后根据用户输入的信息动态地调用适当的函数

3.4 详细设计

1. 定义景点,顶点,地图结构体 typedef struct { char name[20];

//景点名称 //景点代号 //景点简介

char number[15];

char introduce[100]; }Elemtype; typedef struct {

- 27 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

int num;

//顶点编号 //顶点信息

Elemtype date; }Vertex;

//定义顶点

typedef struct Vertex vexs[MaxVertexNum];//存放顶点的一维数组,数组第零个单元没有用上 unsigned int edges[MaxVertexNum][MaxVertexNum]; //存放路径的长度 int n,e; }MGraph; 2. 初始化地图

void init() { int i,j;

MGr.vexs[1].num=1;

strcpy(MGr.vexs[1].date.name,\"学校后门\"); strcpy(MGr.vexs[1].date.number,\"001\");

strcpy(MGr.vexs[1].date.introduce,\"一般从这里离开学校。\"); MGr.vexs[2].num=2;

strcpy(MGr.vexs[2].date.name,\"北苑食堂\"); strcpy(MGr.vexs[2].date.number,\"002\");

strcpy(MGr.vexs[2].date.introduce,\"吃饭的地方。\"); MGr.vexs[3].num=3;

strcpy(MGr.vexs[3].date.name,\"北苑篮球场\"); strcpy(MGr.vexs[3].date.number,\"003\");

- 28 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

strcpy(MGr.vexs[3].date.introduce,\"锻炼身体的地方。\"); MGr.vexs[4].num=4;

strcpy(MGr.vexs[4].date.name,\"体育馆\"); strcpy(MGr.vexs[4].date.number,\"004\");

strcpy(MGr.vexs[4].date.introduce,\"正在修建。。。\"); MGr.vexs[5].num=5;

strcpy(MGr.vexs[5].date.name,\"2号楼\"); strcpy(MGr.vexs[5].date.number,\"005\");

strcpy(MGr.vexs[5].date.introduce,\"做实验的地方。\"); MGr.vexs[6].num=6;

strcpy(MGr.vexs[6].date.name,\"图书馆\"); strcpy(MGr.vexs[6].date.number,\"006\");

strcpy(MGr.vexs[6].date.introduce,\"看书的地方。\"); MGr.vexs[7].num=7;

strcpy(MGr.vexs[7].date.name,\"弘德桥\"); strcpy(MGr.vexs[7].date.number,\"007\");

strcpy(MGr.vexs[7].date.introduce,\"图书馆到3号楼必经之\"); MGr.vexs[8].num=8;

strcpy(MGr.vexs[8].date.name,\"紫薇广场\"); strcpy(MGr.vexs[8].date.number,\"008\");

strcpy(MGr.vexs[8].date.introduce,\"开晚会搞活动的地方。\"); MGr.vexs[9].num=9;

- 29 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

strcpy(MGr.vexs[9].date.name,\"3号楼\"); strcpy(MGr.vexs[9].date.number,\"009\");

strcpy(MGr.vexs[9].date.introduce,\"上课的地方。\"); MGr.vexs[10].num=10;

strcpy(MGr.vexs[10].date.name,\"绮园\"); strcpy(MGr.vexs[10].date.number,\"010\");

strcpy(MGr.vexs[10].date.introduce,\"景色还可以。\"); MGr.vexs[11].num=11;

strcpy(MGr.vexs[11].date.name,\"南苑食堂\"); strcpy(MGr.vexs[11].date.number,\"011\");

strcpy(MGr.vexs[11].date.introduce,\"吃饭的地方。\"); MGr.vexs[12].num=12;

strcpy(MGr.vexs[12].date.name,\"南苑体育场\"); strcpy(MGr.vexs[12].date.number,\"011\");

strcpy(MGr.vexs[12].date.introduce,\"锻炼身体的地方。 for(i=1;i<=T;i++) { for(j=1;j<=T;j++) {

MGr.edges[i][j]=MAXCOST;}}

for(i=1;i<=T;i++) {

shortest[i][i]=0;}

//初始化

MGr.edges[1][2]=MGr.edges[2][1]=20;

MGr.edges[1][3]=MGr.edges[3][1]=40;

- 30 -

\"); 数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

MGr.edges[1][5]=MGr.edges[5][1]=80; MGr.edges[1][9]=MGr.edges[9][1]=100; MGr.edges[2][3]=MGr.edges[3][2]=20; MGr.edges[2][4]=MGr.edges[4][2]=40; MGr.edges[4][6]=MGr.edges[6][4]=50; MGr.edges[4][8]=MGr.edges[8][4]=70; MGr.edges[5][9]=MGr.edges[9][5]=10; MGr.edges[6][7]=MGr.edges[7][6]=8; MGr.edges[6][12]=MGr.edges[12][6]=90; MGr.edges[7][8]=MGr.edges[8][7]=10; MGr.edges[8][9]=MGr.edges[9][8]=10; MGr.edges[9][11]=MGr.edges[11][9]=40; MGr.edges[10][11]=MGr.edges[11][10]=20;}

3. 根据用户输入的信息打印景点信息 void introduce() { int n;

cout<<\"请输入查询景点编号:\"<>n; switch(n) {case 1:

cout<<\"景点编号:\"<- 31 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

cout<<\"景点简介:\"<cout<<\"景点编号:\"<cout<<\"景点简介:\"<cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<- 32 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

case 6:

cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<case 9:

cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<case 10:

cout<<\"景点编号:\"<- 33 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

点名称:\"<cout<<\"

\"<case 11:

cout<<\"景点编号:\"<名称:\"<cout<<\"

\"<case 12:

cout<<\"景点编号:\"<点名称:\"<cout<<\"

\"<default:

cout<<\"输入序号错误。\"; break;}} 4. FLOYD算法 5. void floyd() {

int i,j,k;

- 34 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

for(i=1;i<=T;i++) {

for(j=1;j<=T;j++) {

shortest[i][j]=MGr.edges[i][j]; path[i][j]=0;}}

//初始化数组

for(k=1;k<=T;k++) {

for(i=1;i<=T;i++) {

for(j=1;j<=T;j++) {

if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {

shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k;

//记录经过的路径}}}}}

6. 打印两个景点的路径及最短距离

void display(int i,int j) { 距离

// 打印两个景点的路径及最短

int a,b; a=i; b=j;

cout<<\"您要查询的两景点间最短路径是:\\n\\n\"; if(shortest[i][j]!=MaxVertexNum) {

if(icout<while(path[i][j]!=0) { // 把i到j的路径上所有经过的景点按

- 35 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

逆序打印出来

cout<<\"<-\"<i=path[j][i];}

cout<<\"<-\"<\"<}

\"<cout<while(path[i][j]!=0) {// 把i到j的路径上所有经过的景点按

顺序打印出来

cout<<\"->\"<cout<<\"->\"<cout<\"<- 36 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

米\\n\\n\"<}

cout<<\"输入错误!不存在此路!\\n\\n\";}

7. 根据用户输入的信息查找的两景点的最短距离及路经

int shortestdistance() {

int i,j;

cout<<\"请输入要查询的两个景点的编号(1->11的数字编号

//要查找的两景点的最短距离

并用空格间隔):\";

cin>>i>>j;

if(i>T||i<=0||j>T||j<0) {

cout<<\"输入信息错误!\\n\\n\";

cout<<\" 请输入要查询的两个景点的编号(1->11的数字

编号并用' '间隔):\";

cin>>i>>j;}

else { floyd(); display(i,j); return 1;}

}

3.5调试分析

- 37 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

3.6设计心得体会

这个设计问题主要是运用弗洛伊德算法求最短路径的问题。在开始的时候,在算法设计上出现了一些小问题,经过询问同学才得以调试成功。对佛洛依德算法的理解是设计的关键。

3.7附录(程序源码)

#include #include

- 38 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

using namespace std; #define MaxVertexNum 50 #define MAXCOST 1000 #define T 12 typedef struct { char name[20]; char number[15]; }Elemtype; typedef struct { int num; }Vertex;

//顶点编号 //顶点信息

Elemtype date;

//景点名称 //景点代号

//景点个数最大50

//定义路径的无穷大 //目前景点个数

char introduce[100]; //景点简介

//定义顶点

typedef struct { Vertex vexs[MaxVertexNum]; //存放顶点的一维数组,数组第零个单元没有用上

unsigned int edges[MaxVertexNum][MaxVertexNum]; //存放路径的长度 int n,e; }MGraph; MGraph MGr; 径

int path[MaxVertexNum][MaxVertexNum]; //定义存贮路径 void init() {

int i,j;

MGr.vexs[1].num=1;

strcpy(MGr.vexs[1].date.name,\"学校北门\"); strcpy(MGr.vexs[1].date.number,\"001\"); strcpy(MGr.vexs[1].date.introduce,\"国教\"); MGr.vexs[2].num=2;

strcpy(MGr.vexs[2].date.name,\"北苑餐厅\"); strcpy(MGr.vexs[2].date.number,\"002\");

strcpy(MGr.vexs[2].date.introduce,\"吃饭的地方。\"); MGr.vexs[3].num=3;

strcpy(MGr.vexs[3].date.name,\"北苑地下篮球场\"); strcpy(MGr.vexs[3].date.number,\"003\");

//全局变量,定义MGr为MGraph类型

int shortest[MaxVertexNum][MaxVertexNum]; //定义全局变量存贮最小路

- 39 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

strcpy(MGr.vexs[3].date.introduce,\"上体育课的地方。\"); MGr.vexs[4].num=4;

strcpy(MGr.vexs[4].date.name,\"体育馆\"); strcpy(MGr.vexs[4].date.number,\"004\");

strcpy(MGr.vexs[4].date.introduce,\"正在修建中,明年投入使用\"); MGr.vexs[5].num=5;

strcpy(MGr.vexs[5].date.name,\"2号实验楼\"); strcpy(MGr.vexs[5].date.number,\"005\");

strcpy(MGr.vexs[5].date.introduce,\"经管的楼。\"); MGr.vexs[6].num=6;

strcpy(MGr.vexs[6].date.name,\"图书馆\"); strcpy(MGr.vexs[6].date.number,\"006\");

strcpy(MGr.vexs[6].date.introduce,\"学习的地方。\"); MGr.vexs[7].num=7;

strcpy(MGr.vexs[7].date.name,\"弘德桥\"); strcpy(MGr.vexs[7].date.number,\"007\");

strcpy(MGr.vexs[7].date.introduce,\"图书馆到紫薇经过这里。\"); MGr.vexs[8].num=8;

strcpy(MGr.vexs[8].date.name,\"紫薇广场\"); strcpy(MGr.vexs[8].date.number,\"008\");

strcpy(MGr.vexs[8].date.introduce,\"开晚会搞活动的地方。\"); MGr.vexs[9].num=9;

strcpy(MGr.vexs[9].date.name,\"3号楼\"); strcpy(MGr.vexs[9].date.number,\"009\");

strcpy(MGr.vexs[9].date.introduce,\"上课自习的地方。\"); MGr.vexs[10].num=10;

strcpy(MGr.vexs[10].date.name,\"绮园\"); strcpy(MGr.vexs[10].date.number,\"010\");

strcpy(MGr.vexs[10].date.introduce,\"景色还可以。\"); MGr.vexs[11].num=11;

strcpy(MGr.vexs[11].date.name,\"南苑餐厅\"); strcpy(MGr.vexs[11].date.number,\"011\");

strcpy(MGr.vexs[11].date.introduce,\"吃饭的地方。\"); MGr.vexs[12].num=12;

strcpy(MGr.vexs[12].date.name,\"南苑体育场\");

- 40 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

}

strcpy(MGr.vexs[12].date.number,\"011\");

strcpy(MGr.vexs[12].date.introduce,\"锻炼身体的地方。\"); for(i=1;i<=T;i++) {

for(j=1;j<=T;j++) {

MGr.edges[i][j]=MAXCOST;}}

//初始化

for(i=1;i<=T;i++) {

shortest[i][i]=0;}

MGr.edges[1][2]=MGr.edges[2][1]=20; MGr.edges[1][3]=MGr.edges[3][1]=40; MGr.edges[1][5]=MGr.edges[5][1]=80; MGr.edges[1][9]=MGr.edges[9][1]=100; MGr.edges[2][3]=MGr.edges[3][2]=20; MGr.edges[2][4]=MGr.edges[4][2]=40; MGr.edges[4][6]=MGr.edges[6][4]=50; MGr.edges[4][8]=MGr.edges[8][4]=70; MGr.edges[5][9]=MGr.edges[9][5]=10; MGr.edges[6][7]=MGr.edges[7][6]=8; MGr.edges[6][12]=MGr.edges[12][6]=90; MGr.edges[7][8]=MGr.edges[8][7]=10; MGr.edges[8][9]=MGr.edges[9][8]=10; MGr.edges[9][11]=MGr.edges[11][9]=40; MGr.edges[10][11]=MGr.edges[11][10]=20;

void introduce() {

int n;

cout<<\"请输入查询景点编号:\"<>n; switch(n) {

case 1:cout<<\"景点编号:\"<称:\"<cout<<\"景点简介:\"<case 2: cout<<\"景点编号:\"<- 41 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

名称:\"<cout<<\"景点简介:\"<case 3: cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 4: cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 5: cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 6: cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 7:cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 8: cout<<\"景点编号:\"<cout<<\"景点简介:\"<case 9: cout<<\"景点编号:\"<cout<<\"景点简介:\"<break;

case 10:cout<<\"景点编号:\"<名称:\"<cout<<\"景点简介:\"<break;

- 42 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

case 11 cout<<\"景点编号:\"<点名称:\"<cout<<\"景点简介:\"<break;

case 12: cout<<\"景点编号:\"<点名称:\"<cout<<\"景点简介:\"<break;

default:

cout<<\"输入序号错误。\"; break; }} void floyd() {

int i,j,k;

for(i=1;i<=T;i++) { }

for(j=1;j<=T;j++) { }

//初始化数组

shortest[i][j]=MGr.edges[i][j]; path[i][j]=0;

for(k=1;k<=T;k++) {

for(i=1;i<=T;i++) {

for(j=1;j<=T;j++) {

if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {

shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k;

//记录经过的路径}}}}}

void display(int i,int j) { // 打印两个景点的路径及最短距离

int a,b; a=i; b=j;

cout<<\"您要查询的两景点间最短路径是:\\n\\n\"; if(shortest[i][j]!=MaxVertexNum) {

if(iwhile(path[i][j]!=0) { // 把i到j的路径上所有经过的景点按逆序打印出来

- 43 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

}

cout<<\"<-\"<j=path[i][j]; i=path[j][i]; else

cout<<\"<-\"<cout<\"<cout<cout<<\"->\"<cout<<\"->\"<while(path[i][j]!=0) {// 把i到j的路径上所有经过的景点按顺序打印出来

cout<\"<else }

int shortestdistance() { }

void main()

{

int i,j;

cout<<\"请输入要查询的两个景点的编号(1->11的数字编号并用空格cin>>i>>j; floyd(); display(i,j); return 1;

//要查找的两景点的最短距离

cout<<\"输入错误!不存在此路!\\n\\n\";

间隔):\";

- 44 -

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

char k; init();

cout<<\"*********************************************\"<- 45 -

cout<<\"* *\"<cout<<\"* ⑴学校后门 *\"<cout<<\"1.景点信息查询请按 i 键\"<>k; switch(k) {

case 'i':

cout<<\"景点简介查询(请输入1~11)。\"; introduce(); break;

cout<<\"景点最短路径查询。\"; shortestdistance(); break; exit(0); } }}

cout<<\"************************************************\"<case 's':

case 'e':

数据结构课程设计报告 计算机学院 网络123班 薛鑫路 201000824109

四.总结

本学期学习了由苗老师担任任课教师的《数据结构》课程。

感觉自己受益匪浅。

在数据结构的课程当中 ,学习到了许多算法知识,对以前的许多程序都有了重新的认识与理解,也为许多新接触的程序找到了设计的方法。此外,感觉经过对数据结构相关知识的学习,自己的逻辑思维也有所增强,尤其是经过这次《数据结构》课程设计,使得这一学期的理论学习得以实践,这样不但得以对所学知识的总结与巩固,也使得自己对编写程序尤其是对数据结构相关程序的编写的兴趣得以大大提高。在以后的学习当中,这部分《数据结构》的知识相信会很有帮助。

- 46 -

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- 版权所有