广工 操作系统课程设计 最佳适应算法、最坏适应算法、循环首次适应算法

动态分区分配算法仿真，循环首次适应算法、最佳适应算法、最坏适应算法

#include

#include//在输入输出流中用到控制符

#include//用到了SetConsoleTextAttribute函数

#define minsize 2//事先规定的不再切割的剩余分区大小为2

using namespace std;

struct Node

{

int name;

int start;

int size;

int state;

Node *pre;

Node *next;

};

typedef struct Dlinklist

{

Node *head;

}Dlist;

//===================

Dlist pro,fre;

int memory,name,size,fit;

Node *temp=NULL;//temp是NestFit算法中的起始查寻指针

//===================

void initDlist(Dlist &L)//创建带有头结点的双向链表

{

L.head=new Node;

L.head->next=L.head->pre=NULL;

}

void MemoryInit()//初始化两个链表

{

initDlist(pro); //process链表

initDlist(fre); //free block链表

Node *p=new Node;

p->name=0;

p->start=0;

p->state=0;

p->size=memory;

p->next=NULL;//这里曾错写成p->pre..............

p->pre=fre.head;//这里曾漏写

fre.head->next=p;

}

int getLength(Dlist &L)//返回链表的长度，即元素的个数

int m=0;

Node *p=L.head->next;

while(p!=NULL)

{

m++;

p=p->next;

}

return m;

}

void arrangeSmaller(Dlist &L)//冒泡排序，链表按size进行排序，从小到大

