西南交通大学
《数据结构》课程设计
北京至其他省会的最短路径
学生班级：一向上吧，少年一
学生学号：2013XXXX
任课教师：赵宏宇
信息科学与技术学院
20##年12月8日
一、实验内容描述：
在I盘下建立一个Graphic_data.txt文件，文件中储存邻接图矩阵，从文件中读取图的数据，按照如下格式：
int ventex edge
int i j weight
注： ventex 顶点数 edge 弧数
i 行坐标 j列坐标 weight 弧权值
将读取到的数据存储到自己定义的图的邻接矩阵数据结构中，dist数组和past数组。辅助向量dist[0....n-1],该向量用于储存n-1条最短路径的长度。path数组保存最短路径的顶点顺序。
二、输入输出设计：
输入：
1.从文件中读取图的邻接矩阵数据，包括顶点数、边数、矩阵的下标以及矩阵的权值。
2.从文件中读取顶点顺序对应的城市名称。
输出：
1.图的最短路径以及顶点的访问顺序。
2.对应的城市名称访问顺序，
1、输入:
I盘下 Graph_data1.txt文件
I盘下City_number.txt文件
2、输出 :
城市顶点编号为:
**************************************************************************
v0---南宁
v1---柳州 v2---株洲 v3---广州 v4---深圳 v5---南昌 v6---福州
v7---贵阳 v8---昆明 v9---成都 v10---上海 v11---徐州 v12---天津
v13---沈阳 v14---大连 v15---长春 v16---哈尔滨 v17---武汉 v18---郑州
v19---西安 v20---兰州 v21---沈阳西宁 v22---乌鲁木齐 v23---呼和浩特
v24---北京
**************************************************************************
假设终点为南宁，顶点号为V0.
最短路径长度为:
2565
最短路径的顶点次序:
v24 -> v18 -> v17 -> v2 -> v1 -> v0
城市顺序
北京 -> 郑州 -> 武汉 -> 株洲 -> 柳州 -> 南宁
三、迪杰特斯拉算法要点描述：
首先，引入辅助向量dist[0..n-1]，该向量用于存储n-1条最短路径的长度。
path[1...n-1]，该量量存储最短路径的顶点顺序。
1、初始时，输入起点begin初始化dist[]数组。
2、求出dist数组中的最小值，作为最短路径顶点Vmin，并将Vmin加入到S集合中。
3、从S集合中不存在的顶点继续出发，寻找下一个Vmin，如果dist[后面] 4、重复上次步骤直到结束，那么dist[n-1]包含的值即更新为最小权值和，即最短路径长度。path[n-1]为最短路径的顶点顺序。 5、最后将得到的数据全部保存到data.txt文件下。 注：具体实现主要函数如下： 1. 程序定义的数据结构： 2. 从文件中读取数据创建邻接矩阵： 3.Dijkstra关键最短路径算法实现函数： 4. 将得到的数据保存到I盘下的Data.txt文件中： 四、算法实现代码： 五、程序运行截图： I盘下Graphic_data1.txt文件数据: I盘下City_number.txt文件数据： 运行输出的Data.txt文件，保存北京为起点到所有城市的最短路径： 五、问题与讨论： 虽然说这次的实验不算难，但是还是不好做，因为上一次做这个实验的数据量很小，所以自己写的程序完全可以运行，而且没有任何错误，但是这次实验的数据量有点大，我按照自己写的实现算法代码，在所要求得北京到其他24个城市的最短路径其中有北京到一个城市的最短路径求出来结果有问题，最后我找来找去，发现是自己在求每一次dist[]数组的最小值的时候算法不是很正确，最后经过思考以及参考老师的代码发现，老师写的代码很精简，比我自己的要好很多，所以最后借鉴了老师的方法。这算是这次实验中遇到的一个比较大的问题吧，还有发现自己理解了的代码以及自己在纸上推敲后感觉毫无错误的代码总是上机后发现错误很多，所以下来自己还是要锻炼多上机敲代码。 《数据结构》课程设计 实验报告 题 目 双向链表 学 院 专 业 计算机科学与技术 班 级 学 号 学生姓名 指导教师 编写日期 2010-7-16 目录 1. 问题分析……………………………………………….3 1.1基本要求…………………………………………………..3 1.2分析过程…………………………………………………..3 2. 数据结构描述………………………………………….3 3. 算法设计……………………………………………….4 3.1算法1：双向链表的建立………………………………..4 3.2算法2：双向链表的查找…………………………………4 3.3算法3：双向链表的插入………………………………..5 3.4算法4：双向链表的删除………………………………..5 4. 程序清单………………………………………………6 5. 程序运行结果…………………………………………10 6. 总结……………………………………………………11 ? 1.问题分析 1.1【基本要求】：建立双向链表，并进行插入，查找，删除等 2 操作。 1.2【分析过程】：先通过创建函数建立双向链表，由文本文件提供数据。可以调用查找函数，查找与e值相同的结点是否存在；也可以通过插入函数，在第i个结点前插入值为e的结点，并且调节指针的变化；也可以调用删除函数，删除第i个结点，调节好指针，最后通过保存函数保留数据到文本文件中。 ? 2.数据结构描述 #include #include using namespace std; typedef struct dulnode{ int data; struct dulnode *prior; struct dulnode *next; }dulnode,*dulinklist; ? 3.算法设计 3.1算法1：创建双向链表 3 status create_dul(dulinklist &l) /*利用尾插法建立头带头结点的双向链表 */ { l=(dulinklist)malloc(sizeof(dulnode)); /* 生成头结点 */ l->prior=NULL; l->next=NULL; /* 头结点的指针域初始值为空 */ l->data=-1; q=l; /* 尾指针初始指向头结点 */ FILE* fp; /* 定义文件指针的形式 */ if((fp=fopen("F:\\test1.txt","r+"))==NULL) /* 打开文本文件 */ { printf("cannot open file!\n"); exit(0); } int n; fscanf(fp,"%d",&n); for(i=0;i { p = (dulinklist)malloc(sizeof(dulnode)); fscanf(fp,"%d",&p->data); /* 在文件读取结点的数据 */ p->next=NULL; /* 新结点指针域为空 */ p->prior=q; q->next=p; /* 尾结点指针域指向新结点 */ q=p; /* q指针后移，始终指向尾指针 */ } fclose(fp); /* 关闭文本文件 */ } 3.2算法2：双向链表的查找 stadus locateelem_dul(dulinklist l,elemtype e) /* 查找双线链表中第一个值为e的结点位置*/ { p=l->next; /* p指向第一个结点 */ j=1; /* j表示结点位置 */ while((p->data!=e)&&p){ p=p->next; ++j; } /* 寻找第一个值为e的结点位置 */ if(!p) return -1; 4 else return 1; } 3.3算法3：双向链表的插入 status listinsert_dul(dulinklist &l,int i,elemtype e) /* 在双向链表l中的第i个位置之前插入新结点s */ { p=l; /* p指向头结点 */ j=0; /* j表示结点位置 */ while(p&&(j p=p->next; ++j; } /* 寻找第i-1个结点位置 */ if(!p||j>i-1) return ERROR; /* 在l中确定插入位置，p=NULL或j>i-1时，即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode)))) return ERROR; /* 动态生成新结点失败，则返回错误 */ s->data=e; /* 给新结点的数据域赋值 */ s->next=p->next; p->next->prior=s; s->prior=p; p->next=s; /* 在双向链表中插入新结点时指针的变化 */ return 0; } 3.4算法4：双向链表的删除 status listdelete_dul(dulinklist &l,int i,elemtype &e) /* 在双向链表l中，删除第i个结点 */ { p=l->next; /* p指向第一个结点 */ int j=1; /* j表示结点位置 */ while(p&&(j p=p->next; ++j; } /* 寻找第i个结点 */ if(!p||j>i) return ERROR; /* 在l中确定第i个元素的位置指针p，p=NULL，即第i个元素不存在 */ e=p->data; /* 把指针p的数据域的值赋给e */ p->prior->next=p->next; 5 p->next->prior=p->prior; /* 在双向链表中删除结点时指针的变化 */ free(p); /* 把结点p删掉 */ return 0; } ? 4.程序清单 #include #include using namespace std; typedef struct dulnode{ int data; /* 数据域 */ struct dulnode *prior; /* 指向前驱的指针域 */ struct dulnode *next; /* 指向后继的指针域 */ }dulnode,*dulinklist; void create_dul(dulinklist &l) /*利用尾插法建立头带头结点的双向链表 */ { dulinklist p,q; int i; l=(dulinklist)malloc(sizeof(dulnode)); /* 生成头结点 */ l->prior=NULL; l->next=NULL; /* 头结点的指针域初始值为空 */ l->data=-1; q=l; /* 尾指针初始指向头结点 */ FILE* fp; /* 定义文件指针的形式 */ if((fp=fopen("H:\\test1.txt","r+"))==NULL) /* 打开文本文件 */ { printf("cannot open file!\n"); exit(0); } int n; fscanf(fp,"%d",&n); for(i=0;i { p = (dulinklist)malloc(sizeof(dulnode)); fscanf(fp,"%d",&p->data); /* 在文件读取结点的数据 */ p->next=NULL; /* 新结点指针域为空 */ 6 p->prior=q; q->next=p; /* 尾结点指针域指向新结点 */ q=p; /* q指针后移，始终指向尾指针 */ } fclose(fp); /* 关闭文本文件 */ } dulinklist listinsert_dul(dulinklist &l,int i,int e) /* 在双向链表l中的第i个位置之前插入新结点s */ { dulinklist p,s; p=l; /* p指向头结点 */ int j=0; /* j表示结点位置 */ while(p&&(j p=p->next; ++j; } /* 寻找第i-1个结点位置 */ if(!p||j>i-1) return NULL; /* 在l中确定插入位置，p=NULL或j>i-1时，即插入位置不合法 */ if(!(s=(dulinklist)malloc(sizeof(dulnode)))) return NULL; /* 动态生成新结点失败，则返回错误 */ s->data=e; /* 给新结点的数据域赋值 */ s->next=p->next; p->next->prior=s; s->prior=p; p->next=s; /* 在双向链表中插入新结点时指针的变化 */ return 0; } dulinklist listdelete_dul(dulinklist &l,int i,int &e) /* 在双向链表l中，删除第i个结点 */ { dulinklist p; p=l->next; /* p指向第一个结点 */ int j=1; /* j表示结点位置 */ while(p&&(j p=p->next; ++j; } /* 寻找第i个结点 */ if(!p||j>i) return NULL; /* 在l中确定第i个元素的位置指针p，p=NULL，即第i个元素不存在 */ e=p->data; /* 把指针p的数据域的值赋给e */ 7 p->prior->next=p->next; p->next->prior=p->prior; /* 在双向链表中删除结点时指针的变化 */ free(p); /* 把结点p删掉 */ return 0; } int locateelem_dul(dulinklist l,int e) /* 查找双线链表中第一个值为e的结点位置*/ { dulinklist p; int j; p=l->next; /* p指向第一个结点 */ j=1; /* j表示结点位置 */ while((p->data!=e)&&p){ p=p->next; ++j; } /* 寻找第一个值为e的结点位置 */ if(!p) return -1; /* 返回第一个值为e的结点位置 */ else return 1; } void print_dul(dulinklist l) /* 打印双向链表l */ { dulinklist p; p=l; /* p指向头结点 */ while(p){ printf("% d",p->data); p=p->next; } /* 把双向链表中的数据都打印出来 */ } void save_dul(dulinklist l) { FILE* fp; if((fp=fopen("H:\\test2.txt","w+"))==NULL) { printf("cannot open file!\n"); exit(0); 8 } while(l) { fprintf(fp,"%d ",l->data); l = l->next; } } void main(){ dulinklist l; int i,e,x; int pos; create_dul(l); /* 调用双向链表建立函数 */ print_dul(l); /* 调用双向链表的打印函数 */ while(1){ printf("input x to choose (1.查找,2.插入,3.删除,4.0ver ): \n"); scanf("%d",&x); switch(x){ case 1: printf("\n please input the data you want to locate: \n"); scanf("%d",&e); /* 输入要查找的值 */ pos=locateelem_dul(l,e); /* 调用双向链表的查找函数 */ if(pos==-1) printf("The data is not found! \n"); else printf("The data is found! \n");break; case 2: printf("please input the position you want to insert: \n"); scanf("%d",&i); /* 输入要插入的位置 */ printf("please input the data you want to insert: \n"); scanf("%d",&e); /* 输入新结点的数据 */ listinsert_dul(l,i,e); /* 调用双向链表的插入函数 */ print_dul(l); break; /* 调用双向链表的打印函数 */ case 3: printf("\n please input the position you want to delete: \n"); scanf("%d",&i); /* 输入要删除结点的位置 */ listdelete_dul(l,i,e); /* 调用双向链表的删除函数 */ print_dul(l);break; /* 调用双向链表的打印函数 */ 9 case 4: save_dul(l); exit(0); } } } ? 5.程序运行结果 ? 6.总结: 通过此次数据结构的课程设计，我对程序的编程，编译，执行等有了更深的认识。理解到思路对于一个程序的重要性，在整个设计过程中，遇到了很多不同的问题，但通过 10 尝试，努力和老师的帮助最终都解决了，感到很有成就感。从中，我意识到程序的成功不仅仅是消除语法上的错误，而且还要执行成功。缺乏完整的思路，尽管语法正确，程序还是无法执行。数据结构的设计考验的不仅仅是我们对书本知识的理解，还考验了我们分析事物时思维的逻辑紧密性，加深并巩固了我对数据结构的认识。总的来说，这次的数据结构课程设计加深了我对数据结构的认识，也学到了相关的知识，并且巩固了课堂上所学的知识，还锻炼了实践的应用操作能力，感受颇深，也收获了成功的喜悦。 11
第二篇：数据结构课程设计_双向链表
