宽度优先算法c语言

❶ C语言算法有哪些 并举例和分析

算法大全（C，C++）
一、 数论算法

1．求两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;

2．求两数的最小公倍数
function lcm(a,b:integer):integer;
begin
if a<b then swap(a,b);
lcm:=a;
while lcm mod b>0 do inc(lcm,a);
end;

3．素数的求法
A.小范围内判断一个数是否为质数：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then begin
prime:=false; exit;
end;
prime:=true;
end;

B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i<50000 do begin
if p[i] then begin
j:=i*2;
while j<50000 do begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p[i] then begin
inc(l);pr[l]:=i;
end;
end;{getprime}

function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr[i]>=x then break
else if x mod pr[i]=0 then exit;
prime:=true;
end;{prime}

二、图论算法

1．最小生成树

A.Prim算法：

procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]<lwocost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}

B.Kruskal算法：(贪心)

按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
var i:integer;
begin
i:=1;
while (i<=n) and (not v in vset[i]) do inc(i);
if i<=n then find:=i else find:=0;
end;

procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
while p>0 do begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i<>j then begin
inc(tot,e[q].len);
vset[i]:=vset[i]+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;

2.最短路径

A.标号法求解单源点最短路径：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径}
mark:array[1..maxn] of boolean;

procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1为源点}
repeat
best:=0;
for i:=1 to n do
If mark[i] then {对每一个已计算出最短路径的点}
for j:=1 to n do
if (not mark[j]) and (a[i,j]>0) then
if (best=0) or (b[i]+a[i,j]<best) then begin
best:=b[i]+a[i,j]; best_j:=j;
end;
if best>0 then begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}

B.Floyed算法求解所有顶点对之间的最短路径：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点}
for k:=1 to n do {枚举中间结点}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]<a[i,j] then begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;

C. Dijkstra 算法：

var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre[i]指最短路径上I的前驱结点}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do begin
d[i]:=a[v0,i];
if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;
end;
mark[v0]:=true;
repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
min:=maxint; u:=0; {u记录离1集合最近的结点}
for i:=1 to n do
if (not mark[i]) and (d[i]<min) then begin
u:=i; min:=d[i];
end;
if u<>0 then begin
mark[u]:=true;
for i:=1 to n do
if (not mark[i]) and (a[u,i]+d[u]<d[i]) then begin
d[i]:=a[u,i]+d[u];
pre[i]:=u;
end;
end;
until u=0;
end;

3.计算图的传递闭包

Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;

4．无向图的连通分量

A.深度优先
procere dfs ( now,color: integer);
begin
for i:=1 to n do
if a[now,i] and c[i]=0 then begin {对结点I染色}
c[i]:=color;
dfs(I,color);
end;
end;

B 宽度优先（种子染色法）

5．关键路径

几个定义： 顶点1为源点，n为汇点。
a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve (1) = 0;
b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 Vl(n) = Ve(n);
c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表示，则Ee[I] = Ve[j];
d. 边活动最晚开始时间 El[I], 若边I由<j,k>表示，则El[I] = Vl[k] – w[j,k];
若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。
求解方法：
a. 从源点起topsort,判断是否有回路并计算Ve;
b. 从汇点起topsort,求Vl;
c. 算Ee 和 El;

6．拓扑排序

找入度为0的点，删去与其相连的所有边，不断重复这一过程。
例 寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.

7.回路问题

Euler回路(DFS)
定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）

Hamilton回路
定义：经过图的每个顶点仅一次的回路。

一笔画
充要条件：图连通且奇点个数为0个或2个。

9．判断图中是否有负权回路 Bellman-ford 算法

x[I],y[I],t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。
procere bellman-ford
begin
for I:=0 to n-1 do d[I]:=+infinitive;
d[0]:=0;
for I:=1 to n-1 do
for j:=1 to m do {枚举每一条边}
if d[x[j]]+t[j]<d[y[j]] then d[y[j]]:=d[x[j]]+t[j];
for I:=1 to m do
if d[x[j]]+t[j]<d[y[j]] then return false else return true;
end;

10．第n最短路径问题

*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。
*同理，第n最短路径可在求解第n-1最短路径的基础上求解。

三、背包问题

*部分背包问题可有贪心法求解：计算Pi/Wi
数据结构：
w[i]:第i个背包的重量；
p[i]:第i个背包的价值；