{

int length=getLength(L);

for(int i=0; i=2的时候才排序

{

Node *p=L.head->next;

Node *q=p->next;

int

a,b,c,d;//===================================================================== =====

for(int j=0; j

{

if(p->size>q->size) //交换位置，如果前面的大于后面的，使小的上浮，如果两个相等，则还是原来在前的保持在前

{

a=p->size;

p->size=q->size;

q->size=a;

b=p->name;

p->name=q->name;

q->name=b;

c=p->start;

p->start=q->start;

q->start=c;

d=p->state;//============================================================== ============

p->state=q->state;

q->state=d;

}

p=p->next;

q=p->next;

}

}

void arrangeBigger(Dlist &L)//链表按size进行排序，从大到小

{

int length=getLength(L);

for(int i=0; i

{

Node *p=L.head->next;

Node *q=p->next;

int a,b,c,d;

for(int j=0; j

{

if(p->sizesize)

{

a=p->size;

p->size=q->size;

q->size=a;

b=p->name;

p->name=q->name;

q->name=b;

c=p->start;

p->start=q->start;

q->start=c;

d=p->state;//============================================================== ============

p->state=q->state;

q->state=d;

}

p=p->next;

q=p->next;

}

}

}

void arrangeStart(Dlist &L)//链表按start递增排序

{

int length=getLength(L);

for(int i=0; i

{

Node *p=L.head->next;

Node *q=p->next;

int a,b,c,d;

for(int j=0; j

{

if(p->start>q->start)

{

a=p->size;

p->size=q->size;

q->size=a;

b=p->name;

p->name=q->name;

q->name=b;

c=p->start;

p->start=q->start;

q->start=c;

d=p->state;//============================================================== ============

p->state=q->state;

q->state=d;

}

p=p->next;

q=p->next;

}

}

}

void DlistInsert(Dlist &L,Node e) //在头结点之后插入元素，即L.head->next指向e {

Node *p=new Node;

p->name=https://www.wendangku.net/doc/911737908.html,;

p->size=e.size;

p->start=e.start;

p->state=e.state;

if(L.head->next!=NULL)//这是个值得注意的地方，L.head->next==NULL，则没有指针L.head->next->pre，如果这里不加判断的话，会出错

L.head->next->pre=p;

p->next=L.head->next;

p->pre=L.head;

L.head->next=p;

//双向链表，插入一个新的元素，如果元素不是插入在链尾，则一共要修改四次指针}

void DlistDelete(Node *p,Node &e)//传递指针p，删除指针p指向的链表元素，用Node 型变量e记录该元素的相关数据

{

https://www.wendangku.net/doc/911737908.html,=p->name;

e.start=p->start;

e.size=p->size;

e.state=p->state;

p->pre->next=p->next;//这里曾写成=p->pre....

if(p->next!=NULL)

p->next->pre=p->pre;//这里曾写成p->next->pre=p，留意

delete(p); //删除一个元素修改一次或两次指针

}

//=======================

void Green()

{

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_GREEN);}

void Red()

{ SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_RED);}

void White()

{

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FORE GROUND_GREEN|FOREGROUND_BLUE);}

void Yellow()

{

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSIT Y|FOREGROUND_RED|FOREGROUND_GREEN);}

//=======================

void BestOrWorst()

{

arrangeStart(fre);//先按地址递增排序

if(fit==1)

arrangeSmaller(fre);//再按size递增排序，当两个空闲区的size一样时，由于先按地址递增排序了，所以还是地址低的在前。

if(fit==2)

arrangeBigger(fre);

Node e;

int flag=0;

Node *p=fre.head->next; /*p=fre.head->next，而这时fre是不可能为空的，因为在input()中加入了判断，如果输入了allocate的请求时，如果fre为空，则不会执行BestOrWorst()

故不用讨论fre是否为空的情况。也就是说，在进入BestOrWorst()的时候就已经确保了fre.head->next!=NULL, 同理，进入NextFit()的时候也保证了fre不为空*/

while(p!=NULL)

{ //遍历fre链表，当找到合适的空间之后就break if(p->size>=size)

{

flag=1;

break;//一定要break不然遇到两个size相同的空闲区就会出现两个都分配出去的状况

}

p=p->next;

}

if(flag==0)//在fre链表不空的前提下，如果flag==0则说明没有找到合适的空闲区间，所以分配失败

{

Red();

cout<<" No fitting block,failed to allocate memory!!"<

}

else

{

if(p->size-size<=minsize)

{

p->state=2;//============================================================== ============

DlistDelete(p,e);

https://www.wendangku.net/doc/911737908.html,=name; //这里注意了，不是https://www.wendangku.net/doc/911737908.html,=p->name因为fre链表中所有的name全部被我置为0，所以当把空闲区间分配给process的时候一定要记得把名字加进去

//其实state对操作什么的都完全没有影响，可改可不改，但为了规范，还是改一下吧

DlistInsert(pro,e);/*这里还有的一个问题是，例如，当输入的信息为name=1,size=48KB,而将要分配给它的空闲区间p->size=50，这样，当在表格中输出的时候

该process的信息是name=1,size=50KB，也就是说它的实际大小向p->size看齐了，但如果这里让e.size=size的话，输出来的信息确实跟原来输入

的时候对应了，但是当kill这个进程的时候，回收的空间并不等于之前分配出去时的空间，会导致memory发生变化 */

}

else

{

e.state=2;//=============================================================== ===========

https://www.wendangku.net/doc/911737908.html,=name; //同理

e.start=p->start;

// e.state=1;

e.size=size;

DlistInsert(pro,e);

p->start=p->start+size;//只要修改一下原来空闲区间的start和size即可

p->size=p->size-size;

p->state=2;//================================================== }

Yellow();

cout<<" Memory allocated"<

}

}

void NextFit()

{

arrangeStart(fre);

Node e;

Node *p=NULL;

//在这里不用讨论fre是否为空，因为只有fre不为空才会执行NextFit(),详情请看input()

int flag=0;

int length=getLength(fre);

if(temp==NULL) //if(length==1 || temp==NULL)当上一次进行分配的空间为链尾元素，则temp会指向NULL,这里加了个length==1，是因为

p=fre.head->next; //第一次执行NextFit()的时候，Node *temp=new Node,但是后来改进了，直接在声明temp的时候就让temp=NULL，这样一来，第一次执行NextFit()的时候也能通过

else

p=temp;

while(length>0)

{

if(p->size>=size)

{

flag=1;

break;

}

length--;

if(p->next==NULL)//这里也是值得注意的地方

p=fre.head->next;

else

p=p->next;

}

if(flag==0)//没有找到合适的空闲区间来进行分配

{

Red();

cout<<" No fitting block,failed to allocate memory!!"<

}

else

{

if(p->size-size<=minsize)

{

//因为reclaim操作并不会减少fre中的元素，只有可能增加而已，所以只要

在这个函数体内记录好temp就行。

//只有这一步操作才会减少fre中的元素，如果移出的元素是链尾元素(或者是fre中只有这个元素)，则temp==NULL，如果不是则temp=p->next

temp=p->next;//应该p指针发生改变之前就执行该操作，保证了temp=p->next，

DlistDelete(p,e);

https://www.wendangku.net/doc/911737908.html,=name;//注意了,因为fre里面所有的name都置零了，所以弹出来之后要修改一下再放入pro中

e.state=2;//=============================================================== =====

DlistInsert(pro,e);

}

else

{

https://www.wendangku.net/doc/911737908.html,=name;

e.start=p->start;

e.state=2;//=============================================================== =====

e.size=size;

DlistInsert(pro,e);

p->start=p->start+size;

p->size=p->size-size;

p->state=2;//============================================================== ======

temp=p->next;//这里注意了，这是跟BestOrWorst()不同。

}

Yellow();

cout<<" Memory allocated"<

}

}

void ReclaimMemory()

{

int flag=0;

Node e;

Node *t=NULL;

Node *s=pro.head->next;//在这里不讨论s==NULL的情况，因为我在后面intput()函数中有补充

while(s!=NULL)

{

if(s->name==name)

{

flag=1;

break;//一定要break

}

s=s->next;

}

if(flag==1)

{

arrangeStart(fre);

Node *p=fre.head->next;

if(p==NULL)

{

DlistDelete(s,e);

https://www.wendangku.net/doc/911737908.html,=0;

e.state=2;////============================================================= =======

DlistInsert(fre,e);

}

else

{

while(p!=NULL)//遍历fre链表

{

if(p->start+p->size==s->start && (p->next==NULL||p->next->start!=s->start+s->size))//当回收区与前一个空闲区邻接{

p->state=2;//============================================================== ============

p->size=p->size+s->size;

DlistDelete(s,e);//要记得删除pro链表中指针s对应的元素

break;//一定要留意，一旦找到了符合条件的元素，执行完之后一定要break

}

if(s->start+s->size==p->start && (p->pre==fre.head||p->pre->start+p->pre->size!=s->start))//当回收区与后一个空闲区邻接

{

p->state=2;//============================================================== ============

p->size=p->size+s->size;

p->start=s->start;

DlistDelete(s,e);

break;

}

if(p->start+p->size==s->start && p->next!=NULL && p->next->start==s->start+s->size)//回收区与前后空闲区邻接

{

t=p->next;

p->state=2;//============================================================== ============

p->size=p->size+s->size+t->size;

DlistDelete(t,e);

DlistDelete(s,e);

break;

}

p=p->next;

}

if(p==NULL)//遍历完fre链表之后发现没有一个元素满足上面三种情况，则在链首部插入该回收区

{

DlistDelete(s,e);

https://www.wendangku.net/doc/911737908.html,=0;

e.state=2;//=============================================================== ===========

DlistInsert(fre,e);

arrangeStart(fre); //由于是在链首插入回收区，所以还是排一下序

}

}

Yellow();

cout<<" Process "<

}

else

{

Red();

cout<<" No matching process!!"<

}

}

void output()

{

//每次执行完输入的请求操作之后两条链表中发生过变动的元素的state==2，output 的时候如果遇到state为2，则字体变色，并且输出完之后，fre中所有的state==0，pro 中所有的state==1

arrangeStart(pro);

if(fit==1)

arrangeSmaller(fre);

if(fit==2)

arrangeBigger(fre);

if(fit==3)

arrangeStart(fre);

Green();

cout<<"============================"<

cout<<" Process information: "<

cout<<" name start size "<

Node *p=pro.head->next;

if(p==NULL)

cout<<" NULL"<

while(p!=NULL)

{

if(p->state==2)//================================================== {

Yellow();

cout<name<start<size<

p->state=1;

}

else//==================================================

{

Green();

cout<name<start<size<

p->state=1;

}

p=p->next;

}

Green();//==================================================

cout<<"============================"<

cout<<" Free block information: "<

cout<<" name start size "<

Node *f=fre.head->next;

int i=1;

if(f==NULL)

cout<<" NULL"<

while(f!=NULL)

{

if(f->state==2)//================================================== {

Yellow();

cout<start<size<

f->state=0;

}

else//==================================================

{

Green();

cout<start<size<

f->state=0;

}

f=f->next;

i++;

}

Green();//==================================================

cout<<"============================"<

}

void input()

{

int num;

cout<<"Please input the memory size (0-1000) "<";

cin>>memory;

MemoryInit();//初始化两个链表

do{

White();

cout<<"Please input the simalating command about memory allocation"<

cout<<" [1]Create a process"<

[3]Exit"<";

cin>>num;//

int lenp=getLength(pro);//要放在这里

int lenf=getLength(fre);

//在这里加入了两个链表是否为空的判断，与我在上文所说的照应。

if(num==1)

{

if(lenf==0)

{

Red();

cout<<" Memory is full,failed to allocate memory!!"<

output();

}

else

{

cout<<"Please input process information"<";

cin>>name>>size;//

switch(fit)

{

case 1:

BestOrWorst();

output();

break;

case 2:

BestOrWorst();

output();

break;

case 3:

NextFit();

output();

break;

default:

Red();

cout<<" ERROR!! Please select(0-3)"<

break;

}

}

}

else if(num==2)

{

if(lenp==0)

{

Red();

cout<<" No process,failed to reclaim memory!!"<

output();

}

else

{

cout<<"Please input name:"<";

cin>>name;

ReclaimMemory();

output();

}

}

else if(num==3)

cout<<"========================================"<

else

{

Red();

cout<<" ERROR! Please selct (0-3) "<

}

}

while(num!=3);

}

int main()

{

do{

White();

cout<<"Please select the fitting algorithm"<

[2]Worst Fit"<

cout<<" [4]Exit"<";

cin>>fit;

switch(fit)

{

case 1:

input();

break;

case 2:

input();

break;

case 3:

input();

break;

case 4:

Red();

cout<<"================Exit!==================="<

break;

default:

Red();

cout<<" ERROR! Please selct (0-4) "<

break;

}

}

while(fit!=4);

return 0;

}

操作系统课程设计

课程设计报告 2015～2016学年第一学期 操作系统综合实践课程设计 实习类别课程设计 学生姓名李旋 专业软件工程 学号130521105 指导教师崔广才、祝勇 学院计算机科学技术学院 二〇一六年一月

- 1 -

- 2 -

一、概述 一个目录文件是由目录项组成的。每个目录项包含16B，一个辅存磁盘块(512B)包含32个目录项。在目录项中，第1、2字节为相应文件的外存i节点号，是该文件的内部标识；后14B为文件名，是该文件的外部标识。所以，文件目录项记录了文件内、外部标识的对照关系。根据文件名可以找到辅存i节点号，由此便得到该文件的所有者、存取权、文件数据的地址健在等信息。UNIX 的存储介质以512B为单位划分为块，从0开始直到最大容量并顺序加以编号就成了一个文件卷，也叫文件系统。UNIX中的文件系统磁盘存储区分配图如下： 本次课程设计是要实现一个简单的模拟Linux文件系统。我们在内存中开辟一个虚拟磁盘空间(20MB)作为文件存储器，并将该虚拟文件系统保存到磁盘上(以一个文件的形式)，以便下次可以再将它恢复到内存的虚拟磁盘空间中。文件存储空间的管理可采用位示图方法。 二、设计的基本概念和原理 2.1 设计任务 多用户、多级目录结构文件系统的设计与实现。可以实现下列几条命令login 用户登录 logout 退出当前用户 dir 列文件目录 creat 创建文件 delete 删除文件 open 打开文件 close 关闭文件 - 3 -

read 读文件 write 写文件 mkdir 创建目录 ch 改变文件目录 rd 删除目录树 format 格式化文件系统 Exit 退出文件系统 2.2设计要求 1) 多用户：usr1,usr2,usr3,……,usr8 (1-8个用户) 2) 多级目录：可有多级子目录； 3) 具有login (用户登录)4) 系统初始化（建文件卷、提供登录模块） 5) 文件的创建：create (用命令行来实现)6) 文件的打开：open 7) 文件的读：read8) 文件的写：write 9) 文件关闭：close10) 删除文件：delete 11) 创建目录（建立子目录）：mkdir12) 改变当前目录：cd 13) 列出文件目录：dir14) 退出：logout 新增加的功能： 15) 删除目录树：rd 16) 格式化文件系统：format 2.3算法的总体思想 - 4 -

