queuetoarray-50

linux内核怎么调度系统

import java.util.ArrayList;。

public class Test40023{。

public static void main(String args[]){。

ArrayList<Integer> a = new ArrayList<Integer>();。

a.add(1);

a.add(2);

for(int i =0;i < a.size();i++){。

System.out.println(a.toArray()[i]);。

}

}

运行结果：

——-------------------。

toArray()方法是指将ArrayList转换为数组，如上述例子所示。

优先队列实现dijkstra算法C++代码

1.调度器的概述

多任务操作系统分为非抢占式多任务和抢占式多任务。与大多数现代操作系统一样，Linux采用的是抢占式多任务模式。这表示对CPU的占用时间由操作系统决定的，具体为操作系统中的调度器。调度器决定了什么时候停止一个进程以便让其他进程有机会运行，同时挑选出一个其他的进程开始运行。

2.调度策略

在Linux上调度策略决定了调度器是如何选择一个新进程的时间。调度策略与进程的类型有关，内核现有的调度策略如下：

#define SCHED_NORMAL        0#define SCHED_FIFO      1#define SCHED_RR        2#define SCHED_BATCH     3/* SCHED_ISO: reserved but not implemented yet */#define SCHED_IDLE      5。

0: 默认的调度策略，针对的是普通进程。

1：针对实时进程的先进先出调度。适合对时间性要求比较高但每次运行时间比较短的进程。

2：针对的是实时进程的时间片轮转调度。适合每次运行时间比较长得进程。

3：针对批处理进程的调度，适合那些非交互性且对cpu使用密集的进程。

SCHED_ISO：是内核的一个预留字段，目前还没有使用。

5：适用于优先级较低的后台进程。

注：每个进程的调度策略保存在进程描述符task_struct中的policy字段。

3.调度器中的机制

内核引入调度类（struct sched_class）说明了调度器应该具有哪些功能。内核中每种调度策略都有该调度类的一个实例。（比如：基于公平调度类为：fair_sched_class，基于实时进程的调度类实例为：rt_sched_class），该实例也是针对每种调度策略的具体实现。调度类封装了不同调度策略的具体实现，屏蔽了各种调度策略的细节实现。

调度器核心函数schedule()只需要调用调度类中的接口，完成进程的调度，完全不需要考虑调度策略的具体实现。调度类连接了调度函数和具体的调度策略。

武特师兄关于sche_class和sche_entity的解释，一语中的。

调度类就是代表的各种调度策略，调度实体就是调度单位，这个实体通常是一个进程，但是自从引入了cgroup后，这个调度实体可能就不是一个进程了，而是一个组。

4.schedule()函数

linux 支持两种类型的进程调度，实时进程和普通进程。实时进程采用SCHED_FIFO 和SCHED_RR调度策略，普通进程采用SCHED_NORMAL策略。

preempt_disable()：禁止内核抢占。

cpu_rq（）：获取当前cpu对应的就绪队列。

prev = rq->curr;获取当前进程的描述符prev。

switch_count = &prev->nivcsw;获取当前进程的切换次数。

update_rq_clock() ：更新就绪队列上的时钟。

clear_tsk_need_resched()清楚当前进程prev的重新调度标志。

deactive_task():将当前进程从就绪队列中删除。

put_prev_task() :将当前进程重新放入就绪队列。

pick_next_task():在就绪队列中挑选下一个将被执行的进程。

context_switch():进行prev和next两个进程的切换。具体的切换代码与体系架构有关，在switch_to()中通过一段汇编代码实现。

post_schedule():进行进程切换后的后期处理工作。

5.pick_next_task函数。

选择下一个将要被执行的进程无疑是一个很重要的过程，我们来看一下内核中代码的实现。

对以下这段代码说明：

1.当rq中的运行队列的个数(nr_running)和cfs中的nr_runing相等的时候，表示现在所有的都是普通进程，这时候就会调用cfs算法中的pick_next_task(其实是pick_next_task_fair函数)，当不相等的时候，则调用sched_class_highest(这是一个宏，指向的是实时进程)，这下面的这个for(;;)循环中，首先是会在实时进程中选取要调度的程序（p = class->pick_next_task(rq);）。如果没有选取到，会执行class=class->next;在class这个链表中有三种类型（fair,idle,rt）.也就是说会调用到下一个调度类。

static inline struct task_struct *pick_next_task(struct rq *rq){    const struct sched_class *class;    struct task_struct *p;    /*。

    * Optimization: we know that if all tasks are in。

    * the fair class we can call that function directly:。

    *///基于公平调度的普通进程。

   if (likely(rq->nr_running == rq->cfs.nr_running)) {。

       p = fair_sched_class.pick_next_task(rq);        if (likely(p))            return p;。

   }//基于实时调度的实时进程。

   class = sched_class_highest;    for ( ; ; ) {。

       p = class->pick_next_task(rq);  //实时进程的类。

       if (p)            return p;        /*。

        * Will never be NULL as the idle class always。

        * returns a non-NULL p:。

        */

       class = class->next;  //rt->next = fair;  fair->next = idle。

   }

在这段代码中体现了Linux所支持的两种类型的进程，实时进程和普通进程。回顾下：实时进程可以采用SCHED_FIFO 和SCHED_RR调度策略，普通进程采用SCHED_NORMAL调度策略。

在这里首先说明一个结构体struct rq,这个结构体是调度器管理可运行状态进程的最主要的数据结构。每个cpu上都有一个可运行的就绪队列。刚才在pick_next_task函数中看到了在选择下一个将要被执行的进程时实际上用的是struct rq上的普通进程的调度或者实时进程的调度，那么具体是如何调度的呢？在实时调度中，为了实现O(1)的调度算法，内核为每个优先级维护一个运行队列和一个DECLARE_BITMAP,内核根据DECLARE_BITMAP的bit数值找出非空的最高级优先队列的编号，从而可以从非空的最高级优先队列中取出进程进行运行。

我们来看下内核的实现

struct rt_prio_array {。

   DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */。

   struct list_head queue[MAX_RT_PRIO];。

};

数组queue[i]里面存放的是优先级为i的进程队列的链表头。在结构体rt_prio_array 中有一个重要的数据构DECLARE_BITMAP，它在内核中的第一如下：

define DECLARE_BITMAP(name,bits) \。

   unsigned long name[BITS_TO_LONGS(bits)]。

5.1对于实时进程的O(1)算法。

这个数据是用来作为进程队列queue[MAX_PRIO]的索引位图。bitmap中的每一位与queue[i]对应，当queue[i]的进程队列不为空时，Bitmap的相应位就为1，否则为0，这样就只需要通过汇编指令从进程优先级由高到低的方向找到第一个为1的位置，则这个位置就是就绪队列中最高的优先级（函数sched_find_first_bit()就是用来实现该目的的）。那么queue[index]->next就是要找的候选进程。

如果还是不懂，那就来看两个图

注：在每个队列上的任务一般基于先进先出的原则进行调度（并且为每个进程分配时间片）

在内核中的实现为：

static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,                           struct rt_rq *rt_rq){    struct rt_prio_array *array = &rt_rq->active;    struct sched_rt_entity *next = NULL;    struct list_head *queue;    int idx;。

   idx = sched_find_first_bit(array->bitmap); //找到优先级最高的位。

   BUG_ON(idx >= MAX_RT_PRIO);    queue = array->queue + idx; //然后找到对应的queue的起始地址。

   next = list_entry(queue->next, struct sched_rt_entity, run_list);  //按先进先出拿任务。

   return next;。

那么当同一优先级的任务比较多的时候，内核会根据。

位图：

将对应的位置为1，每次取出最大的被置为1的位，表示优先级最高：

5.2 关于普通进程的CFS算法：

我们知道，普通进程在选取下一个需要被调度的进程时，是调用的pick_next_task_fair函数。在这个函数中是以调度实体为单位进行调度的。其最主要的函数是：pick_next_entity，在这个函数中会调用wakeup_preempt_entity函数，这个函数的主要作用是根据进程的虚拟时间以及权重的结算进程的粒度，以判断其是否需要抢占。看一下内核是怎么实现的：

wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)。