1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：

A.求最多可放入的重量。
NOIP2001 装箱问题
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
l 搜索方法
procere search(k,v:integer); {搜索第k个物品，剩余空间为v}
var i,j:integer;
begin
if v<best then best:=v;
if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n个物品的重量和}
if k<=n then begin
if v>w[k] then search(k+1,v-w[k]);
search(k+1,v);
end;
end;

l DP
F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。
实现:将最优化问题转化为判定性问题
f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true.
For I:=1 to n do
For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];
优化：当前状态只与前一阶段状态有关，可降至一维。
F[0]:=true;
For I:=1 to n do begin
F1:=f;
For j:=w[I] to v do
If f[j-w[I]] then f1[j]:=true;
F:=f1;
End;

B.求可以放入的最大价值。
F[I,j] 为容量为I时取前j个背包所能获得的最大价值。
F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }

C.求恰好装满的情况数。
DP:
Procere update;
var j,k:integer;
begin
c:=a;
for j:=0 to n do
if a[j]>0 then
if j+now<=n then inc(c[j+now],a[j]);
a:=c;
end;

2．可重复背包

A求最多可放入的重量。
F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。
状态转移方程为
f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])

B.求可以放入的最大价值。
USACO 1.2 Score Inflation
进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。
*易想到：
f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])
其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。
*实现：
Begin
FillChar(f,SizeOf(f),0);
For i:=1 To M Do
For j:=1 To N Do
If i-problem[j].time>=0 Then
Begin
t:=problem[j].point+f[i-problem[j].time];
If t>f[i] Then f[i]:=t;
End;
Writeln(f[M]);
End.

C.求恰好装满的情况数。
Ahoi2001 Problem2
求自然数n本质不同的质数和的表达式的数目。
思路一，生成每个质数的系数的排列，在一一测试，这是通法。
procere try(dep:integer);
var i,j:integer;
begin
cal; {此过程计算当前系数的计算结果，now为结果}
if now>n then exit; {剪枝}
if dep=l+1 then begin {生成所有系数}
cal;
if now=n then inc(tot);
exit;
end;
for i:=0 to n div pr[dep] do begin
xs[dep]:=i;
try(dep+1);
xs[dep]:=0;
end;
end;

思路二，递归搜索效率较高
procere try(dep,rest:integer);
var i,j,x:integer;
begin
if (rest<=0) or (dep=l+1) then begin
if rest=0 then inc(tot);
exit;
end;
for i:=0 to rest div pr[dep] do
try(dep+1,rest-pr[dep]*i);
end;
{main: try(1,n); }

思路三：可使用动态规划求解
USACO1.2 money system
V个物品，背包容量为n，求放法总数。
转移方程：

Procere update;
var j,k:integer;
begin
c:=a;
for j:=0 to n do
if a[j]>0 then
for k:=1 to n div now do
if j+now*k<=n then inc(c[j+now*k],a[j]);
a:=c;
end;
{main}
begin
read(now); {读入第一个物品的重量}
i:=0; {a[i]为背包容量为i时的放法总数}
while i<=n do begin
a[i]:=1; inc(i,now); end; {定义第一个物品重的整数倍的重量a值为1，作为初值}
for i:=2 to v do
begin
read(now);
update; {动态更新}
end;
writeln(a[n]);

四、排序算法

A.快速排序：

procere qsort(l,r:integer);
var i,j,mid:integer;
begin
i:=l;j:=r; mid:=a[(l+r) div 2]; {将当前序列在中间位置的数定义为中间数}
repeat
while a[i]<mid do inc(i); {在左半部分寻找比中间数大的数}
while a[j]>mid do dec(j);{在右半部分寻找比中间数小的数}
if i<=j then begin {若找到一组与排序目标不一致的数对则交换它们}
swap(a[i],a[j]);
inc(i);dec(j); {继续找}
end;
until i>j;
if l<j then qsort(l,j); {若未到两个数的边界，则递归搜索左右区间}
if i<r then qsort(i,r);
end;{sort}

B.插入排序：

思路：当前a[1]..a[i-1]已排好序了，现要插入a[i]使a[1]..a[i]有序。
procere insert_sort;
var i,j:integer;
begin
for i:=2 to n do begin
a[0]:=a[i];
j:=i-1;
while a[0]<a[j] do begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=a[0];
end;
end;{inset_sort}