动态规划实验报告

华东师范大学计算机科学技术系上机实践报告 一、 内容与设计思想 1．对于以下5 个矩阵： M 1: 2?3, M 2: 3?6, M 3: 6?4, M 4: 4?2, M 5: 2?7 , (a) 找出这5个矩阵相乘需要的最小数量乘法的次数。 (b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。 输入： 第一行为正整数N,表示有N 组测试数据； 每组测试数据的第一行为n,表示有n 个矩阵,2<=n<=50； 接下去的n 行,每行有两个整数x 和y,表示第ni 个矩阵是x*y 的。 输出： 对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。 我们保证输出的结果在2^64之内。 基本思想： 对于n 个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： 2．定义0/1/2背包问题为：}x p max{n 1i i i ∑=。限制条件为：c x w n 1i i i ≤∑=，且 n i 1},2,1,0{x i ≤≤∈。设f(i , y)表示剩余容量为y ，剩余物品为：i ，i+1，…，n 时的最优解的值。 1．）给出f(i , y)的递推表达式； 2．）请设计求解f(i , y)的算法，并实现你的算法； 3．）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。 输入： 第一行为一个正整数N ，表示有几组测试数据。 每组测试数据的第一行为两个整数n 和M ，0=-=∑-=

操作系统实验四实验报告动态分区分配算法

操作系统实验四 【实验题目】：动态分区分配算法 【实验学时】：4学时 【实验目的】 通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。 【实验内容及要求】 问题描述： 设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求： 1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。 2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。 3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m。

4）输出：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法，最终内存空闲分区的分配情况。 实现源代码： #include #include #include #include #define max 100 using namespace std; int work_num; int zone_num; struct Data{ int data; char name; }; Data *d=new Data[max]; struct Table{ int data; char array[max]; int length; };

操作系统课程设计文件系统管理)