   s64 gran, vdiff = curr->vruntime - se->vruntime;//计算两个虚拟时间差//如果se的虚拟时间比curr还大，说明本该curr执行，无需抢占。

   if (vdiff <= 0)        return -1;。

   gran = wakeup_gran(curr, se);    if (vdiff > gran)        return 1;    return 0;。

gran为需要抢占的时间差，只有两个时间差大于需要抢占的时间差，才需要抢占，这里避免太频繁的抢占。

wakeup_gran(struct sched_entity *curr, struct sched_entity *se)。

   unsigned long gran = sysctl_sched_wakeup_granularity;    if (cfs_rq_of(curr)->curr && sched_feat(ADAPTIVE_GRAN))。

       gran = adaptive_gran(curr, se);。

   /*

    * Since its curr running now, convert the gran from real-time。

    * to virtual-time in his units.。

    */    if (sched_feat(ASYM_GRAN)) {。

       /*

        * By using 'se' instead of 'curr' we penalize light tasks, so。

        * they get preempted easier. That is, if 'se' < 'curr' then。

        * the resulting gran will be larger, therefore penalizing the。

        * lighter, if otoh 'se' > 'curr' then the resulting gran will。

        * be smaller, again penalizing the lighter task.。

        *

        * This is especially important for buddies when the leftmost。

        * task is higher priority than the buddy.。

        */        if (unlikely(se->load.weight != NICE_0_LOAD))。

           gran = calc_delta_fair(gran, se);。

   } else {        if (unlikely(curr->load.weight != NICE_0_LOAD))。

           gran = calc_delta_fair(gran, curr);。

   }    return gran;。

6.调度中的nice值

首先需要明确的是：nice的值不是进程的优先级，他们不是一个概念，但是进程的Nice值会影响到进程的优先级的变化。

通过命令ps -el可以看到进程的nice值为NI列。PRI表示的是进程的优先级，其实进程的优先级只是一个整数，它是调度器选择进程运行的基础。

普通进程有：静态优先级和动态优先级。

静态优先级：之所有称为静态优先级是因为它不会随着时间而改变，内核不会修改它，只能通过系统调用nice去修改,静态优先级用进程描述符中的static_prio来表示。在内核中/kernel/sched.c中，nice和静态优先级的关系为：

#define NICE_TO_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20)。

#define PRIO_TO_NICE(prio)  ((prio) - MAX_RT_PRIO - 20)。

动态优先级：调度程序通过增加或者减小进程静态优先级的值来奖励IO小的进程或者惩罚cpu消耗型的进程。调整后的优先级称为动态优先级。在进程描述中用prio来表示，通常所说的优先级指的是动态优先级。

由上面分析可知，我们可以通过系统调用nice函数来改变进程的优先级。

#include <stdlib.h>#include <stdio.h>#include <math.h>#include <unistd.h>#include <sys/time.h>#define JMAX (400*100000)#define GET_ELAPSED_TIME(tv1,tv2) ( \。

