XXXX
大學信息學院
課程設計報告
起止日期:
xxxxxxx
系別
xxxx
班級
x
學號
xxxxxx
姓名
xxxxxx
完成日期
xxxxxxx
實
驗
題
目
優先隊列的實現
自
我
評
價
功
能
算法設計
獨立完成情況
算法熟練程度
測試
通過
成功
失敗
獨立
幫助
掌握
了解
不懂
插入算法
√
√
√
√
刪除算法
√
√
√
√
查找算法
√
√
√
√
個
人
總
結
優先隊列并非
F I F O
結構,優先隊列中元素出隊列的順序由元素的優先級決定。從優先隊列
查找和刪除元素是根據優先權高或低的次序,
而不是元素進入隊列的次序,
又因為要求控制其查
找、插入、刪除操作的算法時間復雜度為
O
(
logn
)
,故用到了堆排序。隊列元素的存儲則用到
了循環隊列,
除去幾個有關進出隊的函數外,
算法中調用的函數基本上都是以前所做實驗用過的,
所以大大省去了編寫代碼的時間。
通過這次實驗接觸到了新的概念,
完成實驗要求的全部功能并
運行通過,算法有一定的新意,程序代碼符合書寫規范,實驗報告敘述清晰完整,有詳盡的分析
和總結。
教師簽名:
xxxxx
題目
1
實驗報告
1
.
數據結構定義
因為該算法需要用到循環隊列、堆和線性表,因此采用以下數據類型:
typedef struct
{
QElemType *base; //
初始化的動態分配存儲空間
int front; //
頭指針
,
若隊列不空
,
指向隊列頭元素
int rear; //
尾指針
,
若隊列不空
,
指向隊列尾元素的下一個位置
}SqQueue;//
循環隊列
typedef struct
{
int *elem;
int length;
int listsize;
}SqList;//
堆排序
2
.
算法說明
void HeapAdjust(int flag,SqList &H,int s,int m)
void HeapSort(int flag,SqList &H)//
對
H
進行堆排序
;
Status InitQueue(SqQueue &Q)//
構造一個空隊列
Q
,該隊列預定義大小為
MAXQSIZE;
Status EnQueue(SqQueue &Q,QElemType e) //
插入元素
e
為
Q
的新的隊尾元素
;
Status DeQueue(SqQueue &Q, QElemType &e) //
若隊列不空
,
則刪除
Q
的隊頭元素
,
用
e
返回其值
,
并返回
OK;
否則返回
ERROR;
Status GetHead(SqQueue Q, QElemType &e)//
若隊列不空,
則用
e
返回隊頭元素,
并返回
OK
,否則返回
ERROR;
Status QueueLength(SqQueue Q) //
返回
Q
的元素個數
;
Status
QueueTraverse(SqQueue
Q)//
若隊列不空,則從隊頭到隊尾依次輸出各個隊列元
素,并返回
OK
;否則返回
ERROR.
3
.
用戶使用說明
運行程序,根據屏幕上的文字提示一步步操作。
4
.
個人測試結果(截圖)
部分測試結果截圖