操作系统课程设计Array文件系统管理 学院计算机学院 专业计算机科学与技术 班级 姓名 学号 2013年1月8日 广东工业大学计算机学院制 文件系统管理 一、实验目的 模拟文件系统的实现的基本功能，了解文件系统的基本结构和文件系统的管理方法看，加深了解文件系统的内部功能的实现。通过高级语言编写和实现一个简单的文件系统，模拟文件管理的工作过程，从而对各种文件操作系统命令的实质内容和执行过程有比较深入的了解。 二、实验内容和要求 编程模拟一个简单的文件系统，实现文件系统的管理和控制功能。在用户程序中通过使用文件系统提供的create，open，read，write，close，delete等文件命令，对文件进行操作。 以下报告主要包括： 1.可行性分析 2.需求分析 3.概要设计

4.详细设计 5.测试 6.总结 三、可行性分析 1、技术可行性 对于图形编程还不了解，但是经过本学期的三次实验的练习，可以设计好命令操作界面。利用大二期间学习的数据结构可以模拟出此课程设计的要求。 2、经济可行性 课程设计作为本课程的练习及进一步加深理解。与经济无关，可以不考虑。（零花费，零收益） 3.法律可行性 自己编写的程序，仅为练习，不作其他用途，与外界没什么联系，可行。 四、需求分析 编写程序实现文件系统，主要有以下几点要求： 1、实现无穷级目录管理及文件管理基本操作 2、实现共享“别名” 3、加快了文件检索 五、概要设计 为了克服单级目录所存在的缺点，可以为每一位用户建立一个单独的用户文件目录UFD（User File Directory）。这些文件目录可以具有相似的结构，它由用户所有文件的文件控制块组成。此外，在系统中再建立一个主文件目录MFD （Master File Directory）；在主文件目录中，每个用户目录文件都占有一个目