 (double)( (tv2.tv_sec - tv1.tv_sec) \。

           + .000001 * (tv2.tv_usec - tv1.tv_usec)))//做一个延迟的计算double do_something (void){    int j;    double x = 0.0;    struct timeval tv1, tv2;。

   gettimeofday (&tv1, NULL);//获取时区。

   for (j = 0; j < JMAX; j++)。

       x += 1.0 / (exp ((1 + x * x) / (2 + x * x)));。

   gettimeofday (&tv2, NULL);    return GET_ELAPSED_TIME (tv1, tv2);//求差值}int main (int argc, char *argv[]){    int niceval = 0, nsched;    /* for kernels less than 2.6.21, this is HZ。

      for tickless kernels this must be the MHZ rate。

      e.g, for 2.6 GZ scale = 2600000000 */。

   long scale = 1000;    long ticks_cpu, ticks_sleep;    pid_t pid;。

   FILE *fp;    char fname[256];    double elapsed_time, timeslice, t_cpu, t_sleep;    if (argc > 1)。

       niceval = atoi (argv[1]);。

   pid = getpid ();    if (argc > 2)。

       scale = atoi (argv[2]);    /* give a chance for other tasks to queue up */。

   sleep (3);    sprintf (fname, "/proc/%d/schedstat", pid);//读取进程的调度状态。

   /*

       在schedstat中的数字是什么意思呢？：

   */

   /*    printf ("Fname = %s\n", fname); */。

   if (!(fp = fopen (fname, "r"))) {        printf ("Failed to open stat file\n");        exit (-1);。

   }    //nice系统调用。

   if (nice (niceval) == -1 && niceval != -1) {        printf ("Failed to set nice to %d\n", niceval);        exit (-1);。

   }

   elapsed_time = do_something ();//for 循环执行了多长时间。

   fscanf (fp, "%ld %ld %d", &ticks_cpu, &ticks_sleep, &nsched);//nsched表示调度的次数。

   t_cpu = (float)ticks_cpu / scale;//震动的次数除以1000，就是时间。

   t_sleep = (float)ticks_sleep / scale;。

   timeslice = t_cpu / (double)nsched;//除以调度的次数，就是每次调度的时间（时间片）

   printf ("\nnice=%3d time=%8g secs pid=%5d"。

           "  t_cpu=%8g  t_sleep=%8g  nsched=%5d"。

           "  avg timeslice = %8g\n",。

           niceval, elapsed_time, pid, t_cpu, t_sleep, nsched, timeslice);。

   fclose (fp);    exit (0);。

说明： 首先说明的是/proc/[pid]/schedstat:在这个文件下放着3个变量，他们分别代表什么意思呢？

第一个：该进程拥有的cpu的时间。

第二个：在对列上的等待时间，即睡眠时间。

第三个：被调度的次数

由结果可以看出当nice的值越小的时候，其睡眠时间越短，则表示其优先级升高了。

7.关于获取和设置优先级的系统调用：sched_getscheduler（）和sched_setscheduler。

