优先队列实验报告

优先队列实验报告

一、使用说明

1.开始编译后，因为优先队列未创建，要求输入队列元素个数与各元素值，以此新建并初始化优先队列。

2.优先队列创建成功后，出现选择菜单，有查找、插入、删除、显示四个功能。

3.查找是查找值最大的元素，并询问是否删除此元素；删除操作用来删除该元素；插入是通过输入一个元素值来将它加在队列底端；显示操作显示自动排列后的各个元素值。 二、算法实现

1.本实验构造静态顺序存储结构来存储优先队列的元素，此静态顺序存储结构有两个结构成员：ElemType *elem; int length; 一个为数据元素存储空间基址，另一个为表长。 2.新建并初始化优先队列后，会调整优先队列的元素排列。执行插入后，也会如此做。 3.所谓调整排列，就是利用大顶堆，将元素值较大的元素不断上调，直到元素值最大的元素调至大顶堆顶部。

4.选择删除后，返回队头第一个元素后，静态顺序表元素从第二个开始依次前移，覆盖第一个元素。若队列清空，会给与提示。

5.插入操作是将新元素先插入队列底端，再进行调整。

6.查找最大值：因为优先队列中队头就是最大值，返回此值即可。 三、总结

1.优先队列实质是堆，堆通过模拟二叉树的结构（实质是静态顺寻表）来进行调整。 2.优先队列可通过定义的不同决定成为最小或最大优先队列。

3.优先队列只允许在底端加入元素，并从顶端取出元素，除此之外别无其它存取元素的途径。 4.新添加的元素并非依照被推入的次序排列，而是自动依照元素的权值排列。

源代码：

#include\等 */ #include\

#include\

typedef int ElemType;

typedef struct /*静态查找表的顺序存储结构 */

{ ElemType *elem; /* 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 */ int length; /* 表长度 */ }SSTable;

void Creat_Seq(SSTable &ST,int n)

{ /* 操作结果: 构造一个含n个数据元素的静态顺序查找表ST(数据来自数组r) */ int i,temp; ST.elem=(ElemType *)malloc((n+1) * sizeof(ElemType)); /* 动态生成n个数据元素空间(0号单元不用) */

if(!(ST).elem) { printf(\

exit(0);

} /*内存分配失败结束程序*/

for(i=1;i<=n;i++) { scanf(\ *(ST.elem+i)=temp; /* 依次赋值给ST */ }

ST.length=n; }

void printf(SSTable &ST) { }

void heapadjust(SSTable &ST,int s,int m) {

int rc,j;

rc= ST.elem[s]; for(j=2*s;j<=m;j*=2) {

if(j

if(ST.elem[j]

break;

ST.elem[s]=ST.elem[j]; for(i=1;i<=ST.length;i++) }

printf(\int i;

if(ST.length==0) printf(\队列已被清空，请插入新元素。\\n\else { printf(\优化队列元素值依次为:\

s=j; }

ST.elem[s]=rc;

}

void heap(SSTable &ST) { int j,i;

for(i=ST.length/2;i>0;i--)

heapadjust(ST,i,ST.length);

}

void heapsort(SSTable &ST)

{ /* 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为 */ /* 该元素在表中的位置，否则为0。算法9.1 */

int j,i;

for(i=ST.length/2;i>0;i--)

heapadjust(ST,i,ST.length); // }

void insert(SSTable &ST,int add) { }

void deletequeue(SSTable &ST) {

ST.elem[++ST.length]=add; printf(ST);

for(i=ST.length;i>1;i--) {

j=ST.elem[1];

ST.elem[1]=ST.elem[i]; ST.elem[i]=j;

heapadjust(ST,1,i-1);

}

else { } }

int i,j;

if(ST.length==1) { ST.elem[1]=NULL; ST.length--; printf(\队列已清空。\\n\}

j=ST.elem[1];

ST.elem[1]=ST.elem[ST.length]; ST.elem[ST.length]=j;

heapadjust(ST,1,ST.length-1);

ST.length--;

printf(\该元素已删除。\\n\

int main() {

printf(\\\n\ printf(\ 欢迎进入优化队列世界 | \\n\ printf(\\\n\ printf(\ printf(\ printf(\

/*创建一个新的优化队列*/

printf(\您还未创建优化队列，请创建！\\n\

printf(\请输入新队列元素个数：\

SSTable ST;

int n,num,add; char c;

//

scanf(\

printf(\请输入各元素的值(整数)：\Creat_Seq(ST,n);

heap(ST);

///选择功能

printf(\优化队列已创建,\printf(ST);

printf(\请按回车键以继续。\\n\scanf(\scanf(\

system(\

printf(\请选择以下功能\\n\

printf(\ <<<< <<< ☆☆☆☆☆☆☆☆☆☆ >>>> >>>> >>>>\\n\

<<<< <<<< <<<< <<<<

<<< >>>> >>>> >>>>\\n\<<< 1.插入新元素 >>>> >>>> >>>>\\n\<<< 2.查找最大值元素 >>>> >>>> >>>>\\n\<<< 3.删除最大值元素 >>>> >>>> >>>>\\n\

printf(\ printf(\ printf(\ printf(\

printf(\ <<<< <<< 4.显示各元素值 >>>> >>>> >>>>\\n\ // printf(\ <<<< <<< 5.根据条件查询 >>>> >>>> >>>>\\n\ printf(\ <<<< <<< 0.退出 >>>> >>>> >>>>\\n\ ///

scanf(\ while(num) {

switch(num) {

case 1:printf(\请输入要插入的元素的值：\ //

//

scanf(\ system(\ insert(ST,add); heap(ST);

printf(\ <<<< <<< >>>> >>>> >>>>\\n\printf(\ <<<< <<< ☆☆☆☆☆☆☆☆☆☆ >>>> >>>> >>>>\\n\