0
0

本科课程【数据结构与算法】实验6 - 创建哈希表、最短路径（Dijkstra算法）

大家好，我是【1+1=王】， 热爱java的计算机（人工智能）渣硕研究生在读。
如果你也对java、人工智能等技术感兴趣，欢迎关注，抱团交流进大厂！！！
Good better best, never let it rest, until good is better, and better best.

近期会把自己本科阶段的一些课程设计、实验报告等分享出来，供大家参考，希望对大家有帮助。

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

一、 实验目的

  1. 实现哈希表的创建
  2. 利用线性探测在散列处理冲突
  3. 掌握图的邻接矩阵表示
  4. 实现图的最短路径查找操作（Di jkstra算法）

二、 实验内容

1. 实验任务

（1）创建哈希表
（2）利用Di jkstra算法寻找图的最短路径

2. 程序设计

1） 数据输入（输入哪些数据、个数、类型、来源、输入方式）
输入哈希表的关键数key（int 整型）

图的顶点数据（data）char字符型；
图的边关系（v1,v2）int 整型；
各边的权值（w）int 整型

2） 数据存储（输入数据在内存中的存储）
定义结构体Hash（key，si）
以数组HashList[i]存储各条数据

采用邻接矩阵存储图

3） 数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）
（1）
①哈希表的查找
储存数据时，将数据存入通过哈希函数所得的地址里，使用同一个哈希函数通过关键字key计算出储存地址，通过该地址访问到查找的记录
②冲突解决
使用线性探测再散列法（冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表）
（2）
在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径；
设置一个顶点集合S，存放最短路径的终点。顶点k为当前最短路径的终点，将Vk加入集合S中，而Dist[k]为最短路径的长度；
每次从集合V-S中取出具有最短特殊路径长度的顶点u，将u加到S中，同时对数组Dist做必要的修改，若Dist[u]+G.arcs[u][k]<Dist[k]则将Dist[k]改为Dist[u]+arcs[u][k]。其中，特殊路径指从源点到u中间只经过S中顶点的路径；
重复操作2）、3）共n-1次1

4） 数据输出
在这里插入图片描述
在这里插入图片描述

三、 实验环境

  1. 操作系统：WINDOWS 10
  2. 开发工具：VC++ 2013
  3. 实验设备：PC

源代码（C++实现）

创建哈希表

#include<stdio.h>#include<iostream>
using namespace std;#defineMaxSize100//定义最大哈希表长度#defineNULLKEY-1//定义空关键字值#defineDELKEY-2//定义被删关键字值typedefint KeyType;//关键字类型typedefchar*InfoType;//其他数据类型typedefstruct{
    KeyType key;//关键字域
    InfoType data;//其他数据域int count;//探查次数域}HashTable[MaxSize];//哈希表类型voidInsertHT(HashTable ha,int&n, KeyType k,int p);voidCreateHT(HashTable ha, KeyType x[],int n,int m,int p);intSearchHT(HashTable ha,int p, KeyType k);intDeleteHT(HashTable ha,int p,int k,int&n);voidDispHT(HashTable ha,int n,int m);voidCompASL(HashTable ha,int m);voidmain(){int x[]={16,74,60,43,54,90,46,31,29,88,77};int n =11, m =13, p =13, i, k =29;
    HashTable ha;CreateHT(ha, x, n, m, p);
    cout << endl;DispHT(ha, n, m);
    i =SearchHT(ha, p, k);if(i !=-1)printf(" ha[%d].key=%d\n", i, k);else
        cout <<"未找到"<< k << endl;
    k =77;printf(" 删除关键字%d\n", k);DeleteHT(ha, p, k, n);DispHT(ha, n, m);
    i =SearchHT(ha, p, k);if(i !=-1)printf(" ha[%d].key=%d\n", i, k);elseprintf(" 未找到%d\n", k);printf(" 插入关键字%d\n", k);InsertHT(ha, n, k, p);DispHT(ha, n, m);
    cout << endl;system("pause");}//将关键字k插入到哈希表中voidInsertHT(HashTable ha,int&n, KeyType k,int p){int i, adr;
    adr = k%p;if(ha[adr].key == NULLKEY || ha[adr].key == DELKEY){
        ha[adr].key = k;
        ha[adr].count =1;}else//发生冲突时,采用线性探查法解决冲突{
        i =1;do{
            adr =(adr +1)% p;
            i++;}while(ha[adr].key != NULLKEY && ha[adr].key != DELKEY);
        ha[adr].key = k;
        ha[adr].count = i;}
    n++;}//创建哈希表voidCreateHT(HashTable ha, KeyType x[],int n,int m,int p){int i, n1 =0;for(i =0; i<m; i++)//哈希表置初值{
        ha[i].key = NULLKEY;
        ha[i].count =0;}for(i =0; i<n; i++)InsertHT(ha, n1, x[i], p);}//在哈希表中查找关键字kintSearchHT(HashTable ha,int p, KeyType k){int i =0, adr;
    adr = k%p;while(ha[adr].key != NULLKEY && ha[adr].key != k){
        i++;//采用线性探查法找下一个地址
        adr =(adr +1)% p;}if(ha[adr].key == k)//查找成功return adr;else//查找失败return-1;}//删除哈希表中关键字kintDeleteHT(HashTable ha,int p,int k,int&n){int adr;
    adr =SearchHT(ha, p, k);if(adr !=-1)//在哈希表中找到关键字{
        ha[adr].key = DELKEY;
        n--;//哈希表长度减1return1;}else//在哈希表中未找到该关键字return0;}//输出哈希表voidDispHT(HashTable ha,int n,int m){float avg =0;int i;
    cout<<" 哈希表地址:";for(i =0; i<m; i++)
        cout<<i<<"  ";
    cout << endl;
    cout<<" 哈希表关键字:";for(i =0; i<m; i++)if(ha[i].key == NULLKEY || ha[i].key == DELKEY)
        cout<<"   ";else
        cout<<ha[i].key<<"  ";
    cout<<endl;
    cout<<" 搜索次数:\t";for(i =0; i<m; i++)if(ha[i].key == NULLKEY || ha[i].key == DELKEY)
        cout<<"   ";else
        cout<<ha[i].count<<"  ";
    cout << endl;for(i =0; i<m; i++)if(ha[i].key != NULLKEY && ha[i].key != DELKEY)
        avg = avg + ha[i].count;
    avg = avg / n;
    cout <<" 平均搜索长度ASL="<< avg << endl;}//查找成功时，平均查找长度voidCompASL(HashTable ha,int m){int i;int s =0, n =0;for(i =0; i<m; i++)if(ha[i].key != DELKEY && ha[i].key != NULLKEY){
        s = s + ha[i].count;
        n++;}printf(" 查找成功的ASL=%.3g\n", s*1.0/ n);}