#include <sched.h>#include <stdlib.h>#include <stdio.h>#include <errno.h>#define DEATH(mess) { perror(mess); exit(errno); }void printpolicy (int policy){    /* SCHED_NORMAL = SCHED_OTHER in user-space */。

   if (policy == SCHED_OTHER)        printf ("policy = SCHED_OTHER = %d\n", policy);    if (policy == SCHED_FIFO)        printf ("policy = SCHED_FIFO = %d\n", policy);    if (policy == SCHED_RR)        printf ("policy = SCHED_RR = %d\n", policy);。

}int main (int argc, char **argv){    int policy;    struct sched_param p;    /* obtain current scheduling policy for this process */。

   //获取进程调度的策略

   policy = sched_getscheduler (0);。

   printpolicy (policy);    /* reset scheduling policy */。

   printf ("\nTrying sched_setscheduler...\n");。

   policy = SCHED_FIFO;。

   printpolicy (policy);。

   p.sched_priority = 50;    //设置优先级为50。

   if (sched_setscheduler (0, policy, &p))。

       DEATH ("sched_setscheduler:");    printf ("p.sched_priority = %d\n", p.sched_priority);    exit (0);。

输出结果：

[root@wang schedule]# ./get_schedule_policy policy = SCHED_OTHER = 0。

Trying sched_setscheduler...。

policy = SCHED_FIFO = 1。

p.sched_priority = 50。

可以看出进程的优先级已经被改变。

java 小题目

#include<fstream>。

#define MaxNum 765432100。

using namespace std;。

ifstream fin("Dijkstra.in");。

ofstream fout("Dijkstra.out");。

int Map[501][501];。

bool is_arrived[501];。

int Dist[501],From[501],Stack[501];。

int p,q,k,Path,Source,Vertex,Temp,SetCard;。

int FindMin()。

{

int p,Temp=0,Minm=MaxNum;。

for(p=1;p<=Vertex;p++)。

if ((Dist[p]<Minm)&&(!is_arrived[p]))。

{

Minm=Dist[p];。

Temp=p;

}

return Temp;

}

int main()

{

memset(is_arrived,0,sizeof(is_arrived));。

fin >> Source >> Vertex;。

for(p=1;p<=Vertex;p++)。

for(q=1;q<=Vertex;q++)。

{

fin >> Map[p][q];。

if (Map[p][q]==0) Map[p][q]=MaxNum;。

}

for(p=1;p<=Vertex;p++)。

{

Dist[p]=Map[Source][p];。

if (Dist[p]!=MaxNum) 。

From[p]=Source;。

else

From[p]=p;

}

is_arrived[Source]=true;。

SetCard=1;

do

{

Temp=FindMin();。

if (Temp!=0)

{

SetCard=SetCard+1;。

is_arrived[Temp]=true;。

for(p=1;p<=Vertex;p++)。

if ((Dist[p]>Dist[Temp]+Map[Temp][p])&&(!is_arrived[p]))。

{

Dist[p]=Dist[Temp]+Map[Temp][p];。

From[p]=Temp;。

}

}

else

break;

}

while (SetCard!=Vertex);。

for(p=1;p<=Vertex;p++)。

if(p!=Source)。

{

fout << "========================\n";。

fout << "Source:" << Source << "\nTarget:" << p << '\n';。

if (Dist[p]==MaxNum)。

{

fout << "Distance:" << "Infinity\n";。

fout << "Path:No Way!";。

}

else

{

fout << "Distance:" << Dist[p] << '\n';。

k=1;

Path=p;

while (From[Path]!=Path)。

{

Stack[k]=Path;。

Path=From[Path];。

k=k+1;

}

fout << "Path:" << Source;。

for(q=k-1;q>=1;q--)。

fout << "-->" << Stack[q];。

}

fout << "\n========================\n\n";。

}

fin.close();

fout.close();。

return 0;

}

Sample Input

2

7

00 20 50 30 00 00 00。

20 00 25 00 00 70 00。

50 25 00 40 25 50 00。

30 00 40 00 55 00 00。

00 00 25 55 00 10 00。

00 70 50 00 10 00 00。

00 00 00 00 00 00 00。

Sample Output。

========================。

Source:2

Target:1

Distance:20

Path:2-->1。

========================。

========================。

Source:2

Target:3

Distance:25

Path:2-->3。

========================。

========================。

Source:2

Target:4

Distance:50

Path:2-->1-->4。

========================。

========================。

Source:2

Target:5

Distance:50

Path:2-->3-->5。

========================。

========================。

Source:2

Target:6

Distance:60

Path:2-->3-->5-->6。

========================。

========================。

Source:2

Target:7

Distance:Infinity。

Path:No Way!

========================。

示例程序及相关子程序：

void Dijkstra(int n,int[] Distance,int[] iPath)。

{

int MinDis,u;。

int i,j;

//从邻接矩阵复制第n个顶点可以走出的路线，就是复制第n行到Distance[]。

for(i=0;i<VerNum;i++)。

{

Distance=Arc[n,i];。

Visited=0;

}//第n个顶点被访问，因为第n个顶点是开始点。

Visited[n]=1;。

//找到该顶点能到其他顶点的路线、并且不是开始的顶点n、以前也没走过。

//相当于寻找u点，这个点不是开始点n。

for(i=0;i<VerNum;i++)。

{

u=0;

MinDis=No;

for(j=0;j<VerNum;j++)。

if(Visited[j] == 0&&(Distance[j]<MinDis))。

{

MinDis=Distance[j];。

u=j;

}

//如范例P1871图G6，Distance=[No,No,10,No,30,100]，第一次找就是V2，所以u=2。

//找完了，MinDis等于不连接，则返回。这种情况类似V5。

if(MinDis==No) return ;。

//确立第u个顶点将被使用，相当于Arc[v,u]+Arc[u,w]中的第u顶点。

Visited[u]=1;。

//寻找第u个顶点到其他所有顶点的最小路，实际就是找Arc[u,j]、j取值在[0，VerNum]。

//如果有Arc[i,u]+Arc[u,j]<Arc[i,j]，则Arc[i,j]=Arc[i,u]+Arc[u,j]<Arc[i,j]。

//实际中，因为Distance[]是要的结果，对于起始点确定的情况下，就是：

//如果(Distance[u] + Arc[u,j]) <= Distance[j] 则：

//Distance[j] = Distance[u] + Arc[u, j]；

//而iPath[]保存了u点的编号；

//同理：对新找出的路线，要设置Visited[j]=0，以后再找其他路，这个路可能别利用到。例如V3。

for(j=0;j<VerNum;j++)。

if(Visited[j]==0&&Arc[u,j]<No&&u!= j) 。

{

if ((Distance[u] + Arc[u,j]) <= Distance[j])。

{

Distance[j] = Distance[u] + Arc[u, j];。

Visited[j]=0;。

iPath[j] = u;。

}

}

}

}

//辅助函数

void Prim()

{

int i,m,n=0;

for(i=0;i<VerNum;i++) 。

{

Visited=0;

T=new TreeNode();。

T.Text =V;

}

Visited[n]++;。

listBox1.Items.Add (V[n]); 。

while(Visit()>0)。

{

if((m=MinAdjNode(n))!=-1)。

{

T[n].Nodes.Add(T[m]); 。

n=m;

Visited[n]++;。

}

else

{

n=MinNode(0);。

if(n>0) T[Min2].Nodes.Add(T[Min1]); 。

Visited[n]++;。

}

listBox1.Items.Add (V[n]); 。

}

treeView1.Nodes.Add(T[0]); 。

}

void TopoSort()。

{

int i,n;

listBox1.Items.Clear(); 。

Stack S=new Stack();。

for(i=0;i<VerNum;i++)。

Visited=0;

for(i=VerNum-1;i>=0;i--)。

if(InDegree(i)==0)。

{

S.Push(i);

Visited++;

}

while(S.Count!=0)。

{

n=(int )S.Pop();。

listBox1.Items.Add (V[n]); 。

ClearLink(n);。

for(i=VerNum-1;i>=0;i--)。

if(Visited==0&&InDegree(i)==0)。

{

S.Push(i);

Visited++;

}

}

}

void AOETrave(int n,TreeNode TR,int w)。

{

int i,w0;

if(OutDegree(n)==0) return;。

for(i=0;i<VerNum;i++)。

if((w0=Arc[n,i])!=0)。

{

listBox1.Items.Add (V+"\t"+(w+w0).ToString()+"\t"+i.ToString()+"\t"+n.ToString());。

TreeNode T1=new TreeNode();。

T1.Text =V+" [W="+(w+w0).ToString()+"]"; 。

TR.Nodes.Add(T1); 。

AOETrave(i,T1,w+w0);。

}

}

void AOE()

{

int i,w=0,m=1;。

TreeNode T1=new TreeNode();。

for(i=0;i<VerNum;i++)。

{

Visited=0;

}

T1.Text =V[0];。

listBox1.Items.Add ("双亲表示法显示这个生成树："); 。

listBox1.Items.Add ("V\tW\tID\tPID");。

for(i=0;i<VerNum;i++)。

{

if((w=Arc[0,i])!=0)。

{

listBox1.Items.Add (V+"\t"+w.ToString()+"\t"+i.ToString()+"\t0");。

TreeNode T2=new TreeNode();。

T2.Text=V+" [W="+w.ToString()+"]";。

AOETrave(i,T2,w);。

T1.Nodes.Add (T2); 。

listBox1.Items.Add("\t\t树"+m.ToString());。

m++;

}

}

treeView1.Nodes.Clear(); 。

treeView1.Nodes.Add (T1);。

}

int IsZero()

{

int i;

for(i=0;i<VerNum;i++)。

if(LineIsZero(i)>=0) return i;。

return -1;

}

int LineIsZero(int n)。

{

int i;

for(i=0;i<VerNum;i++)。

if (Arc[n,i]!=0) return i;。

return -1;

}

void DepthTraverse()。

{

int i,m;

for(i=0;i<VerNum;i++)。

{

Visited=0;

T=new TreeNode();。

T.Text =V;

R=0;

}

while((m=IsZero())>=0)。

{

if(Visited[m]==0) 。

{

listBox1.Items.Add (V[m]);。

R[m]=1;

}

Visited[m]++;。

DTrave(m);

}

for(i=0;i<VerNum;i++)。

{

if(R==1)

treeView1.Nodes.Add (T); 。

}

}

void DTrave(int n)。

{

int i;

if (LineIsZero(n)<0) return;。

for(i=VerNum-1;i>=0;i--)。

if(Arc[n,i]!=0)。

{

Arc[n,i]=0;

Arc[i,n]=0;

if(Visited==0)。

{

listBox1.Items.Add (V);。

T[n].Nodes.Add (T); 。

R=0;

}

Visited++;

DTrave(i);

}

}

void BreadthTraverse()。

{

int i,m;

for(i=0;i<VerNum;i++)。

{

Visited=0;

T=new TreeNode();。

T.Text =V;

R=0;

}

while((m=IsZero())>=0)。

{

if(Visited[m]==0) 。

{

listBox1.Items.Add (V[m]);。

R[m]=1;

}

Visited[m]++;。

BTrave(m);

}

for(i=0;i<VerNum;i++)。

{

if(R==1)

treeView1.Nodes.Add (T); 。

}

}

void BTrave(int n)。

{

int i;

Queue Q=new Queue();。

Q.Enqueue(n);。

while(Q.Count!=0)。

{

for(i=0;i<VerNum;i++)。

{

if(Arc[n,i]!=0)。

{

Arc[n,i]=0;

Arc[i,n]=0;

if(Visited==0)。

{

listBox1.Items.Add(V); 。

T[n].Nodes.Add (T); 。

R=0;

}

Visited++;

Q.Enqueue(i);。

}

}

n=(int )Q.Dequeue(); 。

}

}

int MinNode(int vn)。

{

int i,j,n,m,Min=No;。

n=-1;m=-1;

for (i=vn;i<VerNum;i++)。

for(j=0;j<VerNum;j++)。

if(Arc[i,j]!=No&&Arc[i,j]<Min&&Visited==0&&Visited[j]==1)。

{

Min=Arc[i,j];n=i;m=j;。

}

Min1=n;Min2=m;。

return n;

}

int MinAdjNode(int n)。

{

int i,Min,m;

Min=No;m=-1;

for(i=0;i<VerNum;i++)。

if(Arc[n,i]!=No&&Visited==0&&Min>Arc[n,i]&&Visited[n]==1)。

{

Min=Arc[n,i];m=i;。

}

return m;

}

int Visit()

{

int i,s=0;

for(i=0;i<VerNum;i++)。

if(Visited==0) s++;。

return s;

}

[编辑本段]dijkstra算法的Pascal实现：

program dijkstra;。

var

a:array[1..100,1..100]of integer;。

flag:array[1..100]of boolean;。

w,x,n,i,j,min,minn:integer;。

begin

readln(n);

for i:=1 to n do。

begin

for j:=1 to n do read(a[i,j]);。

readln;

end;

fillchar(flag,sizeof(flag),false);。

flag[1]:=true;。

minn:=1;

for x:=2 to n do。

begin

min:=32767;

for i:=2 to n do。

if (a[1,i]<min)and(flag=false) then。

begin

min:=a[1,i];

minn:=i;

end;

flag[minn]:=true;。

for j:=1 to n do。

if (j<>minn) and (a[1,minn]+a[minn,j]<a[1,j]) and(flag[j]=false) then。

a[1,j]:=a[1,minn]+a[minn,j];。

end;

for i:=1 to n do。

write(a[1,i],' ');。

end.

4

0 100 30 999

100 0 99 10

30 99 0 99

999 10 99 0

程序输出：0 100 30 110。

dijkstra算法的MATLAB实现：

clear;

clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];。