C.选择排序：
procere sort;
var i,j,k:integer;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then swap(a[i],a[j]);
end;

D. 冒泡排序
procere bubble_sort;
var i,j,k:integer;
begin
for i:=1 to n-1 do
for j:=n downto i+1 do
if a[j]<a[j-1] then swap( a[j],a[j-1]); {每次比较相邻元素的关系}
end;

E.堆排序：
procere sift(i,m:integer);{调整以i为根的子树成为堆,m为结点总数}
var k:integer;
begin
a[0]:=a[i]; k:=2*i;{在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1}
while k<=m do begin
if (k<m) and (a[k]<a[k+1]) then inc(k);{找出a[k]与a[k+1]中较大值}
if a[0]<a[k] then begin a[i]:=a[k];i:=k;k:=2*i; end
else k:=m+1;
end;
a[i]:=a[0]; {将根放在合适的位置}
end;

procere heapsort;
var
j:integer;
begin
for j:=n div 2 downto 1 do sift(j,n);
for j:=n downto 2 do begin
swap(a[1],a[j]);
sift(1,j-1);
end;

❷ 深度优先和广度优先 的区别 ，用法。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

(2)宽度优先算法c语言扩展阅读：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

❸ c语言数据结构（考题，测试你的能力）－－编写源代码

P88 稀疏矩阵十字链表相加算法如下：
/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};

struct linknode creatlindmat( ) /*建立十字链表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("请输入稀疏矩阵的行、列数及非零元个数\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("请输入一个三元组(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是将p插入到第i行链表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的两个稀疏矩阵相加，相加的结果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*删除一个结点*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*输出十字链表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}

void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一个十字链表ha*/
hb=creatlindmat( ); /*生成另一个十字链表hb*/
printf("A:\n"); /*输出十字链表ha*/
print(ha);printf("\n");
printf("B:\n"); /*输出十字链表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字链表相加*/
printf("A+B:\n"); /*输出相加后的结果*/
print(hc);printf("\n");
}

P94 数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}

P95 数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}

P96 求广义表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}

P96 广义表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}

P97 输出广义表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}

P98 该算法的时间复杂度为O(n)。整个完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};

void creat(struct node1 LS) /*建立广义表的单链表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求广义表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/
print(p); /*输出广义单链表*/
dep=depth(p); /*求广义表的深度*/
printf("%d\n",dep);
}

第六章 树
P109 二叉链表的结点类型定义如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;

P109 三叉链表的结点类型定义如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;

P112 C语言的先序遍历算法：
void preorder (tnodetype *t)
/*先序遍历二叉树算法，t为指向根结点的指针*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}

P113 C语言的中序遍历算法：
void inorder(tnodetype *t)
/*中序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}

P113 C语言的后序遍历算法：
void postorder(tnodetype *t)
/*后序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}

P114 如果引入队列作为辅助存储工具，按层次遍历二叉树的算法可描述如下：
void levelorder(tnodetype *t)
/*按层次遍历二叉树算法，t为指向根结点的指针*/
{tnodetype q[20]; /*辅助队列*/
front=0;
rear=0; /*置空队列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根结点入队*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，则入队*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，则入队*/
{ rear++;
q [rear]=t->rch;
}
}
}

P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为：
void inordercount (tnodetype *t)
/*中序遍历二叉树，统计树中的结点数和叶子结点数*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/
printf ("%c\n",t->data); /*访问根结点*/
countnode++; /*结点计数*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/
}
}

P115 可按如下方法计算一棵二叉树的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树，并计算二叉树的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*访问根结点*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍历左子树*/
preorderdeep (t->rch,j); /*先序遍历右子树*/
}
}

P117 线索二叉树的结点类型定义如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右标志域*/
}

P117 中序次序线索化算法
void inorderxs (struct nodexs *t)
/*中序遍历t所指向的二叉树，并为结点建立线索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向结点的左线索，令其指向前驱结点pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向结点的右线索，令其指向后继结点p*/
pr=p;
inorderxs (t->rch);
}
}

P118 在中根线索树上检索某结点的前驱结点的算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的前驱结点*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}

P119 在中根线索树上检索某结点的后继结点的算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的后继结点*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}

