A. 怎样用DIJKSTRA算法设计最短路径
以下................
输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示
当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点
比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径
Dijkstra算法的完整实现版本，算法的源代码
/* Dijkstra.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
#include "stdio.h"
#include "malloc.h"
#define maxium 32767
#define maxver 9 /*defines the max number of vertexs which the programm can handle*/
#define OK 1
struct Point
{
char vertex[3];
struct Link *work;
struct Point *next;
};
struct Link
{
char vertex[3];
int value;
struct Link *next;
};
struct Table /*the workbannch of the algorithm*/
{
int cost;
int Known;
char vertex[3];
char path[3];
struct Table *next;
};
int Dijkstra(struct Point *,struct Table *);
int PrintTable(int,struct Table *);
int PrintPath(int,struct Table *,struct Table *);
struct Table * CreateTable(int,int);
struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/
int main()
{
int i,j,num,temp,val;
char c;
struct Point *poinpre,*poinhead,*poin;
struct Link *linpre,*linhead,*lin;
struct Table *tabhead;
poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point));
poin->next=NULL;
poin->work=NULL;
restart:
printf("Notice:if you wanna to input a vertex,you must use the format of number!\n");
printf("Please input the number of points:\n");
scanf("%d",&num);
if(num>maxver||num<1||num%1!=0)
{
printf("\nNumber of points exception!");
goto restart;
}
for(i=0;i<num;i++)
{
printf("Please input the points next to point %d,end with 0:\n",i+1);
poin=(struct Point *)malloc(sizeof(struct Point));
poinpre->next=poin;
poin->vertex[0]='v';
poin->vertex[1]='0'+i+1;
poin->vertex[2]='\0';
linpre=lin=poin->work;
linpre->next=NULL;
for(j=0;j<num-1;j++)
{
printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1);
scanf("%d",&temp);
if(temp==0)
{
lin->next=NULL;
break;
}
else
{
lin=(struct Link *)malloc(sizeof(struct Link));
linpre->next=lin;
lin->vertex[0]='v';
lin->vertex[1]='0'+temp;
lin->vertex[2]='\0';
printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp);
scanf("%d",&val);
lin->value=val;
linpre=linpre->next;
lin->next=NULL;
}
}
poinpre=poinpre->next;
poin->next=NULL;
}
printf("Please enter the vertex where Dijkstra algorithm starts:\n");
scanf("%d",&temp);
tabhead=CreateTable(temp,num);
Dijkstra(poinhead,tabhead);
PrintTable(temp,tabhead);
return OK;
}
struct Table * CreateTable(int vertex,int total)
{
struct Table *head,*pre,*p;
int i;
head=pre=p=(struct Table *)malloc(sizeof(struct Table));
p->next=NULL;
for(i=0;i<total;i++)
{
p=(struct Table *)malloc(sizeof(struct Table));
pre->next=p;
if(i+1==vertex)
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=0;
p->Known=0;
}
else
{
p->vertex[0]='v';
p->vertex[1]='0'+i+1;
p->vertex[2]='\0';
p->cost=maxium;
p->Known=0;
}
p->next=NULL;
pre=pre->next;
}
return head;
}
int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/
{
int costs;
char temp;
struct Point *poinhead=p1,*now;
struct Link *linna;
struct Table *tabhead=p2,*searc,*result;
while(1)
{
now=FindSmallest(tabhead,poinhead);
if(now==NULL)
break;
result=p2;
result=result->next;
while(result!=NULL)
{
if(result->vertex[1]==now->vertex[1])
break;
else
result=result->next;
}
linna=now->work->next;
while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/
{
temp=linna->vertex[1];
searc=tabhead->next;
while(searc!=NULL)
{
if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/
{
if((result->cost+linna->value)<searc->cost)
{
searc->cost=result->cost+linna->value;/*set the new value*/
searc->path[0]='v';
searc->path[1]=now->vertex[1];
searc->path[2]='\0';
}
break;
}
else
searc=searc->next;
}
linna=linna->next;
}
}
return 1;
}
struct Point * FindSmallest(struct Table *head,struct Point *poinhead)
{
struct Point *result;
struct Table *temp;
int min=maxium,status=0;
head=head->next;
poinhead=poinhead->next;
while(head!=NULL)
{
if(!head->Known&&head->cost<min)
{
min=head->cost;
result=poinhead;
temp=head;
status=1;
}
head=head->next;
poinhead=poinhead->next;
}
if(status)
{
temp->Known=1;
return result;
}
else
return NULL;
}
int PrintTable(int start,struct Table *head)
{
struct Table *begin=head;
head=head->next;
while(head!=NULL)
{
if((head->vertex[1]-'0')!=start)
PrintPath(start,head,begin);
head=head->next;
}
return OK;
}
int PrintPath(int start,struct Table *head,struct Table *begin)
{
struct Table *temp=begin->next,*p,*t;
p=head;
t=begin;
if((p->vertex[1]-'0')!=start&&p!=NULL)
{
while(temp->vertex[1]!=p->path[1]&&temp!=NULL)
temp=temp->next;
PrintPath(start,temp,t);
printf("%s",p->vertex);
}
else
if(p!=NULL)
printf("\n%s",p->vertex);
return OK;
}
B. 10个常用算法
原理：
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
一般步骤：
（1）确定该区间的中间位置K；
（2）将查找的值T与array[k]比较。
若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间将缩小一半，递归查找即可。
原理：
一种通过重复将问题分解为同类的子问题而解决问题的方法
典型例子：
斐波那契数列
描述： 斐波那契数列 指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368.....自然中的斐波那契数列") 自然中的斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。
解决方式：
原理：
在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
解决问题一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
典型例子：
八皇后问题
描述：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
解决方式： https://blog.csdn.net/weixin_41865447/article/details/80034433
概念：
将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。
分类：
非稳定排序算法：快速排序、希尔排序、堆排序、直接选择排序
稳定的排序算法：基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序
十个常用排序算法
利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。
分类：
枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。
将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。
很难找到逆向规律
只要符合散列思想的算法都可以被称为是Hash算法
对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称为 碰撞 。
原理
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在 某种意义上的局部最优解 。
从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
一种近似算法
一般步骤：
1、建立数学模型来描述问题；
2、把求解的问题分成若干个子问题；
3、对每一子问题求解，得到子问题的局部最优解；
4、把子问题的解局部最优解合成原来解问题的一个解。
典型例子：
0/1背包问题
马踏棋盘
均分纸牌
例题： https://www.cnblogs.com/hust-chen/p/8646009.html
概念：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
一般步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
典型例子：
排序中：归并排序、堆排序、快速排序；
实例：找伪币、求最值、棋盘覆盖
https://ke..com/item/%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95/3263297
概念：
用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济）等；
应用实例：
最短路径问题 ，项目管理，网络流优化等；
https://ke..com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408?fromtitle=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%AE%97%E6%B3%95&fromid=15742703&fr=aladdin
概念：
在一个给定的字符文本内搜寻出自己想要找的一个字符串，平常所用的各种文本编辑器里的ctrl+F大多就是使用的这些字符匹配算法。
分类：
KMP、BM、Sunday、Horspool、RK
参考：
https://cloud.tencent.com/developer/news/282694
https://blog.csdn.net/paincupid/article/details/81159320