a(2,:)=[zeros(1,2),15,20,M,25];。

a(3,:)=[zeros(1,3),10,20,M];。

a(4,:)=[zeros(1,4),10,25];。

a(5,:)=[zeros(1,5),55];。

a(6,:)=zeros(1,6);。

a=a+a';

pb(1:length(a))=0;pb(i)=1;index1=1;index2=ones(1,length(a));。

d(1:length(a))=M;d(i)=0;temp=1;。

while sum(pb)<length(a)。

tb=find(pb==0);。

d(tb)=min(d(tb),d(temp)+a(temp,tb));。

tmpb=find(d(tb)==min(d(tb)));。

temp=tb(tmpb(i));。

pb(temp)=1;

index1=[index1,temp];。

index=index1(find(d(index1)==d(temp)-a(temp,index1)));。

if length(index)>=2。

index=index(1);。

end

index2(temp)=index;。

end

d, index1, index2 。

matlab编程

function [s,d]=minroute(i,m,w,opt)。

% 图与网络论中求最短路径的dijkstra算法M函数。

% 格式[s,d]=minroute(i,m,w,opt)。

if nargin<4,opt=0;end。

dd=[];tt=[];ss=[];ss(1,1)=i;v=1:m;v(i)=[];。

dd=[0;i];kk=2;[mdd,ndd]=size(dd);。

