OS实验一 (软件) 2010
模拟进程队列的管理（出入队）(红色字体为再思考修改处)
操作系统实验一 实验题
（1）模拟双向链接队列的出入队
（2）要求：写出算法思想（程序流程图或自然语言描述） （3）提交形式：以学号+姓名创建一个文件夹，里面必须包含(源程序.CPP、可执行程序.exe、
算法思想文档.doc)
(一)分析题意得模型 进程1 进程2 进程5 … 0 0 双向链接： (队首前向指针为0；队尾后向指针为0) …
可将其转换为： front rear head 2 参考：数据结构书p61的链式队列 3 图1 1 1 而后，细想，这里设front和rear没有很大作用（当时觉得毕竟它不是真的链式队列，设这样的头，没必要，过后细看老师给出的删除算法，再看图1中的头结点，觉得头中的front,rear可做标记，故图2不太切合题意，不妥。故采取图1）故可简化为（不带头结点的双链表）： head 1 2 3 图2
（二）写主要算法 双链表置空init(), 创建creat(), 在尾插入append（）， 删除dele(), 输出print() 写入头文件为“dlnkqueue.h” 可参考：数据结构书P61 （三）调试运行（多种情况都要运行）
OS实验一 （软件0967020050）2010
OS实验一 (软件) 2010
（四）不足体会 一开始本来想输入字符， 比如，1.但是总是在一些方面不怎么会处理，运行不出来。 在输入或输出中稍微改动下，把%d改为%c等，可总是运行有些小错误。最后只 好改用输入常用的数字。 所以，应再好好花时间思考用字符要注意一些的问题。这也突显了我对字符的掌 握不是很熟练。 .一开始对题意分析不清，对应转化成的数据模型没把握好，导致重写算法，又得2 修改。
源代码为：
/******创建双向链表模拟进程队列管理（出入队）（有前后指针之分的带头结点），放在文件dlnkqueue.h 中*******/
typedef int datatype; typedef struct dlink_node { datatype info; struct dlink_node *llink,*rlink; }dnode;
typedef struct//封装带头结点前后指针 { dnode *front,*rear; }queue;
/********双向链表置空**********/
OS实验一 （软件0967020050）2010
OS实验一 (软件) 2010
queue *init() { queue *head; head=(queue*)malloc(sizeof(queue)); head->front=NULL; head->rear=NULL; return head; }
/*******输出双向链表元素**********/ void print(queue *head) { dnode *p; p=head->front; if(!p)printf(\"进程队列为空!\\n\"); else { printf(\"进程队列为:\\n\"); while(p) { printf(\"%d \ } } }
/*********查找元素X是否存在*********/ dnode *find(queue *head,datatype x) {
dnode *p=head->front; while(p&&p->info!=x) p=p->rlink; if(!p)return NULL; else return p; }
/***********在队尾插入**********/ queue *append(queue *head,datatype x) { dnode *p,*q; p=(dnode*)malloc(sizeof(dnode)); p->info=x; if(!head->front)//原进程中队列中无进程//
OS实验一 0967020050）2010
（软件OS实验一 (软件) 2010
{ head->front=head->rear=p; p->llink=NULL; p->rlink=NULL; } else//原进程队列中有进程// { q=head->front; while(q->rlink) q=q->rlink; p->rlink=q->rlink; p->llink=q; q->rlink=p; head->rear=p; } return head; }
/*********删除X********/
queue *dele(queue *head,datatype x) { dnode *q; q=find(head,x); if(!q) {printf(\"该进程%d找不到,无法出队!\\n\ else { //队首出队// if(q->llink==NULL) { head->front=q->rlink; q->rlink->llink=NULL; } //队尾出队//
else if(q->rlink==NULL) { head->rear=q->llink; q->llink->rlink=NULL; }
OS实验一 （软件0967020050）2010
OS实验一 (软件) 2010
//队中出队// else { q->llink->rlink=q->rlink; q->rlink->llink=q->llink; } free(q);return head; } }
/********创建输入双向链表元素*********/ queue *creat(queue *head) { datatype x; scanf(\"%d\ while(x!=-999) { head=append(head,x); scanf(\"%d\ } return head; }
/******模拟进程队列的管理（出入队）（带前后指针的头结点）（双向链表）*****/
#include #include #include\"dlnkqueue.h\"void main() {
queue *head;dnode *p,*q; int i,j;
head=init(); printf(\"创建一入队进程（以数字-999结束）:\\n\"); head=creat(head); printf(\"\\n请输入要入队的一进程:\\n\"); scanf(\"%d\ p=find(head,i); if(p) printf(\"该进程%d已存在，无法入队!\\n\ else
OS实验一 （软件0967020050）2010
OS实验一 (软件) 2010
{ head=append(head,i); printf(\"入队后:\\n\"); print(head);
}
printf(\"\\n\\n请输入要出队的一进程:\\n\"); scanf(\"%d\ q=find(head,j); if(!q) printf(\"该进程%d不存在，无法出队!\\n\ else { head=dele(head,j); printf(\"出队后:\\n\"); print(head); printf(\"\\n\"); }
}
OS实验一 0967020050）2010
（软件