动态规划算法的应用实验报告

实验二动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 三、算法设计 void main() { 申明一个5*5的二维数组； for(int i=0;i<5;i++) { for(int j=0;j<=i;j++) { 输入数组元素p[i][j]; }

} for(int k=0;k<5;k++) { for(int w=0;w<=k;w++) { 输出数组元素p[k][w]; } } for(int a=4;a>0;a--) { for(int s=0;s<=a;s++) { if(p[a][s]大于p[a][s+1]) p[a-1][s]等于p[a-1][s]加p[a][s]; else p[a-1][s] 等于p[a-1][s] 加p[a][s+1]; } } 输出p[0][0] }

四.程序调试及运行结果分析 五.实验总结 虽然这个实验比较简单，但是通过这次实验使我更加了解的动态规划法的好处和、，在解决问题时要尝试使用动态规划，这样就有可能得到一种即简单复杂性有不高的算法。

操作系统实验_首次适应算法与循环首次适应算法

学号P7******* 专业计算机科学与技术姓名 实验日期2017.11.16 教师签字成绩 实验报告 【实验名称】首次适应算法和循环首次适应算法 【实验目的】 学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法。 【实验原理】 理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。 采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。 采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。 数据结构： 1、bool ROM[N]; //定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为1024 2、pcb num[20];//定义作业数组，最大支持20个作业 3、typedef struct Pcb //定义作业结构体，包括名称，开始时间，大小，是否执行状态 { char name[10]; int start; int size; int state=0; } pcb; typedef struct Free_rom //空闲区结构体

{ int num; int start; int end; int space; } Free_room; Free_rom free_rom[100];//设置空闲区数组为100个 主要函数 void init()；//初始化信息，包括初始化内存信息，和初始化作业队列 void insert_pcb1(pcb &a)；插入作业函数，首次适应算法，如果有适合的就插入，无合适输出‘插入失败’ void insert_pcb1(pcb &a)；插入作业函数，循环首次适应算法，如果有适合的就插入，无合适输出‘插入失败’ void Delete(pcb &a)//删除作业信息，包括修改内存状态修改作业状态并对作业进行初始化 void show();//显示信息 void find_free_rom() //寻找空闲区 算法流程图

操作系统课程设计-模拟文件系统

目录 第1章需求分析 (1) 第2章概要设计 (1) 2.1 系统的主要功能 (1) 2.2系统模块功能结构 (1) 2.3运行环境要求 (2) 2.4数据结构设计 (2) 第3章详细设计 (3) 3.1模块设计 (3) 3.2算法流程图 (3) 第4章系统源代码 (4) 第5章系统测试及调试 (4) 5.1运行结果及分析 (4) 5.2系统测试结论 (5) 第6章总结与体会 (6) 第7章参考文献 (6) 附录 (7)

第1章需求分析 通过模拟文件系统的实现，深入理解操作系统中文件系统的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法,更好地掌握操作系统的原理及实现方法,提高综合运用各专业课知识的能力；掌握操作系统结构、实现机理和各种典型算法，系统地了解操作系统的设计和实现思路，并了解操作系统的发展动向和趋势。 模拟二级文件管理系统的课程设计目的是通过研究Linux的文件系统结构，模拟设计一个简单的二级文件系统，第一级为主目录文件，第二级为用户文件。 第2章概要设计 2.1 系统的主要功能 1) 系统运行时根据输入的用户数目创建主目录 2) 能够实现下列命令： Login 用户登录 Create 建立文件 Read 读取文件 Write写入文件 Delete 删除文件 Mkdir 建立目录

Cd 切换目录 Logout 退出登录 2.2系统模块功能结构 2.3运行环境要求 操作系统windows xp ，开发工具vc++6.0 2.4数据结构设计 用户结构：账号与密码结构 typedef struct users { char name[8]; char pwd[10]; }users;

操作系统课程设计报告

上海电力学院 计算机操作系统原理 课程设计报告 题目名称：编写程序模拟虚拟存储器管理 姓名：杜志豪.学号： 班级： 2012053班 . 同组姓名：孙嘉轶 课程设计时间：—— 评语： 成绩： 目录 一、设计内容及要求 (4) 1. 1 设计题目 (4) 1．2 使用算法分析： (4)

1． FIFO算法（先进先出淘汰算法） (4) 1． LRU算法（最久未使用淘汰算法） (5) 1. OPT算法（最佳淘汰算法） (5) 分工情况 (5) 二、详细设计 (6) 原理概述 (6) 主要数据结构(主要代码) (6) 算法流程图 (9) 主流程图 (9) Optimal算法流程图 (10) FIFO算法流程图 (10) LRU算法流程图 (11) ．1源程序文件名 (11) . 2执行文件名 (11) 三、实验结果与分析 (11) Optimal页面置换算法结果与分析 (11) FIFO页面置换算法结果与分析 (16) LRU页面置换算法结果与分析 (20) 四、设计创新点 (24) 五、设计与总结 (27)