while~isempty(v)。

[tmpd,j]=min(w(i,v));tmpj=v(j);。

for k=2:ndd

[tmp2,jj]=min(dd(1,k)+w(dd(2,k),v));。

tmp2=v(jj);tt(k-1,:)=[tmp1,tmp2,jj];。

end;

tmp=[tmpd,tmpj,j;tt];[tmp3,tmp4]=min(tmp(;,1));。

if tmp3==tmpd。

ss(1:2,kk)=[i;tmp(tmp4,2)];。

else,tmp5=find(ss(:,tmp4)~=0);tmp6=length(tmp5);。

if dd(2,tmp4)=ss(tmp6,tmp4)。

ss(1:tmp6+1,kk)=[ss(tmp5,tmp4);tmp(tmp4,2)];。

else,ss(1:3,kk)=[i;dd(2,tmp4);tmp(tmp4,2)];。

end;end

dd=[dd,[tmp3,tmp(tmp4,2)]];v(tmp(tmp4,3))=[];。

[mdd,ndd]=size(dd);kk=kk+1;。

end;

if opt==1

[tmp,t]=sort(dd(2,:));s=ss(:t);d=dd(1,t);。

else,s=ss;d=dd(1,:);。

end

C# 队列移除某个元素

package util;

import java.util.Collection;。

import java.util.Comparator;。

import java.util.Iterator;。

import java.util.List;。

import java.util.ListIterator;。

