C语言实现任务调度
任务调度
①问题描述
多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。
●忽略任务提交的时间差，即认为各任务同时提交。
●各任务不同时提交。
②基本要求
●为任务列表设计数据结构和存储结构。
●任务输入，至少包括任务编号及所需CPU的服务时间，任务数不得少
于5个。
●如果按提交顺序执行，求出每个任务的开始执行时间、终止时间、等待
时间和所有任务的平均等待时间。
●按平均等待时间最短，设计任务调度算法，输出任务的执行序列；求出
每个任务的开始执行时间、终止时间、等待时间和所有任务的平均等待
时间；并把结果与上一时间对比。
③设计要点提示
●为使各任务平均等待时间最短，如果忽略任务提交的时间差，调度时应
该按短任务优先进行调度，即：按照各任务需要CPU服务时间的长短，
确定执行顺序，短的在前，长的在后。
例：任务列表2如下，则执行序列如表3所示。
表2 任务列表
任务所需CPU时间(s) 任务所需CPU时间(s)
P1 8 P5 9
P2 4 P6 20
P3 12 P7 15
P4 5
表3 任务执行序列
任务所需CPU时间(s) 等待时间结束时间开始时间P1 4 0 4 0
P2 5 4 9 4
P3 8 9 17 9
P4 9 17 26 17
P5 12 26 38 26
P6 15 38 53 38
P7 20 53 73 53
●根据上一问题的分析，需要根据任务列表，按任务的CPU服务时间进
行排序。
●如果考虑任务提交的时间差，应该按“最短剩余时间”优先进行调度。
调度发生在每次任务提交时，从未完成任务中选择需要CPU时间最短
的任务。
例：任务提交情况如表4所示。
表4 任务列表
任务提交时刻所需CPU时间(s) 任务提交时刻所需CPU时间(s) P1 0 8 P5 4 9
P2 1 4 P6 5 20
P3 2 12 P7 6 15
P4 3 5
0时刻，只有P1，所以运行P1。
1s时，P2提交，此时，P2需要CPU服务时间为4，P1还需7，则暂停P1，先运行P2。
2s时，P3提交，此时，P1、P2、P3各自需CPU服务时间为：7、3、12，所以继续运行P2。
依次类推，直至所有任务完成。
#include
#include
#define MAXNUM 100
typedef struct Node1
{int name;
int time;
int gettime;
struct Node1 *next;
}Lnode1;
void waitlest(Lnode1 *p)
{Lnode1 *q,*head;
int a,wt,st,ft;
wt=0;st=0;ft=0;
printf("任务所需CPU时间(s) 等待时间结束时间开始时间\n");
head=p;
while(head->next)
{q=head;
p=q->next;
while(p->next)
{ q=q->next;
p=p->next;
if(q->time
{a=q->name;
q->name=p->name;
p->name=a;
a=q->time;
q->time=p->time;
p->time=a;
}
}
printf(" %d ",p->name);
printf("%10d",p->time);
wt=ft;
st=wt;
ft=ft+p->time;
printf("%10d",wt);
printf("%10d",ft);
printf("%10d",st);
printf("\n");
q->next=NULL;
free(p);
}
}
void shijiancha(Lnode1 *p)
{Lnode1 *first,*head,*q,*r;
int a,n,t;
printf("任务\n");
first=p;
p=first->next;
n=p->gettime;
q=(Lnode1*)malloc(sizeof(struct Node1)); head=q;
while(p)
{r=(Lnode1*)malloc(sizeof(struct Node1)); q->next=r;
q=q->next;
q->next=NULL;
q->name=p->name;
q->time=p->time;
q->gettime=p->gettime;
r=head->next;
if(r->next)
{if(r->next->next)
{q=r->next;
while(q->next)
{
if(r->time>q->time)
{a=r->name;
r->name=q->name;
a=r->time;
r->time=q->time;
q->time=a;
}
q=q->next;
r=r->next;
}//end while q n
}//end if r n n
}//end if r n
if(head->next->next)
{t=p->gettime-n;
n=p->gettime;
while(t!=0)
{if(t>head->next->time)
{t=t-head->next->time;
printf(" %d ",head->next->name);
printf("\n");
head->next=head->next->next;
}
else {if(t
{head->next->time=head->next->time-t;
t=0;
}
else
{t=0;
printf(" %d ",head->next->name);
printf("\n");
head->next=head->next->next;
}
}
}//end while t
}//end if h n n
p=p->next;
}//end while p
r=head->next;
q=r->next;
while(q)
{
if(r->time>q->time)
{a=r->name;
r->name=q->name;
a=r->time;
r->time=q->time;
q->time=a;
}
q=q->next;
r=r->next;
}
r=head->next;
while(r)
{ printf(" %d ",r->name);
printf("\n");
r=r->next;
}
}//end shijiancha
void main()
{int t,a,b,n;
Lnode1 *p,*q,*first;
p=(Lnode1*)malloc(sizeof(struct Node1));
first=p;
a=0;
printf("输入1，选择忽略提交任务的时间差；输入2，选择考虑提交任务的时
间差:");
scanf("%d",&b);
do
{ q=(Lnode1*)malloc(sizeof(struct Node1));
p->next=q;
p=p->next;
printf("请输入任务名:");
scanf("%d",&n);
p->name=n;
if(b==2)
{ printf("请输入任务提交时刻:");
scanf("%d",&t);
p->gettime=t;
}
else p->gettime=0;
printf("请输入任务所需时间(s):");
scanf("%d",&t);
p->time=t;
printf("是否继续添加任务？输入1继续提交，输入0结束提交");
scanf("%d",&a);
}while(a!=0);
p->next=NULL;
if(b==1)
{ printf("输入1：按提交顺序执行；输入2：按平均等待时间最短");
scanf("%d",&a);
if(a==1)
{ p=first->next;
printf("任务所需CPU时间(s)\n");
while(p)
{
printf(" %d ",p->name);
printf(" %d",p->time);
printf("\n");
p=p->next;
}
}
else waitlest(first);
}
else shijiancha(first);
}
处理器调度习题
处理器调度 选择题 当CPU执行操作系统代码时，则处理机处于( )。 A．执行态 B．目态 C．管态 D．就绪态 ( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 A．系统调用 B．操作系统 C．内核 D．特权指令 操作系统提供给程序员的接口是( )。 A．进程 B．系统调用 C．库函数 D．B和C 用户程序向系统提出使用外设的请求方式是( )。 A．作业申请 B．原语 C．系统调用 D．I／O指令 当作业正常完成进入完成状态时，操作系统( )。 A．将输出该作业的结果并删除内存中的作业 B．将收回该作业的所占资源并输出结果 C．将收回该作业的所占资源及输出结果，并删除该作业 D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 B．作业是比进程低一级的概念。 C．一个作业至少由一个进程组成。 D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 作业从后备作业到被调度程序选中的时间称为( )。 周转时间B．响应时间C．等待调度时间D．运行时间 设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 A．T1+T2+T3 B．1／3(T1+T2+T3) C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 从作业提交给系统到作业完成的时间间隔称为作业的( )。 A．中断时间 B．等待时间 C．周转时间 D．响应时间 设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 A．1 h B．5 h C．2．5 h D．8 h FCFS调度算法有利于( )。 A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 下列哪种说法不是SJ(P)F调度算法的缺点( )。 A．对于长作业(进程)不利 B．未考虑作业(进程)的紧迫程度 C．不能有效降低作业(进程)的平均等待时间 D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 A．先来先服务调度算法B．短进程优先调度算法 C．优先权调度算法D．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。
哈夫曼树及其应用(完美版)
数据结构课程设计设计题目：哈夫曼树及其应用 学院：计算机科学与技术 专业：网络工程 班级：网络 131 学号：1308060312 学生姓名：谢进 指导教师：叶洁 2015年7 月12 日
设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 1、熟悉树的二叉树的存储结构及其特点。 2、掌握建立哈夫曼树和哈夫曼编码的方法。 设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括A 、B 、C 、D 、E 、F六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100），对这六种字符进行哈夫曼编码。 设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，∑WiLi 恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。设计实现的功能： 1.以二叉链表存储， 2.建立哈夫曼树； 3.求每个字符的哈夫曼编码并显示。
操作系统处理器调度算法C++程序
一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include
数据结构哈夫曼树的实现
#include
哈夫曼树的实验报告1
一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree
哈夫曼树及应用
常熟理工学院微课教学比赛教学设计 1、课程基本信息 课程名称：哈夫曼树及应用所属课程：数据结构与算法 课程所属专业：软件工程适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林时长：15分钟 所属学校：常熟理工学院所属院系：计算机科学与工程学院 2.教学背景 《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点 《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。 《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点 “树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。 本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。 3.教学设计 3.1教学目的 通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用； （2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫
进程调度C语言实现
#include
哈夫曼树建立、哈夫曼编码算法的实现
#include
if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {
哈夫曼算法的实现及应用
摘要：哈夫曼树是带权路径长度（WPL）最小的二叉树，通过对哈夫曼算法的研究，提出一种求取哈夫曼树带权路径长度的计算方法和应用。 关键词：哈夫曼算法、二叉树、WPL、编码 1 引言： 哈夫曼树是一种特殊的二叉树，又称最优二叉树：假设有一组（无序）实数｛w1,w2,w3,w4,…,wm｝，现要构造一棵以wi（i=1，2，3，4…，m）为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。若l表示从根到第i个外部结点的路径长度，m为外部结点的个数，wi 为第i个外部结点的权值，则有WPL=∑wili（0 一、目得与要求?进程调度就是处理机管理得核心内容。本实验要求用高级语言编写模拟进程调度程序,以便加深理解有关进程控制快、进程队列等概念，并体会与了解优先数算法与时间片轮转算法得具体实施办法。 二、实验内容 1、设计进程控制块PCB得结构,通常应包括如下信息: 进程名、进程优先数(或轮转时间片数）、进程已占用得CPＵ时间、进程到完成还需要得时间、进程得状态、当前队列指针等。 2、编写两种调度算法程序: 优先数调度算法程序?循环轮转调度算法程序 3、按要求输出结果。?三、提示与说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态;执行状态(ＲUN)、就绪状态(ＲEＡDY,包括等待状态)与完成状态(ＦＩＮＩSH）,并假定初始状态为就绪状态。?(一）进程控制块结构如下：?ＮAＭE——进程标示符ＰRIO／ＲＯＵNＤ——进程优先数／进程每次轮转得时间片数（设为常数2)? CPUTIME——进程累计占用CPU得时间片数? NEEDTＩME——进程到完成还需要得时间片数 SＴＡTE——进程状态?ＮEXT——链指针?注: １、为了便于处理，程序中进程得得运行时间以时间片为单位进行计算; 2、各进程得优先数或轮转时间片数,以及进程运行时间片数得初值,均由用户在程序运行时给定。?(二)进程得就绪态与等待态均为链表结构，共有四个指针如下:? RUＮ——当前运行进程指针 RＥADY——就需队列头指针 TAIＬ——就需队列尾指针 FINISＨ——完成队列头指针 1、在优先数算法中,进程优先数得初值设为： (三)程序说明? 50－NEEDＴIME?每执行一次,优先数减1，CＰU时间片数加１,进程还需要得时间片数减1。 在轮转法中,采用固定时间片单位（两个时间片为一个单位),进程每轮转一次,CP 一、目的和要求 进程调度是处理机管理的核心容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。 二、实验容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写两种调度算法程序： 优先数调度算法程序 循环轮转调度算法程序 3.按要求输出结果。 三、提示和说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（R UN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 （一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME——进程累计占用CPU的时间片数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； 2.各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 （三）程序说明 1. 在优先数算法中，进程优先数的初值设为： 50-NEEDTIME 每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 2. 程序的模块结构提示如下： 整个程序可由主程序和如下7个过程组成： （1）INSERT1——在优先数算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中； （2）INSERT2——在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； （3）FIRSTIN——调度就绪队列的第一个进程投入运行； （4）PRINT——显示每执行一次后所有进程的状态及有关信息。 （5）CREATE——创建新进程，并将它的PCB插入就绪队列； （6）PRISCH——按优先数算法调度进程； （7）ROUNDSCH——按时间片轮转法调度进程。 主程序定义PCB结构和其他有关变量。 （四）运行和显示 程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIM E值。 每次显示结果均为如下5个字段： name cputime needtime priority state 注： 时间片轮转算法和优先级调度算法C语言模拟实现收藏 一、目的和要求 进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。 二、实验内容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写两种调度算法程序： 优先数调度算法程序 循环轮转调度算法程序 3.按要求输出结果。 三、提示和说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（R UN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 （一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME——进程累计占用CPU的时间片数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； 2.各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 （三）程序说明 1. 在优先数算法中，进程优先数的初值设为： 50-NEEDTIME 每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 2. 程序的模块结构提示如下： 整个程序可由主程序和如下7个过程组成： （1）INSERT1——在优先数算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中； （2）INSERT2——在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； （3）FIRSTIN——调度就绪队列的第一个进程投入运行； （4）PRINT——显示每执行一次后所有进程的状态及有关信息。 （5）CREATE——创建新进程，并将它的PCB插入就绪队列； （6）PRISCH——按优先数算法调度进程； （7）ROUNDSCH——按时间片轮转法调度进程。 主程序定义PCB结构和其他有关变量。 （四）运行和显示 程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIM E值。 每次显示结果均为如下5个字段： name cputime needtime priority state 注： #include 实验6：哈夫曼树及哈夫曼编码的算法实现 实验所需 学时数 2学时 实验目的1)掌握哈夫曼树的基本概念及其存储结构； 2)掌握哈夫曼树的建立算法； 3)掌握哈夫曼树的应用（哈夫曼编码和译码）。 实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。 实验所需 器材 计算机及VC++ 6.0软件 内容要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树 2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据： 输入字符串“this*program*is*my*favourite”，完成这28个字符的编码和译码。 实验结果 1、演示程序运行结果。 2、说明调试过程中出现的现象 学生实验评价依据： 优：实验认真、刻苦，有钻研精神，不无故缺席。 良：能认真对待实验，不无故缺席。 中：基本能认真对待实验，不无故缺席。 差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。 #include #include "stdio.h" #include 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; } } c++数据结构实验哈夫曼树 数据结构实验报告 1．实验要求 i.实验目的: （1）掌握二叉树基本操作的实现方法 （2）掌握二叉树基本操作的实现方法 （3）了解哈夫曼树的思想和相关概念 （4）学习使用二叉树解决实际问题的能力 （5）熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方法。 （6）熟悉设计算法的过程 （7）进一步掌握指针、异常处理的使用 ii.实验内容： 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度 的字符串s进行统计，统计每个字符的频 度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经 建好的赫夫曼树进行编码，并将每个字符 的编码输出。 3、编码(Encoding)：根据编码表对输入 的字符串进行编码，并将编码后的字符串 输出。 4、译码(Decoding)：利用已经建好的赫 夫曼树对编码后的字符串进行译码，并输 出译码结果。 5、打印(Print)：以直观的方式打印赫夫 曼树（选作） 6、计算输入的字符串编码前和编码后的 长度，并进行分析，讨论赫夫曼编码的压 缩效果。 测试数据： I love data Structure, I love Computer.I will try my best to study data structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现 的次数统计频度，对没有出现的 字符一律不用编码。 iii.代码要求： 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析 树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是每个结点最多两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。 2.1 存储结构 1.结点结构的存储方式： 题目：哈夫曼树应用 学生姓名：谢辉 学号： 201317010201 专业班级：计科13102 同组姓名：赵丽娜 指导教师：徐晓蓉 设计时间：2014年下学期第18周 目录 一、需求分析 (3) 1. 分析问题 (3) 2. 确定解决方案 (3) 3. 输入的形式和输入值的范围 (3) 4.输出的形式 (3) 5.程序所能达到的功能 (3) 二、概要设计 (4) 1. 主程序的流程图： (4) 2．程序中数据类型的定义： (5) 3．各程序模块之间的层次(调用)关系： (5) 三、详细设计 (6) 1．哈夫曼树存储及类的定义： (6) 2.哈夫曼树的基本操作: (6) 3.主函数 (6) 四、调试分析和测试结果 (8) 1. 测试数据及其输出结果： (8) 2. 调试过程中遇到的问题及解决办法: (12) 五、总结 (13) 六、参考文献 (13) 七、致谢 (13) 八、附录 (13) 2 一、需求分析 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 （1）I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n 个权值，建立哈夫曼树，并将它存于文件hfmTree中。 （2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 （3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 （4）P:打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每 3 2009级数据结构实验报告 实验名称：实验三——哈夫曼编/解码器的实现 学生姓名：陈聪捷 日期：2010年11月28日 1．实验要求 一、实验目的： 了解哈夫曼树的思想和相关概念； 二、实验内容： 利用二叉树结构实现哈夫曼编/解码器 1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。 2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。 6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2. 程序分析 存储结构 二叉树 template 如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到 链表尾部，同时n++ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表 源代码： void HuffmanTree::Init(string Input) { Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)）算法伪代码： 1.创建一个长度为2*tSize-1的三叉链表 2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点 的data域，并将对应结点的孩子域和双亲域赋为空 3.从三叉链表的第tSize个结点开始，i=tSize 3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下 标x,y。 3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点 3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i 结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结 点的双亲设置为空 4. 根据哈夫曼树创建编码表 源代码： void HuffmanTree::CreateHTree(Node *p,int n) { root= new BiNode时间片轮转算法和优先级调度算法 C语言模拟实现
时间片轮转算法和优先级调度算法-C语言模拟实现-收藏
时间片轮转算法和优先级调度算法 C语言模拟实现 收藏精编版
短作业优先调度算法C语言实现
实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
进程调度算法 C与C++
c++数据结构实验哈夫曼树
哈夫曼树的应用数据结构课程设计
北京邮电大学信通院数据结构实验三——哈夫曼树实验报告
- 哈夫曼编码、哈夫曼树构建、哈夫曼树Java实现
- 哈夫曼树的实验报告1
- 数据结构_哈夫曼树的构造及其应用_课程设计_实验报告
- 用C++实现哈夫曼树的代码
- 实验二 哈夫曼树及哈夫曼编码译码的实现
- 哈夫曼树建立、哈夫曼编码算法的实现
- c++数据结构实验哈夫曼树
- 数据结构 哈夫曼树 C++实现
- 哈夫曼树的实现代码
- 数据结构哈夫曼树的实现
- 哈夫曼树讲解
- 北京邮电大学信通院数据结构实验三——哈夫曼树实验报告
- 构造哈夫曼树并求哈夫曼编码的算法实现
- 最优二叉树(哈夫曼树)
- 数据结构哈夫曼树实验报告
- 实验6：哈夫曼树及哈夫曼编码的算法实现 - 副本
- 哈夫曼树的课程设计报告
- 哈夫曼树实验报告
- 哈夫曼树C语言实现
- 哈夫曼算法的理解及原理分析,算法实现,构造哈夫曼树的算法