P120 算法程序用C语言描述如下：
void sortBT(BT *t,BT *s) /*将指针s所指的结点插入到以t为根指针的二叉树中*/
{ if (t==NULL) t=s; /*若t所指为空树，s所指结点为根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s结点插入到t的左子树上去*/
else
sortBT(t->rch,s); /*s结点插入到t的右子树上去*/
}

P121 二叉排序树结点删除算法的C语言描述如下：
void delnode(bt,f,p)
/*bt为一棵二叉排序树的根指针，p指向被删除结点，f指向其双亲*/
/*当p=bt时f为NULL*/
{ fag=0; /*fag=0时需修改f指针信息，fag=1时不需修改*/
if (p->lch==NULL)
s=p->rch; /*被删除结点为叶子或其左子树为空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被删除结点的左、右子树均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*寻找s结点*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的结点代替被删除结点*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改双亲指针*/
{ if (f=NULL)
bt=s; /*被删除结点为根结点*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*释放被删除结点*/
}
}

第七章 图
P134 用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：
# define n 6 /*图的顶点数*/
# define e 8 /*图的边(弧)数*/
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;

P135 建立一个无向网络的算法。
CREATGRAPH(ga) /*建立无向网络*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*读入顶点信息，建立顶点表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*邻接矩阵初始化*/
for(k＝0;k<e;k++) /*读入e条边*/
(scanf("％d％d％f",&I,&j,&w); /*读入边(vi,vj)上的权w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/

P136 邻接表的形式说明及其建立算法：
typedef struct node
{int adjvex; /*邻接点域*/
struct node * next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{vextype vertex; /*顶点信息*/
edgenode link; /*边表头指针*/
}vexnode; /*顶点表结点*/
vexnode ga[n];

CREATADJLIST(ga) /*建立无向图的邻接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*读入顶点信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*边表头指针初始化*/
}
for(k＝0;k<e;k++＝ /*建立边表*/
{scanf("％d％d",&i,&j); /*读入边(vi , vj)的顶点对序号*/
s＝malloc(sizeof(edgenode)); /*生成邻接点序号为j的表结点*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*将*s插入顶点vi的边表头部*/
s＝malloc(size0f(edgende)); /*生成邻接点序号为i的边表结点*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*将*s插入顶点vj的边表头部*/
}
} /* CREATADJLIST */

P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法，算法中g、g1和visited为全程量，visited的各分量初始值均为FALSE。
int visited[n] /*定义布尔向量visitd为全程量*/
Graph g; /*图g为全程量*/

DFS(i) /*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*访问出发点vi+1 */
Visited[i]＝TRUE; /*标记vi+l已访问过*/
for (j＝0;j<n;j++) /*依次搜索vi+1的邻接点*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的邻接点vj+l未曾访问过，则从vj+l出发进行深度优先搜索*/
} /*DFS*/
vexnode gl[n] /*邻接表全程量*/

DFSL(i) /*从vi+l出发深度优先搜索图g1，g1用邻接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/
p＝p - >next; /*找vi+l的下一个邻接点*/
}
} /* DFSL */

P142 以邻接矩阵和邻接表作为图的存储结构，分别给出宽度优先搜索算法。
BFS(k) /＊从vk+l出发宽度优先搜索图g，g用邻接矩阵表示，visited为访问标志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空队Q */
printf("％c＼n"，g.vexs[k]); /*访问出发点vk+l*x/
visited[k]＝TRUE; /*标记vk+l已访问过*/
ENQUEUE(Q，K); /*已访问过的顶点(序号)入队列*/
While(!EMPTY(Q)) /*队非空时执行*/
{i＝DEQUEUE(Q); /*队头元素序号出队列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*访问vi+l的未曾访问的邻接点vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*访问过的顶点入队*/
}
}
} /* BFS */
BFSL(k) /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/
}
p＝p - >next; /*找vi+l的下一个邻接点*/
}
}
} /*BFSL*/

P148 在对算法Prim求精之前，先确定有关的存储结构如下：
typdef struct
{Int fromvex，endvex; /*边的起点和终点*/
float length; /*边的权值*/
} edge;

float dist[n][n]; /*连通网络的带权邻接矩阵*/
edgeT[n-1]; /*生成树*/