六、代码附录 (27) 课程设计题目 一、设计内容及要求 编写程序模拟虚拟存储器管理。假设以M页的进程分配了N

块内存（N

动态规划算法实验

一、实验目的 (2) 二、实验内容 (2) 三、实验步骤 (3) 四.程序调试及运行结果分析 (5) 附录：程序清单（程序过长，可附主要部分） (7)

实验四动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 题目二：最长单调递增子序列问题(课本184页例28) 设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 若存在i1

题目三 0-1背包问题 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，，物品的个数n。接下来的n 行表示n个物品的重量和价值。输出为最大的总价值。 输入样例： 20 3 11 9 9 10 7 5 输出样例 19 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。

采用首次适应算法的动态分区分配模拟课程设计实验报告

】 1 需求分析 1）本程序要求实现对内存的动态分配与回收的模拟，同时，在内存的分配时还必须使用首次适应算法，最后，还要显示内存块分配和回收后空闲内存分区链的情况。 2）要实现对作业的内存分配，首先要有一个对作业进行创建和分配内存的模块，其中，该模块在分配内存时要使用首次适应算法；要实现对内存的回收，要有一个内存回收的模块，其中，该模块在回收内存时要考虑内存回收的四种情况；最后，还要有一个能显示内存空闲分区链的情况的模块。 2 概要设计 1）首次适应算法的结构如图1： 图1 首次适应算法的结构图 》

2）数据结构： struct Fq { int size,o,no; Fq *before,*next; }; 其中，Fq表示结构体的名字（类型），size表示分区的可用空间大小，o表示该分区的状态（是否已分配），no表示该分区中的作业标志，*before表示该结点的向前指针，*next表示该结点的向后指针。 3）各种函数说明： \ void alloc(int b,int no,Fq *p)； 对作业no进行内存分配的功能函数；其中，参数b表示需求的内存大小，参数no表示作业的编号，参数*p表示空闲分区链的第一个非空结点的指针； void free(Fq *c)； 将地址为c的分区的内存回收；其中，参数*c表示要回收内存的结点； void create(Fq *head)； 创建新作业的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数alloc（）使用； void cha(Fq *head)； 查看内存中的空闲分区链的子函数；其中，参数*head表示空闲分区链的链首指针； # void hui(Fq *head)； 回收内存的子函数；其中，参数*head表示空闲分区链的链首指针；要配合函数free（）使用； 3 运行环境 1）操作系统: Windows XP ( 32位 / DirectX 11 ) 2）电脑: X86 兼容台式电脑

【精选】操作系统课程设计(文件系统管理)文件

评定等级 操作系统课程设计 文件系统管理 学院计算机学院 专业计算机科学与技术 班级 姓名 学号 2013年1月8日 广东工业大学计算机学院制

文件系统管理 一、实验目的 模拟文件系统的实现的基本功能，了解文件系统的基本结构和文件系统的管理方法看， 加深了解文件系统的内部功能的实现。通过高级语言编写和实现一个简单的文件系统，模拟文件管理的工作过程，从而对各种文件操作系统命令的实质内容和执行过程有比较深入的了 解。 二、实验内容和要求 编程模拟一个简单的文件系统，实现文件系统的管理和控制功能。在用户程序中通过使用文件系统提供的create，open，read，write，close，delete 等文件命令，对文件进行操作。以下报告主要包括： 1.可行性分析 2.需求分析 3.概要设计 4.详细设计 5.测试 6.总结 三、可行性分析 1、技术可行性 对于图形编程还不了解，但是经过本学期的三次实验的练习，可以设计好命令操作界面。利用大二期间学习的数据结构可以模拟出此课程设计的要求。 2、经济可行性 课程设计作为本课程的练习及进一步加深理解。与经济无关，可以不考虑。（零花费，零收益） 3.法律可行性 自己编写的程序，仅为练习，不作其他用途，与外界没什么联系，可行。 四、需求分析 编写程序实现文件系统，主要有以下几点要求： 1、实现无穷级目录管理及文件管理基本操作 2、实现共享“别名” 3、加快了文件检索 五、概要设计 为了克服单级目录所存在的缺点，可以为每一位用户建立一个单独的用户文件目录 UFD （User File Directory ）。这些文件目录可以具有相似的结构，它由用户所有文件的文件 控制块组成。此外，在系统中再建立一个主文件目录MFD （Master File Directory ）；在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目 录的指针。

动态规划算法分析实验报告

四、实验结果显示 五、实验总结 通过理解最优子结构的性质和子问题重叠性质，在VC++6.0环境下实现动态规划算法。动态规划算法是由单阶段的决策最优逐步转化为多阶段的决策最优，最后构造一个最优解。经过反复的调试操作，程序运行才得出结果。