import java.util.Map;。

import java.util.Set;。

import java.util.SortedMap;。

import java.util.SortedSet;。

import java.util.concurrent.locks.Lock;。

import java.util.concurrent.locks.ReadWriteLock;。

import java.util.concurrent.locks.ReentrantReadWriteLock;。

/**

* <p>

* 操作集合的类，可以返回以读写锁实现的各类集合<br>。

* </p>

*

*/

public class CollectionUtils {。

private CollectionUtils() {}。

/**

* <p>

* 返回用读写锁实现的集合。

* </p>

*

* @param collection。

* 基础集合。

* @return 同步集合。

*/

public static <T> Collection<T> readWriteLockCollection(。

Collection<T> collection) {。

return new ReadWriteLockCollection<T>(collection);。

}

/**

* <p>

* 返回用读写锁实现的List。

* </p>

*

* @param list。

* 基础List。

* @return 同步List。

*/

public static <T> List<T> readWriteLockList(List<T> list) {。

return new ReadWriteLockList<T>(list);。

}

/**

* <p>

* 返回用读写锁实现的Set。

* </p>

*

* @param set

* 基础Set。

* @return 同步Set。

*/

public static <T> Set<T> readWriteLockSet(Set<T> set) {。

return new ReadWriteLockSet<T>(set);。

}

/**

* <p>

* 返回用读写锁实现的SortedSet。

* </p>

*

* @param sortedSet。

* 基础SortedSet。

* @return 同步SortedSet。

*/

public static <T> SortedSet<T> readWriteLockSortedSet(SortedSet<T> sortedSet) {。

return new ReadWriteLockSortedSet<T>(sortedSet);。

}

/**

* <p>

* 返回用读写锁实现的Map。

* </p>

*

* @param map

* 基础Map。

* @return 同步Map。

*/

public static <K, V> Map<K, V> readWriteLockMap(Map<K, V> map) {。

return new ReadWriteLockMap<K, V>(map);。

}

/**

* <p>

* 返回用读写锁实现的SortedMap。

* </p>

*

* @param sortedMap。

* 基础SortedMap。

* @return 同步SortedMap。

*/

public static <K, V> SortedMap<K, V> readWriteLockSortedMap(。

SortedMap<K, V> sortedMap) {。

return new ReadWriteLockSortedMap<K, V>(sortedMap);。

}

private static class ReadWriteLockCollection<T> implements Collection<T> {。

private Collection<T> collection;。

protected ReadWriteLock lock = new ReentrantReadWriteLock();。

private ReadWriteLockCollection(Collection<T> collection) {。

if (collection == null)。

throw new NullPointerException();。

this.collection = collection;。

}

@Override

public boolean add(T e) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return collection.add(e);。

} finally {

lock.unlock();。

}

}

@Override

public boolean addAll(Collection<? extends T> c) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return collection.addAll(c);。

} finally {

lock.unlock();。

}

}

@Override

public void clear() {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

collection.clear();。

} finally {

lock.unlock();。

}

}

@Override

public boolean contains(Object o) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.contains(o);。

} finally {

lock.unlock();。

}

}

@Override

public boolean containsAll(Collection<?> c) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.containsAll(c);。

} finally {

lock.unlock();。

}

}

@Override

public boolean isEmpty() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.isEmpty();。

} finally {

lock.unlock();。

}

}

@Override

public Iterator<T> iterator() {。

return collection.iterator();。

}

@Override

public boolean remove(Object o) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return collection.remove(o);。

} finally {

lock.unlock();。

}

}

@Override

public boolean removeAll(Collection<?> c) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return collection.removeAll(c);。

} finally {

lock.unlock();。

}

}

@Override

public boolean retainAll(Collection<?> c) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return collection.retainAll(c);。

} finally {

lock.unlock();。

}

}

@Override

public int size() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.size();。

} finally {

lock.unlock();。

}

}

@Override

public Object[] toArray() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.toArray();。

} finally {

lock.unlock();。

}

}

@Override

public <E> E[] toArray(E[] a) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return collection.toArray(a);。

} finally {

lock.unlock();。

}

}

}

private static class ReadWriteLockList<T> extends。

ReadWriteLockCollection<T> implements List<T> {。

private List<T> list;。

private ReadWriteLockList(List<T> list) {。

super(list);。

this.list = list;。

}

@Override

public void add(int index, T element) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

list.add(index, element);。

} finally {

lock.unlock();。

}

}

@Override

public boolean addAll(int index, Collection<? extends T> c) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return list.addAll(index, c);。

} finally {

lock.unlock();。

}

}

@Override

public T get(int index) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return list.get(index);。

} finally {

lock.unlock();。

}

}

@Override

public int indexOf(Object o) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return list.indexOf(o);。

} finally {

lock.unlock();。

}

}

@Override

public int lastIndexOf(Object o) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return list.lastIndexOf(o);。

} finally {

lock.unlock();。

}

}

@Override

public ListIterator<T> listIterator() {。

return list.listIterator();。

}

@Override

public ListIterator<T> listIterator(int index) {。

return list.listIterator(index);。

}

@Override

public T remove(int index) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return list.remove(index);。

} finally {

lock.unlock();。

}

}

