2、词法分析器的输入是源程序的字符流，输出孝枣圆是词法记号流。
3、等价
4、（a|b）*(aa|bb)(a|b)*
排序算法全集【附C++代码】排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所拍李歼谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N＊N)（因为没有使用word，所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。
现在，让我们开始吧：
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有扰纤涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这袭冲是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include ＜iostream.h＞
void BubbleSort(int＊ pData，int Count)
{
int iTemp
for(int i＝1i＜Counti++)
{
for(int j＝Count-1j＞＝ij--)
{
if(pData[j]＜pData[j-1])
{
iTemp ＝ pData[j-1]
pData[j-1] ＝ pData[j]
pData[j] ＝ iTemp
}
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
BubbleSort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
倒序(最糟情况)
第一轮：10，9，8，7-＞10，9，7，8-＞10，7，9，8-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，10，8，9-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9-＞8，10，7，9-＞8，7，10，9-＞7，8，10，9(交换2次)
第二轮：7，8，10，9-＞7，8，10，9-＞7，8，10，9(交换0次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，
显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。
写成公式就是1/2＊(n-1)＊n。
现在注意，我们给出O方法的定义：
若存在一常量K和起点n0，使当n＞＝n0时，有f(n)＜＝K＊g(n)，则f(n) ＝ O(g(n))。（呵呵，不要说没
学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看1/2＊(n-1)＊n，当K＝1/2，n0＝1，g(n)＝n＊n时，1/2＊(n-1)＊n＜＝1/2＊n＊n＝K＊g(n)。所以f(n)
＝O(g(n))＝O(n＊n)。所以我们程序循环的复杂度为O(n＊n)。
再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的
有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），
复杂度为O(n＊n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因，我们通常都是通过循环次数来对比算法。
2.交换法：
交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include ＜iostream.h＞
void ExchangeSort(int＊ pData，int Count)
{
int iTemp
for(int i＝0i＜Count-1i++)
{
for(int j＝i+1j＜Countj++)
{
if(pData[j]＜pData)
{
iTemp ＝ pData
pData ＝ pData[j]
pData[j] ＝ iTemp
}
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
ExchangeSort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7-＞8，10，9，7-＞7，10，9，8(交换3次)
第二轮：7，10，9，8-＞7，9，10，8-＞7，8，10，9(交换2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：6次
其他：
第一轮：8，10，7，9-＞8，10，7，9-＞7，10，8，9-＞7，10，8，9(交换1次)
第二轮：7，10，8，9-＞7，8，10，9-＞7，8，10，9(交换1次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2＊(n-1)＊n，所以算法的复杂度仍然是O(n＊n)。由于我们无法给出所有的情况，所以
只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。
3.选择法：
现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中
选择最小的与第二个交换，这样往复下去。
#include ＜iostream.h＞
void SelectSort(int＊ pData，int Count)
{
int iTemp
int iPos
for(int i＝0i＜Count-1i++)
{
iTemp ＝ pData
iPos ＝ i
for(int j＝i+1j＜Countj++)
{
if(pData[j]＜iTemp)
{
iTemp ＝ pData[j]
iPos ＝ j
}
}
pData[iPos] ＝ pData
pData ＝ iTemp
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
SelectSort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
倒序(最糟情况)
第一轮：10，9，8，7-＞(iTemp＝9)10，9，8，7-＞(iTemp＝8)10，9，8，7-＞(iTemp＝7)7，9，8，10(交换1次)
第二轮：7，9，8，10-＞7，9，8，10(iTemp＝8)-＞(iTemp＝8)7，8，9，10(交换1次)
第一轮：7，8，9，10-＞(iTemp＝9)7，8，9，10(交换0次)
循环次数：6次
交换次数：2次
其他：
第一轮：8，10，7，9-＞(iTemp＝8)8，10，7，9-＞(iTemp＝7)8，10，7，9-＞(iTemp＝7)7，10，8，9(交换1次)
第二轮：7，10，8，9-＞(iTemp＝8)7，10，8，9-＞(iTemp＝8)7，8，10，9(交换1次)
第一轮：7，8，10，9-＞(iTemp＝9)7，8，9，10(交换1次)
循环次数：6次
交换次数：3次
遗憾的是算法需要的循环次数依然是1/2＊(n-1)＊n。所以算法复杂度为O(n＊n)。
我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)＜＝n
所以我们有f(n)＝O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。
4.插入法：
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include ＜iostream.h＞
void InsertSort(int＊ pData，int Count)
{
int iTemp
int iPos
for(int i＝1i＜Counti++)
{
iTemp ＝ pData
iPos ＝ i-1
while((iPos＞＝0) &&(iTemp＜pData[iPos]))
{
pData[iPos+1] ＝ pData[iPos]
iPos--
}
pData[iPos+1] ＝ iTemp
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
InsertSort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
倒序(最糟情况)
第一轮：10，9，8，7-＞9，10，8，7(交换1次)(循环1次)
第二轮：9，10，8，7-＞8，9，10，7(交换1次)(循环2次)
第一轮：8，9，10，7-＞7，8，9，10(交换1次)(循环3次)
循环次数：6次
交换次数：3次
其他：
第一轮：8，10，7，9-＞8，10，7，9(交换0次)(循环1次)
第二轮：8，10，7，9-＞7，8，10，9(交换1次)(循环2次)
第一轮：7，8，10，9-＞7，8，9，10(交换1次)(循环1次)
循环次数：4次
交换次数：2次
上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，
因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)＜＝
1/2＊n＊(n-1)＜＝1/2＊n＊n。所以其复杂度仍为O(n＊n)（这里说明一下，其实如果不是为了展示这些简单
排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似
选择法），但我们每次要进行与内层循环相同次数的‘＝’ *** 作。正常的一次交换我们需要三次‘＝’
而这里显然多了一些，所以我们浪费了时间。
最终，我个人认为，在简单排序算法中，选择法是最好的。
二、高级排序算法：
高级排序算法中我们将只介绍这一种，同时也是目前我所知道（我看过的资料中）的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值，然后
把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使
用这个过程（最容易的方法——递归）。
1.快速排序：
#include ＜iostream.h＞
void run(int＊ pData，int left，int right)
{
int i，j
int middle，iTemp
i ＝ left
j ＝ right
middle ＝ pData[(left+right)/2]//求中间值
do{
while((pData＜middle) &&(i＜right))//从左扫描大于中值的数
i++
while((pData[j]＞middle) &&(j＞left))//从右扫描大于中值的数
j--
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData
pData ＝ pData[j]
pData[j] ＝ iTemp
i++
j--
}
}while(i＜＝j)//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j)
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right)
}
void QuickSort(int＊ pData，int Count)
{
run(pData，0，Count-1)
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
QuickSort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k＝log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2＊(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n＊(n/n) ＝ n+n+n+...+n＝k＊n＝log2(n)＊n
所以算法复杂度为O(log2(n)＊n)
其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变
成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？？呵呵，你完全
不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。
如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)＊n)算法，但是通常情况下速度要慢
于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include ＜iostream.h＞
void Bubble2Sort(int＊ pData，int Count)
{
int iTemp
int left ＝ 1
int right ＝Count -1
int t
do
{
//正向的部分
for(int i＝righti＞＝lefti--)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData
pData ＝ pData[i-1]
pData[i-1] ＝ iTemp
t ＝ i
}
}
left ＝ t+1
//反向的部分
for(i＝lefti＜right+1i++)
{
if(pData＜pData[i-1])
{
iTemp ＝ pData
pData ＝ pData[i-1]
pData[i-1] ＝ iTemp
t ＝ i
}
}
right ＝ t-1
}while(left＜＝right)
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4}
Bubble2Sort(data，7)
for (int i＝0i＜7i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include ＜iostream.h＞
void ShellSort(int＊ pData，int Count)
{
int step[4]
step[0] ＝ 9
step[1] ＝ 5
step[2] ＝ 3
step[3] ＝ 1
int iTemp
int k，s，w
for(int i＝0i＜4i++)
{
k ＝ step
s ＝ -k
for(int j＝kj＜Countj++)
{
iTemp ＝ pData[j]
w ＝ j-k//求上step个元素的下标
if(s ＝＝0)
{
s ＝ -k
s++
pData[s] ＝ iTemp
}
while((iTemp＜pData[w]) &&(w＞＝0) &&(w＜＝Count))
{
pData[w+k] ＝ pData[w]
w ＝ w-k
}
pData[w+k] ＝ iTemp
}
}
}
void main()
{
int data[] ＝ {10，9，8，7，6，5，4，3，2，1，-10，-1}
ShellSort(data，12)
for (int i＝0i＜12i++)
cout＜＜data＜＜” ”
cout＜＜”＼n”
}
呵呵，程序看起来有些头疼。不过也不是很难，把s＝＝0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。
四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index，char＊ strData)
CMyData()
virtual ~CMyData()
int m_iIndex
int GetDataSize(){ return m_iDataSize}
const char＊ GetData(){ return m_strDatamember}
//这里重载了 *** 作符：
CMyData&operator ＝(CMyData &SrcData)
bool operator ＜(CMyData&data )
bool operator ＞(CMyData&data )
private:
char＊ m_strDatamember
int m_iDataSize
}
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember !＝ NULL)
delete[] m_strDatamember
m_strDatamember ＝ NULL
}
CMyData::CMyData(int Index，char＊ strData):
m_iIndex(Index)，
m_iDataSize(0)，
m_strDatamember(NULL)
{
m_iDataSize ＝ strlen(strData)
m_strDatamember ＝ new char[m_iDataSize+1]
strcpy(m_strDatamember，strData)
}
CMyData&CMyData::operator ＝(CMyData &SrcData)
{
m_iIndex ＝ SrcData.m_iIndex
m_iDataSize ＝ SrcData.GetDataSize()
m_strDatamember ＝ new char[m_iDataSize+1]
strcpy(m_strDatamember，SrcData.GetData())
return ＊this
}
bool CMyData::operator ＜(CMyData&data )
{
return m_iIndex＜data.m_iIndex
}
bool CMyData::operator ＞(CMyData&data )
{
return m_iIndex＞data.m_iIndex
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include ＜iostream.h＞
#include ”MyData.h”
template ＜class T＞
void run(T＊ pData，int left，int right)
{
int i，j
T middle，iTemp
i ＝ left
j ＝ right
//下面的比较都调用我们重载的 *** 作符函数
middle ＝ pData[(left+right)/2]//求中间值
do{
while((pData＜middle) &&(i＜right))//从左扫描大于中值的数
i++
while((pData[j]＞middle) &&(j＞left))//从右扫描大于中值的数
j--
if(i＜＝j)//找到了一对值
{
//交换
iTemp ＝ pData
pData ＝ pData[j]
pData[j] ＝ iTemp
i++
j--
}
}while(i＜＝j)//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left＜j)，递归左半边
if(left＜j)
run(pData，left，j)
//当右边部分有值(right＞i)，递归右半边
if(right＞i)
run(pData，i，right)
}
template ＜class T＞
void QuickSort(T＊ pData，int Count)
{
run(pData，0，Count-1)
}
void main()
{
CMyData data[] ＝ {
CMyData(8，”xulion”)，
CMyData(7，”sanzoo”)，
CMyData(6，”wangjun”)，
CMyData(5，”VCKBASE”)，
CMyData(4，”jacky2000”)，
CMyData(3，”cwally”)，
CMyData(2，”VCUSER”)，
CMyData(1，”isdong”)
}
QuickSort(data，8)
for (int i＝0i＜8i++)
cout＜＜data.m_iIndex＜＜” ”＜＜data.GetData()＜＜”＼n”
cout＜＜”＼n”
一、目的和要求进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深竖咐理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。
二、实验内容
1.设计进程控制块PCB的结构，通常应包括如下信息：
进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时带纤模间、进程到完成还需要的时间、进程的状态、当前队列指针等。
2.编写两种调度蠢缓算法程序：
优先数调度算法程序
循环轮转调度算法程序
3.按要求输出结果。
三、提示和说明
分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（RUN）、就绪状态（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结构和其他有关变量。
（四）运行和显示
程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIME值。
每次显示结果均为如下5个字段：
name cputime needtime priority state
注：
1．在state字段中，"R"代表执行态，"W"代表就绪（等待）态，"F"代表完成态。
2．应先显示"R"态的，再显示"W"态的，再显示"F"态的。
3．在"W"态中，以优先数高低或轮转顺序排队；在"F"态中，以完成先后顺序排队。
view plaincopy to clipboardprint?
/*
*** 作系统实验之时间片轮转算法和优先级调度算法
By Visual C++ 6.0
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
char name[20] /*进程的名字*/
int prio/*进程的优先级*/
int round/*分配CPU的时间片*/
int cputime /*CPU执行时间*/
int needtime /*进程执行所需要的时间*/
char state/*进程的状态，W——就绪态，R——执行态，F——完成态*/
int count/*记录执行的次数*/
struct node *next /*链表指针*/
}PCB
PCB *ready=NULL,*run=NULL,*finish=NULL/*定义三个队列，就绪队列，执行队列和完成队列*/
int num
void GetFirst() /*从就绪队列取得第一个节点*/
void Output()/*输出队列信息*/
void InsertPrio(PCB *in) /*创建优先级队列，规定优先数越小，优先级越高*/
void InsertTime(PCB *in) /*时间片队列*/
void InsertFinish(PCB *in) /*时间片队列*/
void PrioCreate() /*优先级输入函数*/
void TimeCreate() /*时间片输入函数*/
void Priority() /*按照优先级调度*/
void RoundRun() /*时间片轮转调度*/
int main(void)
{
char chose
printf("请输入要创建的进程数目:\n")
scanf("%d",&num)
getchar()
printf("输入进程的调度方法：(P/R)\n")
scanf("%c",&chose)
switch(chose)
{
case 'P':
case 'p':
PrioCreate()
Priority()
break
case 'R':
case 'r':
TimeCreate()
RoundRun()
break
default:break
}
Output()
return 0
}
void GetFirst() /*取得第一个就绪队列节点*/
{
run = ready
if(ready!=NULL)
{
run ->state = 'R'
ready = ready ->next
run ->next = NULL
}
}
void Output()/*输出队列信息*/
{
PCB *p
p = ready
printf("进程名\t优先级\t轮数\tcpu时间\t需要时间\t进程状态\t计数器\n")
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count)
p = p->next
}
p = finish
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count)
p = p->next
}
p = run
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count)
p = p->next
}
}
void InsertPrio(PCB *in) /*创建优先级队列，规定优先数越小，优先级越低*/
{
PCB *fst,*nxt
fst = nxt = ready
if(ready == NULL) /*如果队列为空，则为第一个元素*/
{
in->next = ready
ready = in
}
else /*查到合适的位置进行插入*/
{
if(in ->prio >= fst ->prio) /*比第一个还要大，则插入到队头*/
{
in->next = ready
ready = in
}
else
{
while(fst->next != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/
{
nxt = fst
fst = fst->next
}
if(fst ->next == NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/
{
in ->next = fst ->next
fst ->next = in
}
else /*插入到队列中*/
{
nxt = in
in ->next = fst
}
}
}
}
void InsertTime(PCB *in) /*将进程插入到就绪队列尾部*/
{
PCB *fst
fst = ready
if(ready == NULL)
{
in->next = ready
ready = in
}
else
{
while(fst->next != NULL)
{
fst = fst->next
}
in ->next = fst ->next
fst ->next = in
}
}
void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/
{
PCB *fst
fst = finish
if(finish == NULL)
{
in->next = finish
finish = in
}
else
{
while(fst->next != NULL)
{
fst = fst->next
}
in ->next = fst ->next
fst ->next = in
}
}
void PrioCreate() /*优先级调度输入函数*/
{
PCB *tmp
int i
printf("输入进程名字和进程所需时间：\n")
for(i = 0i <numi++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc")
exit(1)
}
scanf("%s",tmp->name)
getchar() /*吸收回车符号*/
scanf("%d",&(tmp->needtime))
tmp ->cputime = 0
tmp ->state ='W'
tmp ->prio = 50 - tmp->needtime /*设置其优先级，需要的时间越多，优先级越低*/
tmp ->round = 0
tmp ->count = 0
InsertPrio(tmp) /*按照优先级从高到低，插入到就绪队列*/
}
}
void TimeCreate() /*时间片输入函数*/
{
PCB *tmp
int i
printf("输入进程名字和进程时间片所需时间：\n")
for(i = 0i <numi++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc")
exit(1)
}
scanf("%s",tmp->name)
getchar()
scanf("%d",&(tmp->needtime))
tmp ->cputime = 0
tmp ->state ='W'
tmp ->prio = 0
tmp ->round = 2 /*假设每个进程所分配的时间片是2*/
tmp ->count = 0
InsertTime(tmp)
}
}
void Priority() /*按照优先级调度，每次执行一个时间片*/
{
int flag = 1
GetFirst()
while(run != NULL) /*当就绪队列不为空时，则调度进程如执行队列执行*/
{
Output() /*输出每次调度过程中各个节点的状态*/
while(flag)
{
run->prio -= 3/*优先级减去三*/
run->cputime++/*CPU时间片加一*/
run->needtime--/*进程执行完成的剩余时间减一*/
if(run->needtime == 0)/*如果进程执行完毕，将进程状态置为F，将其插入到完成队列*/
{
run ->state = 'F'
run->count++/*进程执行的次数加一*/
InsertFinish(run)
flag = 0
}
else /*将进程状态置为W，入就绪队列*/
{
run->state = 'W'
run->count++/*进程执行的次数加一*/
InsertTime(run)
flag = 0
}
}
flag = 1
GetFirst() /*继续取就绪队列队头进程进入执行队列*/
}
}
void RoundRun()/*时间片轮转调度算法*/
{
int flag = 1
GetFirst()
while(run != NULL)
{
Output()
while(flag)
{
run->count++
run->cputime++
run->needtime--
if(run->needtime == 0) /*进程执行完毕*/
{
run ->state = 'F'
InsertFinish(run)
flag = 0
}
else if(run->count == run->round)/*时间片用完*/
{
run->state = 'W'
run->count = 0 /*计数器清零，为下次做准备*/
InsertTime(run)
flag = 0
}
}
flag = 1
GetFirst()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）