六、附录 A #include #include #include #include #define MAX 100 #define n 12 #define k 5 int c[n][n]; void init(int cost[]) { int i,j; for(i=0;i<13;i++) { for(j=0;j<13;j++) { c[i][j]=MAX; } } c[1][2]=9; c[1][3]=7;c[1][4]=3; c[1][5]=2; c[2][6]=4; c[2][7]=2; c[2][8]=1; c[3][6]=2; c[3][7]=7; c[4][8]=11; c[5][7]=11;c[5][8]=8; c[6][9]=6; c[6][10]=5; c[7][9]=4; c[7][10]=3; c[8][10]=5;c[8][11]=6; c[9][12]=4; c[10][12]=2; c[11][12]=5; } void fgraph(int cost[],int path[],int d[]) { int r,j,temp,min; for(j=0;j<=n;j++) cost[j]=0; for(j=n-1;j>=1;j--) { temp=0; min=c[j][temp]+cost[temp]; for(r=0;r<=n;r++) { if(c[j][r]!=MAX)

计算机操作系统内存分配实验报告记录

计算机操作系统内存分配实验报告记录

————————————————————————————————作者：————————————————————————————————日期：

一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。 实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。此时，作业4进入系统，要求分配200KB内存。作业3、1运行完毕，释放所占内存。此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。 设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明

操作系统课程设计报告

; 一、概述 课程设计目的、意义： 课程设计目的使学生熟悉文件管理系统的设计方法；加深对所学各种文件操作的了解及其操作方法的特点。通过模拟文件系统的实现，深入理解操作系统中文件系统的理论知识, 加深对教材中的重要算法的理解。同时通过编程实现这些算法,更好地掌握操作系统的原理及实现方法,提高综合运用各专业课知识的能力。 主要任务： 模拟文件系统设计是设计和实现一个简单的文件系统。内容包括： 1.建立文件存储介质的管理机制 2.建立目录（采用一级目录结构） 3.文件系统功能（显示目录、创建、删除、打开、关闭、读、写） ~ 4.文件操作接口（显示目录、创建、删除、打开、关闭、读、写） 二、系统设计 课程设计的系统设计： 本系统模拟一个文件管理系统，要完成对文件的基本操作，文件的基本操作有文件、文件夹的打开、新建、删除和读取写入文件，创建更改目录，列出目录内容等信息。系统建立了文件目录树，存储文件系统中的所有文

件。对于用户名下的文件，用文件目录树的分枝来存贮。采用命令行操作界面很直观，也方便用户进行操作，用户只要按照操作界面所显示的命令来操作就行了。 整体设计框架： 系统初始化界面是由创建用户存储空间，管理文件，退出系统三个模块组成。用户创建由创建用户存储空间，进入目录，删除用户存储空间，显示所有用户存储空间，等模块组成。然后各个模块再由一些小模块组成。其中创建文件，打开关闭文件，读写文件等文件操作模块包括在进入目录模块里面。 三、系统实现 课程设计主要内容的实现程序代码： 《 #include <> #include <> #include <> typedef struct file{ char name[10]; struct file *next; }File; typedef struct content{ ! char name[10]; File *file;

计算机操作系统内存分配实验报告

一、实验目的 熟悉主存的分配与回收。理解在不同的存储管理方式下.如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。 二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配.就是解决多道作业或多进程如何共享主存空间的问题。所谓回收.就是当作业运行完成时将作业或进程所占的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区.使分区大小正好适合作业的需求.并且分区个数是可以调整的。当要装入一个作业时.根据作业需要的主存量查看是否有足够的空闲空间.若有.则按需要量分割一个分区分配给该作业；若无.则作业不能装入.作业等待。随着作业的装入、完成.主存空间被分成许多大大小小的分区.有的分区被作业占用.而有的分区是空闲的。 实验要求使用可变分区存储管理方式.分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行.分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。同时.要求设计一个实用友好的用户界面.并显示分配与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料 实验环境 硬件环境：PC或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析 某系统采用可变分区存储管理.在系统运行当然开始.假设初始状态下.可用的内存空间为640KB.存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。 （作业1 申请130KB、作业2 申请60KB、作业3 申请100KB 、作业2 释放 60KB 、作业4 申请 200KB、作业3释放100KB、作业1 释放130KB 、作业5申请140KB 、作业6申请60KB 、作业7申请50KB） 当作业1进入内存后.分给作业1（130KB）.随着作业1、2、3的进入.分别分配60KB、100KB.经过一段时间的运行后.作业2运行完毕.释放所占内存。此时.作业4进入系统.要求分配200KB内存。作业3、1运行完毕.释放所占内存。此时又有作业5申请140KB.作业6申请60KB.作业7申请50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理.使用空闲分区链实现主存分配和回收。 空闲分区链：使用链指针把所有的空闲分区链成一条链.为了实现对空闲分区的分配和链接.在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针.由状态位指示该分区是否分配出去了；同时.在分区尾部还设置有一后向指针.用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间.当该分区分配出去后.状态位就由“0”置为“1”。 设置一个内存空闲分区链.内存空间分区通过空闲分区链来管理.在进行内存分配时.系统优先使用空闲低端的空间。 设计一个空闲分区说明链.设计一个某时刻主存空间占用情况表.作为主存当前使用基础。初始化空间区和已分配区说明链的值.设计作业申请队列以及作业完成后释放顺序.实现主存的分配和回收。要求每次分配和回收后显示出空闲内存分区链的情况。把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。

操作系统课程设计二级文件系统