最短路径

#include<stdio.h>#include<stdlib.h>#include<iostream>#include<string.h>
using namespace std;#defineMAX100// 矩阵最大容量#defineINF65535// 最大值65535#defineLENGTH(a)(sizeof(a)/sizeof(a[0]))// 图的邻接矩阵存储typedefstruct_graph{char vexs[MAX];// 顶点集合int vexnum;// 顶点数int edgnum;// 边数int matrix[MAX][MAX];// 邻接矩阵}Graph,*PGraph;// 边的结构体typedefstruct_EdgeData{char start;// 边的起点char end;// 边的终点int weight;// 边的权重}EData;

Graph*create_graph();voidprint_graph(Graph G);voiddijkstra(Graph G,int vs,int prev[],int dist[]);intmain(){int vs;int prev[MAX]={0};int dist[MAX]={0};
    Graph* pG;
    pG =create_graph();print_graph(*pG);// 打印图
    cout <<"从第几个节点开始寻找最短路径：";
    cin >> vs;dijkstra(*pG, vs, prev, dist);system("pause");return0;}/*
* 创建图(用已提供的矩阵)
*/
Graph*create_graph(){char vexs[]={'A','B','C','D','E','F','G'};int matrix[][9]={/*A*//*B*//*C*//*D*//*E*//*F*//*G*//*A*/{0,12, INF, INF, INF,16,14},/*B*/{12,0,10, INF, INF,7, INF },/*C*/{ INF,10,0,3,5,6, INF },/*D*/{ INF, INF,3,0,4, INF, INF },/*E*/{ INF, INF,5,4,0,2,8},/*F*/{16,7,6, INF,2,0,9},/*G*/{14, INF, INF, INF,8,9,0}};int vlen =LENGTH(vexs);int i, j;
    Graph* pG;
    pG =(Graph*)malloc(sizeof(Graph));
    pG->vexnum = vlen;for(i =0; i < pG->vexnum; i++)
        pG->vexs[i]= vexs[i];for(i =0; i < pG->vexnum; i++){for(j =0; j < pG->vexnum; j++)
            pG->matrix[i][j]= matrix[i][j];}for(i =0; i < pG->vexnum; i++){for(j =0; j < pG->vexnum; j++)if(i != j && pG->matrix[i][j]!= INF)
            pG->edgnum++;}
    pG->edgnum /=2;return pG;}/*
* 打印矩阵队列图
*/voidprint_graph(Graph G){int i, j;
    cout <<"Martix Graph:"<< endl;;for(i =0; i < G.vexnum; i++){for(j =0; j < G.vexnum; j++)printf("%10d ", G.matrix[i][j]);
        cout << endl;}}/*
* Dijkstra最短路径。
* 统计图(G)中"顶点vs"到其它各个顶点的最短路径。
*
* 参数说明：
*        G -- 图
*       vs -- 起始顶点(start vertex)。计算"顶点vs"到其它顶点的最短路径。
*     prev -- 前驱顶点数组。
*     dist -- 长度数组。
*/voiddijkstra(Graph G,int vs,int prev[],int dist[]){int i, j, k;int min;int tmp;int flag[MAX];// flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。// 初始化for(i =0; i < G.vexnum; i++){
        flag[i]=0;// 顶点i的最短路径还没获取到。
        prev[i]=0;// 顶点i的前驱顶点为0。
        dist[i]= G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。}// 对"顶点vs"自身进行初始化
    flag[vs]=1;
    dist[vs]=0;// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。for(i =1; i < G.vexnum; i++){// 寻找当前最小的路径；
        min = INF;for(j =0; j < G.vexnum; j++){if(flag[j]==0&& dist[j]<min){
                min = dist[j];
                k = j;}}// 标记"顶点k"为已经获取到最短路径
        flag[k]=1;// 修正当前最短路径和前驱顶点// 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。for(j =0; j < G.vexnum; j++){
            tmp =(G.matrix[k][j]== INF ? INF :(min + G.matrix[k][j]));// 防止溢出if(flag[j]==0&&(tmp  < dist[j])){
                dist[j]= tmp;
                prev[j]= k;}}}// 打印dijkstra最短路径的结果printf("dijkstra(%c): \n", G.vexs[vs]);for(i =0; i < G.vexnum; i++)printf("  shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);}

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

标签： 哈希表 最短路径 迪杰斯特拉算法
本文转载自: https://blog.csdn.net/weixin_43598687/article/details/123726816
版权归原作者 1 + 1=王 所有， 如有侵权，请联系我们删除。
登录后发布评论

“本科课程【数据结构与算法】实验6 - 创建哈希表、最短路径（Dijkstra算法）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航