❶ c#)圖的深度優先搜索和廣度優先搜索演算法的實現
#include "exam8-2.cpp"
void BFS(ALGraph *G,int v)
{
ArcNode *p;
int queue[MAXV],front=0,rear=0; //定義循環隊列並初始化
int visited[MAXV]; //定義存放結點的訪問標志的數組
int w,i;
for (i=0;i<G->n;i++) visited[i]=0; //訪問標志數組初始化
printf("%2d",v); //輸出被訪問頂點的編號
visited[v]=1; //置已訪問標記
rear=(rear+1)%MAXV;
queue[rear]=v; //v進隊
while (front!=rear) //若隊列不空時循環
{ front=(front+1)%MAXV;
w=queue[front]; //出隊並賦給w
p=G->adjlist[w].firstarc; //找與頂點w鄰接的第一個頂點
while (p!=NULL)
{ if (visited[p->adjvex]==0) //若當前鄰接頂點未被訪問
{ printf("%2d",p->adjvex); //訪問相鄰頂點
visited[p->adjvex]=1; //置該頂點已被訪問的標志
rear=(rear+1)%MAXV; //該頂點進隊
queue[rear]=p->adjvex;
}
p=p->nextarc; //找下一個鄰接頂點
}
}
printf("\n");
}
void main()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAXV][5]={
{0,1,0,1,1},
{1,0,1,1,0},
{0,1,0,1,1},
{1,1,1,0,1},
{1,0,1,1,0}};
g.n=5;g.e=16;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
G=(ALGraph *)malloc(sizeof(ALGraph));
MatToList(g,G);
printf(" 鄰接表:\n");DispAdj(G);
printf("廣度優先序列:");BFS(G,2);printf("\n");
}
以上為廣度優先搜索遍歷
#include "exam8-2.cpp"
int visited[MAXV];
void DFS(ALGraph *G,int v)
{
ArcNode *p;
visited[v]=1; //置已訪問標記
printf("%d ",v); //輸出被訪問頂點的編號
p=G->adjlist[v].firstarc; //p指向頂點v的第一條弧的弧頭結點
while (p!=NULL)
{
if (visited[p->adjvex]==0) //若p->adjvex頂點未訪問,遞歸訪問它
DFS(G,p->adjvex);
p=p->nextarc; //p指向頂點v的下一條弧的弧頭結點
}
}
void main()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAXV][5]={
{0,1,0,1,1},
{1,0,1,1,0},
{0,1,0,1,1},
{1,1,1,0,1},
{1,0,1,1,0}};
g.n=5;g.e=16;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
G=(ALGraph *)malloc(sizeof(ALGraph));
MatToList(g,G);
printf(" 鄰接表:\n");DispAdj(G);
for (i=0;i<MAXV;i++)
visited[i]=0;
printf("深度優先序列:");DFS(G,2);printf("\n");
}
這是深度優先搜索遍歷。
具體還需自己懂後創新
❷ 優先順序調度演算法如何用JAVA實現
在多線程時,可以手動去設置每個線程的優先順序setPriority(int newPriority)
更改線程的優先順序。
❸ 求廣度優先演算法C++走迷宮程序,可以顯示路徑
一般迷宮尋路可以用遞歸的演算法,或者用先進後出的棧數據結構實現
用的是深度優先的演算法,可以尋找到走出迷宮的路徑
但本題要求求出最短的路徑,這就要使用廣度優先的演算法
一般在程序中需要用到先進先出的隊列數據結構
下面是程序的代碼,主要原理是用到
quei,quej和prep三個數組來構成隊列
分別儲存路徑的行,列坐標和上一個節點在隊列中的位置
大致演算法如下,右三個嵌套的循環實現
首先是第一個節點進入隊列
當隊列不空(循環1)
{
遍歷隊列中每節點(循環2)
{
將八個方向能夠走的節點加入隊列(循環3)
}
舊的節點出列
}
#include<iostream>
#include<ctime>
usingnamespacestd;
#defineMAXNUM50
voidmain()
{
intm,n,i,j,x;
cout<<"請輸入迷宮大小"<<endl;
cin>>m>>n;
intmaze[MAXNUM][MAXNUM];
srand((int)time(NULL));
for(i=0;i<=m+1;i++){
for(j=0;j<=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x>700){maze[i][j]=1;}//控制矩陣中1的個數,太多1迷宮很容易走不通
else{maze[i][j]=0;}
}
cout<<maze[i][j]<<'';
}
cout<<endl;
}
//以上是輸入和迷宮生成,一下是走迷宮
intmove[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int*quei=newint[m*n];//儲存行坐標隊列
int*quej=newint[m*n];//儲存列坐標隊列
int*prep=newint[m*n];//儲存之前一步在隊列中的位置
inthead,rear,length;//隊列頭,隊列尾,隊列長度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置進隊列
intpos;//當前節點在隊列中的位置,
intii,jj,ni,nj;//當前節點的坐標,新節點的坐標
intdir;//移動方向
if(maze[1][1]==1)length=0;//第一點就不能通過
elsemaze[1][1]=1;
while(length)//隊列非空繼續
{
for(pos=head;pos<head+length;pos++)//尋找這一層所有節點
{
ii=quei[pos];jj=quej[pos];//當前位置坐標
if(ii==m&&jj==n)break;
for(dir=0;dir<8;dir++)//尋找8個方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐標
if(maze[ni][nj]==0)//如果沒有走過
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新節點入隊
rear=rear+1;
maze[ni][nj]=1;//標記已經走過
}
}
}
if(ii==m&&jj==n)break;
head=head+length;
length=rear-head;//這一層節點出列
}
if(ii==m&&jj==n)
{
while(pos!=-1)
{
cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
pos=prep[pos];
if(pos!=-1)cout<<',';
}
}
else
{
cout<<"THEREISNOPATH."<<endl;
}
delete[]quei;
delete[]quej;
delete[]prep;
}
❹ css優先順序計算規則
梳理這部分是因為在使用組件模式開發h5應用會出現組件樣式修改未生效的問題,在解決樣式修改的問題前,需要理清楚CSS樣式生效的優先順序。樣式根據引入和聲明需要分開介紹,分為 引入樣式優先順序 和 聲明樣式優先順序 。
引入樣式優先順序
引入樣式優先順序一般是在外部樣式、內部樣式、內聯樣式之間應用同一個樣式的情況是使用, 優先順序如下:
外部樣式 | 內部樣式 < 內聯樣式
外部樣式 和 內部樣式 ,最後出現的優先順序最高,例如:
<!-- 內聯樣式 --><spanstyle="color:red;">Hello</span><styletype="text/css">/* 內部樣式 */h3{color:green;}</style><!-- 外部樣式 style.css --><linkrel="stylesheet"type="text/css"href="style.css"/>
因此,對於一些重置的樣式集,比如 normalize.css/reset.css 必須寫在所有樣式的前面。
PS: 沒有外聯樣式, 參考 。
聲明樣式優先順序
1. 大致的優先順序
一般來說滿這個規則:
繼承不如指定
!important > 內聯 > ID > Class|屬性|偽類 > 元素選擇器
:link、:visited、:hover、:active按照LVHA(LoVe HAte)順序定義
上面是優先順序演算法反映出的大致結果,在一般的開發中熟記即可。如果需要進一步研究原理,則了解下優先順序演算法。
2. 優先順序演算法
選擇器的特殊性值分為四個等級,如下:
等級標簽內選擇符ID選擇符Class選擇符/屬性選擇符/偽類選擇符元素選擇符
示例<span style="color:red;">#text{color:red;}.text{color:red;} [type="text"]{color:red}span{color:red;}
標記位x,0,0,00,x,0,00,0,x,00,0,0,x
特點:
每個等級的初始值為0,
每個等級的疊加為選擇器出 現的次數相加
不可進位,比如0,99,99,99
依次表示為:0,0,0,0
每個等級計數之間沒關聯
等級判斷從左向右,如果某一位數值相同,則判斷下一位數值
如果兩個優先順序相同,則最後出現的優先順序高,!important也適用
通配符選擇器的特殊性值為:0,0,0,0
繼承樣式優先順序最低 ,通配符樣式優先順序高於繼承樣式
計算示例:
a{color: yellow;} /*特殊性值:0,0,0,1*/
div a{color: green;} /*特殊性值:0,0,0,2*/
.demo a{color: black;} /*特殊性值:0,0,1,1*/
.demo input[type="text"]{color: blue;} /*特殊性值:0,0,2,1*/
.demo *[type="text"]{color: grey;} /*特殊性值:0,0,2,0*/
#demo a{color: orange;} /*特殊性值:0,1,0,1*/
div#demo a{color: red;} /*特殊性值:0,1,0,2*/
生效示例:
<ahref="">第一條應該是黃色</a><!--適用第1行規則--><divclass="demo"><inputtype="text"value="第二條應該是藍色"/><!--適用第4、5行規則,第4行優先順序高--><ahref="">第三條應該是黑色</a><!--適用第2、3行規則,第3行優先順序高--></div><divid="demo"><ahref="">第四條應該是紅色</a><!--適用第6、7行規則,第7行優先順序高--></div>
關於偽類LVHA的解釋
a標簽有四種狀態:鏈接訪問前、鏈接訪問後、滑鼠滑過、激活,分別對應四種偽類:link、:visited、:hover、:active;
當滑鼠滑過a鏈接時,滿足:link和:hover兩個偽類,要改變a標簽的顏色,就必須將:hover偽類在:link偽類後面聲明;
當滑鼠點擊激活a鏈接時,同時滿足:link、:hover、:active三種狀態,要顯示a標簽激活時的樣式(:active),必須將:active聲明放到:link和:hover之後。因此得出LVHA這個順序。
這個順序能不能變?可以,但也只有:link和:visited可以交換位置,因為一個鏈接要麼訪問過要麼沒訪問過,不可能同時滿足,也就不存在覆蓋的問題。
在組件中的應用
目前的前端開發為了增加開發效率,會對常用組件進行封裝,此外,組件還會添加一些必要的結構樣式。但是業務的設計文稿中可不一定按照預先寫好的默認樣式,需要在開發業務時根據組件的DOM結構修改默認樣式,此時會出現樣式不生效的問題。
例如下面的結構,如果對Title直接增加樣式類,則肯定不會生效,因為Title的DOM結構為兩層(組件樣式定義規定不能使用ID選擇器,且類選擇器滿足最小標記原則)),故樣式最多為0,0,2,x。因此,樣式多層標記就可提高自定義樣式的優先順序,例如下方的SCSS寫法。
<Pageclass="test"><Headerclass="test__header"><Navbar><Titleclass="test__header--title">Toolbar</Title></Navbar></Header><Content></Content></Page>
.test{.test__header{.test__header--title{height:100px;}}}
此外,對於Page組件的樣式標記策略推薦使用 金字塔形(樹形) ,比如上面的SCSS書寫,這樣可以保證內部自定義樣式不會受到外部干擾,減少不必要的麻煩。
鏈接:https://www.jianshu.com/p/1c4e639ff7d5
❺ 動態優先順序調度演算法
給你兩個例子,第一個:http://dev.csdn.net/article/53/53415.shtm
第二個:
#include "stdio.h"
#include <STDLIB.H>
#include <CONIO.H>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0
struct pcb { /* 定義進程式控制制塊PCB */
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
sort() /* 建立對進程進行優先順序排列函數*/
{
PCB *first, *second;
int insert=0;
if((ready==NULL)||((p->super)>(ready->super))) /*優先順序最大者,插入隊首*/
{
p->link=ready;
ready=p;
}
else /* 進程比較優先順序,插入適當的位置中*/
{
first=ready;
second=first->link;
while(second!=NULL)
{
if((p->super)>(second->super)) /*若插入進程比當前進程優先數大,*/
{ /*插入到當前進程前面*/
p->link=second;
first->link=p;
second=NULL;
insert=1;
}
else /* 插入進程優先數最低,則插入到隊尾*/
{
first=first->link;
second=second->link;
}
}
if(insert==0) first->link=p;
}
}
input() /* 建立進程式控制制塊函數*/
{
int i,num;
//clrscr(); /*清屏*/
printf("\n 請輸入進程號?");
scanf("%d",&num);
for(i=0;i<NUM;I++) scanf(?%s?,p- 輸入進程名:?); printf(?\n p="getpch(PCB);" 進程號No.%d:\n?,i); {>name);
printf("\n 輸入進程優先數:");
scanf("%d",&p->super);
printf("\n 輸入進程運行時間:");
scanf("%d",&p->ntime);
printf("\n");
p->rtime=0;p->state='w';
p->link=NULL;
sort(); /* 調用sort函數*/
}
}
int space()
{
int l=0; PCB* pr=ready;
while(pr!=NULL)
{
l++;
pr=pr->link;
}
return(l);
}
disp(PCB * pr) /*建立進程顯示函數,用於顯示當前進程*/
{
printf("\n qname \t state \t super \t ndtime \t runtime \n");
printf("|%s\t",pr->name);
printf("|%c\t",pr->state);
printf("|%d\t",pr->super);
printf("|%d\t",pr->ntime);
printf("|%d\t",pr->rtime);
printf("\n");
}
check() /* 建立進程查看函數 */
{
PCB* pr;
printf("\n **** 當前正在運行的進程是:%s",p->name); /*顯示當前運行進程*/
disp(p);
pr=ready;
printf("\n ****當前就緒隊列狀態為:\n"); /*顯示就緒隊列狀態*/
while(pr!=NULL)
{
disp(pr);
pr=pr->link;
}
}
destroy() /*建立進程撤消函數(進程運行結束,撤消進程)*/
{
printf("\n 進程 [%s] 已完成.\n",p->name);
free(p);
}
running() /* 建立進程就緒函數(進程運行時間到,置就緒狀態*/
{
(p->rtime)++;
if(p->rtime==p->ntime)
destroy(); /* 調用destroy函數*/
else
{
(p->super)--;
p->state='w';
sort(); /*調用sort函數*/
}
}
main() /*主函數*/
{
int len, h=0;
char ch;
input();
len=space();
while((len!=0)&&(ready!=NULL))
{
ch=getchar();
h++;
printf("\n The execute number:%d \n",h);
p=ready;
ready=p->link;
p->link=NULL;
p->state='R';
check();
running();
printf("\n 按任一鍵繼續......");
ch=getchar();
}
printf("\n\n 進程已經完成.\n");
ch=getchar();
}
❻ 動態高優先權優先調度演算法
動態高優先權優先調度演算法:
動態優先權是指,在創建進程時所賦予的優先權,是可以隨進程的推進或隨其等待時間的增加而改變的,以便獲得更好的調度性能。例如,我們可以規定,在就緒隊列中的進程,隨其等待時間的增長,其優先權以速率a提高。若所有的進程都具有相同的優先權初值,則顯然是最先進入就緒隊列的進程,將因其動態優先權變得最高而優先獲得處理機,此即FCFS演算法。若所有的就緒進程具有各不相同的優先權初值,那麼,對於優先權初值低的進程,在等待了足夠的時間後,其優先權便可能升為最高,從而可以獲得處理機。當採用搶占式優先權調度演算法時,如果再規定當前進程的優先權以速率b下降,則可防止一個長作業長期地壟斷處理機。
演算法代碼模擬實現:
#include<stdio.h>
#include<stdlib.h>
#defineN6
//待插入就緒隊列的進程數據
intid[N]={0,1,
2,3,4,
5};
intpriority[N]={9,38,17,
2,7,18};
intcpuTime[N]={0,
0,0,0,
0,0};
intallTime[N]={3,
2,3,6,
1,3};
//********************************
//
//模擬進程/PCB數據結構
//
//********************************
//
枚舉進程的狀態:就緒、執行、阻塞、完成
enumSTATE{Ready,Run,Block,Finish
};
//建立PCB結構體
structPCB{
intid;//標志數
intpriority;//優先數
intcpuTime;//
已佔CPU時間
intallTime;//
還需佔CPU時間
intblockTime;//已被阻塞的時間
STATEstate;//
進程狀態
PCB*pre;//
PCB的前指針
PCB*nxt;//
PCB的後指針
};
//********************************
//
//模擬進程隊列
//
//********************************
//進程入列
voidqueQush(PCB*process,PCB
*queHead)
{
process->pre=NULL;
process->nxt=
queHead->nxt;
if(queHead->nxt!=NULL){
//非第一個入列
queHead->nxt->pre=
process;
}
queHead->nxt=process;
}
//進程出列
voidquePop(PCB*process,PCB
*queHead)
{
if(process->pre!=NULL){
//不是頭節點
process->pre->nxt=
process->nxt;
}
else{
queHead->nxt=
process->nxt;
}
if(process->nxt!=NULL){
//不是尾節點
process->nxt->pre=
process->pre;
}
//
清空進程指針
process->pre=process->nxt=
NULL;
}
//查看隊列里進程的信息
voidqueWalk(PCB*queHead)
{
PCB*pro=queHead->nxt;
if(pro==NULL){
printf("(無進程) ");
return;
}
while(pro!=NULL)
{
printf("id:%d,
pri:%d,alltime:%d ",
pro->id,
pro->priority,
pro->allTime);
pro=
pro->nxt;
}
}
//********************************
//
//模擬就緒隊列
//
//********************************
intreadyQueNum;//就緒隊列的進程數量
PCBreadyQueHead;//
就緒隊列的頭部
PCB*readyMaxProcess;//就緒隊列中優先順序最高的進程
//進程插入到就緒隊列
voidreadyQueQush(PCB
*process)
{
readyQueNum++;
process->state=Ready;
queQush(process,&readyQueHead);
}
//優先順序最高的進程出列
PCB*readyQuePop()
{
readyQueNum--;
quePop(readyMaxProcess,
&readyQueHead);
returnreadyMaxProcess;
}
//每個時間片,更新就緒隊列里進程的信息
voidreadyQueUpdate()
{
intmaxPriority=-1;
PCB*pro=readyQueHead.nxt;
if(pro==NULL){
//就緒隊列沒有進程
readyMaxProcess=
NULL;
return;
}
while(pro!=NULL)
{
pro->priority
++;
if(pro->priority>maxPriority)
{
maxPriority=
pro->priority;
readyMaxProcess=pro;
}
pro=
pro->nxt;
}
}
//返回就緒隊列最高優先順序的值
intreadyMaxPriority()
{
returnreadyMaxProcess->priority;
}
//查看就緒隊列里進程的信息
voidreadyQueWalk()
{
printf("就緒隊列里的進程信息為: ");
queWalk(&readyQueHead);
}
//********************************
//
//模擬阻塞隊列
//
//********************************
#defineEndBlockTime3
//進程最長被阻塞時間
intblockQueNum;//阻塞隊列的進程數量
PCBblockQueHead;//
阻塞隊列的頭部
PCB*blockMaxProcess;//阻塞隊列中優先順序最高的進程
//進程插入到阻塞隊列
voidblockQueQush(PCB
*process)
{
blockQueNum++;
process->blockTime=0;
process->state=Block;
queQush(process,&blockQueHead);
}
//優先順序最高的進程出列
PCB*blockQuePop()
{
blockQueNum--;
quePop(blockMaxProcess,
&blockQueHead);
returnblockMaxProcess;
}
//每個時間片,更新阻塞隊列里進程的信息
voidblockQueUpdate()
{
intmaxPriority=-1;
PCB*pro=blockQueHead.nxt;
while(pro!=NULL)
{
pro->blockTime
++;
if(pro->blockTime>=EndBlockTime)
{
PCB*process=pro;
pro=pro->nxt;
//阻塞時間到,調入就緒隊列
blockQueNum--;
quePop(process,
&blockQueHead);
readyQueQush(process);
}else
if(pro->priority>maxPriority)
{
//更新阻塞隊列里優先順序最高的進程指針
maxPriority=
pro->priority;
blockMaxProcess=pro;
pro=pro->nxt;
}
}
}
//查看阻塞隊列里進程的信息
voidblockQueWalk()
{
printf("阻塞隊列里的進程信息為: ");
queWalk(&blockQueHead);
}
//********************************
//
//模擬動態優先權的進程調度
//
//********************************
//初始化數據
voidinitData()
{
//
初始化就緒隊列和阻塞隊列
readyQueNum=blockQueNum=0;
readyMaxProcess=blockMaxProcess=NULL;
readyQueHead.pre=readyQueHead.nxt=NULL;
blockQueHead.pre=blockQueHead.nxt=NULL;
//
初始化進程進入就緒隊列
inti,maxPriority=-1;
for(i=0;i<N;i
++)
{
//分配一個PCB的內存空間
PCB*pro=(PCB
*)malloc(sizeof(PCB));
//給當前的PCB賦值
pro->id
=id[i];
pro->priority
=priority[i];
pro->cpuTime
=cpuTime[i];
pro->allTime
=allTime[i];
pro->blockTime
=0;
if(pro->allTime>0){
//插入到就緒隊列中
readyQueQush(pro);
//更新就緒隊列優先順序最高的進程指針
if(pro->priority>
maxPriority){
maxPriority=pro->priority;
readyMaxProcess=pro;
}
}
}
}
//模擬cpu執行1個時間片的操作
voidcpuWord(PCB
*cpuProcess)
{
cpuProcess->priority-=3;
if(cpuProcess->priority<0)
{
cpuProcess->priority=0;
}
cpuProcess->cpuTime++;
cpuProcess->allTime--;
//
顯示正執行進程的信息:
printf("CPU正執行的進程信息為: ");
printf("id:M,pri:M,
alltime:M ",
cpuProcess->id,
cpuProcess->priority,
cpuProcess->allTime);
}
intmain()
{
inttimeSlice=0;//
模擬時間片
intcpuBusy=0;
//模擬cpu狀態
PCB*cpuProcess=NULL;//當前在cpu執行的進程
//
初始化數據
initData();
//
模擬進程調度
while(1)
{
if(readyQueNum==0
&&blockQueNum==0
&&cpuBusy==0){
//就緒隊列、阻塞隊列和cpu無進程,退出
break;
}
//printf(" %d%d",
readyQueNum,blockQueNum);
if(cpuBusy==0)
{
//cpu空閑,選擇一個進程進入cpu
if(readyQueNum>0)
{
//
選擇緒隊列優先順序最高的進程
cpuProcess
=readyQuePop();
}else{
//
就緒隊列沒有進程,改為選擇阻塞隊列優先順序最高的進程
cpuProcess
=blockQuePop();
}
cpuProcess->cpuTime=
0;
cpuProcess->state=
Run;
cpuBusy=1;
}
timeSlice++;
printf(" 第%d個時間片後: ",
timeSlice);
//
模擬cpu執行1個時間片的操作
cpuWord(cpuProcess);
if(cpuProcess->allTime==0){
cpuProcess->state=
Finish;
//釋放已完成進程的PCB
free(cpuProcess);
cpuBusy=0;
}
//
更新就緒隊列和阻塞隊列里的進程信息
blockQueUpdate();
readyQueUpdate();
//
查看就緒隊列和阻塞隊列的進程信息
readyQueWalk();
blockQueWalk();
if(cpuBusy==1
&&readyQueNum>0
&&
cpuProcess->priority
<readyMaxPriority()){
//需搶佔cpu,當前執行的進程調入阻塞隊列
blockQueQush(cpuProcess);
cpuProcess=readyQuePop();
}
}
printf(" 模擬進程調度演算法結束 ");
return0;
}