操作系统课程设计报告 专业：计算机信息处理 学号：09103408 姓名：纪旻材 提交日期：2011-12-28

【设计目的】 1. 课程设计目的是通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能和内部实现。 2. 结合数据结构、程序设计、计算机原理等课程的知识，设计一个二级文件系统，进一步理解操作系统。 3. 通过对实际问题的分析、设计、编程实现，提高学生实际应用、编程的能力 【设计内容】 1、delete 删除文件 2、open 打开文件 3、close 关闭文件 4、write 写文件 【实验环境】 Windows7系统

Visual studio 2010 【相关知识综述】 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 首先应确定文件系统的数据结构：主目录、子目录及活动文件等。主目录和子目录都以文件的形式存放于磁盘，这样便于查找和修改。用户创建的文件，可以编号存储于磁盘上。如：file0,file1,file2…并以编号作为物理地址，在目录中进行登记。 【设计思路】 1 主要数据结构 #define MAXNAME 25 /*the largest length of mfdname,ufdname,filename*/ #define MAXCHILD 50 /*the largest child每个用户名下最多有50个文件*/ #define MAX (MAXCHILD*MAXCHILD) /*the size of fpaddrno*/ typedef struct/*the structure of OSFILE定义主文件*/

操作系统(一个小型操作系统的设计与实现)课程设计

南通大学计算机科学与技术学院操作系统课程设计报告 专业： 学生姓名： 学号： 时间：

操作系统模拟算法课程设计报告 设计要求 将本学期三次的实验集成实现： A.处理机管理； B.存储器管理； C.虚拟存储器的缺页调度。 设计流程图 主流程图 开始的图形界面 处理机管理存储器管理缺页调度 先来先服务时 间 片 轮 转 首 次 适 应 法 最 佳 适 应 法 先 进 先 出 L R U 算 法

A.处理机调度 1)先来先服务FCFS N Y 先来先服务算法流程 开始 初始化进程控制块，让进程控制块按进程到达先后顺序让进程排队 调度数组中首个进程，并让数组中的下一位移到首位 计算并打印进程的完成时刻、周转时间、带权周转时间 其中：周转时间 = 完成时间 - 到达时间 带权周转时间=周转时间/服务时间 更改计时器的当前时间,即下一刻进程的开始时间 当前时间=前一进程的完成时间+其服务时间 数组为空 结束

2)时间片轮转法 开始 输入进程总数 指针所指的进程是 否结束 输入各进程信息 输出为就绪状态的进程的信息 更改正在运行的进程的已运行时间 跳过已结束的程序 结束 N 指向下一个进程 Y 如果存在下一个进程的话 Y N 输出此时为就绪状态的进程的信息 时间片轮转算法流程图

B.存储器管理(可变式分区管理） 1)首次适应法 分配流程图 申请xkb内存 由链头找到第一个空闲区 分区大小≥xkb？ 大于 分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb 将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针 等于 小于延链查找下 一个空闲区 到链尾 了？ 作业等待 返回是 否 登记已分配表 返回分配给进程的内存首地址 开始

南京邮电大学算法设计实验报告——动态规划法

实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++

三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。

操作系统课程设计(文件系统)

操作系统课程设计 班级： 姓名： 学号： 使用语言：C++ 指导老师： 学院：

一、系统要求 1、实验目的 通过一个简单多用户文件系统的设计，加深理解文件系统的内部功能及内部实现。 2、实验内容 为linux系统设计一个简单的二级文件系统。要求做到以下几点： （1）可以实现下列几条命令（至少4条）； login 用户登陆 dir 列文件目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件 （2）列目录时要列出文件名、物理地址、保护码和文件长度； （3）源文件可以进行读写保护。 二、系统分析 1、设计思想 本文件为二级文件系统，即要实现对文件的增删改查，同时又具备登陆系统、注册用户的功能，各个用户之间的文件系统互不干扰。 本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。 系统采用结构体来存储用户、文件目录、文件数据内容： 0 48*5 48*5+44*50 48*5+44*50+264*200 每个分区都是由结构体组成，每个个去的结构体的个数由格式化系统是决定。整个系统的编码构成主要分为：

Allstruct.h 定义了每个分区的结构体； Mysys.h 声明了对系统操作的各种方法； Myuserfile.h 声明了对文件操作的各种方法； Mymain.cpp 整个系统的主函数，操作入口； Mysys.cpp 包含了mysys.h，实现了操作系统的各种方法；Myuserfile.cpp 包含了myuserfile.h，实现了操作文件的各种方法； 2、主要数据结构 Allstruct.h文件的内容： struct s_user //用户区结构体 { long isuse; //是否使用 char name[20]; //用户名 char psd[20]; //密码 long address; //目录地址 }; struct s_list //目录结构体 { long isuse; //是否使用 char name[20]; //文件名字 long myaddress; //本条目录地址 long pointaddress; //指向的文件的地址 long isfile; //是否锁定 long pointsize; //目标文件的大小 long nextaddress; //下条目录的地址 }; struct s_file //文件结构体 { long isuse; //是否使用 char content[256]; //文件内容 long next; //下个文件块地址 };

算法设计与分析实验报告

本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日

实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011

010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计：