P149 抽象语句(1)可求精为：
for(j=1;j<n;j++) /*对n-1个蓝点构造候选紫边集*/
{T[j-1].fromvex＝1}; /*紫边的起点为红点*/
T[j-1].endvex＝j+1; /*紫边的终点为蓝点*/
T[j-1].1ength＝dist[0][j]; /*紫边长度*/
}

P149 抽象语句(3)所求的第k条最短紫边可求精为：
min＝max; /*znax大于任何边上的权值*/
for (j＝k;j<n-1;j++) /*扫描当前候选紫边集T[k]到T[n-2]，找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*记录当前最短紫边的位置*/
}

P149 抽象语句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交换*/
v＝T[kl.Endvex]; /* v是刚被涂红色的顶点*/

P149 抽象语句(5)可求精为：
for(j＝k+1;j<n-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(d<T[j].1ength) /*新紫边的长度小于原最短紫边*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫边取代原最短紫边*/
}
}

P150 完整的算法：
PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*构造初始候选紫边集*/
{T[j-1].formvex＝1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k条边*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是当前最短紫边*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交换后，T[k]是第k条红色树边*/
v＝T[k].endvex ; /* v是新红点*/
for(j＝k+1;j<n-1;j++) /*调整候选紫边集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */

P151 Kruskl算法的粗略描述：
T＝(V,φ);
While(T中所含边数<n-1)
{从E中选取当前最短边(u,v);
从E中删去边(u,v);
if((u,v)并入T之后不产生回路，将边(u,v)并入T中;
}

P153 迪杰斯特拉算法实现。算法描述如下：
#define max 32767 /*max代表一个很大的数*/
void dijkstra (float cost[][n],int v)
/*求源点v到其余顶点的最短路径及其长度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/
pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/
}
} /*所有顶点均已加入到S集合中*/
for (j=0;j<n;j++) /*打印结果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}

P155 弗洛伊德算法可以描述为：
A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n

P155 弗洛伊德算法实现。算法描述如下：
int path[n][n]; /*路径矩阵*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*设置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]

❹ 罗马尼亚度假问题，不会啊，求代码

一、问题描述
（1）罗马尼亚问题：Find Bucharest starting at Arad
分别用宽度优先、深度优先、贪婪算法和A*算法求解“罗马利亚度假问题”。要求：分别用文件存储地图和启发函数表，用生成节点数比较几种算法在问题求解时的效率，列表给出结果。
（2）附（罗马尼亚地图）

（3）附各结点启发值：
366 241 0 234 160 380 242 100 161 193 176 253 77 329 151 80 226 199 244 374

二、数据结构
1、逻辑结构：用到线性结构包括数组、链表、栈；非线性结构：图。
2、存储结构（物理结构）：顺序存储结构和链式存储结构
(1)启发函数表采用顺序存储结构数组data[20].存储，从文件中读入： for (n=0;n<20;n++)
{
fscanf(fp1,"%d",&data[n]);
}
(2)图采用二维数组map[]存储，从文件中读入：
for (i=0;i<20;i++)
{
for(j=0;j<20;j++)
{
fscanf(fp2,"%d",&map[i][j]);

}
}
（3）宽度戚梁优先的fringe表采用链式存储结构存储，且每一个结点为一个包含结点序号、h、g、f值等的结构体；
（4）深度优先的fringe表采用顺序栈存储，且每一个结点为一个包含结点序号、h、g、f值等的结构体；
（5）贪婪算法和A*算法采用结构体数组存储。
3、数据的运算：
抽象数据类型
（1） 定义
typedef struct fringe
{

int state;//存储点序号信息 int g;//g值 int h;//h值 int f;//f值 int k;//标记是否已扩展
}FringeType;
（2） 运算：检索、插入、删除等运算
（3） 表示：
每一个数据元素就是一个记录。它包括学生的结点序号信息、g值、h值、f值等数据项，在解决实际应用问题时把每个记录当作一个基本单位进行访问和处理。

三、算法思想 1、宽度优先
（1）算法描述：
从Arad结点出发，判断是否为目标结点，若否，宽度优先搜索系统地探寻与该结点相连的结点，算法首先搜索和Arad距离为k的所有顶点，然后再去搜索和Arad距离为k+l的其他顶点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否则从待扩展结点表中取出一个结高旅运点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。该算法同时能生成一棵根为Arad且包括所有可达顶点的宽度优先树。
宽度优先算法一直通过已找镇闭到和未找到顶点之间的边界向外扩展。通过为每个顶点着色（白色、灰色和黑色）。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐被着色。在搜索中第一次碰到，着灰色，然后是灰色。因此，灰色和黑色顶点都已被发现，灰色顶点与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。
在宽度优先搜索中，我用到单链表来存储待扩展结点表。
（2）伪代码实现:
while(fringe[]!=NULL)
take out u∈fringe[]
do
color u;
while(u≠goal)
do
expand u;
BFS()
{
for (1-20循环)

put successors（BFS） in fringe[]; { } if (有路径存在) { } 新生成结点； BFSnode++; 取链表的第一个结点； if (为goal) { return BFSnode;} else if(不为goal) { } return BFSnode; } BFS（）；//递归调用
end;
end;
（3）算法评价：
宽度优先是完备的（如果分支因子有限的话），所以说，在任何情况下宽度优先都能找到一个解。此外，最坏的情况是，当目标结点是第d层的最后一个被扩展的结点时。
时间复杂度：
度）
空间复杂度：所存储的节点的个数。
2、深度优先
（1）算法描述：
深度优先搜索是一种每次都要达到被搜索结构的叶结点的搜索方法 ，直到不能再深入为止，然后返回到另一个结点，继续对该结点进行深搜。当有目标结点出现时，返回目标结点，搜索结束；否则，若待扩展结点表已空，且未找到目标结点，则返回失败，停止搜索。
同样，深度优先搜索从Arad结点出发，判断是否为目标结点，若否，探寻与该结点相连的结点，算法首先搜索一条分支上的所有顶点，然后再去搜索和Arad的其它分支结点，找出并存进待扩展结点表，等待扩展，每次先判断待扩展结点表是否为空，若否，则从待扩展结点表中取出一个结点进行扩展，并将扩展后的结点存进该表，若是，则返回失败。该算法同时能生成一棵根为Arad且包括所有可达顶点的深度优先树。
在深度优先搜索中，我用到堆栈来存储待扩展结点表。 （2）伪代码实现
while(fringe[]!=NULL)
take out u∈fringe[]
do
color u;
while(u≠goal)
do （b为分支因子，d为深 expand u;

{

for (1-20循环) { if (有路径存在) { } 新生成结点； DFSnode++; DFS() }

}
出堆栈； if (是目标结点) { { } return DFSnode; put successors（DFS） in fringe[]; DFS（）；//递归调用 return DFSnode; } else
end;
end;
（3）算法评价：

不是完备的（除非查找空间是有限的）。同时，也不能找到最优解。 时间复杂度：空间复杂度： （b为分支因子，m为深度，仅有一枝需要存储）
3、贪婪算法
（1）算法描述：
贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。贪婪算法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
在解决罗马尼亚度假问题时，贪婪算法通过比较每个待扩展结点的h值，即启发函数生成的到目标结点的启发函数值，选取一个最小的，来确定当前要扩展的结点，并将生成的结点放进fringe结点表。
在贪婪算法中，我用到结构体数组存储待扩展结点表。
（2）伪代码实现：
while(fringe[]!=NULL)
take out u∈fringe[]
do
color u;
while(u≠goal)
do
expand u;
三亿文库3y.uu456.com包含各类专业文献、各类资格考试、幼儿教育、小学教育、生活休闲娱乐、文学作品欣赏、外语学习资料、中学教育、专业论文、高等教育、行业资料、n皇后问题和罗马尼亚问题实习报告26等内容。

❺ C语言运算符优先级口诀

C语言运算符及其优先级汇总表口诀 圆下箭头一顿号 非凡增减富强针地长 三乘除，四加减，五移位 千万别把鱼忘记，它在盛饭的厨子里 小灯大灯灯灯不等 爸喂鱼，舅疑惑，裸鸡也疑惑 十三姨，十四父，十五逗，兜到低 “圆下箭头一顿号”指的是第15级的运算符。其中圆指的是运算符（），下指的是下标运算符[]，箭头指的是指向结构体成员运算符->，顿号指的是结构体成员运算符、 “非凡增减富强针地长”指的是第14级的运算符。其中非指的是逻辑运算符!，凡指的是按位取反运算符~，增减指的是自增和自减运算符++和--，富指的是负号运算符-，强指的是类型转换运算符（类型），针指的是指针运算符*，地指的是地址运算符&，长指的是长度运算符Sizeof “三乘除，四加减，五移位” 指的是第13级到第11级的运算符。其中三四五并无实际意义，只是起区分级别而已。也可以想象三指的是第13级运算符。乘除指的是乘法运算符*和除法运算符/，加减指的是加法运算符+和减法运算符-，移位指的是铅渗左移运算符<<和右移运算符>> “千万别把鱼忘记，它在盛饭的厨子里”指的是求余运算符%，它位于盛饭的厨子里，即指和乘巧激并法运算符、除法运算符在一起。 “小灯大灯灯灯不等” 指的是第10级到第9级的运算符。其中小灯大灯指的是关系运算符<、<=、>和>=，灯灯指的是等于运算符==，不等指的是不等于运算符!= “爸喂孝迹鱼，舅疑惑，裸鸡也疑惑”指的是第8级到第4级的运算符。其中，爸喂鱼之指的是第8级的按位与运算符&，舅疑惑指的是第7级的按位异或运算符^和第6级的按位或运算符||，裸鸡也疑惑指的是第5级、第4级的逻辑与运算符&&和逻辑或运算符|| “十三姨，十四父，十五逗，兜到低”指的是第3级到第1级的运算符。其中，十三姨指的是条件运算符?: （三有双重含义，即指?:的优先级别是三，它的运算符类型也是三目，？难道不是姨即疑惑吗?），十四父的十四没有实际意义，父指的是赋值运算符=、+=、-=、*=、/=、%=、>>=、<<=、&=、^=和|= ，十五逗指的是第1级的运算符，兜到低指的是15级运算符以，结束。

❻ 短作业优先算法用c语言如何写

这样写应该可以：
#include<iostream.h>

#include<stdio.h>
struct pcb{
char pno;
int come_time; //到达时间
int run_time; //服务时间
};
float fcfs(pcb pro[],int n)
{
struct pcb temp;
int i,j,k; //time为当前时间
float weight_time=0,time=0; //记录周转时间的和
//temp=(pcb)malloc(sizeof(pcb));
cout<<"进程调度情况如下:"<<endl;
cout<<"进程号 到达时间 服务时间 周转时间:"<<endl;
//选择排序过程,按到达时间升序排列
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
if(pro[k].come_time>pro[j].come_time)
k=j;
if(k!=i)
{
temp=pro[i];
pro[i]=pro[k];
pro[k]=temp;
}
}
for(i=0;i<n;i++)
{ time+=pro[i].run_time;
weight_time+=(time-pro[i].come_time)/pro[i].run_time; //(time-pro[i].come_time)/pro[i].run_time为排序后第i个进程的周转时间
cout<<pro[i].pno<<" "<<pro[i].come_time<<" "<<pro[i].run_time<<" "<<(time-pro[i].come_time)/pro[i].run_time<<endl;
}
return weight_time/=n; //返回平均带权周转时间
}
void insert(pcb pro[],pcb pro1,int start,int end)//将一pcb类型的元素插入到有序数组中，最后还保持有序
{
int i=end;
while((i--)>start)
if(pro[i].run_time>pro1.run_time)pro[i+1]=pro[i];
pro[i]=pro1;

}
float sjp(pcb pro[],int n)
{
int i,first=0,count,flag[20],k,min;
float time=0,weight_time=0;
//调度第一个到达内存的进程
for(i=1;i<n;i++)
{
if(pro[first].come_time>pro[i].come_time) first=i;
flag[i]=0;
}
flag[first]=1;
time=(float)pro[first].run_time;
weight_time=1;
cout<<pro[first].pno<<" "<<pro[first].come_time<<" "<<pro[first].run_time<<" "<<weight_time<<endl;
//pro_temp[0]=pro[first];
count=n-1;
while(count)
{
k=0;
min=32767; //设置一个较大的阈值，
for(i=0;i<n;i++) //找到一个未被访问的，作业较短的且已经到达内存的作业调度
if((i!=first)&&(flag[i]==0)&&(time>=pro[i].come_time)&&(min>pro[i].run_time))
{
k=i;
min=pro[i].run_time;

}
flag[k]=1; //访问后置标记为访问
time+=pro[k].run_time;
weight_time+=(time-pro[k].come_time)/pro[k].run_time;
cout<<pro[k].pno<<" "<<pro[k].come_time<<" "<<pro[k].run_time<<" "<<(time-pro[k].come_time)/pro[k].run_time<<endl;
count--; //每调度一个作业，count减1
}
return weight_time/=n;
}

void main()
{
pcb pro[5]={{'C',2,5},{'A',0,4},{'B',1,3},{'D',3,2},{'E',4,4}};
cout<<fcfs(pro,5)<<endl;
cout<<sjp(pro,5)<<endl;
}

❼ 7.3实现宽度优先搜索

在单词关系图建立完成以后，需要继续在图中寻找词梯问题的最短序列，需要用到“宽度优先搜索Breadth First Search”算法对单词关系图进行搜索
BFS是搜索图的最简单算法之一，也是其它一些重要的图算法的基础给定图G，以及开始搜索的起始顶点s。BFS搜索所有从s可到达顶点的边而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为耐核慎k的顶点可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次宽度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中。
BFS算法过程
❖为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加3个属性
1.距离distance：从起始顶点到此顶点路径长度；
2.前驱顶点predecessor：可反向追溯到起点；
3.颜色color：标识了此顶点是尚未发现（白色）、已经发现（灰昌敬色）、还是已经完成探索（黑色）
❖还需要用一个队列Queue来对已发现的顶点进行排列
决定下一个要探索的顶点（队首顶点）
❖从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None，加入队列，接下来是个循环迭代过程：
从队首取出一个顶点作为当前顶点；遍历当前顶点的邻接顶点，如果是尚未发现的白
色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点

算法分析
BFS算法主体是两个循环的嵌套
while循环对每个顶点访问一次，所以是O(|V|)，而嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，而每个顶点最多出队1次，所以边最多被检查1次，一共是O(|E|)综合起来BFS的时间复杂度为O(V+E)
词梯问题还包括两个部分算法
建立BFS树之后，回溯氏橘顶点到起始顶点的过程，最多为O(|V|)，创建单词关系图也需要时间，最多为O(|V|2)

❽ c语言广度优先算法

既然b[i]记录的是前纯弊驱城市。做旅族
那也就是通过i的前一个城市存在b[i]中，能保证从A到H是镇敏最短的。

❾ 宽度优先搜索算法(pascal)

宽度优先搜索（BFS，BreadthFirstSearch）是一种搜索算法，其主要用来解决最优解问题。原型是图的宽度优先遍历问题，即从源顶点s出发，遍历每一个节点，它的基本思路是：先扩展当前节点所有邻接的节点，然后再从这些顶点出发，遍历所有顶点，即分层处理，将遍历路径表示成树，就是按层次遍历。

宽度优先搜索实现要依赖队列，即先进先出表（FIFO），这样保证了搜索的顺序正确。下面以图的遍历为例，写出标准算法（伪代码）

BFS(G,s)

foreachvertexuexceptsdo//对除源顶点外的所有节点进行初始化

begin

visited[u]:=false;//是否访问过

distance[u]:=infinite;//距源顶点距离

parent[u]:=NIL;//父节点

end;

visited[s]:=true;//对源顶点进行初始化

distance[s]:=0;

parent[s]:=NIL;

ENQUEUE(Q,s);//入队；Q为队列

whilenot(empty(Q))do //队列不空

begin

u:=DEQUEUE(Q);//队首元素出队

foreachvertexVbelongstoAdj[u]do//扩展每个邻接节点

ifvisited[v]=falsethen//如果未访问

begin

visited[v]:=true;//标记已访问

distance[v]:=distance[u]+1;//距离更新

parent[v]:=u;//父节点记录

ENQUEUE(Q,v);//入队

end;

end;

实际运用时要注意在达到结果后就要加一个break退出并输出。为什么宽度优先搜索能解决最优问题呢？因为根据宽搜的策略，被搜索到的顶点被戳上的distance标记就是到源顶点的最短路径的距离，因此可以解决无权图的最短路径问题以及由其抽象而来的最优问题。

题目要求并不一样，有的要求最优解大小，就可以直接输出distance；有的要输出最优解路径、方法，可以用循环将parent层层取出，入栈调整顺序输出，这也算一个技巧。

也许你还看不懂算法，可以找本算法导论好好读读，上面的图示对于理解很有帮助。

PS：敲完之后看了看网络，发现上面的内容完全改成了算法导论，可以去看看。尤其图示，很有帮助的。