@Override

public T set(int index, T element) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return list.set(index, element);。

} finally {

lock.unlock();。

}

}

@Override

public List<T> subList(int fromIndex, int toIndex) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockList<T>(。

list.subList(fromIndex, toIndex));。

} finally {

lock.unlock();。

}

}

}

private static class ReadWriteLockSet<T> extends ReadWriteLockCollection<T>。

implements Set<T> {。

private ReadWriteLockSet(Set<T> set) {。

super(set);

}

}

private static class ReadWriteLockSortedSet<T> extends ReadWriteLockSet<T>。

implements SortedSet<T> {。

private SortedSet<T> sortedSet;。

private ReadWriteLockSortedSet(SortedSet<T> sortedSet) {。

super(sortedSet);。

this.sortedSet = sortedSet;。

}

@Override

public Comparator<? super T> comparator() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedSet.comparator();。

} finally {

lock.unlock();。

}

}

@Override

public T first() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedSet.first();。

} finally {

lock.unlock();。

}

}

@Override

public SortedSet<T> headSet(T toElement) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedSet<T>(。

sortedSet.headSet(toElement));。

} finally {

lock.unlock();。

}

}

@Override

public T last() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedSet.last();。

} finally {

lock.unlock();。

}

}

@Override

public SortedSet<T> subSet(T fromElement, T toElement) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedSet<T>(sortedSet.subSet(。

fromElement, toElement));。

} finally {

lock.unlock();。

}

}

@Override

public SortedSet<T> tailSet(T fromElement) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedSet<T>(。

sortedSet.tailSet(fromElement));。

} finally {

lock.unlock();。

}

}

}

private static class ReadWriteLockMap<K, V> implements Map<K, V> {。

private Map<K, V> map;。

protected ReadWriteLock lock = new ReentrantReadWriteLock();。

private ReadWriteLockMap(Map<K, V> map) {。

if (map == null)。

throw new NullPointerException();。

this.map = map;。

}

@Override

public void clear() {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

map.clear();。

} finally {

lock.unlock();。

}

}

@Override

public boolean containsKey(Object key) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return map.containsKey(key);。

} finally {

lock.unlock();。

}

}

@Override

public boolean containsValue(Object value) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return map.containsValue(value);。

} finally {

lock.unlock();。

}

}

@Override

public Set<java.util.Map.Entry<K, V>> entrySet() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSet<java.util.Map.Entry<K, V>>(。

map.entrySet());。

} finally {

lock.unlock();。

}

}

@Override

public V get(Object key) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return map.get(key);。

} finally {

lock.unlock();。

}

}

@Override

public boolean isEmpty() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return map.isEmpty();。

} finally {

lock.unlock();。

}

}

@Override

public Set<K> keySet() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSet<K>(map.keySet());。

} finally {

lock.unlock();。

}

}

@Override

public V put(K key, V value) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return map.put(key, value);。

} finally {

lock.unlock();。

}

}

@Override

public void putAll(Map<? extends K, ? extends V> m) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

map.putAll(m);。

} finally {

lock.unlock();。

}

}

@Override

public V remove(Object key) {。

Lock lock = this.lock.writeLock();。

lock.lock();。

try {

return map.remove(key);。

} finally {

lock.unlock();。

}

}

@Override

public int size() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return map.size();。

} finally {

lock.unlock();。

}

}

@Override

public Collection<V> values() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockCollection<V>(map.values());。

} finally {

lock.unlock();。

}

}

}

private static class ReadWriteLockSortedMap<K, V> extends。

ReadWriteLockMap<K, V> implements SortedMap<K, V> {。

private SortedMap<K, V> sortedMap;。

private ReadWriteLockSortedMap(SortedMap<K, V> sortedMap) {。

super(sortedMap);。

this.sortedMap = sortedMap;。

}

@Override

public Comparator<? super K> comparator() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedMap.comparator();。

} finally {

lock.unlock();。

}

}

@Override

public K firstKey() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedMap.firstKey();。

} finally {

lock.unlock();。

}

}

@Override

public SortedMap<K, V> headMap(K toKey) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedMap<K, V>(。

sortedMap.headMap(toKey));。

} finally {

lock.unlock();。

}

}

@Override

public K lastKey() {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return sortedMap.lastKey();。

} finally {

lock.unlock();。

}

}

@Override

public SortedMap<K, V> subMap(K fromKey, K toKey) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedMap<K, V>(sortedMap.subMap(。

fromKey, toKey));。

} finally {

lock.unlock();。

}

}

@Override

public SortedMap<K, V> tailMap(K fromKey) {。

Lock lock = this.lock.readLock();。

lock.lock();。

try {

return new ReadWriteLockSortedMap<K, V>(。

sortedMap.tailMap(fromKey));。

} finally {

lock.unlock();。

}

}

}

c#中如何读取文本文件的最后一行？

队列只能移除第一个对象，如果想把某个对象移除，它之前的所有对象都得移除。

方法：Dequeue()

如果想移除某个元素，请把队列转换为List。

List

new

List(q.ToArray())。

原文地址：http://www.qianchusai.com/queuetoarray-50.html